N-grama

Un n-grama es una subsecuencia de n elementos de una secuencia dada. Los n-gramas se emplean en varias áreas del procesamiento estadístico del lenguaje natural, así como en algunos métodos de predicción o descubrimiento de genes.

Un n-grama de tamaño 1 se denomina "unigrama"; de tamaño 2 es un "bigrama" o "digrama"; de tamaño 3, "trigrama"; de tamaño 4 o más se denomina "n-grama" o "modelo de Márkov de orden (n − 1)".

Modelo de n-grama

Un modelo de n-grama modeliza secuencias, como lenguajes naturales, empleando las propiedades estadísticas de los n-gramas.

Esta idea tiene su origen en un experimento realizado por Claude Shannon sobre teoría de la información. Su idea fue que dada una secuencia de letras (por ejemplo, la secuencia "por ej"), ¿cuál es la siguiente letra más probable? A partir de un conjunto de datos de aprendizaje, uno puede deducir una distribución de probabilidad para la siguiente letra dado un conjunto de datos históricos de tamaño n: a = 0.4, b = 0.00001, c = 0, ....; donde las probabilidades de todas las posibles letras siguientes suman 1.0.

Más precisamente, un modelo de n-grama predice x_i basándose en $x_{i-1}, x_{i-2}, \dots, x_{i-n}$. Aplicándose al modelado de lenguajes, debido a limitaciones computacionales y a la naturaleza abierta del lenguaje (donde hay infinitas palabras posibles), se asume una independencia tal que cada palabra solo depende de las últimas n palabras, convirtiéndose en un buen modelo de Márkov.

Los modelos de n-gramas se emplean habitualmente en el procesamiento estadístico del lenguaje natural. En el reconocimiento de voz, los fonemas se modelan empleando una distribución de n-gramas. Al analizarse, las palabras se modelan de modo que cada n-grama se componga de n palabras. Dada una secuencia de palabras, (como por ejemplo "la madrastra era una auténtica bruja"), los trigramas serían: "la madrastra era", "madrastra era una", "era una auténtica" y "una auténtica bruja". Para secuencias de caracteres, los trigramas que podrían generarse a partir de "buenos días" serían "bue", "uen", "eno", "nos", "os ", "s d", " di", etc. Algunos sistemas procesan las cadenas de texto eliminando los espacios. Otros no. En casi todos los casos, los signos de puntuación se eliminan durante el preproceso. Los n-gramas se pueden emplear para secuencias de palabras o, de hecho, para casi cualquier tipo de datos. Se han empleado, por ejemplo, para extraer características comunes de grandes conjuntos de imágenes de la Tierra tomadas desde satélite, y para determinar a qué parte de la Tierra pertenece una imagen dada.

Uso de n-gramas para encajes por aproximación

Los n-gramas también pueden emplearse para realizar eficientemente encajes por aproximación. Convirtiendo una secuencia de elementos en un conjunto de n-gramas, éste puede introducirse en un espacio vectorial (en otras palabras, representarse como un histograma), permitiendo así a la secuencia compararse con otras secuencias de una manera eficiente. Por ejemplo, si convertimos cadenas de texto con sólo letras del alfabeto español en 3-gramas, conseguiremos un espacio vectorial de 27³ dimensiones (la primera dimensión mide el número de ocurrencias de "aaa", la segunda de "aab", y así para todas las posibles combinaciones de 3 letras). Empleando esta representación, perdemos información sobre la cadena de texto. Por ejemplo, las cadenas "abcba" y "bcbab" llevarán exactamente a los mismos digramas. Sin embargo, se conoce empíricamente que si dos cadenas de texto real tienen una representación vectorial similar (medida a través del producto escalar) es muy probable que sean similares. También pueden aplicarse otras métricas a los vectores de n-gramas con resultados variados (a veces, mejores). Por ejemplo la distribución normal puede emplearse para comparar documentos, examinando cúantas desviaciones típicas de cada n-grama difieren de la media en un conjunto grande de documentos (que forma el vector de fondo).

Otras aplicaciones

Los n-gramas se emplean en diversas áreas de la informática, lingüística computacional, y matemática aplicada. Son una técnica comúnmente empleada para diseñar núcleos que permiten a algoritmos automáticos de aprendizaje extraer datos a partir de cadenas de texto. Los n-gramas también pueden emplearse para encontrar candidatos probables para la correcta ortografía de una palabra mal escrita. También en algoritmos de compresión, donde una pequeña zona de datos necesita n-gramas de longitud mayor para mejorar la compresión. Los n-gramas se emplean a menudo en sistemas de reconocimiento de patrones para determinar la probabilidad de que una palabra dada aparezca en un texto. Esta capacidad puede ser útil en reconocimiento de voz, OCR (reconocimiento óptico de caracteres), reconocimiento inteligente de caracteres, traducciones automáticas, y aplicaciones similares en las que un sistema debe elegir el siguiente elemento (letra, palabra, fonema, etc.) de entre una lista de posibles candidatos. También se emplean en recompilación de información cuando es necesario encontrar "documentos" similares dado un documento y una base de datos de documentos de referencia.

En bioinformática, y en particular en la predicción de genes, se analizan n-gramas extraídos de las largas cadenas de ácidos nucleicos del ADN (secuencias o frases de un alfabeto de cuatro letras, en definitiva), así como de aminoácidos (un alfabeto que consta, usualmente, de veinte letras), con el objetivo de detectar patrones estadísticos que permitan poner de manifiesto la posible existencia de genes.

Compromiso entre varianza y parcialidad

¿Qué determina la n de un n-grama?

Existen problemas derivados de asignar demasiado peso a gramas poco frecuentes (por ejemplo, si un nombre propio aparecía en el conjunto de datos de aprendizaje) y demasiado poco peso a los gramas frecuentes. También, los elementos que no aparezcan en el conjunto de datos de aprendizaje recibirán una probabilidad de 0.0 sin suavizado posible. Para los datos que no aparecen en una muestra, pero que son plausibles, se pueden introducir pseudocontadores.

Técnicas de suavizado

Artículo principal: Suavizado de n-gramas

• Interpolación lineal (esto es, tomar la media ponderada de los unigramas, bigramas y trigramas)
• Descuento de Good-Turing
• Descuento de Witten-Bell

Véase también

• Modelo oculto de Márkov
• Trigrama, Bigrama
• Técnicas de suavizado

Bibliografía

• Christopher D. Manning, Hinrich Schütze, Foundations of Statistical Natural Language Processing, MIT Press: 1999. ISBN 0-262-13360-1.

Enlaces externos

• Generador de N-gramas de palabras.
• Un generador de N-Gramas.
• Otro generador de texto aleatorio a partir de N-Gramas.