Análisis probabilístico

PLN parsing probabilístico 1

Análisis probabilístico

• Introducción• SCFG• Algoritmo Inside• Algoritmo Outside• Algoritmo Viterbi• Aprendizaje de los modelos• Otras aproximaciones• La adquisición de las gramáticas:

• Inducción gramatical


Métodos probabilísticos 1

• Uso de preferencias estadísticas para• resolver ambigüedades

• guiar el proceso de análisis

• obtener el análisis más plausible

• Inducción gramatical a partir de corpus• Objetivo: Análisis de textos no restringidos con un

nivel aceptable de corrección (>90%) y de eficiencia.• Prerrequisitos:

• Corpus etiquetados (con POS): Brown, LOB, Clic-Talp

• Corpus analizados: Penn treebank, Susanne, 3LB



• Aproximaciones léxicas• No contextuales: unigram

• Contextuales: N-gram, HMM

• Aproximaciones gramaticales• SCFG

• Aproximaciones híbridas• Stochastic lexicalized Tags

• Cálculo del análisis más probable• Viterbi

• Estimación de los parámetros• Corpus etiquetado (aprendizaje supervisado)

• Corpus no etiquetado (aprendizaje no supervisado)• Baum-Welch (Fw-Bw) para HMM• Inside-Outside para SCFG



• Parsers robustos, precisos y de amplia cobertura (Charniak 1997, Collins 1997, Ratnaparkhi 1997, Charniak 2000)

• Convierten el parsing en una tarea de clasificación utilizando técnicas de ML

• Métodos Estadísticos para resolver las ambigüedades• Eficientes – A menudo coste lineal (usando beam search)• Producen LM que pueden integrarse en ASR


SCFG: Gramáticas CF probabilísticas

• Asociar una probabilidad a cada regla• Asociar una probabilidad a cada entrada léxica• Restricción frecuente CNF:

• Ap Aq Ar matriz Bpqr

• Ap bm matriz Upm

• Si deseamos encontrar el árbol de análisis más probable para una oración W sin generar todas las derivaciones posibles podemos recurrir al algoritmo de Viterbi


• Alguna idea de la probabilidad de un análisis• Pero no muy buena. No se tiene en cuenta, por ejemplo, la

coocurrencia léxica

• Las CFG no pueden aprenderse sin ejemplos negativos, las SCFG si

• Las SCFGs proporcionan un LM para una lengua• En la práctica las SCFG proporcionan un LM peor que

una 3-gram• P([N [N toy] [N [N coffee] [N grinder]]]) = P ([N [N [N cat] [N

food]] [N tin]])

• P (NP Pro) mayor en posición de sujeto que de objeto.

Pros y Contras de las SCFG 1


• Robustez• Posibilidad de combinación de SCFG con 3-grams• Las SCFG asignan demasiada masa de probabilidad a

las oraciones cortas (un árbol pequeño es más probable que uno grande)

• Estimación de los parámetros del modelo (probabilidades)

• Problema de la sparseness• Volumen: tratamiento computacional y desarrollo de

la gramática



• Asociación a la regla. Se pierde información sobre la aplicación de la regla en un punto concreto del árbol de derivación

• Penalización de las construcciones infrecuentes• Probabilidad de la derivación. Se asume

independencia contextual• Posibilidad de relajar las condiciones de

independencia:• Sensitividad a la estructura

• Lexicalización




• Sensitividad a la estructura• La expansión de un nodo depende de su posición en el árbol

Pronoun Lexical Subject 91% 9%

Object 34% 66%

• Enriquecimiento del nodo con información de su (s) antecesor (es)• SNP es diferente de VPNP

• Pronombres como Argumentos de los verbos ditransitivos• I gave Charlie the book

• I gave the book to Charlie

• I gave you the book

• ? I gave the book to you



• (Head) Lexicalization• put takes both an NP and a VP

• Sue put [ the book ]NP [ on the table ]PP

• * Sue put [ the book ]NP

• * Sue put [ on the table ]PP

• like usually takes an NP and not a PP• Sue likes [ the book ]NP

• * Sue likes [ on the table ]PP



Local Tree Come Take Think WantVP-> V 9.5% 2.6% 4.6% 5.7%

VP-> V NP 1.1% 32.1% 0.2% 13.9%

VP-> V PP 34.5% 3.1% 7.1% 0.3%

VP- V SBAR 6.6% 0.3% 73.0% 0.2%

VP-> V S 2.2% 1.3% 4.8% 70.8%

VP->V NP S 0.1% 5.7% 0.0% 0.3%

VP->V PRT NP 0.3% 5.8% 0.0% 0.0%

VP->V PRT PP 6.1% 1.5% 0.2% 0.0%



• Lexicalizar la SCFG: Swalked

NPSue VPwalked

Sue Vwalked PPinto

walked Pinto NPstore

into DTthe NPstore

the store


Analizadores probabilísticos

• Gramáticas incontextuales probabilísticas• Obtención del modelo

• aprendizaje supervisado• MLE sobre un treebank (ej. Penn Treebank)

• aprendizaje no supervisado• inside/outside

• aprendizaje semisupervisado

• Análisis: Viterbi

• Introducción del contexto• History Based Grammars

• Sistemas lexicalizados• Sistemas basados en técnicas de máxima

entropía

Charniak, 1993Krenn, Samuelson, 1997Manning, Schütze, 1999Rodríguez, 1999Lari, Young, 1990Pereira, Schabes, 1992Briscoe, Waegner, 1992

Black et al, 1993

Collins, 1996, 1997Magerman, 1995

Ratnaparkhi, 1998, 1999


Modelos Probabilísticos para Parsing 1

• Dos modelos• Modelo condicional :

• Estimamos directamente la probabilidad de un árbol de análisis

• Las probabilidades quedan condicionadas por una oración concreta.

• No se asume ninguna distribución de oraciones

1 G) s,|P(tcon G) s,|P(targmax t̂tt


Modelos Probabilísticos para Parsing 2

• Modelo generativo/conjunto :• Asigna probabilidades a todos los árboles generados por la

gramática. Las probabilidades son, pues, para el languaje L:

Σ{t:yield(t) L} P(t) = 1

G)|P(sG) s,|P(targmax G)|sP(t,argmax t̂tt


Gramáticas incontextuales probabilísticas (SCFG) 1

• CFG• SCFG

• para toda regla de la gramática G, (A ) PG debe poder definirse una probabilidad P(A )

• Probabilidad de un árbol

GPA

AP)(

1)(

);(

)(

)()(

Af

PA

AP

G

P


• P(t) -- Probabilidad del árbol (producto de probabilidades de las reglas que lo generan.

• P(w1n) -- Probabilidad de la oración es la suma de las probabilidades de los árboles que son análisis posibles de la oración

P(w1n) = Σj P(w1n, t) donde t es un análisis de w1n

= Σj P(t)




• Invariancia posicional:• La probabilidad de un subárbol no depende de la posición

en la oración de la cadena subsumida por la raiz del subárbol

• Independencia del contexto (Context-free):• La probabilidad de un subárbol no depende de las palabras

no subsumidas por la raiz del subárbol

• Independencia de los antecesores:• La probabilidad de un subárbol no depende de los nodos

en la derivación fuera del subárbol


Aprendizaje de las probabilidades

• Aprendizaje supervisado• el corpus de aprendizaje ha sido analizado y

consta de una colección de N árboles de análisis: {1, …, N} (Un treebank)

• Aprendizaje no supervisado• Inside/Outside (EM)

• Similar a Baum-Welch de HMM


Aprendizaje supervisado

GPA

A

AAP

)(

)(#

)(#)(

N

iiAfA

1

);()(#


SCFG en CNF 1

Aproximación más usual (alternativas en Charniak,1993 y Kupiek,1991)

Binary rules: Ap Aq Ar Se pueden almacenar en una matriz Bp,q,r

Unary rules: Ap bm Se pueden almacenar en una matriz Up,m

Se debe satisfacer:

A1 es el axioma de la gramática.d = derivación = secuencia de aplicaciones de reglas desde A1 a w:A1 = 0 1 ... |d| = w

1UB p,m

mp,rq,

rp,q,

|d|

1kk1k G)|p( G)|p(d

wA :d *

1

G)|P(dG)|p(w


SCFG en CNF 2

A1

Ap

Aq

As

Ar

w1 ... wi wk+1 ... wn

bm = wj

wi+1 ... ... wk


SCFG en CNF 3

• Problemas a resolver (~ HMM)• Probabilidad de una cadena (LM)

• p(w1n |G)

• Análisis más probable de una cadena

• arg maxt p(t | w1nG)

• Aprendizaje de los parámetros del modelo:• Encontrar G tal que maximice p(w1n |G)


HMM y SCFG

• HMM• Probability distribution over

strings of a certain length

• For all n: ΣW1n P(w1n ) = 1

• Forward/Backward • Forward

αi(t) = P(w1(t-1), Xt=i)

• Backward

βi(t) = P(wtT|Xt=i)

• PCFG• Probability distribution over the

set of strings that are in the language L

• Σ L P( ) = 1

• Inside/Outside• Outside

αj(p,q) = P(w1(p-1), Njpq,

w(q+1)m | G)

• Inside

βj(p,q) = P(wpq | Njpq, G)


Algoritmos Inside y Outside 1

A1

Ap

Aq Ar

outside

inside


Algoritmo Inside

Probabilidad Inside Ip(i,j) = P(Ap * wi+1 ... wj )Esta probabilidad puede calcularse bottom up empezando por los componentes más cortos

caso base:

IP(i,i+1) = p(Ap * wi+1) = Up,i+1

recurrencia:

rq,

1k

11jrp,q,rqp Bk)(j,Ij)(i,Ik)(i,I


Algoritmo Outside 1

Probabilidad Outside: Op(i,j) = P(A1 * w1 ... wi Ap wi+1 ... wj )Esta probabilidad puede calcularse top down empezando por los componentes más largos

caso base:

O1(0,n) = p(A1 * A1) = 1Oj(0,n) = 0, for j 1

Recurrencia: dos casos, sobre todas las particiones posibles

N

1p

N

1r

kin

1j

N

1p

N

1r

i

1jrp,q,rrp,q,r

q

Bi)j,(iIk)ij,Op(iBj)kik,(iIj)kiOp(i,

k)i(i,O


Algoritmo Outside 2

A1

Ap

Aq Ar

A1

Aq

w1 ... wi wi+k+1 ... wi+k+j wi+k+j+1... wn

w1...wi wi+k+1...wn

Dos formas de partir:primera

rp,q,rq Bj)kik,(iIj)kiOp(i,k)i(i,O


Algoritmo Outside 3

A1

Aq

w1...wi wi+k+1...wn

A1

Ap

Ar Aq

w1 ... wi-j wi-j+1 ... wi wi+k+1...wn

rp,q,rq Bi)j,(iIk)ij,Op(ik)i(i,O

segunda:


Algoritmo de Viterbi 1

O(|G|n3)Dada una oración w1 ... wn

MP(i,j) contiene la probabilidad máxima de la derivación Ap * wi+1 ... wj

La matriz puede calcularse de forma incremental para valorescrecientes de j - i mediante inducción sobre la longitud j - i

caso base:

MP(i,i+1) = p(Ap * wi+1) = Up,i+1

Ap

wj+1



Ap

Aq Ar

wi+1 ... wj wj+1 ... wi+k

j - i i + k - j k

Recurrencia:Considerar todas las formas en que Ap puede descomponerse en 2 componentes. Mantener la probabilidad máxima

Recordar que si en vez de calcularel máximo sumamos tenemos el algoritmoinside: p(w1n |G)

rq,p,rq

1ki

1ijrq,p Bk)i(j,Mj)(i,Mmaxmaxk)i(i,M



Para obtener la probabilidad de la mejor (más probable) derivation: MS(0,n)Para obtener el árbol de derivación más probable hay que mantener no sólo la probabilidad MP(i,j) sino también elpunto de corte y las dos categorías de la parte derecha de laregla Ap

ARHS1(p,i,k) ARHS2(p,i,k)

wi+1 ... wSPLIT(p,i,k) wSPLIT(p,i,k) +1 ... wk


Aprendizaje de los modelos 1

Parámetros (probabilities, i.e. matrices M y U) de un corpus

MLE (Maximum Likelihood Estimation): Aprendizaje Supervisado: Corpus totalmente analizado (con el árbol de derivación correcto para cada oración)

Aprendizaje no supervisado: Algoritmo Inside/Outside:Variante CFG del Forward/Backward (Baum, Welch) para HMM. Basado en EM (Expectation Maximization)

G)|AE(#

G)|AAAE(#)AA(Ap̂B̂

p

rqprqprp,q,



• Aprendizaje Supervisado:• Necesidad de treebanks como el Penn Treebank, Negra

o el 3LB

• Entrenamiento de los clasificadores.• Modelos probabilísticos

• Árboles de decisión

• Listas de decisión

• aprendizaje basado en transformaciones





Podemos formar el producto de probabilidades inside y outside:

Oi(j,k) Ii(j,k) = P(A1 * w1 ... wn, Ai * wj ... wk |G ) = P(w1n , Ai

jk |G)

Podemos reestimar los valores de: P(Ap Aq Ar ) y de P(Ap wm) y a partir de ellos los nuevos valores de Up,m y Bp,q,r



• Imaginemos que nuestro treebank contiene las siguientes oraciones:

S (1)

A A

a a

S (2)

B B

a a

S (3)

A A

f g

S (4)

A A

f a

S (5)

A A

g f



• Supongamos que (1) occurre 40 veces, (2) occurre 10 veces, (3) occurre 5 veces, (4) occurre 5 veces, y (5) occurre una vez.

• Deseamos una SCFG que refleje esta gramática.• ¿Qué parámetros maximizarían la verosimilitud de los

datos?Σj P(Ni ζj | Ni ) = 1



• ReglasS A A : 40 + 5 + 5 + 1 = 51

S B B : 10

A a : 40 + 40 + 5 = 85

A f : 5 + 5 + 1 = 11

A g : 5 + 1 = 6

B a : 10



• Parámetros que maximizan la verosimilitud counjunta:

G

S A A

S B B

A a

A f

A g

B a

Frecuencia

51

10

85

11

6

10

Total

61

61

102

102

102

10

Probabilidad

0.836

0.164

0.833

0.108

0.059

1.0



• Dados estos parámetros ¿cuál es el análisis más plausible para la cadena "a a"?

• P(1) = P(S A A) * P(A a) * P(A a)

= 0.836 * 0.833 * 0.833 = 0.580• P(2) = P(S B B) * P(B a) * P(B a)

= 0.164 * 1.0 * 1.0 = 0.164

S (1)

A A

a a

S (2)

B B

a a



• Aprendizaje no supervisado:• Corpus sin anotar (simple conjunto de oraciones)

• Algoritmo Inside/Outside

• Forma de EM

• Para cada oración, en cada iteración se calcula la Expectation de uso de cada regla usando las probabilidades Inside y Autside

• Asumimos que las oraciones son independientes

• Sumamos las expectations sobre análisis de cada una de ellas

• Reestimamos las probabilidades inside y outside basándonos en estos contajes


La adquisición de las gramáticas

• Análisis sintáctico sin utilizar gramática

• Gramática construida manualmente• Gramática inducida a partir de cero

• ej. Tree-bank Grammars

• Gramática inducida a partir de un núcleo inicial ya existente (o construido a mano)

• Transformación de gramáticas• Afinado de gramáticas

• Simplificación de gramáticas

DOP: Bod, 1995

Charniak, 1996

Krotov et al, 1999Sekine, 1998

Alvey: Grover et al, 1989CLE: Alsawhi, 1992TOSCA: Oostdijk, 1991

Briscoe, Waegner, 1992


DOP 1

• Data Oriented Parsing [Bod,95]

• Corpus de fragmentos de árbol con probabilidades asociadas

• [F [SN Juan] [FV [V quiere] [SP [PREP a] [SN Maria]]]] (1)

• [F [SN *] [FV [V quiere] [SP [PREP a][SN *]]]]

• [SN Maria]

• [SN Juan]

• [F [SN Pedro] [FV [V odia] [SP [PREP a] [SN Luisa]]]] (2)

• [F [SN *] [FV [V odia] [SP [PREP a][SN *]]]]

• [SN Luisa]

• [SN pedro


DOP 2

• Un conjunto de operaciones de combinación para obtener estructuras nuevas a partir de las existentes:

• [F [SN Maria] [FV [V quiere] [SP [PREP a][SN Luisa]]]]


Induccion gramatical

• Uso del algoritmo Inside/Outside para hacer inferencia gramatical. • (Lari,Young, 92,93) Kupiec, Cutting

• Problema: I/O tiende a agrupar las palabras por afinidad (información mutua) y no por estructura

• Pereira/Schabes 92 Corpus parcialmente parentizado• Problemas: entrenamiento, falta de conocimiento gramatical,

tamaño pequeño.

• Briscoe, Waegner, 92,93,94


Otras aproximaciones

• Markov grammars• Collins,1996, Magerman,1995

• Más que almacenar reglas explícitas, una MG almacena probabilidades que permiten generar las reglas sobre la marcha

• Decision tree parsers• Magerman,1995, Jelinek et al,1994

• Árboles de decisión history-based sin construcción manual de la gramática

• Goodman,1997 • Estadísticas de bigramas de los head-words en una gramática de

rasgos


Treebank grammars 1

• Gramáticas directamente derivadas de un treebank• Charniak,1996

• Uso del PTB • 47,000 oraciones

• Recorrido del PTB donde cada subárbol local proporciona las partes izquierda y derecha de una regla

• Precision y recall sobre un 80%• Unas 17,500 reglas

• Sekine,1997, Sekine & Grishman,1995• Compactación de Treebank grammars

• Crecimiento continuo del número de reglas• Krotov et al,1999, Krotov,1998, Gaizauskas,1995


Treebank grammars 2

• Sekine & Grishman,1995, Sekine,1997• Apple Pie parser

• Encontrar la estructura de una oración en el corpus• pero en PTB II: de 47,219 oraciones sólo 2,332 (4.7%) poseen exactamente la misma estructura

• Corpus-based probabilistic grammar with only 2 non-terminals (S and NP)

57.927.5% of instances covered by top 10 structures

98.177.2% of instances covered by structures of 2 or more occurrences

7114Number of structures which cover 50% of instances

9,71124,465Distinct structures

351,11388,921Total instances

NPSCategory


Treebank grammars 3

S NP VBX JJ CC VBX NP: structure “(S <1> (VP (VP <2> (ADJ <3>)) <4> (VP <5> <6>)))”

S

VP

VPVP

ADJ

NP NP

DT NN NN VBX JJ CC VBX DT JJ NNThis apple pie looks good and is a real treat


Treebank grammars 4

4,56532,296Total

2,0878,910NP

2,47823,386S

Grammar 2Grammar 0Category Grammar 0: directly induced from PTB IIGrammar 2: Remove rules occurring less than 2 times96% PTB for learning4% for testingG0 with backing off to G2 when no parse is generated:

Parseval recall 73.43%Parseval precision 72.61%

8.122.2421721,989G2

13.619.9293201,989G0

Run time (sec/sent)

Sentence length

Space exhausted

No parsesentencesGrammar


Treebank grammars 5

• Compactación de Treebank Grammars• Basado en DOP (tree depth =1)

• Partial bracketting• NP DT NN CC DT NN • NP NP CC NP • NP DT NN

• Eliminación de redundancia (reglas que pueden ser generadas por otras• => Compactación

• Algoritmo• Iterar hasta que no se puedan borrar más reglas

• Para cada regla en el TBG• Si la regla es redundante eliminarla


Treebank grammars 6

• Aplicación de la compactación• 17,529 1,667 reglas

• El tamaño de la gramática parece estabilizarse

10% corpus 60% 100%

#rules2000

1500


• Retención de las reglas lingüísticamente válidas• Asignar probabilidades (MLE) a las reglas iniciales

• Eliminar las reglas excepto cuando la probabilidad de la estructura creada con su aplicación sea mayor que mediante la aplicación de reglas más simples

• thresholding• Eliminación de las reglas que sólo ocurren n veces

6,4174,8201,1227,27815,421Grammar size

77.2172.1919.1877.6677.89precision

70.7671.5530.9370.7870.55Recall

Linguistically

Compacted

Grammar 2

Linguistically

Compacted

Grammar 1

Fully

compacted

Simply

thresholded

Full

Treebank grammars 7


Parsing LR Probabilístico 1

• Fuente: SCFG• Ng,Tomita,1991

• tabla LR table + factores estocásticos

• producto estocástico en tiempo de ejecución para guiar la búsqueda

• Podado de ramas

• problema: mantenimiento de la consistencia de la probabilidad • merging• splitting• L.A. packing

• Otras aproximaciones• Wright,1990

• Wright,Wrigley,1989


Parsing LR Probabilístico 2

• Problema: ¿cómo distribuir las probabilidades en la tabla LR ?

• Briscoe,Carroll,1993• LR parsing probabilístico con gramáticas de unificación

• CF Backbone Grammar

• Asignación de probabilidades directamente a tabla (no a las reglas)

• Corpus de entrenamiento: conjunto de LR parse histories (intervención humana para escoger la transición correcta en la tabla LR)

• Asignación de probabilidades a las acciones (tabla action)

• Asignación de probabilidades a las transiciones (tabla goto)


Modelos de Máxima Entropía 1

• Modelos exponenciales• [Chen et al, 1999], [Rosenfeld et al, 1999]

• Modelos de Máxima Entropía• [Rosenfeld, 1994], [Ratnaparkhi, 1998], [Ratnaparkhi, 1999], [Berger et

al, 1996], [Borthwick, 1997]

• Funciones (rasgos, features)


Modelos de Máxima Entropía 2Modelos de Máxima Entropía 2

• Para cada rasgo fi podemos considerar que sus valores fluctuarán de forma que su valor esperado (para la distribución de probabilidad teórica P) sea constante

• Normalmente los valores de Ki se calculan a partir de la distribución de probabilidad empírica que podemos obtener de un corpus de entrenamiento.

• Para cada rasgo fi podemos considerar que sus valores fluctuarán de forma que su valor esperado (para la distribución de probabilidad teórica P) sea constante

• Normalmente los valores de Ki se calculan a partir de la distribución de probabilidad empírica que podemos obtener de un corpus de entrenamiento.



• Lo que se trata ahora es de construir un modelo probabilístico que satisfaga el conjunto de restricciones (supuesto consistente) siendo tan próximo como sea posible a la distribución uniforme• en palabras de E. T. Jaynes, “it agrees with everything that is known but carefully

avoids assuming everything that is not known”

• proximidad de dos distribuciones• entropía relativa (o medida de Kullback-Leibler).

• Lo que se trata ahora es de construir un modelo probabilístico que satisfaga el conjunto de restricciones (supuesto consistente) siendo tan próximo como sea posible a la distribución uniforme• en palabras de E. T. Jaynes, “it agrees with everything that is known but carefully

avoids assuming everything that is not known”

• proximidad de dos distribuciones• entropía relativa (o medida de Kullback-Leibler).



• La distribución de probabilidad buscada, de entre las que satisfacen las restricciones es la que maximiza esta medida:

• Dentro de los modelos exponenciales existe una única solución a esa ecuación

• Los parámetros del modelo (las i) se calculan mediante Generalized Iterative Scaling

• La distribución de probabilidad buscada, de entre las que satisfacen las restricciones es la que maximiza esta medida:

• Dentro de los modelos exponenciales existe una única solución a esa ecuación

• Los parámetros del modelo (las i) se calculan mediante Generalized Iterative Scaling


Analizador de Ratnaparkhi 1Analizador de Ratnaparkhi 1

• Basado en Máxima Entropía• 4 procedimientos

• Tag• Chunk• Build• Check

• donde • X es uno de los procedimientos• a es una acción válida para dicho procedimiento• b es el contexto

• Basado en Máxima Entropía• 4 procedimientos

• Tag• Chunk• Build• Check

• donde • X es uno de los procedimientos• a es una acción válida para dicho procedimiento• b es el contexto

b)|(aPX



• Los rasgos aquí son funciones con dos parámetros, una acción y un contexto

• contextual predicates (cp) son predicados que examinan el contexto para verificar la presencia o ausencia de determinada información.

• Los rasgos aquí son funciones con dos parámetros, una acción y un contexto

• contextual predicates (cp) son predicados que examinan el contexto para verificar la presencia o ausencia de determinada información.

contrario caso en : 0

a' a y cierto (b) cp si :1b)f(a,



• Ratnaparkhi hace aprender su sistema a partir de un conjunto de templetas que se asocian a cada uno de los procedimientos

• Las templetas incorporan el tipo de factores que el autor considera relevante para el análisis:• Headwords de los constituyentes• Combinación de headwords• Generalizaciones (categorías morfosintácticas,

categorías sintácticas de los constituyentes)• Formas limitadas de look-ahead

• Ratnaparkhi hace aprender su sistema a partir de un conjunto de templetas que se asocian a cada uno de los procedimientos

• Las templetas incorporan el tipo de factores que el autor considera relevante para el análisis:• Headwords de los constituyentes• Combinación de headwords• Generalizaciones (categorías morfosintácticas,

categorías sintácticas de los constituyentes)• Formas limitadas de look-ahead



• En principio no tienen porqué establecerse límites sobre la localidad de la información consultada aunque en la práctica si se hace por motivos de eficiencia en el aprendizaje. • Por ejemplo, BUILD tiene asociadas templetas del tipo

cons(m), cons(m,n) y cons(m,n,p) donde los valores de m, n y p están limitados (por ejemplo, para cons(m,n,p) el rango de valores permitidos está limitado a (0,-1,-2), (0,1,2) y (-1,0,2)). Los valores asociados a estas templetas son etiquetas de constituyente, headword o categoría morfo-sintáctica de los árboles implicados.

• En principio no tienen porqué establecerse límites sobre la localidad de la información consultada aunque en la práctica si se hace por motivos de eficiencia en el aprendizaje. • Por ejemplo, BUILD tiene asociadas templetas del tipo

cons(m), cons(m,n) y cons(m,n,p) donde los valores de m, n y p están limitados (por ejemplo, para cons(m,n,p) el rango de valores permitidos está limitado a (0,-1,-2), (0,1,2) y (-1,0,2)). Los valores asociados a estas templetas son etiquetas de constituyente, headword o categoría morfo-sintáctica de los árboles implicados.



• El aprendizaje es muy simple: • se realiza por simple contaje de forma que los rasgos que

aparecen menos de 5 veces en el corpus se rechazan.

• Utilizando 40.000 oraciones del PTB se incorporaron al modelo 120.000 rasgos de tipo TAG, 230.000 de tipo CHUNK, 180.000 de tipo CHECK y 530.000 de tipo BUILD (la inmensa mayoría de ellos lexicalizados).

• El sistema produce unos resultados notables:• en términos de cobertura (85.3%) y precisión (87.5%).

• Queda abierta la posibilidad del examen manual de los rasgos inducidos y de la incorporación de otros criterios.

• El aprendizaje es muy simple: • se realiza por simple contaje de forma que los rasgos que

aparecen menos de 5 veces en el corpus se rechazan.

• Utilizando 40.000 oraciones del PTB se incorporaron al modelo 120.000 rasgos de tipo TAG, 230.000 de tipo CHUNK, 180.000 de tipo CHECK y 530.000 de tipo BUILD (la inmensa mayoría de ellos lexicalizados).

• El sistema produce unos resultados notables:• en términos de cobertura (85.3%) y precisión (87.5%).

• Queda abierta la posibilidad del examen manual de los rasgos inducidos y de la incorporación de otros criterios.


Analizadores estadísticos lexicalizados 1

• Dos tipos de estadísticos• Relación entre el head de un sintagma y la regla usada para

expandirlo:• p(r|h)

• r = regla, h = head

• Relación entre el head de un sintagma y el de un subcomponente:

• p(h|m,t)

• h = head del subcomponente, m =head del componente, t = tipo del subcomponente

• probabilidad de un árbol de análisis lexicalizado: • p(s,) = p(h(c)|m(c),t) . p(r(c)|h(c))


Analizadores estadísticos lexicalizados 2

• Otros estadísticos (útiles) • El tipo del padre condiciona la probabilidad de la regla

(Charniak,1997)

• Contexto izquierdo inmediato (Collins,1996)

• Clasificación de NP dentro de VP como opcional u obligatorio (Collins,1997)

• ...


Analizador de M. Collins 1

• analizador basado en SCFG.

• Donde OPT es el árbol de análisis más probable y

representa cualquier árbol de análisis de la oración s. Si se obtiene aplicando n reglas del tipo A para producir s, tendremos:

s), P(argmax s)| P(argmaxOPT

n

1iii

n

1ii )A|P()) P((As),P(



• Se lexicalizan las reglas de la gramática de forma que para cada regla la parte izquierda tiene asociada una palabra (head) aportada por uno de los componentes de la parte derecha.

• P componente padre, H núcleo, Li y Rj componentes a

izquierda (modificadores izquierdos) y derecha (modificadores derechos) del núcleo, h, head y li y rj

palabras asociadas a dichas componentes:• P(h) Ln(ln) … L1(l1) H(h) R1(r1) … Rm(rm)



• El modelo propuesto, lexicalizado, es inabordable y Collins lo descompone en tres modelos más simples que pueden ser aprendidos a partir del PTB y que nos generarían la parte derecha de la ecuación

• El primero es el que nos generaría el constituyente núcleo H con probabilidad dada una categoría P y una palabra núcleo h.

•



• A continuación se generarían los modificadores derechos a distancia i = 1, …, m+1 (donde Rm+1(rm+1) = STOP):

•

• condicionada ahora no sólo a P y h sino también a H • finalmente generación de los modificadores a la izquierda:

1m

1iiir H)h,P,|)(r(RP

1n

1iiil H)h,P,|)(l(LP



• ejemplo, la probabilidad asociada a la regla siguiente: • S(bought) NP(week) NP(Mark) VP(bought)

• Sería la siguiente:

VP)bought,S,|(STOPP

VP)bought,S,|(STOPPVP)bought,S,|(NP(week)P

VP)bought,S,|(NP(Mark)Pbought)S,|(VPP

h

ll

lh



• El analizador se entrenó con unas 40.000 oraciones del PTB

• Resultados de 87.4% de cobertura y 88.1% de precisión.• En Collins (1997) el modelo se mejora con información

lingüística sobre la distinción de complementos y adjuntos (modelo 2) y desplazamiento de constituyentes, concretamente de oraciones de relativo (modelo 3).

• Con ello se llega a 88.1% de cobertura y 88.6% de precisión.

Documents

Análisis probabilístico