Transactions of the Association for Computational Linguistics, 1 (2013) 151–164. Action Editor: Patrick Pantel.
Submitted 12/2012; Revised 2/2013; Published 5/2013. c
(cid:13)
2013 Association for Computational Linguistics.
Dijkstra-WSA:AGraph-BasedApproachtoWordSenseAlignmentMichaelMatuschek‡andIrynaGurevych†‡†UbiquitousKnowledgeProcessingLab(UKP-DIPF),GermanInstituteforEducationalResearchandEducationalInformationSchloßstr.29,60486Frankfurt,Germany‡UbiquitousKnowledgeProcessingLab(UKP-TUDA),DepartmentofComputerScience,TechnischeUniversit¨atDarmstadtHochschulstr.10,64289Darmstadt,Germanyhttp://www.ukp.tu-darmstadt.deAbstractInthispaper,wepresentDijkstra-WSA,anovelgraph-basedalgorithmforwordsensealignment.Weevaluateitonfourdifferentpairsoflexical-semanticresourceswithdif-ferentcharacteristics(WordNet-OmegaWiki,WordNet-Wiktionary,GermaNet-WiktionaryandWordNet-Wikipedia)andshowthatitachievescompetitiveperformanceon3outof4datasets.Dijkstra-WSAoutperformsthestateoftheartoneverydatasetifitiscom-binedwithaback-offbasedonglosssimilar-ity.WealsodemonstratethatDijkstra-WSAisnotonlyflexiblyapplicabletodifferentre-sourcesbutalsohighlyparameterizabletoop-timizeforprecisionorrecall.1IntroductionLexical-semanticresources(LSRs)areacorner-stoneformanyNaturalLanguageProcessing(NLP)applicationssuchaswordsensedisambiguation(WSD)andinformationextraction.However,thegrowingdemandforlarge-scaleresourcesindif-ferentlanguagesishardtomeet.ThePrincetonWordNet(WN)(Fellbaum,1998)iswidelyusedforEnglish,butformostlanguagescorrespondingre-sourcesareconsiderablysmallerormissing.Col-laborativelyconstructedresourceslikeWiktionary(WKT)andOmegaWiki(OW)provideaviableop-tionforsuchcasesandseemespeciallysuitableforsmallerlanguages(Matuscheketal.,2013),buttherearestillconsiderablegapsincoveragewhichneedtobefilled.Arelatedproblemisthatthereusuallydoesnotexistasingleresourcewhichworksbestforallpurposes,asdifferentLSRscoverdiffer-entwords,sensesandinformationtypes.Theseconsiderationshavesparkedincreasingre-searcheffortsintheareaofwordsensealignment(WSA).Ithasbeenshownthatalignedresourcescanindeedleadtobetterperformancethanusingtheresourcesindividually.Examplesincludeseman-ticparsingusingFrameNet(FN),WN,andVerbNet(VN)(ShiandMihalcea,2005),wordsensedisam-biguationusinganalignmentofWNandWikipedia(WP)(NavigliandPonzetto,2012)andsemanticrolelabelingusingacombinationofPropBank,VNandFNintheSemLinkproject(Palmer,2009).SomeoftheseapproachestoWSAeitherrelyheav-ilyonmanuallabor(e.g.ShiandMihalcea(2005))oroninformationwhichisonlypresentinfewresourcessuchasthemostfrequentsense(MFS)(Suchaneketal.,2008).Thismakesitdifficulttoapplythemtoalargersetofresources.Inearlierwork,wepresentedthelarge-scalere-sourceUBY(Gurevychetal.,2012).ItcontainsnineresourcesintwolanguageswhicharemappedtoauniformrepresentationusingtheLMFstandard(Eckle-Kohleretal.,2012).Theyarethusstruc-turallyinteroperable.UBYcontainspairwisesensealignmentsbetweenasubsetoftheseresources,andthisworkalsopresentedaframeworkforcreat-ingalignmentsbasedonthesimilarityofglosses(MeyerandGurevych,2011).Cependant,itisnotcleartowhatextentthisapproachcanbeappliedtoresourceswhichlackthiskindofinformation(seeSection3).Insummary,aligningsensesisakeyrequirementforsemanticinteroperabilityofLSRstoincreasethe
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
152
coverageandeffectivenessinNLPtasks.Still,exist-ingeffortsaremostlyfocusedonspecifictypesofre-sources(mostoftenrequiringglosses)orapplicationscenarios.Inthispaper,weproposeanapproachtoalleviatethisandpresentDijkstra-WSA,anovel,ro-bustalgorithmforwordsensealignmentwhichisapplicabletoawidevarietyofresourcepairsandlanguages.Forthefirsttime,weapplyagraph-basedalgorithmwhichworksonfullgraphrepresentationsofbothresourcestowordsensealignment.Thisen-ablesustotakeamoreabstractperspectiveandre-ducetheproblemofidentifyingequivalentsensestotheproblemofmatchingnodesinthesegraphs.Alsoforthefirsttime,wecomparativelyevaluateaWSAalgorithmonavarietyofdifferentdatasetswithdif-ferentcharacteristics.ThekeypropertiesofDijkstra-WSAare:RobustnessTheentitieswithintheLSRswhicharetobealigned(usuallysensesorsynsets)aremod-eledasnodesinthegraph.Thesenodesarecon-nectedbyanedgeiftheyaresemanticallyrelated.While,forinstance,semanticrelationslendthem-selvesverywelltoderivingedges,differentpossi-bilitiesforgraphconstructionareequallyvalidasthealgorithmisagnostictotheoriginoftheedges.Language-independenceNoexternalresourcessuchascorporaorotherdictionariesareneeded;thegraphconstructionandalignmentonlyrelyontheinformationfromtheconsideredLSRs.FlexibilityThegraphconstructionaswellastheactualalignmentarehighlyparameterizabletoac-commodatedifferentrequirementsregardingpreci-sionorrecall.Therestofthispaperisstructuredasfollows:InSection2wegiveapreciseproblemdescriptionandintroducetheresourcescoveredinourexperi-ments,inSection3wediscusssomerelatedwork,whileourgraph-basedalgorithmDijkstra-WSAispresentedinSection4.Wedescribeanevaluationonfourdatasetswithdifferentproperties,includinganerroranalysis,inSection5andconcludeinSec-tion6,pointingoutdirectionsforfuturework.2NotationandResources2.1ProblemDescriptionAwordsensealignment,oralignmentforshort,isformallydefinedasalistofpairsofsensesfromtwoLSRs.Apairofalignedsensesdenotethesamemeaning.E.g.,thetwosensesofletter“Theconven-tionalcharactersofthealphabetusedtorepresentspeech”and“Asymbolinanalphabet,bookstave”(takenfromWNandWKT,respectivement)areclearlyequivalentandshouldbealigned.2.2EvaluationResourcesFortheevaluationofDijkstra-WSA,wealignfourpairsofLSRsusedinpreviouswork,namelyWN-OW(Gurevychetal.,2012),WN-WKT(MeyerandGurevych,2011),GN-WKT(Henrichetal.,2011)andWN-WP(NiemannandGurevych,2011).Ourgoalistocoverresourceswithdifferentcharacter-istics:Expert-built(WN,GN)andcollaborativelyconstructedLSRs(WP,WKT,OW),resourcesindifferentlanguages(EnglishandGerman)andalsoresourceswithfewsensedescriptions(GN)orse-manticrelations(WKT).WecontrastivelydiscusstheresultsoftheDijkstra-WSAalgorithmonthesedifferentdatasetsandrelatetheresultstotheprop-ertiesoftheLSRsinvolved.Moreover,usingexist-ingdatasetsensurescomparabilitytopreviousworkwhichdiscussesonlyonedatasetatatime.WordNet(WN)(Fellbaum,1998)isalexicalre-sourcefortheEnglishlanguagecreatedatPrincetonUniversity.Theresourceisorganizedinsetsofsyn-onymouswords(synsets)whicharerepresentedbyglosses(sometimesaccompaniedbyexamplesen-tences)andorganizedinahierarchy.Thelatestver-sion3.0contains117,659synsets.Wikipedia(WP)isafreelyavailable,multilin-gualonlineencyclopedia.WPcanbeeditedbyev-eryWebuser,whichcausesrapidgrowth:ByFebru-ary2013theEnglishWPcontainedover4,000,000articlepages.Eacharticleusuallydescribesadis-tinctconcept,andarticlesareconnectedbyhyper-linkswithinthearticletexts.Wiktionary(WKT)isthedictionarypendanttoWP.ByFebruary2013theEnglishWKTcontainedover3,200,000articlepages,whiletheGermanedi-tioncontainedover200,000ones.Foreachword,multiplesensescanbeencoded.SimilartoWN,theyarerepresentedbyaglossandusageexam-ples.Therealsoexisthyperlinkstosynonyms,hy-pernyms,meronymsetc.Thetargetsoftheserela-tionsarenotsenses,cependant,butmerelylexemes(i.e.therelationsarenotdisambiguated).
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
153
LSRsP/R/F1/Acc.ApproachMeyerandGurevych(2011)WN-WKT0.67/0.65/0.66/0.91Glosssimilarity+MachinelearningNiemannandGurevych(2011)WN-WP0.78/0.78/0.78/0.95Glosssimilarity+MachinelearningHenrichetal.(2011)GN-WKT0.84/0.85/0.84/0.94Pseudo-glossoverlapdeMeloandWeikum(2010)WN-WP0.86/NA/NA/NAGloss/articleoverlapLaparraetal.(2010)FN-WN0.79/0.79/0.79/NADijkstra-SSI+(WSDalgorithm)Navigli(2009)WN0.64/0.64/0.64/NAGraph-basedWSDofWNglossesPonzettoandNavigli(2009)WN-WPNA/NA/NA/0.81Graph-based,onlyforWPcategoriesNavigliandPonzetto(2012)WN-WP0.81/0.75/0.78/0.83Graph-basedWSAusingWNrelationsTable1:SummaryofvariousapproachestoWSA.“NA”standsfor“NotAvailable”.OmegaWiki(OW)isafreelyeditableonlinedictionarylikeWKT.However,theredonotex-istdistinctlanguageeditionsasOWisorganizedinlanguage-independentconcepts(“DefinedMean-ings”)towhichlexicalizationsinvariouslanguagesareattached.Thesecanbeconsideredasmultilin-gualsynsets,andtheyareinterconnectedbyunam-biguousrelationsjustlikeWN.AsofFebruary2013,OWcontainsover46,000oftheseconceptsandlex-icalizationsinover400languages.GermaNet(GN)istheGermancounterparttoWN(HampandFeldweg,1997).Itisalsoorganizedinsynsets(around70,000inthelatestversion7.0)whichareconnectedviasemanticrelations.3RelatedWorkThearetwostrandsofcloselyrelatedwork:Similarity-basedandgraph-basedapproachestowordsensealignment.Toourknowledge,thereex-istsnopreviousworkwhichfullyrepresentsbothLSRsinvolvedinanalignmentasgraphs.WegiveasummaryofdifferentapproachesinTable1.3.1Similarity-basedApproachesNiemannandGurevych(2011)andMeyerandGurevych(2011)createdWN-WPandWN-WKTalignmentsusingaframeworkwhichfirstcalcu-latesthesimilarityofglosses(orglossesandar-ticlesinthecaseofWN-WP)usingeithercosineorpersonalizedpagerank(PPR)similarité(AgirreandSoroa,2009)andthenlearnsathresholdonthegoldstandardtoclassifyeachpairofsensesasa(non-)validalignment.Thisapproachwaslaterex-tendedtocross-lingualalignmentbetweentheGer-manOWandWN(Gurevychetal.,2012)usingamachinetranslationcomponent.However,itsappli-cabilitydependsontheavailabilityandqualityoftheglosses,whicharenotpresentineverycase(e.g.forVN).De plus,asitinvolvessupervisedmachinelearning,itrequirestheinitialeffortofmanuallyan-notatingasufficientamountoftrainingdata.Hen-richetal.(2011)useasimilarapproachforalign-ingGNandWKT.However,theyusewordover-lapasasimilaritymeasureanddonotrequireama-chinelearningcomponentastheyaligntothecan-didatesensewiththehighestsimilarityregardlessoftheabsolutevalue.ThealignmentofWParticlesandWNsynsetsreportedbydeMeloandWeikum(2010)alsoreliesonwordoverlap.Althoughtheseapproachesgivereasonablere-sults(withprecisionintherangeof0.67-0.84),theyalldependonthelexicalknowledgecontainedintheglosses,yieldinglowrecallifthereisinsufficientlexicaloverlap(knownasthe“lexicalgap”,seeforinstance(MeyerandGurevych,2011)).ConsiderthesetwosensesofThessalonianinWKTandWN:“AnativeorinhabitantofThessalonica”and“Some-oneorsomethingfrom,orpertainingto,Thessa-loniki”.Theseare(mostly)identicalandshouldbealigned,butthereisnowordoverlapduetothein-terchangeableusageofthesynonymsThessalonicaandThessaloniki.3.2Graph-basedApproachesLaparraetal.(2010)utilizetheSSI-Dijkstra+al-gorithmtoalignFNlexicalunits(LUs)withWNsynsets.ThebasicideaistoalignmonosemousLUsfirstand,basedonthis,findtheclosestsynsetinWNfortheotherLUsinthesameframe.However,asSSI-Dijkstra+isawordsensedisambiguation(notalignment)algorithme,theLUsaremerelyconsid-eredastextswhicharetobedisambiguated;thereisnoattemptmadetobuildaglobalgraphstructureforFN.Moreover,thealgorithmsolelyreliesonthe
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
154
semanticrelationsfoundinWNandeXtendedWN(MihalceaandMoldovan,2001).Ainsi,itisnotap-plicabletootherresourceswhichhavenooronlyfewrelationssuchasWKT.Navigli(2009)aimsatdisambiguatingWNglosses,i.e.assigningthecorrectsensestoallnon-stopwordsineachWNgloss.HisapproachistofindtheshortestpossiblecirclesintheWNrelationgraphtoidentifythecorrectdisambiguation.Inlaterwork,thisideawasextendedtothedisambiguationoftranslationsinabilingualdictionary(FlatiandNavigli,2012).Cependant,thereisnodiscussionofhowthisideacouldbeappliedtowordsensealign-mentoftwoormoreresources.Webuilduponthisideaoffindingshortestpaths(circlesareaspecialkindofpath)andextendittomultipleresourcesandedgesotherthansemanticrelations,inparticularWPlinksandlinkstosensesofmonosemouslexemesappearinginglosses.PonzettoandNavigli(2009)proposeagraph-basedmethodtotackletherelated,butslightlydif-ferentproblemofaligningWNsynsetsandWPcat-egories(notarticles).Usingsemanticrelations,theybuildWNsubgraphsforeachWPcategoryandthenalignthosesynsetswhichbestmatchthecategorystructure.Inlaterwork,NavigliandPonzetto(2012)alsoalignWNwiththefullWP.Theybuild“disam-biguationcontexts”forthesensesinbothresourcesbyusing,forinstance,WPredirectsorWNglossesandthencomputethesimilaritybetweenthesecon-texts.Again,agraphstructureisbuiltfromWNse-manticrelationscoveringallpossiblesensesinthesecontexts.ThegoalistodeterminewhichWNsenseisclosesttotheWPsensetobealigned.WhiletheseapproachesareinsomerespectssimilartoDijkstra-WSA,theydonottaketheglobalstructureofbothresourcesintoaccount.Instead,theymerelyrelyona(locallyrestricted)subsetofWNrelationsforcreatingthealignment.Thus,applyingtheseap-proachestoresourcesindifferentlanguagesmightbedifficultifWNrelationsarenotapplicable.4Dijkstra-WSAInthissection,wediscussourapproachtoaligninglexical-semanticresourcesbasedonthegraphstruc-ture.Thisincludestwosteps:(je)theinitialconstruc-tionofthegraphsusingappropriateparameters,et(ii)thealignmentitself.4.1GraphConstructionWerepresentthesetofsenses(orsynsets,ifappli-cable)ofanLSRLasasetofnodesVwherethesetofedgesE,E⊆V×Vbetweenthesenodesrep-resentssemanticrelatednessbetweenthem.Wecallthisaresourcegraph.AWParticleisconsideredasenseasitrepresentsadistinctconcept.Therearemultipleoptionsforderivingtheedgesfromtheresource.Themoststraightforwardap-proachistodirectlyusetheexistingsemanticrela-tions(suchashyponymy),asithasbeenreportedinpreviouswork(Laparraetal.,2010;Navigli,2009).ForWP,wecandirectlyusethegivenhyperlinksbe-tweenarticlesastheyalsoexpressacertaindegreeofrelatedness(MilneandWitten,2008).Cependant,formanyLSRsnooronlyfewsemanticrelationsexist.ConsiderWKT:Itsrelationsarenotsensedis-ambiguated(MeyerandGurevych,2012).Wethuscannotdeterminethecorrecttargetsenseifarelationispointingtoanambiguousword.Oursolutiontothisistwofold:D'abord,foreachsenses,wecreateanedge(s,t)forthoseseman-ticrelationswhichhaveamonosemoustargett,asinthiscasethetargetsenseisunambiguous.Thisapproach,cependant,onlyrecoversasubsetofthere-lations,anditisnotapplicabletoresourceswherenosenserelationsexistatall,e.g.FN.Forthiscase,weproposetousetheglossesofsensesintheLSRtoderiveadditionaledgesinthefollowingway:Foreachmonosemous,non-stopwordlexemel(acom-binationoflemmaandpartofspeech)intheglossofasenses1withasensesl,weintroduceanedge(s1,sl).De plus,ifthereisanothersenses2withlinitsgloss,wealsointroduceanedge(s1,s2).Thistechniquewillbecalledlinkingofmonosemouslex-emesormonosemouslinkingthroughouttherestofthispaper.Theintuitionbehindthisisthatmonose-mouslexemesusuallyhavearatherspecificmean-ing,andthusitcanbeexpectedthatthesensesinwhosedescriptiontheyappearhaveatleastacertaindegreeofsemanticrelationship.Thisdirectlyre-latestothenotionof“informationcontent”(Resnik,1995),statingthatsensesinanLSRwhicharemorespecific(andhencemorelikelytobemonosemous)aremoreusefulforevaluatingsemanticsimilarity.Notethatthissteprequirespartofspeechtagging
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
155
oftheglosses,whichweperformasapreprocess-ingstep.Therebywefilteroutstopwordsandwordstaggedas“unknown”bythePOStagger.Asanexample,considertheglossofJava:“Anobject-orientedprogramminglanguage”.Evenintheabsenceofanysemanticrelations,wecouldunambiguouslyderiveanedgebetweenthissenseofJavaandthemultiwordnounprogramminglan-guageifthelatterismonosemous,i.e.ifthereexistsexactlyonesenseforthislexemeintheLSR.Also,ifprogramminglanguageappearsintheglossofoneofthesensesofPython,wecanderiveanedgebe-tweenthesesensesofJavaandPython,expressingthattheyaresemanticallyrelated.Animportantfactortokeepinmind,cependant,isthedensityoftheresultinggraph.Inpreliminaryex-periments,wediscoveredthatlinkingeverymonose-mouslexemeyieldedverydensegraphswithshortpathsbetweenmostsenses.Inturn,wedecidedtoexclude“common”lexemesandfocusonmorespe-cificonesinordertoincreasethegraph’smeaning-fulness.TheindicatorforthisisthefrequencyofalexemeintheLSR,i.e.howoftenitoccursintheglosses.Ourexperimentsonsmalldevelopmentsets(100randomsamplesofeachgoldstandard)indeedshowthatastrictfilterleadstodiscriminativeedgesresultinginhighprecision,whileatthesametimegraphsparsitydecreasesrecall.Independentlyoftheresourcepair,wediscoveredthatsettingthisfre-quencylimitvalueφtoabout1/100ofthegraphsize(e.g.1,000foragraphcontaining100,000senses)givesthebestbalancebetweenprecisionandrecall;largervaluesofφusuallyledtonosignificantim-provement1inrecallwhiletheprecisionwascontin-uouslydegrading.NotethatWPwasexcludedfromtheseexperimentsastheidentificationandlinkingofmonosemouslexemesinallWParticlesprovedtootime-consuming;instead,wedecidedtouseonlythealreadygivenlinks(seeSection5.3).4.2ComputingSenseAlignmentsInitializationAfterresourcegraphsforbothLSRsAandBarecreated,thetrivialalignmentsarere-trievedandintroducedasedgesbetweenthem.Triv-ialalignmentsarethosebetweensenseswhichhave1AllsignificancestatementsthroughoutthepaperarebasedonMcNemar’stestandtheconfidencelevelof1%.Dijkstra-WSA(UN,B)1ASenseSet=A.senses2BSenseSet=B.senses3UnalignableSenses=∅45foreachsenses∈ASenseSet6if(s.isMonosemous)7t=findTrivialMatch(s,BSenseSet)8si(t!=null)9ASenseSet.remove(s)10BSenseSet.remove(t)11createEdge(s,t)1213foreachsenses’∈ASenseSet14ASenseSet.remove(s’)15T=findCandidatesWithSameLexeme(s’,B)16si(T!=∅)17t’=findShortestPathToCandidates(s’,T)18si(t’!=null)19createEdge(s’,t’)20else21UnalignableSenses.put(s’)22else23UnalignableSenses.put(s’)Table2:PseudocodeoftheDijkstra-WSAalgorithm.thesameattachedlexemeinAandBandwherethislexemeisalsomonosemouswithineitherresource.E.g.,ifthenounphraseprogramminglanguageiscontainedineitherresourceandhasexactlyonesenseineachone,wecandirectlyinferthealign-ment.ForWP,alexemewasconsideredmonose-mousiftherewasexactlyonearticlewiththistitle,alsocountingtitleswithabracketeddisambiguation(e.g.,Java(programminglanguage)andJava(is-land)aretwodistinctsensesofJava).Whilethismethoddoesnotworkperfectly,weobservedapre-cision>0.95formonosemousgoldstandardsenses,whichisinlinewiththeobservationsbyHenrichetal.(2011).AlignmentWeconsidereachsenses∈Awhichhasnotbeenalignedintheinitializationstep.Forthis,wefirstretrievethesetofpossibletargetsensesT⊂B(thosewithmatchinglemmaandpartofspeech)andcomputetheshortestpathtoeachofthemwithDijkstra’sshortestpathalgorithm(Dijk-
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
156
stra,1959).Thecandidatet∈Twiththeshortestdistanceisthenassignedasthealignmenttarget,andthealgorithmcontinueswiththenextstillunalignedsenseinAuntileitherallsensesarealignedornopathcanbefoundfortheremainingsenses.Thein-tuitionbehindthisisthatthetrivialalignmentsfromtheinitializationserveas“bridges”betweenAandB,suchthatapathstartingfromasenses1inAtra-versesedgestofindanearbyalreadyalignedsenses2,“jumps”toBusingacross-resourceedgelead-ingtot2andthenideallyfindsanappropriatetargetsenset1inthevicinityoft2.Notethatwitheachsuccessfulalignment,edgesareaddedtothegraphsothat,intheory,adifferentorderingoftheconsid-eredsenseswouldleadtodifferentresults.Whileweobservedslightdifferencesforrepeatedrunsus-ingthesameconfiguration,thesewereinnocasestatisticallysignificant.Thepseudocodeofthisal-gorithmcanbefoundinTable2,whileanexamplecanbefoundinFigure1.Figure1:AnexampleofhowDijkstra-WSAworks.Whilethereexist2candidatesforaligningasenses1∈A(dashedlines)(un),thecorrectonet1∈Bcanbedeter-minedbyfindingtheshortestpathusinganalreadyes-tablishededgebetweentwomonosemoussensess2∈Aandt2∈B(solidline)(b).ParameterInfluenceApartfromthealreadymentionedparameterφforlimitingthenumberofedgesinthegraph,anotherimportantvariableisthemaximumallowedpathlengthλofDijkstra’salgo-rithm.Ingeneral,allowinganunboundedsearchforthecandidatesensesisundesirableaslongpaths,whileincreasingrecall,usuallyalsoleadtoade-creaseinprecision,asthenodeswhichcanbereachedinmanystepsareusuallyalsosemanticallydistantfromthesourcesense.Inthisrespect,wefoundsignificantdifferencesbetweentheoptimalconfigurationforindividualresourcepairs.How-ever,thegeneralobservationisthatshortpaths(λ≤3)leadtoaveryhighprecision,whilepathslongerthan10donotincreaserecallsignificantlyanymore.Amodificationofthealgorithmistonotonlyaligntheclosesttargetsense,butallsenseswhichcanbereachedwithacertainnumberofsteps.Thiscaterstothefactthat,duetodifferentsensegranu-larities,onecoarsersenseinAcanberepresentedbyseveralsensesinBandviceversa(seeTable3forthefractionof1:nalignmentsinthedatasets).Re-gardingthismodification,wemadetheobservationthattherecallimproved(sometimesconsiderably),butatthesametimetheprecisiondecreased,some-timestoanextentwheretheoverallF-Measure(theharmonicmeanofprecisionandrecall)gotworse.Intheevaluationsection,westatewhichsettingisusedforwhichdatasetsandconfigurations.5ExperimentalWork5.1DatasetsandtheirCharacteristicsWN3.0-EnglishOWThepreviousalignmentbe-tweenthesetworesourcesreportedinGurevychetal.(2012)isbasedontheGermanOW(databasedumpfrom2010/01/03)andWN3.0andutilizesglosssimilaritiesusingmachinetranslationasanin-termediatecomponent.Thisdoesnotposeaprob-lemsinceforeachsynsetintheGermanpartofOW,thereisatranslationintheEnglishpart.ThismakestheGerman-Englishgoldstandarddirectlyusableforourpurposes.2Table3presentsthedetailsaboutthisaswellastheotherevaluationdatasets,includ-ingtheobservedinter-rateragreementA0(whereavailable)whichcanbeconsideredasanupperboundforautomaticalignmentaccuracyandthede-greeofpolysemy(i.e.thenumberofpossiblealign-menttargetspersense)whichisahinttowardsthedifficultyofthealignmenttask.WN3.0-EnglishWKTWeusethegoldstan-darddatasetfromMeyerandGurevych(2011)with-outanymodification,thusforcomparabilitytothis2Cross-lingualalignmentislefttofuturework.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
157
travail,weusethesameWKTdumpversion(from2010/02/01)whichcontainsaround421,000senses.GN7.0-GermanWKTHenrichetal.(2011)alignedtheGermanWKT(dumpfrom2011/04/02,72,000senses)andGN7.0.Thisistheonlyexistingalignmentbetweenthesetworesourcessofar,andweusetheirfreelyavailabledataset3totestDijkstra-WSAonalanguageotherthanEnglish.Asthisalignmentisfairlylarge(seeTable3),wecreatedarandomsampleasagoldstandardtokeepthecom-putationtimeatbay.However,thedatasetsarestillsimilarenoughtoallowdirectcomparisonoftheresults.Notethatnointer-annotatoragreementisavailableforthisstudy.WN3.0-EnglishWPWeusethegoldstandardfromNiemannandGurevych(2011).Forcompa-rability,weusethesameWikipedadumpversion(from2009/08/22)witharound2,921,000articles.5.2BaselinesWN-OWWeusedthesameconfigurationasinGurevychetal.(2012)tocalculateasimilarity-basedalignmentforthemonolingualcase(i.e.with-outthetranslationstep)asabaselineandachievedcomparableresults.WN-WKTAsstatedabove,thealignment4pre-sentedinMeyerandGurevych(2011)wascreatedbycalculatingthesimilarityofglossesandtrainingamachine-learningclassifieronthegoldstandardtoclassifyeachpairofsenses.GN-WKTTheautomaticalignmentresults(i.e.theoutcomeofthealgorithmwithoutmanualpost-correction)reportedbyHenrichetal.(2011)wereunavailableforusasabaseline.Thus,weutilizethealignmentapproachbyMeyerandGurevych(2011)tocreateasimilarity-basedbaseline,withmi-normodifications.Unliketheoriginalapproach,wedirectlyalignsensesregardlessoftheirsimilarityifthedecisionistrivial(seeSection4.2).Wealsodonottrainamachinelearningcomponentonagoldstandard.Instead,weadapttheideaofHenrichetal.(2011)toalignthemostsimilarcandidateregardlessoftheabsolutevalue.WN-WPThealignmentreportedinNiemannandGurevych(2011)wascreatedinthesamewayas3http://www.sfs.uni-tuebingen.de/GermaNet/wiktionary.shtml4Availableathttp://www.ukp.tu-darmstadt.de/data/lexical-resources/wordnet-wiktionary-alignment/theWN-WKTalignmentdescribedinMeyerandGurevych(2011).Notethatwhilethefullalignmentresults5provedincomplete,thecorrectalignmentre-sultsonthegoldstandardwereavailableandthususedinourexperiments.Wewillhenceforthmarkthesesimilarity-basedresultswithSB.5.3SystemConfigurationsFortheconstructionoftheresourcegraphsweex-perimentedwiththreeoptions:Semanticrelationsonly(SR)OW,WNandGNallfeaturedisambiguatedsenserelationswhichcanbedirectlyusedasedgesbetweensenses.Notethatintheexpert-builtresources,themajorityofnodesareconnectedbysenserelations,whilethisisnotthecaseforOW.ForWKT,onlytheunambiguoussemanticrelationscanbeused(seeSection4.1),re-sultingingraphslessdenseandwithmanyisolatednodes.However,aswereportedinMatuscheketal.(2013),theEnglishWKTisalmost6timesaslargeastheGermanonefortheversionsweusedinourexperiments(421,000sensesvs.72,000senses),whileitcontainsnoteventwiceasmanyrelations(720,000vs.430,000).ThisisdirectlyreflectedinthefewerisolatednodesfortheGermanWKT.WPlinksarealsounambiguousastheyleadtoadistinctarticle.However,intuitivelynotalllinksinanarti-cleareequallymeaningful.Thus,fortheSRconfig-uration,wedecidedtoretainonlythecategorylinksandthelinkswithinthefirstparagraphofthearticle.Weassumethatthetargetsoftheselinksaremostcloselyrelatedtothesenseanarticlerepresentsasthefirstparagraphusuallyincludesaconcisedefini-tionofaconcept,andthecategorylinksallowdeter-miningthetopicanarticlebelongsto.Linkingofmonosemouslexemesonly(LM)Forthisconfiguration,thelimitingparameterφwassetto1/100ofthegraphsizeforeveryresourceex-ceptWPasdescribedinsection4.1.Asourex-perimentsshow,linkingthemonosemouslexemesintheglosseswhiledisregardingsemanticrelationsre-sultsinwell-connectedgraphsforallresourcesbutGNandWKT.Onlyabout10%oftheGNsenseshaveagloss,thusthisoptionwascompletelydisre-5Availableathttp://www.ukp.tu-darmstadt.de/data/lexical-resources/wordnet-wikipedia-alignment/
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
158
PairAlignedNotAlignedSum1:nAlignments%PolysemySamplingA0WN-OW21047368310.7%1.50Random0.85WN-WKT3132,1102,4232.7%4.76Balanced0.93GN-WKT(full)27,12718,50945,6365.6%1.78AllN/AGN-WKT(sample)1,0007511,7514.8%1.84RandomN/AWN-WP2271,5881,8155.2%5.7Balanced0.97Table3:Characteristicsofthegoldstandardsusedintheevaluation.A0istheobservedinter-rateragreementwhichcanbeconsideredasanupperboundforalignmentaccuracy.Thedegreeofpolysemy(i.e.thenumberofpossiblealignmenttargetspersense)hintstowardsthedifficultyofthealignmenttask.gardedinthiscase.ForbothWKTs,ananalysisofthegraphsrevealedthatthereasonfortherelativelyhighnumberofisolatednodesareveryshortglosses,containingmanypolysemouslexemes.ForWP,werefrainedfrommonosemouslinkingduetothepro-hibitivecomputationtime.Instead,wedecidedtousethefullylinkedWP(excludingthelinksusedfortheSRconfiguration)inthiscase.Therationaleisthatinthemajorityofarticlesmanymeaningfultermslinktothecorrespondingarticlesanyway,sothattheresultinggraphiscomparablewiththosefortheotherLSRs.Combiningboth(SR+LM)Thisconfigurationyieldsthemaximumnumberofavailableedges.WereporttheresultsforGNonlyforthisconfigurationandomittheSRresultsforthesakeofbrevityastheinfluenceontheF-MeasurefortheGN-WKTalignment(seeSection5.4)isnotstatisticallysig-nificant.ForWKT,thisconfigurationonlyincreasesthenumberofconnectednodesslightly(asinsuffi-cientglossesoftencoincidewithmissingsemanticrelations),whileforOWanalmostconnectedgraphcanbeconstructed.Table4givesanoverviewofthefractionofiso-latednodesforeachresourceineveryconfiguration.Noteagainthatforeachalignmenttask(i.e.eachpairofresources),wetunedtheparameterson100randomsamplesfromeachgoldstandardforaresultbalancingprecisionandrecallasdiscussedabove.IndividualtuningofparameterswasnecessaryforeachpairduetothegreatlyvaryingpropertiesoftheLSRs(e.g.thenumberofsenses).Whileitwouldhavebeenidealtotrainandtestondisjointsets,wecalculatedtheoverallresultsonthefullgoldstan-dardsincludingthedevelopmentsetstoensurecom-parabilitywiththepreviouswork.HybridApproachManualinspectionofthere-sultsrevealedthatthealignmentsfoundbyDijkstra-ResourceSRLMSR+LMWN0.250.070.02GN0.00.920.0WKT-en0.980.320.30WKT-de0.690.180.15OW0.410.330.04WP0.060.050.04Table4:Thistabledescribeswhatpercentageofnodesremainsisolated(i.e.with0attachededges)indiffer-entgraphconfigurationsusingsemanticrelations(SR),monosemouslinking(LM)(φ=1/100)orboth(SR+LM).NotethatthisnumberishighestfortheEn-glishWKTasthefewsemanticrelationsandshortglossesdonotoffermanypossibilitiesforconnectingnodes,whiletheGermanWKTandOWdonotsufferfromthisproblemasmuch.GNisfullylinkedviare-lations,buthasonlyfewglosseswhichmakesmonose-mouslinkingineffective.WNandWParerelativelywell-linkedinallconfigurations.AlsonotethatforWP,SRmeansthatweusedcategorylinksandlinksfromthefirstparagraph,whilelinksfromtherestofthearticlewereusedfortheLMconfiguration.WSAareusuallydifferentfromthosebasedontheglosssimilarity.Whilethelatterpreciselyrecog-nizesalignmentswithsimilarwordingofglosses,Dijkstra-WSAisadvantageousiftheglossesaredif-ferentbutthesensesarestillsemanticallycloseinthegraph.Section5.5willanalyzethisingreaterdetail.Exploitingthisfact,weexperimentedwithahybridapproach:Weperformanalignmentus-ingDijkstra-WSA,tunedforhighprecision(i.e.us-ingshorterpathlengths)andfallbacktousingtheresultsofthesimilarity-basedapproachesforthosecaseswherenoalignmenttargetcouldbefoundinthegraph.Theseresultsaremarkedwith+SBintheresultoverview(Table5).
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
159
WordNet-OmegaWikiWordNet-WiktionaryGermaNet-WiktionaryWordNet-WikipediaPRF1Acc.PRF1Acc.PRF1Acc.PRF1Acc.Random0.460.350.400.510.210.590.310.670.440.510.470.540.490.620.530.86SB0.550.530.540.730.670.650.660.910.930.740.830.830.780.780.780.95SR0.660.450.530.760.950.130.230.890.940.650.770.780.820.630.710.93LM0.620.540.580.770.720.240.360.890.890.750.810.800.650.660.650.91SR+LM0.560.690.620.740.680.270.390.890.900.780.830.820.750.670.710.93SR+SB0.600.650.630.760.680.670.680.920.900.820.860.840.750.870.810.95LM+SB0.600.700.640.760.680.700.690.920.860.870.870.850.700.870.780.94SR+LM+SB0.570.750.650.750.680.710.690.920.870.880.870.850.750.870.810.95A0—0.85—0.93—N/A—0.97Table5:Alignmentresultsforalldatasetsandconfigurations:Usingsemanticrelations(SR),monosemouslinks(LM)orboth(SR+LM).Thesimilarity-based(SB)baselines,alsousedasaback-offforthehybridapproaches(+SB),werecreatedusingtheapproachreportedinGurevychetal.(2012).NotethatforGN,theSR+LMconfigurationwasalwaysused.ThedifferentconfigurationsgivenforthisalignmentthusonlyapplytoWKT.ForWP,SRmeansthatonlycategorylinksandlinkswithinthefirstparagraphwereused,whileLMuseslinksfromthefullarticle.Arandombaselineandtheinter-annotatoragreementA0ofthegoldstandardannotation(ifavailable)aregivenforreference.5.4ExperimentalResultsWN-OWWhenusingonlysemanticrelations(SR),weachievedanF-Measureof0.53whichiscom-parablewiththe0.54fromGurevychetal.(2012).Notably,ourapproachhasahighprecision,whiletherecallisconsiderablyworseduetotherelativesparsityoftheresultingOWresourcegraph.Whenaddingmoreedgestothegraphbylinkingmonose-mouslexemes(SR+LM),wecandrasticallyimprovetherecall,leadingtoanoverallF-Measureof0.62,whichisasignificantimprovementoverourprevi-ousresults(Gurevychetal.,2012).Usingmonose-mouslinksonly(LM),theresultof0.58stillout-performsGurevychetal.(2012)duetothehigherprecision.Buildingagraphfromglossesaloneisthusaviableapproachifnooronlyfewsemanticrelationsareavailable.Regardingthepathlengths,λ=10worksbestwhensemanticrelationsarein-cludedinthegraph,whilefortheLMconfigura-tionshorterpaths(λ≤5)weremoreappropriate.Theintuitionbehindthisisthatforsemanticrela-tions,unlikemonosemouslinks,evenlongerpathsstillexpressahighdegreeofsemanticrelatedness.Also,whensemanticrelationsareinvolvedallow-ingmultiplealignmentsincreasestheoverallresults(whichisinlinewiththerelativelyhighnumberof1:nalignmentsinthegoldstandard),whilethisisnotthecasefortheLMconfiguration;ici,theedgesagaindonotsufficientlyexpressrelatedness.Usingthehybridapproach(+SB),wecanincreasetheF-Measureupto0.65ifsemanticrelationsandmonosemouslinkingarecombined(SR+LM)andtheparametersaretunedforhighprecision(λ≤3,1:1alignments).ThisissignificantlybetterthanDijkstra-WSAaloneinanyconfiguration.Inthisscenario,wealsoobservethebestoverallrecall.WN-WKTExperimentsusingonlythesemanticrelations(SR)yieldaverylowrecall-thesmallnumberofsenserelationswithmonosemoustargetsinWKTleavesthegraphverysparse.Nevertheless,thealignmenttargetswhichDijkstra-WSAfindsaremostlycorrect,withaprecisiongreaterthan0.95evenwhenallowing1:nalignments.Usingonlymonosemouslinks(LM)improvestherecallconsid-erably,butunliketheWN-OWalignment,itstaysfairlylow.Consequently,evenwhenusingseman-ticrelationsandmonosemouslinksinconjunction(SR+LM),therecallcanonlybeincreasedslightly,leadingtoanoverallF-Measureof0.39.Asmen-tionedabove,thisisduetotheWKTglosses.Inmanycases,theyareveryshort,oftenconsistingofonly3-5words,manyofwhicharepolysemous.Thisleadstomanyisolatednodesinthegraphwithnooronlyveryfewconnectingedges.Theideal,rathershortpathlengthλof2-3stemsfromtherela-tivelyhighpolysemyofthegoldstandard(seeTable3).Weexperimentedwithλ≥4,achievingrea-sonablerecall,butinthiscasetheprecisionwassolowthatthisconfiguration,inconclusion,doesnotincreasetheF-Measure.However,1:nalignmentsworkwellwiththeseshortpathsasthecorrectalign-mentsaremostlyintheclosevicinityofasense,
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
160
henceweachieveanincreaseinrecallinthiscasewithouttoomuchlossofprecision.Forthehybridapproach,weachieveanF-Measureof0.69whenusingalledges(SR+LM+SB),settingthepathlengthto2,andalsoallowing1:nalignments.ThisisastatisticallysignificantimprovementoverMeyerandGurevych(2011)whichagainconfirmstheeffectivenessofthehybridapproach.GN-WKTAsstatedabove,weusedtheSR+LMconfigurationforGNineverycase.FortheGermanWKT,themuchgreaternumberofrelationscom-paredtoitsEnglishcounterpartisdirectlyreflectedintheresults,asusingthesemanticrelationsonly(SR)notonlyyieldsthebestprecisionof0.94butalsoagoodrecallof0.65.Usingthesemanticre-lationstogetherwithmonosemouslinks(SR+LM)yieldstheF-Measureof0.83,whichisonparwiththesimilarity-based(SB)approach.Inthehybridconfiguration,wecanincreasetheperformancetoanF-Measureofupto0.87(SR+LM+SB),significantlyoutperformingallgraph-basedandsimilarity-basedconfigurations.Ingeneral,resultsforthispairofLSRsarehigherincomparisonwiththeothers.WeattributethistothefactthattheGermanWKTandGNbotharedenselylinkedwithsemanticrelationswhichises-peciallybeneficialfortherecallofDijkstra-WSA.Thisisalsoreflectedintheidealλof10-12:Manyhigh-confidenceedgesallowlongpathswhichstillexpressaconsiderabledegreeofrelatedness.How-ever,whiletheresultsfor1:nalignmentsareal-readygood,restrictingoneselfto1:1alignmentsgivesthebestoverallresultsastheprecisioncanthenbepushedtowards0.90withouthurtingrecalltoomuch.AnimportantfactorinthisrespectisthattheGN-WKTdatasethasarelativelylowdegreeofpolysemy(comparedtoWN-WKT)andonlyfew1:nalignments(comparedtoWN-OW),twofactswhichmakethetasksignificantlyeasier.WN-WPTheSRconfiguration(WNrelations+WPcategory/firstparagraphlinks)yieldsthebestprecision(0.82),evenoutperformingtheSBap-proach,andanF-Measureof0.71.Thisagainshowsthatusinganappropriateparametrization(λ≤4inthiscase)Dijkstra-WSAcandetectalignmentswithhighconfidence.Therelativelylowrecallof0.63couldbeincreasedbyallowinglongerpaths,cependant,ashyperlinksdonotexpressrelatednessasreliablyassemanticrelations,thisintroducesmanyfalsepositivesandthushurtsprecisionconsiderably.Thisissueof“misleading”WPlinksbecomesevenmoreprominentwhenthelinksfromthefullarticlesareusedasedges(LM);whiletheincreaseinrecallisrelativelysmalltheprecisiondropssubstantially.However,usingallpossiblelinks(SR+LM)allowsustobalanceoutprecisionandrecalltosomeextent,whileyieldingthesameF-MeasureastheSRconfig-uration.Notethat1:1alignmentswereenforcedinanycase,asthehighpolysemyofthedatasetincon-junctionwiththedenseWPlinkstructurerendered1:nalignmentsveryimprecise.Usingthehybridapproach,wecanincreasetheF-Measureupto0.81(SR+SB),outperformingthere-sultsreportedinNiemannandGurevych(2011)byasignificantmargin.TheF-MeasureforLM+SBisslightlyworseduetothelowerprecision.Combin-ingalledges(SR+LM+SB)doesnotinfluencetheresultsanymore,butinanycasethehybridconfigu-rationachievesthebestoverallrecall(0.87).Inconclusion,ourexperimentsonallfourdatasetsconsistentlydemonstratethatcombiningDijkstra-WSAwithasimilarity-basedapproachasaback-offyieldsthestrongestperformance.There-sultsofthesebestalignmentswillbemadefreelyavailabletotheresearchcommunityonourwebsite(http://www.ukp.tu-darmstadt.de).5.5ErrorAnalyisThebyfarmostsignificanterrorsource,reflectedintherelativelylowrecallfordifferentconfigurations,isthehighnumberoffalsenegatives,i.e.sensepairswhichwerenotalignedalthoughtheyshouldhavebeen.ThisisespeciallystrikingfortheWN-WKTalignment.Asdiscussedearlier,WKTcontainsasignificantnumberofshortglosses,whichinmanycasesalsocontainfewornomonosemousterms.Aprototypicalexampleisthefirstsenseofseedling:“Ayoungplantgrownfromseed”.Thisglosshasnomonosemouswordswhichcouldbelinked,andastherearealsonosemanticrelationsattachedtothissensewhichcouldbeexploited,thenodeisiso-latedinthegraph.OurexperimentsshowthatfortheEnglishWKT,evenwhenoptimizingtheparam-etersforrecall,around30%ofthesensesremainisolated,i.e.withoutedges.Thisisbyfarthehigh-
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
161
estvalueacrossallresources(seeTable4).Solv-ingthisproblemwouldrequiremakingthegraphmoredense,andespeciallyfindingwaystoincludeisolatednodesaswell.However,thisexamplealsoshowswhythehybridapproachworkssowell:ThecorrectWNsense“youngplantortreegrownfromaseed”wasrecognizedbythesimilarity-basedap-proachwithhighconfidence.Withregardtofalsepositives,Dijkstra-WSAandthesimilarity-basedapproachesdisplayverysimilarperformance.Thisisbecausesenseswithverysim-ilarwordingarelikelytosharethesamemonose-mouswords,leadingtoaclosevicinityinthegraphandthefalsealignment.Asanexample,considertwosensesofbowdlerizationinWN(“writtenmate-rialthathasbeenbowdlerized”)andWKT(“Theac-tionorinstanceofbowdlerizing;theomissionorre-movalofmaterialconsideredvulgarorindecent.”).Whilethesesensesareclearlyrelated,theyarenotidenticalandshouldnotbealigned,neverthelessthesimilarwording(andespeciallytheuseofthehighlyspecificverb“bowdlerize”)resultsinanalignment.Similarlytothesimilarity-basedapproaches,itisanopenquestionhowthiskindoferrorcanbeeffec-tivelyavoided(MeyerandGurevych,2011).Thereisaconsiderablenumberofexam-pleswhereDijkstra-WSArecognizesanalignmentwhichsimilarity-basedapproachesdonot.ThetwosensesofThessalonianfromtheintroductoryexam-ple(Section3)containthetermsThessalonicaandThessalonikiintheirglosseswhicharebothmonose-mousinWNaswellasinWKT,sharingthealsomonosemousnounGreeceintheirglosses.Thisyieldsthebridgebetweentheresourcestofindapathandcorrectlyderivethealignment.6ConclusionsandFutureWorkInthiswork,wepresentDijkstra-WSA,agraph-basedalgorithmforwordsensealignment.Weshowthatthisalgorithmperformscompetitivelyon3outof4evaluationdatasets.Ahybridapproachleadstoastatisticallysignificantimprovementoversimilarity-basedstateoftheartresultsoneverydataset.Dijkstra-WSAcanoperateonglossesorsemanticrelationsalone(althoughitisbeneficialifbotharecombined),anditdoesnotrequireanyex-ternalknowledgeintheformofannotatedtrainingdataorcorpora.Additionally,itisflexiblyconfig-urablefordifferentpairsofLSRsinordertoopti-mizeforprecisionorrecall.Animportanttaskforfutureworkistoevalu-ateDijkstra-WSAonLSRswhichstructurallydif-ferfromtheonesdiscussedhere.ItisimportanttodeterminehowresourceslikeFNorVNcanbemeaningfullytransformedintoagraphrepresenta-tion.Anotherideaistoextendtheapproachtocross-lingualresourcealignment,whichwouldre-quireamachinetranslationcomponenttoidentifysensealignmentcandidateswiththecorrectlexeme.Regardingthealgorithmitself,themaindirectionforfutureworkistoincreaserecallwhilekeepinghighprecision.Onepossiblewaywouldbetonotonlylinkmonosemouslexemes,butalsotocreateedgesforpolysemousones.Laparraetal.(2010)discussapossibilitytodothiswithhighprecision.Themainideaistofocusonlexemeswithalowde-greeofpolysemyandalignifoneofthepossiblesensesisclearlymoresimilartothesourcesensethantheother(s).Ifrecallisstilllow,morepoly-semouslexemescanbeexamined.Aweightingofedges(e.g.basedonglosssimi-larities)hasnotbeenconsideredatall,butwouldbeeasilyapplicabletotheexistingframework.Amoreelaborateideawouldbetoinvestigateentirelydifferentgraph-basedalgorithms,e.g.formatchingnodesinbipartitegraphs.Also,weplantoinvestigateifandhowourapproachcanbeextendedtoalignmorethantworesourcesatonceusingthegraphrepresentations.Thismightimprovealign-mentresultsasmoreinformationabouttheoverallalignmenttopologybecomesavailable.AcknowledgementsThisworkhasbeensupportedbytheVolkswagenFoundationaspartoftheLichtenbergProfessorshipProgramundergrantNo.I/82806andbytheHessianresearchexcellenceprogram“Landes-OffensivezurEntwicklungWissenschaftlich-¨okonomischerExzellenz(LOEWE)”aspartoftheresearchcenter“DigitalHumanities”.WewouldliketothankChristianM.Meyer,WolfgangStille,KarstenWeiheandTristanMillerforinsightfuldiscussionsandcomments.Wealsothanktheanonymousreviewersfortheirhelpfulremarks.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
162
ReferencesEnekoAgirreandAitorSoroa.2009.Personaliz-ingPageRankforWordSenseDisambiguation.InProceedingsofthe12thConferenceoftheEuropeanChapteroftheAssociationforComputationalLinguis-tics,pages33–41,Athens,Greece.GerarddeMeloandGerhardWeikum.2010.Pro-vidingMultilingual,MultimodalAnswerstoLexicalDatabaseQueries.InProceedingsofthe7thLanguageResourcesandEvaluationConference(LREC2010),pages348–355,Valetta,Malta.Edsger.W.Dijkstra.1959.Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik,1:269–271.10.1007/BF01386390.JudithEckle-Kohler,IrynaGurevych,SilvanaHartmann,MichaelMatuschek,andChristianM.Meyer.2012.UBY-LMF-AUniformModelforStandardizingHet-erogeneousLexical-SemanticResourcesinISO-LMF.InProceedingsofthe8thInternationalConferenceonLanguageResourcesandEvaluation(LREC’12),pages275–282,Istanbul,Turkey.ChristianeFellbaum.1998.WordNet:AnElectronicLexicalDatabase.MITPress.TizianoFlatiandRobertoNavigli.2012.TheCQCal-gorithm:Cyclingingraphstosemanticallyenrichandenhanceabilingualdictionary.JournalofArtificialIntelligenceResearch(JAIR),43:135–171.IrynaGurevych,JudithEckle-Kohler,SilvanaHartmann,MichaelMatuschek,ChristianM.Meyer,andChris-tianWirth.2012.UBY-ALarge-ScaleUnifiedLexical-SemanticResourceBasedonLMF.InPro-ceedingsofthe13thConferenceoftheEuropeanChapteroftheAssociationforComputationalLinguis-tics(EACL’12),pages580–590,Avignon,France.BirgitHampandHelmutFeldweg.1997.Germanet-alexical-semanticnetforgerman.InInProceedingsofACLworkshopAutomaticInformationExtractionandBuildingofLexicalSemanticResourcesforNLPAp-plications,pages9–15.VerenaHenrich,ErhardHinrichs,andTatianaVodola-zova.2011.Semi-AutomaticExtensionofGermaNetwithSenseDefinitionsfromWiktionary.InProceed-ingsofthe5thLanguageandTechnologyConference(LTC2011),pages126–130,Poznan,Poland.EgoitzLaparra,GermanRigau,andMontseCuadros.2010.ExploringtheintegrationofWordNetandFrameNet.InProceedingsofthe5thGlobalWordNetConference(GWC’10),Mumbai,India.MichaelMatuschek,ChristianM.Meyer,andIrynaGurevych.2013.MultilingualKnowledgeinAlignedWiktionaryandOmegaWikiforComputer-AidedTranslation.Translation:Computation,Cor-pora,Cognition.SpecialIssueon“LanguageTechnol-ogyforaMultilingualEurope”,toappear.ChristianM.MeyerandIrynaGurevych.2011.WhatPsycholinguistsKnowAboutChemistry:AligningWiktionaryandWordNetforIncreasedDomainCov-erage.InProceedingsofthe5thInternationalJointConferenceonNaturalLanguageProcessing(IJC-NLP),pages883–892,ChiangMai,Thailand.ChristianM.MeyerandIrynaGurevych.2012.Wik-tionary:Anewrivalforexpert-builtlexicons?Ex-ploringthepossibilitiesofcollaborativelexicography.InSylvianeGrangerandMagaliPaquot,editors,Elec-tronicLexicography,chapter13,pages259–291.Ox-fordUniversityPress.RadaMihalceaandDanI.Moldovan.2001.eXtendedWordNet:progressreport.InProceedingsofNAACLWorkshoponWordNetandOtherLexicalResources,pages95–100,Pittsburgh,Pennsylvanie,USA.DavidMilneandIanH.Witten.2008.Aneffective,low-costmeasureofsemanticrelatednessobtainedfromWikipedialinks.InProceedingsoftheAAAIWorkshoponWikipediaandArtificialIntelligence:anEvolvingSynergy,pages25–30,Chicago,IL,USA.RobertoNavigliandSimonePaoloPonzetto.2012.Ba-belNet:Theautomaticconstruction,evaluationandapplicationofawide-coveragemultilingualsemanticnetwork.ArtificialIntelligence,193:217–250.RobertoNavigli.2009.UsingCyclesandQuasi-CyclestoDisambiguateDictionaryGlosses.InProceedingsofthe12thConferenceoftheEuropeanChapteroftheAssociationforComputationalLinguistics(EACL’09),pages594–602,Athens,Greece.ElisabethNiemannandIrynaGurevych.2011.ThePeo-ple’sWebmeetsLinguisticKnowledge:AutomaticSenseAlignmentofWikipediaandWordNet.InPro-ceedingsofthe9thInternationalConferenceonCom-putationalSemantics(IWCS),pages205–214,Oxford,UK.MarthaPalmer.2009.SemLink:LinkingPropBank,VerbNetandFrameNet.InProceedingsoftheGenera-tiveLexiconConferenceGenLex-09,pages9–15,Pisa,Italy.SimonePaoloPonzettoandRobertoNavigli.2009.Large-scaletaxonomymappingforrestructuringandintegratingWikipedia.InProceedingsofthe21stIn-ternationalJointConferenceonArtificialIntelligence,pages2083–2088,Pasadena,Californie,USA.PhilipResnik.1995.UsingInformationContenttoEvaluateSemanticSimilarityinaTaxonomy.InIn-ternationalJointConferenceforArtificialIntelligence(IJCAI-95),pages448–453,Montreal,Canada.LeiShiandRadaMihalcea.2005.PuttingPiecesTo-gether:CombiningFrameNet,VerbNetandWordNetforRobustSemanticParsing.InComputationalLin-guisticsandIntelligentTextProcessing:6thInterna-tionalConference,volume3406ofLectureNotesin
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
163
ComputerScience,pages100–111.Berlin/Heidelberg:Springer.FabianM.Suchanek,GjergjiKasneci,andGerhardWeikum.2008.YAGO:ALargeOntologyfromWikipediaandWordNet.WebSemantics,6(3):203–217.
je
D
o
w
n
o
un
d
e
d
F
r
o
m
h
t
t
p
:
/
/
d
je
r
e
c
t
.
m
je
t
.
e
d
toi
/
t
un
c
je
/
je
un
r
t
je
c
e
–
p
d
F
/
d
o
je
/
.
1
0
1
1
6
2
/
t
je
un
c
_
un
_
0
0
2
1
7
1
5
6
6
6
3
5
/
/
t
je
un
c
_
un
_
0
0
2
1
7
p
d
.
F
b
oui
g
toi
e
s
t
t
o
n
0
7
S
e
p
e
m
b
e
r
2
0
2
3
164