Procesamiento de Lenguaje Natural TEMA 3 An´ alisis sint´ actico Enrique Alfonseca Pilar Rodr´ıguez

´ Indice

• An´ alisis parcial

• Formalismos

• Algoritmos de an´ alisis

2

• • • • • • • • • • • • • • •

Introducci´ on Listas de transformaci´ on Aprendizaje basado en memoria Otros sistemas CFG DCG HPSG PCFG Otros Introducci´ on Top-down Bottom-up Shift-reduce Left-corner Chart parsing

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on

Parcial Introducci´ on List.Trans. Memoria Otros

Ciertas agrupaciones de palabras se comportan como constituyentes: • Pueden ocurrir en distintas posiciones de las oraciones. • Muestran posibilidades sint´ acticas uniformes. Algunas pruebas de constituencia: • Movimiento:

Formalismos

Algoritmos

a. b. c. d.

Ya estudi´ e la lecci´ on 3. La lecci´ on 3, ya la estudi´ e. ?Ya la lecci´ on 3 estudi´ e. *Ya lecci´ on 3 estudi´ e la.

• Sustituci´ on a. Pedro quiere una manzana. b. Pedro quiere un l´ apiz de otro color. c. Pedro quiere el coche que vimos ayer.

´ındice

3

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (II) Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

4

Sintagma nominal (noun phrase) Van cabezados por nombres.

en-

El perro triste que me encontr´ e ayer en la calle

Sintagma preposicional (prepositional phrase) Van encabezadas por una preposici´ on, y tienen un complemento sintagma nominal. para los ni˜ nos pobres de todo el mundo

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (III) Parcial Introducci´ on List.Trans. Memoria Otros

Sintagma verbal (verb phrase) Van encabezados por un verbo. En general, organiza todos los dem´ as elementos de la oraci´ on. Llegaremos a tiempo al cine

Formalismos

Sintagma adjetival (adjectival phrase) Van encabezados por adjetivos. Algoritmos

´ındice

5

especialmente seguro de s´ı mismo

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (IV) - Argumentos y adjuntos Adjuntos o modificadores • Modifican el significado de aquello que modifican. Parcial Introducci´ on List.Trans. Memoria Otros

• Generalmente lo hacen m´ as espec´ıfico, sin alterar su significado b´ asico. El libro sobre la mesa, Marchamos r´ apidamente • Puede haber cualquier n´ umero de ellos El libro rojo sobre la mesa con dibujos

Argumentos o complementos Formalismos • La interpretaci´ on del argumento viene completamente determinada por la cabeza a la que complementa. Algoritmos

discusi´ on con Juan sobre el men´ u • El n´ umero de complementos viene tambi´ en determinado. rey de Francia, retrato de Juan

´ındice

6

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (V)

Parcial

Sintagmas nominales Suelen comenzar con un determinante, seguido de un nombre y sus complementos.

Introducci´ on List.Trans. Memoria Otros

NP XXX

XXX X

especificador N’

  T  T

N complementos Formalismos

Ejemplo:

NP

  T  T

el N’

Algoritmos

  @  @

rey PP de F rancia

´ındice

7

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (VI) Parcial Introducci´ on List.Trans. Memoria Otros

Sintagmas nominales Opcionalmente, puede tener modificadores a la derecha o a la izquierda de la cabeza. Ejemplo:

NP

(( (((( TT ((((

el N’

Formalismos

  bb  b

mejor N’

  @  @

rey PP Algoritmos de F rancia

´ındice

8

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (VII)

Parcial Introducci´ on List.Trans. Memoria Otros

Sintagmas verbales Suelen comenzar con el sujeto (como especificador), seguido de un verbo y sus argumentos. Puede haber tambi´ en adjuntos. VP @@

NP V’

  T  T

V complementos

Formalismos

VP H

Ejemplo: Algoritmos

HH H

NP

V’

  bb  b

El ni˜ no come NP manzanas ´ındice

9

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (VIII) Parcial

Teor´ıa de la X-barra Introducci´ on List.Trans. Memoria Otros

XP XXX

XXX X

especificador X’

(((```` (((((( ``` ( ( ( ( ( ` (

Formalismos

modificador izdo. X’ ``` `

``` `

modificador dcho. X’

  T  T

Algoritmos

´ındice

10

X complementos

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

11

Introducci´ on (IX) • Abney (1991) propuso implementar an´ alizadores completos como una cascada de peque˜ nos analizadores. • Cada uno puede especializarse en detectar un tipo particular de constituyente: sintagmas nominales, verbos compuestos, cuantificadores, sintagmas adjetivales, etc. • Previamente, Church (1988) hab´ıa construido a mano un detector de sintagmas nominales.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Introducci´ on (X)

Parcial Introducci´ on List.Trans. Memoria Otros

NP chunking • Sintagma nominal b´ asico: sintagma nominal no recursivo y sin solapamiento. • NP chunking: identificaci´ on de sintagmas nominales b´ asicos en un texto. S

(((( ((((((( @ (((((( @

NP Formalismos

VP

(((aa ((((( ( ( aa ( ( ((

Yo he visto NP PPP

PPP

Algoritmos

NP

PP

  @  @

un hombre con NP un telescopio ´ındice

12

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial Introducci´ on List.Trans. Memoria Otros

Listas de transformaci´ on (I) (Ramshaw and Marcus, 1995) • Lista de reglas usada para clasificar objetos en distintas clases. • Las reglas se aplican en orden, de modo que los efectos de una regla influyen en las siguientes.

Formalismos

Algoritmos

´ındice

13

⇒ ¡¡¡Igual que las utilizadas en etiquetado de las partes del lenguaje!!!

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Listas de transformaci´ on (II)

Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

14

Representaci´ on del problema † Las palabras ser´ an clasificadas en tres conjuntos, llamados I, O y B. • I todas aquellas palabras que est´ an dentro de un sintagma nominal b´ asico. • O todas aquellas palabras que est´ an fuera de un sintagma nominal b´ asico. • B todas aquellas palabras que est´ an al comienzo de un sintagma nominal b´ asico, siempre y cuando la palabra anterior est´ a al final de otro sintagma nominal. Ejemplo [Dio] a [Francisca] [un abrazo] Dio/I a/O Francisca/I un/B abrazo/I Procesamiento de Lenguaje Natural 2004 - LATEX slides

Listas de transformaci´ on (III) Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

15

Procedimiento 1. Aprender una Lista de Transformaci´ on para etiquetar cada palabra con una de las tres etiquetas, {I, O, B}. 2. Cada palabra recibir´ a inicialmente una etiqueta. Por ejemplo consideramos que todos los nombres, pronombres, adjetivos y determinantes constituyen por s´ı mismos sintagmas nominales. 3. Cada regla, en funci´ on de la palabra actual, las palabras que la rodean, y sus etiquetas decidir´ a si se cambia la etiqueta o no.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Listas de transformaci´ on (IV) Ejemplo El hombre dio a un amigo un regalo Parcial Introducci´ on List.Trans. Memoria Otros

El/I hombre/I dio/O a/O un/I amigo/I un/B regalo/I

Etiquetado inicial: El hombre dio a un amigo un regalo El/I hombre/B dio/O a/O un/I amigo/B un/B regalo/B

Formalismos

Regla: Si la palabra actual es un nombre com´ un etiquetado como B, y va precedido por un determinante, cambiar la etiqueta del nombre a I.

Algoritmos

Resultado: El hombre dio a un amigo un regalo El/I hombre/I dio/O a/O un/I amigo/I un/B regalo/I

´ındice

16

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Listas de transformaci´ on (V) Algoritmo de aprendizaje Parcial

Inicializar las etiquetas IOB.

Repetir Introducci´ on List.Trans. Memoria Otros

Formalismos

• Sea x un ejemplo arbitrario con la etiqueta err´ onea. • Generar todas las reglas que arreglan la etiqueta de x • Para cada una de ellas, calcular la mejora que producir´ıa aplicada a la totalidad del corpus: Ganancia(r) = Errs arreglados − Errs producidos • Tomar la regla Best que maximiza la ganancia.

Algoritmos

• A˜ nadir Best al final de la Lista de Transformaci´ on, y aplicarla a los datos de entrenamiento • Recalcular el conjunto de ejemplos a´ un no cubiertos por la Lista de Transformaci´ on.

´ındice

17

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Listas de transformaci´ on (VI) Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmo de etiquetado 1. Inicializar las etiquetas IOB. 2. Para cada regla r de la lista, • Aplicarla al texto. 3. Devolver el texto anotado.

Algoritmos

´ındice

18

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Listas de transformaci´ on (VII) Evaluaci´ on Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

19

N P s correctos encontrados P recision = N P s encontrados Recall =

N P s correctos encontrados N P s totales

(β 2 + 1) · P · R F (β) = β2 · P + R

Correcta: El hombre dio a un amigo un regalo Obtenida: El hombre dio a un amigo un regalo Precision = 0.5, Recall = 0.33, F(1) = 0.4 Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

20

Aprendizaje basado en memoria (I) (Argamon, 1998; Veenstra, 1998; Tjong Kim Sang, 1999) • Se almacena en memoria todo el corpus de entrenamiento, ya etiquetado. • A la hora de encontrar sintagmas nominales b´ asicos en un texto nuevo, se buscan fragmentos similares del corpus de entrenamiento. → se pueden usar heur´ısticas para escoger entre varias opciones. • Cada fragmento se etiqueta igual que alguna de sus apariciones en el corpus.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Aprendizaje basado en memoria (II) Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

21

• El aprendizaje es muy r´ apido (simplemente cargar el corpus de entrenamiento). • Ocupa mucha m´ as memoria que las listas de transformaci´ on. • Se puede implementar con algoritmos de b´ usqueda muy r´ apidos, pero nunca puede igualar a las listas de transformaci´ on (que se pueden compilar como aut´ omatas finitos, que se ejecutan en tiempo lineal).

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Otros procedimientos (I) Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Algoritmos

´ındice

22

• Aprendizaje de gram´ aticas para sintagmas nominales (Cardie y Pierce, 1998). • Redes neuronales (Mu˜ noz, 1999). • Combinaci´ on de los anteriores (Tjong Kim Sang, 2000) • Support Vector Machines (Kudo, 2001) Todos ellos han ido aumentando la F-score(β = 1) de 92.03% (Ramshaw y Marcus, 1994) a 94.22% (Kudo, 2001).

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Otros procedimientos (II)

Parcial Introducci´ on List.Trans. Memoria Otros

Formalismos

Otra posibilidad es subdividir la identificaci´ on de sintagmas nominales a´ un m´ as, en varios chunkers diferentes: 1. Identificaci´ on de expresiones cuantificadoras. 2. Identificaci´ on de sintagmas adjetivales. 3. Identificaci´ on de los sintagmas nominales. Aplicado al aprendizaje con listas de transformaci´ on, y entrenado en un corpus depurado, se consigue una F(β = 1) de 94.94% utilizando un PoS-tagger basado en cadenas de Markov.

Algoritmos

Tambi´ en puede utilizarse para localizar otros tipos de constituyentes, como verbos compuestos ´ındice

23

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial Introducci´ on List.Trans. Memoria Otros

Otros procedimientos (III)

Formalismos

Demostraci´ on

Algoritmos

´ındice

24

Procesamiento de Lenguaje Natural 2004 - LATEX slides

´ Indice

• An´ alisis parcial

• Formalismos

• Algoritmos de an´ alisis

25

• • • • • • • • • • • • • • •

Introducci´ on Listas de transformaci´ on Aprendizaje basado en memoria Otros sistemas CFG DCG HPSG PCFG Otros Introducci´ on Top-down Bottom-up Shift-reduce Left-corner Chart parsing

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (I) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

26

Una gram´ atica independiente del contexto G est´ a formada por: • Un conjunto de s´ımbolos terminales T (en el caso del lenguaje, son las palabras). • Un conjunto de s´ımbolos no terminales N , que representan los diferentes tipos de constituyentes. • Un s´ımbolo inicial S. • Un conjunto de reglas de producci´ on, que indican las maneras en que podemos derivar oraciones v´ alidas a partir del s´ımbolo inicial.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (II) Parcial

Ejemplo Formalismos CFG DCG HPSG PCFG Otros

S ::= NP VP NP ::= DT NNS | DT NN VP ::= VB NP | VB DT ::= los | un NNS ::= ni~ nos | hombres VB ::= comen | cantan | miran NN ::= kiwi | canto | coche

Algoritmos

´ındice

27

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

Context-Free Grammars (III) Utilizando las reglas de la gram´ atica, podemos derivar oraciones: • Una regla se aplica sustituyendo el s´ımbolo que aparece en la parte izquierda por los que aparecen en su parte derecha. S ⇒ NP VP • Una derivaci´ on es la aplicaci´ on sucesiva de reglas hasta obtener una expresi´ on que s´ olo contiene s´ımbolos terminales.

Algoritmos

´ındice

28

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (IV) Ejemplo Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

29

S ⇒ NP VP ⇒ DT NNS VP ⇒ los NNS VP ⇒ los ni~ nos VP ⇒ los ni~ nos VB NP ⇒ los ni~ nos miran ⇒ los ni~ nos miran ⇒ los ni~ nos miran ⇒ los ni~ nos miran

NP DT NN un NN un coche

Podemos abreviar la derivaci´ on: S ⇒? los ni~ nos miran un coche Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (V) Ejemplo Parcial

Formalismos CFG DCG HPSG PCFG Otros

La manera en que se ha realizado la derivaci´ on se puede capturar con un ´ arbol de derivaci´ on sint´ actica: S ⇒? los ni~ nos miran un coche S

  aaa a 

NP   ee

DT NNS

VP !!bb !! b

VB

NP " "" ee

Algoritmos

los ni˜ nos miran DT NN un coche

´ındice

30

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

Context-Free Grammars (VI) Lenguaje generado por una gram´ atica Se dice que una gram´ atica G genera una cadena s si S⇒?s El lenguaje generado por una gram´ atica G se define como L(G) = {sT ∗|S⇒?s}

Algoritmos

´ındice

31

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (VII) Ambig¨ uedad S ::= NP VP NP ::= PName NP ::= whisky NP ::= the rocks NP ::= NP PP PP ::= on NP

Parcial

Formalismos CFG DCG HPSG PCFG Otros

VP ::= V NP VP ::= V VP ::= VP PP PName ::= Peter V ::= drinks

S

S

((b ((((( bb (((((

((b ((((( bb (((((

NP

VP

PName V

NP

  HHH    H

Peter drinks

XXX  XXX  X

PName

VP

PP

bb  b

Peter NP

Algoritmos

VP

NP

((b (((( bb ((((

PP

  e  e

whisky on

  e  e

on V

NP

drinks whisky

NP the rocks

NP the rocks ´ındice

32

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (VIII) Utilidad Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

33

• Generaci´ on de texto, para... – Gu´ıas de museos. – Sistemas de recomendaci´ on. – Interfaces de di´ alogo. – etc. • An´ alisis de texto, para... – Correctores gramaticales – Generaci´ on de res´ umenes – B´ usqueda de respuestas a preguntas – Extracci´ on de Informaci´ on – etc.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Context-Free Grammars (X) Problemas Parcial

Para a˜ nadir concordancia, habr´ıa que multiplicar el n´ umero de reglas por todas las posibilidades de concordancia:

Formalismos

S ::= NP 1sg VP 1sg S ::= NP 2sg VP 2sg S ::= NP 3sg VP 3sg S ::= NP 1pl VP 1pl S ::= NP 2pl VP 2pl S ::= NP 3pl VP 3pl VP 1sg ::= VB intrans 1sg VP 1sg ::= VB trans 1sg NP VP 1sg ::= VB ditrans 1sg NP NP ...

CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

34

El n´ umero de reglas crece de forma exponencial sobre el n´ umero de caracter´ısticas que queremos incorporar a la gram´ atica. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

Definite-Clause Grammars (I) • Es igual que una CFG, pero permite generalizar las reglas. • Los no terminales pueden ser predicados de l´ ogica de primer orden, con argumentos. • En esos argumentos, se pueden codificar los par´ ametros para implementar concordancia y otros fen´ omenos ling¨ u´ısticos (movimiento, topicalizaci´ on, etc.)

Algoritmos

´ındice

35

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Definite-Clause Grammars (II) Ejemplo Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

S(Per,Num) ::= NP(Per,Num) VP(Per,Num) VP(Per,Num) ::= VB trans(Per,Num) NP( , ) NP(Per,Num) ::= PRON(Per,Num) NP(3,Num) ::= DT(Num), NN(Num) VB VB VB VB VB VB

trans(1, trans(2, trans(3, trans(1, trans(2, trans(3,

sg) sg) sg) pl) pl) pl)

::= ::= ::= ::= ::= ::=

como comes come comemos com´ eis comen

PRON(1, sg) ::= yo PRON(1, pl) ::= nosotros DT(sg) DT(pl) NN(sg) NN(pl)

::= ::= ::= ::=

el los ni~ no | pl´ atano ni~ nos | pl´ atanos

S ⇒? los ni~ nos comen el pl´ atano ´ındice

36

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Definite-Clause Grammars (III) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

37

• Cada regla en una DCG equivale a un n´ umero arbitrario de reglas de una CFG, que se obtienen sustituyendo las variables por cualquier combinaci´ on de constantes. • El lenguaje generado por una DCG es el lenguaje generado por esas reglas CFG. • El n´ umero de reglas CFG a que equivale una DCG puede ser infinito (por ejemplo, si un argumento es num´ erico y admite cualquier valor). ⇒ La clase de lenguajes que se pueden representar con una DCG es estrictamente mayor que con una CFG.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Definite-Clause Grammars (IV) Ejemplo con tiempos y casos Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

38

S(Per,Num) ::= NP(Per,Num, ,nom) VP(Per,Num, ) VP(Per,Num,Tiempo) ::= VB trans(Per,Num,Tiempo) NP( , , ,acc) NP(Per,Num,Gen,Caso) ::= PRON(Per,Num,Gen,Caso) NP(3,Num,Gen,Caso) ::= DT(Num,Gen), NN(Num,Gen) VB VB VB VB VB VB

trans(1, trans(2, trans(3, trans(1, trans(2, trans(3,

sg, sg, sg, pl, pl, pl,

pres) pres) pres) pres) pres) pres)

::= ::= ::= ::= ::= ::=

como comes come comemos com´ eis comen

PRON(1, sg, , nom) ::= yo PRON(1, sg, , acc) ::= me PRON(1, pl, , nom) ::= nosotros DT(sg, DT(pl, NN(sg, NN(pl,

masc) masc) masc) masc)

::= ::= ::= ::=

el los ni~ no | pl´ atano ni~ nos | pl´ atanos

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Definite-Clause Grammars (V) Formalismos CFG DCG HPSG PCFG Otros

Demostraci´ on

Algoritmos

´ındice

39

Procesamiento de Lenguaje Natural 2004 - LATEX slides

HPSG (I) Introduction (I) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

40

Movimiento: Varios fen´ omenos ling¨ u´ısticos conllevan un movimiento de constituyentes: • Preguntas: el sintagma sobre el que se pregunta se mueve al comienzo. En ingl´ es, el auxiliar se adelanta tambi´ en: ¿A qui´ eni viste ti en el teatro? Whomi did you see ti at the theatre? • Topicalizaci´ on: Este libroi, yo loi quiero. This booki, I want ti. El constituyente que se ha movido deja una trace (huella) en el lugar donde se origin´ o. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

41

HPSG (II) Introduction (II) Papeles sem´ anticos: Los argumentos de nombs y verbos se pueden clasificar en funci´ on de los papeles sem´ anticos que realizan: • Agente: aquello que realiza una acci´ on. • Paciente: aquello sobre lo que se realiza una acci´ on. • Instrumento: aquello con lo que la acci´ on se lleva a cabo.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

HPSG (III) Introduction (III) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

En general, el papel que realiza un constituyente vendr´ a determinado por la funci´ on sint´ actica que realiza. Enviar • sujeto = agente • objeto = paciente • objeto indirecto = receptor Recibir • sujeto = receptor • objeto = paciente • pp(de) = agente Voz activa vs. pasiva

´ındice

42

Procesamiento de Lenguaje Natural 2004 - LATEX slides

HPSG (IV) Introduction (IV) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Subcategorizaci´ on: Los verbos se pueden clasificar seg´ un el n´ umero de argumentos que requieren, y su tipo. La mayor´ıa de los argumentos se representan con sintagmas nominales, pero hay excepciones. Algunos ejemplos son: • Comer necesita dos NPs: sujeto y complemento directo. Mafalda comi´ o la sopa

Algoritmos

• Dar necesita dos NPs (sujeto y complemento directo) y un PP(a) (complemento indirecto). Gustavo le dio el micr´ ofono a Peggy

´ındice

43

Procesamiento de Lenguaje Natural 2004 - LATEX slides

HPSG (V) Introduction (V)

Parcial

Subcategorizaci´ on: • Despojar necesita un NP (sujeto), un PP(a) (complemento indirecto) y un PP(de).

Formalismos CFG DCG HPSG PCFG Otros

Los orcos despojaron a los hobbits de su libertad • Decir necesita un NP (sujeto) y un S(that) (complemento directo). Dice la leyenda que el anillo se perdi´ o • Volverse necesita un NP (sujeto) y un adjetivo (predicativo). Grendel se volvi´ o loco.

Algoritmos

Se llama subcategorizaci´ on de un verbo a la descripci´ on de sus argumentos. ´ındice

44

Procesamiento de Lenguaje Natural 2004 - LATEX slides

HPSG (VI) Gram´ aticas lexicalizadas (I) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Una soluci´ on elegante para incorporar informaci´ on de movimiento y subcategorizaci´ on en la gram´ atica es proporcionarla para cada palabra. Ejemplos: v([vform:fin,tns:pres| ],np([per:3,num:sg,case:nom| ])) --> [sleeps].

She sleeps n([lex:plus|N],s([vform:bse,tns: ,comp:that| ]))

Algoritmos

--> [desire].

The desire that he be granted asylum

´ındice

45

Procesamiento de Lenguaje Natural 2004 - LATEX slides

HPSG (VII) Gram´ aticas lexicalizadas (II) Parcial

Formalismos CFG DCG HPSG PCFG Otros

• Ahora, la estructura de las oraciones las proporcionan las reglas que generan los s´ımbolos terminales (las palabras). • Las reglas entre s´ımbolos no terminales simplemente han de ir rellenando los argumentos de los terminales. s([Vform,TNS,comp:minus|V]) --> np(Subj), vp([Vform,TNS|V],np(Subj)). vp(V,Subj) --> v(V,Subj,np(Obj)), % transitive np(Obj).

Algoritmos vp(V,Subj) --> v(V,Subj,np).

´ındice

46

% intransitive

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

HPSG (VIII) Gram´ aticas lexicalizadas (III)

Demostraci´ on

Algoritmos

´ındice

47

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

HPSG (IX) • Feature Structure Grammars (FSG) son una formalizaci´ on de la gram´ atica lexicalizada. • Cada palabra tiene atributos y valores. • Se representa con una AVM (Attribute-Value Matrix)

Formalismos v([vform:fin,tns:pres| ],np([per:3,num:sg| ]),np( )) --> CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

48

[writes].

 lex  cat  vform  tns      subj     obj1



writes   verb   fin   pres    cat np     3  per  num sg  h i   cat np

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

HPSG (X) Head-Driven Phrase Structure Grammars (HPSG) • Estructuras de rasgos para representar las palabras. • Las reglas de la gram´ atica consisten en combinar las distintas estructuras, unificando los argumentos de unas palabras con las estructuras de otros constituyentes.

Algoritmos

´ındice

49

Procesamiento de Lenguaje Natural 2004 - LATEX slides

PCFG (I) Una gram´ atica independiente del contexto probabil´ıstica es: Parcial

• Un conjunto de s´ımbolos terminales T (palabras). • Un conjunto de s´ımbolos no terminales N .

Formalismos CFG DCG HPSG PCFG Otros

• Un s´ımbolo inicial S. • Un conjunto de reglas de producci´ on, Ni → G j donde Gj es una secuencia de s´ımbolos terminales y no terminales. • Un conjunto de probabilidades sobre las reglas P (Ni → Gj |Ni)

Algoritmos tal que ∀i

X

P (Ni → Gj |Ni) = 1

j

´ındice

50

Procesamiento de Lenguaje Natural 2004 - LATEX slides

PCFG (II) Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

51

• Hasta ahora, dada una oraci´ on, pod´ıamos obtener muchas derivaciones posibles, y nada nos permit´ıa discriminar entre ellas. • La probabilidad de una derivaci´ on sint´ actica es el producto de las probabilidades de todas las reglas que se han aplicado. • De este modo, podemos escoger el ´ arbol de derivaci´ on con la mayor probabilidad. • Las probabilidades se pueden estimar a partir de un corpus anotado.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

PCFG (III)

Parcial

S ::= NP VP PP ::= P NP VP ::= V NP VP ::= VP PP P ::= con V ::= vieron

1.0 1.0 0.7 0.3 1.0 1.0

NP NP NP NP NP NP

::= ::= ::= ::= ::= ::=

NP PP los astr´ onomos estrellas orejas telescopios espejos

0.4 0.1 0.18 0.18 0.1 0.04

S

Formalismos

XXX ((1.0 (((( XXX ( ( ( X ((

NP0.1 CFG DCG HPSG PCFG Otros

VPb0.7

bb

los astr´ onomos V1.0

NP

0.4 a aa   a

vieron NP0.18

PP 1.0 "

"" @@

estrellas con NP0.18 Algoritmos

orejas P = 1.0 × 0.1 × 0.7 × 1.0 × 0.4 × 0.18 × 1.0 × 0.18 = 0.0009072

´ındice

52

Procesamiento de Lenguaje Natural 2004 - LATEX slides

PCFG (IV)

Parcial

S ::= NP VP PP ::= P NP VP ::= V NP VP ::= VP PP P ::= con V ::= vieron

1.0 1.0 0.7 0.3 1.0 1.0

NP NP NP NP NP NP

::= ::= ::= ::= ::= ::=

NP PP los astr´ onomos estrellas orejas telescopios espejos

0.4 0.1 0.18 0.18 0.1 0.04

S

Formalismos

XXX ((1.0 (((( XXX ( ( ( X ((

NP0.1 CFG DCG HPSG PCFG Otros

VP

0.3 X XXX  XXX 

los astr´ onomos VP 0.7 !b

! !!

bb

PP 1.0 "

@ "" @

con V1.0

NP0.4

vieron

NP0.18 orejas

NP0.18 Algoritmos

estrellas P = 1.0 × 0.1 × 0.3 × 0.7 × 1.0 × 0.18 × 1.0 × 0.18 = 0.0006804

´ındice

53

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos CFG DCG HPSG PCFG Otros

Otros formalismos (I) Tree Adjoining Grammars (TAG) • Cada palabra se representa con la porci´ on del ´ arbol de derivaci´ on sint´ actica que le corresponde, con huecos para sus argumentos. • Analizar una frase consiste en combinar los ´ arboles asociados a cada una de las palabras de la frase unos con otros. • A cada ´ arbol se le pueden a˜ nadir probabilidades.

Algoritmos

´ındice

54

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Otros formalismos (I)

Parcial

Formalismos CFG DCG HPSG PCFG Otros

Algoritmos

´ındice

55

Combinatory Categorial Grammar (CCG) • Cada palabra se representa como el constituyente del cual es ra´ız (los verbos representan oraciones). • Adem´ as, para cada una se a˜ nade informaci´ on de los argumentos que le faltan por la derecha o por la izquierda. Un verbo transitivo ser´ıa: S\NP/NP • Para analizar una frase, se combinan las representaciones de las palabras de la frase unas con otras. • A cada posible representaci´ on de una palabra se le pueden a˜ nadir probabilidades. Procesamiento de Lenguaje Natural 2004 - LATEX slides

´ Indice

• An´ alisis parcial

• Formalismos

• Algoritmos de an´ alisis

56

• • • • • • • • • • • • • • •

Introducci´ on Listas de transformaci´ on Aprendizaje basado en memoria Otros sistemas CFG DCG HPSG PCFG Otros Introducci´ on Top-down Bottom-up Shift-reduce Left-corner Chart parsing

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Introducci´ on (I)

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner

• Un analizador sint´ actico busca posibles derivaciones de una frase a partir de la gram´ atica. • Un analizador es completo si para toda frase produce todas las derivaciones posibles de ese ´ arbol. • En el caso de gram´ aticas probabil´ısticas, puede interesarnos conocer tan solo los K an´ alisis m´ as probables. • En otro caso, a veces basta con conocer una sola derivaci´ on correcta.

Chart

´ındice

57

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Introducci´ on (II) Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce

El n´ umero de posibles derivaciones suele ser exponencial: Ejemplo: S ::= X | Y | λ X ::= aS Y ::= aS Hay 2n maneras de generar an con esta gram´ atica.

Left corner Chart

´ındice

58

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner

Analizador Top-down • Mantiene un conjunto de constituyentes que tiene que formar con las palabras de la oraci´ on. • Inicialmente, es el s´ımbolo inicial, S. • Va sustituyendo los constituyentes aplicando las reglas de la gram´ atica, hasta que genera las palabras buscadas. En ciertos momentos habr´ a que tomar una decisi´ on: 1. Cuando haya varias reglas con la misma parte izquierda (reglas aplicables). 2. El orden en el cual aplicar las reglas.

Chart

´ındice

59

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Analizador Top-down Ejemplo:

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner

Pendiente s np vp Pedro vp vp v np quiere np np comida λ

Palabras Pedro quiere comida Pedro quiere comida Pedro quiere comida quiere comida quiere comida quiere comida comida comida λ

Regla aplicada s ::= np vp np ::= Pedro vp ::= v np v ::= quiere np ::= comida

Chart

´ındice

60

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Analizador Top-down Parcial

Caracter´ısticas: Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner Chart

´ındice

61

• Si un camino de an´ alisis no lleva a la oraci´ on buscada, se hace backtracking y se intenta otro. • Un analizador top-down no termina nunca si la gram´ atica contiene reglas recursivas por la izquierda NP ::= NP PP, incluso aunque sean recursivas como combinaci´ on de varias reglas: NP ::= Det NN Det ::= NP ’s Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner

Analizador Bottom-up • Comienza con las palabras de la oraci´ on. • Si una sub-cadena de s´ımbolos coincide con la parte derecha de una regla, la reemplaza por la parte izquierda. • Se termina cuando se han reducido todas al s´ımbolo inicial, S. En ciertos momentos habr´ a que tomar una decisi´ on: 1. Cuando haya varias reglas con la misma parte derecha (reglas aplicables). 2. El orden en el cual aplicar las reglas.

Chart

´ındice

62

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Analizador Bottom-up Ejemplo:

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner

Pendiente Pedro quiere comida np quiere comida np v np np v np np vp np s np np v np np vp s

Regla aplicada np ::= Pedro v ::= quiere np ::= comida vp ::= v (intransitivo) s ::= np vp backtrack vp ::= v np (transitivo) s ::= np vp

Chart

´ındice

63

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos

Analizador Bottom-up Algoritmos

Introducci´ on

Caracter´ısticas: • Poco eficiente si hay mucha ambig¨ uedad l´ exica.

Top-down Bottom-up Shift-reduce Left corner Chart

´ındice

64

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Analizador Shift-reduce Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce

• Es un caso particular del bottom-up. • La lista de palabras pendientes se divide en dos tipos: completadas y originales. • Las operaciones se dividen en dos tipos: 1. shift: cuando una palabra original se transforma en un constituyente completado. 2. reduce: una operaci´ on entre palabras completadas.

Left corner Chart

´ındice

65

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Analizador Shift-reduce

Formalismos

Completadas Algoritmos

Introducci´ on Top-down

np np v np v np np vp s

Originales Pedro quiere comida quiere comida comida

Operaci´ on shift shift shift reduce reduce

Bottom-up Shift-reduce Left corner Chart

´ındice

66

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up

Analizador Left corner Definici´ on: un s´ımbolo A es left-corner de un s´ımbolo B si • A = B. • Existe una regla B ::= A .... • Existe un s´ımbolo C tal que A es left-corner de C y C es left-corner de B.

Shift-reduce Left corner Chart

´ındice

67

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Analizador Left corner Parcial

Ejemplos: Formalismos

S ::= NP VP NP ::= Det N VP ::= V PP | V NP

Algoritmos

Los siguientes son left-corners directamente por las reglas: lc(NP, S). lc(Det, NP). lc(V, VP). Los siguientes lo son por la propiedad transitiva:

Introducci´ on Top-down Bottom-up Shift-reduce Left corner Chart

´ındice

68

lc(Det, S).

Por ´ ultimo, todos son left-corner de s´ı mismos: lc(S, S). lc(NP, NP). lc(VP, VP). lc(Det, Det).

lc(PP, PP). lc(N, N).

lc(V, V).

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Analizador Left corner (III) Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce

• El analizador left-corner es un analizador bottom-up, pero la informaci´ on de left-corner se utiliza para reducir el n´ umero de decisiones equivocadas. • S´ olo se aplican las reglas cuyo primer elemento es un left-corner del constituyente que queremos reconocer. → ¿Por qu´ e?

Left corner Chart

´ındice

69

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Chart parsing (tabulated parsing) Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up

• Los algoritmos que hemos visto hasta ahora pueden tardar un tiempo exponencial en analizar una frase (dependiendo de la gram´ atica). • Es posible mejorarlo bastante utilizando programaci´ on din´ amica.

Shift-reduce Left corner Chart

´ındice

70

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Chart parsing (II) Forma Normal de Chomsky

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner Chart

´ındice

71

Una gram´ atica est´ a en Forma Normal de Chomsky si todas las reglas son de una de las siguientes dos formas: 1. Reglas binarias con s´ımbolos no terminales: A ::= B C 2. Reglas unarias que generan s´ımbolos terminales: A ::= w Teorema: Para toda CFG existe una gram´ atica equivalente en Forma Normal de Chomsky.

Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up Shift-reduce Left corner Chart

´ındice

72

Chart parsing (III) Algoritmo de Cocke-Kasami-Younger

El algoritmo CKY funciona del siguiente modo: 1. La gram´ atica debe estar en Forma Normal de Chomsky. 2. Define una funci´ on multiplicaci´ on, que toma dos conjuntos de no terminales A = {a1, ..., am} y B = {b1, ..., bn} y devuelve un conjunto G = {g1, ..., gk } tal que ∀gi∃aj A ∧ ∃bk Bsuch that[gi ::= aj bk ]G Por ejemplo, si NP pertenece a A y VP pertenece a B, entonces S pertenece a G, dado que S ::= NP VP es una regla de la gram´ atica. Procesamiento de Lenguaje Natural 2004 - LATEX slides

Parcial

Formalismos

Algoritmos

Introducci´ on Top-down Bottom-up

Chart parsing (IV) Algoritmo de CKY

3. Se crea una matriz de tama˜ no (n + 1)2, donde n es la longitud de la oraci´ on a analizar. 4. Se va completando la matriz, de modo que la casilla (i, j) es chart(i, j) = ∪i