Transacciones de la Asociación de Lingüística Computacional, 1 (2013) 267–278. Editor de acciones: Brian Roark.
Submitted 3/2013; Publicado 7/2013. C(cid:13)2013 Asociación de Lingüística Computacional.

EfficientParsingforHead-SplitDependencyTreesGiorgioSattaDept.ofInformationEngineeringUniversityofPadua,Italysatta@dei.unipd.itMarcoKuhlmannDept.ofLinguisticsandPhilologyUppsalaUniversity,Swedenmarco.kuhlmann@lingfil.uu.seAbstractHeadsplittingtechniqueshavebeensuccess-fullyexploitedtoimprovetheasymptoticruntimeofparsingalgorithmsforproject-ivedependencytrees,underthearc-factoredmodel.Inthisarticleweextendthesetech-niquestoaclassofnon-projectivedependencytrees,calledwell-nesteddependencytreeswithblock-degreeatmost2,whichhasbeenprevi-ouslyinvestigatedintheliterature.Wedefineastructuralpropertythatallowsheadsplittingforthesetrees,andpresenttwoalgorithmsthatim-proveovertheruntimeofexistingalgorithmsatnosignificantlossincoverage.1IntroductionMuchoftherecentworkondependencyparsinghasbeenaimedatfindingagoodbalancebetweenac-curacyandefficiency.Foroneendofthespectrum,Eisner(1997)showedthatthehighest-scoringpro-jectivedependencytreeunderanarc-factoredmodelcanbecomputedintimeO.n3/,wherenisthelengthoftheinputstring.Laterworkhasfocusedonmak-ingprojectiveparsingviableundermoreexpressivemodels(Carreras,2007;KooandCollins,2010).Atthesametime,ithasbeenobservedthatformanystandarddatasets,thecoverageofprojectivetreesisfarfromcomplete(KuhlmannandNivre,2006),whichhasledtoaninterestinparsingal-gorithmsfornon-projectivetrees.Whilenon-project-iveparsingunderanarc-factoredmodelcanbedoneintimeO.n2/(McDonaldetal.,2005),parsingwithmoreinformedmodelsisintractable(McDonaldandSatta,2007).Thishasledseveralauthorstoinvestig-ate‘mildlynon-projective’classesoftrees,withthegoalofachievingabalancebetweenexpressivenessandcomplexity(KuhlmannandNivre,2006).Inthisarticlewefocusonaclassofmildlynon-projectivedependencystructurescalledwell-nesteddependencytreeswithblock-degreeatmost2.ThisclasswasfirstintroducedbyBodirskyetal.(2005),whoshowedthatitcorresponds,inanaturalway,totheclassofderivationtreesoflexicalizedtree-adjoin-inggrammars(JoshiandSchabes,1997).Whiletherearelinguisticargumentsagainsttherestrictiontothisclass(MaierandLichte,2011;Chen-MainandJoshi,2010),KuhlmannandNivre(2006)foundthatithasexcellentcoverageonstandarddatasets.Assum-inganarc-factoredmodel,well-nesteddependencytreeswithblock-degree(cid:20)2canbeparsedintimeO.n7/usingthealgorithmofG´omez-Rodr´ıguezetal.(2011).Recientemente,Pitleretal.(2012)haveshownthatifanadditionalrestrictioncalled1-inheritisim-posed,parsingcanbedoneintimeO.n6/,withoutanyadditionallossincoverageonstandarddatasets.Standardcontext-freeparsingmethods,whenadap-tedtotheparsingofprojectivetrees,provideO.n5/timecomplexity.TheO.n3/timeresultreportedbyEisner(1997)hasbeenobtainedbyexploitingmoresophisticateddynamicprogrammingtechniquesthat‘split’dependencytreesatthepositionoftheirheads,inordertosavebookkeeping.Splittingtechniqueshavealsobeenexploitedtospeedupparsingtimeforotherlexicalizedformalisms,suchasbilexicalcontext-freegrammarsandheadautomata(EisnerandSatta,1999).Sin embargo,toourknowledgenoat-tempthasbeenmadeintheliteraturetoextendthesetechniquestonon-projectivedependencyparsing.InthisarticleweleveragethecentralideafromEisner’salgorithmandextendittotheclassofwell-nesteddependencytreeswithblock-degreeatmost2.

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

268

Weintroduceastructuralproperty,calledhead-split,thatallowsustosplitthesetreesatthepositionsoftheirheads.Thepropertyisrestrictive,meaningthatitreducestheclassoftreesthatcanbegenerated.However,weshowthattherestrictiontohead-splittreescomesatnosignificantlossincoverage,anditallowsparsingintimeO.n6/,anasymptoticimprove-mentofoneorderofmagnitudeoverthealgorithmbyG´omez-Rodr´ıguezetal.(2011)fortheunrestric-tedclass.Wealsoshowthatrestrictingtheclassofhead-splittreesbyimposingthealreadymentioned1-inheritpropertydoesnotcauseanyadditionallossincoverage,andthatparsingforthecombinedclassispossibleintimeO.n5/,oneorderofmagnitudefasterthanthealgorithmbyPitleretal.(2012)forthe1-inheritclasswithoutthehead-splitcondition.Theaboveresultshaveconsequencesalsofortheparsingofotherrelatedformalisms,suchasthealreadymentionedlexicalizedtree-adjoininggram-mars.Thiswillbediscussedinthefinalsection.2HeadSplittingTointroducethebasicideaofthisarticle,webrieflydiscussinthissectiontwowell-knownalgorithmsforcomputingthesetofallprojectivedependencytreesforagiveninputsentence:thena¨ıve,CKY-stylealgorithm,andtheimprovedalgorithmwithheadsplitting,intheversionofEisnerandSatta(1999).1CKYparsingTheCKY-stylealgorithmworksinapurebottom-upway,buildingdependencytreesbycombiningsubtrees.AssuminganinputstringwDa1(cid:1)(cid:1)(cid:1)un,norte(cid:21)1,eachsubtreetisrepresentedbymeansofafinitesignatureŒi;j;h(cid:141),calleditem,wherei;jaretheboundarypositionsoft’sspanoverwandhisthepositionoft’sroot.Thisistheonlyinformationweneedinordertocombinesubtreesunderthearc-factoredmodel.NotethatthenumberofpossiblesignaturesisO.n3/.ThemainstepofthealgorithmisdisplayedinFigure1(a).Hereweintroducethegraphicalconven-tion,usedthroughoutthisarticle,ofrepresentingasubtreebyashadedarea,withanhorizontallinein-dicatingthespannedfragmentoftheinputstring,andofmarkingthepositionoftheheadbyabullet.TheillustratedstepattachesatreewithsignatureŒk;j;d(cid:141)1Eisner(1997)describesaslightlydifferentalgorithm.(a)ahadikj)ahadij(b)ahadk)ahad(C)ahadj)ahadjFigure1:Basicstepsfor(a)theCKY-stylealgorithmand(b,C)theheadsplittingalgorithm.asadependentofatreewithsignatureŒi;k;h(cid:141).TherecanbeO.n5/instantiationsofthisstep,andthisisalsotherunningtimeofthealgorithm.Eisner’salgorithmEisnerandSatta(1999)im-proveovertheCKYalgorithmbyreducingthenum-berofpositionrecordsinanitem.Theydothisby‘splitting’eachtreeintoaleftandarightfragment,sothattheheadisalwaysplacedatoneofthetwoboundarypositionsofafragment,asopposedtobe-ingplacedataninternalposition.Inthiswayitemsneedonlytwoindices.Leftandrightfragmentscanbeprocessedindependently,andmergedafterwards.Letusconsiderarightfragmenttwithheadah.Attachmentattofarightdependenttreewithheadadisnowperformedintwosteps.Thefirststepat-tachesaleftfragmentwithheadad,asinFigure1(b).Thisresultsinanewtypeoffragment/itemthathasbothheadsahandadplacedatitsboundaries.Thesecondstepattachesarightfragmentwithheadad,asinFigure1(C).Thenumberofpossibleinstanti-ationsofthesesteps,andtheasymptoticruntimeofthealgorithm,isO.n3/.Inthisarticleweextendthesplittingtechniquetotheclassofwell-nesteddependencytreeswithblock-degreeatmost2.Thisamountstodefiningafac-torizationforthesetreesintofragments,eachwithitsownheadatoneofitsboundarypositions,alongwithsomeunfoldingoftheattachmentoperationintointermediatesteps.Whileforprojectivetreesheadsplittingcanbedonewithoutanylossincoverage,fortheextendedclassheadsplittingturnsouttobeaproperrestriction.Theempiricalrelevanceofthiswillbediscussedin(cid:144)7.

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

269

3Head-SplitTreesInthissectionweintroducetheclassofwell-nesteddependencytreeswithblock-degreeatmost2,anddefinethesubclassofhead-splitdependencytrees.3.1PreliminariesFornon-negativeintegersi;jwewriteŒi;j(cid:141)tode-notethesetfi;iC1;:::;jg;wheni>j,Œi;j(cid:141)istheemptyset.ForastringwDa1(cid:1)(cid:1)(cid:1)un,wheren(cid:21)1andeachaiisalexicaltoken,andfori;j2Œ0;norte(cid:141)withi(cid:20)j,wewritewi;jtodenotethesubstringaiC1(cid:1)(cid:1)(cid:1)ajofw;Wisconsin;iistheemptystring.Adependencytreetoverwisadirectedtreewhosenodesareasubsetofthetokensaiinwandwhosearcsencodeadependencyrelationbetweentwonodes.Wewriteai!ajtodenotethearc.ai;aj/int;aquí,thenodeaiisthehead,andthenodeajisthedependent.Ifeachtokenai,i2Œ1;norte(cid:141),isanodeoft,thentiscalledcomplete.Sometimeswewritetaitoemphasizethattreetisrootedinnodeai.Ifaiisanodeoft,wealsowritetŒai(cid:141)todenotethesubtreeoftcomposedbynodeaiasitsrootandallofitsdescendantnodes.Thenodesoftuniquelyidentifyasetofmax-imalsubstringsofw,thatis,substringsseparatedbytokensnotint.Thesequenceofsuchsubstrings,orderedfromlefttoright,istheyieldoft,writtenyd.t/.Letaibesomenodeoft.Theblock-degreeofaiint,writtenbd.ai;t/,isdefinedasthenumberofstringcomponentsofyd.tŒai(cid:141)/.Theblock-degreeoft,writtenbd.t/,isthemaximalblock-degreeofitsnodes.Treetisnon-projectiveifbd.t/>1.Treetiswell-nestedif,foreachnodeaioftandforeverypairofoutgoingdependenciesai!ad1andai!ad2,thestringcomponentsofyd.tŒad1(cid:141)/andyd.tŒad2(cid:141)/donot‘interleave’inw.Moreprecisely,itisrequiredthat,ifsomecomponentofyd.tŒadi(cid:141)/,i2Œ1;2(cid:141),occursinwinbetweentwocomponentss1;s2ofyd.tŒadj(cid:141)/,j2Œ1;2(cid:141)andj¤i,thenallcomponentsofyd.tŒadi(cid:141)/occurinbetweens1;s2.Throughoutthisarticle,wheneverweconsideradependencytreetwealwaysimplicitlyassumethattisoverw,thatthasblock-degreeatmost2,andthattiswell-nested.Lettaibesuchatree,withbd.ai;tai/D2.Wecalltheportionofwinbetweenthetwosubstringsofyd.tai/thegapoftai,denotedbygap.tai/.ahad4ad3ad2ad1m.tah/Figure2:Exampleofanodeahwithblock-degree2inanon-projective,well-nesteddependencytreetah.Integerm.tah/,definedin(cid:144)3.2,también está marcado. Ejemplo 1 La Figura 2 muestra esquemáticamente un árbol bien anidado con grado de bloque 2;Hemos marcado el nodo raíz y sus nodosadi dependientes. Para cada nododeadi,área sombreadadestacadastŒadi(cid:141).Wehavebd.ah;tah/Dbd.ad1;tah/Dbd.ad4;tah/D2andbd.ad2;tah/Dbd.ad3;tah/D1.(cid:3)3.2La propiedad de división de cabeza Decimos que un árbol de dependencia cuya propiedad de división de cabeza satisface la siguiente condición. Letah!adbeanydependencyintwithbd.ah;t/Dbd.ad;t/D2.Whenevergap.tŒad(cid:141)/contieneah,tambiéndebecontenerap.tŒah(cid:141)/.Intuitivamente,estosignificaqueifyd.tŒad(cid:141)/'cruce'el token léxico ahinw,entoncesyd.tŒad(cid:141)/también debe “cruzar” la brecha.tŒah(cid:141)/.Ejemplo2Dependenciaah!ad1enFigura3viol-atesthehead-splitcondition,sinceyd.tŒad1(cid:141)/cruces sobre el token léxico ahinw,pero no cruza la brecha.tŒah(cid:141)/.Las dependencias salientes restantes de ah satisfacen trivialmente la condición de división de cabeza,ya que los nodos secundarios tienen grado de bloque 1.(cid:3)Lettahbeadependencytreesatisfacethehead-splitpropertyandwithbd.ah;tah/D2.Wespecifybelowaconstructionthat‘splits’tahwithrespecttothepositionoftheheadahinyd.tah/,resultingintwodependencytreessharingtherootahandhavingalloftheremainingnodesformingtwodisjointsets.Furthermore,theresultingtreeshaveblock-degreeatmost2.ahad1ad2ad3Figure3:Arcah!ad1violatesthehead-splitcondition.

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

270

(a)ahad4ad3(b)ahad2ad1m.tah/Figure4:Lowertree(a)anduppertree(b)fragmentsforthedependencytreeinFigure2.Letyd.tah/Dhwi;j;wp;qiandassumethatahisplacedwithinwi;j.(Asymmetricconstructionshouldbeusedincaseahisplacedwithinwp;q.)Themirrorimageofahwithrespecttogap.tah/,writtenm.tah/,isthelargestintegerinŒp;q(cid:141)suchthattherearenodependencieslinkingnodesinwi;h(cid:0)1andnodesinwp;m.tah/andtherearenodependencieslinkingnodesinwh;jandnodesinwm.tah/;q.Itisnothardtoseethatsuchanintegeralwaysexists,sincetahiswell-nested.Weclassifyeverydependentadofahasbeingan‘upper’dependentora‘lower’dependentofah,accordingtothefollowingconditions:(i)Ifd2Œi;h(cid:0)1(cid:141)[Œm.tah/C1;q(cid:141),thenadisanupperdependentofah.(ii)Ifd2ŒhC1;j(cid:141)[Œp;m.tah/(cid:141),luegonadesdisminuyedependientedeah.Elárbolsuperiordeesteárboldedependenciaenraizadoenmanocompuestoportodaslasdependenciasah!adintahwithadanupperdependienteofah,junto con todos los subtreestahŒad(cid:141)arraigados en aquellos dependientes. De manera similar,elárbolinferiordeesteelárboldedependenciaarraigadoenmanocompuestoportodaslasdependenciasah!adintahwithadalowerde-pendentofah,junto con todos los subtreestahŒad(cid:141)arraigados en aquellos dependientes. Como una convención general,en este artículo escribimos U;ahandtL;ah para denotar los árboles superiores e inferiores de ah,respectivamente. Tenga en cuenta que,en algunos casos degenerados,estos a flores o dependientes superiores pueden estar vacíos;entonces U;ahortL;ah consta únicamente del nodo raíz. Ejemplo 3 Considere el árbol que se muestra en la Figura 2. Integerm.tah/denota el límite entre el componente correcto de d.tahŒad4(cid:141)/andtherightcomponentofyd.tahŒad1(cid:141)/.Los nodos ad3 y ad4 son dependientes menores,y los nodosad1yad2sonsuperdependientes.TreestL;ahandtU;se muestra en la Figura 4(a)y(b),respectivamente.(cid:3)La importancia de la propiedad dividida puede explicarse informalmente de la siguiente manera. Letah!adbeadependencyintah.Cuandoseparamoslosárbolessuperioresylosinferioresdeah,elsubtreetahŒad entero(cid:141)termina en cualquiera de estos dos fragmentos. Esto nos permite almacenar fragmentos superiores e inferiores para alguna cabeza independientemente de la otra.,y recombinarlos libremente. Más formalmente,Nuestros algoritmos harán uso de las siguientes tres propiedades.,declarado aquí sin ninguna prueba formal:P1árbolU;ahandtL;aharewell-anidado,tener grado de bloque(cid:20)2,y satisface la propiedad head-split.P2TreestU;ahandtL;ahtienensucabezasiempreubicadaunodeloslímitesensuscampos.P3Lett0U;ahandt00L;ahbelosárbolessuperioresyinferioresdeárboldistinto0ahandt00ah,respectivamente.Ifm.t0ah/Dm.t00ah/,entoncesexisteunárboltalquetU;ahDt0U;ahandtL;ahDt00L;ah.4ParsingItemsLetwDa1(cid:1)(cid:1)(cid:1)un,norte(cid:21)1,ser la cadena de entrada. Necesitamos representar de manera compacta los árboles que abarcan subcadenas de w registrando solo la información necesaria para combinar estos árboles en árboles más grandes durante el proceso de análisis. Hacemos esto asociando cada árbol con una firma,calleditem,cualisatupleŒi;j;pag;q;h(cid:141)X,dondeh2Œ1;norte(cid:141)identifica la tokenah,i;con0(cid:20)i(cid:20)j(cid:20)iidentificarsubcadenawi;j,etc.;qconjh>jC1ThetwocaseshjC1arribaseutilizarácuandoelnodoraízdetahaúnnoharecopiladotodossusdependientes.Tengaencuentaqueth2fi;jC1gi no se utiliza en la definición de elemento. Esto tiene como objetivo evitar diferentes entidades que representen el mismo árbol de dependencia.,

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

271

lo cual no es deseado para la especificación de nuestro algoritmo radial. Como ejemplo,artículosŒi;j;(cid:0);(cid:0);iC1(cid:141)XandŒiC1;j;(cid:0);(cid:0);iC1(cid:141)Xbothrepresentadepend-encytreetaiC1withyd.taiC1/Dhwi;ji.Esteyotroscasossimilaressonevitadosporelbancontrath2fi;jC1g,lo cual equivale a imponer alguna forma normal para los artículos. En nuestro ejemplo,soloitemŒi;j;(cid:0);(cid:0);iC1(cid:141)Firma Xisvalid.Finalmente,distinguimos entre varios tipos de artículos,indicado por el valor del subíndice X. Estos tipos son específicos de cada algoritmo de análisis,y se definirá en secciones posteriores. 5 Análisis de árboles con división de cabeza Presentamos en esta sección nuestro primer algoritmo tabular para calcular el conjunto de todos los árboles de dependencia para una oración de entrada que tiene la propiedad de división de cabeza,modelo factorizado bajo el arco. Recuerde que taidenotasunárbolconraíz,ytL;aiandtU;aiasonlosárbolesinferiorysuperiordeai.Lospasosdelosalgoritmosespecificadosmediantereglasdededucciónsobreelementos,siguiendo el enfoque de Shieberetal.(1995).5.1Idea básicaNuestro algoritmoconstruyeárbolespaso a paso,adjuntando un árbol tah0 como dependiente de una mano de árbol creando la nueva dependencia ah!ah0.Computacionalmente,el peor caso para esta operación es cuando ambos tahandtah0 tienen un espacio;entonces,para cada árbol necesitamos llevar un registro de los cuatro límites,junto con la posición de la cabeza,como hecho por Gómez-Rodr´ıguezetal.(2011).Sin embargo,si estamos interesados ​​en analizar árboles que satisfagan la propiedad de división de cabeza,podemosevitarrepresentarunárbolconungapmedianteunelementoúnico.En cambio,seguimoslaideageneralde(cid:144)2para análisis proyectivo,y usar diferentes elementos para los árboles superior e inferior del árbol fuente. Cuando necesitamos adjuntar tah0 como un superior dependiente de tah,definido sin(cid:144)3.2,Realizamos dos pasos consecutivos. Primero,weattachtL;ah0totU;ah,resultanteenunanuevaárbolintermedia1.Comosegundopaso,weattachtU;ah0tot1,resultandoenunnuevoárbol2queesU;ahwithtah0adjuntocomosuperdependiente,como se desee. Ambos pasos se muestran en la Figura 5;Aquí presentamos la convención de indicar la agrupación de árboles a través de una línea discontinua. Se puede utilizar un procedimiento asimétrico para adjuntar tah0 como un totL inferior dependiente.;ah.TheahtU;ahah0tL;ah0+t1(a)t1ah0ahah0tU;ah0+t2(b)Figura 5:Adjunto en dos pasos deah0attU;ah:(a)adjunto-mentoftL;ah0;(b)adjuntooftU;ah0.la corrección del enfoque en dos pasos se desprende de las propiedades P1 y P3 en(cid:144)3.2.Por propiedadP2in(cid:144)3.2,enambospasossobrelascabezasléxicassahandah0sepuedeleerdesdeloslímitesdelosárbolesinvolucrados. Luego,estospasospuedenimplementarsede maneramáseficientequeelmétodona¨ıvequejuntatah0totahenunsolopaso.Seproporcionaráunanálisiscomputacionalmásdetalladoen(cid:144)5.7.Para simplificar la presentación,fueron estrictos en el uso de la división de cabezas en árboles con un hueco y analizar árboles sin huecos con el método ingenuo;esto no afecta la complejidad computacional. 5.2 Tipos de elementos Distinguimos cinco tipos diferentes de elementos,indicado por el subíndice X2f0;l;Ud.;=L;=Y,como se describe a continuación.(cid:15)SiXD0,tenemospDqD(cid:0)andyd.ah/isspecifiedasin(cid:144)4.(cid:15)SiXDL,Usamos el elemento para representar algún árbol inferior.;q¤(cid:0)andh2fiC1;qg.(cid:15)SiXDU,Usamos el elemento para representar algún árbol superior.;q¤(cid:0)andh2fj;pC1g.(cid:15)SiXD=LoXD=U,Usamos el elemento para representar algún paso intermedio en el proceso de análisis.,en el que solo el árbol superior inferior de algún dependiente ha sido recopilado por la cabeza,y todavía nos falta la parte superior(=U)orthelower(=L)árbol.

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

272

Wefurtherspecializesymbol=Ubywriting=U<(=U>)para indicar que el árbol superior que falta debe tener su cabeza hacia la izquierda(bien)ofitsgap.Wealsouse=Lcon un significado similar. 5.3 Elemento en forma normal Podría suceder que nuestro algoritmo natural produzca elementos de tipo 0 que no satisfagan la condición de forma normal analizada en(cid:144)4.Para evitar este problema,Suponemos que cada elemento de tipo 0 producido por el algoritmo se convierte en un elemento de formato normal equivalente.,por medio de las siguientes reglas:Œi;j;(cid:0);(cid:0);i(cid:141)0Œi(cid:0)1;j;(cid:0);(cid:0);i(cid:141)0(1)Œi;j;(cid:0);(cid:0);jC1(cid:141)0Œi;jC1;(cid:0);(cid:0);jC1(cid:141)0(2)5.4Elementos de tipo 0 Comenzamos con reglas de deducción que producen elementos de tipo 0. Como ya se mencionó,En este caso, no aplicamos la técnica de división de cabezas. La siguiente regla crea árboles con un solo nodo.,representando a la cabeza,y sin dependientes. La regla es en realidad un axioma(no hay antecedentes)yladeclaracioni2Œ1;norte(cid:141)isasidecondition.Œi(cid:0)1;i;(cid:0);(cid:0);i(cid:141)0˚i2Œ1;norte(cid:141)(3)La siguiente regla toma un árbol con cabeza en h 0 y lo hace dependiente de una nueva cabeza ah. Esta regla implementa lo que se ha llamado el “truco del gancho”. La primera condición lateral obliga a que el árbol con cabeza en h 0 haya reunido a todos sus dependientes.,como se discute(cid:144)4.La condición del segundo lado obliga a que no se cree ningún ciclo. También escribimos ah!ah0 para indicar que se crea una nueva dependencia en el bosque analizador.Œi;j;(cid:0);(cid:0);h0(cid:141)0Œi;j;(cid:0);(cid:0);h(cid:141)08<:h02ŒiC1;j(cid:141)h62ŒiC1;j(cid:141)ah!ah0(4)Thenexttworulescombinegap-freedependentsofthesameheadah.Œi;k;(cid:0);(cid:0);h(cid:141)0Œk;j;(cid:0);(cid:0);h(cid:141)0Œi;j;(cid:0);(cid:0);h(cid:141)0(5)Œi;h;(cid:0);(cid:0);h(cid:141)0Œh(cid:0)1;j;(cid:0);(cid:0);h(cid:141)0Œi;j;(cid:0);(cid:0);h(cid:141)0(6)Weneedthespecialcasein(6)todealwiththecon-catenationoftwoitemsthatsharetheheadahattheconcatenationpoint.Observetheapparentmismatchinstep(6)betweenindexhinthefirstantecedentandindexh(cid:0)1inthesecondantecedent.Thisisbecauseinournormalform,boththefirstandthesecondantecedenthavealreadyincorporatedacopyofthesharedheadah.Thenexttworulescollectadependentofahthatwrapsaroundthedependentsthathavealreadybeencollected.Asalreadydiscussed,thisoperationisperformedbytwosuccessivesteps:Wefirstcollectthelowertreeandthentheuppertree.Wepresentthecaseinwhichthesharedheadofthetwotreesisplacedattheleftofthegap.Thecaseinwhichtheheadisplacedattherightofthegapissymmetric.Œi0;j0;(cid:0);(cid:0);h(cid:141)0Œi;i0;j0;j;iC1(cid:141)LŒi;j;(cid:0);(cid:0);h(cid:141)=U<(cid:26)h62ŒiC1;i0(cid:141)[Œj0C1;j(cid:141)(7)Œi0;j0;(cid:0);(cid:0);h(cid:141)=U<Œi;i0C1;j0;j;i0C1(cid:141)UŒi;j;(cid:0);(cid:0);h(cid:141)08<:h62ŒiC1;i0C1(cid:141)[Œj0C1;j(cid:141)ah!ai0C1(8)Again,thereisanoverlapinrule(8)betweenthetwoantecedents,duetothefactthatbothitemshavealreadyincorporatedcopiesofthesamehead.5.5ItemsofTypeUWenowconsiderthedeductionrulesthatareneededtoprocessuppertrees.Throughoutthissubsectionweassumethattheheadoftheuppertreeisplacedattheleftofthegap.Theothercaseissymmetric.Thenextrulecreatesanuppertreewithasinglenode,rep-resentingitshead,andnodependents.Weconstructanitemforallpossiblerightgapboundariesj.Œi(cid:0)1;i;j;j;i(cid:141)U(cid:26)i2Œ1;n(cid:141)j2ŒiC1;n(cid:141)(9)Thenextruleaddstoanuppertreeagroupofnewdependentsthatdonothaveanygap.Wepresentthecaseinwhichthenewdependentsareplacedattheleftofthegapoftheuppertree.Œi;i0;(cid:0);(cid:0);j(cid:141)0Œi0;j;p;q;j(cid:141)UŒi;j;p;q;j(cid:141)U(10) 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 2 2 6 1 5 6 6 6 6 5 / / t yo a C _ a _ 0 0 2 2 6 pag d . F b y gramo tu mi s t t oh norte 0 7 S mi pag mi metro b mi r 2 0 2 3 273 Las siguientes reglas recopilan un nuevo dependiente que envuelve el árbol superior.,esta operación se realiza mediante dos pasos sucesivos:Primero recolectamos el árbol inferior,luegoelárbolsuperior.Presentamoselcasoenelquelacabezacomúndelosdosárbolessecolocaalaizquierdadelhueco.Œi0;j;pag;q0;j(cid:141)interfaz de usuario;i0;q0;q;iC1(cid:141)LŒi;j;pag;q;j(cid:141)=U<(11)Œi0;j;p;q0;j(cid:141)=U<Œi;i0C1;q0;q;i0C1(cid:141)UŒi;j;p;q;j(cid:141)U˚aj!ai0C1(12)5.6ItemsofTypeLSofarwehavealwaysexpandeditems(type0orU)attheirexternalboundaries.Whendealingwithlowertrees,wehavetoreversethisstrategyandexpanditems(typeL)attheirinternalboundaries.Apartfromthisdifference,thedeductionrulesbelowareentirelysymmetrictothosein(cid:144)5.5.Again,weas-sumethattheheadofthelowertreeisplacedattheleftofthegap,theothercasebeingsymmetric.Ourfirstrulecreatesalowertreewithasinglenode,representingitshead.Weblindlyguesstherightboundaryofthegapofsuchatree.Œi(cid:0)1;i;j;j;i(cid:141)L(cid:26)i2Œ1;n(cid:141)j2ŒiC1;n(cid:141)(13)Thenextruleaddstoalowertreeagroupofnewdependentsthatdonothaveanygap.Wepresentthecaseinwhichthenewdependentsareplacedattheleftofthegapofthelowertree.Œj0;j;(cid:0);(cid:0);iC1(cid:141)0Œi;j0;p;q;iC1(cid:141)LŒi;j;p;q;iC1(cid:141)L(14)Thenexttworulescollectanewdependentwithagapandembeditwithinthegapofourlowertree,creatinganewdependency.Again,thisoperationisperformedbytwosuccessivesteps,andwepresentthecaseinwhichthecommonheadoftheloweranduppertreesthatareembeddedisplacedattheleftofthegap,theothercasebeingsymmetric.Œi;j0;p0;q;iC1(cid:141)LŒj0;j;p;p0;j(cid:141)UŒi;j;p;q;iC1(cid:141)=L<(15)Œi;j0;p0;q;iC1(cid:141)=L<Œj0(cid:0)1;j;p;p0;j0(cid:141)LŒi;j;p;q;iC1(cid:141)L˚aiC1!aj0(16)ahad1ad2ad3ad4ad5tU;ahtLL;ahtLR;ahFigure6:Nodeahsatisfiesboththe1-inheritandhead-splitconditions.Accordingly,treetahcanbesplitintothreefragmentstU;ah,tLL;ahandtLR;ah.5.7RuntimeThealgorithmrunsintimeO.n6/,¿Dónde está la longitud de la oración de entrada? El peor caso se debe a reglas de deducción que combinan dos elementos.,cada uno de los cuales representa árboles con un espacio vacío. Por ejemplo,regla(11)involucra seis índices libres que van sobre Œ1;norte(cid:141),y por lo tanto se podría crear una instancia en 6/muchas veces. Si la propiedad dividida en cabeza no mantiene,la vinculación de un dependiente en un paso resulta en el tiempo O.n7/, como se observa por ejemplo en Gómez-Rodr´ıguezetal.(2011).6Análisis de árboles divididos en cabeza de herencia 1 En esta sección especializamos el algoritmo de análisis de(cid:144)5a la nueva,algoritmo más eficiente para una clase de árboles restringida. 6.11-Heredar árboles divididos en cabezaPitleretal.(2012)introducir una restricción en árboles de dependencia bien anidados con un grado de bloque como máximo de 2. Un árbol satisface la propiedad de herencia 1 si,foreverynodeahintwithbd.ah;t/D2,hayunadependenciamáximaah!anuncio(cid:3)talthatgap.tŒad(cid:3)(cid:141)/contienegap.tŒah(cid:141)/.Informalmente,esto significa quetyd.tŒad(cid:3)(cid:141)/brecha 'cruzada'.tŒah(cid:141)/,y decimos eso(cid:3)"hereda" la brecha. En esta sección investigamos el análisis de árboles divididos en cabeza que también tienen la propiedad de herencia 1. El ejemplo 4, Figura 6, muestra un nodo adelante junto con los sadi dependientes.,satisfaciendo la condición de división de cabeza. Sólo un poquito tiene su rendimiento cruzando la brecha.tah/. Por lo tanto, también satisface la condición de herencia 1.(cid:3)6.2Idea básica Permita que sea algún árbol que satisfaga tanto la propiedad de división de cabeza como la propiedad de herencia de 1. Supongamos que el nodo dependiente está muerto(cid:3)que hereda la brecha de su lugar dentro de U;Ah. Esto significa que,para cada 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 2 2 6 1 5 6 6 6 6 5 / / t yo a C _ a _ 0 0 2 2 6 pag d . F b y gramo tu mi s t t oh norte 0 7 S mi pag mi metro b mi r 2 0 2 3 274 dependenciaah!adintL;ah,maíz(cid:141)/nocrossovergap.tL;ah/.Entonces podemos dividirnos aún másL;ahintodosarboles,ambos con raíz. A estos dos árboles los llamamos el árbol inferior izquierdo,escritotLL;ah,y el árbol inferior derecho,escritotLR;ah;ver de nuevoFigura 6.ElbasicidioabetrasuralgoritmistosedivideentresárbolesdedependenciaU;ah,tLL;ahandtLR;ah,todos compartiendo la misma raíz. Esto significa que tah puede unirse a un árbol existente a través de tres pasos sucesivos,cada uno procesa uno de los tres árboles anteriores. La corrección de este procedimiento se deriva de una extensión directa de las propiedades P1 y P3 de(cid:144)3.2,indicando que el árbol se fragmenta;ah,tLL;ahandtLR;puedo ser representado y procesado uno independientemente de los demás,y combinarse libremente si sus rendimientos satisfacen ciertas condiciones.(cid:3)se coloca dentro de L;ah,presentamos los árboles superior izquierdo y superior derecho,escritotUL;ahandtUR;ah,y aplicar una idea similar. 6.3 Tipos de elementos al procesar un archivo adjunto,el orden en el que el algoritmo ensambla los tres fragmentos de árbol definidos en(cid:144)6.2no siempre es el mismo. Tal orden se elige en función de dónde está el jefe y el dependiente.(cid:3)heredandoelespaciosecolocadodentrodelosárbolesinvolucrados.Comoconsecuencia,Enelgoritmouralnecesitamosrepresentarvariosestadosdeanálisisintermedios.Ademásdelostiposdeelementosde(cid:144)5.2,Por lo tanto, necesitamos tipos adicionales. La especificación de estos nuevos tipos de elementos es bastante técnica.,y, por lo tanto, se retrasa hasta que introduzcamos las reglas de deducción relevantes. 6.4 Elementos de tipo 0 Comenzamos con las reglas de deducción para el análisis de LL de árbol;ahandtLR;ah;árbolestUL;ahandtUR;Ahcanbetratadosimétricamente.TheyieldsoftLL;ahandtLR;Tengo la forma especificada en(cid:144)4paraelcasopDqD(cid:0).Por lo tanto, podemos usar elementos de tipo 0 para analizar estos árboles.,adoptando una estrategia similar a la del uno en(cid:144)5.4.La principal diferencia es que,cuandoatreetah0conagapiseadjuntacomodependientedelacabezaah,usamos tres pasos consecutivos,cadaprocesamientocomounúnicofragmentodeah0.Asumimosquedebajodequetah0sepuededividirenárbolU;ah0,tLL;ah0andtLR;Ah0, el otro caso se puede tratar de manera similar.(3),(4)y(5)de(cid:144)5.4.sinceinad(cid:3)ah „ƒ‚…(cid:27)1"ƒ...(cid:27)2"ƒ...(cid:27)3"ƒ...(cid:27)4un poco(cid:3)tú;anuncio(cid:3)tLL;anuncio(cid:3)tLR;anuncio(cid:3)Figura 7:ÁrbolU;ahisdescompuestointotad(cid:3)y subárboles que cubren subcadenas(cid:27)i,i2Œ1;4(cid:141).Arboleda(cid:3)se descompone a su vez en tres fragmentos(árbolestLL;anuncio(cid:3),tLR;anuncio(cid:3),ytU;anuncio(cid:3)en este ejemplo).thetreeestll;ahandtLR;Ah, la cabeza nunca se coloca en medio del campo.,regla(6)no es necesario ahora y se puede descartar con seguridad.(7),adjuntando un árbol más bajo,necesita ser reemplazado por dos nuevas reglas,procesando un árbol de abajo a la izquierda y otro de abajo a la derecha. Suponemos aquí que la cabeza común de estos árboles está ubicada en el límite izquierdo del árbol de abajo a la izquierda;dejamos fuera el caso simétrico.Œi;i0;(cid:0);(cid:0);iC1(cid:141)0Œi0;j;(cid:0);(cid:0);h(cid:141)0Œi;j;(cid:0);(cid:0);h(cid:141)=LR<˚h62ŒiC1;i0(cid:141)(17)Œj0;j;(cid:0);(cid:0);iC1(cid:141)0Œi;j0;(cid:0);(cid:0);h(cid:141)=LR<Œi;j;(cid:0);(cid:0);h(cid:141)=U<˚h62Œj0C1;j(cid:141)(18)Thefirstantecedentin(17)encodesalower-lefttreewithitsheadattheleftboundary.Theconsequentitemhasthenthenewtype=LR<,meaningthatalower-righttreeismissingthatmusthaveitsheadattheleft.Thefirstantecedentin(18)providesthemissinglower-righttree,havingthesameheadasthealreadyincorporatedlower-lefttree.Aftertheserulesareapplied,rule(8)from(cid:144)5.4canbeappliedtotheconsequentitemof(18).Thiscompletestheattachmentofa‘wrapping’dependentofah,withtheincorporationofthemissinguppertreeandwiththeconstructionofthenewdependency.6.5ItemsofTypeUWenowassumethatnodead(cid:3)isrealizedwithintU;ah,sothattahcanbesplitintotreestU;ah,tLL;ahandtLR;ah.WeprovidedeductionrulestoparseoftU;ah;thisisthemostinvolvedpartofthealgorithm.Incasead(cid:3)isrealizedwithintL;ah,tahmustbesplitintotL;ah,tUL;ahandtUR;ah,andasymmetricalstrategycanbeappliedtoparsetL;ah. 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 2 2 6 1 5 6 6 6 6 5 / / t yo a C _ a _ 0 0 2 2 6 pag d . F b y gramo tu mi s t t oh norte 0 7 S mi pag mi metro b mi r 2 0 2 3 275 anuncio(cid:3)ah(cid:27)1(cid:27)2(cid:27)3(cid:27)4tú;anuncio(cid:3)tLL;anuncio(cid:3)tLR;anuncio(cid:3)regla(19)regla(20)Figura 8:Descomposición de U;ahasinFigura7,conaplicacióndereglasresaltadas(19)y(20).Westartbyobservingthatyd.tad(cid:3)/splitsyd.tU;ah/intoatmostfoursubstrings(cid:27)i;ver Figura 7.2 Debido a la propiedad bien anidada,dentro de la calle U;aheachdependientedeaotherthanad(cid:3)tiene un campo que está completamente ubicado dentro de uno de los(cid:27)son subcadenas. Esto significa que cada subcadena(cid:27)Se puede analizar independientemente de las otras subcadenas. Como primer paso en el proceso de análisis de U;ah,analizamos cada subcadena(cid:27)i.Hacemos esto siguiendo la estrategia de análisis especificada en(cid:144)6.4.Como segundo paso,asumimos que cada uno de los tres fragmentos resultantes de la descomposición del árbol(cid:3)ya ha sido analizado;ver nuevamente la Figura 7. Luego 'fusionamos' estos tres fragmentos y los árboles para los segmentos(cid:27)Estoy en un árbol analizador completo que representa tU;ah.Esto se describe en detalle a continuación. Suponemos que su lugar está a la izquierda de la brecha en U.;ah(el caso correcto siendo simétrico)ywedistinguecuatrocasos,dependiendo de las dos maneras en que tad(cid:3)canbesplit,y las dos posiciones laterales de la cabeza(cid:3)conrespetogap.tad(cid:3)/.Caso 1 Asumimos eso(cid:3)canbesplitintotreestU;anuncio(cid:3),tLL;anuncio(cid:3),tLR;anuncio(cid:3),y la cabeza(cid:3)está colocado a la izquierda del espacio.tad(cid:3)/;ver de nuevoFigura 7.Regla(19)debajocombinestLL;anuncio(cid:3)con un segmento disperso(cid:27)2,que tiene su cabeza y su lugar en su límite derecho;ver Figura 8 para una representación gráfica de una regla(19).El resultado es un elemento del nuevo tipo HH. Este elemento se usa incorrectamente para representar un fragmento de árbol intermedio con raíz de bloque de grado 1, donde tanto el límite izquierdo como el derecho son cabezas.;dependencia2Segúnnuestradefinicióndem.tah/in(cid:144)3.2,(cid:27)3es siempre la cadena vacía. Sin embargo,aquí tratamos la formulación general del problema para poder reclamar en(cid:144)8que nuestro algoritmo oral puede adaptarse directamente para analizar algunas subclases de gramáticas contiguas a árboles flexicalizadas.(cid:3)(cid:27)1(cid:27)2(cid:27)3(cid:27)4tú;anuncio(cid:3)tLL;anuncio(cid:3)tLR;anuncio(cid:3)regla(22)regla(23)Figura 9:Descomposición de U;ahasinFigura7,conaplicacióndereglasresaltadas(22)y(23).entre estas cabezas se construirá más tarde.Œi;i0;(cid:0);(cid:0);iC1(cid:141)0Œi0;j;(cid:0);(cid:0);j(cid:141)0Œi;j;(cid:0);(cid:0);j(cid:141)S.S(19)Regla(20)combinatU;anuncio(cid:3)conatype0itemrep-resentingtLR;anuncio(cid:3);Vea nuevamente la Figura 8. Tenga en cuenta que esta operación combinada expande un árbol superior para ajustarse a los límites internos.,algo que no era posible con las reglas especificadas en(cid:144)5.5.Œi;j;p0;q;j(cid:141)uŒp;p0;(cid:0);(cid:0);j(cid:141)0Œi;j;pag;q;j(cid:141)Ud.(20)Finalmente,combinamos las consecuencias de(19)y(20),y procesar la dependencia que quedó pendiente en el ítem de tipo HH.Œi;j0;pag;q;j0(cid:141)UŒj0(cid:0)1;j;(cid:0);(cid:0);j(cid:141)hoi;j;pag;q;j(cid:141)U˚aj!aj0(21)Después de los pasos anteriores,parsingoftU;ahcanbecompletedbycombiningitemŒi;j;pag;q;j(cid:141)Udesde(21)con elementos de tipo 0 que representan análisis de las subcadenas(cid:27)1,(cid:27)3y(cid:27)4.Caso 2 Asumimos eso(cid:3)canbesplitintotreestU;anuncio(cid:3),tLL;anuncio(cid:3),tLR;anuncio(cid:3),y la cabeza(cid:3)se coloca a la derecha del espacio.tad(cid:3)/,como se muestra en la Figura 9.Regla(22)abajo,representado gráficamente en la Figura 9, combineestU;anuncio(cid:3)con un tipo de elemento que representa-ingtLL;anuncio(cid:3).Esto se puede ver como la versión simétrica de la regla(20)DelCaso1,expandiendounárbolsuperiorparaunoslímitesinternos.Œi;j0;pag;q;pC1(cid:141)UŒj0;j;(cid:0);(cid:0);pC1(cid:141)0Œi;j;pag;q;pC1(cid:141)Ud.(22) 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 2 2 6 1 5 6 6 6 6 5 / / t yo a C _ a _ 0 0 2 2 6 pag d . F b y gramo tu mi s t t oh norte 0 7 S mi pag mi metro b mi r 2 0 2 3 276 ÁrabeChecoDanésHolandésPortuguésSuecoNúmerodeárboles1,46072,7035,19013,3499,07111,042WN2O.n7/1,45899.9r,32199.5%5,17599.7,89696.6%8,65095.4,95599.2 %Clases consideradas en este documentoWN2+HSO.n6/1,45799.8% 72,18299.3%5,17499.7,77495.7%8,64895.3,95199.2%WN2+HS+1IO.n5/1,45799.8r,18299.3%5,17499.7,77495.7%8,64895.3, 95199,2%Clases consideradas porPitleretal.(2012)WN2+1IO.n6/1,45899.9r,32199.5%5,17599.7,89696.6%8,65095.4,95599.2%WN2+0IO.n5/1,39495.5p,69597.2%4,98596.1, 06890,4%8,48193,5,78797,7%ProyectivoO.n3/1,29788,8U,87276,8%4,37984,4%8,48463,6%7,35381,1%9,96390,2%Tabla1:Cobertura de varias clases de árboles de dependencia en los conjuntos de capacitación utilizados en la tarea compartida CoNLL-X(WN2=bien anidado,grado de bloque(cid:20)2;HS=cabeza dividida;1I=1-heredar;0I=0-heredar,'mente vacía')Próximo,combinamoselresultadode(22)conaparseforsubstring(cid:27)2.Theresultisanitemofthenewtype=LR>.Thisitemisusedtorepresentanintermediatetreefragmentthatismissingalower-righttreewithitsheadattheright.Inthisfragment,dos cabezas quedan pendientes,y eventualmente se establecerá una relación de dependencia entre ellos.Œi;j0;pag;q;pC1(cid:141)UŒj0;j;(cid:0);(cid:0);j(cid:141)0Œi;j;pag;q;j(cid:141)=LR>(23)La siguiente regla combina el elemento consecuente de(23)conatreetLR;anuncio(cid:3)tener la cabeza en el límite derecho,andprocessesthedependencythatwasleftpendinginthe=LR>item.Œi;j;p0;q;j(cid:141)=LR>Œp;p0C1;(cid:0);(cid:0);p0C1(cid:141)0Œi;j;pag;q;j(cid:141)U˚aj!ap0C1(24)Después de las reglas,parsingoftU;ah continúa combinando el elemento consecuenteŒi;j;pag;q;j(cid:141)Ufromrule(24)con elementos que representan análisis de las subcadenas(cid:27)1,(cid:27)3y(cid:27)4.Casos 3 y 4 Discutimos informalmente los casos en los que(cid:3)canbesplitintotreestL;anuncio(cid:3),tul;anuncio(cid:3),debería;anuncio(cid:3),para ambas posiciones de la cabeza(cid:3)withre-specttogap.tad(cid:3)/.En ambos casos podemos adoptar una estrategia similar a la del Caso 2. Primero expandimos L;anuncio(cid:3)externamente,en el lado opuesto a la cabeza(cid:3),conatreefragmenttUL;anuncio(cid:3)ortUR;anuncio(cid:3),de manera similar(22)delCaso2.Estoresultaenunnuevofragmentot1.Siguiente,fusionamos1conaparsepara(cid:27)2conteniendolacabeza,de manera similar(23)del Caso 2. Esto resulta en un nuevo fragmento t2 donde una relación de dependencia que involucra a las cabezas es triste.(cid:3)andahis queda pendiente.Finalmente,fusionamos2conunárbolfaltanteUL;anuncio(cid:3)ortUR;anuncio(cid:3),y procesar la dependencia pendiente,de manera similar(24).Se debe contrastar esta estrategia con la estrategia alternativa adoptada en el Caso 1, donde el fragmento de AD(cid:3)tener un bloque de grado 2 no se puede fusionar con un fragmento para el segmento que contiene la cabeza ah((cid:27)2en caso1),debido a un fragmento intermedio de ad(cid:3)con grado de bloque 1(tLL;anuncio(cid:3)en caso1).Finalmente,si no hay ningún muerto(cid:3)intu;ahthatinheritsthegapofah,wecansplittU;ahintotwodependencytrees,como lo hemos hechofortl;es(cid:144)6.2,y analizar los dos fragmentos usando la estrategia de(cid:144)6.4.6.6Tiempo de ejecución Nuestro algoritmo se ejecuta en tiempo O.n5/, donde es la longitud de la oración de entrada. La razón de su mejora con respecto al resultado O.n6/(cid:144)5es que ya no tenemos reglas de deducción donde ambos antecedentes representan árboles con un espacio. En el nuevo algoritmo,el peor de los casos se debe a reglas en las que solo un antecedente tiene un vacío. Esto lleva a reglas que involucran un máximo de cinco índices.,que abarca más de 1;norte(cid:141).Estas reglas se pueden crear en O.n5/ways..

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

277

En conexión con la propiedad 1-heredada,esto incluso aumenta a dos órdenes de magnitud.,como ya se indicó en(cid:144)2,esta mejora se paga con una pérdida de cobertura;por ejemplo,Los árboles de la forma que se muestran en la Figura 3 ya no se pueden analizar. 7.1 Evaluación cuantitativa para evaluar la pérdida empírica de cobertura en la que incurre la restricción de los árboles divididos en cabezas,evaluamos la cobertura de varias clases de árboles de dependencia en conjuntos de datos estándar. Siguiendo a Pitleretal.(2012),Se presentaron en la Tabla 1 las cifras para los conjuntos de capacitación de seis idiomas utilizados en el análisis de dependencia de tareas compartidas de CoNLL-X.(BuchholzandMarsi,2006).Como podemos ver,la clase O.n6/de árboles divididos en cabeza tiene solo una cobertura ligeramente inferior en estos datos que la clase de referencia de árboles de dependencia bien anidados con grado de bloque como máximo 2. Las pérdidas son de hasta 0,2 puntos porcentuales en cinco de los seis idiomas,y 0,9 puntos en los datos holandeses. Nuestro árbol aún más restringido O.n5/clase de 1-hereditario-dividido tiene la misma cobertura que nuestro O.n6/clase,lo cual es esperado dados los resultados de Pitleretal.(2012):Sus árboles de herencia O.n6/clase de 1 tienen exactamente la misma cobertura que la línea base.(y por lo tanto más cobertura que nuestra O.n6/clase).Curiosamente,su clase O.n5/de árboles de “mentalidad de brechas” tiene una cobertura significativamente menor que nuestra clase O.n5/. Concluimos que nuestra clase parece lograr un buen equilibrio entre la expresividad y la complejidad del análisis. 7.2 Evaluación cualitativa Si bien la motivación original detrás de la introducción de la propiedad de división de cabeza era mejorar la complejidad del análisis,Esinteresantediscutirtambiénlarelevancialingüísticadeestapropiedad.Unaprimerainspeccióndelasestructurasqueviolanlapropiedaddedivisióndecabezasrevelóquemuchasviolacionesdesaparecensiunoignoralosespacioscausadosporlapuntuación.Algunasdecisionessobrequénodosdebenfuncionarcomocabezasdelossímbolosdepuntuaciónconducenamásespaciosqueotros.Paracuantificarlasimplicacionesdeesto,Se calculó la cobertura de la clase de árboles divididos en cabeza en conjuntos de datos donde eliminamos toda la puntuación por primera vez. Los resultados se dan en la Tabla 2. Nos restringimos a los bancos de árboles de dependencia venativos utilizados en la tarea compartida CoNLL-X.,ignorando los bancos de árboles que se han convertido a partir de representaciones de estructuras de frases. Árabe checo danés esloveno turco con 1139122 sin 146002 Tabla 2:Violaciones contra la propiedad dividida(en relación con la clase de árboles bien anidados con grado de bloque(cid:20)2)con y sin puntuación. Vemos que cuando eliminamos la puntuación de las oraciones,elnúmerodeviolacionescontralapropiedaddivididadisminuyecomomáximo.Paradanésyesloveno,eliminar la puntuación incluso tiene el efecto de que todos los árboles de dependencia bien anidados con un grado de bloque como máximo de 2 se dividen.,El número absoluto de violaciones es extremadamente pequeño, excepto en el caso de la República Checa.,donde tenemos 139 violaciones con y 46 sin puntuación. Una inspección más cercana de las oraciones checas revela que muchas de estas presentan coordinaciones bastante complejas.,de las 46 violaciones en los datos libres de puntuación,Sólo quedan 9 cuando se ignora a los que tienen coordinación.,No hemos podido identificar ningún patrón claro. 8 Observaciones finales En este artículo hemos ampliado las técnicas de división de cabezas.,desarrollado originalmente para analizar árboles de dependencia proyectiva,a dos subclases de árboles de dependencia bien anidados con un grado de bloque como máximo 2. Hemos mejorado el tiempo de ejecución sencillo y simpótico de dos algoritmos existentes,sinpérdidasignificativaencobertura.Conelmismoobjetivodemejorarlaeficienciadeanálisisparasubclasesdeárbolesnoproyectivos,en un trabajo muy reciente Pitleretal.(2013)han propuesto un algoritmo O.n4/time para una subclase de árboles no proyectivos que no están bien anidados,usando un enfoque que es ortogonal al que hemos explorado aquí. Aparte del análisis de dependencia,Nuestros resultados también tienen implicaciones formalismos de estructuras de frases ligeramente sensibles al contexto.,algoritmo real(cid:144)5puede adaptarse a subclase de parsea flexicalizado gramáticas contiguas a árboles,mejorandoelresultadoporEisnerySatta(2000)deO.n7/aO.n6/.Similarmente,el algoritmo de(cid:144)6se puede adaptar a una versión analizada alexicalizada de las gramáticas contiguas a árboles investigadas por Satta y Schuler(1998),mejorandoana¨ıveO.n7/algorithmtoO.n5/.

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
2
2
6
1
5
6
6
6
6
5

/

/
t

yo

a
C
_
a
_
0
0
2
2
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

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

278

ReferenciasManuelBodirsky,marcokuhlmann,y Mathias M¨ohl.2005. Dibujos bien anidados como modelos de estructura sintáctica. En las actas de la décima conferencia sobre gramática formal(FG)y Noveno Encuentro Sobre Matemáticas Del Lenguaje(MOL),páginas 195–203, Edimburgo,Reino Unido.SabineBuchholzandErwinMarsi.2006.CoNLL-Xsharedtaskonmultilingualdependencyparsing.En las actuaciones de la Décima Conferencia sobre Aprendizaje Computacional de Lenguajes Naturales(CONLL),páginas 149–164,Nueva York,EE.UU. Xavier Carreras. 2007. Experimentos con un analizador de dependencia proyectiva de orden superior. En las actuaciones de la sesión de tareas compartidas de EMNLP-CoNLL 2007, páginas 957–961, Praga,República Checa. Joan Chen-Main y Aravind K. Joshi. 2010. Inevitable mal anidado en el lenguaje natural y la adecuación de las estructuras de dependencia inducida por el MCTAG local de árboles. En las actuaciones de la Décima Conferencia Internacional sobre gramáticas contiguas de árboles y formalismos relacionados(ETIQUETA+),NuevoHaven,EE.UU. Jason Eisner y Giorgio Satta. 1999. Análisis eficiente de gramáticas libres de contexto biliéxico y gramáticas de autómatas principales. En las actuaciones de la 37ª reunión anual de la Asociación de Lingüística Computacional(LCA),páginas 457–464,Parque Universitario,Maryland,EE.UU. Jason Eisner y Giorgio Satta. 2000. Un algoritmo de análisis más rápido para gramáticas contiguas a árboles lexicalizadas. En las actuaciones del quinto taller sobre gramáticas contiguas a árboles y formalismos relacionados(ETIQUETA+),páginas 14–19,París,Francia.JasonEisner.1997.Gramáticas biléxicas y analizador probabilístico de tiempo cúbico.En las actuaciones del Quinto Taller Internacional sobre Tecnologías de Análisis(IWPT),páginas 54–65, Cambridge,MAMÁ,Estados Unidos.CarlosG´omez-Rodr´ıguez,juancarroll,yDavidJ.Weir.2011.Esquemas de análisis de dependencia y análisis de dependencia ligeramente no proyectivo.Lingüística computacional,37(3):541–586.AravindK.JoshiandYvesSchabes.1997.Gramáticas contiguas a árboles.En GrzegorzRozenbergyArtoSalomaa,editores,Manual De Idiomas Formales,volumen 3, páginas 69–123. Springer. Terry Koo y Michael Collins. 2010. Analizadores de dependencia de tercer orden eficientes. En las actuaciones de la 48.ª reunión anual de la Asociación de Lingüística Computacional(LCA),páginas 1–11, Upsala,Suecia. Marco Kuhlmann y Joakim Nivre. 2006. Estructuras de dependencia levemente no proyectivas. En las actas de la XXI Conferencia Internacional sobre Lingüística Computacional(COLECCIONAR)y 44ª Reunión Anual de la Asociación de Lingüística Computacional(LCA)Conferencia PrincipalPosterSessions,páginas 507–514, Sídney,Australia.WolfgangMaierandTimmLichte.2011.Caracterización de la discontinuidad en los bancos de árboles constituyentes. En PhilippedeGroote,MarkusHuevo,y Laura Kallmeyer,editores,Gramática Formal. XIV Congreso Internacional,FG2009, Burdeos,Francia,25 y 26 de julio de 2009, artículos seleccionados revisados,volumen 5591 de notas de conferencias sobre ciencias informáticas,páginas 167–182.Springer.RyanMcDonald y Giorgio Satta.2007.Sobre la complejidad del análisis de dependencia basado en datos no proyectivos.En las actuaciones de la Décima Conferencia Internacional sobre Tecnologías de Análisis(IWPT),páginas 121–132, Praga,República Checa.RyanMcDonald,FernandoPereira,KirilRibarov,y JanHajiˇc.2005. Análisis de dependencia no proyectiva utilizando algoritmos de árbol de expansión. En la Conferencia de Tecnología del Lenguaje Humano(HLT)y Conferencia sobre métodos empíricos en el procesamiento del lenguaje natural(EMNLP),páginas 523–530, Vancouver,Canadá.EmilyPitler,SampathKannan,y Mitchell Marcus.2012. Programación dinámica para el análisis de orden superior de árboles de detección de brechas. En las actuaciones de la conferencia conjunta de 2012 sobre métodos empíricos en el procesamiento del lenguaje natural(EMNLP)y Aprendizaje Computacional de Idiomas Naturales(CONLL),páginas 478–488,Isla de Jeju,República De Corea.EmilyPitler,SampathKannan,y Mitchell Marcus.2013.Findingoptimal1-endpoint-crossingtrees.TransactionsoftheAssociationforComputationalLinguistics.GiorgioSattayWilliamSchuler.1998.Restrictionsontreeadjoininglanguages.InProcedingsofthe36thAnnualReunionoftheAssociationforComputationalLinguistics.(LCA)y XVII Congreso Internacional de Lingüística Computacional(COLECCIONAR),páginas 1176–1182, Montreal,Canadá.StuartM.Shieber,YvesSchabes,y Fernando Pereira.1995.Principios e implementación del análisis deductivo. JournalofLogicProgramming,24(1–2):3–36.
Descargar PDF