1 calculando probabilidades (diapositivas adaptadas de j. eisner) n-gram models luis villaseñor...
TRANSCRIPT
1
Calculando probabilidades
(diapositivas adaptadas de J. Eisner)
N-gram modelsLuis Villaseñor Pineda
Laboratorio de Tecnologías del LenguajeCoordinación de Ciencias Computacionales,
Instituto Nacional de Astrofísica, Óptica y Electrónica
2
Breves sobre la probabilidad
¿Que quiere decir una probabilidad?
p(Jacinto primer lugar | cielo despejado) = 0.9
Comportamiento anterior? Certeza de una creencia?
3
p es una función sobre conjuntos de eventos
despejado
ganador
Todos los eventos
p(ganador | despejado) p(ganador, despejado) / p(despejado)
4
Algunas propiedades de p
• p() = 0 p(todos los eventos) = 1
• p(X) p(Y) para cualquier X Y
• p(X) + p(Y) = p(X Y) si X Y=
5
Deseamos identificar el idioma de un texto
“Horses and Lukasiewicz are on the curriculum.”
Está en inglés o en polaco?
Es parecido (=probable) al inglés? Es parecido (=probable) al polaco?
El espacio de eventos no son carreras son secuencias de caracteres (x1, x2, x3, … xn) donde xn = EOS (end of sentence)
6
Sea p(X) = probabilidad de que el texto esté en inglés Sea q(X) = probabilidad de que el texto esté en polaco ¿Qué probabilidad es mayor?
“Horses and Lukasiewicz are on the curriculum.”
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
Deseamos identificar el idioma de un texto
7
Aplicamos la regla de la cadena
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
= p(x1=h)
* p(x2=o | x1=h)
* p(x3=r | x1=h, x2=o)
* p(x4=s | x1=h, x2=o, x3=r)
* p(x5=e | x1=h, x2=o, x3=r, x4=s)
* p(x6=s | x1=h, x2=o, x3=r, x4=s, x5=e)* … = 0
4470/52108
395/ 44705/ 395
3/ 5
3/ 3
0/ 3
counts from Brown corpus
8
Debilitamos la dependencia
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
p(x1=h)
* p(x2=o | x1=h)
* p(x3=r | x1=h, x2=o)
* p(x4=s | x2=o, x3=r)
* p(x5=e | x3=r, x4=s)
* p(x6=s | x4=s, x5=e)* … = 7.3e-10 * …
4470/52108
395/ 4470
5/ 395
12/ 919
12/ 126
3/ 485
counts from Brown corpus
9
Aun mayor independencia
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
p(x1=h)
* p(x2=o | x1=h)
* p(xi=r | xi-2=h, xi-1=o)
* p(xi=s | xi-2=o, xi-1=r)
* p(xi=e | xi-2=r, xi-1=s)
* p(xi=s | xi-2=s, xi-1=e)* … = 5.4e-7 * …
4470/52108
395/ 4470
1417/14765
1573/26412
1610/12253
2044/21250
counts from Brown corpus
10
Simplificamos la notación
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
p(x1=h)
* p(x2=o | x1=h)* p(r | h, o)* p(s | o, r)* p(e | r, s)* p(s | s, e)* …
4470/52108
395/ 4470
1417/14765
1573/26412
1610/12253
2044/21250
counts from Brown corpus
11
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …) p(h | BOS, BOS)* p(o | BOS, h)* p(r | h, o)* p(s | o, r)* p(e | r, s)* p(s | s, e)* …
4470/52108
395/ 4470
1417/14765
1573/26412
1610/12253
2044/21250
counts from Brown corpus
Estas probabilidades son usadas para definir p(horses)
Simplificamos la notación
12
p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
t BOS, BOS, h
* t BOS, h, o
* t h, o, r
* t o, r, s
* t r, s, e
* t s, e,s
* …
4470/52108
395/ 4470
1417/14765
1573/26412
1610/12253
2044/21250
counts from Brown corpus
Simplificamos la notación
Estas probabilidades son usadas para definir p(horses)
13
Nuestro modelo de probabilidad
Trigram Model(en términos de
parámetros como t h, o, r and t o, r, s )
valores param
definiciónde p
determinar probabilidades de un evento
generamostexto aleatorio
14
Inglés vs. Polaco
Trigram ModelValores para el polaco
definiciónde q
calculamosq(X)
Valores para el inglés
definiciónde p
calculamosp(X)
15
¿Qué es la “X” en p(X)?
compare
• Un elemento de algún espacio de eventos implícito• e.g., carrera• e.g., frase
• ¿Qué pasaría si el evento es un documento completo?• p(texto)
= p(frase1, frase2, …)= p(frase1) * p(frase2 | frase1)* …
16
compare
• Supongamos que un evento es una secuencia de letras:
p(horses)
• Pero nosotros reescribimos p(horses) como p(x1=h, x2=o, x3=r, x4=s, x5=e, x6=s, …)
p(x1=h) * p(x2=o | x1=h) * …• ¿Qué significa la notación variable=value ?
¿Qué es la “X” en p(X)?
17
Variables Aleatorias
compare
• p(x1=h) • El evento es una secuencia de letras
• x1 es la primera letra en la secuencia
• p(número de soles=2) o sólo p(S=2)• El evento es una secuencia de 3 volados
• S es el número de soles• p(despejado=true) o sólo p(despejado)
• El evento es una carrera• despejado es verdadero o falso
Respuesta: variable es en realidad una función de eventos
18
Como aplicar estas ideas al tratamiento del lenguaje
Contar palabras, fonemas, caracteres, signos de puntuación, frases, etc. condicionados por un contexto anterior
¿para qué?
19
Identificación del lenguaje
Útil para motores de búsqueda Útiles para text-to-speech (como pronunciar el
nombre “Jan Lukasiewicz”?)
20
Otras más
Categorización de Textos Segmentación por tópicos Corrección ortográfica contextual
*esta es una prueba esta prueba es una
Reconocimiento de voz El pato maulla
Traducción automática
21
Traducción
151. In quale città si trova la Porta di Brandeburgo?
¿En cuál ciudad se encuentra la Puerta de Brandeburgo? ¿En qué ciudad la puerta de Brandeburgo se encuentra? #¿En qué pueblo se encuentra la Puerta de Brandeburgo? ¿En cuál ciudad halla la puerta de Brandeburgo?
22
Problemas al calcular los n-gramas
¿Qué pasa con los n-gramas que no hemos visto?
¿su probabilidad es cero? ¿qué pasa si les damos probabilidad cero?
¿Cómo lo resolvemos? “smoothing” / “discounting”
23
Ejemplifiquemos el problema
El caso de los bigramas:
Generalizamos a n-gramas:
24
Nuestro corpus
25
Probabilidades por bigrama
26
Primera solución: incrementar en 1 todos los contadores
27
Entonces tenemos
Recordando nuestra fórmula:
Agregamos 1 y normalizamos por el tamaño del vocabulario
28
Nuestros nuevos datos
29
Nuevas probabilidades
30
Nuevas probabilidades
31
¿Qué tanto cambio?
32
Otra solución: Witten-Bell
Usar la cuenta de cosas “vistas” para estimar la cuenta de las cosas “no-vistas”
¿Cuál es la probabilidad de ver un n-grama por la primera vez? Contemos el número de veces que vemos N-gramas por primera
vez en nuestro corpus
T – total de N-gramas N – número de tokens
33
Los valores son más razonables
34
Reconocimiento de voz en Diálogo
C: l'agence APT
A: oui bonjour c'est l'APT du... du Trentino bonjour
C: oui bonjour je voudrais faire un voyage dans le Trentin
A: oui
C: et je voudrais savoir ce que vous proposez comme... comme organisation toute
prête avec les voyages les réservations d'hôtels
A: ah oui bien sûr nous avons des offres des forfaits pour l'hiver et pour l'été en quelle
saison désirez-vous arriver
C: nous allons arriver au mois d'août donc en été
A: en été oui quelles exigences avez-vous vous avez des des préférences pour certaines
localités du Trentino
C: non non du tout c'est un voyage donc on sera deux adultes plus deux enfants
A: d'accord
35
Creación de un modelo de lenguaje
1 – experimentos del mago de Oz
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Corpus de transcripciones
2 – aprendizaje de un modelo de lenguaje
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52Pentat
euque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Modelofinal
Herramientasde cálculo
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Modelo inicial
Herramientasde adaptación
36
Producción de un modelo de lenguaje estadístico
Sensible al corpus de entrenamiento
Creación del
corpus
Cálculo
del modelo de
lenguaje
Adaptación del
modelo
Modelo de
Lenguaje
37
Problemática
Obtener modelos de lenguaje estadísticos minimizando el trabajo humano
únicamente necesario en la definición del vocabulario permitiendo el modelado del lenguaje oral
a través de la utilización de documentos de Internet
38
Ejemplos de los corpus Grace
Texto de estilo periodístico para el proyecto de evaluación de sistemas de etiquetado GRACE
WebFr (o WebFr1) 1.5 Millones de documentos del Web (febrero 1999)
NewsFr 440000 mensajes de los newsgroups (junio 1999)
WebFr4 5 Millones de documentos (diciembre 2000)
WebMex Resultado de la colaboración franco-mexicana
39
Tamaño del vocabulario
0
50000
100000
150000
200000
250000
Grace WebFr NewsFr WebFr4
Num
ero
de v
ocab
los
Estudio cuantitativo
Tamaño original de los datos
1
1000
1000000
1E+09
Grace WebFr NewsFr WebFr4
Tam
año
del
co
rpu
s
40 Mb
650 Mb
10 Gb
44 Gb
40
Crecimiento de la cantidad de datos disponibles
Corpus Tamaño originalTamaño
promedio de las páginas
Tamaño del texto en cada página
% de texto% de páginas francófonas
Tamaño útil
WebFr (02/99) 10 Gb 6.6 Kb 4.2 Kb 63% 73% ~4.5 GbWebFr4 (12/00) 44 Gb 8,5 Kb 3.6 Kb 43% 73% ~13 Gb
41
Estudio cualitativo
Representación proporcional de pronombres personales en:Grace, WebFr, NewsFr & WebFr4
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
je ou j' tu ou t' il, elle ouon
nous vous ils ouelles
Grace
WebFr
NewsFr
WebFr4
42
bonjour monsieur durand comment allez vous . Extracción de texto
Vocabulario
allez
bonjour
comment
monsieur
vous
Filtrado en bloques mínimos
<s>l ≥ 1 bonjour monsieur
comment allez vous </s>
l ≥ 2 <s> bonjour monsieur
comment allez vous </s>
l ≥ 3 comment allez vous </s>
l ≥ 4 Ø
Filtrado en bloques mínimos
43
Tamaño de los bloques mínimos
Hacer una elección óptima entre el volumen de datos y la representación en 3-gramas:
– el tamaño debe ser 3 dado que nosotros trabajamos con 3-gramas
– si escojemos 3 :comment allez-vous ?
– si escojemos 4 :bonjour comment allez-vous ?
– si escojemos 5 :bonjour monsieur comment allez-vous ?
nuestra 1er elección
nuestra elección final
44
La probabilidad de una palabra dado su antecedente se calcula como sigue :
En un texto « normal » esto conduce a una aproximación sobre las últimas palabras de los textos
En este caso, todas las probabilidades P( x | je voudrais) están mal estimadas dado que la cuenta del último « je voudrais » interfiere. Generalmente uno supone que sobre un gran corpus este problema es mínimo.
Problema del aprendizaje
)mm(
)mmm( )mm | m P(
21
321213 N
N
… … … … … c’est un grand lit que je voudrais
45
Si se considera el siguiente corpus de aprendizaje:
P( réserver | je voudrais ) = 0.5
El problema precedente aparece al final de cada bloque, y nosotros tenemos un gran número de bloques. Las probabilidades por lo tanto son equivocadas. Para resolverlo, nosotros utilizamos la siguiente fórmula con contadores diferentes:
P( réserver | je voudrais ) = 1
Problema con los bloques mínimos
)mm(
)mmm( )mm | m P(
212
3211213 N
N
<s> bonjour ici monsieur durand je voudrais réserver<s> c'est une chambre que je voudrais
462 – Agregado de palabras frecuentes
1 – Frecuencia de formas lexicales
Problema de las palabras desconocidas
WebFr
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
ABU
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
BDLex
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Vocabulariode la tarea
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Frecuencia de palabras
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Nuevovocabulario
+
47
5 – cálculo del modelo de lenguaje
Cálculo del modelo de lenguaje
WebFr
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
VocabularioFinal
Filtro deBloquesmínimos
Il mordait en ce moment de fort bon appétit dans un morceau de pain.Il en arracha un peu de mie pour faire une boulette.Il la lança railleusement par le vasistas d'une fenêtre sur laquelle il s'appuyait. Bien dirigée, la boulette rebondit presque à la hauteur de la croisée.Cet inconnu traversait la cour d'une maison située rue Vivienne, où.Cette exclamation échappait à un clerc appartenant au genre de ceu.Il mordait en ce moment de fort bon appétit dans un morceau de pain.Il en arracha un peu de mie pour faire une boulette.Il la lança railleusement par le vasistas d'une fenêtre sur laquelle il s'appuyait. Il en arracha un peu de mie pour faire une boulette.Il la lança railleusement par le vasistas d'une fenêtre sur laquelle il s'appuyait. Bien dirigée, la boulette rebondit presque à la hauteur de la croisée, Cet inconnu traversait la cour d'une maison.
Corpus de Bloques mínimos
Herramientasadaptadas
délissasses 1croquantes 42emmènerais 9emmènerait 26badgé 19badge 3439faillirent 52pentateuque 309tabloïde 17
tabloïds 117attendriraient 5agatisé 1portiques 1165accusais 18accusait 662bioclimats 4circonscriras 2
Modelode lenguaje
final
48
Desempeño de reconocedor
Tasa de reconocimiento dado eltamaño del corpus
35
40
45
50
55
60
65
70
75
2 6 10
14
18
22
26
30
34
38
42
46
Corpus en milliones de palabras
Tasa d
e
reco
no
cim
ien
to
WebFr
Grace
Geod
Grace 40.35%
mago de Oz 39.47%
145
~78%~88% con
bloques 5
Corpus de aprendizaje
Corpus de prueba
Num. de locutores
Num. de frasesNum. de palabras
WebFr1 CStar120 2 120 1127- ah bon alors c' est d' accord vous me la réservez au nom de monsieur martin
- pour quatre jours à partir de demain quel est le tarif
- ah à trois cent soixante eh bien je je préfère encore l'autre la première