Transactions of the Association for Computational Linguistics, vol. 5, pp. 441–454, 2017. Action Editor: Marco Kuhlmann.
Submission batch: 4/2017; Published 11/2017.
2017 Association for Computational Linguistics. Distributed under a CC-BY 4.0 license.
c
(cid:13)
ParsingwithTraces:AnO(n4)AlgorithmandaStructuralRepresentationJonathanK.KummerfeldandDanKleinComputerScienceDivisionUniversityofCalifornia,BerkeleyBerkeley,CA94720,USA{jkk,klein}@cs.berkeley.eduAbstractGeneraltreebankanalysesaregraphstruc-tured,butparsersaretypicallyrestrictedtotreestructuresforefficiencyandmodelingrea-sons.Weproposeanewrepresentationandalgorithmforaclassofgraphstructuresthatisflexibleenoughtocoveralmostalltreebankstructures,whilestilladmittingefficientlearn-ingandinference.Inparticular,weconsiderdirected,acyclic,one-endpoint-crossinggraphstructures,whichcovermostlong-distancedislocation,sharedargumentation,andsimilartree-violatinglinguisticphenomena.Wede-scribehowtoconvertphrasestructureparses,includingtraces,toournewrepresentationinareversiblemanner.Ourdynamicprogramuniquelydecomposesstructures,issoundandcomplete,andcovers97.3%ofthePennEn-glishTreebank.Wealsoimplementaproof-of-conceptparserthatrecoversarangeofnullelementsandtracetypes.1IntroductionManysyntacticrepresentationsusegraphsand/ordiscontinuousstructures,suchastracesinGovern-mentandBindingtheoryandf-structureinLexi-calFunctionalGrammar(Chomsky1981;KaplanandBresnan1982).SentencesinthePennTree-bank(PTB,Marcusetal.1993)haveacoreprojec-tivetreestructureandtraceedgesthatrepresentcon-trolstructures,wh-movementandmore.However,mostparsersandthestandardevaluationmetricig-noretheseedgesandallnullelements.Byleavingoutpartsofthestructure,theyfailtoprovidekeyrelationstodownstreamtaskssuchasquestionan-swering.Whiletherehasbeenworkoncapturingsomepartsofthisextrastructure,ithasgenerallyei-therbeenthroughpost-processingontrees(Johnson2002;Jijkoun2003;Campbell2004;LevyandMan-ning2004;Gabbardetal.2006)orhasonlycapturedalimitedsetofphenomenaviagrammaraugmenta-tion(Collins1997;DienesandDubey2003;Schmid2006;Caietal.2011).Weproposeanewgeneral-purposeparsingalgo-rithmthatcanefficientlysearchoverawiderangeofsyntacticphenomena.Ouralgorithmextendsanon-projectivetreeparsingalgorithm(Pitleretal.2013;Pitler2014)tographstructures,withimprove-mentstoavoidderivationalambiguitywhilemain-taininganO(n4)runtime.Ouralgorithmalsoin-cludesanoptionalextensiontoensureparsescontainadirectedprojectivetreeofnon-traceedges.Ouralgorithmcannotapplydirectlytocon-stituencyparses–itrequireslexicalizedstructuressimilartodependencyparses.Weextendandim-provepreviousworkonlexicalizedconstituentrep-resentations(Shenetal.2007;Carrerasetal.2008;HayashiandNagata2016)tohandletraces.Inthisform,tracescancreateproblematicstructuressuchasdirectedcycles,butweshowhowcarefulchoiceofheadrulescanminimizesuchissues.Weimplementaproof-of-conceptparser,scor-ing88.1ontreesinsection23and70.6ontraces.Together,ourrepresentationandalgorithmcover97.3%ofsentences,farabovethecoverageofpro-jectivetreeparsers(43.9%).2BackgroundThisworkbuildsontwoareas:non-projectivetreeparsing,andparsingwithnullelements.Non-projectivityisimportantinsyntaxforrep-
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
0
7
2
1
5
6
7
5
3
3
/
/
t
l
a
c
_
a
_
0
0
0
7
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
442
resentingmanystructures,butinferenceoverthespaceofallnon-projectivegraphsisintractable.For-tunately,inpracticealmostallparsesarecoveredbywell-definedsubsetsofthisspace.Fordepen-dencyparsing,recentworkhasdefinedalgorithmsforinferencewithinvarioussubspaces(G´omez-Rodr´ıguezandNivre2010;Pitleretal.2013).Webuilduponthesealgorithmsandadaptthemtocon-stituencyparsing.Forconstituencyparsing,arangeofformalismshavebeendevelopedthataremildly-contextsensitive,suchasCCG(Steedman2000),LFG(KaplanandBresnan1982),andLTAG(JoshiandSchabes1997).Concurrentlywiththiswork,Caoetal.(2017)alsoproposedagraphversionofPitleretal.(2013)’sOne-EndpointCrossing(1-EC)algorithm.How-ever,Cao’salgorithmdoesnotconsiderthedirec-tionofedges1andsoitcouldproducecycles,orgraphswithmultiplerootnodes.Theiralgorithmalsohasspuriousambiguity,withmultiplederiva-tionsofthesameparsestructurepermitted.OneadvantageoftheiralgorithmisthatbyintroducinganewitemtypeitcanhandlesomecasesoftheLocked-Chainwedefinebelow(specifically,whenNiseven),thoughinpractisetheyalsorestricttheiralgorithmtoignoresuchcases.Theyalsoshowthattheclassofgraphstheygeneratecorrespondstothe1-ECpagenumber-2space,apropertythatappliestothisworkaswell2.ParsingwithNullElementsinthePTBhastakentwogeneralapproaches.ThefirstbroadlyeffectivesystemwasJohnson(2002),whichpost-processedtheoutputofaparser,insertingextraelements.Thiswaseffectiveforsometypesofstructure,suchasnullcomplementizers,buthaddifficultywithlongdistancedependencies.Theothercommonapproachhasbeentothreadatracethroughthetreestruc-tureonthenon-terminalsymbols.Collins(1997)’sthirdmodelusedthisapproachtorecoverwh-traces,whileCaietal.(2011)usedittorecovernullpro-nouns,andothershaveuseditforarangeofmove-menttypes(DienesandDubey2003;Schmid2006).Theseapproacheshavethedisadvantagethateach1Toproducedirectededges,theirparsertreatsthedirectionaspartoftheedgelabel.2Thisisatopologicalspacewithtwohalf-planessharingaboundary.Alledgesaredrawnononeofthetwohalf-planesandeachhalf-planecontainsnocrossings.additionaltracedramaticallyexpandsthegrammar.OurrepresentationissimilartoLTAG-Spinal(Shenetal.2007)buthastheadvantagethatitcanbeconvertedbackintothePTBrepresentation.HayashiandNagata(2016)alsoincorporatednullelementsintoaspinalstructurebutdidnotincludearepresentationofco-indexation.Inrelatedwork,dependencyparsershavebeenusedtoassistincon-stituencyparsing,withvaryingdegreesofrepresen-tationdesign,butonlyfortrees(Hall,Nivre,andNilsson2007;HallandNivre2008;Fern´andez-Gonz´alezandMartins2015;Kongetal.2015).KatoandMatsubara(2016)describedanewap-proach,modifyingatransition-basedparsertore-covernullelementsandtraces,withstrongresults,butusingheuristicstodeterminetracereferents.3AlgorithmOuralgorithmisadynamicprogram,similaratahighleveltoCKY(Kasami1966;Younger1967;Cocke1969).Thestatesofourdynamicprogram(items)representpartialparses.UsuallyinCKY,itemsaredefinedascoveringthenwordsinasen-tence,startingandendingatthespacesbetweenwords.WefollowEisner(1996),definingitemsascoveringthen−1spacesinasentence,startingandendingonwords,asshowninFigure1.Thismeansthatweprocesseachword’sleftandrightdepen-dentsseparately,thencombinethetwohalves.Weusethreetypesofitems:(1)asingleedge,linkingtwowords,(2)acontinuousspan,goingfromonewordtoanother,representingalledgeslinkingpairsofwordswithinthespan,(3)aspan(asdefinedin2)plusanadditionalwordoutsidethespan,enablingtheinclusionofedgesbetweenthatwordandwordsinthespan.WithintheCKYframework,thekeytodefiningouralgorithmisasetofrulesthatspecifywhichitemsareallowedtocombine.Fromabottom-upperspective,aparseisbuiltinaseriesofsteps,whichcomeinthreetypes:(1)addinganedgetoanitem,(2)combiningtwoitemsthathavenon-overlappingadjacentspanstoproduceanewitemwithalargerspan,(3)combiningthreeitems,similarlyto(2).Example:Tobuildintuitionforthealgorithm,wewilldescribethederivationinFigure1.Note,itemsub-types(I,X,andN)aredefinedbelow,andin-
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
0
7
2
1
5
6
7
5
3
3
/
/
t
l
a
c
_
a
_
0
0
0
7
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
443
ROOTWelikerunning.I0,1I1,2I2,3I3,4(1)I1,2I2,3X3,4,2(2)X1,2,3(3)N0,2,3(4)N0,2,3(5)I0,4(6)Figure1:Anexamplederivationusingourgraphparsingdeductionrules.cludedhereforcompleteness.(1)Weinitializewithspansofwidthone,goingbe-tweenadjacentwords,e.g.betweenROOTandWe.∅7→I0,1(2)Edgescanbeintroducedinexactlytwoways,eitherbylinkingthetwoendsofaspan,e.g.like–running,orbylinkingoneendofaspanwithawordoutsidethespan,e.g.like–.(whichinthiscaseformsanewitemthathasaspanandanexternalword).I2,3∧like–running7→I2,3I3,4∧like–.7→X3,4,2(3)Weaddasecondedgetooneoftheitems.I1,2∧running–We7→X1,2,3(4)NowthatalltheedgestoWehavebeenadded,thetwoitemseithersideofitarecombinedtoformanitemthatcoversit.I0,1∧X1,2,37→N0,2,3(5)Weaddanedge,creatingacrossingbecauseWeisanargumentofawordtotherightoflike.N0,2,3∧ROOT–like7→N0,2,3(7)Weuseaternaryruletocombinethreeadjacentitems.Intheprocesswecreateanothercrossing.N0,2,3∧I2,3∧X3,4,27→I0,63.1AlgorithmdefinitionNotationVerticesarep,q,etc.Continuousrangesare[pq],[pq),(pq],or(pq),wherethebracketsindi-cateinclusion,[],orexclusion,(),ofeachendpoint.Aspan[pq]andvertexothatarepartofthesameitemare[pq.o].Twoverticesandanarrowindicateanedge,~pq.Twoverticeswithoutanarrowareanedgeineitherdirection,pq.Rangesand/orverticesconnectedbyadashdefineasetofedges,e.g.thesetofedgesbetweenoand(pq)iso–(pq)(insomeplaceswewillalsousethistorefertoanedgefromtheset,ratherthanthewholeset).Ifthereisapathfromptoq,qisreachablefromp.ItemTypesAsshowninFigure1,ouritemsstartandendonwords,fullycoveringthespacesinbe-tween.Earlierwedescribedthreeitemtypes:anedge,aspan,andaspanplusanexternalvertex.HerewedefinespansmorepreciselyasI,anddividethespanplusanexternalpointcaseintofivetypesdifferinginthetypeofedgecrossingtheycontain:pqI,IntervalAspanforwhichtherearenoedgessr:r∈(pq)ands/∈[pq].oX,ExtervalAnintervalandeitheroporoq,whereo/∈[pq].B,BothAspanandvertex[pq.o],forwhichtherearenoedgessr:r∈(pq)ands/∈[pq]∪o.Edgeso–[pq]maybecrossedbypq,p–(pq)orq–(pq),andatleastonecrossingofthesecondandthirdtypesoccurs.Edgeso–(pq)maynotbecrossedby(pq)–(pq)edges.L,LeftSameasB,buto–(pq)edgesmayonlycrossp–(pq]edges.R,RightSymmetricwithL.N,NeitherAnintervalandavertex[pq.o],withatleastoneo–(pq)edge,whichcanbecrossedbypq,butnoother[pq]–[pq]edges.ItemsarefurtherspecifiedasdescribedinAlg.1.Mostimportantly,foreachpairofo,p,andqinanitem,therulesspecifywhetheroneisaparentoftheother,andiftheyaredirectlylinkedbyanedge.ForanitemHwithspan[ij],definecovered(H)as(ij),anddefinevisible(H)as{i,j}.Whenanexternalvertexxispresent,itisinvisible(H).Calltheunionofmultiplesuchsetscovered(F,G,H),andvisible(F,G,H).DeductionRulesTomakethedeductionrulesmanageable,weusetemplatestodefinesomecon-straintsexplicitly,andthenusecodetogeneratetherules.Duringrulegeneration,weautomaticallyap-plyadditionalconstraintstopreventrulesthatwouldleaveawordinthemiddleofaspanwithoutaparentorthatwouldformacycle(provenpossiblebelow).Algorithm1presentstheexplicitconstraints.Onceexpanded,thesegiverulesthatspecifyallpropertiesforeachitem(generaltype,externalvertexposition
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
0
7
2
1
5
6
7
5
3
3
/
/
t
l
a
c
_
a
_
0
0
0
7
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
444
Algorithm1DynamicprogramforLock-Free,One-EndpointCrossing,Directed,Acyclicgraphparsing.AddingEdges:Consideraspan[lr]andvertexx/∈[lr].EdgesbetweenlandrcanbeaddedtoitemsI,N,L,R,andB(makingˆLandˆNinthosecases).EdgesbetweenlandxcanbeaddedtoitemsI(forminganX),R,andN.EdgesbetweenrandxcanbeaddedtoitemsI(forminganX),L,andN.Thel–redgecannotbeaddedafteranotheredge,andNitemscannotgetbothl–xandr–xedges.CombiningItems:Intherulesbelowthefollowingnotationisused:ForthisexplanationitemsareT[lrcrlclr]andT[lrxcrlcxlclrcxrclxcrx].Tisthetypeofitem.Multiplelettersindicateanyofthosetypesareallowed.Forthenextthreetypesofnotation,ifanitemdoesnothaveamark,eitheroptionisvalid.˙TandT:indicatethenumberofedgesbetweentheexternalvertexandthespan:oneormorethanonerespectively.·TandT·indicatethepositionoftheexternalvertexrelativetotheitem’sspan(leftorrightrespectively).ˆTindicatesforNandLthat∀p∈(ij)∃rs:i≤r
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
0
7
2
1
5
6
7
5
3
3
/
/
t
l
a
c
_
a
_
0
0
0
7
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
445
OurproofisverysimilarinstyleandstructuretoPitleretal.(2013).Thegeneralapproachistoconsiderthesetofstructuresanitemcouldrepre-sent,anddividethemintocasesbasedonpropertiesoftheinternalstructure.Wethenshowhoweachcasecanbedecomposedintoitems,takingcaretoensureallthepropertiesthatdefinedthecasearesatisfied.Uniquenessfollowsfromhavingnoam-biguityinhowagivenstructurecouldbedecom-posed.Completenessandsoundnessfollowfromthefactthatourrulesapplyequallywellineitherdirec-tion,andsoourtop-downdecompositionimpliesabottom-upformation.Togiveintuitionfortheproof,weshowthederivationofonerulebelow.Thecom-pleteproofcanbefoundinKummerfeld(2016).Wedonotincludeithereduetolackofspace.WedoprovidethecompletesetofruletemplatesinAlgorithm1,andintheproofofLemma2weshowthatthecaseinwhichanitemcannotbede-composedoccursifandonlyifthegraphcontainsaLocked-Chain.Toempiricallycheckourrulegener-ationcode,wecheckedthatourparseruniquelyde-composesall1-ECparsesinthePTBandisunabletodecomposetherest.Notethatbyusingsubsetsofourrules,wecanrestrictthespaceofstructureswegenerate,givingparsingalgorithmsforprojectiveDAGs,projectivetrees(Eisner1996),or1-ECtrees(Pitleretal.2013).Versionsofthesespaceswithundirectededgescouldalsobeeasilyhandledwiththesameapproach.pqstDerivationofrule(4)inAlgorithm1:Thisruleap-pliestointervalswiththesub-structureshown,andwithnoparentinthisitemforp.Theyhaveatleastonep–(pq)edge(otherwiserule1applies).Thelongestp–(pq)edge,ps,iscrossed(otherwiserule2applies).LetCbethesetof(ps)–(sq)edges(note:thesecrossps).EitheralloftheedgesinChaveacommonendpointt∈(sq),orif|C|=1lettbetheendpointin(sq)(otherwiserule6or7applies).LetDbethesetofs–(tq)edges.|D|>0(otherwiserule3or5applies).Wewillbreakthisintothreeitems.First,(st)–(tq]edgeswouldviolatethe1-ECpropertyand(st)–[ps)edgesdonotexistbyconstruction.Therefore,themiddleitemisanInterval[st],theleftitemis[ps.t],andtherightitemis[tq.s](since|C|>0and|D|>0).Theleftitemcanbeeither0123N−3N−2N−1N……Figure2:VisualizationofLocked-Chainstructures.Note,theuseof0toNdoesnotimplythismustspantheentiresentence,thesenumbersarejustforconvenienceinthedefinition.anNorR,butnotanLorBbecausethatwouldviolatethe1-ECpropertyfortheCedges.TherightitemcanbeanX,L,orN,butnotanRorBbecausethatwouldviolatethe1-ECpropertyfortheDedges.Wewillrequireedgepstobepresentinthefirstitem,andnotallowpt.Toavoidaspuriousambiguity,wealsopreventthefirstorthirditemsfromhavingst(whichcouldotherwiseoccurinanyofthethreeitems).Nowwehavebrokendowntheoriginalitemintovalidsub-items,andwehaveensuredthatthosesub-itemscontainallofthestructureusedtodefinethecaseinauniqueway.NowwewillfurthercharacterizethenatureoftheLock-Freerestrictiontothespaceofgraphs.Lemma1.NoedgeinaLocked-Chainina1-ECgraphiscrossedbyedgesthatarenotpartofit.Proof.First,notethat:Pt((0,N−1))=N,Pt((1,N))=0,and{Pt((i,i+2))=i+1∀i∈[0,N−2]}Calltheset{(i,i+2)∀i∈[0,N−2]},thechain.ConsideranedgeethatcrossesanedgefinaLocked-Chain.Leteinbetheendofethatisbe-tweenthetwoendsoff,andeoutbetheotherend.Oneofe’sendpointsisatPt(f),andPt(e)isanendpointoff.Therearethreecases:(i)f=(1,N).Here,eout=Pt(f)=0,andein∈(1,N).Forallverticesv∈(1,N)thereisanedgeginthechainsuchthatvisbetweentheendpointsofg.Therefore,ewillcrosssuchanedgeg.Tosatisfythe1-ECproperty,gmustshareanendpointwithf,whichmeansgiseither(1,3)or(N−2,N).Inthefirstcase,the1-ECpropertyforcese=(0,2),andintheseconde=(0,N−1),bothofwhicharepartoftheLocked-Chain.(ii)f=(0,N−1),symmetricalwith(i).(iii)f=(i,i+2),forsomei∈[0,N−2].Here,ein=Pt(f)=i+1.Wecanassumeedoesnotcross(0,N−1)or(1,N),asthosecasesarecoveredby(i).Asin(i),emustcrossanotheredgeinthechain,andthatedgemustshareanendpointwithf.
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
0
7
2
1
5
6
7
5
3
3
/
/
t
l
a
c
_
a
_
0
0
0
7
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
446
Thisforcesetobeeither(i−1,i+1)or(i+1,i+3)(excludingoneorbothiftheycross(0,N−1)or(1,N)),whicharebothintheLocked-Chain.Ourrulesdefineauniquewaytodecomposeal-mostanyitemintoasetofotheritems.Theexcep-tionisB,whichinsomecasescannotbedividedintotwoitems(i.e.hasnovalidbinarydivision).Lemma2.AB[ij.x]hasnovalidbinarydivisionifandonlyifthegraphhasaLocked-Chain.Proof.ConsiderthekandlthatgivethelongestikandljedgesinaBwithnovalidbinarydivision(atleastoneedgeofeachtypemustexistbydefinition).Novertexin(ik)or(jl)isavalidsplitpoint,astheywouldallrequireoneoftheitemstohavetwoexternalvertices.Now,considerp∈[kj].Ifthereisnoedgel1r1,wherei≤l1