Modelos del LenguajeModelos del Lenguaje

¿Qué es un ML?

Modelos basados en N-gramas

Modelos basados en Gramáticas

Propuesta de T.D

Modelos De LenguajeModelos De Lenguaje¿Qué es un modelo de lenguaje? Mecanismo para definir la estructura del lenguaje, es decir, para restringir adecuadamente las secuencias de unidades lingüísticas más probables.

En general son útiles en aplicaciones que exhiban una sintaxis y/o semántica compleja.Un buen ML solamente debería aceptar (con alta probabilidad) frases correctas y rechazar (o asignar baja probabilidad a) aquellas secuencias de palabras incorrectas.Modelos clásicos:

N-gramasGramáticas estocásticas

Modelos De N-gramasModelos De N-gramasP(W) se puede descomponer como:P(W) se puede descomponer como:

P(W) = P(W) = ΠΠnni=1...ni=1...nP(wP(wii|w|w11 ... w ... wi-1i-1)=)=

P(wP(w11) ) .. P(w P(w22|w|w11) ) .. P(w P(w33|w|w1 1 ww22) ) .... .... P(wP(wnn |w|w11 ..... .....

wwn-1n-1) )

Con N=2 tendremos Bigramas Con N=2 tendremos Bigramas

P(W) = P(wP(W) = P(w11) ) .. P(w P(w22|w|w11) ) .. P(w P(w33|| ww22) ) .... .... P(wP(wnn || wwn-1n-1) )

Con N= 3 tendremos Trigramas Con N= 3 tendremos Trigramas

P(W) = P(wP(W) = P(w11) ) .. P(w P(w22|w|w11) ) .. P(w P(w33|| ww2 2 ww11) ) .... .... P(wP(wnn || wwn-2n-2.. wwn-1n-1) )

Supongamos que el resultado de una decodificación acústica Supongamos que el resultado de una decodificación acústica asigna semejantes probabilidades a las frases:asigna semejantes probabilidades a las frases:

the{ }dogthe{ }dog

Si P(pig | the)=P(big | the) entonces la elección de una u otra Si P(pig | the)=P(big | the) entonces la elección de una u otra dependencia de la palabra dog.dependencia de la palabra dog.

P(the pig dog)=P(the). P(pig | the). P(dog | the pig)P(the pig dog)=P(the). P(pig | the). P(dog | the pig)

P(the big dog)=P(the). P(big | the). P(dog | the big)P(the big dog)=P(the). P(big | the). P(dog | the big)

como P(dog | the big)> P(dog | the pig) el modelo ayuda a como P(dog | the big)> P(dog | the pig) el modelo ayuda a decodificar la frase correctamente.decodificar la frase correctamente.

PigPigbigbig

Un ejemplo Un ejemplo

PROBLEMA:PROBLEMA:

Necesidad de un elevado numero de muestras de aprendizaje.Necesidad de un elevado numero de muestras de aprendizaje.

UnigramasUnigramas p(w)p(w) |Σ||Σ|BigramasBigramas p(wp(w22|w|w11)) |Σ||Σ|22TrigramasTrigramas p(wp(w33|w|w11ww22)) |Σ||Σ|33

Numero de parámetros excesivamente grande incluso con esta Numero de parámetros excesivamente grande incluso con esta simplificación.simplificación.Ejemplo:Ejemplo: |Σ||Σ|=5000 palabras, 125000 millones de trigramas.=5000 palabras, 125000 millones de trigramas.

Wall Street Journal: Corpus de 38 millones de palabras.Wall Street Journal: Corpus de 38 millones de palabras.

Test 1: 5000 palabras, 21% trigramas no vistos.Test 1: 5000 palabras, 21% trigramas no vistos.Test 2: 20000 palabras, 32% trigramas no vistos.Test 2: 20000 palabras, 32% trigramas no vistos.

Ventajas:Ventajas:

- Fácil implementación.- Fácil implementación.

- integración sencilla con el proceso acústico.- integración sencilla con el proceso acústico.

- Algoritmos eficientes de reconocimiento.- Algoritmos eficientes de reconocimiento.

- Aprendizaje automático.- Aprendizaje automático.

Inconvenientes:Inconvenientes:

- Son muy generales: Necesaria adaptación a aplicaciones.- Son muy generales: Necesaria adaptación a aplicaciones.

- Falta de muestras de aprendizaje.- Falta de muestras de aprendizaje.

✍Sólo captura relaciones a corta distancia.Sólo captura relaciones a corta distancia.

✍¿ Que se hace con los N-gramas que no aparecen en el ¿ Que se hace con los N-gramas que no aparecen en el entrenamiento?entrenamiento?

Estimación de las ProbabilidadesEstimación de las Probabilidades

Vamos a supones que el modelo de N-gramas se ha modelizado Vamos a supones que el modelo de N-gramas se ha modelizado con un autómata finito. con un autómata finito.

UnigramaUnigrama

ΣΣww11 ww33

ww22

Bigrama Bigrama ww1 1 ww22

ww1 1 ww22 ww2 2 ww33

ww33

Trigrama Trigrama ww1 1 ww2 2 ww33

Supongamos que se disponen de una muestra de Supongamos que se disponen de una muestra de entrenamiento, sobre la que se ha estimado un modelo de N-entrenamiento, sobre la que se ha estimado un modelo de N-gramas, representado como un autómata finito.gramas, representado como un autómata finito.

Sea q un estado del autómata, y sea c(q) el numero total e Sea q un estado del autómata, y sea c(q) el numero total e eventos (N-gramas) observados en la muestra cuando el eventos (N-gramas) observados en la muestra cuando el modelo se encuentra en el estado q.modelo se encuentra en el estado q.

Sea c(w|q) el numero de veces que ha sido observada la Sea c(w|q) el numero de veces que ha sido observada la palabra w en la muestra estando el modelo en el estado q.palabra w en la muestra estando el modelo en el estado q.

Sea P(w|q) la probabilidad de observación de la palabra w Sea P(w|q) la probabilidad de observación de la palabra w condicionada al estado q.condicionada al estado q.

Sea Sea ΣΣqq el conjunto de palabras observadas en la muestra el conjunto de palabras observadas en la muestra cuando el modelo se encuentra en el estado q.cuando el modelo se encuentra en el estado q.

Sea Sea ΣΣ el vocabulario total del lenguaje a modelar. el vocabulario total del lenguaje a modelar.

ESTIMACION POR MAXIMA ESTIMACION POR MAXIMA VEROSIMILITUDVEROSIMILITUD

PPMLML(w|q)= (w|q)= c(w|q)c(w|q) c(q)c(q)

En un modelo de bigramas:En un modelo de bigramas:

PPMLML(w(wii|w|wi-1i-1)= )= c(wc(w i-1 i-1 ww ii)) c(wc(wi-1i-1 ))

Este criterio asigna a una probabilidad cero a los eventos no Este criterio asigna a una probabilidad cero a los eventos no vistosvistos

==> problemas de cobertura ==> problemas de cobertura

Una solución es suavizar el modeloUna solución es suavizar el modelo

Eventos No ObservadosEventos No Observados

nc(qw) el numero total de eventos que han sido observados c(qw) veces. C en numero total de eventos observados.La situación mas usual en Modelado del lenguaje es– n1 < C << n0 < numero total de eventos– Ejemplo:|Σ|=104 El número total de Bigramas es 108

C=106

Tipos de Suavizados:Plano, Lineal, No lineal, Back-off, Back-off sintáctico,bCoocurrencias.

MODELOS BASADOS EN MODELOS BASADOS EN GRAMÁTICASGRAMÁTICAS

Representan las restricciones del lenguaje de una Representan las restricciones del lenguaje de una manera naturalmanera natural

Permite modelar dependencias tan largas como se Permite modelar dependencias tan largas como se quieraquiera

la definición de estos modelos entraña gran la definición de estos modelos entraña gran dificultad para tareas que conlleven lenguajes dificultad para tareas que conlleven lenguajes próximos a lenguajes naturales (pseudo-naturales)próximos a lenguajes naturales (pseudo-naturales)

No es muy natural la integración con el modelo No es muy natural la integración con el modelo acústico.acústico.

Tipos de gramáticasTipos de gramáticas

Dada una gramatica G=(N,Dada una gramatica G=(N,ΣΣ,P,S),P,S)

V= N V= N ∪∪ ΣΣ; N ; N ∩∩ ΣΣ=; S =; S ∈∈ N N

((α →α → ββ) ) ∈∈ P P αα ∈∈VV++ ββ ∈∈ V* V*

Jerarquía de chomskyJerarquía de chomsky

0. No restringidas0. No restringidas

1. Sensibles al contexto 1. Sensibles al contexto

αΑβ → σΒβ α,βαΑβ → σΒβ α,β ∈∈ V* A V* A ∈∈N; B N; B ∈∈ V* V*

2 . Independientes del contexto2 . Independientes del contexto

Α → β α,βΑ → β α,β ∈∈ V* A V* A ∈∈N; B N; B ∈∈ V* V*

3. Regulares3. Regulares

Α → Α → a a Β ο Α → Β ο Α → a a Α,Β Α,Β ∈∈ N a N a ∈∈ ΣΣ

Gramáticas y Lenguajes Estocásticos Gramáticas y Lenguajes Estocásticos

Una Gramática estocástica es una pareja (G,Una Gramática estocástica es una pareja (G,pp))

Donde G es una gramática y p es una función p:PDonde G es una gramática y p es una función p:P→→ [0,1] [0,1]

Que posee la siguiente propiedad Que posee la siguiente propiedad

∀∀ A A ∈∈ N N ΣΣ P (A P (A→α→α)=1)=1

(A→α)∈ ΓA

Donde Donde ΓΓAA representa el conjunto de reglas de la gramáatica cuyo antecedente representa el conjunto de reglas de la gramáatica cuyo antecedente es Aes A

Un lenguaje Estocástico sobre un alfabeto Un lenguaje Estocástico sobre un alfabeto ΣΣ es un par ( es un par (LL,,ΦΦ) que ) que cumple las siguientes condiciones:cumple las siguientes condiciones:

1. 1. xx ∉∉ LL ⇒Φ⇒Φ(x) = 0 para todo x (x) = 0 para todo x ∈∈ ΣΣ**

2. 2. x x ∈∈ LL ⇒⇒ 0< 0< ΦΦ(x) <= 1 para todo x (x) <= 1 para todo x ∈∈ ΣΣ**

3. 3. Σ Σ x x ∈∈ LL ΦΦ(x) =1(x) =1

EjemploEjemploR1:R1: ¾¾ SS S SS S R2:R2: ¼¼ SS AA

R3:R3: 2/32/3 AA aAaA R3:R3: 1/31/3 AA aa

W= a a aW= a a a

D1: S D1: S R2

AAR3

aAaAR3

aaAaaAR4

aaa P(D1)=1/4* 2/3*2/3*1/3 = 4/108 aaa P(D1)=1/4* 2/3*2/3*1/3 = 4/108

D2: S D2: S R1

SSSSR2

SASAR3

SaASaAR4

SaaSaaR2

AaaAaaR4

aaa P(D2)= 6/1788aaa P(D2)= 6/1788

D3: S D3: S R1

SSSSR2

SASAR4

SaSaR2

AaAaR3

aAaaAaR4

aaa P(D2)= 6/1788aaa P(D2)= 6/1788

D4: S D4: S R1

SSSSR1

SSSSSSR2

SSASSAR4

SSaSSaR2

SAaSAaR4

Saa Saa R2

Aaa Aaa R4

aaa aaa

P(D2)= 9/27648P(D2)= 9/27648

P(aaa)= 4/108 + 6/1788 + 6/1788 + 9/27648 P(aaa)= 4/108 + 6/1788 + 6/1788 + 9/27648 ≈ 0.044 0.044

Gramáticas libres de contextos Gramáticas libres de contextos estocásticas en FNCestocásticas en FNC

Las reglas de la gramática tienen la forma:Las reglas de la gramática tienen la forma:

AA BC BC A,B,C A,B,C ∈∈ N N

AA a A a A ∈∈N, a N, a ∈∈ ΣΣ

Algoritmos desarrollados:Algoritmos desarrollados:

Probabilidad de una cadena: el Inside y el OutsideProbabilidad de una cadena: el Inside y el Outside

Probabilidad de la mejor derivación: Conteo de Probabilidad de la mejor derivación: Conteo de ViterbiViterbi

Estimación de probabilidades de cada regla: “inside-Estimación de probabilidades de cada regla: “inside-outside”outside”

COMENTARIOS:COMENTARIOS:

Todos los algoritmos anteriores se basan en técnicas de programación dinámica Todos los algoritmos anteriores se basan en técnicas de programación dinámica : algoritmo CYK: algoritmo CYK

Complejidad temporal: O(|X|Complejidad temporal: O(|X|3 3 |P| ) |P| )

donde |X| es la longitud de la cadena y |P| es el número de reglas.donde |X| es la longitud de la cadena y |P| es el número de reglas.

en el peor caso |P| es O(|N|en el peor caso |P| es O(|N|33 ) )

Complejidad Espacial: O(|X|Complejidad Espacial: O(|X|2 2 |P| )|P| )

Si no se tiene una gramática se puede definir una, usando todos las Si no se tiene una gramática se puede definir una, usando todos las combinaciones posibles de terminales y no terminales.combinaciones posibles de terminales y no terminales.

Sus altos costos han impedido su uso en tareas reales de modelado de lenguajes Sus altos costos han impedido su uso en tareas reales de modelado de lenguajes

No se hay propuestas claras de integración de la gramática con el modelo No se hay propuestas claras de integración de la gramática con el modelo acústico.acústico.

Pero son un modelo mucho más expresivo que los modelos n-gramasPero son un modelo mucho más expresivo que los modelos n-gramas

Recursos en InternetRecursos en Internet

CMU SML Toolkit. Carnie Mellon University: Es un conjunto de software unix diseñado para facilitar el trabajo en modelado del lenguaje. Básicamente permite hacer estadísticas sobre modelos clásicos como los bigramas y los trigramas.SRILM. The SRI languages Modeling Toolkit: SRILM es un toolkit para construir y aplicar modelos de lenguaje estadísticos, principalmente para el reconocimiento del habla, el etiquetamiento estadístico y la segmentación