comparative魅族mx

HybridAdaptiveWebServiceSelectionwithSAWSDL-MXandWSDL-AnalyzerMatthiasKlusch,PatrickKapahnke,andIngoZinnikusGermanResearchCenterforArticialIntelligenceStuhlsatzenhausweg3,Saarbr¨ucken,Germany{klusch,patrick.
kapahnke,ingo.
zinnikus}@dfki.
deAbstract.
Inthispaper,wepresentanadaptive,hybridsemanticmatchmakerforSAWSDLservices,calledSAWSDL-MX2.
Itdeterminesthreekindsofsemanticservicesimilaritywithagivenservicerequest,thatarelogic-based,text-basedandstructuralsimilarity.
Inparticular,thedegreeofstructuralservicesimilarityiscomputedbytheWSDL-Analyzertool[12]bymeansofXMLStreeeditdistancemeasurement,string-basedandlexicalcomparisonoftherespectiveXML-basedWSDLservices.
SAWSDL-MX2thenlearnstheoptimalaggregationofthesedierentmatchingdegreesoverasubsetofatestcollectionSAWSDL-TC1basedonabinarysupportvectormachine-basedclassier.
Finally,wecomparetheretrievalperformanceofSAWSDL-MX2withanon-adaptivematchmakervariantSAWSDL-MX1[1]andthestraightforwardcombinationofitslogic-basedonlyvariantSAWSDL-M0withWSDL-Analyzer.
1IntroductionAsaW3CrecommendationdatedAugust28,2007,theSAWSDL1specicationproposesmechanismstoenrichWebservicesdescribedinWSDL2(WebServiceDescriptionLanguage)withsemanticannotations.
Amongothers,onegoaloftheseadditionaldescriptionsistosupportintelligentagentsinautomatedserviceselection,ataskwhichishardtoaccomplishusingpuresyntacticinformationofserviceprolesbasedmainlyonXML-Schemadenitions.
Typicalapplicationscenariosthatrequireorbenetfromaservicematchmakingcomponentincludeforexamplenegotiationandcoalitionformingamongagentsandautomatedorassistedservicecomposition.
ThersthybridsemanticservicematchmakerSAWSDL-MX1forSAWSDLweproposedin[1]adoptedtheideasofourhybridmatchmakersOWLS-MXandWSMO-MX(see[5,3])forOWL-S,respectively,WSML.
However,SAWSDL-MX1focusedonsemanticannotationsofthesignaturebutnotontheXMLstructureoftheWebserviceasawhole.
Thisistakeninto1http://www.
w3.
org/TR/sawsdl/2http://www.
w3.
org/TR/wsdl/,http://www.
w3.
org/TR/wsdl20/L.
Aroyoetal.
(Eds.
):ESWC2009,LNCS5554,pp.
550–564,2009.
cSpringer-VerlagBerlinHeidelberg2009HybridAdaptiveWebServiceSelection551accountbytheWSDL-Analyzertoolpresentedin[12]bymeansofmeasuringtheXMLtreeeditdistancesbetweengivenpairofservicesthroughXMLtypecompatibility,token-basedtextandlexicalsimilaritymeasurements.
Besides,SAWSDL-MX1combineslogic-basedandtext-similaritybasedmatchinginaxedmanner:Itappliesvelogicalmatchingltersandranksserviceoersthatsharethesamelogicalmatchingdegreewithrespecttoagivenrequestaccordingtotheirtextsimilarityvalue.
ThehybridvariantSAWSDL-M0+WAdoesthesameasSAWSDL-MX1exceptthatitsrankingofserviceswiththesamelogicalmatchingdegreeisaccordingtotheirstructuralsimilarityvalueascomputedbytheWSDL-Analyzer.
Finally,theadaptivehybridvariantSAWSDL-MX2com-putesthreekindsofsemanticmatching,logical,textandstructuralsimilarity-based.
Inaddition,itlearnstheoptimalaggregationofthesedierenttypesofsemanticmatchingtodecideonthesemanticrelevanceofaservicetoagivenrequest.
Onemajorquestionconcernsthepracticalapplicabilityofthesedierentmatchmakersingeneral,notrestrictedtosomegivendomain-specicand/orverysmall-sizedscenario,bymeansoftheirretrievalperformanceoveragiveninitialtestcollection,SAWSDL-TC1,thatconsistsofmorethan900SAWSDLservicesfromdierentapplicationdomains.
Theresultsofourexperimentsshowsthatallhybridmatchmakervariantsoutperformthesinglematchingtypevari-ants(logic-basedortextorstructuralonly)intermsofprecision,whiletheperformanceofallthreehybridvariantsdonotsignicantlydierwithrespecttoSAWSDL-TC1.
Theremainderofthepaperisstructuredasfollows.
AfterabriefintroductiontoSAWSDLinsection2,thematchingapproachofthenon-adaptivematch-makerSAWSDL-MX1isrecapitulatedinsection3.
Section4presentsthestruc-turalmatchingofWSDLservicesperformedbytheWSDL-Analyzertool.
TheadaptiveaggregationofmatchingresultsbasedonabinarySVM-basedclassierbyournewadaptivematchmakerSAWSDL-MX2isdescribedinsection5.
Re-sultsofourexperimentalevaluationoverthegiventestcollectionSAWSDL-TC1intermsofrecall,(macro-)averagedprecisionandaveragequeryresponsetimeareshowninsection6.
Wecommentonrelatedworkinsection7,andconcludeinsection8.
2ServiceDescriptionsinSAWSDLSAWSDLisdesignedasanextensionofWSDLenablingserviceproviderstoenrichtheirservicedescriptionswithadditionalsemanticinformation.
Forthispurpose,thenotionsofmodelreferenceandschemamappinghavebeenintro-ducedintermsofXMLattributes(tags)thatcanbeaddedtoalreadyexistingWSDLservicedescriptionelementsasdepictedingure1.
SemanticannotationofWSDLservices.
Moreprecisely,thefollowingex-tensionsareusedforsemanticannotationsofWSDLservices:552M.
Klusch,P.
Kapahnke,andI.
ZinnikusFig.
1.
SAWSDLextensionsofWSDLinterfacecomponents–modelReference:AmodelReferencepointstooneoremoreconceptswithequallyintendedmeaningexpressedinanarbitrarysemanticrepresentationlanguage.
TheyareallowedtobedenedforeveryWSDLandXMLSchemaelement,thoughtheSAWSDLspecicationdenestheiroccurrenceonlyinWSDLinterfaces,operations,faultsaswellasXMLSchemaelements,complextypes,simpletypesandattributes.
Thepurposeofamodelreferenceismainlytosupportautomatedservicediscovery.
–liftingSchemaMapping:Schemamappingsareintendedtosupportautomatedserviceexecutionbyprovidingrulesspecifyingthecorrespondencesbetweensemanticannotationconceptsdenedinagivenontology(the"upper"level)totheXMLSchemarepresentationofdataactuallyrequiredtoinvoketheWebservice(the"lower"level),andviceversa.
AliftingSchemaMappingdescribesthetransformationfromthe"lower"levelinXMLSchemauptotheontologylanguageusedforsemanticannotation.
–loweringSchemaMapping:TheattributeloweringSchemaMappingdescribesthetransformationfromthe"upper"levelofagivenontologytothe"lower"levelinXMLSchema.
However,thecurrentspecicationofSAWSDLmodelreferencesimposesquitesomeproblemsforsemanticservicematchmakingasfollows.
Nouniform,formalontologylanguage.
UnlikeOWL-SorWSML,thespeci-cationofSAWSDLdoesnotrestrictthedevelopertoanyuniform,formalontol-ogylangagelikeOWLorWSMO.
Asaresult,anymeanofautomatedsemanticserviceselectionhastocopewiththesemanticinteroperabilityproblemsofhet-erogeneousdomainontologiesandontologylanguages.
Whilethisproblemcouldberesolvedinsomecasesbymeansofsyntacticandsemantictransformations-suchasforOWL-DLandWSML-DL-itremainshardingeneral.
Multiplereferencestodierentontologies.
Thesameholdsespeciallyforreferencestodierentkindsofontologieslikeplainorstructuredtextles,HybridAdaptiveWebServiceSelection553annotatedimagearchive,orlogictheories.
Infact,SAWSDLallowsmultiplereferencestodierentkindsofontologiesforannotatingeventhesameservicedescriptionelement.
HowshallanysemanticservicematchmakerknowhowtoprocessthemtounderstandthesemanticsofthatsingleelementAreitsan-notationsmeanttobecomplementaryorequivalentIfcomplementary,howtoaggregatethem,ifequivalent,whichonetoselectbestforfurtherprocess-ingThisopensupawiderangeofpragmaticsolutionsforSAWSDLservicematching.
Top-levelvsbottom-levelannotations.
AccordingtotheSAWSDLspec-ication,semanticannotationbymeansofso-calledtop-levelannotationandbottom-levelannotationshallbeconsideredbothindependentfromeachotherandapplicableatthesametime.
Whiletop-levelannotationreferstotheanno-tationofacomplextypeorelementdenitionofamessageparameterbymeansofamodelreferenceasawhole,anybottom-levelannotationfocusesonlyonasingle(atomic)XMLelement.
Unfortunately,itremainsunclearhowtoevalu-ateamatchingbetweentop-levelandlow-levelannotatedparameters,orwhichonetopreferifbothlevelsofannotationareavailableforacomplexservicede-scriptionelement.
Inaddition,elementandtypedenitionspecifyingamessagecomponentcanbeannotatedatthesametime.
PragmaticassumptionsforSAWSDLservicematching.
RegardingtheabovementionedproblemsofSAWSDLservicematching,thefollowingprag-maticassumptionsweremadeforusingourSAWSDL-MXmatchmakervariantsSAWSDL-M0+WA,SAWSDL-MX1,andSAWSDL-MX2:–Referencestoformalontologiesindescriptionlogicsonly.
Thecurrentimple-mentationofSAWSDL-MXperformsreasoningonlogic-basedannotationsinOWL-DL3butisnotrestrictedtoit:Itsupportsotherdescriptionlogics(DL)iftheyaretranslatedintothestandardDIG1.
14interfacerepresenta-tionformat.
–Onlytop-levelsemanticannotationsofserviceparametersareconsideredforservicematching.
However,anydirecttop-levelannotationofaWSDLmessageparthaspriorityoverthetop-levelannotationoftherespectivelyreferenced(andlikewiselyannotated)XML-Schemaelementortype.
–Incaseofmultipleannotationsofasingleelementatthesamelevel,oneofthemisselecteduniformlyatrandom.
Onlysemanticannotationsofservice(IO)parametersareconsidered,butnotannotationsofentireoperationsorinterfaces.
However,theproposedmatchingvariantscouldeasilybeadoptedforthispurpose.
Inthefollowingsections,wedescribeeachofthesedierentSAWSDLmatch-makervariantsandresultsoftheircomparativeexperimentalevaluationofperformance.
3http://www.
w3.
org/2004/OWL/4http://dig.
sourceforge.
net/554M.
Klusch,P.
Kapahnke,andI.
Zinnikus3SAWSDL-MX:LogicandTextSimilarity-BasedSignatureMatchingInthissection,wedescribethehybridservicesignaturematchingperformedbybothSAWSDL-MXmatchmakervariants,thenon-adaptiveSAWSDL-MX1andtheadaptiveSAWSDL-MX2.
Thelogic-basedonlyvariantofSAWSDL-MXiscalledSAWSDL-M0.
Servicerequestsandoersarepresumedtobeformu-latedinSAWSDL,eachcomprisingoneormultipleoperationswithsemanticallyannotatedsignatures.
3.
1HybridServiceInterfaceMatchingForeachpairofserviceoerOandservicerequestR,thematchmakerdeterminestheirsemanticsimilaritybyevaluatingeverycombinationoftheiroperationsintermsofeitherlogic-basedonly(SAWSDL-M0)ortextsimilarity-basedonlyoperationmatching,orboth(SAWSDL-MX1,SAWSDL-MX2).
Theprocessoflogic-basedandtextsimilarity-based(service)operationmatchingisdescribedinmoredetailbelow.
Todetermineaninjectivemappingbetweenserviceoerandrequestoper-ationsthatisoptimalregardingtheirmatchingdegrees,SAWSDL-MXappliesbipartiteoperationgraphmatching.
Nodesinthegraphrepresenttheoperationsandtheweightededgesarebuiltfrompossibleone-to-oneassignmentswiththeirweightsderivedfromthecomputeddegreeof(logical/text/hybrid)operationmatch.
Ifthereexistssuchamapping,thenitisguaranteedthatthereexistsanoperationoftheserviceoerforeveryrequestedoperation,disregardingthequalityoftheirmatchingatthispoint.
Forexample,considertheservicerequestandserviceoergiveningure2.
EveryrequestoperationROi(withi∈{1,2})iscomparedtoeveryadvertise-mentoperationOj(withj∈{1,2,3})withrespecttologic-basedltersdenedinthenextsection.
Inthisexample,RO1exactlymatcheswithO1,butfailsforO2andO3.
O3isaweakerplug-inmatchforRO2(thesubsumed-bymatchofRO2withO2isevenweakerthanaplug-inmatch).
Thebest(max)assignmentofmatchingoperationsis{RO1,O1,RO2,O3}.
Oneconservative(min-max)optionofdeterminingthematchingdegreebe-tweenserviceoerandrequestbasedontheirpairwiseoperationmatchingsistoassumetheworstresultofthebestoperationmatchings.
Inotherwords,weguaranteeaxedlowerboundofsimilarityforeveryrequestedoperation-whichiswhatSAWSDL-MXisdoing.
Intheexampleshowningure2,theserviceoerisconsideredaplug-inmatchfortherequest.
Othernotyetimplementedpossibilitieswouldbetomergetheoperationmatchingresultsbasedontheiraveragesyntacticsimilarityvaluesandtoprovidemoredetailedfeedbacktotheuserontheoperationmatchingsinvolved.
3.
2Logic-BasedOperationMatchingThelogic-basedoperationmatchingbySAWSDL-MXbasesonthesuccessiveapplicationofthefollowingfourltersofincreasingdegreeofrelaxationtoaHybridAdaptiveWebServiceSelection555Fig.
2.
InterfacelevelmatchingofSAWSDL-MXgivenpairserviceoeroperationOOandservicerequestOR:Exact,Plug-in,SubsumesandSubsumed-by.
TheseltershavebeenoriginallydevelopedforthematchmakerOWLS-MXbutextendedwithbipartiteconceptgraphmatchingtoensureaninjectivemappingbetweenI/Oconceptsofserviceoerandrequest,wheneverpossible.
AsanoverviewtodescriptionlogicandDLreasoning,wereferto[9].
Thesetslgc(c)andlsc(c)containtheleastgenericconceptsofc(directparent)andtheleastspecicconceptsofc(directchild),respectively.
Exactmatch:ServiceoperationOOexactlymatchesserviceoperationOR(injectiveassignmentMin:m∈Min:m1∈in(OO)∧m2∈in(OR)∧m1≡m2)∧(injectiveassignmentMout:m∈Mout:m1∈out(OR)∧m2∈out(OO)∧m1≡m2).
Thereexistaone-to-onemappingofperfectlymatchinginputsaswellasperfectlymatchingoutputs.
Assumingthatanoperationfullllsarequestersneedifeveryinputcanbesatisedandeveryrequestedoutputisprovided,theassignmentsonlyrequiretobeinjective(butnotbijective),thusadditionalavailableinformationnotrequiredforserviceinvocationandaddi-tionalprovidedoutputsnotexplicitlyrequestedaretolerated.
Plug-inmatch:ServiceoperationOOplugsintoserviceoperationOR(in-jectiveassignmentMin:m∈Min:m1∈in(OO)∧m2∈in(OR)∧m1m2)∧(injectiveassignmentMout:m∈Mout:m1∈out(OR)∧m2∈out(OO)∧m2∈lsc(m1)).
Thelterrelaxestheconstraintsoftheexactmatchinglterbyaddi-tionallyallowinginputconceptsoftheserviceoertobearbitrarilymoregeneralthanthoseoftheservicerequest,andadvertisementoutputconceptstobedirectchildconceptsofthequeriedones.
Subsumesmatch:ServiceoperationOOsubsumesserviceoperationOR(injectiveassignmentMin:m∈Min:m1∈in(OO)∧m2∈in(OR)∧m1m2)∧(injectiveassignmentMout:m∈Mout:m1∈out(OR)∧m2∈556M.
Klusch,P.
Kapahnke,andI.
Zinnikusout(OO)∧m1m2).
Thislterfurtherrelaxesconstraintsbyallowingserviceoeroutputstobearbitrarilymorespecicthantherequestoutputs(asopposedtotheplug-inlter,wheretheyhavetobedirectchildren).
Thus,aplug-incanbeseenasspecialcaseofasubsumesmatchresultinginamorene-grainedviewattheoverallserviceranking.
Subsumed-bymatch:ServiceoperationOOissubsumedbyserviceopera-tionOR(injectiveassignmentMin:m∈Min:m1∈in(OO)∧m2∈in(OR)∧m1m2)∧(injectiveassignmentMout:m∈Mout:m1∈out(OR)∧m2∈out(OO)∧m2∈lgc(m1)).
Theideaofthesubsumed-bymatchinglteristodeterminetheserviceoersthattherequesterisabletoprovidewithallrequiredinputsandatthesametimedeliveroutputsthatareatleastcloselyrelatedtotherequestedoutputsintermsoftheinferredconceptclassication.
Thematchingdegreeoffailistrueifandonlyifnoneofthematchingltersdenedabovesucceed.
Asaresult,servicesarerankedaccordingtotheirmatch-ingdegreeinthefollowingdecreasingorder:exact>plug-in>subsumes>subsumed-by>fail.
SAWSDL-M0.
Thelogic-basedonlymatchmakervariantSAWSDL-M0appliestheabovelogicalmatchingltersonly,andranksserviceoersthatsharethesamelogicalmatchingdegreewithrespecttoagivenrequestuniformlyatrandom.
3.
3TextSimilarity-BasedOperationMatchingThehybridvariantsofSAWSDL-MXalsoperformcomplementarytextsimilarity-basedmatchingbymeansofclassicaltoken-basedtextsimilaritymea-suresLoss-of-Information,ExtendedJaccard,CosineandJensen-Shannonasim-plemented,forexample,inSimPack5.
Forthispurpose,thesignaturesofbothrequestandoerareconsideredastextsuchthatthedegreeofsemanticsimi-larityismeasuredintermsoftheiraveragedtextsimilarity.
Moreconcrete,eachsemanticservicesignatureistransformedintoapairofweightedkeywordvectorsforinput,respectively,output-accordingtotheclassi-calvectorspacemodelofinformationretrieval.
Forthispurpose,eachinputcon-ceptislogicallyunfoldedinthesharedontology(asdenedforstandardtableauxreasoningalgorithms)andconcatenatedwithallotherstoacomplexlogicalex-pressioncontainingonlyprimitivecomponentsandlogicaloperators.
Thisex-pressionistreatedasmeretextstringbeingprocessedtoaTFIDFweightedkeywordvector;thesameisdonewithserviceoutputconcepts.
TheTFIDFtermweightingvaluesarecomputedovertwodistincttextindicesdependingonwhetherserviceinputsoroutputsarecompared.
SAWSDL-MX1.
ThehybridsemanticservicematchmakerSAWSDL-MX1ap-pliesthelogicalmatchingltersmentionedaboveandranksserviceoersthat5http://www.
i.
uzh.
ch/ddis/research/semweb/simpack/HybridAdaptiveWebServiceSelection557sharethesamelogicalmatchingdegreewithrespecttoagivenrequestaccordingtotheirtextsimilarityvalue.
4WSDL-Analyzer:StructuralWSDLMatchingTheWSDL-Analyzer(WA)toolintroducedin[12]performsastrucrualonlymatchingofWSDL1.
1services.
Infact,itignoresthesemanticannotationsofSAWSDLdescriptionsandtreatsaSAWSDLdescriptionasamereWSDLde-scription.
TheWAtooldetectssimilaritiesanddierencesbetweenWSDLlesandcanbeusedtondalistofnon-logic-basedsemanticallyrelevantWebser-vices.
SinceitssimilarityalgorithmproducesamappingbetweenWSDLservicedescriptions,thetoolcanalsobeusedforsupportingmediationbetweenservices.
Moreconcrete,theWAtoolexploitsvarioustypesofschemainformationsuchaselementnames,datatypesandstructuralproperties,andcharacteristicsofdatainstances,aswellasbackgroundknowledgefromdictionariesandthesauri.
ThesimilarityalgorithmcalculatesthesimilaritybetweentheXMLstructuresofarequestedandacandidateservices,respectsthestructuralinformationofcomplexdatatypesandisexibleenoughtoallowforrelaxedmatchingaswellasmatchingbetweenparametersthatcomeindierentordersinserviceparameterlists.
ThecomparisonoftwoWSDLservicesisamulti-stepprocess.
Itstartsowith(1)thecomparisonoftheoperationsetsoeredbytheservices,whichisbasedon(2)thecomparisonofthestructuresoftheoperationsinputandoutputmessages,which,inturn,isbasedon(3)thecomparisonofthedatatypesoftheobjectscommunicatedbythesemessages.
TherecursivestructuralmatchingoftwoXML-basedWSDLservicedescriptionsisperformedasfollows.
AWSDLdescriptionisrepresentedasalabelledtreewhereleafnodesarethebasicbuilt-indatatypesprovidedbytheXMLschemaspecication6.
LetL={l1,l2,.
.
.
,ln}beasetoflabels.
AlabelledtreeT=(N,E,root(T),)isanacyclic,connectedgraphwith:–N={n1,n2,.
.
.
,nn}isasetofnodes.
–EN*Nisasetofedges.
–root(T)therootofthetree.
–:N→LisafunctionwhichassignsalabeltoeachnodewithbasicdatatypesDL.
TheprocessofcalculatingthesimilarityoftwotreesT1andT2startswiththerootsroot(T1)androot(T2),andtraversesthesetreesrecursively:Fora∈NT1andb∈NT2docompute,sim(a,b)=ωnamesimname((a),(b))+ωstructmax(i,j(sim(ni,mj))),(a),(b)∈Dsimtype((a),(b)),(a),(b)∈D.
6http://www.
w3c.
org/TR/xmlschema-2/558M.
Klusch,P.
Kapahnke,andI.
Zinnikuswhere(a,ni)∈ET1,(b,mj)∈ET2andi,j(ni,mj)denotesthesumofpairssim(ni,mj)for1≤i≤card(n)and1≤j≤card(m)suchthateachniandmjoccuratmostonceinthesum.
Ifcard(n)=card(m),someofthenodescannotbematched.
Weightsωnameandωstructareusedtoeitherincreaseorde-creasetheeectofelement(label)nameorstructuralsimilarity.
Computationoftypesimilaritysimtypebasesonagiventypecompatibilitytablewhichassignsavaluetoeachcombinationofbasicdatatypes.
Thesimilarityoflabelssimnamecanbecalculatedwithdierentmeasuressuchasstringeditdistance,substringcontainmentorWordNet7similarity(semanticproximity).
Inordertoimprovethemappingresults,weusedsubstringmatchingandWordNet.
Experimentsshowedthatespeciallyinratherstandardizedareastheresultsarebetterthanwithpuredatatypemapping.
SAWSDL-M0+WA.
ThehybridsemanticservicematchmakerSAWSDL-M0+WAappliesthelogicalmatchingltersonly,andranksserviceoersthatsharethesamelogicalmatchingdegreewithrespecttoagivenrequestaccordingtotheirdegreeofstructuralsimilarityascomputedbytheWSDL-Analyzer.
5SAWSDL-MX2:AdaptiveMatchingAggregationInspiredby[2,4],wedevelopedanadaptive,hybridsemanticservicematchmakerSAWSDL-MX2.
Thismatchmaker(a)separatelycomputesthreedierentkindsofsemanticservicematchingdegrees,thatarelogical,textandstructuralmatch-ing(eachofthemasdescribedinprevioussections),andthen(b)learnsoveragiventraingsethowtobestaggregatethemtodecideonthesemanticrelevance(ranking)ofaservicetoagivenrequest.
Forthelatterpurpose,SAWSDL-MX2exploitsaSupportVectorMachine(SVM)tolearnabinaryclassicationfunc-tion,whichischaracterizedbyahyperplaneinagivenfeaturespace.
Thisclas-sicationfunctionevaluatesforanygivenpairofserviceoerandrequest,theirbinaryrelevanceclassmembership,i.
e.
relevantorirrelevant,forthematchingproblemathand.
Forresultranking,thedistancesoftrainingsamplestothisplanearecomputed,andthentakenasreferencesimilarityvaluesfordecidingontherelevanceofunknownservices.
Moreconcrete,letX={0,1}5*[0,1]*[0,1]featurespacewithfeaturevec-torsxi=(f1,f2,f3,f4,f5,f6,f7)featurevectorswhereeachfeaturef1tof5representsthelogic-basedmatchingresultforaservicequery/oerpairinclud-ingfail,featuref6standsforthetext-basedsimilarityvalue,andf7forthestructuralsimilarityvaluecomputedbytheWSDL-Analyzer.
Forexample,thefeaturevector(0,0,1,0,0,0.
6,0.
7)representsthehybridsemanticmatchingre-sultcomputedbySAWSDL-MXasfollows:Alogicalsubsumesmatchwithtextsimilarityof0.
6andstructuralsimilarityof0.
7.
Theyivaluesofthetrainingsamplesequal1foranirrelevantserviceoergivenaquery,and1fortherele-vantcase.
Asusual,relevancesetsinthetestcollectionaresubjectivelydened7http://wordnet.
princeton.
edu/HybridAdaptiveWebServiceSelection559bydomainexperts.
Eventually,theinputtotheSVMofSAWSDL-MX2isasetoftrainingexamples{(x1,y1)xm,ym)}withxi∈Xandyi∈{1,1}.
TheresultofrunningaSVMonsuchinputisahyperplane,possiblyinahigherdimensionalspace,whichseparatestrainingexamplesinthefeaturespaceasgoodaspossiblewhilethedistanceofthenearestpointsofeachcategoryismaximizedtoavoidbiasedcategorization.
Thisisexpressedinthefollowingoptimizationproblem:minimizew,b,ζ:12wTw+CNi=1ζisubjectto1≤i≤N:yi(wTφ(xi)+b)≥1ζi,ζi≥0,wherewandbdenetheoptimalhyperplaneaccordingtothepreviouslymen-tionedcharacteristics.
TheerrortermCNi=1ζiisintroducedtoallowforout-liersinanon-linearseparabletrainingset,wheretheerrorpenaltyparameterCmustbespeciedbeforehand.
φisapredenedfunctionwhichmapsfea-turesintoahigherdimensionalspace.
Thereexistsalsoadualproblemde-scription,whichutilizesLagrangemultiplierstoexpressthehyperplaneaslinearcombinationofsupportvectors.
Thisformallowsfortheintroductionofaker-nelfunctionK,whichimplicitlydenestheoriginalfunctionφoftheprimalproblem.
Forourexperiments,theradialbasisfunction(RBF)hasbeenusedaskernel.
Itiscontrolledbyasecondparameterγandisdenedasfollows:K(xi,xj)=eγxixj2.
Tondagoodparametersetting(C,γ),then-foldcrossvalidationandgrid-searchapproachproposedin[13]hasbeenconducted.
FormoredetailsonSVM'singeneralandonthedualproblemsolving,werefertheinterestedreaderforexampleto[14].
ImplementationofSAWSDL-MX2.
SAWSDL-MX2hasbeenfullyimple-mentedinJavausingthesawsdl4j8API(handlingSAWSDLforWSDL1.
1)andtheOWLAPI9foraccesstoSAWSDLandOWLles,theDIG1.
1asstandardinterfacetohandleSHOIQknowledgebasequeries,andthePellet10reasonerasinferenceengineforlogic-basedmatchmaking.
AsSVMimplementation,weusedlibSVM11.
6EvaluationofPerformanceFortheadaptiveintegrationofSAWSDL-MXandWSDLAnalyzerbySAWSDL-MX2,aretrievalperformanceevaluationbasedonthewellknownmeasuresrecallandprecisionhasbeenconducted.
Toprovethestatisticalsignicanceofdierentmatchingvariants,weappliedtheFriedmanTest.
Inthefollowing,wefocus8http://knoesis.
wright.
edu/opensource/sawsdl4j/9http://owlapi.
sourceforge.
net/10http://pellet.
owldl.
com/11http://www.
csie.
ntu.
edu.
tw/cjlin/libsvm/560M.
Klusch,P.
Kapahnke,andI.
ZinnikusonthecomparativeevaluationofthethreeSAWSDL-MXvariantsdescribedinprevioussections:thenon-adaptiveSAWSDL-M0+WA,SAWSDL-MX1andtheadaptiveSAWSDL-MX2.
FormoredetailedresultsonSAWSDL-MX1alone,wereferto[1].
6.
1EvaluationSetupTheexperimentalevaluationofserviceretrievalperformanceisbasedontherstSAWSDLtestcollectionSAWSDL-TC1.
Itissemi-automaticallyderivedfromOWLS-TC2.
212usingtheOWLS2WSDL13tool,asthereiscurrentlynootherstandardtestcollectionforSAWSDLavailable.
OWLS2WSDLtransformsOWL-Sservicedescriptions(andconceptdenitionsrelevantforparameterdescrip-tion)toWSDLthroughsyntactictransformation.
Top-levelannotationstakenfromtheoriginalOWL-SdescriptionshavebeenaddedforXMLSchematypedenitionsusedtodescribemessageinputsandoutput.
Thecollectionconsistsofaround900Webservicescoveringdierentapplicationdomains:education,med-icalcare,food,travel,communication,economyandweaponry.
Italsoincludesasetofqueriesandbinaryrelevancesetssubjectivelyspeciedbydomainexperts.
Asoneresult,eachserviceinSAWSDL-TC1containsonlyasingleinterfacewithoneoperation.
AllautomaticallyderivedmodelreferencespointtoOWLontolo-gies.
Therefore,thistestcollectioncanonlybeseenasarstattempttowardsacommonlyagreedtestingenvironmentforSAWSDLservicediscoveryandourevaluationhastobeconsideredaspreliminary.
TheperformancetestshavebeenconductedonamachinewithWindows2000,Java6,1,7GHzCPUand2GBRAMusingtheSME2tool14forautomatedevaluation.
6.
2PerformanceTestsForretrievalperformanceevaluation,wemeasuredprecisionandrecall:Prec=|A∩B||B|andRec=|A∩B||A|,whereAisthesetofallrelevantdocuments,andBthesetofallretrieveddocumentsforarequest.
Further,wemeasuredthemacro-averagedprecision:Preci=1|Q|·q∈Qmax{Po|Ro≥Reci∧(Ro,Po)∈Oq},whereOqdenotesthesetofobservedpairsofrecall/precisionvaluesforqueryqwhenscanningtherankedservicesintheanswersetforqstepwisefortruepositivesintherelevancesetsofthetestcollection.
Forevaluation,theanswersetsarethesetsofallservicesregisteredatthematchmakerwhicharerankedwithrespecttotheir(totallyordered)matchingdegree.
Inotherwords,wecomputedthemeanofprecisionvaluesforanswersetsreturnedbythematchmakerforallqueriesinthetestcollectionatstandardrecalllevelsReci(0≤i<λ).
Ceilinginterpolationisusedtoestimateprecisionvaluesthatarenotobservedintheanswersetsforsomequeriesattheselevels;thatis,ifforsomequerythereisnoprecisionvalueatsomerecalllevel(duetotherankingof12http://projects.
semwebcentral.
org/projects/owls-tc/13http://projects.
semwebcentral.
org/projects/owls2wsdl/14http://projects.
semwebcentral.
org/projects/sme2/HybridAdaptiveWebServiceSelection561(a)integrationvs.
basicstrategies(b)dierentintegrationvariantsFig.
3.
Performanceofmatchingvariantsservicesinthereturnedanswersetbythematchmaker)themaximumprecisionofthefollowingrecalllevelsisassumedforthisvalue.
Thenumberofrecalllevelsfrom0to1(inequidistantstepsnλ,n=1.
.
.
λ)weusedforourexperimentsisλ=20.
TheAveragePrecision(AP)measureproducesasingle-valuedratingofamatchmakerforasinglequeryresult:AP=1|R||L|r=1isrel(r)count(r)r,whereRisthesetofrelevantitemspreviouslydenedbydomainexpertsfortheexaminedquery,Ltherankingofreturneditemsforthatquery,isrel(r)=1iftheitematrankrisrelevantand0otherwiseandcount(r)thenumberofrelevantitemsfoundintherankingwhenscanningtop-down,i.
e.
count(r)=ri=1isrel(i).
TheAPmeasureisindependentfromthewayandsizeofranking.
Asarstexperiment,wecomparedtheretrievalperformanceofSAWSDL-M0+WAtothatofbothapproachesappliedsolely.
Thisexperimentwascon-ductedmainlytocheck,whetherevensuchasimplehybridcombinationoflogic-basedandnon-logic-basedsemanticmatchingasinSAWSDL-M0+WAcanimproveupontheperformanceofeachofboth(SAWSDL-M0andText-IR)in-dividually.
Asshowningure3(a),thecombinationofbothperformsbestatalmosteveryrecalllevelexcepttowardsfullrecall.
ThisisinperfectlinewithourexperimentalresultsonSAWSDL-MX1reportedin[1].
Aswealreadypointedoutthere,ontologiescurrentlyfoundintheWebaremerelyinclusionhierarchiesortaxonomiesrarelymakinguseofelaboratedlogicalconceptdenitionsforserviceannotation,whichstilldampensthebenetofanylogic-basedsemanticmatchingapproach.
TocomparetheperformanceoftheadaptivehybridmatchmakerSAWSDL-MX2(logic,text,structuralsimilarity)withthatofthenon-adaptivevariantsSAWSDL-M0+WA(logicandstructuralsimilarity)andSAWSDL-MX1(logicandtextsimilarity),weconductedasecondevaluationexperiment.
Asshowngurein3(b),theadaptiveSAWSDL-MX2performsbetterthanSAWSDL-M0(logic-basedonly)butisasgoodasthenon-adaptivevariantSAWSDL-MX1utilizinglogic-basedmatchingandextendedJaccardtextsimilarity-basedmatching.
562M.
Klusch,P.
Kapahnke,andI.
ZinnikusTable1.
Averageprecisionandqueryresponsetime(inseconds)ofSAWSDL-MXmatchmakervariantsSAWSDL-M0+WASAWSDL-MX1SAWSDL-MX2AP0.
610.
660.
65AQRT15.
48s8.
17s18.
8sThisismainlytothefact,thattextsimilaritycomputationasdescribedinsection3.
3iscloselyrelatedtostructuralmatchingwhenappliedtomereis-aon-tologies(inclusionhierarchies,taxonomies).
Infact,forthegiventestcollection,whereSAWSDLleshavebeensemi-automaticallyderivedfromOWL-SandtheXMLSchemaparametersoriginfromOWLconceptdenitions,theWSDL-Analyzer(WA)indirectlyperformsbothstructuralandtextsimilarity-basedconceptmatchingwhichmakesitpartlyredundanttoSAWSDL-MX2insuchcases.
Nevertheless,forthegeneralcase,theadaptiveapproachofSAWSDL-MX2enablesaneasyandwell-denedintegrationofarbitrarymatchingmechanismstoimproveresultrankings.
Table1summarizestheaveragedprecision(AP)andqueryresponsetimeofthediscussedSAWSDLmatchmakers.
Weemphasizethattheseresultsstronglydependonthetestcollectionused.
Insummary,thenon-adaptiveSAWSDL-MX1(logic+text)stillperformsbestevenovertheadaptivevariantSAWSDL-MX2whichexhibitsalongerresponsetimeinaverageduetoitscomparativelymostcomplexmatching(logic+text+structural).
6.
3StatisticalSignicanceTestsThedierencesintheperformanceevaluationresultscanbeshowntobestatis-ticallysignicantorinsignicantbymeansoftheso-calledFriedmantest.
Thisisanon-parametrictestforsimultaneouslyanalyzingrankedresultsetsofatleasttwodierent(servicematching)methodsandhasbeenshownin[11]tobeavitalexplanatorycomponentofacomparativeretrievalperformanceevaluation.
WeareusingtheFriedmanTestvariantproposedin[10]asFN=MSRMSE,whereMSRisthemean-squareddierencebetweenthedierentmatchingvariantsandMSEthemean-squarederror.
TheresultingvaluecanbecomparedtotheF-distributionwithm1and(n1)(m1)degreesoffreedom,wherenisthenumberofqueriesanfmthenumberoftestedmatchingvariants.
Theresultingp-valueindicates,ifthereisasignicantdierencebetweenthevariantswhichonecannotinterpretasbeinganimplicationofthenullhypothesis,i.
e.
thatvariationsofthematchmakerrankingsperqueryareinsignicant.
Asathresholdvalueforp,werelyonα=0.
05,whichisfrequentlyusedfortestslikethis.
Toproducetherankingsforthetest,averagedAPvalueshavebeenused.
Thetestresultedinavalueofp=0.
026forSAWSDL-M0+WAcomparedtotheWSDL-Analyzer,andp=0.
0028comparedtoSAWSDL-M0.
Bothval-uesarebelowthethresholdαwhichmeansthattherecall/precisionresultsareasignicantimprovementat5%level.
However,thetestreturnedavalueofp=0.
331forthesecondevaluationexperimentwhichmeansthatnoneoftheevaluatedHybridAdaptiveWebServiceSelection563matchmakervariantsperformssignicantlybetterthananyoftheothersregard-ingtheusedtestcollection.
Asalreadymeantionedbefore,thisismainlyduetothefact,thattheadditionalstructuralcomparisonimplicitlyperformspartlyredun-dantmatching,asthesemi-automaticallyderivedtestcollectionservicesmainlydierwithrespecttotheXMLSchemaparameterdenitionsderivedfromtheorig-inalOWLconceptsusedintheoriginaltestcollectionOWLS-TC2.
1.
7RelatedWorkTothebestofourknowledge,thereexistonlyveryfewimplementedseman-ticservicediscoverysystemsforSAWSDL.
InFUSION[7],anySAWSDLser-vicedescriptionisclassiedatthetimeofitspublishingandthenmappedtoUDDItoallowforfastlookups.
Incaseofunknownsemanticservicere-questsreasoninghastobedoneatquerytime.
IncontrasttoSAWSDL-MX,theFUSIONdiscoveryreliesononeinferedlogicalmatchingdegreeonly,LikeSAWSDL-MX,FUSIONisstrictlyboundtoOWL-DL.
Lumina[8]developedintheMETEOR-Sproject15followsasimilarapproachbasedonmappingofWSDL-S(andlateronSAWSDLrespectively)toUDDIbutperformssyntactic(structuralandtextsimilarity-based)servicematchingonly.
Finally,theURBEmatchmakerbyPlebani16performsnon-logic-basedmatchingintermsoftextsimilarityandstructuralcomparisons.
Unfortunately,nopublicinformationisavailableonthismatchmakeryet.
Forasurveyofsemanticservicematchmakersingeneral,werefertheinterestedreaderto[6].
8ConclusionWediscussedthreedierenthybridSAWSDLservicematchmakersallofwhichoutperformingtheindividualtypesofmatchingtheycombinefordetectingthese-manticrelevanceofaservicewithinterfaceswithmultipleoperationstoagivenre-quest.
ThecombinationwithstructuralservicematchingbytheWSDL-Analyzertoolturnedouttobeofbenetcomparedtologic-basedonlymatchingbutnotwithrespecttologicalandtextsimilarity-basedmatching.
Inaddition,appliedtothegiventestcollectionSAWSDL-TC1,theadaptivehybridapproachcombiningallthreetypesofmatchingdidnotoutperformthenon-adaptivevariantin[1]yet.
WearecurrentlyworkingonanewhybridmatchmakervariantSAWSDL-MX3thatalsosupportsdierentknowledgerepresentationformalisms.
SAWSDL-MX1andSAWSDL-TC1arepubliclyavailableatsemwebcentral.
org.
References1.
Klusch,M.
,Kapahnke,P.
:SemanticWebServiceSelectionwithSAWSDL-MX.
In:Proceedingsofthe2ndWorkshoponServiceMatchmakingandResourceRetrievalintheSemanticWeb(SMR2)(2008)15http://lsdis.
cs.
uga.
edu/projects/meteor-s/16http://www-ags.
dfki.
uni-sb.
de/klusch/s3/html/2008.
html564M.
Klusch,P.
Kapahnke,andI.
Zinnikus2.
Joachims,T.
,Radlinski,F.
:SearchEnginesthatLearnfromImplicitFeedback.
Computer40(8),34–40(2007)3.
Kaufer,F.
,Klusch,M.
:WSMO-MX:ALogicProgrammingBasedHybridSer-viceMatchmaker.
In:Proceedingsofthe4thIEEEEuropeanConferenceonWebServices(ECOWS2006).
IEEECSPress,Zurich(2006)4.
Kiefer,C.
,Bernstein,A.
:TheCreationandEvaluationofiSPARQLStrategiesforMatchmaking.
In:Bechhofer,S.
,Hauswirth,M.
,Homann,J.
,Koubarakis,M.
(eds.
)ESWC2008.
LNCS,vol.
5021,pp.
463–477.
Springer,Heidelberg(2008)5.
Klusch,M.
,Fries,B.
,Sycara,K.
:AutomatedSemanticWebServiceDiscoverywithOWLS-MX.
In:Proceedingsof5thInternationalConferenceonAutonomousAgentsandMulti-AgentSystems(AAMAS),Hakodate,Japan.
ACMPress,NewYork(2006)6.
Klusch,M.
:SemanticWebServiceCoordination.
In:Schumacher,M.
,Helin,H.
,Schuldt,H.
(eds.
)CASCOM-IntelligentServiceCoordinationintheSemanticWeb,ch.
4.
Birkh¨auserVerlag/Springer(2008)7.
Kourtesis,D.
,Paraskakis,I.
:CombiningSAWSDL,OWL-DLandUDDIforSe-manticallyEnhancedWebServiceDiscovery.
In:Bechhofer,S.
,Hauswirth,M.
,Homann,J.
,Koubarakis,M.
(eds.
)ESWC2008.
LNCS,vol.
5021,pp.
614–628.
Springer,Heidelberg(2008)8.
Li,K.
,Verma,K.
,Mulye,R.
,Rabbani,R.
,Miller,J.
A.
,Sheth,A.
P.
:SemanticWebProcessesandTheirApplications.
In:Cardoso,J.
,Sheth,A.
(eds.
)DesigningSe-manticWebProcesses:TheWSDL-SApproach.
Springer,Heidelberg(submitted)9.
Baader,F.
,Calvanese,D.
,McGuinness,D.
L.
,Nardi,D.
,Patel-Schneider,P.
F.
:TheDescriptionLogicHandbook:Theory,Implementation,andApplications.
Cam-bridgeUniversityPress,Cambridge(2003)10.
Iman,R.
L.
,Davenport,J.
M.
:Approximationsofthecriticalregionofthefriedmanstatistic.
CommunicationsinStatisticsA9,571(1980)11.
Hull,D.
:Usingstatisticaltestingintheevaluationofretrievalexperiments.
In:Proceedingsofthe16thannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval,pp.
329–338(1993)12.
Zinnikus,I.
,Rupp,H.
J.
,Fischer,K.
:DetectingSimilaritiesbetweenWebServiceInterfaces:TheWSDLAnalyzer.
In:SecondInternationalWorkshoponWebSer-vicesandInteroperability(WSI2006),Pre-conferenceWorkshopofConferenceonInteroperabilityforEnterpriseSoftwareandApplications,I-ESA2006,March20-21,Bordeaux(2006)13.
Hsu,C.
-W.
,Chang,C.
-C.
,Lin,C.
-J.
:APracticalGuidetoSupportVectorClas-sication(2007)14.
Boser,B.
E.
,Guyon,I.
M.
,Vapnik,V.
N.
:Atrainingalgorithmforoptimalmarginclassiers.
In:ProceedingsofthefthannualworkshoponComputationallearningtheoryPittsburgh,Pennsylvania,UnitedStates,pp.
144–152(1992)