计算语言学协会会刊, 1 (2013) 13–24. 动作编辑器: Giorgio Satta.

Submitted 11/2012; 已发表 3/2013. C
(西德:13)

2013 计算语言学协会.

FindingOptimal1-Endpoint-CrossingTreesEmilyPitler,SampathKannan,MitchellMarcusComputerandInformationScienceUniversityofPennsylvaniaPhiladelphia,PA19104epitler,kannan,mitch@seas.upenn.eduAbstractDependencyparsingalgorithmscapableofproducingthetypesofcrossingdependenciesseeninnaturallanguagesentenceshavetra-ditionallybeenordersofmagnitudeslowerthanalgorithmsforprojectivetrees.For95.8-99.8%ofdependencyparsesinvariousnat-urallanguagetreebanks,wheneveranedgeiscrossed,theedgesthatcrossitallhaveacommonvertex.Theoptimaldependencytreethatsatisﬁesthis1-Endpoint-Crossingprop-ertycanbefoundwithanO(n4)parsingal-gorithmthatrecursivelycombinesforestsoverintervalswithoneexteriorpoint.1-Endpoint-CrossingtreesalsohavenaturalconnectionstolinguisticsandanotherclassofgraphsthathasbeenstudiedinNLP.1IntroductionDependencyparsingisoneofthefundamentalprob-lemsinnaturallanguageprocessingtoday,withap-plicationssuchasmachinetranslation(DingandPalmer,2005),informationextraction(CulottaandSorensen,2004),andquestionanswering(Cuietal.,2005).Mosthigh-accuracygraph-baseddepen-dencyparsers(KooandCollins,2010;RushandPetrov,2012;ZhangandMcDonald,2012)ﬁndthehighest-scoringprojectivetrees(inwhichnoedgescross),despitethefactthatalargeproportionofnat-urallanguagesentencesarenon-projective.Projec-tivetreescanbefoundinO(n3)时间(艾斯纳,2000),butcoveronly63.6%ofsentencesinsomenaturallanguagetreebanks(Table1).TheclassofdirectedspanningtreescoversalltreebanktreesandcanbeparsedinO(n2)withedge-basedfeatures(McDonaldetal.,2005),butitisNP-hardtoﬁndthemaximumscoringsuchtreewithgrandparentorsiblingfeatures(McDonaldandPereira,2006;McDonaldandSatta,2007).Therearevariousexistingdeﬁnitionsofmildlynon-projectivetreeswithbetterempiricalcoveragethanprojectivetreesthatdonothavethehardnessofextensibilitythatspanningtreesdo.However,thesehavehadparsingalgorithmsthatareordersofmag-nitudeslowerthantheprojectivecaseortheedge-basedspanningtreecase.Forexample,well-nesteddependencytreeswithblockdegree2(Kuhlmann,2013)coveratleast95.4%ofnaturallanguagestruc-tures,buthaveaparsingtimeofO(n7)(Gómez-Rodríguezetal.,2011).Nopreviouslydeﬁnedclassoftreessimultane-ouslyhashighcoverageandlow-degreepolynomialalgorithmsforparsing,allowinggrandparentorsib-lingfeatures.Wepropose1-Endpoint-Crossingtrees,inwhichforanyedgethatiscrossed,allotheredgesthatcrossthatedgeshareanendpoint.Whilesimpletostate,thispropertycovers95.8%ormoreofde-pendencyparsesinnaturallanguagetreebanks(Ta-ble1).Theoptimal1-Endpoint-Crossingtreecanbefoundinfasterasymptotictimethananyprevi-ouslyproposedmildlynon-projectivedependencyparsingalgorithm.Weshowhowany1-Endpoint-Crossingtreecanbedecomposedintoisolatedsetsofintervalswithoneexteriorpoint(Section3).Thisisthekeyinsightthatallowsefﬁcientparsing;theO(n4)parsingalgorithmispresentedinSection4.1-Endpoint-Crossingtreesareasubclassof2-planargraphs(Section5.1),aclassthathasbeenstudied

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你

/
t

A
C
我
/

我

A
r
t
我
C
e
–
p
d

F
/

d
哦

我
/

1
0
1
1
6
2

/
t

我

A
C
_
A
_
0
0
2
0
6
1
5
6
6
6
3
9

/
t

我

A
C
_
A
_
0
0
2
0
6
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

inNLP.1-Endpoint-Crossingtreesalsohavesomelinguisticinterpretation(pairsofcrossserialverbsproduce1-Endpoint-Crossingtrees,Section5.2).2DeﬁnitionsofNon-ProjectivityDeﬁnition1.Edgeseandfcrossifeandfhavedistinctendpointsandexactlyoneoftheendpointsoffliesbetweentheendpointsofe.Deﬁnition2.Adependencytreeis1-Endpoint-Crossingifforanyedgee,alledgesthatcrosseshareanendpointp.Table1showsthepercentageofdependencyparsesintheCoNLL-Xtrainingsetsthatare1-Endpoint-Crossingtrees.Acrosssixlanguageswithvaryingamountsofnon-projectivity,95.8-99.8%ofdependencyparsesintreebanksare1-Endpoint-Crossingtrees.1Wenextreviewandcompareotherrelevantdef-initionsofnon-projectivityfrompriorwork:well-nestedwithblockdegree2,gap-minding,projective,and2-planar.Thedeﬁnitionsofblockdegreeandwell-nestednessaregivenbelow:Deﬁnition3.Foreachnodeuinthetree,ablockofthenodeis“alongestsegmentconsistingofdescen-dantsofu.”(Kuhlmann,2013).Theblock-degreeofuis“thenumberofdistinctblocksofu”.Theblockdegreeofatreeisthemaximumblockdegreeofanyofitsnodes.Thegapdegreeisthenumberofgapsbetweentheseblocks,andsobydeﬁnitionisonelessthantheblockdegree.(Kuhlmann,2013)Deﬁnition4.Twotrees“T1andT2interleaveifftherearenodesl1,r1∈T1andl2,r2∈T2suchthatl1l 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 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 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 15 ArabicCzechDanishDutchPortugueseSwedishParsing1-Endpoint-Crossing1457(99.8)71810(98.8)5144(99.1)12785(95.8)9007(99.3)10902(98.7)氧(n4)Well-nested,blockdegree21458(99.9)72321(99.5)5175(99.7)12896(96.6)8650(95.4)10955(99.2)氧(n7)Gap-Minding1394(95.5)70695(97.2)4985(96.1)12068(90.4)8481(93.5)10787(97.7)氧(n5)Projective1297(88.8)55872(76.8)4379(84.4)8484(63.6)7353(81.1)9963(90.2)氧(n3)Sentences146072703519013349907111042Table1:Over95%ofthedependencyparsetreesintheCoNLL-Xtrainingsetsare1-Endpoint-Crossingtrees.Coveragestatisticsandparsingtimesofpreviouslyproposedpropertiesareshownforcomparison.Deﬁnition8.Withina1-Endpoint-Crossingtree,这(crossing)pencil2ofanedgee(磷(e))isdeﬁnedasthesetofedges(sharinganendpoint)thatcrosse.The(crossingpencil)pointofanedgee(Pt(e))isdeﬁnedastheendpointthatalledgesinP(e)share.Wewilluseeuvtoindicateanedgeineitherdirec-tionbetweenuandv,i.e.,eitheru→voru←v.Beforedeﬁningtheparsingalgorithm,weﬁrstgivesomeintuitionbyanalogytoparsingforpro-jectivetrees.(ThisargumentmirrorsthatofEisner(2000,pps.38-39).)Projectivetreescanbeproducedusingdynamicprogrammingoverintervals.Inter-valsaresufﬁcientforprojectivetrees:consideranyedgeeuvinaprojectivetree.Theverticesin(你,v)mustonlyhaveedgestoverticesin[你,v].Iftherewereanedgebetweenavertexin(你,v)andavertexoutside[你,v],suchanedgewouldcrosseuv,whichwouldcontradicttheassumptionofprojectivity.Thuseveryedgeinaprojectivetreecreatesoneinteriorintervalisolatedfromtherestofthetree,allowingdynamicprogram-mingoverintervals.Wecananalyzethecaseof1-Endpoint-Crossingtreesinasimilarfashion:Deﬁnition9.Anisolatedinterval[我,j]hasnoedgesbetweentheverticesin(我,j)andtheverticesout-sideof[我,j].Anintervalandoneexteriorvertex[我,j]∪{X}iscalledanisolatedcrossingregionifthefollowingtwoconditionsaresatisﬁed:1.Therearenoedgesbetweenthevertices∈(我,j)andvertices/∈[我,j]∪{X}2.Noneoftheedgesbetweenxandvertices∈(我,j)arecrossedbyanyedgeswithbothend-points∈(我,j)2Thisnotationcomesfromananalogytogeometry:“Asetofdistinct,coplanar,concurrentlinesisapenciloflines”(Rin-genberg,1967,p.221);concurrentlinesallintersectatthesamesinglepoint.uvp(A)[你,v]∪{p}uvp(乙)[v,p]∪{你}upv(C)[你,p]∪{v}upv(d)[p,v]∪{你}Figure2:AnedgeeuvandPt(euv)=pformtwosetsofisolatedcrossingregions(Lemma1).2aand2bshowp/∈(你,v);2cand2dshowp∈(你,v).Lemma1.ConsideranyedgeeuvandPt(euv)=pina1-Endpoint-CrossingforestF.Letl,r,andmdenotetheleftmost,最右边的,andmiddlepointoutof{你,v,p},respectively.Thenthethreepointsu,v,andpdeﬁnetwoisolatedcrossingregions:(1)[我,米]∪{r},和(2)[米,r]∪{我}.Proof.Firstnotethatasp=Pt(euv),磷(euv)isnon-empty:theremustbeatleastoneedgebetweenvertices∈(你,v)andvertices/∈[你,v].piseither/∈[你,v](i.e.,p=l∨p=r)or∈(你,v)(i.e.,p=m):Case1:p=l∨p=r:Assumewithoutlossofgeneralitythatux/∈[你,v]∪{p}.Thensuchanedgewouldcrosseuvwithouthavinganendpointatp,whichcontradictsthe1-Endpoint-Crossingprop-ertyforeuv.Condition2:Assumethatforsomeepasuchthata∈(你,v),epawascrossedbyanedgeintheinteriorof(你,v).Theinterioredgewouldnotshareanend-pointwitheuv;sinceeuvalsocrossesepa,thiscon-tradictsthe1-Endpoint-Crossingpropertyforepa. 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 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 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 16 (乙)[v,p]∪{你}isanisolatedcrossingregion(Figure2b):Condition1:Assumetherewereanedgeeabwitha∈(v,p)andb/∈[v,p]∪{你}.bcannotbein(你,v)(byabove).因此,b/∈[你,p],whichimpliesthateabcrossestheedgesinP(euv);aseuvdoesnotshareavertexwitheab,thiscontra-dictsthe1-Endpoint-CrossingpropertyforalledgesinP(euv).Condition2:Assumethatforsomeeuasuchthata∈(v,p),euawascrossedbyanedgeintheinteriorof(v,p).euawouldalsobecrossedbyalltheedgesinP(euv);astheinterioredgewouldnotshareanendpointwithanyoftheedgesinP(euv),thiswouldcontradictthe1-Endpoint-Crossingpropertyforeua.Case2:p=m:(A)[你,p]∪{v}isanisolatedcrossingregion(Figure2c):Condition1:Assumetherewereanedgeeabwitha∈(你,p)andb/∈[你,p]∪{v}(b∈(p,v)∨b/∈[你,v]).Firstassumeb∈(p,v).TheneabcrossesalledgesinP(euv);aseabdoesnotshareanendpointwitheuv,thiscontradictsthe1-Endpoint-CrossingpropertyfortheedgesinP(euv).Nextassumeb/∈[你,v].Theneabcrosseseuv;sincea6=p∧b6=p,thisviolatesthe1-Endpoint-Crossingpropertyforeuv.Condition2:Assumethatforsomeevawitha∈(你,p),evawascrossedbyanedgeintheinteriorof(你,v).evaisalsocrossedbyalltheedgesinP(euv);astheinterioredgewillnotshareanendpointwiththeedgesinP(euv),thiscontradictsthe1-Endpoint-Crossingpropertyforeva.(乙)[p,v]∪{你}isanisolatedcrossingregion(Figure2d):Symmetrictotheabove.4ParsingAlgorithmTheoptimal1-Endpoint-Crossingtreecanbefoundusingadynamicprogrammingalgorithmthatex-ploitsthefactthatedgesandtheircrossingpointsdeﬁneintervalsandisolatedcrossingregions.Thissectionassumesanarc-factoredmodel,inwhichthescoreofatreeisdeﬁnedasthesumofthescoresofitsedges;scoringfunctionsforedgesaregenerallylearnedfromdata.(A)Onlyedgesinci-denttotheLeftpointoftheintervalmaycrosstheedgesfromtheexteriorpoint(乙)Onlyedgesin-cidenttotheRightpointoftheinter-valmaycrosstheedgesfromtheexte-riorpoint(C)两个都(LR)(d)NeitherFigure3:Isolatedcrossingregionsub-problems.Thedynamicprogramusesﬁvetypesofsub-problems:intervalsub-problemsforeachinterval[我,j],denotedInt[我,j],andfourtypesofisolatedcrossingregionsub-problemsforeachintervalandexteriorpoint[我,j]∪{X},whichdifferinwhetheredgesfromtheexteriorpointmaybecrossedbyedgeswithanendpointattheLeftpointoftheinter-val,theRightpoint,bothLR,orNeither(Figure3).L[我,j,X],forexample,referstoanisolatedcrossingregionovertheinterval[我,j]withanexteriorpointofx,inwhichedgesincidenttoi(theleftboundarypoint)cancrossedgesbetweenxand(我,j).Thesedistinctionsallowthe1-Endpoint-Crossingpropertytobegloballyenforced;crossingedgesinoneregionmayconstrainedgesinanother.Forex-ample,considerthatFigure2aallowsedgeswithanendpointatvtocrosstheedgesfromp,whileFigure2ballowsedgesfromuinto(v,p).Bothsimultane-ouslywouldcausea1-Endpoint-CrossingviolationfortheedgesinP(euv).Figures4and5showvalidcombinationsofthesub-problemsinFigure3.ThefulldynamicprogramisshowninAppendixA.Theﬁnalanswermustbeavaliddependencytree,whichrequireseachwordtohaveexactlyoneparentandprohibitscycles.Weusebooleans(双,bj,bx)foreachsub-problem,inwhichthebooleanissettotrueifandonlyifthesolutiontothesub-problemmustcontaintheincoming(parent)edgeforthecorre-spondingboundarypoint.WeusethesufﬁxAFromBforasub-problemtoenforcethataboundarypointAmustbedescendedfromboundarypointB(toavoidcycles).Wewilloccasionallymentiontheseissues, 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 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 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 17 (A)Ifl∈(k,j]:kilj(乙)Ifl∈(我,k):likj(我)Ifthedashededgeexists:Alltheedgesfromlinto(我,k)mustchoosekastheirPt.TheintervaldecomposesintoS[eik]+右[我,k,我]+Int[k,我]+L[我,j,k]:kilj(二)Ifnoedgeslikethedashededgeexist:Alledgesfromlinto(我,k)maychooseeitheriorkastheirPt.TheintervaldecomposesintoS[eik]+LR[我,k,我]+Int[k,我]+Int[我,j]:iklj(我)Ifdashededgeexists:Alltheedgesfromlinto(k,j]mustchooseiastheirPt.Theintervaldecom-posesintoS[eik]+Int[我,我]+L[我,k,我]+氮[k,j,我]:likj(二)Ifnoedgeslikethedashededgeexist:AlledgesfromlmaychoosekastheirPt.Theintervaldecom-posesintoS[eik]+右[我,我,k]+Int[我,k]+L[k,j,我]:likjFigure4:DecomposinganInt[我,j]sub-problem,withPt(eik)=lbutforsimplicityfocusthediscussiononthedecom-positionintocrossingregionsandthemaintenanceofthe1-Endpoint-Crossingproperty.Edgedirectiondoesnotaffectthesepointsoffocus,andsowewillrefersimplytoS[euv]tomeanthescoreofeithertheedgefromutovorvice-versa.Inthefollowingsubsections,weshowthattheop-timalparseforeachtypeofsub-problemcanbede-composedintosmallervalidsub-problems.Ifwetakethemaximumoverallthesepossiblecombina-tionsofsmallersolutions,wecanﬁndthemaximumscoringparseforthatsub-problem.Notethattheoveralltreeisavalidsub-problem(overtheinter-val[0,n]),sotheargumentwillalsoholdforﬁndingtheoptimaloveralltree.Eachindividualvertexandeachpairofadjacentvertices(withnoedges)triv-iallyformisolatedintervals(asthereisnointerior);thisformsthebasecaseofthedynamicprogram.TheoveralldynamicprogramtakesO(n4)时间:thereareO(n2)intervalsub-problems,eachofwhichneedstwofreesplitpointstoﬁndthemax-imum,andO(n3)regionsub-problems,eachofwhichisamaximizationoveronefreesplitpoint.4.1DecomposinganIntsub-problemConsideranisolatedintervalsub-problemInt[我,j].Therearethreecases:(1)therearenoedgesbetweeniandtherestoftheinterval,(2)thelongestedgein-cidenttoiisnotcrossed,(3)thelongestedgeinci-denttoiiscrossed.AnIntsub-problemcanbede-composedintosmallervalidsub-problemsineachofthesethreecases.FindingtheoptimalIntforestcanbedonebytakingthemaximumoverthesecases:Noedgesbetweeniand[i+1,j]:ThesamesetofedgesisalsoavalidInt[i+1,j]sub-problem.bimustbetruefortheInt[i+1,j]sub-problemtoensurei+1receivesaparent.Furthestedgefromiisnotcrossed:Ifthefurthestedgeistoj,theproblemcanbedecomposedintoS[eij]+Int[我,j],asthatedgehasnoeffectontheinterioroftheinterval.Clearly,thisisonlyappli-cableiftheboundarypointneededaparent(asin-dicatedbythebooleans)andthebooleanmustthenbeupdatedaccordingly.Ifthefurthestedgeistosomekin(我,j),theproblemisdecomposedintoS[eik]+Int[我,k]+Int[k,j].Furthestedgefromiiscrossed:Thisisthemost 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 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 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 18 interestingcase,whichusestwosplitpoints:theotherendpointoftheedge(k),andl=Pt(eik).Thedynamicprogramdependsontheorderofkandl.l/∈(我,k)(Figure4a):ByLemma1,[我,k]∪{我}和[k,我]∪{我}formisolatedregions.(我,j]istheremain-deroftheinterval,andtheonlyvertexfrom[我,我)thatcanhaveedgesinto(我,j]isk:(我,k)和(k,我)arepartofisolatedregions,andiisruledoutbecausekwasi’sfurthestneighbor.Ifatleastoneedgefromkinto(我,j](thedashedlineinFigure4a)存在,thedecompositionisasinFigure4a,Casei;否则,itisasinFigure4a,Caseii.InCasei,eikandtheedge(s)betweenkand(我,j]forcealloftheedgesbetweenland(我,k)tohavekastheirPt.Thus,theregion[我,k]∪{我}mustbeasub-problemoftypeR(Figure3b),astheseedgesfromlcanonlybecrossedbyedgeswithanendpointatk(therightendpointof[我,k]).Alloftheedgesbetweenkand(我,j]havelastheirPt,astheyarecrossedbyalltheedgesinP(eik),andsothesub-problemcorrespondingtotheregion[我,j]∪{k}isoftypeL(Figure3a).InCaseii,eachoftheedgesinP(eik)maychooseeitheriorkastheirPt,sothesub-problem[我,k]∪{我}isoftypeLR(Figure3c).Notethatl=jisaspecialcaseofCaseiiinwhichtherightmostintervalInt[我,j]isempty.l∈(我,k)(Figure4b):[我,我]∪{k}和[我,k]∪{我}formisolatedcrossingregionsbyLemma1.Therecannotbothbeedgesbetweeniand(我,k)andbe-tweenkand(我,我),asthiswouldviolate1-Endpoint-CrossingfortheedgesinP(eik).Ifthereareanyedgesbetweeniand(我,k)(i.e.,CaseiinFigure4b),thenalloftheedgesinP(eik)mustchooseiastheirPt,andsotheseedgescannotbecrossedatallintheregion[k,j]∪{我},andtherecannotbeanyedgesfromkinto(我,我).Iftherearenosuchedges(Caseiiin4b),thenkmustbeavalidPtforalledgesinP(eik),andsotherecanbothbeedgesfromkinto(我,我)和[k,j]∪{我}maybeoftypeL(allowingcrossingswithanendpointatk).4.2DecomposinganLRsub-problemAnLRsub-problemisoveranisolatedcrossingre-gion[我,j]∪{X},suchthatedgesfromxinto(我,j)maybecrossedbyedgeswithanendpointateitheriorj.Thissub-problemisonlydeﬁnedwhenneitherinorjgettheirparentfromthissub-problem.Fromatop-downperspective,thiscaseisonlyusedwhentherewillbeanedgebetweeniandj(asinoneofthesub-problemsinFigure4a,Caseii).Ifnoneoftheedgesfromxarecrossedbyanyedgeswithanendpointati,thiscanbeconsideredanRproblem.Similarly,ifnonearecrossedbyanyedgeswithanendpointatj,thismaybeconsideredanLsub-problem.Theonlycasewhichneedsdis-cussioniswhenbothedgeswithanendpointatiandalsoatjcrossedgesfromx;seeFigure3cforaschematic.Inthatscenario,theremustexistasplitpointsuchthat:(1)totheleftofthepoint,alledgescrossingx-edgeshaveanendpointati,andtotherightofthepoint,allsuchedgeshaveanendpointatj,和(2)noedgesintheregioncrossthesplitpoint.Letribei’srightmostchildin(我,j);letljbej’sleftmostchildin(我,j).Everyedgefromxinto(我,ri)iscrossedbyeiri;everyedgebetweenxand(lj,j)iscrossedbyeljj.eiricannotcrosseljj,asthatwouldeitherviolate1-Endpoint-Crossing(be-causeofthex-interioredges)orcreateacycle(ifbothchildrenarealsoconnectedbyanedgetox).riandljalsocannotbeequal:asneitherinorjmaybeassignedaparent,theymustbothbeinthedirec-tionofthechild,andthechildcannothavemultipleparents.Thus,riistotheleftoflj.Anysplitpointbetweenriandljclearlysatis-ﬁes(1).Thereisatleastonepointwithin[ri,lj]thatsatisﬁes(2)aslongasthereisnotachainofcrossingedgesfromeiritoeljj.Theproofisomittedforspacereasons,butsuchachaincanberuledoutusingacountingargumentsimilartothatintheproofinSection5.1.Thedecompositionis:L[我,k,X]+右[k,j,X]forsomek∈(我,j).4.3DecomposinganNsub-problemConsiderthemaximumscoringforestoftypeNover[我,j]∪{X}(Figure3d;noedgesfromxarecrossedinthissub-problem).Iftherearenoedgesfromx,thenitisalsoavalidInt[我,j]sub-problem.Ifthereareedgesbetweenxandtheendpointsiorj,thentheforestwiththatedgeremovedisstillavalidNsub-problem(withtheancestorandparentbook-keepingupdated).否则,ifthereareedgesbe-tweenxand(我,j),choosetheneighborofxclosesttoj(callitk).Sincetheedgeexkisnotcrossed,therearenoedgesfrom[我,k)进入(k,j];sincekwastheneighborofxclosesttoj,therearenoedgesfromxinto(k,j].因此,theregiondecomposesinto 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 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 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 19 xkji(我)Ifdashededgeexists:Alltheedgesfromiinto(k,j]mustchoosexastheirPt.Theintervaldecom-posesintoS[exk]+L[我,k,X]+氮[k,j,我]:xkji(二)Ifnoedgeslikethedashededgeexist:Edgesfromiinto(k,j]maychoosekastheirPt.Thein-tervaldecomposesintoS[exk]+Int[我,k]+L[k,j,我]:xkjiFigure5:AnLsub-problemover[我,j]∪{X},kistheneighborofxfurthestfromiintheinterval.S[eik]+Int[k,j]+氮[我,k,X].Asanaside,ifbxwastrue(xneededaparentfromthissub-problem),andkwasachildofx,thenx’sparentmustcomefromthe[我,k]∪{X}sub-problem.However,itcannotbeadescendantofk,asthatwouldcauseacycle.Thusinthiscase,wecallthesub-problemaN_XFromIproblem,toin-dicatethatxneedsaparent,iandkdonot,andxmustbedescendedfromi,notk.4.4DecomposinganLorRsub-problemAnLsub-problemover[我,j]∪{X}requiresthatanyedgesinthisregionthatcrossanedgewithanend-pointatxhaveanendpointati(theleftendpoint).Iftherearenoedgesbetweenxand[我,j]inanLsub-problem,thenitisalsoavalidIntsub-problemover[我,j].Ifthereareedgesbetweenxandiorj,thenthesub-problemcanbedecomposedintothatedgeplustherestoftheforestwiththatedgeremoved.Theinterestingcaseiswhenthereareedgesbe-tweenxandtheinterior(Figure5).Letkbetheneighborofxwithin(我,j)thatisfurthestfromi.Asalledgesthatcrossexkwillhaveanendpointati,therearenoedgesbetween(我,k)和(k,j].Com-binedwiththefactthatkwastheneighborofxclos-esttoj,wehavethat[我,k]∪{X}mustformaniso-abcdefFigure6:2-planarbutnot1-Endpoint-Crossinglatedcrossingregion,asmust[k,j]∪{我}.Ifthereareadditionaledgesbetweenxandthein-terior(Caseiin5),alloftheedgesfromiinto(k,j]crossboththeedgeexkandtheotheredgesfromxinto(我,k).ThePtforalltheseedgesmustthere-forebex,andasxisnotintheregion[k,j]∪{我},thoseedgescannotbecrossedatallinthatregion(IE。,[k,j]∪{我}mustbeoftypeN).Iftherearenoadditionaledgesfromxinto(我,k)(CaseiiinFig-ure5),thenalloftheedgesfromiinto(k,j)mustchooseeitherxorkastheirPt.Astherewillbenomoreedgesfromx,choosingkastheirPtallowsstrictlymoretrees,andso[k,j]∪{我}canbeoftypeL(allowingedgesfromitobecrossedinthatregionbyedgeswithanendpointatk).AnRsub-problemisidentical,withkinsteadchosentobetheneighborofxfurthestfromj.5Connections5.1GraphTheory:All1-Endpoint-CrossingTreesare2-PlanarThe2-planarcharacterizationofdependencystruc-turesinGómez-RodríguezandNivre(2010)exactlycorrespondto2-pagebookembeddingsingraphthe-ory:anembeddingoftheverticesinagraphontoaline(byanalogy,alongthespineofabook),andtheedgesofthegraphontooneof2(moregener-ally,k)half-planes(pagesofthebook)suchthatnoedgesonthesamepagecross(BernhartandKainen,1979).Theproblemofﬁndinganembeddingthatminimizesthenumberofpagesrequiredisanaturalformulationofmanyproblemsarisingindisparateareasofcomputerscience,forexample,sortingase-quenceusingtheminimumnumberofstacks(EvenandItai,1971),orconstructingfault-tolerantlayoutsinVLSIdesign(Chungetal.,1987).Inthissectionweprove1-Endpoint-Crossing⊆2-planar.Theseclassesarenotequal(Figure6).Weﬁrstprovesomepropertiesaboutthecrossingsgraphs(Gómez-RodríguezandNivre,2010)of1-Endpoint-Crossingtrees.Thecrossingsgraphofa 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 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 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 20 (A,乙)(A,C)(乙,d)(C,e)(d,F)(A)(A,乙)(A,C)(乙,e)(G,d)(H,F)(乙,G)(G,H)(乙)Figure7:ThecrossinggraphsforFigures1aand1b.graphhasavertexcorrespondingtoeachedgeintheoriginal,andanedgebetweentwoverticesifthetwoedgestheycorrespondtocross.ThecrossingsgraphsforthedependencytreesinFigures1aand1bareshowninFigures7aand7b,respectively.Lemma2.No1-Endpoint-Crossingtreehasacycleoflength3initscrossingsgraph.Proof.Assumethereexistedacyclee1,e2,e3.e1ande3mustshareanendpoint,astheybothcrosse2.Sincee1ande3shareanendpoint,e1ande3donotcross.Contradiction.Lemma3.Anyoddcycleofsizen(n≥4)inacrossingsgraphofa1-Endpoint-Crossingtreeusesatmostndistinctverticesintheoriginalgraph.Proof.Lete1,e2,...,enbeanoddcycleinacross-ingsgraphofa1-Endpoint-Crossingtreewithn≥4.Sincen≥4,e1,e2,en−1,andenaredistinctedges.Letabethevertexthate1anden−1share(becausetheybothcrossen)andletbbethevertexthate2andenshare(bothcrosse1).Notethate1anden−1cannotcontainbandthate2andencannotcontaina(otherwisetheywouldnotcrossanedgeadjacenttothemalongthecycle).Wewillnowconsiderhowmanyverticeseachedgecanintroducethataredistinctfromallverticespreviouslyseeninthecycle.e1ande2necessarilyintroducetwodistinctverticeseach.Leteobetheﬁrstoddedgethatcontainsb(weknowoneexistssinceencontainsb).(oisatleast3,sincee1doesnotcontainb.)eo’sothervertexmustbetheonesharedwitheo−2(eo−2doesnotcontainb,sinceeowastheﬁrstoddedgetocontainb).There-fore,bothofeo’sverticeshavealreadybeenseenalongthecycle.Similarly,leteebetheﬁrstevenedgethatcon-tainsana.Bythesamereasoning,eemustnotin-troduceanynewvertices.Allotheredgeseisuchthati>2andei6=eoandei6=eeintroduceatmostonenewvertex,sinceonemustbesharedwiththeedgeei−2.Therearen−4suchedges.Countingupallpossibilities,themaximumnum-berofdistinctverticesis4+(n−4)=n.Theorem1.1-Endpoint-Crossingtrees⊆2-planar.Proof.Assumethereexistedanoddcycleinthecrossingsgraphofa1-Endpoint-Crossingtree.Thecyclehassizeatleast5(byLemma2).Thereareatleastasmanyedgesasverticesinthesubgraphoftheforestinducedbytheverticesusedinthecycle(byLemma3).Thatimpliestheexistenceofacycleintheoriginalgraph,contradictingthattheoriginalgraphwasatree.Sincetherearenooddcyclesinthecrossingsgraph,thecrossingsgraphofedgesisbipartite.Eachsideofthebipartitegraphcanbeassignedtoapage,suchthatnotwoedgesonthesamepagecross.Therefore,theoriginalgraphwas2-planar.5.2Linguistics:Cross-serialVerbConstructionsandSuccessiveCyclicityCross-serialverbconstructionswereusedtoprovideevidenceforthe“non-context-freeness”ofnaturallanguage(Shieber,1985).Cross-serialverbcon-structionswithtwoverbsform1-Endpoint-Crossingtrees.Belowisacross-serialsentencefromSwiss-German,从(1)inShieber(1985):dasmeremHanseshuushälfedaastriichethatweHansDATthehouseACChelpedpaintTheedges(那,helped),(helped,我们),和(helped,Hans)areeachonlycrossedbyanedgewithanendpointatpaint;theedge(paint,房子)isonlycrossedbyedgeswithanendpointathelped.Moregenerally,withasetoftwocrossserialverbsinasubordinateclause,eachverbshouldsufﬁceasthecrossingpointforalledgesincidenttotheotherverbthatarecrossed.Cross-serialconstructionswiththreeormoreverbswouldhavedependencytreesthatviolate1-

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你

/
t

A
C
我
/

我

A
r
t
我
C
e
–
p
d

F
/

d
哦

我
/

1
0
1
1
6
2

/
t

我

A
C
_
A
_
0
0
2
0
6
1
5
6
6
6
3
9

/
t

我

A
C
_
A
_
0
0
2
0
6
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

WhatdidsayBAC…Zatet?nsaid1said2t1t2Figure8:Anexampleofwh-movementoverapoten-tiallyunboundednumberofclauses.Theedgesbe-tweentheheadsofeachclausecrosstheedgesfromtracetotrace,butallobey1-Endpoint-Crossing.Endpoint-Crossing.Psycholinguistically,betweentwoandthreeverbsisexactlywherethereisalargechangeinthesentenceprocessingabilitiesofhumanlisteners(basedonbothgrammaticaljudgmentsandscoresonacomprehensiontask)(Bachetal.,1986).Morespeculatively,theremaybeaconnectionbetweentheformof1-Endpoint-Crossingtreesandphases(大致,propositionalunitssuchasclauses)inMinimalism(Chomskyetal.,1998).Figure8showsanexampleofwh-movementoverapoten-tiallyunboundednumberofclauses.Thephase-impenetrabilitycondition(PIC)statesthatonlytheheadofthephaseandelementsthathavemovedtoitsedgeareaccessibletotherestofthesentence(Chomskyetal.,1998,p.22).Movementisthere-forerequiredtobesuccessivecyclic,withamovedelementleavingachainoftracesattheedgeofeachclauseonitswaytoitsﬁnalpronouncedloca-tion(Chomsky,1981).InFigure8,noticethatthecrossingedgesformarepeatedpatternthatobeysthe1-Endpoint-Crossingproperty.Moregenerally,wesuspectthattreessatisfyingthePICwilltendtoalsobe1-Endpoint-Crossing.Furthermore,ifthetraceswerenotattheedgeofeachclause,andin-steadwerepositionedbetweenaheadandoneofitsarguments,1-Endpoint-Crossingwouldbevio-lated.Forexample,ift2inFigure8werebe-tweenCandsaid2,thentheedge(t1,t2)wouldcross(说,said1),(said1,said2),和(C,said2),whichdonotallshareanendpoint.Anexplorationoftheselinguisticconnectionsmaybeaninterestingavenueforfurtherresearch.6Conclusions1-Endpoint-Crossingtreescharacterizeover95%ofstructuresfoundinnaturallanguagetreebank,andcanbeparsedinonlyafactorofnmoretimethanprojectivetrees.Thedynamicprogrammingalgo-rithmforprojectivetrees(艾斯纳,2000)hasbeenextendedtohandlehigherorderfactors(McDonaldandPereira,2006;Carreras,2007;KooandCollins,2010),addingatmostafactorofntotheedge-basedrunningtime;itwouldbeinterestingtoex-tendthealgorithmpresentedheretoincludehigherorderfactors.1-Endpoint-Crossingisaconditiononedges,whilepropertiessuchaswell-nestednessorblockdegreeareframedintermsofsubtrees.Threeedgeswillalwayssufﬁceasacertiﬁcateofa1-Endpoint-Crossingviolation(twovertex-disjointedgesthatbothcrossathird).Incontrast,forapropertylikeill-nestedness,twonodesmighthavealeastcommonancestorarbitrarilyfaraway,andsoonemightneedtheentiregraphtoverifywhetherthesub-treesrootedatthosenodesaredisjointandill-nested.Wehavediscussedcross-serialdepen-dencies;afurtherexplorationofwhichlinguisticphenomenawouldandwouldnothave1-Endpoint-Crossingdependencytreesmayberevealing.AcknowledgmentsWewouldliketothankJulieLegateforanin-terestingdiscussion.ThismaterialisbaseduponworksupportedunderaNationalScienceFoun-dationGraduateResearchFellowship,NSFAwardCCF1137084,andArmyResearchOfﬁceMURIgrantW911NF-07-1-0216.ADynamicProgramtoﬁndthemaximumscoring1-Endpoint-CrossingTreeInput:MatrixS:S[我,j]isthescoreofthedirectededge(我,j)输出:Maximumscoreofa1-Endpoint-Crossingtreeoververtices[0,n],rootedat0Init:∀iInt[我,我,F,F]=Int[我,i+1,F,F]=0Int[我,我,时间,F]=Int[我,我,F,时间]=Int[我,我,时间,时间]=−∞Final:Int[0,n,F,时间]Shorthandforbooleans:TF(X,S):=ifx=T,exactlyoneofthesetSistrueifx=F,allofthesetSmustbefalsebi,bj,bxaretrueiffthecorrespondingboundarypointhasitsincomingedge(parent)inthatsub-problem.FortheLRsub-problem,biandbjarealwaysfalse,andsoomitted.Forallsub-problemswiththesufﬁxAFromB,theboundarypointAhasitsparentedgeinthesub-problemsolution;theothertwoboundarypointsdonot.Forexample,L_XFromIwouldcor-respondtohavingbooleansbi=bj=Fandbx=T,withtherestrictionthatxmustbeadescendantofi.

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你

/
t

A
C
我
/

我

A
r
t
我
C
e
–
p
d

F
/

d
哦

我
/

1
0
1
1
6
2

/
t

我

A
C
_
A
_
0
0
2
0
6
1
5
6
6
6
3
9

/
t

我

A
C
_
A
_
0
0
2
0
6
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

Int[我,j,F,bj]←maxInt[i+1,j,时间,F]ifbj=FS[我,j]+Int[我,j,F,F]ifbj=Tmaxk∈(我,j)S[我,k]+Int[我,k,F,F]+Int[k,j,F,bj]maxTF(bj,{bl,br})LR[我,k,j,bl]+Int[k,j,F,br]maxl∈(k,j),TF(时间,{bl,bm,br})(西德:26)右[我,k,我,F,F,bl]+Int[k,我,F,bm]+L[我,j,k,br,bj,F]LR[我,k,我,bl]+Int[k,我,F,bm]+Int[我,j,br,bj]maxl∈(我,k),TF(时间,{bl,bm,br})(西德:26)Int[我,我,F,bl]+L[我,k,我,bm,F,F]+氮[k,j,我,F,bj,br]右[我,我,k,F,bl,F]+Int[我,k,bm,F]+L[k,j,我,F,bj,br]Int[我,j,时间,F]←symmetrictoInt[我,j,F,时间]Int[我,j,时间,时间]←−∞LR[我,j,X,bx]←maxL[我,j,X,F,F,bx]右[我,j,X,F,F,bx]maxk∈(我,j),TF(bx,{bxl,bxr}),TF(时间,{bkl,bkr})L[我,k,X,F,bkl,bxl]+右[k,j,X,bkr,F,bxr]氮[我,j,X,双,bj,F]←maxInt[我,j,双,bj]S[X,我]+氮[我,j,X,F,bj,F]ifbi=TS[X,j]+氮[我,j,X,双,F,F]ifbj=Tmaxk∈(我,j)S[X,k]+氮[我,k,X,双,F,F]+Int[k,j,F,bj]氮[我,j,X,F,bj,时间]←maxS[我,X]+氮[我,j,X,F,bj,F]S[X,j]+N_XFromI[我,j,X]ifbj=TS[j,X]+氮[我,j,X,F,F,F]ifbj=FS[j,X]+Int[我,j,F,时间]ifbj=Tmaxk∈(我,j)S[X,k]+N_XFromI[我,k,X]+Int[k,j,F,bj]maxk∈(我,j)S[k,X]+(西德:26)Int[我,k,F,时间]+Int[k,j,F,bj]氮[我,k,X,F,F,F]+Int[k,j,时间,bj]氮[我,j,X,时间,F,时间]←symmetrictoN[我,j,X,F,时间,时间]氮[我,j,X,时间,时间,时间]←−∞N_XFromI[我,j,X]←maxS[我,X]+氮[我,j,X,F,F,F]maxk∈(我,j)(西德:26)S[X,k]+N_XFromI[我,k,X]+Int[k,j,F,F]S[k,X]+Int[我,k,F,时间]+Int[k,j,F,F]N_IFromX[我,j,X]←max(S[X,我]+氮[我,j,X,F,F,F]maxk∈(我,j)S[X,k]+氮[我,k,X,时间,F,F]+Int[k,j,F,F]N_XFromJ[我,j,X]←symmetrictoN_XFromI[我,j,X]N_JFromX[我,j,X]←symmetrictoN_IFromX[我,j,X]L[我,j,X,双,bj,F]←maxInt[我,j,双,bj]S[X,我]+L[我,j,X,F,bj,F]ifbi=TS[X,j]+L[我,j,X,双,F,F]ifbj=Tmaxk∈(我,j),TF(双,{bl,br})S[X,k]+(西德:26)L[我,k,X,bl,F,F]+氮[k,j,我,F,bj,br]Int[我,k,bl,F]+L[k,j,我,F,bj,br]L[我,j,X,F,bj,时间]←maxS[我,X]+L[我,j,X,F,bj,F]S[X,j]+L_XFromI[我,j,X]ifbj=TS[j,X]+L[我,j,X,F,F,F]ifbj=FS[j,X]+L_JFromI[我,j,X]ifbj=Tmaxk∈(我,j)S[X,k]+L_XFromI[我,k,X]+氮[k,j,我,F,bj,F]maxk∈(我,j)S[k,X]+L_JFromI[我,k,X]+氮[k,j,我,F,bj,F]L[我,k,X,F,F,F]+氮[k,j,我,时间,bj,F]maxTF(时间,{bl,br})Int[我,k,F,bl]+L[k,j,我,br,bj,F]L[我,j,X,时间,bj,时间]←notreachableL_XFromI[我,j,X]←maxS[我,X]+L[我,j,X,F,F,F]maxk∈(我,j)S[X,k]+L_XFromI[我,k,X]+氮[k,j,我,F,F,F]maxk∈(我,j)S[k,X]+L_JFromI[我,k,X]+氮[k,j,我,F,F,F]L[我,k,X,F,F,F]+N_IFromX[k,j,我]Int[我,k,F,时间]+L[k,j,我,F,F,F]Int[我,k,F,F]+L_IFromX[k,j,我]L_IFromX[我,j,X]←maxS[X,我]+L[我,j,X,F,F,F]maxk∈(我,j)S[X,k]+L[我,k,X,时间,F,F]+氮[k,j,我,F,F,F]L[我,k,X,F,F,F]+N_XFromI[k,j,我]Int[我,k,时间,F]+L[k,j,我,F,F,F]Int[我,k,F,F]+L_XFromI[k,j,我]L_JFromX[我,j,X]←maxS[X,j]+L[我,j,X,F,F,F]maxk∈(我,j)S[X,k]+(西德:26)L[我,k,X,F,F,F]+Int[k,j,F,时间]Int[我,k,F,F]+L_JFromI[k,j,我]L_JFromI[我,j,X]←maxInt[我,j,F,时间]maxk∈(我,j)S[X,k]+(西德:26)L[我,k,X,F,F,F]+N_JFromX[k,j,我]Int[我,k,F,F]+L_JFromX[k,j,我]

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你

/
t

A
C
我
/

我

A
r
t
我
C
e
–
p
d

F
/

d
哦

我
/

1
0
1
1
6
2

/
t

我

A
C
_
A
_
0
0
2
0
6
1
5
6
6
6
3
9

/
t

我

A
C
_
A
_
0
0
2
0
6
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

右[我,j,X,双,bj,F]←symmetrictoL[我,j,X,双,bj,F]右[我,j,X,双,F,时间]←symmetrictoL[我,j,X,F,bj,时间]右[我,j,X,双,时间,时间]←notreachableR_XFromJ[我,j,X]←symmetrictoL_XFromI[我,j,X]R_JFromX[我,j,X]←symmetrictoL_IFromX[我,j,X]R_IFromX[我,j,X]←symmetrictoL_JFromX[我,j,X]R_IFromJ[我,j,X]←symmetrictoL_JFromI[我,j,X]ReferencesE.Bach,C.Brown,andW.Marslen-Wilson.1986.Crossedandnesteddependenciesingermananddutch:Apsycholinguisticstudy.LanguageandCognitiveProcesses,1(4):249–262.F.BernhartandP.C.Kainen.1979.Thebookthicknessofagraph.JournalofCombinatorialTheory,SeriesB,27(3):320–331.M.Bodirsky,M.Kuhlmann,andM.Möhl.2005.Well-nesteddrawingsasmodelsofsyntacticstructure.InInTenthConferenceonFormalGrammarandNinthMeetingonMathematicsofLanguage,pages88–1.UniversityPress.X.Carreras.2007.Experimentswithahigher-orderprojectivedependencyparser.InProceedingsoftheCoNLLSharedTaskSessionofEMNLP-CoNLL,vol-ume7,pages957–961.N.Chomsky,MassachusettsInstituteofTechnology.Dept.ofLinguistics,andPhilosophy.1998.Minimal-istinquiries:theframework.MIToccasionalpapersinlinguistics.DistributedbyMITWorkingPapersinLinguistics,和,Dept.ofLinguistics.N.Chomsky.1981.LecturesonGovernmentandBind-ing.Dordrecht:Foris.F.Chung,F.Leighton,andA.Rosenberg.1987.Em-beddinggraphsinbooks:Alayoutproblemwithap-plicationstoVLSIdesign.SIAMJournalonAlgebraicDiscreteMethods,8(1):33–58.H.Cui,R.Sun,K.Li,M.Y.Kan,andT.S.Chua.2005.Questionansweringpassageretrievalusingdepen-dencyrelations.InProceedingsofthe28thannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval,pages400–407.ACM.A.CulottaandJ.Sorensen.2004.Dependencytreekernelsforrelationextraction.InProceedingsofthe42ndAnnualMeetingonAssociationforComputa-tionalLinguistics,page423.AssociationforCompu-tationalLinguistics.Y.DingandM.Palmer.2005.Machinetranslationusingprobabilisticsynchronousdependencyinsertiongram-mars.InProceedingsofthe43rdAnnualMeetingonAssociationforComputationalLinguistics,pages541–548.AssociationforComputationalLinguistics.J.Eisner.2000.Bilexicalgrammarsandtheircubic-timeparsingalgorithms.InHarryBuntandAntonNijholt,编辑,AdvancesinProbabilisticandOtherParsingTechnologies,pages29–62.KluwerAcademicPublishers,October.S.EvenandA.Itai.1971.Queues,stacks,andgraphs.InProc.InternationalSymp.onTheoryofMachinesandComputations,pages71–86.C.Gómez-RodríguezandJ.Nivre.2010.Atransition-basedparserfor2-planardependencystructures.InProceedingsofACL,pages1492–1501.C.Gómez-Rodríguez,J.Carroll,andD.Weir.2011.De-pendencyparsingschemataandmildlynon-projectivedependencyparsing.ComputationalLinguistics,37(3):541–586.T.KooandM.Collins.2010.Efﬁcientthird-orderde-pendencyparsers.InProceedingsofACL,pages1–11.M.Kuhlmann.2013.Mildlynon-projectivedependencygrammar.ComputationalLinguistics,39(2).R.McDonaldandF.Pereira.2006.Onlinelearningofapproximatedependencyparsingalgorithms.InPro-ceedingsofEACL,pages81–88.R.McDonaldandG.Satta.2007.Onthecomplexityofnon-projectivedata-drivendependencyparsing.InProceedingsofthe10thInternationalConferenceonParsingTechnologies,pages121–132.R.McDonald,F.Pereira,K.Ribarov,andJ.Hajiˇc.2005.Non-projectivedependencyparsingusingspanningtreealgorithms.InProceedingsoftheconferenceonHumanLanguageTechnologyandEmpiricalMethodsinNaturalLanguageProcessing,pages523–530.As-sociationforComputationalLinguistics.E.Pitler,S.Kannan,andM.Marcus.2012.Dynamicprogrammingforhigherorderparsingofgap-mindingtrees.InProceedingsofEMNLP,pages478–488.L.A.Ringenberg.1967.Collegegeometry.Wiley.A.RushandS.Petrov.2012.Vinepruningforefﬁ-cientmulti-passdependencyparsing.InProceedingsofNAACL,pages498–507.S.M.Shieber.1985.Evidenceagainstthecontext-freenessofnaturallanguage.LinguisticsandPhiloso-phy,8(3):333–343.H.ZhangandR.McDonald.2012.Generalizedhigher-orderdependencyparsingwithcubepruning.InPro-ceedingsofEMNLP,pages320–331.

我

D
哦
w
n
哦
A
d
e
d

F
r
哦
米
H

t
t

:
/
/

d
我
r
e
C
t
.

米

我
t
.

e
d
你

/
t

A
C
我
/

我

A
r
t
我
C
e
–
p
d

F
/

d
哦

我
/

1
0
1
1
6
2

/
t

我

A
C
_
A
_
0
0
2
0
6
1
5
6
6
6
3
9

/
t

我

A
C
_
A
_
0
0
2
0
6
p
d

乙
y
G
你
e
s
t

哦
n
0
8
S
e
p
e
米
乙
e
r
2
0
2
3

24
下载pdf