Howard Wolowitz: ¡Se pone mejor! Alguien tiene que ir con el telescopio como especialista y adivinen quién es ese alguien.
Sheldon Cooper: Mohammed Lee.
(todo el mundo mira confundido)
Howard Wolowitz: ¿Quién es Mohammed Lee?
Sheldon Cooper: Mohammed es el nombre más común en el mundo, y Lee el apellido más común. Como yo no sabía la respuesta, pensé que me daría una ventaja matemática.
pueden verlo aquí: http://www.youtube.com/watch?v=IEiX_Aj5tVQ
¿Por qué está mal Sheldon Cooper?
Sheldon está utilizando el modelo de lenguaje probabilístico más simple que vimos: unigramas, las probabilidades por separado de cada palabra son altas pero la probabilidad conjunta es prácticamente cero, P(Lee | Mohammed ) ≈ 0
Esto nos lleva de nuevo a la pregunta: ¿Cómo lidiar con secuencias de palabras nunca antes vistas?, vimos una forma de resolver esto: Add-One Smoothing, (también conocido como Laplace Smoothing) pero no es realmente un método muy utilizado. Veamos otros:
Add-k Smoothing:
Padd-1(Wi | Wi-1) = count (Wi-1,Wi) +1
count (Wi-1) +|V|
Si lo generalizamos la fórmula para k: Add-k, será:
Padd-k(W | Wi-1) = count (Wi-1,Wi) +k
count (Wi-1) +k|V|
Padd-k(Wi | Wi-1) = count (Wi-1,Wi)+m(1/V)
count (Wi-1) + m
nota: V=|V| por simplificación
Si nos fijamos en Add-k smoothing, podemos ver que a cada "cantidad de bigrama" le estamos sumando 1/V, extendiendo esta idea y cambiando 1/V por la probabilidad del unigrama de wi, obtenemos un mejor modelo llamado: Unigram Prior Smoothing:
PunigramPrior(Wi | Wi-1) = count (Wi-1,Wi)+mP(Wi)
count (Wi-1) + m
A pesar de que este modelo funciona mejor que Add-k, sigue sin ser suficientemente bueno como otros modelos que voy a explicar a continuación: Good-Turing y Kneser-Ney.
Todos estos modelos tienen algo en común, le asignan una probabilidad dada a los bigramas que nunca vimos en el conjunto de entrenamiento. Pero en particular: Good-Turing y Kneser-Ney trabajan con la idea de considerar a los bigramas que nunca vimos como a todos aquellos que vimos al menos una vez. Voy a explicar mejor esta idea con un ejemplo. Pero antes déjenme explicar el concepto de frecuencia de frecuencia o Nc. ¿Qué es esto? Dada la siguiente secuencia de palabras:
tres tristes tigres, tres tristes tigres, tristes no comen trigo
veamos la frecuencia de los unigramas:
P(tristes) =3
P(tres) = 2
P(tigres) =2
P(comen) =1
P(trigo) =1
P(no) =1
La frecuencia de las cosas que aparecen 1 vez es 3 => N1=3
La frecuencia de las cosas que aparecen 2 veces es 2 => N2=2
La frecuencia de las cosas que aparecen 3 veces es 1 => N3=1
Sigo con el ejemplo:
Imaginemos un pescador en el río Paraná en un buen día, ya ha atrapado varios peces: 10 carpas, 3 bogas, 2 dorados, 1 pacú, 1 surubí y 1 anguila => total=18 pescados.
¿Cuál es la probabilidad de que el próximo pez que saque sea un surubí ? Bueno debe ser: 1/18....
pero entonces..
¿Cuál es la probabilidad de que el próximo pez sea de una especia nueva, por ejemplo un patí?
Acá vamos a usar la intuición detrás del algoritmo Good-Turing, la frecuencia de las cosas que vimos una sola vez es: 3. N1=3 (1 pacú, 1 surubí y 1 anguila) así que la posibilidad de que el próximo pez sea de una especie nueva será: 3/18.
Ajá.. ¿Cuál es la probabilidad de que el próximo pez que saque sea un surubí entonces? Ya no puede seguir siendo 1/18, tiene que ser menor.
Good Turing Smoothing:
PgoodTuring = N1/ N para las cosas que tienen cero ocurrencia (c=0)
PgoodTuring = c*/ N para las cosas que tienen ocurrencia mayor que cero
donde c* = (c+1) Nc+1 donde c es la cantidad de ocurrencias
Nc
En el ejemplo anterior, P(surubí ) = (1+1) N2 / N = 2*1 / 18 => (2/3) / 18 => 1/27
N1 3
Todos estos modelos tienen algo en común, le asignan una probabilidad dada a los bigramas que nunca vimos en el conjunto de entrenamiento. Pero en particular: Good-Turing y Kneser-Ney trabajan con la idea de considerar a los bigramas que nunca vimos como a todos aquellos que vimos al menos una vez. Voy a explicar mejor esta idea con un ejemplo. Pero antes déjenme explicar el concepto de frecuencia de frecuencia o Nc. ¿Qué es esto? Dada la siguiente secuencia de palabras:
tres tristes tigres, tres tristes tigres, tristes no comen trigo
veamos la frecuencia de los unigramas:
P(tristes) =3
P(tres) = 2
P(tigres) =2
P(comen) =1
P(trigo) =1
P(no) =1
La frecuencia de las cosas que aparecen 1 vez es 3 => N1=3
La frecuencia de las cosas que aparecen 2 veces es 2 => N2=2
La frecuencia de las cosas que aparecen 3 veces es 1 => N3=1
Sigo con el ejemplo:
Imaginemos un pescador en el río Paraná en un buen día, ya ha atrapado varios peces: 10 carpas, 3 bogas, 2 dorados, 1 pacú, 1 surubí y 1 anguila => total=18 pescados.
pero entonces..
¿Cuál es la probabilidad de que el próximo pez sea de una especia nueva, por ejemplo un patí?
Acá vamos a usar la intuición detrás del algoritmo Good-Turing, la frecuencia de las cosas que vimos una sola vez es: 3. N1=3 (1 pacú, 1 surubí y 1 anguila) así que la posibilidad de que el próximo pez sea de una especie nueva será: 3/18.
Ajá.. ¿Cuál es la probabilidad de que el próximo pez que saque sea un surubí entonces? Ya no puede seguir siendo 1/18, tiene que ser menor.
Good Turing Smoothing:
PgoodTuring = N1/ N para las cosas que tienen cero ocurrencia (c=0)
PgoodTuring = c*/ N para las cosas que tienen ocurrencia mayor que cero
donde c* = (c+1) Nc+1 donde c es la cantidad de ocurrencias
Nc
En el ejemplo anterior, P(surubí ) = (1+1) N2 / N = 2*1 / 18 => (2/3) / 18 => 1/27
N1 3
Veamos una tabla, con valores reales en donde se ve la cantidad original: "C", y la nueva cantidad que calcula Good Turing: "C*" para los bigramas que aparecen pocas veces:
Podemos ver que los nuevos valores se parecen a los originales, de hecho se les está descontando un número menor que uno a cada valor original. Para simplificar podríamos decir que a cada valor se le descuenta una cantidad fija: "0.75" y tendríamos una tabla bastante parecida. Esta idea es la que está detrás del siguiente algoritmo de Smoothing.
PabsoluteDiscounting(Wi | Wi-1 ) = count(Wi-1,Wi) -d + λ(Wi-1) P(W)
count(Wi-1)
donde "d" es una constante cualquiera, en el ejemplo anterior podría ser el 0.75
λ(Wi-1) es un término que depende de la palabra Wi-1, y lo veremos después
P(W) es la probabilidad del unigrama de W
donde "d" es una constante cualquiera, en el ejemplo anterior podría ser el 0.75
λ(Wi-1) es un término que depende de la palabra Wi-1, y lo veremos después
P(W) es la probabilidad del unigrama de W
Este método tiene un problema y es que utiliza la probabilidad del unigrama, que como dijimos al principio no siempre tiene sentido en un bigrama.
La probabilidad de continuación de una palabra W, es la probabilidad de que esa palabra sea la siguiente palabra después de Wi-1.
Pcontinuation(W) = ___|{Wi-1: count(Wi-1, W)>0}|__
|{(Wj-1,Wj): count(Wj-1, Wj)>0}|
Básicamente lo que dice esa ecuación es: la cantidad de tipos de palabra distintos que son precedidos por W divididos la cantidad de tipos de palabra distintos que pueden preceder a cualquier palabra. Esto es lo mismo que decir: la cantidad de bigramas.
Kneser-Ney Smoothing:
Reemplazando en la ecuación de Absolute Discounting, ahora nos queda:
count(Wi-1)
En donde λ(Wi-1) se calcula de la siguiente manera:
λ(Wi-1) = d |{W: count(Wi-1,Wi ) > 0}|
count(Wi-1)El último término es el mismo que usamos para calcular Pcontinuation, : la cantidad de tipos de palabra distintos que son precedidos por W. Este término está multiplicando a "d"
No hay comentarios:
Publicar un comentario