PLN Modelos del lenguaje 1

Modelos Estadísticos del lenguaje

• Modelos del lenguaje (Language Models, LM)• Noisy Channel model• Modelos simples de Markov• Smoothing

PLN Modelos del lenguaje 2

Language Models 1

• Modelos estadísticos• Modelos del lenguaje (LM)• Vocabulario (V), palabra

• w V

• Lenguaje (L), oración • s L

• L V* normalmente infinito

• s = w1,…wN

• Probabilidad de s• P(s)

PLN Modelos del lenguaje 3

Noisy Channel Model 1

• Mecanismo de modelado estadístico de un canal de comunicación de mensajes en presencia de ruido

• Se pretende optimizar la calidad de la comunicación de mensajes a través del canal en presencia de ruido

• Compresión (eliminación de la redundancia) y calidad de la transmisión (conseguida introduciendo redundancia de forma controlada de forma que se pueda recuperar el mensaje original en presencia de ruido)

PLN Modelos del lenguaje 4

Noisy Channel Model 2

W X W*Yencoder decoderChannel

p(y|x)message

input to channel

Output fromchannel

Attempt to reconstruct message based on output

PLN Modelos del lenguaje 5

Noisy Channel Model 3

• Capacidad del canal (C): Nivel al que se puede transmitir información con una probabilidad pequeña de ser incapaz de recuperar la entrada a partir de la salida

•

• Alcanzamos la capacidad del canal si logramos diseñar un input code X con distribución estadística p(X) que maximice la I (información mutua) entre entrada y salida.

Y)I(X;max Cp(X)

PLN Modelos del lenguaje 6

Noisy Channel Model 4

• En PLN no podemos actuar sobre la fase de codificación (encoding). El problema es decodificar la salida para lograr la entrada más verosimil

i)|p(i)p(oargmax p(o)

i)|p(i)p(oargmax o)|p(iargmax I

iii

ˆ

decoderNoisy Channel p(o|I)

I O I

PLN Modelos del lenguaje 7

Noisy Channel Model 5

i)|p(i)p(oargmax p(o)

i)|p(i)p(oargmax o)|p(iargmax I

iii

ˆ

Modelo del lenguaje Probabilidad del canal

PLN Modelos del lenguaje 8

Noisy Channel Model 6

noisy channel X Y

lenguaje real X

lenguaje observado Y

Deseamos recuperar X a partir de Y

PLN Modelos del lenguaje 9

Noisy Channel Model 7

texto correcto

errores

texto con errores

noisy channel X Y

lenguaje real X

lenguaje observado Y

PLN Modelos del lenguaje 10

Noisy Channel Model 8

texto correcto

eliminación de espacios

texto sinespacios

noisy channel X Y

lenguaje real X

lenguaje observado Y

PLN Modelos del lenguaje 11

Noisy Channel Model 9

texto

pronunciación

habla

language model

acoustic model noisy channel X Y

lenguaje real X

lenguaje observado Y

PLN Modelos del lenguaje 12

Noisy Channel Model 10

árbol

inserción determinales

texto

probabilistic CFG

noisy channel X Y

lenguaje real X

lenguaje observado Y

PLN Modelos del lenguaje 13

Noisy Channel Model 11

lengua f

traducción

lengua o

noisy channel X Y

lenguaje real X

lenguaje observado Y

PLN Modelos del lenguaje 14

Noisy Channel model 12

Cadena acústica Cadena de palabras

Modelo del lenguaje Modelo acústico

ejemplo: ASR Automatic Speech Recognizer

PLN Modelos del lenguaje 15

Noisy Channel model 13

Modelo del lenguaje objetivo Modelo de la traducción

ejemplo: Traducción Automática

PLN Modelos del lenguaje 16

Implementación de LM

• Implementación intuitiva• Enumerar s L

• Calcular las p(s)

• Parámetros del modelo |L|

• Simplificaciones

• historia• hi = { wi, … wi-1}

• Modelos de Markov

PLN Modelos del lenguaje 17

Modelos de Markov simples 1

• Modelos de Markov de orden n+ 1

• P(wi|hi) = P(wi|wi-n+1, … wi-1)

• 0-grama

• 1-grama• P(wi|hi) = P(wi)

• 2-grama• P(wi|hi) = P(wi|wi-1)

• 3-grama• P(wi|hi) = P(wi|wi-2,wi-1)

PLN Modelos del lenguaje 18

Modelos de Markov simples 2

• n grande:• más información del contexto (más poder discriminativo)

• n pequeño:• más casos en el corpus de entrenamiento (más confianza)

• Selección de n: • ej. para |V| = 20.000

n num. parámetros

2 (bigrams) 400,000,000

3 (trigrams) 8,000,000,000,000

4 (4-grams) 1.6 x 1017

PLN Modelos del lenguaje 19

Modelos de Markov simples 3

• Parámetros de un modelo de n-grama• |V|n

• Estimación MLE• a partir de un corpus

• Problema sparseness

PLN Modelos del lenguaje 20

Modelos de Markov simples 4

• Modelo 1-gram

• Modelo 2-gram

• Modelo 3-gram

V

wCwPMLE

)()(

)(

)(),|(

12

1221

ii

iiiiiiMLE wwC

wwwCwwwP

)(

)()|(

1

11

i

iiiiMLE wC

wwCwwP

PLN Modelos del lenguaje 21

Modelos de Markov simples 5

PLN Modelos del lenguaje 22

Modelos de Markov simples 6

PLN Modelos del lenguaje 23

Modelos de Markov simples 7

Distribución real de probabilidad

PLN Modelos del lenguaje 24

Modelos de Markov simples 8

Los casos vistos están sobre estimados, los no vistos tienen probabilidad nula

PLN Modelos del lenguaje 25

Smoothing 1

• Métodos que actúan sobre el contaje de los n-gramas• Laplace, Lidstone, Jeffreys-Perks

• Métodos que actúan sobre las probabilidades:• Held-Out

• Good-Turing

• Descuento

• Métodos de combinación• Interpolación lineal

• Back Off

PLN Modelos del lenguaje 26

Smoothing 2

BN

)wC(w)w(wP n

nlaplace

11

1

P = probabilidad de un n-grama

C = contaje del n-grama en el corpus de entrenamiento

N = total n-gramas en el corpus de entrenamiento

B = parámetros del modelo (n-gramas posibles)

Laplace (add 1)

PLN Modelos del lenguaje 27

Smoothing 3

λBN

λ)wC(w)w(wP n

nLid

11

= número positivo pequeño

M.L.E: = 0Laplace: = 1Jeffreys-Perks: = ½

Lidstone (generalización de Laplace)

PLN Modelos del lenguaje 28

Smoothing 4

• Calcular qué porcentaje de la masa de probabilidad debe conservarse para los n-gramas no presentes en el corpus de entrenamiento

• Se reverva parte del corpus de entrenamiento como corpus de validación (otra parte es para test)

• Se calculan cuántos n-gramas ausentes del corpus de entrenamiento aparecen en el de validación

• Posibilidad de usar Cross-Validation

Held-Out

PLN Modelos del lenguaje 29

Smoothing 5

NN

TwwP

wwCT

r

rnho

rwwCwwnr

nn

)(

)(

1

})(:{12

111

Sea un n-grama w1… wn

r = C(w1… wn)

C1(w1… wn) frecuencia del n-grama en el training set

C2(w1… wn) frecuencia del n-grama en el held out set

Nr número de n-gramas con frecuencia r en el training set

Held-Out

PLN Modelos del lenguaje 30

Smoothing 6

r* = “frecuencia ajustada”

Nr = número de n-gram-types que aparecen r veces

E(Nr) = “valor esperado”

E(Nr+1) < E(Nr)

)(

)()1( 1*

r

r

NE

NErr NrPGT

*

Good-Turing

PLN Modelos del lenguaje 31

Smoothing 7

Primero se calcula la probabilidad de held-out.• Absolute discounting: Decrementar en una

pequeña constante la probabilidad de cada n-grama observado en el corpus de aprendizaje

• Linear discounting: Decrementar la probabilidad de cada n-grama observado en el corpus de aprendizaje multiplicándola por una cantidad.

Métodos de descuento

PLN Modelos del lenguaje 32

Smoothing 8

Combinación de métodos

• Combinación lineal de 1-grama, 2-grama, 3-grama, ...• Estimación de las mediante un corpus de validación

),|( 12 nnnli wwwP

),|()|()( 123112211 nnnnnn wwwPwwPwP

PLN Modelos del lenguaje 33

Smoothing 9

• Usar n-grama cuando hay suficientes casos en el corpus de entrenamiento, si no hacer back-off a n-1-grama

• Repetir en caso de necesidad

Katz’s Backing-Off

PLN Modelos del lenguaje 34

Enriquecimiento de los LM

• Actuación sobre la historia

• Modelos basados en clases• agrupación de palabras en clases

• Rosenfeld, 2000:• P(wi|wi-2,wi-1) = P(wi|Ci) P(Ci|wi-2,wi-1)

• P(wi|wi-2,wi-1) = P(wi|Ci) P(Ci|wi-2,Ci-1)

• P(wi|wi-2,wi-1) = P(wi|Ci) P(Ci|Ci-2,Ci-1)

• P(wi|wi-2,wi-1) = P(wi|Ci-2,Ci-1)

PLN Modelos del lenguaje 35

Structured Language Models

• Jelinek, Chelba, 1999• Inclusión de la estructura sintáctica en la historia

• Ti son las estructuras sintácticas • árboles binarios lexicalizados