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