Suavizado de n-gramas

Conocimientos adicionales recomendados

Cómo realizar un pesaje correcto

Procedimientos normalizados de trabajo (PNT) para la comprobación de balanzas

Cómo comprobar rápidamente el rendimiento de las pipetas

Tabla de contenidos

1 Introducción
2 Aproximación o descuento de Laplace
3 Algoritmos de interpolación lineal
- 3.1 Deleted interpolation
- 3.2 Interpolación aproximada
4 Técnicas de back-off
5 Otras técnicas de suavizado
6 Referencias
7 Véase también
8 Enlaces externos

Introducción

Un problema bastante frecuente en procesamiento del lenguaje natural es el cálculo de la verosimilitud (probabilidad) de una secuencia de palabras, por ejemplo para puntuar diversas hipótesis alternativas y seleccionar la más probable.

Supongamos que un sistema de reconocimiento de voz identifica una frase y sugiere, debido a su parecido fonético, dos posibles textos alternativos:

Texto A: "sax and violins on TV"
Texto B: "sex and violence on TV"

A primera vista parece que el texto B es más probable que el A, sin embargo, un sistema automático carece de tal sentido común y deberá basarse en un modelo de lenguaje determinado para evaluar cuál de las dos secuencias de palabras tiene mayor puntuación. Para el cálculo de la probabilidad de la observación (la frase en cuestión) se emplea habitualmente un modelo de k-gramas y es bastante frecuente que determinados k-gramas tengan probabilidad 0, es decir, que no aparecen en el texto.

Con las técnicas de suavizado intentamos evitar las probabilidades cero producidas por k-gramas no vistos.

Son varios los algoritmos de suavizado que se conocen. A continuación se describen algunos de los más utilzados.

Aproximación o descuento de Laplace

El descuento de Laplace asume que todos los k-gramas se han visto al menos una vez. Por tanto, para evitar probabilidades cero para trigramas no vistos el cálculo quedaría así:

$\hat{p}(v|v_1,v_2)=\frac{1 + n(v_1 v_2 v)}{ \displaystyle\sum_{v' \in V}{1+ n(v_1 v_2 v')}}$

El problema fundamental de esta solución es que da demasiado porcentaje de la masa total de probabilidad a los k-gramas no vistos.

Algoritmos de interpolación lineal

Deleted interpolation

En general:

$p(w|h) = \lambda \frac{N(hw)}{\displaystyle\sum_{w'}{hw'}} + (1-\lambda) \beta(w|\hat{h})$

$h$ es la historia detallada ( $w 1 w 2 w$ )
$β$ es la probabilidad más robusta
$\hat{h}$ es la historia simplificada ( $w 2 w$ )

Para el caso concreto de trigramas:

$p(v|v_{1}v_{2}) = \lambda_3(v_{1},v_{2}) \frac{n(v_{1}v_{2}v)}{\displaystyle\sum_{V'}{n(v_{1}v_{2}v')}} + (1-\lambda_3(v_{1},v_{2})) \hat{p}(v|v_{2})$

$\hat{p}(v|v_{2}) = \lambda_2(v_{2}) \frac{n(v_{2}v)}{\displaystyle\sum_{V'}{n(v_{2}v')}} + (1- \lambda_2(v_{2})) \hat{p}(v)$

$\hat{p}(v) = \lambda_1 \frac{n(v)}{N} + (1 - \lambda) \frac{1}{|V|}$

$| V |$ es el tamaño del vocabulario.

Interpolación aproximada

$\hat{p}(v|v_{1}v_{2})= \frac{N(v_{1}v_{2})^{\frac{1}{2}}}{1+N(v_{1}v_{2})^{\frac{1}{2}}} \frac{N(v_{1}v_{2}v)}{\displaystyle\sum_{V'}{N(v_{1}v_{2}v')}} + \left(1 - \frac{N(v_{1}v_{2})^{\frac{1}{2}}}{1+N(v_{1}v_{2})^{\frac{1}{2}}} \right) \hat{p}(v_{1}v_{2})$

$\hat{p}(v|v_{2}) = \frac{N(v_{2})^{\frac{1}{2}}}{1+N(v_{2})^{\frac{1}{2}}} \frac{N(v_{2}v)}{\displaystyle\sum_{V'}{N(v_{2}v')}} + \left(1-\frac{N(v_{2})^{\frac{1}{2}}}{1+N(v_{2})^{\frac{1}{2}}} \right) \hat{p}(v)$

Técnicas de back-off

Si $N (h w) > 0$

$p(w|h)= \lambda \frac{N(hw)}{\displaystyle\sum_{w'}{N(hw')}}$

Si $N (h w) = 0$

$(1-\lambda) \frac{\beta(w|\hat{h})}{\displaystyle\sum_{w':N(hw')=0}{\beta(w'|\hat{h})}}$

La diferencia fundamental entre los modelos de backoff y de interpolación es que en el caso de probabilidades no nulas, los modelos de interpolación usan información de k-gramas de orden inferior mientras que mediante técnicas de backoff no occurre así.

Otras técnicas de suavizado

Add-delta (Lidstone’s & Jeffreys-Perks’ Laws)
Descuento de Good-Turing
Descuento de Witten-Bell

Referencias

Brants, Thorsten; Samuelsson, Christer (1995): «Tagging the Teleman Corpus», en Proceedings of the 10th Nordic Conference of Computational Linguistics. Helsinki, Finland. http://citeseer.ist.psu.edu/brants95tagging.html
Martin, S.; Hamacher, C.; Liermann, J.; Wessel, F.; Ney, H. (1999): «Assessment of smoothing methods and complex stochastic language modeling», en 6th European Conference on Speech Communication and Technology, Budapest, Hungary.

Véase también

n-grama

Enlaces externos

Good-Turing en la versión en inglés de la Wikipedia.

Categoría: Bioinformática

Este articulo se basa en el articulo Suavizado_de_n-gramas publicado en la enciclopedia libre de Wikipedia. El contenido está disponible bajo los términos de la Licencia de GNU Free Documentation License. Véase también en Wikipedia para obtener una lista de autores.