1

Calculando probabilidades

(diapositivas originales 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 ventos no son carreras son secuencias de caracteres (x1, x2, x3, …) 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é el 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

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

12

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

13

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)

14

Nuestro modelo de probabilidad

Trigram Model(en términos de

parámetros como t h, o, r and t o, r, s )

paramvalores

definiciónde p

determinar probabilidades de un evento

generamostexto aleatorio

15

Inglés vs. Polaco

Trigram ModelValores para el polaco

definiciónde q

calculamosq(X)

Valores para el inglés

definiciónde p

calculamosp(X)

16

¿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)* …

17

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)?

18

Variables Aleatorias

compare

• p(x1=h) * p(x2=o | x1=h) * …• Un evento es una secuencia de letras

• x2 es la segunda letra en la secuencia

• p(númbero de soles=2) o sólo p(S=2)• El evento es una secuencia de 3 volados

• H ies el número de soles• p(despejado=true) o sólo p(despejado)

• El evento es una carreca• despejado es verdadero o falso

Respuesta: variable es en realidad una función de eventos

19

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é?

20

Identificación del lenguaje

Útil para moteores de búsqueda Útiles para text-to-speech (como pronunciar el

nombre “Jan Lukasiewicz”?)

21

Otras más

Categorización de Texto 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

22

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?

23

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

24

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

25

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

26

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

27

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

28

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

29

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

30

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

31

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

32

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

33

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

34

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

352 – 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

+

36

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

37

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

38

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”

39

Ejemplifiquemos el problema

El caso de los bigramas:

Generalizamos a n-gramas:

40

Nuestro corpus

41

Probabilidades por bigrama

42

Primera solución: incrementar en 1 todos los contadores

43

Entonces tenemos

Recordando nuestra fórmula:

Agregamos 1 y normalizamos por el tamaño del vocabulario

44

Nuestros nuevos datos

45

Nuevas probabilidades

46

Nuevas probabilidades

47

¿Qué tanto cambio?

48

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

49

Los valores son más razonables