Transactions of the Association for Computational Linguistics, 1 (2013) 219–230. Action Editor: Brian Roark.
Submitted 1/2013; Revised 3/2013; Published 5/2013. c
(cid:13)
2013 Association for Computational Linguistics.
JointArc-factoredParsingofSyntacticandSemanticDependenciesXavierLlu´ısandXavierCarrerasandLlu´ısM`arquezTALPResearchCenterUniversitatPolit`ecnicadeCatalunyaJordiGirona1–3,08034Barcelona{xlluis,carreras,lluism}@lsi.upc.eduAbstractInthispaperweintroduceajointarc-factoredmodelforsyntacticandsemanticdependencyparsing.Thesemanticrolelabelerpredictsthefullsyntacticpathsthatconnectpredicateswiththeirarguments.Thisprocessisframedasalinearassignmenttask,whichallowstocontrolsomewell-formednessconstraints.Forthesyntacticpart,wedefineastandardarc-factoreddependencymodelthatpredictsthefullsyntactictree.Finally,weemploydualdecompositiontechniquestoproduceconsis-tentsyntacticandpredicate-argumentstruc-tureswhilesearchingoveralargespaceofsyntacticconfigurations.InexperimentsontheCoNLL-2009Englishbenchmarkweob-serveverycompetitiveresults.1IntroductionSemanticrolelabeling(SRL)isthetaskofidenti-fyingtheargumentsoflexicalpredicatesinasen-tenceandlabelingthemwithsemanticroles(GildeaandJurafsky,2002;M`arquezetal.,2008).SRLisanimportantshallowsemantictaskinNLPsincepredicate-argumentrelationsdirectlyrepresentse-manticpropertiesofthetype“who”did“what”to“whom”,“how”,and“why”foreventsexpressedbypredicates(typicallyverbsandnouns).Predicate-argumentrelationsarestronglyrelatedtothesyntacticstructureofthesentence:thema-jorityofpredicateargumentscorrespondtosomesyntacticconstituent,andthesyntacticstructurethatconnectsanargumentwiththepredicateisastrongindicatorofitssemanticrole.Actually,semanticrolesrepresentanabstractionofthesyntacticformofapredicativeevent.Whilesyntacticfunctionsofargumentschangewiththeformoftheevent(e.g.,activevs.passiveforms),thesemanticrolesofargu-mentsremaininvarianttotheirsyntacticrealization.Consequently,sincethefirstworks,SRLsystemshaveassumedaccesstothesyntacticstructureofthesentence(GildeaandJurafsky,2002;CarrerasandM`arquez,2005).Asimpleapproachistoobtaintheparsetreesasapre-processtotheSRLsystem,whichallowstheuseofunrestrictedfeaturesofthesyntax.However,asinotherpipelineapproachesinNLP,ithasbeenshownthattheerrorsofthesyn-tacticparserseverelydegradethepredictionsoftheSRLmodel(GildeaandPalmer,2002).AcommonapproachtoalleviatethisproblemistoworkwithmultiplealternativesyntactictreesandlettheSRLsystemoptimizeoveranyinputtreeorpartofit(Toutanovaetal.,2008;Punyakanoketal.,2008).Asastepfurther,morerecentworkhasproposedparsingmodelsthatpredictsyntacticstructureaug-mentedwithsemanticpredicate-argumentrelations(Surdeanuetal.,2008;Hajiˇcetal.,2009;Johansson,2009;Titovetal.,2009;Llu´ısetal.,2009),whichisthefocusofthispaper.Thesejointmodelsshouldfavorthesyntacticstructurethatismostconsistentwiththesemanticpredicate-argumentstructuresofasentence.Inprinciple,thesemodelscanexploitsyntacticandsemanticfeaturessimultaneously,andcouldpotentiallyimprovetheaccuracyforbothsyn-tacticandsemanticrelations.Onedifficultyinthedesignofjointsyntactic-semanticparsingmodelsisthatthereexistimpor-tantstructuraldivergencesbetweenthetwolayers.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
220
Marylovestoplayguitar.SBJOPRDIMOBJPARG0ARG1ARG0ARG1Figure1:Anexample…Dasetal.(2012)…RiedelandMcCallum(2011)…3ASyntactic-SemanticDependencyModelWewilldescribestructuresofsyntacticandseman-ticdependencieswithvectorsofbinaryvariables.Wewilldenotebyyh,m,lasyntacticdependencyfromheadtokenhtodependanttokenmlabeledwithsyntacticfunctionl.Similarlywewilldenotebyzp,a,rasemanticdependencybetweenpredicatetokenpandargumenttokenalabeledwithseman-ticroler.Wewilluseyandztodenotevectorsofbinaryvariablesindexedbysyntacticandsemanticdependencies,respectively.Ajointmodelforsyntacticandsemanticdepen-dencyparsingcouldbedefinedas:argmaxy,zssyn(x,y)+ssrl(x,z,y).Intheequation,ssyn(x,y)givesascoreforthesyntactictreey.Intheliterature,itisstandardtousearc-factoredmodelsdefinedasssyn(x,y)=yh,m,l=1ssyn(x,h,m,l),whereweoverloadssyntobeafunctionthatcomputesscoresforindividuallabeledsyntacticdependencies.Indiscriminativemodelsonehasssyn(x,h,m,l)=wsyn·fsyn(x,h,m,l),wherefsynisafeaturevectorforthesyntacticdependencyandwsynisavectorofparameters(McDonaldetal.,2005).Theotherterm,ssrl(x,z,y),givesascoreforasemanticdependencystructureusingthesyntacticstructureyasfeatures.Previousworkhasempiri-callyprovedtheimportanceofexploitingsyntacticfeaturesinthesemanticcomponent(GildeaandJu-rafsky,2002;XueandPalmer,2004;Punyakanoketal.,2008).However,withoutfurtherassumptions,thispropertymakestheoptimizationproblemcom-putationallyhard.Onesimpleapproximationistouseapipelinemodel:firstcomputetheoptimalsyn-tactictree,andthenoptimizeforthebestsemanticstructuregiventhesyntactictree.Intherestofthepaperwedescribeamethodthatsearchesoversyn-tacticandsemanticdependencystructuresjointly.Wefirstimposetheassumptionthatsyntacticfea-turesofthesemanticcomponentarerestrictedtothesyntacticpathbetweenapredicateandanargument,followingpreviouswork(Johansson,2009).For-mally,forapredicatep,argumentaandrolerwewilldefineavectorofdependencyindicatorsπp,a,rsimilartotheonesabove:πp,a,rh,m,lindicatesifade-pendencyh,m,lispartofthesyntacticpaththatlinkspredicatepwithtokena.Figure1givesanex-ampleofonesuchpaths.Givenfullsyntacticandsemanticstructuresyandzitistrivialtoconstructavectorπthatisaconcatenationofvectorsπp,a,rforallp,a,rinz.Wecannowdefinealinearseman-ticmodelasssrl(x,z,π)=zp,a,r=1ssrl(x,p,a,r,πp,a,r),(1)wheressrlcomputesascoreforasemanticde-pendencyp,a,rtogetherwithitssyntacticpathπp,a,r.Asinthesyntacticcomponent,thisfunctionistypicallydefinedasalinearfunctionoverasetoffeaturesofthesemanticdependencyanditspath.Withthisjointmodel,theinferenceproblemcanbeformulatedas:argmaxy,z,πssyn(x,y)+ssrl(x,z,π)(2)subjecttocTree:yisavaliddependencytreecRole:∀p,r:azp,a,r≤1cArg:∀p,a:rzp,a,r≤1cPath:∀p,a,r:ifzp,a,r=1thenπp,a,risapathfromptoaotherwiseπp,a,r=0cSubtree:∀p,r,a:πp,r,aisasubtreeofyFigure1:Asentencewithsyntacticdependencies(top)andsemanticdependenciesforthepredicates“loves”and“play”(bottom).Thethickarcsillustrateastructuraldi-vergencewheretheargument“Mary”islinkedto“play”withapathinvolvingthreesyntacticdependencies.Thisisclearlyseenindependency-basedrepresenta-tionsofsyntaxandsemanticroles(Surdeanuetal.,2008),suchasintheexampleinFigure1:thecon-struct“lovesto”causestheargument“Mary”tobesyntacticallydistantfromthepredicate“play”.Lin-guisticphenomenasuchasauxiliaryverbs,controlandraising,typicallyresultinsyntacticstructureswheresemanticargumentsarenotamongthedirectdependantsoftheirpredicate—e.g.,about25%ofargumentsaredistantintheEnglishdevelopmentsetoftheCoNLL-2009sharedtask.Besides,standardmodelsfordependencyparsingcruciallydependonarcfactorizationsofthedependencystructure(Mc-Donaldetal.,2005;NivreandNilsson,2005),other-wisetheircomputationalpropertiesbreak.Hence,itischallengingtodefineefficientmethodsforsyntac-ticandsemanticdependencyparsingthatcanexploitfeaturesofbothlayerssimultaneously.Inthispaperweproposeamethodforthisjointtask.Inourmethodwedefinepredicate-centricseman-ticmodelsthat,ratherthanpredictingjustthear-gumentthatrealizeseachsemanticrole,theypre-dictthefullsyntacticpaththatconnectsthepredi-catewiththeargument.Weshowhowefficientpre-dictionswiththesemodelscanbemadeusingas-signmentalgorithmsinbipartitegraphs.Simulta-neously,weuseastandardarc-factoreddependencymodelthatpredictsthefullsyntactictreeofthesen-tence.Finally,weemploydualdecompositiontech-niques(Kooetal.,2010;Rushetal.,2010;Sontagetal.,2010)tofindagreementbetweenthefullde-pendencytreeandthepartialsyntactictreeslinkingeachpredicatewithitsarguments.Insummary,themaincontributionsofthispaperare:•WeframeSRLasaweightedassignmentprob-leminabipartitegraph.Underthisframeworkwecancontrolassignmentconstraintsbetweenrolesandarguments.Keytoourmethod,wecanefficientlysearchoveralargespaceofsyn-tacticrealizationsofsemanticarguments.•Wesolvejointinferenceofsyntacticandse-manticdependencieswithadualdecomposi-tionmethod,similartothatofKooetal.(2010).Oursystemproducesconsistentsyntacticandpredicate-argumentstructureswhilesearchingoveralargespaceofsyntacticconfigurations.Intheexperimentalsectionwecomparejointandpipelinemodels.Thefinalresultsofourjointsyntactic-semanticsystemarecompetitivewiththestate-of-the-artandimproveoverthebestresultspublishedbyajointmethodontheCoNLL-2009Englishdataset.2ASyntactic-SemanticDependencyModelWefirstdescribehowwerepresentstructuresofsyn-tacticandsemanticdependenciesliketheoneinFig-ure1.Throughoutthepaper,wewillassumeafixedinputsentencexwithntokenswherelexicalpredi-catesaremarked.WewillalsoassumefixedsetsofsyntacticfunctionsRsynandsemanticrolesRsem.Wewillrepresentdepencencystructuresusingvec-torsofbinaryvariables.Avariableyh,m,lwillin-dicatethepresenceofasyntacticdependencyfromheadtokenhtodependanttokenmlabeledwithsyn-tacticfunctionl.Then,asyntactictreewillbede-notedasavectoryofvariablesindexedbysyntacticdependencies.Similarly,avariablezp,a,rwillindi-catethepresenceofasemanticdependencybetweenpredicatetokenpandargumenttokenalabeledwithsemanticroler.Wewillrepresentasemanticrolestructureasavectorzindexedbysemanticdepen-dencies.Wheneverweenumeratesyntacticdepen-dencieshh,m,liwewillassumethattheyareinthevalidrangeforx,i.e.0≤h≤n,1≤m≤n,h6=mandl∈Rsyn,whereh=0standsforaspecialroottoken.Similarly,forsemanticdepen-dencieshp,a,riwewillassumethatppointstoapredicateofx,1≤a≤nandr∈Rsem.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
221
Ajointmodelforsyntacticandsemanticdepen-dencyparsingcouldbedefinedas:argmaxy,zssyn(x,y)+ssrl(x,z,y).(1)Intheequation,ssyn(x,y)givesascoreforthesyntactictreey.Intheliterature,itisstandardtousearc-factoredmodelsdefinedasssyn(x,y)=Xyh,m,l=1ssyn(x,h,m,l),(2)whereweoverloadssyntobeafunctionthatcomputesscoresforindividualsyntacticdepen-dencies.Inlineardiscriminativemodelsonehasssyn(x,h,m,l)=wsyn·fsyn(x,h,m,l),wherefsynisafeaturevectorforasyntacticdependencyandwsynisavectorofparameters(McDonaldetal.,2005).InSection6wedescribehowwetrainedscorefunctionswithdiscriminativemethods.TheotherterminEq.1,ssrl(x,z,y),givesascoreforasemanticdependencystructurezusingfeaturesofthesyntacticstructurey.Previousworkhasempiricallyprovedtheimportanceofexploit-ingsyntacticfeaturesinthesemanticcomponent(GildeaandJurafsky,2002;XueandPalmer,2004;Punyakanoketal.,2008).However,withoutfurtherassumptions,thispropertymakestheoptimizationproblemcomputationallyhard.Onesimpleapprox-imationistouseapipelinemodel:firstcomputetheoptimalsyntactictreey,andthenoptimizeforthebestsemanticstructurezgiveny.Intherestofthepaperwedescribeamethodthatsearchesoversyn-tacticandsemanticdependencystructuresjointly.Wefirstnotethatforafixedsemanticdependency,thesemanticcomponentwilltypicallyrestrictthesyntacticfeaturesrepresentingthedependencytoaspecificsubtreeofy.Forexample,previousworkhasrestrictedsuchfeaturestothesyntacticpaththatlinksapredicatewithanargument(Moschitti,2004;Johansson,2009),andinthispaperweemploythisrestriction.Figure1givesanexampleofasub-tree,wherewehighlightthesyntacticpaththatcon-nectsthesemanticdependencybetween“play”and“Mary”withroleARG0.Formally,forapredicatep,argumentaandrolerwedefinealocalsyntacticsubtreeπp,a,rrepre-sentedasavector:πp,a,rh,m,lindicatesifadependencyhh,m,liispartofthesyntacticpaththatlinkspred-icatepwithtokenaandroler.1Givenfullsyntacticandsemanticstructuresyandzitistrivialtocon-structavectorπthatconcatenatesvectorsπp,a,rforallhp,a,riinz.Thesemanticmodelbecomesssrl(x,z,π)=Xzp,a,r=1ssrl(x,p,a,r,πp,a,r),(3)wheressrlcomputesascoreforasemanticde-pendencyhp,a,ritogetherwithitssyntacticpathπp,a,r.Asinthesyntacticcomponent,thisfunctionistypicallydefinedasalinearfunctionoverasetoffeaturesofthesemanticdependencyanditspath.Theinferenceproblemofourjointmodelis:argmaxy,z,πssyn(x,y)+ssrl(x,z,π)(4)subjecttocTree:yisavaliddependencytreecRole:∀p,r:Xazp,a,r≤1cArg:∀p,a:Xrzp,a,r≤1cPath:∀p,a,r:ifzp,a,r=1thenπp,a,risapathfromptoa,otherwiseπp,a,r=0cSubtree:∀p,a,r:πp,a,risasubtreeofyConstraintcTreedictatesthatyisavaliddepen-dencytree;see(Martinsetal.,2009)foradetailedspecification.Thenexttwosetsofconstraintscon-cernthesemanticstructureonly.cRoleimposesthateachsemanticroleisrealizedatmostonce.2Con-versely,cArgdictatesthatanargumentcanrealizeatmostonesemanticroleinapredicate.Thefinaltwosetsofconstraintsmodelthesyntactic-semanticinterdependencies.cPathimposesthateachπp,a,rrepresentsasyntacticpathbetweenpandawhen-everthereexistsasemanticrelation.Finally,cSub-treeimposesthatthepathsinπareconsistentwiththefullsyntacticstructure,i.e.theyaresubtrees.1Inthispaperwesaythatstructuresπp,a,rarepathsfrompredicatestoarguments,buttheycouldbemoregeneralsub-trees.TheconditiontobuildajointsystemisthatthesesubtreesmustbeparseableinthewaywedescribeinSection3.1.2Ingeneralasemanticrolecanberealizedwithmorethanoneargument,thoughitisrare.Itisnothardtomodifyourframeworktoallowforamaximumnumberofoccurrencesofasemanticrole.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
222
InSection3wedefineaprocessthatoptimizesthesemanticstructureignoringconstraintcSubtree.TheninSection4wedescribeadualdecompositionmethodthatusesthefirstprocessrepeatedlytosolvethejointproblem.3SRLasAssignmentInthissectionweframetheproblemoffindingse-manticdependenciesasalinearassignmenttask.Theproblemweoptimizeis:argmaxz,πssrl(x,z,π)(5)subjecttocRole,cArg,cPathInthiscasewedroppedthefullsyntacticstructureyfromtheoptimizationinEq.4,aswellasthecorrespondingconstraintscTreeandcSubtree.Asaconsequence,wenotethatthesyntacticpathsπarenottiedtoanyconsistencyconstraintotherthaneachofthepathsbeingawell-formedsequenceofdependencieslinkingthepredicatetotheargument.Inotherwords,theoptimalsolutioninthiscasedoesnotguaranteethatthesetofpathsfromapredicatetoallofitsargumentssatisfiestreeconstraints.Wefirstdescribehowthesepathscanbeoptimizedlocally.ThenweshowhowtofindasolutionzsatisfyingcRoleandcArgusinganassignmentalgorithm.3.1LocalOptimizationofSyntacticPathsLetbzandbπbetheoptimalvaluesofEq.5.Foranyhp,a,ri,let˜πp,a,r=argmaxπp,a,rssrl(x,p,a,r,πp,a,r).(6)Foranyhp,a,risuchthatbzp,a,r=1ithastobethatbπp,a,r=˜πp,a,r.Ifthiswasnottrue,replacingbπp,a,rwith˜πp,a,rwouldimprovetheobjectiveofEq.5withoutviolatingtheconstraints,thuscontradictingthehypothesisaboutoptimalityofbπ.Therefore,foreachhp,a,riwecanoptimizeitsbestsyntacticpathlocallyasdefinedinEq.6.Inthispaper,wewillassumeaccesstoalistoflikelysyntacticpathsforeachpredicatepandargu-mentcandidatea,suchthattheoptimizationinEq.6canbesolvedexplicitlybyloopingovereachpathinthelist.Themainadvantageofthismethodisthat,sincepathsareprecomputed,ourmodelcanmakeunrestricteduseofsyntacticpathfeatures.(1)Mary(2)plays(3)guitar(4)NULL(5)NULL(6)NULL(1)ARG0(2)ARG1(3)ARG2(4)NULL(5)NULL(6)NULLW1,1W4,2W2,3W3,4W5,5W6,6W1,1W4,2W2,3W3,4W5,5W6,6W1,1W4,2W2,3W3,4W5,5W6,6W1,1W4,2W2,3W3,4W5,5W6,6W1,1W4,2W2,3W3,4W5,5W6,6W1,1W4,2W2,3W3,4W5,5W6,6Figure2:Illustrationoftheassignmentgraphforthesen-tence“Maryplaysguitar”,wherethepredicate“plays”canhaveuptothreeroles:ARG0(agent),ARG1(theme)andARG2(benefactor).NodeslabeledNULLrepresentanullroleortoken.Highlightededgesarethecorrectassignment.Itissimpletoemployaprobabilisticsyntacticde-pendencymodeltocreatethelistoflikelypathsforeachpredicate-argumentpair.Intheexperimentsweexplorethisapproachandshowthatwithanaverageof44pathsperpredicatewecanrecover86.2%ofthecorrectpaths.Weleaveforfutureworkthedevelopmentofef-ficientmethodstorecoverthemostlikelysyntacticstructurelinkinganargumentwithitspredicate.3.2TheAssignmentAlgorithmComingbacktosolvingEq.5,itiseasytoseethatanoptimalsolutionsatisfyingconstraintscRoleandcArgcanbefoundwithalinearassignmentalgorithm.Theprocesswedescribedeterminesthepredicate-argumentrelationsseparatelyforeachpredicate.AssumeabipartitegraphofsizeNwithrolenodesr1…rNononesideandargumentnodesa1…aNontheotherside.Assumealsoamatrixofnon-negativescoresWi,jcorrespondingtoassigningargumentajtoroleri.Alinearassignmentalgo-rithmfindsabijectionf:i→jfromrolestoargu-mentsthatmaximizesPNi=1Wi,f(i).TheHungarianalgorithmfindstheexactsolutiontothisprobleminO(N3)time(Kuhn,1955;Burkardetal.,2009).Allthatisleftistoconstructabipartitegraphrep-resentingpredicaterolesandsentencetokens,suchthatsomerolesandtokenscanbeleftunassigned,whichisacommonsettingforassignmenttasks.Al-gorithm1describesaprocedureforconstructingaweightedbipartitegraphforSRL,andFigure2il-lustratesanexampleofabipartitegraph.Wethen
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
223
Algorithm1ConstructionofanAssignmentGraphforSemanticRoleLabelingLetpbeapredicatewithkpossibleroles.Letnbethenumberofargumentcandidatesinthesentence.Thisal-gorithmcreatesabipartitegraphwithN=n+kverticesoneachside.1.Createroleverticesrifori=1…N,where•for1≤i≤k,riisthei-throle,•for1≤i≤n,rk+iisaspecialNULLrole.2.Createargumentverticesajforj=1…N,where•for1≤j≤n,ajisthej-thargumentcandidate,•for1≤j≤k,an+jisaspecialNULLargument.3.DefineamatrixofmodelscoresS∈R(k+1)×n:(a)Optimizationofsyntacticpaths:For1≤i≤k,1≤j≤nSi,j=maxπp,aj,rissrl(x,p,aj,ri,πp,aj,ri)(b)ScoresofNULLassignments3:For1≤j≤nSk+1,j=04.LetS0=mini,jSi,j,theminimumofanyscoreinS.Defineamatrixofnon-negativescoresW∈RN×Nasfollows:(a)for1≤i≤k,1≤j≤nWi,j=Si,j−S0(b)fork
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
225
dencytogetherwiththesyntacticpathconnectingthepredicateandtheargument.Thatmethodusesanapproximateparsingalgorithmthatemploysk-bestinferenceandbeamsearch.Similarly,Llu´ısetal.(2009)definedajointmodelthatforcesthepredi-catestructuretoberepresentedinthesyntacticde-pendencytree,byenrichingarcswithsemanticin-formation.Thesemanticcomponentusesfeaturesofpre-computedsyntacticstructuresthatmaydivergefromthejointstructure.Incontrast,ourjointpars-ingmethodisexactwheneverthedualdecomposi-tionalgorithmconverges.Titovetal.(2009)augmentedatransition-baseddependencyparserwithoperationsthatproducesynchronousderivationsofsyntacticandsemanticstructures.Insteadofexplicitlyrepresentingseman-ticdependenciestogetherwithasyntacticpath,theyinducelatentrepresentationsoftheinteractionsbe-tweensyntacticandsemanticlayers.Inallworksmentionedthemodelhasnocon-trolofassignmentconstraintsthatdisallowlabel-ingmultipleargumentswiththesamesemanticrole.Punyakanoketal.(2008)firstintroducedasystemthatexplicitlycontrolstheseconstraints,aswellasotherconstraintsthatlookatpairwiseassignmentswhichwecannotmodel.TheysolveSRLusinggeneral-purposeIntegerLinearProgramming(ILP)methods.Insimilarspirit,RiedelandMcCallum(2011)presentedamodelforextractingstructuredeventsthatcontrolsinteractionsbetweenpredicate-argumentassignments.Theytakeintoaccountpair-wiseassignmentsandsolvetheoptimizationprob-lemwithdualdecomposition.Morerecently,Dasetal.(2012)proposedadualdecompositionmethodthatdealswithseveralassignmentconstraintsforpredicate-argumentrelations.TheirmethodisanalternativetogeneralILPmethods.Toourknowl-edge,ourworkisthefirstthatframesSRLasalinearassignmenttask,forwhichsimpleandexactalgo-rithmsexist.Weshouldnotethattheseworksmodelpredicate-argumentrelationswithassignmentcon-straints,butnoneofthempredictstheunderlyingsyntacticstructure.OurdualdecompositionmethodfollowsfromthatofKooetal.(2010).Inbothcasestwoseparatepro-cessespredictsyntacticdependencystructures,andthedualdecompositionalgorithmseeksagreementatthelevelofindividualdependencies.Onedif-ferenceisthatoursemanticprocesspredictspartialsyntax(restrictedtosyntacticpathsconnectingpred-icatesandarguments),whileintheircaseeachofthetwoprocessespredictsthefullsetofdependencies.6ExperimentsWepresentexperimentsusingoursyntactic-semanticparserontheCoNLL-2009SharedTaskEnglishbenchmark(Hajiˇcetal.,2009).ItconsistsoftheusualWSJtraining/development/testsectionsmappedtodependencytrees,augmentedwithse-manticpredicate-argumentrelationsfromPropBank(Palmeretal.,2005)andNomBank(Meyersetal.,2004)alsorepresentedasdependencies.Italsocon-tainsaPropBankedportionoftheBrowncorpusasanout-of-domaintestset.Ourgoalwastoevaluatethecontributionsofpars-ingalgorithmsinthefollowingconfigurations:BasePipelineRunsasyntacticparserandthenrunsanSRLparserconstrainedtopathsofthebestsyntactictree.IntheSRLitonlyenforcescon-straintcArg,bysimplyclassifyingthecandi-dateargumentineachpathintooneofthepos-siblesemanticrolesorasNULL.PipelinewithAssignmentRunstheassignmental-gorithmforSRL,enforcingconstraintscRoleandcArg,butconstrainedtopathsofthebestsyntactictree.ForestRunstheassignmentalgorithmforSRLonalargesetofprecomputedsyntacticpaths,de-scribedbelow.ThisconfigurationcorrespondstorunningDualDecompositionforasingleit-eration,andisnotguaranteedtopredictconsis-tentsyntacticandsemanticstructures.DualDecomposition(DD)Runsdualdecomposi-tionusingtheassignmentalgorithmonthesetofprecomputedpaths.Syntacticandsemanticstructuresareconsistentwhenitreachescon-vergence.Allfoursystemsusedthesametypeofdiscrimina-tivescorersandfeatures.Nextweprovidedetailsaboutthesesystems.Thenwepresenttheresults.6.1ImplementationSyntacticmodelWeusedtwodiscriminativearc-factoredmodelsforlabeleddependencyparsing:a
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
226
first-ordermodel,andasecond-ordermodelwithgrandchildreninteractions,bothreimplementationsoftheparsersbyMcDonaldetal.(2005)andCar-reras(2007)respectively.Inbothcasesweusedprojectivedependencyparsingalgorithmsbasedon(Eisner,2000).4Tolearnthemodels,weusedalog-linearlossfunctionfollowingKooetal.(2007),whichtrainsprobabilisticdiscriminativeparsers.Attesttime,weusedtheprobabilisticparserstocomputemarginalprobabilitiesp(h,m,l|x),us-inginside-outsidealgorithmsforfirst/second-ordermodels.Hence,foreitheroftheparsingmodels,wealwaysobtainatableoffirst-ordermarginalscores,withonescoreperlabeleddependency.Thenwerunfirst-orderinferencewiththesemarginalstoob-tainthebesttree.Wefoundthatthehigher-orderparserperformedequallywellondevelopmentus-ingthismethodasusingsecond-orderinferencetopredicttrees:sinceweruntheparsermultipletimeswithinDualDecomposition,ourstrategyresultsinfasterparsingtimes.PrecomputedPathsBothForestandDualDe-compositionrunassignmentonasetofprecomputedpaths,andhereweexplainhowwebuildit.Wefirstobservedthat98.4%ofthecorrectargumentsinde-velopmentdataareeitherdirectdescendantsofthepredicate,directdescendantsofanancestorofthepredicate,oranancestorofthepredicate.5Allmeth-odswetestarerestrictedtothissyntacticscope.Togeneratealistofpaths,wedidasfollows:•Calculatemarginalsofunlabeleddependenciesusingthefirst-orderparser:p(h,m|x)=Plp(h,m,l|x).Notethatforeachm,theprobabilitiesp(h,m|x)forallhformadistri-bution(i.e.theysumtoone).Then,foreachm,keepthemost-likelydependenciesthatcoveratleast90%ofthemass,andprunetherest.•Startingfromapredicatep,generateapathbytakinganynumberofdependenciesthatas-cend,andoptionallyaddingonedependencythatdescends.Weconstrainedpathstobepro-jective,andtohaveamaximumnumberof64Ourmethodallowstousenon-projectivedependencypars-ingmethodsseamlessly.5ThisisspecifictoCoNLL-2009dataforEnglish.Ingen-eral,forotherlanguagesthecoverageoftheserulesmaybelower.Weleavethisquestiontofuturework.ascendantdependencies.•Labeleachunlabelededgehh,miinthepathswithl=argmaxlp(h,m,l|x).Ondevelopmentdata,thisproceduregeneratedanaverageof43.8pathsperpredicatethatcover86.2%ofthecorrectpaths.Incontrast,enumeratingpathsofthesingle-besttreecovers79.4%ofcorrectpathsforthefirst-orderparser,and82.2%forthesecond-orderparser.6SRLmodelWeusedadiscriminativemodelwithsimilarfeaturestothoseinthesystemofJohansson(2009).Inaddition,weincludedthefollowing:•Unigram/bigram/trigrampathfeatures.Foralln-gramsinthesyntacticpath,patternsofwordsandPOStags(e.g.,mary+loves+to,mary+VB+to).•Voicefeatures.Thepredicatevoicetogetherwiththeword/POSoftheargument(e.g.,pas-sive+mary).•Pathcontinuity.Countofnon-consecutiveto-kensinapredicate-argumentpath.TotrainSRLmodelsweusedtheaveragedper-ceptron(Collins,2002).ForthebasepipelinewetrainedstandardSRLclassifiers.FortherestofmodelsweusedthestructuredPerceptronrunningtheassignmentalgorithmasinferenceroutine.Inthiscase,wegeneratedalargesetofsyntacticpathsfortrainingusingtheproceduredescribedabove,andwesetthelossfunctiontopenalizemistakesinpredictingthesemanticroleofargumentsandtheirsyntacticpath.DualDecompositionWeaddedaparameterβweightingthesyntacticandsemanticcomponentsofthemodelasfollows:(1−β)ssyn(x,y)+βssrl(x,z,π).Assyntacticscoresweusednormalizedmarginalprobabilitiesofdependencies,eitherfromthefirstorthehigher-orderparser.ThescoresofallfactorsoftheSRLmodelwerenormalizedateverysen-tencetobebetween-1and1.Therestofdetails6Onecanevaluatethemaximumrecalloncorrectargumentsthatcanbeobtained,irrespectiveofwhetherthesyntacticpathiscorrect:forthesetofpathsitis98.3%,whileforsingle-besttreesitis91.9%and92.7%forfirstandsecond-ordermodels.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
227
oLASUASsempsemrsemF1semppPipeline185.3288.8686.2367.6775.8345.64w.Assig.185.3288.8684.0871.8277.4751.17Forest—80.6773.6076.9751.33Pipeline287.7790.9687.0768.6576.7747.07w.Assig.287.7790.9685.2173.4178.8753.80Table1:Resultsondevelopmentforthebaselineandas-signmentpipelines,runningfirstandsecond-ordersyn-tacticparsers,andtheForestmethod.oindicatestheor-derofsyntacticinference.ofthemethodwereimplementedfollowingKooetal.(2010),includingthestrategyfordecreasingthestepsizeαt.Weranthealgorithmforupto500it-erations,withinitialstepsizeof0.001.6.2ResultsToevaluatesyntacticdependenciesweuseunla-beledattachmentscore(UAS),i.e.,thepercentageofwordswiththecorrecthead,andlabeledattach-mentscores(LAS),i.e.,thepercentageofwordswiththecorrectheadandsyntacticlabel.Semanticpredicate-argumentrelationsareevaluatedwithpre-cision(semp),recall(semr)andF1measure(semF1)attheleveloflabeledsemanticdependencies.Inad-dition,wemeasurethepercentageofperfectlypre-dictedpredicatestructures(sempp).7Table1showstheresultsonthedevelopmentsetforourthreefirstmethods.WecanseethatthepipelinemethodsrunningassignmentimproveoverthebaselinepipelinesinsemanticF1byabout2points,duetotheapplicationofthecRoleconstraint.TheForestmethodalsoshowsanimprovementinrecallofsemanticroleswithrespecttothepipelinemethods.Presumably,thesetofpathsavailableintheForestmodelallowstorecognizeahighernum-berofargumentsatanexpenseofalowerpreci-sion.Regardingthepercentageofperfectpredicate-argumentstructuresthereisaremarkableimprove-mentinthesystemsthatapplythefullsetofcon-7Ourevaluationmetricsdifferslightlyfromtheofficialmet-ricatCoNLL-2009.Thatmetricconsiderspredicatesensesasspecialsemanticdependenciesand,thus,itincludestheminthecalculationoftheevaluationmetrics.Inthispaper,wearenotaddressingpredicatesensedisambiguationand,conse-quently,weignorepredicatesenseswhenpresentingevaluationresults.WhenwereporttheperformanceofCoNLLsystems,theirscoreswillbenoticeablylowerthanthescoresreportedatthesharedtask.Thisisbecausepredicatedisambiguationisareasonablysimpletaskwithaveryhighbaselinearound90%.oβLASUASsempsemrsemF1sempp%conv10.185.3288.8684.0971.8477.4851.7710010.485.3688.9184.0771.9477.5351.8510010.585.3888.9384.0872.0377.5951.9610010.685.4188.9584.0572.1977.6752.0399.810.785.4489.0084.1072.4277.8252.2499.710.885.4889.0283.9972.6977.9452.5799.510.985.3988.9383.6872.8277.8852.4999.820.187.7890.9685.2073.1178.6953.7410020.487.7890.9685.2173.1278.7053.7410020.587.7890.9685.1973.1278.7053.7210020.687.7890.9685.2073.1378.7053.7299.920.787.7890.9685.1973.1378.7053.7299.820.887.8090.9885.2073.1878.7453.7799.820.987.8491.0285.2073.2378.7653.82100Table2:Resultsofthedualdecompositionmethodondevelopmentdata,fordifferentvaluesoftheβparame-ter.oistheorderofthesyntacticparser.%convisthepercentageofexamplesthatconverged.straintsusingtheassignmentalgorithm.WebelievethatthecRoleconstraintthatensuresnorepeatedrolesforagivenpredicateisakeyfactortopredictthefullsetofargumentsofapredicate.TheForestconfigurationisthestartingpointtorunthedualdecompositionalgorithm.Weranex-perimentsforvariousvaluesoftheβparameter.Ta-ble2showstheresults.Weseethatasweincreaseβ,theSRLcomponenthasmorerelativeweight,andthesyntacticstructurechanges.TheDDmethodsarealwaysabletoimproveovertheForestmethods,andfindconvergenceinmorethan99.5%ofsentences.Comparedtothepipelinerunningassignment,DDimprovessemanticF1forfirst-orderinference,butnotforhigher-orderinference,suggestingthat2ndorderpredictionsofpathsarequiteaccurate.Wealsoobserveslightbenefitsinsyntacticaccuracy.Table3presentsresultsofoursystemonthetestsets,wherewerunPipelinewithAssignmentandDualDecompositionwithourbestconfigura-tion(β=0.8/0.9for1st/2ndordersyntax).Forcomparison,thetablealsoreportstheresultsofthebestCoNLL–2009jointsystem,Merlo09(Ges-mundoetal.,2009),whichprovedtobeverycom-petitiverankingthirdintheclosedchallenge.WealsoincludeLlu´ıs09(Llu´ısetal.,2009),whichisan-otherjointsyntactic-semanticsystemfromCoNLL–2009.8IntheWSJtestDDobtainsthebestsyntacticaccuracies,whilethePipelineobtainsthebestse-8AnothersystemtocomparetoisthejointsystembyJo-hansson(2009).Unfortunately,adirectcomparisonisnotpossi-blebecauseitisevaluatedontheCoNLL-2008datasets,which
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
228
WSJLASUASsempsemrsemF1semppLlu´ıs0987.4889.9173.8767.4070.4939.68Merlo0988.7991.2681.0076.4578.6654.80Pipe-Assig1st86.8589.6885.1273.7879.0554.12DD1st87.0489.8985.0374.5679.4554.92Pipe-Assig2nd89.1991.6286.1175.1680.2655.96DD2nd89.2191.6486.0174.8480.0455.73BrownLASUASsempsemrsemF1semppLlu´ıs0980.9285.9662.2959.2260.7129.79Merlo0980.8486.3268.9763.0665.8938.92Pipe-Assig1st80.9686.5872.9160.1665.9338.44DD1st81.1886.8672.5360.7666.1238.13Pipe-Assig2nd82.5687.9873.9461.6367.2338.99DD2nd82.6188.0474.1261.5967.2838.92Table3:ComparativeresultsontheCoNLL–2009En-glishtestsets,namelytheWSJtest(toptable)andtheoutofdomaintestfromtheBrowncorpus(bottomtable).manticF1.ThebottompartofTable3presentsre-sultsontheout-of-domainBrowntestcorpus.Inthiscase,DDobtainsslightlybetterresultsthantherest,bothintermsofsyntacticaccuracyandsemanticF1.Table4showsstatisticalsignificancetestsforthesyntacticLASandsemanticF1scoresofTable3.Wehaveappliedthesigntest(Wackerlyetal.,2007)andapproximaterandomizationtests(Yeh,2000)toallpairsofsystemsoutputs.Thedifferencesbe-tweensystemsintheWSJtestcanbeconsideredsignificantinalmostallcaseswithp=0.05.IntheBrowntestset,resultsaremoreunstableanddif-ferencesarenotsignificantingeneral,probablybe-causeoftherelativelysmallsizeofthattest.Regardingrunningtimes,ourimplementationofthebaselinepipelinewith2ndorderinferenceparsesthedevelopmentset(1,334sentences)inlessthan7minutes.Runningassignmentinthepipelinein-creasesparsingtimeby∼8%duetotheoverheadfromtheassignmentalgorithm.TheForestmethod,withanaverageof61.3pathsperpredicate,is∼13%slowerthanthepipelineduetotheexplorationofthespaceofprecomputedpaths.Finally,DualDecom-positionwith2ndorderinferenceconvergesin36.6iterationspersentenceonaverage.Thefirstitera-tionofDDhastoperformroughlythesameworkasForest,whilesubsequentiterationsonlyneedtore-parsethesentencewithrespecttothedualup-areslightlydifferent.However,notethatMerlo09isanapplica-tionofthesystembyTitovetal.(2009).InthatpaperauthorsreportresultsontheCoNLL-2008datasets,andtheyarecom-parabletoJohansson’s.WSJBrownMEPA1DD1PA2DD2MEPA1DD1PA2DD2LL◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)•(cid:3)(cid:4)◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)(cid:3)(cid:4)(cid:3)(cid:4)(cid:3)(cid:4)◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)ME◦•◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)••PA1◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)•◦•(cid:4)◦•(cid:3)(cid:4)DD1◦•(cid:3)(cid:4)◦•(cid:3)(cid:4)◦•(cid:4)◦•(cid:3)(cid:4)PA2•(cid:3)(cid:4)Table4:StatisticaltestsofsignificanceforLASandsemF1differencesbetweenpairsofsystemsfromTable3.◦/•=LASdifferenceissignificantbythesign/approxi-materandomizationtestsat0.05level.(cid:3)/(cid:4)=samemean-ingforsemF1.Thelegendforsystemsis:LL:Llu´ıs09,ME:Merlo09,PA1/2:PipelinewithAssignment,1st/2ndorder,DD1/2:DualDecomposition,1st/2ndorder.dates,whichareextremelysparse.Ourcurrentim-plementationdidnottakeadvantageofthesparsityofupdates,andoverall,DDwasonaverage13timesslowerthanthepipelinerunningassignmentand15timesslowerthanthebaselinepipeline.7ConclusionWehaveintroducedefficientmethodstoparsesyntacticdependencystructuresaugmentedwithpredicate-argumentrelations,withtwokeyideas.Oneistopredictthelocalsyntacticstructurethatlinksapredicatewithitsarguments,andseekagree-mentwiththefullsyntacticstructureusingdualdecompositiontechniques.Thesecondistocon-trollinearassignmentconstraintsinthepredicate-argumentstructure.Inexperimentsweobservelargeimprovementsresultingfromtheassignmentconstraints.Asforthedualdecompositiontechniqueforjointparsing,itdoesimproveoverthepipelineswhenweuseafirstorderparser.Thismeansthatinthisconfigu-rationtheexplicitsemanticfeatureshelptofindasolutionthatisbetterinbothlayers.Tosomeex-tent,thisempiricallyvalidatestheresearchobjec-tiveofjointmodels.However,whenwemovetosecond-orderparsersthedifferenceswithrespecttothepipelineareinsignificant.Itistobeexpectedthatassyntacticparsersimprove,theneedofjointmethodsislesscritical.Itremainsanopenquestiontovalidateiflargeimprovementscanbeachievedbyintegratingsyntactic-semanticfeatures.Tostudythisquestion,itisnecessarytohaveefficientpars-ingalgorithmsforjointdependencystructures.Thispapercontributeswithamethodthathasoptimality
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
229
guaranteeswheneveritconverges.Ourmethodcanincorporatericherfamiliesoffea-tures.Itisstraightforwardtoincorporatebetterse-manticrepresentationsofpredicatesandargumentsthanjustplainwords,e.g.byexploitingWordNetordistributionalrepresentationsasin(Zapirainetal.,2013).Potentially,thiscouldresultinlargerim-provementsintheperformanceofsyntacticandse-manticparsing.Itisalsonecessarytoexperimentwithdiffer-entlanguages,wheretheperformanceofsyntacticparsersislowerthaninEnglish,andhencethereispotentialforimprovement.Ourtreatmentoflocalsyntacticstructurethatlinkspredicateswithargu-ments,basedonexplicitenumerationoflikelypaths,wassimplistic.Futureworkshouldexploremeth-odsthatmodelthesyntacticstructurelinkingpredi-cateswitharguments:wheneverthisstructurecanbeparsedefficiently,ourdualdecompositionalgorithmcanbeemployedtodefineanefficientjointsystem.AcknowledgmentsWethanktheeditorandtheanonymousreviewersfortheirvaluablefeedback.ThisworkwasfinancedbytheEuropeanCommissionfortheXLikeproject(FP7-288342);andbytheSpanishGovernmentforprojectOpenMT-2(TIN2009-14675-C03-01),projectSkater(TIN2012-38584-C06-01),andaRam´onyCajalcontractforXavierCarreras(RYC-2008-02223).ReferencesRainerBurkard,MarioDell’Amico,andSilvanoMartello.2009.AssignmentProblems.SocietyforIndustrialandAppliedMathematics.XavierCarrerasandLlu´ısM`arquez.2005.Introduc-tiontotheCoNLL-2005sharedtask:Semanticrolelabeling.InProceedingsoftheNinthConferenceonComputationalNaturalLanguageLearning(CoNLL-2005),pages152–164,AnnArbor,Michigan,June.XavierCarreras.2007.Experimentswithahigher-orderprojectivedependencyparser.InProceedingsoftheCoNLLSharedTaskSessionofEMNLP-CoNLL2007,pages957–961,Prague,CzechRepublic,June.MichaelCollins.2002.Discriminativetrainingmeth-odsforHiddenMarkovModels:Theoryandexperi-mentswithPerceptronalgorithms.InProceedingsofthe2002ConferenceonEmpiricalMethodsinNaturalLanguageProcessing,pages1–8,July.DipanjanDas,Andr´eF.T.Martins,andNoahA.Smith.2012.Anexactdualdecompositionalgorithmforshallowsemanticparsingwithconstraints.InPro-ceedingsoftheFirstJointConferenceonLexicalandComputationalSemantics-Volume1:Proceedingsofthemainconferenceandthesharedtask,andVolume2:ProceedingsoftheSixthInternationalWorkshoponSemanticEvaluation,SemEval’12,pages209–217,Stroudsburg,PA,USA.JasonEisner.2000.Bilexicalgrammarsandtheircubic-timeparsingalgorithms.InHarryBuntandAntonNijholt,editors,AdvancesinProbabilisticandOtherParsingTechnologies,pages29–62.KluwerAcademicPublishers,October.AndreaGesmundo,JamesHenderson,PaolaMerlo,andIvanTitov.2009.Alatentvariablemodelofsyn-chronoussyntactic-semanticparsingformultiplelan-guages.InProceedingsoftheThirteenthConfer-enceonComputationalNaturalLanguageLearning(CoNLL2009):SharedTask,pages37–42,Boulder,Colorado,June.DanielGildeaandDanielJurafsky.2002.Automaticla-belingofsemanticroles.ComputationalLinguistics,28(3):245–288,September.DanielGildeaandMarthaPalmer.2002.Thenecessityofparsingforpredicateargumentrecognition.InPro-ceedingsof40thAnnualMeetingoftheAssociationforComputationalLinguistics,pages239–246,Philadel-phia,Pennsylvania,USA,July.JanHajiˇc,MassimilianoCiaramita,RichardJohans-son,DaisukeKawahara,MariaAnt`oniaMart´ı,Llu´ısM`arquez,AdamMeyers,JoakimNivre,SebastianPad´o,JanˇStˇep´anek,PavelStraˇn´ak,MihaiSurdeanu,NianwenXue,andYiZhang.2009.TheCoNLL-2009sharedtask:Syntacticandsemanticdependen-ciesinmultiplelanguages.InProceedingsofthe13thConferenceonComputationalNaturalLanguageLearning(CoNLL-2009):SharedTask,pages1–18,Boulder,Colorado,USA,June.RichardJohansson.2009.Statisticalbistrataldepen-dencyparsing.InProceedingsofthe2009ConferenceonEmpiricalMethodsinNaturalLanguageProcess-ing,pages561–569,Singapore,August.TerryKoo,AmirGloberson,XavierCarreras,andMichaelCollins.2007.Structuredpredictionmod-elsviathematrix-treetheorem.InProceedingsofthe2007JointConferenceonEmpiricalMethodsinNat-uralLanguageProcessingandComputationalNatu-ralLanguageLearning(EMNLP-CoNLL),pages141–150,Prague,CzechRepublic,June.TerryKoo,AlexanderM.Rush,MichaelCollins,TommiJaakkola,andDavidSontag.2010.Dualdecompo-sitionforparsingwithnon-projectiveheadautomata.InProceedingsofthe2010ConferenceonEmpiri-calMethodsinNaturalLanguageProcessing,pages1288–1298,Cambridge,MA,October.
l
D
o
w
n
o
a
d
e
d
f
r
o
m
h
t
t
p
:
/
/
d
i
r
e
c
t
.
m
i
t
.
e
d
u
/
t
a
c
l
/
l
a
r
t
i
c
e
–
p
d
f
/
d
o
i
/
.
1
0
1
1
6
2
/
t
l
a
c
_
a
_
0
0
2
2
2
1
5
6
6
6
5
3
/
/
t
l
a
c
_
a
_
0
0
2
2
2
p
d
.
f
b
y
g
u
e
s
t
t
o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3
230
HaroldW.Kuhn.1955.TheHungarianmethodfortheassignmentproblem.NavalResearchLogisticsQuar-terly,2(1-2):83–97.XavierLlu´ıs,StefanBott,andLlu´ısM`arquez.2009.Asecond-orderjointeisnermodelforsyntacticandsemanticdependencyparsing.InProceedingsoftheThirteenthConferenceonComputationalNatu-ralLanguageLearning(CoNLL2009):SharedTask,pages79–84,Boulder,Colorado,June.Llu´ısM`arquez,XavierCarreras,KennethC.Litkowski,andSuzanneStevenson.2008.SemanticRoleLabel-ing:AnIntroductiontotheSpecialIssue.Computa-tionalLinguistics,34(2):145–159,June.Andr´eMartins,NoahSmith,andEricXing.2009.Con-ciseintegerlinearprogrammingformulationsforde-pendencyparsing.InProceedingsoftheJointCon-ferenceofthe47thAnnualMeetingoftheACLandthe4thInternationalJointConferenceonNaturalLan-guageProcessingoftheAFNLP,pages342–350,Sun-tec,Singapore,August.RyanMcDonald,KobyCrammer,andFernandoPereira.2005.Onlinelarge-margintrainingofdependencyparsers.InProceedingsofthe43rdAnnualMeet-ingoftheAssociationforComputationalLinguistics(ACL’05),pages91–98,AnnArbor,Michigan,June.AdamMeyers,RuthReeves,CatherineMacleod,RachelSzekely,VeronikaZielinska,BrianYoung,andRalphGrishman.2004.TheNomBankProject:Aninterimreport.InA.Meyers,editor,HLT-NAACL2004Work-shop:FrontiersinCorpusAnnotation,pages24–31,Boston,Massachusetts,USA,May.AlessandroMoschitti.2004.Astudyonconvolutionkernelsforshallowstatisticparsing.InProceedingsofthe42ndMeetingoftheAssociationforComputa-tionalLinguistics(ACL’04),MainVolume,pages335–342,Barcelona,Spain,July.JoakimNivreandJensNilsson.2005.Pseudo-projectivedependencyparsing.InProceedingsofthe43rdAnnualMeetingoftheAssociationforComputa-tionalLinguistics(ACL’05),pages99–106,AnnAr-bor,Michigan,June.MarthaPalmer,DanielGildea,andPaulKingsbury.2005.ThePropositionBank:Anannotatedcorpusofsemanticroles.ComputationalLinguistics,31(1):71–106,March.VasinPunyakanok,DanRoth,andWentauYih.2008.Theimportanceofsyntacticparsingandinferenceinsemanticrolelabeling.ComputationalLinguistics,34(3):257–287,June.SebastianRiedelandAndrewMcCallum.2011.Fastandrobustjointmodelsforbiomedicaleventextraction.InProceedingsofthe2011ConferenceonEmpiricalMethodsinNaturalLanguageProcessing,pages1–12,Edinburgh,Scotland,UK.,July.AlexanderMRush,DavidSontag,MichaelCollins,andTommiJaakkola.2010.Ondualdecompositionandlinearprogrammingrelaxationsfornaturallanguageprocessing.InProceedingsofthe2010ConferenceonEmpiricalMethodsinNaturalLanguageProcessing,pages1–11,Cambridge,MA,October.DavidSontag,AmirGloberson,andTommiJaakkola.2010.Introductiontodualdecompositionforinfer-ence.InS.Sra,S.Nowozin,andS.J.Wright,editors,OptimizationforMachineLearning.MITPress.MihaiSurdeanu,RichardJohansson,AdamMeyers,Llu´ısM`arquez,andJoakimNivre.2008.Theconll2008sharedtaskonjointparsingofsyntacticandse-manticdependencies.InCoNLL2008:ProceedingsoftheTwelfthConferenceonComputationalNatu-ralLanguageLearning,pages159–177,Manchester,England,August.IvanTitov,JamesHenderson,PaolaMerlo,andGabrieleMusillo.2009.Onlinegraphplanarisationforsyn-chronousparsingofsemanticandsyntacticdependen-cies.InProceedingsofthe21stinternationaljontconferenceonArtificalintelligence,IJCAI’09,pages1562–1567.KristinaToutanova,AriaHaghighi,andChristopherD.Manning.2008.Aglobaljointmodelforsemanticrolelabeling.ComputationalLinguistics,34(2):161–191,June.DennisD.Wackerly,WilliamMendenhall,andRichardL.Scheaffer,2007.MathematicalStatis-ticswithApplications,chapter15:Nonparametricstatistics.DuxburyPress.NianwenXueandMarthaPalmer.2004.Calibratingfeaturesforsemanticrolelabeling.InDekangLinandDekaiWu,editors,ProceedingsofEMNLP2004,pages88–94,Barcelona,Spain,July.AlexanderS.Yeh.2000.Moreaccuratetestsforthesta-tisticalsignificanceofresultdifferences.InProceed-ingsofthe18thconferenceonComputationallinguis-tics,pages947–953.Be˜natZapirain,EnekoAgirre,Llu´ısM`arquez,andMihaiSurdeanu.2013.Selectionalpreferencesforsemanticroleclassification.ComputationalLinguistics,39(3).
Download pdf