¿Por qué se usa n-gram en la identificación del lenguaje de texto en lugar de palabras?

12

En dos bibliotecas de identificación de idiomas populares, Compact Language Detector 2 para C ++ y el detector de idiomas para java, ambos utilizaron n-gramos (basados ​​en caracteres) para extraer características de texto. ¿Por qué no se usa una bolsa de palabras (una sola palabra / diccionario), y cuál es la ventaja y desventaja de la bolsa de palabras y n-gramas?

Además, ¿cuáles son algunos otros usos del modelo n-gramas en la clasificación de texto?

Oh vaya. Parece que hay una pregunta similar aquí: con respecto al uso del modelo bigram (N-gram) para construir el vector de características para el documento de texto

¿Pero alguien puede dar una respuesta más completa? ¿Qué es mejor en el caso de la identificación del idioma?

(Espero haber entendido bien el significado de n-gramas y bolsa de palabras, jaja, si no, ayúdenme con eso).

dennis97519
fuente

Respuestas:

20

Creo que las respuestas más detalladas se pueden encontrar en el extenso trabajo de Mehryar Mohri sobre el tema. Aquí hay un enlace a una de sus diapositivas sobre el tema: http://www.cims.nyu.edu/~mohri/amls/lecture_3.pdf

El problema de la detección del lenguaje es que el lenguaje humano (palabras) tiene estructura. Por ejemplo, en inglés, es muy común que la letra 'u' siga a la letra 'q', mientras que este no es el caso en árabe transliterado. Los n-gramas funcionan capturando esta estructura. Por lo tanto, ciertas combinaciones de letras son más probables en algunos idiomas que en otros. Esta es la base de la clasificación n-gram.

La bolsa de palabras, por otro lado, depende de buscar en un diccionario grande y esencialmente de hacer coincidir las plantillas. Aquí hay dos inconvenientes principales: 1) cada idioma tendría que tener un extenso diccionario de palabras en el archivo, lo que tomaría un tiempo relativamente largo para buscar, y 2) la bolsa de palabras fallará si ninguna de las palabras en El conjunto de entrenamiento se incluye en el conjunto de prueba.

Suponiendo que está usando bigrams (n = 2) y hay 26 letras en su alfabeto, entonces solo hay 26 ^ 2 = 676 bigrams posibles para ese alfabeto, muchos de los cuales nunca ocurrirán. Por lo tanto, el "perfil" (para usar las palabras del detector de idiomas) para cada idioma necesita una base de datos muy pequeña. Un clasificador de bolsa de palabras, por otro lado, necesitaría un diccionario completo para CADA idioma para garantizar que un idioma pueda ser detectado en función de la oración que se le haya dado.

En resumen, cada perfil de idioma se puede generar rápidamente con un espacio de características relativamente pequeño. Curiosamente, los n-gramos solo funcionan porque las letras no se dibujan en un idioma, esto es explícitamente apalancamiento.

Nota: la ecuación general para el número de n-gramos para palabras es l ^ n donde l es el número de letras en el alfabeto.

justanotherbrain
fuente
Supongo que para algunos idiomas cercanos, sería útil usar listas de palabras además de n-gramas. He visto, a veces, textos noruegos que se clasifican como daneses. Dudo que n-gramas sea una buena manera de distinguir esos dos idiomas.
kjetil b halvorsen
Gracias por tu respuesta detallada. Sin embargo, tengo algunas preguntas con respecto a esto, en primer lugar, ¿podría explicar 'la bolsa de palabras fallará si ninguna de las palabras del conjunto de entrenamiento se incluye en el conjunto de prueba'? y en segundo lugar, ¿por qué CLD2 usa 4 gramos, lo que resultará en 456976 entradas para el idioma inglés, cuando el uso de un método de diccionario puede generar aproximadamente la mitad del tamaño del perfil ( oxforddictionaries.com/words/… )?
dennis97519
1
@ dennis97519 re: "bolsa de palabras ..." Suponga que su diccionario solo consta de las palabras {"perro", "gato", "tortuga", "animal"} para inglés y {"perro", "gato" , "tortuga", "animal"} para español. Su diccionario no podría clasificar la siguiente oración: "Un burro es un animal" porque la palabra "animal" aparece en ambos diccionarios, pero ninguna de las otras palabras existe. Este es un ejemplo extremo. Re 4 gramos: 1) Recuerde que necesita un diccionario para cada idioma, 2) los n-gramos tienden a ser escasos (búsqueda más rápida) y 3) como dijo Dougal, se pueden representar en solo unos pocos bytes.
justanotherbrain
1
@loretoparisi: hay dos compensaciones: la primera es entre la complejidad del modelo (N grande = más complejo) y el error de generalización (qué tan bien le va en algún conjunto de prueba): no desea sobreajustar. La segunda compensación es la complejidad computacional. La complejidad de la memoria crece exponencialmente con N. El entrenamiento suele ser lineal con la cantidad de palabras en el texto, por lo que tener un texto muy largo no suele ser un problema. Dicho esto, el texto grande a menudo significa más palabras en su diccionario D. Entonces, nuevamente, la complejidad de la memoria es O (D ^ N). En la práctica, generalmente es mejor usar una N tan grande como sea computacionalmente posible.
justanotherbrain
1
@loretoparisi: siguiendo eso, como se mencionó anteriormente, los N-gramos tienden a ser escasos, pero esto no siempre es cierto. Si es escaso para su texto en particular, entonces la validación cruzada con diferentes N es el mejor enfoque para encontrar un N óptimo (nuevamente, con restricciones computacionales).
justanotherbrain
3

Se usan letras N-gramas en lugar de palabras por varias razones:

1) La lista de palabras necesarias para un idioma dado es bastante grande, quizás 100,000 si considera rápido, más rápido, más rápido, ayuno, ayuno, ayuno, ... como todas las palabras diferentes. Para 80 idiomas, necesita aproximadamente 80 veces más palabras, ocupando mucho espacio: más de 50 megabytes.

2) El número de trigramas de letras para un alfabeto de 26 letras es 26 ** 3 o alrededor de 17,000 y para los quadgrams (N = 4) alrededor de 450,000 que cubren TODOS los idiomas que usan ese alfabeto. Números similares pero algo mayores para N-gramos en alfabetos mayores de 30-100 caracteres Para los idiomas CJK con más de 4000 letras en el script Han, los unigramas (N = 1) son suficientes. Para algunas secuencias de comandos Unicode, solo hay un idioma por secuencia de comandos (griego, armenio), por lo que no se necesitan combinaciones de letras (los llamados nil-gramos N = 0)

3) Con las palabras, no tiene ninguna información cuando se le da una palabra que no está en el diccionario, mientras que con la letra N-gramos a menudo tiene al menos algunas combinaciones de letras útiles dentro de esa palabra.

CLD2 utiliza quadgrams para la mayoría de los scripts Unicode (alfabetos), incluyendo latín, cirílico y árabe, unigramas para los scripts CJK, nilgrams para otros scripts, y también incluye un número limitado de palabras completas bastante distintivas y bastante comunes y pares de palabras para distinguir dentro de grupos difíciles de idiomas estadísticamente similares, como indonesio y malayo. Las letras grandes y los trigramas son quizás útiles para distinguir entre una pequeña cantidad de idiomas (aproximadamente ocho, consulte https://docs.google.com/document/d/1NtErs467Ub4yklEfK0C9AYef06G_1_9NHL5dPuKIH7k/edit), pero son inútiles para distinguir docenas de idiomas. Por lo tanto, CLD2 usa quadgrams, asociando con cada combinación de letras los tres idiomas más probables que usan esa combinación. Esto permite cubrir 80 idiomas con aproximadamente 1,5 MB de tablas y 160 idiomas con más detalle con aproximadamente 5 MB de tablas.

Sitios Dick
fuente