Transacciones de la Asociación de Lingüística Computacional, volumen. 5, páginas. 441–454, 2017. Editor de acciones: Marco Kuhlmann.

in tacl on

Transacciones de la Asociación de Lingüística Computacional, volumen. 5, páginas. 441–454, 2017. Editor de acciones: Marco Kuhlmann.
Lote de envío: 4/2017; Publicado 11/2017.

2017 Asociación de Lingüística Computacional. Distribuido bajo CC-BY 4.0 licencia.

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-

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
0
7
2
1
5
6
7
5
3
3

/

/
t

yo

a
C
_
a
_
0
0
0
7
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
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(Sala,Nivre,andNilsson2007;HallandNivre2008;Fern´andez-Gonz´alezandMartins2015;Kongetal.2015).KatoandMatsubara(2016)describedanewap-proach,modifyingatransition-basedparsertore-covernullelementsandtraces,withstrongresults,butusingheuristicstodeterminetracereferents.3AlgorithmOuralgorithmisadynamicprogram,similaratahighleveltoCKY(Kasami1966;Younger1967;Cocke1969).Thestatesofourdynamicprogram(elementos)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).Ejemplo:Tobuildintuitionforthealgorithm,wewilldescribethederivationinFigure1.Note,itemsub-types(I,X,andN)aredefinedbelow,andin-

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
0
7
2
1
5
6
7
5
3
3

/

/
t

yo

a
C
_
a
_
0
0
0
7
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
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],o(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)borde,whichcanbecrossedbypq,butnoother[pq]–[pq]edges.ItemsarefurtherspecifiedasdescribedinAlg.1.Mostimportantly,foreachpairofo,pag,andqinanitem,therulesspecifywhetheroneisaparentoftheother,andiftheyaredirectlylinkedbyanedge.ForanitemHwithspan[ij],definecovered(h)como(ij),anddefinevisible(h)como{i,j}.Whenanexternalvertexxispresent,itisinvisible(h).Calltheunionofmultiplesuchsetscovered(F,GRAMO,h),andvisible(F,GRAMO,h).DeductionRulesTomakethedeductionrulesmanageable,weusetemplatestodefinesomecon-straintsexplicitly,andthenusecodetogeneratetherules.Duringrulegeneration,weautomaticallyap-plyadditionalconstraintstopreventrulesthatwouldleaveawordinthemiddleofaspanwithoutaparentorthatwouldformacycle(provenpossiblebelow).Algorithm1presentstheexplicitconstraints.Onceexpanded,thesegiverulesthatspecifyallpropertiesforeachitem(generaltype,externalvertexposition

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
0
7
2
1
5
6
7
5
3
3

/

/
t

yo

a
C
_
a
_
0
0
0
7
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

444

Algorithm1DynamicprogramforLock-Free,One-EndpointCrossing,Directed,Acyclicgraphparsing.AddingEdges:Consideraspan[lr]andvertexx/∈[lr].EdgesbetweenlandrcanbeaddedtoitemsI,norte,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≤rN>3,withedges{(0,N−1),(1,norte)}∪{(i,i+2)∀i∈[0,N−2]}.Definition3.AgraphisLock-FreeifitdoesnotcontainedgesthatformaLocked-Chain.Notethatinpractice,mostparsestructuressatisfy1-EC,andtheLocked-Chainstructuredoesnotoc-curinthePTBwhenusingourheadrules.Theorem1.ForthespaceofLock-FreeOne-EndpointCrossinggraphs,thealgorithmissound,completeandgivesuniquedecompositions.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
0
7
2
1
5
6
7
5
3
3

/

/
t

yo

a
C
_
a
_
0
0
0
7
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
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)borde(otherwiserule1applies).Thelongestp–(pq)borde,ps,iscrossed(otherwiserule2applies).LetCbethesetof(ps)–(sq)bordes(nota: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](desde|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:punto((0,N−1))=N,punto((1,norte))=0,and{punto((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(mi)isanendpointoff.Therearethreecases:(i)f=(1,norte).Aquí,eout=Pt(F)=0,andein∈(1,norte).Forallverticesv∈(1,norte)thereisanedgeginthechainsuchthatvisbetweentheendpointsofg.Therefore,ewillcrosssuchanedgeg.Tosatisfythe1-ECproperty,gmustshareanendpointwithf,whichmeansgiseither(1,3)o(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].Aquí,ein=Pt(F)=i+1.Wecanassumeedoesnotcross(0,N−1)o(1,norte),asthosecasesarecoveredby(i).Asin(i),emustcrossanotheredgeinthechain,andthatedgemustshareanendpointwithf.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

a
C
_
a
_
0
0
0
7
2
1
5
6
7
5
3
3

/

/
t

yo

a
C
_
a
_
0
0
0
7
2
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

446

Thisforcesetobeeither(i−1,i+1)o(i+1,i+3)(excludingoneorbothiftheycross(0,N−1)o(1,norte)),whicharebothintheLocked-Chain.Ourrulesdefineauniquewaytodecomposeal-mostanyitemintoasetofotheritems.Theexcep-tionisB,whichinsomecasescannotbedividedintotwoitems(i.e.hasnovalidbinarydivision).Lemma2.AB[ij.x]hasnovalidbinarydivisionifandonlyifthegraphhasaLocked-Chain.Proof.ConsiderthekandlthatgivethelongestikandljedgesinaBwithnovalidbinarydivision(atleastoneedgeofeachtypemustexistbydefinition).Novertexin(I)o(jl)isavalidsplitpoint,astheywouldallrequireoneoftheitemstohavetwoexternalvertices.Now,considerp∈[kj].Ifthereisnoedgel1r1,wherei≤l1j>N),y(i<0∧j≥N).Itemsofthelastthreetypeswouldbedividedbyourrulesintosmalleritems,oneofwhichcontainsthewholeLocked-Chain.ThefirsttwoareBsofthetypediscussedabove.NowwewillprovethatourcodetogeneraterulesfromthetemplatescanguaranteeaDAGisformed.Lemma3.ForanyitemH,∀v∈covered(H)∃u∈visible(H):visreachablefromu.Proof.Thisistrueforinitialitemsbecausecovered(H)=∅.Toapplyinduction,consideraddingedgesandcombingitems.Thelemmaclearlyremainstruewhenaddinganedge.Considercom-biningitemsE,F,GtoformH[ij.x],andas-sumethelemmaistrueforE,F,andG(thebi-narycaseissimilar).Sinceallverticesarereach-ablefromvisible(E,F,G),weonlyneedtoensurethat∀v∈visible(E,F,G)∃u∈visible(H):visreachablefromu.Theconnectivitybetweenallpairs{(u,v)|u∈visible(H),v∈visible(E,F,G)}canbeinferredfromtheitemdefinitions,andsothisrequirementcanbeenforcedinrulegeneration.Lemma4.Thefinalitemisadirectedacyclicgraph.Proof.First,consideracyclicity.Initialitemsdonotcontainanyedgesandsocannotcontainacycle.Forinduction,therearetwocases:(i)AddinganEdge~pqtoanitemH:AssumethatHdoesnotcontainanycycles.~pqwillcreateacycleifandonlyifpisreachablefromq.Byconstruction,pandq∈visible(H),andsotheitemdefinitioncontainswhetherpisreachablefromq.(ii)CombiningItems:Assumethatinisolation,noneoftheitemsbeingcombinedcontaincycles.Therefore,acycleinthecombineditemmustbecomposedofpathsinmultipleitems.Apathinoneitemcanonlycontinueinanotheritembypassingthroughavisiblevertex.Therefore,acyclewouldhavetobeformedbyasetofpathsbetweenvisiblevertices.Buttheconnectivityofeverypairofvisibleverticesisspecifiedintheitemdefinitions.Inbothcases,rulesthatcreateacyclecanbeex-cludedduringrulegeneration.Byinduction,theitemsconstructedbyouralgo-rithmdonotcontaincycles.TogetherwithLemma3andthefinalitemdefinition,thismeansthefinalstructureisanacyclicgraphwithallverticesreach-ablefromvertexn.Next,wewillshowtwopropertiesthatgiveintu-itionforthealgorithm.Specifically,wewillprovewhichrulesaddedgesthatarecrossedinthefinalderivation.Lemma5.AnedgeijaddedtoI[ij]isnotcrossed.Proof.First,wewillshowthreepropertiesofanypairofitemsinaderivation(using[ij.x]and[kl.y]). 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 447 (1)Itisimpossibleforeitherix/∈(kl).As-sumex∈(kl)fortwoitemswithoutnestedspans.Noneoftherulescombinesuchapairofitems,orallowonetobeextendedsothattheotherisnestedwithinit.However,allitemsareeventuallycom-binedtocompletethederivation.Bycontradiction,x/∈(kl).Juntos,thesemeanthatgivenanintervalHwithspan[ij],andanotheritemG,either∀v∈visible(GRAMO),v∈[ij]or∀v∈visible(GRAMO),v/∈(ij).Sinceedgesareonlycreatedbetweenvisiblever-tices,noedgecancrossedgeij.Lemma6.AlledgesasidefromthoseconsideredinLemma5arecrossed.Proof.First,consideranedgeijaddedtoanitem[ij.x]oftypeB,l,R,orN.Thisedgeiscrossedbyallx–(ij)bordes,andintheseitems|x–(ij)|≥1bydefinition.Note,bythesameargumentasLemma5,theedgeisnotcrossedlaterinthederivation.Second,consideraddinge∈{xi,xj},toH,anitemwith[ij]o[ij.x],forminganitemG[ij.x].Nota,edoesnotcrossanyedgesinH.LetE(F[kl.y])bethesetofy–[kl]edgesinsomeitemF.Notethate∈E(GRAMO).Wewillshowhowthissetofedgesisaffectedbytherulesandwhatthatim-pliesfore.ConsidereachinputitemA[kl.y]ineachrule,withoutputitemC.EveryitemAfallsintooneoffourcategories:(1)∀f∈E(A),fiscrossedbyanedgeinanotheroftherule’sinputitems,(2)mi(A)⊆E(C),(3)A∧kl7→CandtherearenokyorlyedgesinA,(4)AcontainsedgeklandtherearenokyorlyedgesinA.Cases2-4arestraightforwardtoidentify.Foranexampleofthefirstcase,considertherightmostiteminrule4.Therelevantedgesarek–(lj](byconstruc-tion,klisnotpresent).SincetheleftmostitemiseitheranRorN,|l–(I)|≥1.SinceiAlgorithmExtensions3.4.1EdgeLabelsandWordLabelsEdgelabelscanbeaddedbycalculatingeitherthesumormaxoveredgetypeswhenaddingeachedge.Wordlabels(e.g.,POSTags)mustbeaddedtothestate,specifyingalabelforeachvisibleword(pag,qando).Thisstateexpansionisnecessarytoensureagreementwhencombiningitems.3.4.2EnsuringaStructuralTreeisPresentOuralgorithmconstrainsthespaceofgraphstruc-tures,butwealsowanttoensurethatourparsecon-tainsaprojectivetreeofnon-traceedges.Toensureeverywordgetsoneandonlyonestruc-turalparent,weaddbooleanstothestate,indicatingwhetherp,qandohavestructuralparents.Whenaddingedges,astructuraledgecannotbeaddedifawordalreadyhasastructuralparent.Whencombin-ingitems,nowordcanreceivemorethanonestruc-turalparent,andwordsthatwillendupinthemiddleofthespanmusthaveexactlyone.Together,theseconstraintsensurewehaveatree.Toensurethetreeisprojective,weneedtopreventstructuraledgesfromcrossing.Crossingedgesareintroducedintwoways,andinbothwecanavoidstructuraledgescrossingbytrackingwhethertherearestructuralo–[pq]edges.Suchedgesarepresentifaruleaddsastructuraloporoqedge,orifarulecombinesanitemwithstructuralo–[pq]edgesandowillstillbeexternalintheitemformedbytherule.Foraddingedges,everytimeweaddapqedgeintheN,l,RandBitemswecreateacrossingwithallo–(pq)edges.Wedonotcreateacrossingwithoqorop,butourorderingofedgecreationmeansthesearenotpresentwhenweaddapqedge,sotrackingstructuralo–[pq]edgesgivesustheinformationweneedtopreventtwostructuraledgescrossing.Forcombiningitems,inLemma6weshowedthatduringcombinations,o–[pq]edgesineachpairofitemswillcross.Asaresult,knowingwhetheranyo–[pq]edgeisstructuralissufficienttodeterminewhethertwostructuraledgeswillcross.3.5ComplexityConsiderasentencewithntokens,andletEandSbethenumberofedgetypesandwordlabelsinourgrammarrespectively.Welike*1running.NPSBJVPSNPSBJVPSROOTNPSBJWeSVPlikeS(NPSBJ*)VPrunning-.Figure3:Parserepresentationsforgraphstructures,PTB(arriba)andours(abajo).Parseswithoutwordoredgelabels:Ruleshaveuptofourpositions,leadingtocomplexityofO(n4).Nota,thereisalsoanimportantconstant–onceourtemplatesareexpanded,thereare49,292rules.Withedgelabels:Whenusingafirst-ordermodel,edgelabelsonlyimpacttherulesforedgecreation,leadingtoacomplexityofO(n4+En2).Withwordlabels:Sinceweneedtotrackwordlabelsinthestate,weneedtoadjusteverynbyafactorofS,leadingtoO(S4n4+ES2n2).4ParseRepresentationOuralgorithmreliesontheassumptionthatwecanprocessthedependentstotheleftandrightofawordindependentlyandthencombinethetwohalves.Thismeansweneedlexicalizedstructures,whichthePTBdoesnotprovide.Wedefineanewrepre-sentationinwhicheachnon-terminalsymbolisas-sociatedwithaspecificword(thehead).Unlikede-pendencyparsing,weretainalltheinformationre-quiredtoreconstructtheconstituencyparse.OurapproachisrelatedtoCarrerasetal.(2008)andHayashiandNagata(2016),withthreekeydif-ferences:(1)weencodenon-terminalsexplicitly,ratherthanimplicitlythroughadjunctionoperations,whichcancauseambiguity,(2)weaddrepresen-tationsofnullelementsandco-indexation,(3)wemodifyheadrulestoavoidproblematicstructures.Figure3showsacomparisonofthePTBrepre-sentationandours.Weaddlexicalization,assigningeachnon-terminaltoaword.Theonlyotherchangesarevisualnotation,withnon-terminalsmovedtobedirectlyabovethewordstomoreclearlyshowthedistinctionbetweenspinesandedges.Spines:Eachwordisassignedaspine,shownim- yo D oh w norte oh a d mi d F r oh metro h t t pag : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 0 7 2 1 5 6 7 5 3 3 / / t yo a C _ a _ 0 0 0 7 2 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 449 cakeswebaked*T*1NP0NPSBJVPWHNP1SNPSBARNPSBAR(WHNP0)SVP(NP*T*)baked(a)NulltonullcookedsouptodayandcurryyesterdayNP1NPTMP,2NP=1NPTMP,=2VPVPVPVPVPNPNPTMP-VPNPNPTMPcookedsouptodayandcurryyesterdayVPVPNPNPTMP-VPNPNPTMPcookedsouptodayandcurryyesterday(b)ParallelConstructionsFigure4:Examplesofsyntacticphenomena.Onlyrele-vantedgesandspinesareshown.mediatelyabovetheword.Aspineistheorderedsetofnon-terminalsthatthewordistheheadof,e.g.S-VPforlike.Ifasymboloccursmorethanonceinaspine,weuseindicestodistinguishinstances.Edges:Anedgeisalinkbetweentwowords,withalabelindicatingthesymbolsitlinksinthechildandparentspines.Inourfigures,edgelabelsareindicatedbywhereedgesstartandend.NullElements:Weincludeeachnullelementinthespineofitsparent,unlikeHayashiandNa-gata(2016),whoeffectivelytreatednullelementsaswords,assigningthemindependentspines.Wealsoconsideredencodingnullelementsentirelyonedgesbutfoundthisledtopoorerperformance.Co-indexation:Thetreebankrepresentsmove-mentwithindexpairsonnullelementsandnon-terminals,e.g.*1andNP1inFigure3.Werepresentco-indexationwithedges,oneperreference,goingfromthenullelementtothenon-terminal.Therearethreespecialcasesofco-indexation:(1)Itispossiblefortraceedgestohavethesamestartandendpointsasanon-traceedge.Werestrictthiscasetoallowatmostonetraceedge.Thisde-creasesedgecoverageinthetrainingsetby0.006%.(2)Insomecasesthereferencenon-terminalonlyspansanullelement,e.g.theWHNPinFigure4a.Fortheseweuseareversededgetoavoidcreatingacycle.Figure4ashowsasituationwherethetraceedgelinkstwopositionsinthesamespine,whichweassignwiththespineduringparsing.(3)Forparallelconstructionsthetreebankco-indexesargumentsthatfulfillthesameroles(Fig.4b).Thesearedistinctfromthepreviouscasesbecauseneitherindexisonanullelement.Wecon-sideredtwooptions:addedgesfromtherepetitionwhich*T*1proposed...NPVPWHNP1SSBARSBARWHNPwhichS(NP*T*)VPproposed(a)CyclePagewasnamed*1CEOtodayNPNPSADJPVPNP1VPSROOTNPSVPVPS(NP*)NPADJPPagewasnamedCEOtoday(b)NotOne-EndpointCrossingFigure5:Examplesofproblematicgraphstructuredsyn-tacticphenomenabeforeourheadrulechanges.tothereferent(middle),oraddedgesfromtherep-etitiontotheparentofthefirstoccurrence(abajo).Optiontwoproducesfewernon-1-ECstructuresandexplicitlyrepresentsallpredicates,butonlyimplic-itlycapturestheoriginalstructure.4.1AvoidingAdjunctionAmbiguityPriorworkonparsingwithspineshasusedr-adjunctiontoaddadditionalnon-terminalstospines.Thisintroducesambiguity,becauseedgesmodifyingthesamespinefromdifferentsidesmaynothaveauniqueorderofapplication.Weresolvethisissuebyusingmorearticulatedspineswiththecompletesetofnon-terminals.Wefoundthat0.045%ofspineinstancesinthedevelopmentsetarenotobservedintraining,thoughin70%ofthosecasesanequivalentspinesansnullelementsisobservedintraining.4.2HeadRulesToconstructthespines,welexicalizewithheadrulesthatconsiderthetypeofeachnon-terminalanditschildren.Differentheadsoftenrepresentmoresyntacticorsemanticaspectsofthephrase.Fortrees,allheadrulesgeneratevalidstructures.Forgraphs,headrulesinfluencethecreationoftwoproblematicstructures:Cycles:Thesearisewhentheheadchosenforaphraseisalsoanargumentofanotherwordinthephrase.Figure5ashowsacyclebetweenwhichandproposed.WeresolvethisbychangingtheheadofanSBARtobeanSratherthanaWh-nounphrase.One-EndpointCrossingViolations:Figure5bshowsanexample,withthetracefromCEOtoPagecrossingtwoedgeswithnoendpointsincommon.WeresolvethiscasebychangingtheheadforVPstobeachildVPratherthananauxiliary. yo D oh w norte oh a d mi d F r oh metro h t t pag : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 0 7 2 1 5 6 7 5 3 3 / / t yo a C _ a _ 0 0 0 7 2 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 450 5ResultsAlgorithmCoverage:InTable1weshowtheimpactofdesigndecisionsforourrepresentation.Thepercentagesindicatehowmanysentencesinthetrainingsetarecompletelyrecoverablebyouralgo-rithm.Eachrowshowstheoutcomeofanadditiontothepreviousrow,startingfromnotracesatall,goingtoourrepresentationwiththeheadrulesofCarrerasetal.(2008),thenchangingtheheadrules,reversingnull-nulledges,andchangingthetargetofedgesinparallelconstructions.Thelargestgaincomesfromchangingtheheadrules,whichisunsurprisingsinceCarrerasetal.(2008)’srulesweredesignedfortrees(anysetofrulesformvalidstructuresfortrees).ProblematicStructures:Ofthesentenceswedonotcover,54%containacycle,45%containa1-ECviolation,and1%containboth.Tounderstandtheseproblematicsentences,wemanuallyinspectedarandomsampleoftwentyparsesthatcontainedacycleandtwentyparseswitha1-ECviolation(thesefortyare6%ofallproblematicparses,enoughtoidentifythekeyremainingchallenges).Forthecycles,elevencasesrelatedtosentencescontainingvariationsofNPsaidinterposedbetweentwopartsofasinglequote.Acyclewaspresentbecausethetopnodeoftheparsewasco-indexedwithanullargumentofsaidwhilesaidwasanar-gumentoftheheadwordofthequote.Theremain-ingcaseswereallinstancesofpseudo-attachment,whichthetreebankusestoshowthatnon-adjacentconstituentsarerelated(Biesetal.1995).ThesecasesweresplitbetweenuseofExpletive(5)andInterpretConstituentHere(4)traces.Itwasmoredifficulttodeterminetrendsforcaseswheretheparsestructurehasa1-ECviolation.Thesamethreecases,Expletive,InterpretConstituentHere,andNPsaidaccountedforhalfoftheissues.5.1ImplementationWeimplementedaparserwithafirst-ordermodelusingouralgorithmandrepresentation.Codefortheparser,forconversiontoandfromourrepre-sentation,andforourmetricsisavailable3.Ourparserusesalineardiscriminativemodel,withfea-turesbasedonMcDonaldetal.(2005).Wetrain3https://github.com/jkkummerfeld/1ec-graph-parserCoverage(%)RepresentationSentencesEdgesProjectivetrees,nonulls26.5996.27Projectivetrees,withnulls43.8596.27Projectivegraphs50.6096.67One-ECgraphs71.8498.31+Headrulechanges92.3599.23+Nullreversal97.0299.45+Parallelconstructionshift97.3199.49Table1:Trainingsetcoveragefordifferentrepresenta-tions.One-ECgraphsusesourrepresentation,butwiththeheadrulesfromCarrerasetal.(2008).Fortheedgeresults,weonlyexcludeedgesnecessarytomakeeachparserepresentable(e.g.excludingonlyoneedgeinacy-cleandcountingtherest).withanonlineprimalsubgradientapproach(Ratliffetal.2007)asdescribedbyKummerfeld,Berg-Kirkpatrick,etal.(2015),withparallellock-freesparseupdates.LossFunction:WeuseaweightedHammingdis-tanceforloss-augmenteddecoding,asitcanbeef-ficientlydecomposedwithinourdynamicprogram.Calculatingthelossforincorrectspinesandextraedgesiseasy.Formissingedges,weaddwhenadeductionrulejoinstwospansthatcoveranendoftheedge,sinceifitdoesnotexistinoneofthoseitemsitisnotgoingtobecreatedinfuture.Toavoiddoublecountingwesubtractwhencombiningtwohalvesthatcontainthetwoendsofagoldedge4.Inside–OutsideCalculations:Assigningscorestoedgesissimple,astheyareintroducedinasingleiteminthederivation.Spinesmustbeintroducedinmultipleitems(izquierda,bien,andexternalpositions)andmustbeassignedascoreineverycasetoavoidtiesinbeams.Weaddthescoreeverytimethespineisintroducedandthensubtractwhentwoitemswithaspineincommonarecombined.Algorithmrulepruning:Many1-ECstructuresarenotseeninourdata.Wekeeponlytherulesusedingoldtrainingparses,reducingthesetof49,292fromthegeneralalgorithmto627(includingrulesforbothaddingarcsandcombiningitems).AlmosteverytemplateinAlgorithm1generatessomeun-necessaryrules,andnoitemsoftypeBareneeded.4Onealternativeistocounthalfofitoneachend,removingtheneedforsubtractionlater.Anotheristoadditduringthecombinationstep. yo D oh w norte oh a d mi d F r oh metro h t t pag : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 0 7 2 1 5 6 7 5 3 3 / / t yo a C _ a _ 0 0 0 7 2 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 451 Theremainingrulesstillhavehighcoverageofthedevelopmentset,missingonly15rules,eachappliedonce(outof78,692ruleapplications).Bypruninginthisway,weareconsideringtheintersectionof1-ECgraphsandthetruespaceofstructuresusedinlanguage.ChartPruning:Toimprovespeedweusebeamsandcubepruning(Chiang2007),discardingitemsbasedontheirViterbiinsidescore.Wedivideeachbeamintosub-beamsbasedonaspectsofthestate.Thisensuresdiversityandenablesconsiderationofonlycompatibleitemsduringbinaryandternarycompositions.CoarsetoFinePruning:Ratherthanparsingimmediatelywiththefullmodelweuseseveralpasseswithprogressivelyricherstructure(Good-man1997):(1)Projectiveparsingwithouttracesorspines,andsimultaneouslyatraceclassifier,(2)Non-projectiveparsingwithoutspines,andsimul-taneouslyaspineclassifier,(3)Fullstructurepars-ing.Eachpassprunesusingparsemax-marginalsandclassifierscores,tunedonthedevelopmentset.Thethirdpassalsoprunesspinesthatarenotconsis-tentwithanyunprunededgefromthesecondpass.ForthespineclassifierweuseabidirectionalLSTMtagger,implementedinDyNet(Neubigetal.2017).Speed:Parsingtookanaverageof8.6secondspersentenceforgraphparsingand0.5secondswhentheparserisrestrictedtotrees5.Ouralgorithmisalsoamenabletomethodssuchassemi-supervisedandadaptivesupertagging,whichcanimprovethespeedofaparseraftertraining(Kummerfeld,Roes-ner,etal.2010;LewisandSteedman2014).TreeAccuracy:Onthestandardtree-metric,wescore88.1.Usingthesamenon-goldPOStagsasinput,Carrerasetal.(2008)score90.9,probablyduetotheirsecond-orderfeaturesandheadrulestunedforperformance6.Shiftingtousetheirheadrules,wescore88.9.Second-orderfeaturescouldbeaddedtoourmodelthroughtheuseofforestrerank-ing,animprovementthatwouldbeorthogonaltothispaper’scontributions.Wecanalsoevaluateonspinesandedges.SincetheirsystemproducesregularPTBtrees,wecon-5UsingasinglecoreofanAmazonEC2m4.2xlargein-stance(2.4GHzXeonCPUand32GbofRAM).6Previousworkhasshownthatthechoiceofheadcansig-nificantlyimpactaccuracy(Schwartzetal.2012).SystemPRFNullElementsOnlyJohnson(2002)857479HayashiandNagata(2016)90.381.785.8KatoandMatsubara(2016)88.582.185.2Thiswork89.581.685.4NullElementsandCo-indexationJohnson(2002)736368KatoandMatsubara(2016)81.274.777.8Thiswork74.367.370.6Table2:Accuracyonsection23usingJohnson’smetric.vertitsoutputtoourrepresentationandcompareitsresultswithoursystemusingtheirheadrules.Weseeslightlyloweraccuracyforoursystemonbothspines(94.0vs.94.3)andedges(90.4vs.91.1).TraceAccuracy:Table2showsresultsusingJohnson(2002)’stracemetric.Ourparseriscompet-itivewithpreviousworkthathashighly-engineeredmodels:Johnson’ssystemhascomplexnon-localfeaturesontreefragments,andsimilarlyKatoandMatsubara(k&M2016)considercompleteitemsinthestackoftheirtransition-basedparser.Onco-indexationourresultsfallbetweenJohnsonandK&M.Convertingtoourrepresentation,ourparserhashigherprecisionthanK&Montraceedges(84.1vs.78.1)butlowerrecall(59.5vs.71.3).Onemod-elingchallengeweobservedisclassimbalance:ofthemanyplacesatracecouldbeadded,onlyasmallnumberarecorrect,andsoourmodeltendstobeconservative(asshownbytheP/Rtradeoff).6ConclusionWeproposearepresentationandalgorithmthatcover97.3%ofgraphstructuresinthePTB.Oural-gorithmisO(n4),uniquelydecomposesparses,andenforcesthepropertythatparsesarecomposedofacoretreewithadditionaltracesandnullelements.Aproofofconceptparsershowsthatouralgorithmcanbeusedtoparseandrecovertraces.AcknowledgmentsWethankGregDurrettforadviceonparserim-plementationanddebugging,andtheactioneditorandanonymousreviewersfortheirhelpfulfeedback.ThisresearchwaspartiallysupportedbyaGeneralSirJohnMonashFellowshipandtheOfficeofNaval l D o w n o a d e d f r o m h t t p : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 0 7 2 1 5 6 7 5 3 3 / / t yo a C _ a _ 0 0 0 7 2 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 452 ResearchunderMURIGrantNo.N000140911081.ReferencesAnnBies,MarkFerguson,KarenKatz,RobertMac-Intyre,VictoriaTredinnick,GraceKim,MaryAnnMarcinkiewicz,andBrittaSchasberger(1995).Brack-etingGuidelinesforTreebank2StylePennTreebankProject.Tech.rep.ShuCai,DavidChiang,andYoavGoldberg(2011).Language-IndependentParsingwithEmptyElements.InProceedingsofthe49thAnnualMeetingoftheAs-sociationforComputationalLinguistics:HumanLan-guageTechnologies(ACL-HLT).https://www.aclweb.org/anthology/P/P11/P11-2037.pdf.RichardCampbell(2004).UsingLinguisticPrinciplestoRecoverEmptyCategories.InProceedingsofthe42ndAnnualMeetingonAssociationforComputa-tionalLinguistics(LCA).https://www.aclweb.org/anthology/P/P04/P04-1082.pdf.JunjieCao,ShengHuang,WeiweiSun,andXiaojunWan(2017).Parsingto1-Endpoint-Crossing,Pagenumber-2Graphs.InProceedingsofthe55thAnnualMeet-ingoftheAssociationforComputationalLinguistics(LCA).XavierCarreras,MichaelCollins,andTerryKoo(2008).TAG,DynamicProgramming,andthePerceptronforEfficient,Feature-richParsing.InProceedingsoftheTwelfthConferenceonComputationalNaturalLanguageLearning(CONLL).https://www.aclweb.org/anthology/W/W08/W08-2102.pdf.DavidChiang(2007).HierarchicalPhrase-BasedTrans-lation.ComputationalLinguistics33.2,pp.201–228.https://www.aclweb.org/anthology/J/J07/J07-2003.pdf.NoamChomsky(1981).Lecturesongovernmentandbinding:ThePisalectures.JohnCocke(1969).ProgrammingLanguagesandTheirCompilers:PreliminaryNotes.Tech.rep.CourantIn-stituteofMathematicalSciences,NewYorkUniver-sity.MichaelCollins(1997).ThreeGenerative,LexicalisedModelsforStatisticalParsing.InProceedingsofthe35thAnnualMeetingoftheAssociationforComputa-tionalLinguistics(LCA).https://www.aclweb.org/anthology/P/P97/P97-1003.pdf.P´etrDienesandAmitDubey(2003).DeepSyntacticPro-cessingbyCombiningShallowMethods.InProceed-ingsofthe41stAnnualMeetingoftheAssociationforComputationalLinguistics(LCA).https://www.aclweb.org/anthology/P/P03/P03-1055.pdf.JasonEisner(1996).ThreeNewProbabilisticModelsforDependencyParsing:AnExploration.InProceed-ingsofthe16thInternationalConferenceonCom-putationalLinguistics(CoLing).http://www.aclweb.org/anthology/C/C96/C96-1058.pdf.DanielFern´andez-Gonz´alezandAndr´eF.T.Martins(2015).ParsingasReduction.InProceedingsofthe53rdAnnualMeetingoftheAssociationforCompu-tationalLinguisticsandthe7thInternationalJointConferenceonNaturalLanguageProcessing(ACL-IJCNLP).https://www.aclweb.org/anthology/P/P15/P15-1147.pdf.RyanGabbard,MitchellMarcus,andSethKulick(2006).FullyParsingthePennTreebank.InProceedingsoftheHumanLanguageTechnologyConferenceoftheNorthAmericanChapteroftheACL(NAACL-HLT).https://www.aclweb.org/anthology/N/N06/N06-1024.pdf.CarlosG´omez-Rodr´ıguezandJoakimNivre(2010).ATransition-basedParserfor2-PlanarDependencyStructures.InProceedingsofthe48thAnnualMeet-ingoftheAssociationforComputationalLinguis-tics(LCA).https://www.aclweb.org/anthology/P/P10/P10-1151.pdf.JoshuaGoodman(1997).GlobalThresholdingandMultiple-PassParsing.InProcessingsoftheSecondConferenceonEmpiricalMethodsinNaturalLan-guageProcessing(EMNLP).https://www.aclweb.org/anthology/W/W97/W97-0302.pdf.JohanHallandJoakimNivre(2008).ADependency-DrivenParserforGermanDependencyandCon-stituencyRepresentations.InProceedingsoftheWork-shoponParsingGerman.https://www.aclweb.org/anthology/W/W08/W08-1007.pdf.JohanHall,JoakimNivre,andJensNilsson(2007).AHybridConstituency-DependencyParserforSwedish.InProceedingsofthe16thNordicConferenceofCom-putationalLinguistics(NODALIDA).https://www.aclweb.org/anthology/W/W07/W07-2444.pdf.KatsuhikoHayashiandMasaakiNagata(2016).EmptyElementRecoverybySpinalParserOperations.InProceedingsofthe54thAnnualMeetingoftheAsso-ciationforComputationalLinguistics(LCA,Volume2:ShortPapers).https://www.aclweb.org/anthology/P/P16/P16-2016.pdf.ValentinJijkoun(2003).FindingNon-localDependen-cies:BeyondPatternMatching.InTheCompanion l D o w n o a d e d f r o m h t t p : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 0 7 2 1 5 6 7 5 3 3 / / t yo a C _ a _ 0 0 0 7 2 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 453 VolumetotheProceedingsof41stAnnualMeet-ingoftheAssociationforComputationalLinguistics(ACL-SRW).https://www.aclweb.org/anthology/P/P03/P03-2006.pdf.MarkJohnson(2002).ASimplePattern-matchingAl-gorithmforRecoveringEmptyNodesandTheirAn-tecedents.InProceedingsofthe40thAnnualMeet-ingonAssociationforComputationalLinguistics.https://www.aclweb.org/anthology/P/P02/P02-1018.pdf.AravindK.JoshiandYvesSchabes(1997).Hand-bookofFormalLanguages:Volume3BeyondWords.In.SpringerBerlinHeidelberg.Chap.Tree-AdjoiningGrammars,pp.69–123.R.M.KaplanandJ.Bresnan(1982).Lexical-FunctionalGrammar:AFormalSystemforGrammaticalRepre-sentation.InTheMentalRepresentationofGrammati-calRelations.MITPress,pp.173–281.TadaoKasami(1966).AnEfficientRecognitionandSyntax-AnalysisAlgorithmforContext-FreeLan-guages.Tech.rep.UniversityofIllinoisatUrbana-Champaign.YoshihideKatoandShigekiMatsubara(2016).Transition-BasedLeft-CornerParsingforIdentifyingPTB-StyleNonlocalDependencies.InProceedingsofthe54thAnnualMeetingoftheAssociationforCom-putationalLinguistics(LCA,Volume1:LongPapers).http://www.aclweb.org/anthology/P/P16/P16-1088.pdf.LingpengKong,AlexanderM.Rush,andNoahA.Smith(2015).TransformingDependenciesintoPhraseStruc-tures.InProceedingsofthe2015ConferenceoftheNorthAmericanChapteroftheAssociationforCom-putationalLinguistics:HumanLanguageTechnolo-gies(ACL-HLT).https://www.aclweb.org/anthology/N/N15/N15-1080.pdf.JonathanK.Kummerfeld(2016).AlgorithmsforIdenti-fyingSyntacticErrorsandParsingwithGraphStruc-turedOutput.PhDthesis.EECSDepartment,Univer-sityofCalifornia,Berkeley.http://www2.eecs.berkeley.edu/Pubs/TechRpts/2016/EECS-2016-138.html.JonathanK.Kummerfeld,TaylorBerg-Kirkpatrick,andDanKlein(2015).AnEmpiricalAnalysisofOpti-mizationforMax-MarginNLP.InProceedingsofthe2015ConferenceonEmpiricalMethodsinNaturalLanguageProcessing(EMNLP).https://www.aclweb.org/anthology/D/D15/D15-1032.pdf.JonathanK.Kummerfeld,JessicaRoesner,TimDaw-born,JamesHaggerty,JamesR.Curran,andStephenClark(2010).FasterParsingbySupertaggerAdapta-tion.InProceedingsofthe48thAnnualMeetingoftheAssociationforComputationalLinguistics(LCA).http://www.aclweb.org/anthology/P/P10/P10-1036.pdf.RogerLevyandChristopherD.Manning(2004).DeepDependenciesfromContext-freeStatisticalParsers:CorrectingtheSurfaceDependencyApproximation.InProceedingsofthe42ndMeetingoftheAssoci-ationforComputationalLinguistics(ACL’04),MainVolume.https://www.aclweb.org/anthology/P/P04/P04-1042.pdf.MikeLewisandMarkSteedman(2014).ImprovedCCGParsingwithSemi-supervisedSupertagging.Transac-tionsoftheAssociationforComputationalLinguis-tics2,pp.327–338.ISSN:2307-387X.https://transacl.org/ojs/index.php/tacl/article/view/388.MitchellP.Marcus,BeatriceSantorini,andMaryAnnMarcinkiewicz(1993).BuildingaLargeAnnotatedCorpusofEnglish:ThePennTreebank.Computa-tionalLinguistics19.2,pp.313–330.https://www.aclweb.org/anthology/J/J93/J93-2004.pdf.RyanMcDonald,KobyCrammer,andFernandoPereira(2005).OnlineLarge-MarginTrainingofDependencyParsers.InProceedingsofthe43rdAnnualMeetingoftheAssociationforComputationalLinguistics(LCA).https://www.aclweb.org/anthology/P/P05/P05-1012.pdf.GrahamNeubig,ChrisDyer,YoavGoldberg,AustinMatthews,WaleedAmmar,AntoniosAnastasopoulos,MiguelBallesteros,DavidChiang,DanielClothiaux,TrevorCohn,KevinDuh,ManaalFaruqui,CynthiaGan,DanGarrette,YangfengJi,LingpengKong,Ad-higunaKuncoro,GauravKumar,ChaitanyaMalaviya,PaulMichel,YusukeOda,MatthewRichardson,NaomiSaphra,SwabhaSwayamdipta,andPengchengYin(2017).DyNet:TheDynamicNeuralNetworkToolkit.arXivpreprintarXiv:1701.03980.https://arxiv.org/abs/1701.03980.EmilyPitler(2014).ACrossing-SensitiveThird-OrderFactorizationforDependencyParsing.TransactionsoftheAssociationforComputationalLinguistics2,pp.41–54.https://transacl.org/ojs/index.php/tacl/article/view/193.EmilyPitler,SampathKannan,andMitchellMarcus(2013).FindingOptimal1-Endpoint-CrossingTrees.TransactionsoftheAssociationforComputationalLinguistics1,pp.13–24.https://www.aclweb.org/anthology/Q/Q13/Q13-1002.pdf.NathanRatliff,J.Andrew(Dibujó)Bagnell,andMartinZinkevich(2007).(En línea)SubgradientMethodsfor l D o w n o a d e d f r o m h t t p : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 0 7 2 1 5 6 7 5 3 3 / / t yo a C _ a _ 0 0 0 7 2 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 454 StructuredPrediction.InProceedingsoftheEleventhInternationalConferenceonArtificialIntelligenceandStatistics(AIStats).HelmutSchmid(2006).TracePredictionandRecoverywithUnlexicalizedPCFGsandSlashFeatures.InPro-ceedingsofthe21stInternationalConferenceonCom-putationalLinguisticsand44thAnnualMeetingoftheAssociationforComputationalLinguistics(LCA).https://www.aclweb.org/anthology/P/P06/P06-1023.pdf.RoySchwartz,OmriAbend,andAriRappoport(2012).Learnability-BasedSyntacticAnnotationDesign.InProceedingsofCOLING2012.http://www.aclweb.org/anthology/C/C12/C12-1147.pdf.LibinShen,LucasChampollion,andAravindK.Joshi(2007).LTAG-spinalandtheTreebank.LanguageRe-sourcesandEvaluation42.1,pp.1–19.MarkSteedman(2000).TheSyntacticProcess.MITPress.DanielH.Younger(1967).RecognitionandParsingofContext-FreeLanguagesinTimen3.InformationandControl10.2,pp.189–208.
Descargar PDF