-
Hablemos acerca de Kneser-Ney Smoothing,
-
una de las formas más sofisticadas de suavizado,
-
pero también una con una intuición hermosa y elegante.
-
Recordemos que en Good-Turing, hablamos acerca de las C estrella,
-
que descontaban los conteos que resultaban de Good-Turing,
-
y descontabamos cada uno de los conteos ---
-
el conteo de uno fue descontado a .4
-
y el conteo de dos, descontado a 1.26 y así ---
-
para guardar masa para reemplazar el conteo de cero con algún número bajo.
-
Y si observamos los valores de estos conteos, 8.25 para el nueve y 7.24 para el ocho,
-
veremos que en una gran cantidad de casos,
-
el conteo descontado tiene una relación estrecha con el conteo original.
-
Es en realidad el conteo original menos .75, o algo por el estilo.
-
Entonces, en la práctica, lo que en general hace Good-Turing es producir una cantidad fija de pequeños descuentos de los conteos.
-
Y esa intuición, de un pequeño descuento fijo, puede aplicarse directamente.
-
Cuando hacemos esto, lo llamamos descuento absoluto, y el descuento absoluto es una forma popular de suavizado.
-
Y aquí mostramos interpolación con descuento absoluto.
-
Y otra vez, la intuición es eso: Ahorraremos tiempo y computaremos todos esos complicados números del Good-Turing
-
y solamente restaremos .75, o quizás será un descuento diferente para distintos corpus.
-
Ahora, aquí tenemos la ecuación para el descuento absoluto.
-
Entonces, hacemos bigramas de vuelta.
-
Entonces la probabilidad, con descuento absoluto, de una palabra dada la palabra anterior,
-
será un bigrama descontado, interpolado con algún peso de la interpolación, con la probabilidad del unigrama.
-
Entonces tenemos la probabilidad del unigrama P(w), y luego la probabilidad del bigrama,
-
y solamente restamos un valor fijo, como .75, del conteo.
-
Y computamos la probabilidad del bigrama de la forma normal.
-
Entonces, tenemos la probabilidad descontada del bigrama, mezclada con algún peso,
-
del cual hablaré mas tarde acerca de como ajustar éste peso, con un unigrama.
-
Y quizás mantendremos un par de valores extra de D para los conteos de uno y dos.
-
Conteos de uno y dos, como vimos anteriormente, no restaban exactamente .75,
-
entonces podemos modelar mas cuidadosamente teniendo conteos separados para ellos.
-
Pero el problema con el descuento absoluto es la probabilidad del unigrama por sí misma.
-
Y quiero hablar acerca de cambiar la probabilidad del unigrama.
-
Y esa es la intuición fundamental de Kneser-Ney.
-
Entonces en Kneser-Ney smoothing, la idea es mantener la misma interpolación que vimos en descuento absoluto,
-
pero usar una mejor estimación de las probabildades de los unigramas de menor orden.
-
Y la intuición para eso, podemos volver y mirar los clásicos juegos de Shannon.
-
Recuerden, en el juego de Shannon, estamos prediciendo una palabra en base a las anteriores,
-
entonces vemos una oración, "No puedo ver sin mis _ "
-
Cual es la palabra más probable?
-
Bueno, "lentes" parece bastante probable.
-
Bueno, que tal la palabra "Francisco"?
-
Bueno, parece bastante improbable en esta situación.
-
Sin embargo "Francisco", como unigrama, es más común que "lentes".
-
Pero la razón de porque "Francisco" parece una mala elección,
-
una intuición que podemos tener es que "Francisco" siempre le sigue a "San" o casi siempre le sigue a "San"
-
Entonces por más que "Francisco" sea muy frecuente, es frecuente en el contexto de la palabra "San".
-
Ahora, los unigramas en un modelo de interpolación, donde mezclamos unigramas y bigramas,
-
son especialmente útiles --- ayudan mucho --- sólo en el caso en el cual no vimos un bigrama.
-
Entonces es desafortunado que sólo en el caso en donde no vimos el bigrama "leyendo Francisco",
-
estamos confiando en el peso del unigrama "Francisco" y es justo donde no deberiamos confiar.
-
Entonces en vez de usar la probabildad de w, "que tan probable es una palabra"
-
nuestra intuición será que cuando volvamos a algo,
-
usaremos la probabilidad de continuación
-
La llamaremos "P continuación" de una palabra
-
que tan probable es que la palabra aparezca como una nueva continuación
-
Bueno, como medimos una continuación nueva?
-
Bueno, por cada palabra, contaremos el número de tipos de bigrama que complete.
-
Cuantos tipos diferentes de bigramas se crean al aparecer después de otra palabra.
-
En otras palabras, cada tipo de bigrama es una continuación nueva cada vez que vemos éste nuevo bigrama
-
En otras palabras, la probabilidad de continuación será proporcional a la cardinalidad de éste conjunto,
-
la cantidad de palabras que preceden otras, I - 1, que ocurren con nuestra palabra.
-
Entonces, que cantidad de palabras ocurren antes de ésta palabra en un bigrama.
-
Cuantas palabras precedentes hay.
-
Eso será la cardinalidad de ese conjunto, que será un número que querríamos que nuestra probabilidad de continuación le sea proporcional.
-
Cuantas veces aparece W como una nueva continuación?
-
Necesitamos transformar eso en una probabilidad
-
Entonces solo dividimos por la cantidad total de tipos de bigramas.
-
Entonces, de todos los bigramas que ocurren mas de cero veces, cual es la cardinalidad del conjunto?
-
Cuantas tipos de bigramas diferentes hay,
-
y solamente vamos a dividir los dos para obtener una probabilidad de continuación,
-
de todos los tipos de bigramas, cuantos de esos tiene a W como una continuación nueva?.
-
Ahora, resulta que hay una metáfora alternativa para Kneser-Ney con las mismas ecuaciones
-
entonces, otra vez podemos ver el numerador como el número total de tipos de palabra que preceden a W,
-
cuantos tipos de palabra puede ser continuados por W, y vamos a normalizarlo por la cantidad de palabras que pueden preceder a todas las palabras
-
Entonces, la suma sobre todas las palabras de la cantidad de tipos de palabra que preceden a la palabra en sí.
-
Y las dos opciones son similares:
-
Éste denominador y el denominador que vimos anteriormente son el mismo
-
porque la cantidad de posibles tipos de bigramas es el mismo que la cantidad de tipos de palabra que pueden proceder todas las palabras, sumado sobre todas las palabras
-
Si piensan acerca de ésto por un segundo, se darán cuenta que es verdad.
-
Entonces en otras palabras, con este tipo de modelo Kneser-Ney,
-
una palabra frecuente como "Francisco" que ocurre solo en un contexto como "San", tendrá una probabilidad de continuación baja.
-
Entonces si juntamos la intuición del descuento absoluto con la probabilidad de Kneser-Ney para los n-gramas de bajo orden,
-
tendremos el algoritmo de suavizado de Kneser-Ney.
-
Entonces, para el bigrama en sí, tenemos descuento absoluto ---
-
Tomamos el conteo de bigramas, le restamos algún descuento D,
-
y mostré aquí que tomamos el máximo entre eso y cero
-
porque, obviamente, si el descuento resulta ser mayor que la probabilidad, no queremos una probabilidad negativa.
-
Y solo interpolaremos con ésta misma probabilidad de continuación que vimos recientemente,
-
P continuación de W_i
-
Y, el lambda, ahora hablaremos de como computar ese lambda.
-
El lambda tomará toda la masa de probablidad de todos los descuentos normalizados
-
que tomamos de éstas probablidades de alto orden,
-
y usarlas para ponderar cuanta probabilidad deberíamos asignar al unigrama
-
y combinaremos eso.
-
Entonces ese lambda es la cantidad del descuento dividido por el denominador.
-
Entonces, es el descuento normalizado.
-
Y luego, multiplicaremos eso por el total de cantidad de tipos de palabra que pueden seguirle a éste contexto, W_i menos uno.
-
En otras palabras, cuantos tipos de palabra diferentes descontamos
-
o cuantas veces aplicamos este descuento normalizado
-
Y multiplicamos esos.
-
Y sabemos cuanta masa de probabilidad total podemos asignarle a la continuación de la palabra.
-
Ahora, esta es la formulación de bigramas para Kneser-Ney.
-
Ahora aquí estamos mostrando la forma general recursiva para n-gramas en general,
-
y aquí tendremos que hacer un pequeño cambio para manejar todos los n-gramas de alto orden.
-
Entonces aquí solo mostramos la probabilidad de Kneser-Ney de una palabra dado el prefijo de la palabra.
-
Y, asi como vimos anteriormente,
-
estamos interpolando un n-grama de alto orden que es descontado con un peso lambda y una probablidad de bajo orden.
-
Pero ahora tendremos que distinguir entre la primer vez que usamos un conteo y estos conteos de bajo orden.
-
Entonces vamos a usar el conteo original para el bigrama de más alto orden,
-
y usaremos el valor de continuación que definimos anteriormente para todas las probabilidades de bajo orden
-
Entonces definiremos esta nueva función: conteo de Kneser-Ney de estrella
-
Este será el conteo original, digamos que estamos haciendo trigramas
-
Para el trigrama, y luego cuando hagamos la recurrencia y tengamos la probabilidad de Kneser-Ney para las cosas de bajo orden.
-
Cuando lleguemos a los bigramas y unigramas, estaremos usando el conteo de continuación,
-
y ese, otra vez, es el contexto para una única palabra que definimos antes.
-
Entonces Kneser-Ney smoothing, un algoritmo excelente.
-
Es comunmente usado en reconocimiento del habla y traducción automática
-
y aún así tiene una elegante y hermosa intuición y espero que lo aprecien.
