1.sgsr213 | Thom Hoffman | • Glacé 0

Formalismes sintàctics


Save this PDF as:
 WORD  PNG  TXT  JPG

Tamaño: px
Comenzar la demostración a partir de la página:

Download "Formalismes sintàctics"

Transcripción

1 Formalismes sintàctics Antoni liver PID_

2 Aquesta obra és llicencia sota la següent llicència Creative Commons: Reconeixement - CompartirIgual 3.0 (by-sa): es permet l ús comercial de l obra i de les possibles obres derivades, la distribució de les quals s ha de fer amb una llicència igual a la que regula l obra original.

3 c CC-BY-SA PID_ Formalismes sintàctics Índex Introducció bjectius Gramàtiques lliures de context Analitzadors per a gramàtiques lliures de context Analitzador descendent recursiu L analitzador shift-reduce L analitzador left-corner Analitzadors amb taules auxiliars (Chart parsers) Gramàtica de trets Processament d estructures de trets Les gramàtiques lliures de context probabilístiques Inducció de gramàtiques Analitzadors per a gramàtiques probabilístiques: l algorisme de Viterbi Gramàtiques de dependències Treebanks de dependències de l LTK Resum Bibliografia

4

5 c CC-BY-SA PID_ Formalismes sintàctics Introducció En aquest mòdul estudiarem s formalismes i tècniques computacionals per a poder portar a terme l anàlisi sintàctica d una oració. En mòdul Anàlisi fragmental (chunking) vam veure com es pot fer una anàlisi superficial (o chunking), que ens permetia detectar s constituents principals de l oració, però no la ració entre s constituents. Veurem com podem escriure gramàtiques que ens permetin analitzar oracions i també com podem aprendre a analitzar oracions a partir de corpus analitzats sintàcticament (que es coneixen també amb nom de treebanks). En l exemple següent (programa-8-1.py) observem un programa que defineix una gramàtica senzilla que permet analitzar una oració. import nltk gramatica_senzilla=nltk.parse_cfg(""" -> -> -> V -> -> nen V -> canta """) frase=[, nen, canta ] parser = nltk.chartparser(gramatica_senzilla) arbres = parser.nbest_parse(frase) for arbre in arbres: print arbre arbre.draw() Si executem aquest programa obtenim l anàlisi en mode text i també gràficament (figura 1): ( ( ( ) ( nen)) ( (V canta))) o sempre fer l anàlisi sintàctica d una oració serà tan senzill; poden aparèixer diversos problemes. En l exemple següent intentem analitzar les oracions

6 c CC-BY-SA PID_ Formalismes sintàctics Figura 1. Anàlisi sintàctica següents: nen menja, nen menja un entrepà de formatge i nen menja un entrepà de formatge a casa (programa-8-2.py): #! -*- coding= utf-8 -*- import nltk gramatica_senzilla=nltk.parse_cfg(""" -> SP -> Prep -> SP -> V V V SP V SP Prep -> de a -> un -> nen formatge casa entrepà V -> canta menja """) parser = nltk.chartparser(gramatica_senzilla) frase=[, nen, menja ] arbres = parser.nbest_parse(frase) for arbre in arbres: print arbre arbre.draw() frase=[, nen, menja, un, entrepà, de, formatge ] arbres = parser.nbest_parse(frase) for arbre in arbres: print arbre arbre.draw() frase=[, nen, menja, un, entrepà, de, formatge, a, casa ] arbres = parser.nbest_parse(frase) for arbre in arbres: print arbre arbre.draw() Quan executeu aquest programa aniran apareixent anàlisis per pantalla. Quan aparegui una anàlisi programa s atura fins que tanquem la finestra gràfica.

7 c CC-BY-SA PID_ Formalismes sintàctics A la figura 2 podem veure l anàlisi de la frase nen menja, que no presenta cap problema especial. En canvi, la frase nen menja un entrepà de formatge presenta problema de determinar d on penja sintagma preposicional de formatge. La nostra gramàtica ofereix dues possibilitats, que podem observar a les figures 3 i 4. Figura 2. Anàlisi sintàctica de la frase nen menja Figura 3. Primera anàlisi sintàctica possible de la frase nen menja un entrepà de formatge Figura 4. Segona anàlisi sintàctica possible de la frase nen menja un entrepà de formatge Per una altra banda, la frase nen menja un entrepà de formatge a casa no presenta cap problema, ja que la nostra gramàtica explicita que pot tenir un SP, però no dos (podem observar aquesta anàlisi a la figura 5). Les regles de la gramàtica sovint s anomenen produccions de la gramàtica.

8 c CC-BY-SA PID_ Formalismes sintàctics Figura 5. Anàlisi sintàctica de la frase nen menja un entrepà de formatge a casa

9 c CC-BY-SA PID_ Formalismes sintàctics bjectius Els objectius bàsics que ha d haver aconseguit l estudiant una vegada treballats s continguts d aquest mòdul són s següents: 1. Conèixer s principals formalismes i tècniques computacionals per a fer l anàlisi sintàctica d oracions. 2. Saber crear gramàtiques senzilles amb LTK. 3. Saber què és un treebank i quina utilitat poden tenir en l entrenament de sistemes d anàlisi sintàctica. 4. Comprendre tipus d anàlisi que ofereixen les gramàtiques de dependències.

10

11 c CC-BY-SA PID_ Formalismes sintàctics 1. Gramàtiques lliures de context. El nombre de possibles produccions d una llengua és infinit, ja que no hi ha un límit superior en la llargària d una oració. Tot i això, volem escriure programes que siguin capaços de processar (ja sigui analitzar o generar) totes les possibles oracions ben formades. Per a poder descriure mitjançant gramàtiques de mida finita un conjunt infinit caldrà fer ús de la recursivitat.. Una gramàtica és un sistema formal que especifica quines seqüències de paraules estan ben formades en una llengua i que proporciona una o més estructures de frase per a les seqüències ben formades. Les gramàtiques lliures de context es defineixen per: Un conjunt de símbols inicials que cobreixen les oracions per analitzar. Aquest conjunt pot estar format per un únic símbol, com per exemple oració ; o per més d un símbol, com per exemple oracio_declarativa i oracio_interrogativa. Un conjunt de símbols no terminals que permeten la representació de les categories sintàctiques. Un conjunt de símbols terminals que representen diccionari: paraules d diccionari o morfemes. Un conjunt de regles en què símbol de la part esquerra es reescriu en la seqüència de símbols de la part dreta. Aquestes regles sovint reben nom de regles de reescriptura o produccions de la gramàtica. Vegem un exemple molt senzill de gramàtica lliure de context que és capaç d analitzar l oració noi menja un entrepà. -> -> -> V -> V -> un -> noi entrepà V -> menja

12 c CC-BY-SA PID_ Formalismes sintàctics En aquesta gramàtica conjunt de símbols inicials està compost p símbol. El símbols no terminals són:,,,, V. Els símbols terminals són:, un, nen, entrepà, menja. En programa següent (programa-8-2b.py) demanem a LTK que ens retorni les produccions de la gramàtica anterior: #! -*- coding= utf-8 -*- import nltk gramatica_senzilla=nltk.parse_cfg(""" -> -> -> V -> V -> un -> noi entrepà V -> menja """) for produccio in gramatica_senzilla.productions(): print produccio Si executem aquest programa obtindrem la sortida següent: -> -> -> V -> V -> -> un -> noi -> entrep\xc3\xa0 V -> menja En s exemples anteriors ja hem vist com podem implementar una gramàtica senzilla com aquesta amb LTK. Per a fer més pràctic programa que farem serà modificar-lo perquè llegeixi la gramàtica d un fitxer (que indicarem per la línia d instruccions) i que li donem la frase també per línia d instruccions. Quan cridem programa primer paràmetre serà fitxer de gramàtica i segon la frase per analitzar. El programa queda de la manera següent (programa-8-3.py):

13 c CC-BY-SA PID_ Formalismes sintàctics # -*- coding: utf-8 -*- import sys import nltk print " Indica nom de la gramatica: ", fgramatica=raw_input() print "Escriu la frase per analitzar: ", frase=raw_input() gramatica=nltk.data.load( file:%s % fgramatica) parser=nltk.chartparser(gramatica) arbres=parser.nbest_parse(frase.split()) for arbre in arbres: print arbre arbre.draw() Si nostre fitxer de gramàtica (gramatica1.cfg) conté: -> -> -> V -> V -> un -> noi entrepà V -> menja Ara ja podrem executar programa i indicar-li fitxer de gramàtica i la frase que volem que analitzi. A partir d aquest moment ens podem centrar en la creació de gramàtiques creant s arxius corresponents i cridant al programa que acabem de presentar. Una gramàtica tan senzilla com l anterior no ens permet fer distincions, per exemple, entre verbs transitius i verbs intransitius. Ampliem una mica s símbols terminals per a afegir una mica de lèxic (gramatica2.cfg). -> -> -> V -> V -> un les -> noi entrepà notes professor V -> menja diu

14 c CC-BY-SA PID_ Formalismes sintàctics Aquesta gramàtica pot analitzar tant professor diu les notes com *El professor diu. Aquesta segona oració no és gramatical, ja que verb dir requereix un complement directe. Amb TLK podem escriure fàcilment totes les produccions de la nostra gramàtica. Podem modificar conjunt de símbols no terminals per a especificar la transitivitat i intransitivitat ds verbs. Així, tindrem un símbol VI per als verbs intransitius i un símbol VT per als verbs transitius. Aquí definirem verbs transitius com aquls verbs que exigeixen un complement directe i intransitius s que no n exigeixen. Així, la gramàtica quedarà (gramatica3.cfg). -> -> -> VI -> VI -> VT -> un les -> noi entrepà notes professor VI -> menja VT -> diu Aquesta gramàtica pot analitzar professor diu les notes, però no * professor diu. En canvi pot analitzar tant professor menja un entrepà com professor menja. Ara bé, en la gramàtica anterior no hem expressat la concordança determinantnom i pot analitzar una oració de l estil les noi menja les entrepà. Per a poder solucionar aquest problema haurem de crear encara més símbols no terminals per a poder preveure fenomen de la concordança nomdeterminant. Ho podem observar a la gramàtica següent (gramatica4.cfg). -> -> _m_s _m_s -> _f_s _f_s -> _m_p _m_p -> _f_p _f_p -> VI -> VI -> VT _m_s -> un _f_s -> la una _m_p -> s uns _f_p -> les unes

15 c CC-BY-SA PID_ Formalismes sintàctics _m_s -> noi entrepà professor _f_s -> noia professora _m_p -> nois entrepans professors _f_p -> noies professores VI -> menja mengen VT -> diu diuen Exercici Modifiqueu la gramàtica gramatica4.cfg per a introduir-hi la concordança subjecteverb, de manera que pugui analitzar les oracions: noi menja un entrepà s nois mengen un entrepà però no les oracions * noi mengen un entrepà *s nois menja un entrepà

16 c CC-BY-SA PID_ Formalismes sintàctics 2. Analitzadors per a gramàtiques lliures de context. Una gramàtica és una especificació declarativa que diu quines oracions estan ben construïdes. Des d punt de vista informàtic són unes cadenes de text, no són uns programes que facin cap tasca. Per a poder fer les anàlisis sintàctiques necessitem uns algorismes capaços d interpretar aquestes gramàtiques i arribar a trobar l anàlisi o anàlisis possibles. Aquests algorismes s anomenen analitzadors o parsers. Els analitzadors es poden classificar segons la metodologia que facin servir per a trobar l anàlisi o anàlisis possibles. Una primera classificació es pot establir sobre si la cerca de l anàlisi la fan de dalt a baix o bé de baix a dalt. D aquesta manera poden tenir dos tipus de parsers: Parsers descendents: parteixen d símbol inicial i van cap a baix fins que arriben als símbols terminals. Parsers ascendents: parteixen ds símbols terminals de la frase per analitzar i intenten arribar al símbol inicial.. Un analitzador descendent parteix de la descripció gramatical (la gramàtica) i busca en text d entrada les seqüències que es corresponen amb les permeses per la descripció gramatical. Un analitzador descendent, en canvi, parteix d text i busca a la gramàtica regles que permetin les seqüències presents en text. A part de la direcció bàsica d procés d anàlisi (ascendent o descendent), hi ha altres factors que determinen l estratègia final d un analitzador: Una primera consideració és si l anàlisi es desenvolupa en profunditat (depth-first) o en amplada (breadth-first). En l estratègia en profunditat cada una de les hipòtesis s explora completament abans d iniciar l explotació d una nova hipòtesi. És a dir, es va recorrent l arbre fins que s arriba a l anàlisi o bé ja no es pot continuar. En canvi, l estratègia per amplada manté més d una hipòtesi (de fet totes les possibles) al mateix temps, i avança pas per pas cada una de les hipòtesis. D aquesta manera les hipòtesis o recorreguts per a l arbre d anàlisi es van descartant o bé una o més arriben fins a l anàlisi final.

17 c CC-BY-SA PID_ Formalismes sintàctics Un altre factor que cal tenir en compte és la manera com s analitzadors recorren l entrada. Les opcions bàsiques són d esquerra a dreta, de dreta a esquerra i fins i tot des d mig cap a la dreta i cap a l esquerra alternativament. En aquest apartat veurem quatre tipus d analitzadors: 1) Analitzador descendent recursiu (recursive descent parser): com seu nou indica, es tracta d un analitzador descendent. 2) Shift-reduce parser: és un analitzador ascendent. 3) Left-corner parser: és un analitzador descendent, però que fa servir un filtratge ascendent. Lectures recomanades S han desenvolupat un gran nombre d estratègies d anàlisi. Es pot trobar una comparació pràctica de diverses estratègies a Slocum (1981). Qui vulgui ampliar aquest tema pot consultar Carroll (2003) i Jurafsky i Martin (2000). 4) Chart parser: és un analitzador que fa servir taules auxiliars 2.1. Analitzador descendent recursiu LTK disposa d un analitzador descendent recursiu*, RecursiveDescentParser. Si en una sessió interactiva de Python fem: *En anglès, recursive descent parser. hp(nltk.recursivedescentparser) btindrem una bona explicació de com funciona, que tradueixo aproximadament en les línies següent: El RecursiveDescentParser és un analitzador de gramàtiques lliures de context que analitza s textos expandint de manera recursiva s extrems de l arbre i comparant-los amb text d entrada. El RecursiveDescentParser fa servir una llista d ubicacions de l arbre per a recordar quins subarbres encara no s han expandit i quines fulles (extrems de l arbre) encara no han coincidit amb text d entrada. Cada ubicació de l arbre consisteix en una llista d índexs ds fills que especifiquen la ruta des de l arr de l arbre fins al subarbre o fins a la fulla; podeu consultar la documentació de referència de Tree per a obtenir més informació sobre sobre les ubicacions de l arbre. Quan l analitzador comença l anàlisi construeix un arbre que conté únicament símbol inicial i una frontera que conté la ubicació d node arr de l arbre. Llavors expandeix l arbre per a cobrir text d entrada fent servir procediment recursiu següent: Si la frontera està buida i text està cobert per l arbre, retorna l arbre com a una anàlisi possible.

18 c CC-BY-SA PID_ Formalismes sintàctics Si la frontera està buida, i text no queda cobert per l arbre d anàlisi, llavors no retorna cap anàlisi. Si primer ement de la frontera és un subarbre fa servir les produccions de la gramàtica lliure de context per a expandir-lo. Per a cada producció aplicable, afegeix fill d subarbre expandit a la frontera, i troba de manera recursiva totes les anàlisis que poden ser generades p nou arbre i frontera. Si primer ement de la frontera és un símbol terminal (paraula) llavors mira si coincideix amb la paraula següent d text d entrada. Elimina la paraula de la frontera i troba de manera recursiva totes les anàlisis que poden ser generades p nou arbre i frontera. Disposem d una demostració interactiva d aquest analitzador; la podem executar fent, en una sessió interactiva: nltk.app.rdparser() Podem observar l aspecte d aquesta versió de demostració a la figura 6. Si feu clic al botó Autostep podreu observar tot procés fins a arribar a una anàlisi possible. Figura 6. Demo de l analitzador descendent recursiu En aquesta versió de demostració podem modificar la gramàtica i posar una altra frase a analitzar. Ara analitzarem una frase molt senzilla amb una gramàtica molt senzilla i anirem veient s passos que fa l analitzador. Per a editar la gramàtica feu Edit > Edit Grammar. Escriviu la gramàtica que es mostra a la figura 7. o oblideu de posar que símbol inicial és. Per a escriure les regles feu servir -> tot i que l editor dibuixarà un tabulador.

19 c CC-BY-SA PID_ Formalismes sintàctics Figura 7. Gramàtica catalana senzilla per a provar la versió de demostració de l analitzador descendent recursiu Ara editem la frase per analitzar fent Edit > Edit text i posant gos menja carn. En les figures següents veiem procés d anàlisi fins a arribar a una anàlisi vàlida. El procés encara continuaria fent tornada enrere i analitzant altres possibilitats, tot i que no arribaria a cap altra anàlisi vàlida. 1. Comencem p símbol inicial 2. Expandeix la regla -> ota Les funcionalitats d edició de la gramàtica i de la frase per analitzar no estan molt desenvolupades. Per aquest motiu he inclòs en la distribució ds programes programa rdparser_app-cat.py, que podeu executar directament amb la gramàtica i la frase modificades. gos menja carn gos menja carn 3. Expandeix la regla -> 4. Prova amb -> gos gos gos menja carn gos menja carn

20 c CC-BY-SA PID_ Formalismes sintàctics 5. Fa tornada enrere 6. Prova amb -> carn carn gos menja carn gos menja carn 7. o hi ha cap altra possibilitat amb -> 8. Fa tornada enrere gos menja carn gos menja carn 9. Expandeix la regla -> 10. Prova amb -> gos menja carn gos menja carn

21 c CC-BY-SA PID_ Formalismes sintàctics 11. Coincideix amb la frase d entrada 12. Prova amb -> gos gos gos menja carn gos menja carn 13. Coincideix amb la frase d entrada 14. Expandeix -> V V gos gos gos menja carn gos menja carn 15. Prova amb V -> menja 16. Coincideix amb la frase d entrada V V menja gos gos menja gos menja carn gos menja carn

22 c CC-BY-SA PID_ Formalismes sintàctics 17. o assoleix una anàlisi completa 18. o hi ha més V V V gos gos gos menja carn gos menja carn 19. Fa tornada enrere 20. Expandeix la regla -> V V gos gos gos menja carn gos menja carn 21. Prova amb V -> menja 22. Coincideix amb la frase d entrada V V menja gos gos menja gos menja carn gos menja carn

23 c CC-BY-SA PID_ Formalismes sintàctics 23. Expandeix la regla -> 24. Prova amb -> gos V V gos gos menja gos menja gos menja carn gos menja carn 25. o coincideix amb la frase d entrada 26. Prova amb -> carn V V carn gos menja gos menja gos menja carn gos menja carn 27. Assoleix una anàlisi completa V gos menja carn gos menja carn Tot i que ha assolit una anàlisi completa, procés d anàlisi no acabaria aquí, ja que l analitzador intentarà buscar altres anàlisis possibles.

24 c CC-BY-SA PID_ Formalismes sintàctics Els analitzadors descendents recursius tenen una sèrie de problemes importants: Les produccions recursives a l esquerra, com per exemple, P -> P PP, fan que l analitzador entri un un bucle infinit. Per a verificar això, executeu la versió de demostració de l analitzador descendent recursiu i modifiqueu la gramàtica que ve per defecte afegint una regla com l anterior. Executeu la versió de demostració i feu clic en Autostep perquè s executi automàticament. Veureu com entra en aquest bucle infinit. A la figura 8 es pot observar l estat de l anàlisi després d una estona. Figura 8. Bucle infinit de l analitzador descendent recursiu L analitzador perd molt de temps en tenir en compte paraules i estructures que no es corresponen amb la frase d entrada. El procés de tornada enrere descarta alguns constituents que ja estan analitzats i que potser s han de tornar a fer servir més tard. Així doncs, s analitzadors descendents fan servir la gramàtica per a predir com serà l entrada, quan l entrada ja està disponible des d principi. Els analitzadors ascendents, que veurem en s propers subapartats, tenen en compte la frase per analitzar des d principi L analitzador shift-reduce LTK implementa un analitzador shift-reduce, ShiftReduceParser. Si en una sessió interactiva de Python fem: hp(nltk.shiftreduceparser)

25 c CC-BY-SA PID_ Formalismes sintàctics obtenim tota l ajuda sobre aquest analitzador, que traduïm aproximadament aquí: El ShiftReduceParser és un analitzador ascendent senzill per a gramàtiques lliures de context que fa servir dues operacions, shift (traslladar) i reduce (reduir), per a trobar una única anàlisi d un text. El ShiftReduceParser manté una pila (stack), que registra l estructura d una part d text. Aquesta pila és una llista de cadenes (strings) i d arbres (trees), que en conjunt cobreixen una porció d text. Per exemple, en analitzar la frase the dog saw the man amb una gramàtica típica, ShiftReduceParser produirà la pila següent, que inclou the dog saw : [(P: (: the ) (: dog )), (V: saw )] El ShiftReduceParser intenta estendre la pila per a cobrir tot text i combinar s ements de la pila en un únic arbre per a produir una anàlisi completa per a la frase. Inicialment, la pila està buida. S estén per a cobrir text, d esquerra a dreta, aplicant repetidament dues operacions: shift (traslladar): mou un token d principi d text al final de la pila. reduce (reduir): fa servir una producció de la gramàtica lliure de context per a combinar s ements de més a la dreta de la pila en un únic arbre. Sovint es pot aplicar més d una operació sobre una pila determinada. En aquest cas, ShiftReduceParser fa servir l heurística següent per a determinar quina operació ha de portar a terme: omés fa servir l operació shift si no hi ha disponible cap operació reduce. Si hi ha disponible més d una operació reduce, llavors aplica la reducció que correspon a la regla que apareix abans en la gramàtica. Cal tenir en compte que aquestes heurístiques no garanteixen que es triï una operació que porti a una anàlisi d text. Fins i tot, si hi ha diverses anàlisis possibles ShiftReduceParser en retornarà només una. També disposem d una demostració interactiva d aquest analitzador; la podem executar fent, en una sessió interactiva: nltk.app.srparser()

26 c CC-BY-SA PID_ Formalismes sintàctics Podem observar l aspecte d aquesta versió de demostració a la figura 9. Si feu clic al botó Autostep podreu observar tot procés fins a arribar a una anàlisi possible. Figura 9. Demo de l analitzador shift-reduce A les figures següents podem observar l anàlisi de l oració gos menja amb una gramàtica adient amb l analitzador shift-reduce. Podeu executar programa srparser_app-cat.py per a observar mateix procés. bservem que en aquest cas l analitzador arriba a una anàlisi vàlida. 1. Shift: 2. Reduce: -> Stack Remaining Text Stack Remaining Text gos menja gos menja 3. Shift: gos 4. Reduce -> gos Stack Remaining Text Stack Remaining Text gos menja menja gos

27 c CC-BY-SA PID_ Formalismes sintàctics 5. Reduce: -> 6. Shift: menja Stack Remaining Text Stack Remaining Text menja menja gos gos 7. Reduce: V -> menja 8. Reduce: -> V Stack Remaining Text Stack Remaining Text V menja V gos gos menja 9. Reduce -> Stack Remaining Text V gos menja Podem observar que procés d anàlisi s ha fet en menys passos que en cas de l analitzador descendent recursiu. Tot i això, cal tenir en compte que un analitzador com aquest no sempre troba l anàlisi tot i que n hi hagi. Si executeu programa srparser_app-cat2.py veurem procés d anàlisi de la frase gos menja carn amb la mateixa gramàtica i veurem que no assoleix cap anàlisi vàlida. 1. Shift: 2. Reduce: -> Stack Remaining Text Stack Remaining Text gos menja carn gos menja carn

28 c CC-BY-SA PID_ Formalismes sintàctics 3. Shift: gos 4. Reduce: -> gos Stack Remaining Text Stack Remaining Text gos menja carn menja carn gos 5. Reduce: -> 6. Shift: menja Stack Remaining Text Stack Remaining Text menja carn menja carn gos gos 7. Reduce: V -> menja 8. Reduce: -> V Stack Remaining Text Stack Remaining Text V carn carn menja V gos gos menja 9. Reduce: -> 10. Shift: carn Stack Remaining Text Stack Remaining Text carn carn V V gos menja gos menja

29 c CC-BY-SA PID_ Formalismes sintàctics 11. Reduce: -> carn 12. Reduce: -> (i failure) Stack Remaining Text Stack Remaining Text carn V V carn gos menja gos menja 2.3. L analitzador left-corner Un analitzador left-corner és un híbrid entre les estratègies descendents i ascendents; és de fet un analitzador descendent, però que fa servir un filtratge ascendent. Amb aquesta aproximació s evita que l analitzador arribi a bucles infinits quan es troba amb una producció recursiva per l esquerra. El primer que fa un analitzador left-corner és processar la gramàtica i construir una taula en què cada filera conté dues c. les, la primera conté un símbol no terminal, i la segona conté totes s possibles extrems esquerres per a aquest no terminal. Si considerem la gramàtica següent: -> SP -> Prep -> SP PronPer -> V V V SP V SP PronPer -> l la Prep -> de a -> un -> nen formatge casa entrepà V -> canta menja La taula inicial que construeix l analitzador la podem trobar a la taula 1. Taula 1. Extrems esquerres de la gramàtica d exemple Categoria Extrem esquerre (preterminals) SP Prep, PronPer V Cada cop que l analitzador considera una determinada producció es verifica que la paraula d entrada següent sigui compatible amb almenys una de les categories preterminals de la taula.

30 c CC-BY-SA PID_ Formalismes sintàctics 2.4. Analitzadors amb taules auxiliars (Chart parsers) Una estratègia per a optimitzar rendiment ds analitzadors és l ús de taules auxiliars on s emmagatzemen s resultats parcials que es van obtenint en procés d anàlisi. Aquests resultats parcials es poden reutilitzar més endavant si convé, sense la necessitat de tornar-los a obtenir. Aquestes taules són llistes de resultats parcials d anàlisi, que poden ser utilitzats en qualsevol moment: indiquen a quins segments de l entrada es corresponen, quina és la seva categoria final i quina és l anàlisi que proposen per al segment. LTK implementa analitzadors amb taules auxiliars en la classe chart. Si fem hp(nltk.parse.chart), obtenim informació sobre aquesta classe, que resumim aquí: Aquesta classe proporciona implementacions de classes de dades i analitzadors per a analitzar amb taules auxiliars (char parsers) que fan servir tècniques de programació dinàmica per a analitzar un text de manera eficient. Un chartparser deriva arbres d anàlisi per a un text afegint de manera interactiva hipòtesis d anàlisi a la taula. La taula és com una pissarra on es poden compondre i combinar aquestes hipòtesis. Quan un analitzador amb taules auxiliars comença a analitzar un text crea una nova taula que està buida i que abasta tot text. Després afegeix noves hipòtesis a la taula d una manera incremental. Un conjunt de chart rules especifica les condicions que s han de donar perquè s afegeixi una nova hipòtesi a la taula. L anàlisi s ha completat un cop la taula assoleixi un estat en què cap de les chart rules afegeixi cap nova hipòtesi. LTK també proporciona una versió de demostració d aquest analitzador; podem accedir a aquesta versió de demostració des d una sessió interactiva de Python. En la primera versió de demostració veurem com funciona amb una estratègia descendent: >>> import nltk >>> nltk.parse.chart.demo(1, should_print_times=false, should_print_grammar=true, trace=1, sent="john saw a dog", numparses=1) * Grammar Grammar with 18 productions (start state = S) S -> P VP PP -> with P P -> P PP VP -> VP PP VP -> Verb P VP -> Verb P -> oun P -> John P -> I -> the -> my

31 c CC-BY-SA PID_ Formalismes sintàctics -> a oun -> dog oun -> cookie Verb -> ate Verb -> saw Prep -> with Prep -> under * Sentence: John saw a dog [ John, saw, a, dog ] * Strategy: Top-down. John. saw. a. dog. [ ]... [0:1] John. [ ].. [1:2] saw.. [ ]. [2:3] a... [ ] [3:4] dog >.... [0:0] S -> * P VP >.... [0:0] P -> * P PP >.... [0:0] P -> * oun >.... [0:0] P -> * John [ ]... [0:1] P -> John * [ >... [0:1] S -> P * VP [ >... [0:1] P -> P * PP. >... [1:1] VP -> * VP PP. >... [1:1] VP -> * Verb P. >... [1:1] VP -> * Verb. >... [1:1] Verb -> * saw. [ ].. [1:2] Verb -> saw *. [ >.. [1:2] VP -> Verb * P. [ ].. [1:2] VP -> Verb * [ ].. [0:2] S -> P VP *. [ >.. [1:2] VP -> VP * PP.. >.. [2:2] P -> * P PP.. >.. [2:2] P -> * oun.. >.. [2:2] -> * a.. [ ]. [2:3] -> a *.. [ >. [2:3] P -> * oun... >. [3:3] oun -> * dog... [ ] [3:4] oun -> dog *.. [ ] [2:4] P -> oun *. [ ] [1:4] VP -> Verb P *.. [ > [2:4] P -> P * PP [=======================================] [0:4] S -> P VP *. [ > [1:4] VP -> VP * PP (S (P John) (VP (Verb saw) (P ( a) (oun dog))))

32 c CC-BY-SA PID_ Formalismes sintàctics El primer que ens mostra la versió de demostració és la gramàtica que fa servir, l oració per analitzar i l estratègia que farà servir. Les regles de la gramàtica que s han pogut fer servir per a analitzar un fragment de la frase es mostren de la manera següent: [ ] i la seva amplada correspondrà al nombre de tokens que pot analitzar (que també estaran determinats per les xifres que s expressen entre claudàtors), així, si ens fixem:. [ ] [1:4] VP -> Verb P * indica que la regla especificada pot analitzar s tokens d 2 (saw) al 4 (dog). També podem mostrar resultat de la versió de demostració fent servir una estratègia ascendent (ara ja no farem que escrigui la gramàtica que fa servir): >>> nltk.parse.chart.demo(2, should_print_times=false, should_print_grammar=false, trace=1, sent="john saw a dog", numparses=1) * Sentence: John saw a dog [ John, saw, a, dog ] * Strategy: Bottom-up. John. saw. a. dog. [ ]... [0:1] John. [ ].. [1:2] saw.. [ ]. [2:3] a... [ ] [3:4] dog >.... [0:0] P -> * John [ ]... [0:1] P -> John * >.... [0:0] S -> * P VP >.... [0:0] P -> * P PP [ >... [0:1] S -> P * VP [ >... [0:1] P -> P * PP. >... [1:1] Verb -> * saw. [ ].. [1:2] Verb -> saw *. >... [1:1] VP -> * Verb P. >... [1:1] VP -> * Verb. [ >.. [1:2] VP -> Verb * P. [ ].. [1:2] VP -> Verb *. >... [1:1] VP -> * VP PP

33 c CC-BY-SA PID_ Formalismes sintàctics [ ].. [0:2] S -> P VP *. [ >.. [1:2] VP -> VP * PP.. >.. [2:2] -> * a.. [ ]. [2:3] -> a *.. >.. [2:2] P -> * oun.. [ >. [2:3] P -> * oun... >. [3:3] oun -> * dog... [ ] [3:4] oun -> dog *.. [ ] [2:4] P -> oun *.. >.. [2:2] S -> * P VP.. >.. [2:2] P -> * P PP. [ ] [1:4] VP -> Verb P *.. [ > [2:4] S -> P * VP.. [ > [2:4] P -> P * PP [=======================================] [0:4] S -> P VP *. [ > [1:4] VP -> VP * PP (S (P John) (VP (Verb saw) (P ( a) (oun dog)))) I també amb una estratègia ascendent left-corner: >>> nltk.parse.chart.demo(3, should_print_times=false, should_print_grammar=false, trace=1, sent="john saw a dog", numparses=1) * Sentence: John saw a dog [ John, saw, a, dog ] * Strategy: Bottom-up left-corner. John. saw. a. dog. [ ]... [0:1] John. [ ].. [1:2] saw.. [ ]. [2:3] a... [ ] [3:4] dog [ ]... [0:1] P -> John * [ >... [0:1] S -> P * VP [ >... [0:1] P -> P * PP. [ ].. [1:2] Verb -> saw *. [ >.. [1:2] VP -> Verb * P. [ ].. [1:2] VP -> Verb *. [ >.. [1:2] VP -> VP * PP [ ].. [0:2] S -> P VP *.. [ ]. [2:3] -> a *.. [ >. [2:3] P -> * oun... [ ] [3:4] oun -> dog *.. [ ] [2:4] P -> oun *.. [ > [2:4] S -> P * VP

34 c CC-BY-SA PID_ Formalismes sintàctics.. [ > [2:4] P -> P * PP. [ ] [1:4] VP -> Verb P *. [ > [1:4] VP -> VP * PP [=======================================] [0:4] S -> P VP * (S (P John) (VP (Verb saw) (P ( a) (oun dog))))

35 c CC-BY-SA PID_ Formalismes sintàctics 3. Gramàtica de trets. Les gramàtiques lliures de context que hem presentat a l apartat 1 descriuen s constituents sintàctics amb l ajut d un conjunt limitat d etiquetes de categories. Aquestes etiquetes poden ser adequades per a descriure l estructura més general d una oració, però no són pràctiques si volem fer distincions gramaticals més fines. Si prenem com a exemple la gramàtica gramatica4.cfg, en què volem descriure la concordança determinant-nom o sintagma nominalverb veiem que formalisme es complica. Les gramàtiques de trets* permeten expressar trets específics per a les diferents categories. La mateixa gramàtica gramatica4.cfg es pot expressar d una manera molt més eficient fent servir trets (gramatica5.fcfg). *En anglès, feature-based grammars. % start ############################# # Regles gramatica ############################# # Regles d expansió d -> [UM=?n] [UM=?n] # Regles d expansió de [UM=?n] -> [UM=?n] [UM=?n] -> [UM=?n, GE=?g] [UM=?n, GE=?g] # Regles d expansió de [TESE=?t, UM=?n] -> VI[TESE=?t, UM=?n] [TESE=?t, UM=?n] -> VI[TESE=?t, UM=?n] [TESE=?t, UM=?n] -> VT[TESE=?t, UM=?n] ############################# # Regles lèxiques ############################# [UM=sg, GE=m] -> un [UM=sg, GE=f] -> la una [UM=pl, GE=m] -> s uns [UM=pl, GE=f] -> les uns [UM=sg, GE=m] -> noi entrepà professor [UM=sg, GE=f] -> noia professora nota [UM=pl, GE=m] -> nois entrepans professors [UM=pl, GE=f] -> noies professores notes VI[TESE=pres, UM=sg] -> menja VT[TESE=pres, UM=sg] -> diu VI[TESE=pres, UM=pl] -> mengen VT[TESE=pres, UM=pl] -> diuen

36 c CC-BY-SA PID_ Formalismes sintàctics El programa que utilitzarem és molt semblant a l anterior i demanarà una gramàtica i una frase per analitzar (programa-8-4.py). # -*- coding: utf-8 -*- import nltk from nltk.parse import load_parser print " Indica nom de la gramàtica: ", fgramatica=raw_input() print "Escriu la frase per analitzar: ", frase=raw_input() tokens=frase.split() gramatica=load_parser( file:%s % fgramatica) arbres=gramatica.nbest_parse(tokens) for arbre in arbres: print arbre arbre.draw() Si demanem que analitzi l oració noi menja uns entrepans ens oferirà una anàlisi en mode text i com a arbre (figura 10): ([] ([UM= sg ] ([GE= m, UM= sg ] ) ([GE= m, UM= sg ] noi)) ([UM= sg, TESE= pres ] (VI[UM= sg, TESE= pres ] menja) ([UM= pl ] ([GE= m, UM= pl ] uns) ([GE= m, UM= pl ] entrepans)))) Figura 10. Anàlisi sintàctica d noi menja uns entrepans

37 c CC-BY-SA PID_ Formalismes sintàctics 3.1. Processament d estructures de trets En aquest subapartat veurem com es poden processar amb LTK les estructures de trets. També presentarem l operació fonamental amb estructures de trets, que s anomena unificació. Les gramàtiques de trets treballen fonamentalment amb aquestes estructures i amb aquesta operació fonamental. En LTK les estructures de trets es declaren amb constructor FeatStruct(). Aquesta estructura és semblant a un diccionari i podem accedir a cada un ds valors i assignar-los de la manera habitual. En una sessió interactiva de Python proveu següent (no oblideu de fer import nltk ): >>> et1=nltk.featstruct(cat=, UM= sg ) >>> et1[ GE ]= m >>> print et1[ CAT ] També es poden definir estructures de trets amb valors complexos, és a dir, que un ds seus valors sigui també una estructura de trets: >>> et1=nltk.featstruct("[ps=, CC=[PER=3, UM= pl, GE= f ]]") >>> print et1 [ [ GE = f ] ] [ CC = [ UM = pl ] ] [ [ PER = 3 ] ] [ ] [ PS = ] Aquesta estructura de trets la podríem haver declarat també de la manera següent: >>> et0=nltk.featstruct(per= 3, UM= pl, GE= f ) >>> et1=nltk.featstruct(ps=, CC=et0) >>> print et1 [ [ GE = f ] ] [ CC = [ UM = pl ] ] [ [ PER = 3 ] ] [ ] [ PS = Les estructures de trets no es fan servir únicament en lingüística; aquestes estructures poden emmagatzemar qualsevol tipus d informació. En l exemple següent podem observar una estructura de trets que emmagatzema informació sobre una persona:

38 c CC-BY-SA PID_ Formalismes sintàctics >>> print nltk.featstruct(nom= Maria, edat= 25, t= ) [ edat = 25 ] [ nom = Maria ] [ t = ] ormalment les estructures de trets donen una informació parcial sobre algun objecte. En aquest sentit, podem ordenar les estructures de trets segons siguin més generals o més específiques. Per exemple, de les estructures de trets següents, la a és més general que la b i aquesta, a la seva vegada, és més general que la c. >>> a=nltk.featstruct(um=125) >>> b=nltk.featstruct(um=125,carrer= Balmes ) >>> c=nltk.featstruct(um=125,carrer= Balmes,CIUTAT= Barcona ) >>> print a [ UM = 125 ] >>> print b [ CARRER = Balmes ] [ UM = 125 ] >>> print c [ CARRER = Balmes ] [ CIUTAT = Barcona ] [ UM = 125 ] Aquest tipus d ordenació s anomena subsumció: una estructura més general subsumeix una estructura menys general. La fusió d informació de dues estructures de trets s anomena unificació. Amb LTK es pot fer aquesta operació amb mètode unify(). Vegem l exemple següent: >>> et1=nltk.featstruct(um=125, CARRER= Balmes ) >>> et2=nltk.featstruct(ciutat= Barcona ) >>> print et1.unify(et2) [ CARRER = Balmes ] [ CIUTAT = Barcona ] [ UM = 125 ] Ara bé, no sempre es pot portar a terme aquesta operació. Fixeu-vos en següent exemple: >>> et1=nltk.featstruct(um=125, CARRER= Balmes ) >>> et2=nltk.featstruct(carrer= Muntaner ) >>> print et1.unify(et2) one

39 c CC-BY-SA PID_ Formalismes sintàctics Les gramàtiques de trets que presentem en aquest apartat funcionen bàsicament amb l operació d unificació. Fixem-nos en l exemple següent, en què s trets d determinant i nom unifiquen i poden constituir un sintagma nominal: >>> det=nltk.featstruct(ge= m,um= s ) >>> nom=nltk.featstruct(ge= m,um= s ) >>> sn=det.unify(nom) >>> print sn [ GE = m ] [ UM = s ] En canvi, en l exemple següent, s trets d determinant i nom no unifiquen: >>> det=nltk.featstruct(ge= m,um= s ) >>> nom=nltk.featstruct(ge= f,um= s ) >>> sn=det.unify(nom) >>> print sn one Exercici Amplieu la gramatica5.fcfg (i anomeneu-la gramatica6.fcfg) perquè pugui analitzar les oracions següents: s nois i les noies mengen entrepans de formatge s nois i les noies mengen entrepans de formatge i pastissos de xocolata noi llegeix un llibre a casa

40 c CC-BY-SA PID_ Formalismes sintàctics 4. Les gramàtiques lliures de context probabilístiques. En certes situacions, una gramàtica lliure de context pot donar més d una possible anàlisi. Fixem-nos en l oració següent: jo miro la noia amb tescopi L oració és ambigua des d punt de vista sintàctic, ja que amb tescopi pot complementar noia o miro. Si tenim la gramàtica següent lliure de context (gramatica7.cfg) (podeu executar programa programa-8-3.py): -> -> -> SP -> PP -> V -> V -> V SP SP -> Prep -> la PP -> jo -> noia tescopi V -> miro Prep -> amb Ens ofereix les dues anàlisis següents (que també podem observar a les figures 11 i 12): ( ( (PP jo)) ( (V miro) ( ( la) ( noia)) (SP (Prep amb) ( ( ) ( tescopi))))) ( ( (PP jo))

41 c CC-BY-SA PID_ Formalismes sintàctics ( (V miro) ( ( la) ( noia)) (SP (Prep amb) ( ( ) ( tescopi))))) Figura 11. Anàlisi sintàctica de jo miro la noia amb tescopi Figura 12. Anàlisi sintàctica de jo miro la noia amb tescopi A un parlant de la llengua primer que li ve al cap és que jo miro la noia fent servir un tescopi i no que la noia porta un tescopi. Però en l oració següent, amb la mateixa estructura sintàctica, jo miro la noia amb barret, queda molt clar que la noia porta un barret. Una gramàtica lliure de context probabilística* és una gramàtica lliure de context amb informació de la probabilitat de cada una de les produccions. Per tal d assegurar que totes les anàlisis generades per la gramàtica formin una distribució de probabilitats, les PCFG imposen com a restricció que totes les produccions amb una part esquerra donada tinguin una suma de probabilitats igual a 1. *En anglès, Probabilistic Context Free Grammar (PCFG).

42 c CC-BY-SA PID_ Formalismes sintàctics A continuació (programa-8-5.py) podem observar un exemple de gramàtica lliure de context probabilística: import nltk grammar = nltk.parse_pcfg(""" S -> [1.0] -> PrP [0.3] -> [0.5] -> SP [0.2] SP -> Prep [1.0] -> V [0.2] -> V [0.4] -> V SP [0.4] PrP -> jo [1.0] -> la [0.5] -> [0.5] -> noia [0.5] -> tescopi [0.5] Prep -> amb [1.0] V -> miro [1.0] """) print grammar viterbi_parser = nltk.viterbiparser(grammar) frase="jo miro la noia amb tescopi" tokens = frase.split() analisi= viterbi_parser.parse(tokens) print analisi analisi.draw() Si executem aquest programa obtindrem la sortida següent i també l anàlisi en forma gràfica (figura 13). Fixeu-vos que també dóna una xifra de probabilitat total (p = 0,001875). Grammar with 15 productions (start state = S) S -> [1.0] -> PrP [0.3] -> [0.5] -> SP [0.2] SP -> Prep [1.0] -> V [0.2] -> V [0.4] -> V SP [0.4] PrP -> jo [1.0] -> la [0.5] -> [0.5]

43 c CC-BY-SA PID_ Formalismes sintàctics -> noia [0.5] -> tescopi [0.5] Prep -> amb [1.0] V -> miro [1.0] (S ( (PrP jo)) ( (V miro) ( ( la) ( noia)) (SP (Prep amb) ( ( ) ( tescopi))))) (p= ) Figura 13. Anàlisi sintàctica de jo miro la noia amb tescopi amb una gramàtica probabilística 4.1. Inducció de gramàtiques Com hem vist, les PCFG són com les CFG però amb probabilitats. En l exemple anterior que hem fet és simplement especificar aquestes probabilitats en la gramàtica (en realitat ens les hem inventades). En un cas real, d on podem obtenir aquests valors de probabilitat? El més habitual és estimar aquestes probabilitats a partir de dades d entrenament, concretament a partir d arbres s anàlisi (parse trees) o treebanks. Un treebank és un corpus en què cada oració s ha anotat amb la seva estructura sintàctica. LTK ofereix diversos treebanks: alpino: Alpino Treebank (Dutch) cess_cat: CESS-CAT Treebank (Catalan) cess_esp: CESS-ESP Treebank (Spanish) floresta: Floresta Treebank (Portuguese) treebank: Penn Treebank Corpus Sample (English) sinica: Sinica Treebank Corpus Sample (Chinese) En una sessió interactiva podem observar les primeres oracions analitzades, per exemple, d Penn Treebank: >>> print nltk.corpus.treebank.parsed_sents() [Tree( S, [Tree( P-SBJ, [Tree( P, [Tree( P, [ Pierre ]),

44 c CC-BY-SA PID_ Formalismes sintàctics Tree( P, [ Vinken ])]), Tree(,, [, ]), Tree( ADJP, [Tree( P, [Tree( CD, [ 61 ]), Tree( S, [ years ])]), Tree( JJ, [ old ])]), Tree(,, [, ])]), Tree( VP, [Tree( MD, [ will ]), Tree( VP, [Tree( VB, [ join ]), Tree( P, [Tree( DT, [ the ]), Tree(, [ board ])]), Tree( PP-CLR, [Tree( I, [ as ]), Tree( P, [Tree( DT, [ a ]), Tree( JJ, [ nonexecutive ]), Tree(, [ director ])])]), Tree( P-TMP, [Tree( P, [ ov. ]), Tree( CD, [ 29 ])])])]), Tree(., [. ])]), Tree( S, [Tree( P-SBJ, [Tree( P, [ Mr. ]), Tree( P, [ Vinken ])]), Tree( VP, [Tree( VBZ, [ is ]), Tree( P-PRD, [Tree( P, [Tree(, [ chairman ])]), Tree( PP, [Tree( I, [ of ]), Tree( P, [Tree( P, [Tree( P, [ Elsevier ]), Tree( P, [.V. ])]), Tree(,, [, ]), Tree( P, [Tree( DT, [ the ]), Tree( P, [ Dutch ]), Tree( VBG, [ publishing ]), Tree(, [ group ])])])])])]), Tree(., [. ])]),...] A partir d aquest treebank podem fer un programa (programa-8-6.py) que indueixi una gramàtica i analitzi l oració the man saw the girl in the park : import nltk from itertools import islice productions = [] S = nltk.onterminal( S ) for tree in nltk.corpus.treebank.parsed_sents(): productions += tree.productions() grammar = nltk.induce_pcfg(s, productions) print grammar viterbi_parser = nltk.viterbiparser(grammar) frase="the man saw the girl in the park" tokens = frase.split() analisi= viterbi_parser.parse(tokens) print analisi analisi.draw() Si executem aquest programa obtindrem la sortida següent (la gramàtica induïda és molt més llarga, però reproduïm només un fragment; si no voleu visualitzar la gramàtica imineu o comenteu la línia print grammar) i l anàlisi de la figura 14. Tingueu en compte que aquest programa pot trigar una bona estona a executar-se.... P -> Solaia [ ] JJ -> proof [ ] VB -> swallow [ ] VB -> parall [ ] P -> RDC [ ]

45 c CC-BY-SA PID_ Formalismes sintàctics CD -> 5.92 [ ] P -> Frenzy [ ] S -> attacks [ ] SBAR -> WHP-258 S [ ] JJR -> fewer [ ] RB -> but [ ] VP -> VBD PP-LC-PRD S-ADV [ e-05] VBG -> dominating [ ] VBG -> failing [ ] VP -> VBD ADJP-PRD ADVP-TMP [ ] VB -> contacted [ ] P-SBJ -> DT JJ P P [ ] (S (P-SBJ (DT the) ( man)) (VP (VBD saw) (P (DT the) ( girl)) (PP-CLR (I in) (P (DT the) ( park))))) (p= e-22) Figura 14. Anàlisi sintàctica de the man saw the girl in the park amb una gramàtica probabilística induïda LTK també incorpora un treebank per al català ( cess_cat). Podem veure algunes oracions analitzades d aquest treebank en una sessió interactiva: >>> print nltk.corpus.cess_cat.parsed_sents() [Tree( S, [Tree( sno-suj, [Tree( espec.ms, [Tree( da0ms0, [ El ])]), Tree( grup.nom.ms, [Tree( np0000o, [ Tribunal_Suprem ]), Tree( sno, [Tree( grup.nom.ms, [Tree( Fpa, [ -Fpa- ]), Tree( np0000o, [ TS ]), Tree( Fpt, [ -Fpt- ])])])])]), Tree( grup.verb, [Tree( vaip3s0, [ ha ]), Tree( vmp00sm, [ confirmat ])]), Tree( sn-cd, [Tree( espec.fs, [Tree( da0fs0, [ la ])]), Tree( grup.nom.fs, [Tree( ncfs000, [ condemna ]), Tree( sp, [Tree( prep, [Tree( sps00, [ a ])]), Tree( sn.co, [Tree( sn, [Tree( espec.mp, [Tree( dn0cp0, [ quatre ])]), Tree( grup.nom.mp, [Tree( ncmp000, [ anys ]), Tree( sp, [Tree( prep, [Tree( sps00, ["d "])]), Tree( sn, [Tree( grup.nom.fs, [Tree( ncfs000, [ inhabilitaci\xf3 ]), Tree( s.a.fs, [Tree( grup.a.fs,

46 c CC-BY-SA PID_ Formalismes sintàctics [Tree( aq0cs0, [ especial ])])])])])])])]), Tree( coord, [Tree( cc, [ i ])]), Tree( sn, [Tree( espec.fs, [Tree( di0fs0, [ una ])]), Tree( grup.nom.fs, [Tree( ncfs000, [ multa ]), Tree( sp, [Tree( prep, [Tree( sps00, [ de ])]), Tree( snn, [Tree( espec.mp, [Tree( Z, [ 3,6 ])]), Tree( grup.nom.mp, [Tree( ncmp000, [ milions ]), Tree( sp, [Tree( prep, [Tree( sps00, [ de ])]), Tree( sn, [Tree( grup.nom.fp, [Tree( Zm... Amb aquest treebank podem induir una gramàtica per al català (programa-8-7.py). En aquest exemple fem servir les primeres oracions d treebank. import nltk from itertools import islice productions = [] S = nltk.onterminal( S ) sents=nltk.corpus.cess_cat.parsed_sents(); for tree in sents[0:1000]: productions += tree.productions() grammar = nltk.induce_pcfg(s, productions) print grammar viterbi_parser = nltk.viterbiparser(grammar) frase= la llista era extensa" tokens = frase.split() analisi= viterbi_parser.parse(tokens) print analisi analisi.draw() Si executem programa obtindrem la sortida següent i l anàlisi de la figura 15:... vmp00sm -> autoinculpat [ ] grup.nom.fp.1n -> Z [ ] di0cs0 -> cada [ ] S.F.R -> ratiu-suj morfema.verbal-pass grup.verb sadv-cc [0.006] W -> 1985 [ ] np0000o -> Çol\xb7legi_d _Aparladors_i_Arquitectes_T\xe8cnics_de_Barcona" [ ] S.F.A-CC -> conj.subord morfema.verbal-impers grup.verb sp-creg [ ] S.F.C -> Fe infinitiu sadv-cc sp-cc Fe [ ] ncms000 -> text [ ] Z -> [ ] (S (sn-suj (espec.fs (da0fs0 la))

47 c CC-BY-SA PID_ Formalismes sintàctics (grup.nom.fs (ncfs000 llista))) (grup.verb (vsii3s0 era)) (sa-atr (grup.a (aq0fs0 extensa)))) (p= e-13) Figura 15. Anàlisi sintàctica de la llista era extensa amb una gramàtica probabilística induïda 4.2. Analitzadors per a gramàtiques probabilístiques: l algorisme de Viterbi En l apartat 2 vam veure un seguit d analitzadors (parsers) que permeten fer anàlisis sintàctiques amb gramàtiques lliures de context. En les gramàtiques lliures de context que hem estudiat en aquest apartat hem afegit una informació addicional a cada una de les produccions de la gramàtica: la seva probabilitat. Una determinada oració pot tenir moltes possibles anàlisis segons una gramàtica donada. Si aquesta gramàtica és probabilística, la probabilitat de cada una d aquestes anàlisis és producte de les probabilitats de cadascuna de les regles utilitzades per a derivar l anàlisi. El càlcul de l anàlisi més probable pot ser massa llarg si que es fa és calcular totes les possibles anàlisis i per a cada anàlisi calcula producte de les seves probabilitats. Si ens fixem en s programes que hem fet servir en aquest apartat, tots fan servir ViterbiParser que proporciona l LTK. Aquest analitzador fa servir l algorisme de Viterbi. L algorisme de Viterbi permet trobar les seqüències d estats més probables en un mod ocult de Markov (HMM, hidden Markov mod) a partir d una observació, és a dir, obté la seqüència òptima que explica millor la seqüència d observacions. Lectures recomanades Per saber-ne més sobre l algorisme de Viterbi podeu consultar les obres de Viterbi (1967), Viterbi i mura (1979) i Forney (1973). Un mod ocult de Markov és un mod estadístic en qual s assumeix que sistema per modar és un procés de Markov de paràmetres desconeguts. Un procés o cadena de Markov és una sèrie d esdeveniments en s quals la probabilitat que ocorri un esdeveniment depèn de l esdeveniment immediatament anterior.

48 c CC-BY-SA PID_ Formalismes sintàctics o entrarem en gaires detalls sobre aquest algorisme i només direm que en comptes de calcular les probabilitats de tots s possibles camins, que fa és descartar aquls que no tenen possibilitats de ser considerats de màxima versemblança (maximum likihood). Se n pot trobar una descripció detallada d funcionament a Kenn i Samusson (1997). El ViterbiParser de LTK és un analitzador ascendent per a gramàtiques lliures de context probabilístiques que fa servir tècniques de programació dinàmica per a trobar l anàlisi més probable d un text. L anàlisi la porta a terme omplint una taula de constituents més probables. Aquesta taula registra la representació en arbre d anàlisi més probable per a qualsevol fragment donat i valor de node. Concretament conté una entrada per a cada valor d índex inicial, índex final i valor de node, i registra subarbre més probable que abraça des de l índex inicial fins a l índex final, i que té valor de node donat. Aquest analitzador emplena aquesta taula de manera incremental. Comença omplint totes les entrades per constituents que abracen un ement de text (és a dir, les entrades per a les quals l índex final és un més que l índex inicial). Un cop ha omplert totes les entrades de la taula corresponents als constituents que abracen un ement d text, emplena les entrades per als constituents que abracen dos ements d text. Després continua omplint les entrades corresponents a constituents que abracen porcions com més va més grans d text, fins que omple tota la taula. Per a trobar constituent més probable per a un fragment i valor de node, l analitzador té en compte totes les produccions que poden produir aquest valor de node. Per a cada producció, troba tots s fills que de manera col. lectiva cobreixen fragment de text i tenen s valors de node especificats per la part dreta de la producció. Si la probabilitat de l arbre format per l aplicació de la producció al fill és més gran que la probabilitat de l entrada actual de la taula, llavors la taula s actualitza amb aquest nou arbre. Podem executar una demostració d aquest analitzador fent: >>> nltk.parse.viterbi.demo() 1: I saw the man with my tescope <Grammar with 17 productions> 2: the boy saw Jack with Bob under the table with a tescope <Grammar with 23 productions> Which demo (1-2)? 1 sent: I saw the man with my tescope parser: <ViterbiParser for <Grammar with 17 productions>>

49 c CC-BY-SA PID_ Formalismes sintàctics grammar: Grammar with 17 productions (start state = S) S -> P VP [1.0] P -> [0.5] P -> P PP [0.25] P -> John [0.1] P -> I [0.15] -> the [0.8] -> my [0.2] -> man [0.5] -> tescope [0.5] VP -> VP PP [0.1] VP -> V P [0.7] VP -> V [0.2] V -> ate [0.35] V -> saw [0.65] PP -> P P [1.0] P -> with [0.61] P -> under [0.39] Inserting tokens into the most liky constituents table... Insert: =... I Insert:.=... saw Insert:..=... the Insert:...=... man Insert:...=.. with Insert:...=. my Insert:...= tescope Finding the most liky constituents spanning 1 text ements... Insert: =... P -> I [0.15] Insert:.=... V -> saw [0.65] Insert:.=... VP -> V [0.2] Insert:..=... -> the [0.8] Insert:...=... -> man [0.5] Insert:...=.. P -> with [0.61] Insert:...=. -> my [0.2] Insert:...= -> tescope [0.5] Finding the most liky constituents spanning 2 text ements... Insert: ==... S -> P VP [1.0] Insert:..==... P -> [0.5] Insert:...== P -> [0.5] Finding the most liky constituents spanning 3 text ements... Insert:.===... VP -> V P [0.7] Insert:...=== PP -> P P [1.0] Finding the most liky constituents spanning 4 text ements... Insert: ====... S -> P VP [1.0] Finding the most liky constituents spanning 5 text ements... Insert:..===== P -> P PP [0.25] Finding the most liky constituents spanning 6 text ements...

50 c CC-BY-SA PID_ Formalismes sintàctics Insert:.====== VP -> VP PP [0.1] Insert:.====== VP -> V P [0.7] Discard:.====== VP -> VP PP [0.1] Finding the most liky constituents spanning 7 text ements... Insert: ======= S -> P VP [1.0] Time (secs) # Parses Average P(parse) n/a Draw parses (y/n)? n Print parses (y/n)? y (S (P I) (VP (V saw) (P (P ( the) ( man)) (PP (P with) (P ( my) ( tescope)))))) [ ] En primer lloc la versió de demostració ens demana que triem entre una de les dues oracions que proposa. Un cop triada ens mostra la gramàtica lliure de context probabilística amb la qual treballarà. A partir d aquí comença a omplir la taula de constituents més probables. En primer lloc omple tots s tokens, cada un a la seva posició. Posteriorment va omplint aquesta taula amb constituents que abracen 1, 2, 3, 4, 5, 6 i 7 ements d text d entrada. Un cop fet això mostra s temps, les anàlisis que ha trobat i les seves probabilitats i ens permet dibuixar i imprimir l anàlisi resultant.

51 c CC-BY-SA PID_ Formalismes sintàctics 5. Gramàtiques de dependències. Les gramàtiques que hem introduït fins ara analitzen les oracions tenint en compte com les paraules i s grups de paraules es combinen per a formar constituents i com es racionen aquests constituents. Hi ha una orientació diferent i complementària, les gramàtiques de dependències, que se centren a establir com les paraules es racionen unes amb les altres.. La dependència és una ració asimètrica binària que s estableix entre un nucli (head) i s seus dependents. ormalment es pren com a nucli verb de l oració. A la figura 16 podem observar una anàlisi de dependències de l oració El noi menja un entrepà de formatge feta amb la versió de demostració en línia de l analitzador Freing ( Figura 16. Anàlisi de dependències de l oració El noi menja un entrepà de formatge

52 c CC-BY-SA PID_ Formalismes sintàctics 5.1. Treebanks de dependències de l LTK L LTK ofereix alguns treebanks anotats per dependències: Dependency Treebanks from CoLL 2007 (Spanish and Basque Subset) Dependency Parsed Treebank En una sessió interactiva podem observar la primera oració d Dependency Parsed Treebank en diversos formats. En primer lloc podem veure simplement l oració: >>> print nltk.corpus.dependency_treebank.sents()[0] [ Pierre, Vinken,,, 61, years, old,,, will, join, the, board, as, a, nonexecutive, director, ov., 29,. ] >>> També podem observar tota la informació que conté treebank de la primera oració: >>> print nltk.corpus.dependency_treebank.parsed_sents()[0] [{ address : 0, deps : [8], r : TP, tag : TP, word : one}, { address : 1, deps : [], head : 2, r :, tag : P, word : Pierre }, { address : 2, deps : [1, 3, 6, 7], head : 8, r :, tag : P, word : Vinken }, { address : 3, deps : [], head : 2, r :, tag :,, word :, }, { address : 4, deps : [], head : 5, r :, tag : CD, word : 61 }, { address : 5, deps : [4], head : 6, r :, tag : S, word : years }, { address : 6, deps : [5], head : 2, r :, tag : JJ, word : old }, { address : 7, deps : [], head : 2, r :, tag :,, word :, }, { address : 8,

53 c CC-BY-SA PID_ Formalismes sintàctics deps : [2, 9, 18], head : 0, r :, tag : MD, word : will }, { address : 9, deps : [11, 12, 16], head : 8, r :, tag : VB, word : join }, { address : 10, deps : [], head : 11, r :, tag : DT, word : the }, { address : 11, deps : [10], head : 9, r :, tag :, word : board }, { address : 12, deps : [15], head : 9, r :, tag : I, word : as }, { address : 13, deps : [], head : 15, r :, tag : DT, word : a }, { address : 14, deps : [], head : 15, r :, tag : JJ, word : nonexecutive }, { address : 15, deps : [13, 14], head : 12, r :, tag :, word : director }, { address : 16, deps : [17], head : 9, r :, tag : P,

54 c CC-BY-SA PID_ Formalismes sintàctics word : ov. }, { address : 17, deps : [], head : 16, r :, tag : CD, word : 29 }, { address : 18, deps : [], head : 8, r :, tag :., word :. }] bé una anàlisi exclusivament de dependències: >>> print nltk.corpus.dependency_treebank.parsed_sents()[0].tree() (will (Vinken Pierre, (old (years 61)),) (join (board the) (as (director a nonexecutive)) (ov. 29)).) També la podem veure en forma de gràfic a la figura 17. >>> print nltk.corpus.dependency_treebank.parsed_sents()[0].tree().draw() Figura 17. Anàlisi de dependències de l oració Pierre Vinken, 61 years old, will join the board as a nonexecutive director ov. 29. També podem veure (figura 18) una anàlisi de dependències per al castlà de l oració Las reservas de oro y divisas de Rusia subieron 80 millones de dólares, informó hoy un comunicado d Banco Central : >>> print nltk.corpus.conll2007.parsed_sents()[0].tree().draw() Figura 18. Anàlisi de dependències de l oració Las reservas de oro y divisas de Rusia subieron 80 millones de dólares, informó hoy un comunicado d Banco Central