¿Es factible utilizar k-Nearest Neighbours para identificar el lenguaje del texto?

Question

He visto varias bibliotecas de identificación de idiomas que afirman utilizar el clasificador de Bayes ingenuo para la identificación de idiomas de texto, como CLD2 y detector de idiomas pero no cualquier biblioteca que utilice otros algoritmos.

Escribí un programa sencillo que utiliza 1-NN con la medida de distancia euclidiana para identificar el idioma de los textos. Las características que he elegido son la ocurrencia de cada palabra, o n-gramas, donde n puede ser cualquier cosa de 1 a 4. Lo entrené con algunos párrafos de texto en inglés y francés de algunas novelas, y luego puse algunas secciones aleatorias (cortas) de texto de Wikipedia en inglés y francés respectivamente. Resulta que cuando se utilizan palabras enteras o n-gramas con n por encima de 2 como características, detecta correctamente.

Actualización: Cuando se utiliza la medida de similitud del coseno, incluso las características de 1 y 2 gramos se detectan correctamente. Además, añadí como muestra de entrenamiento un pasaje completo sin división en saltos de línea y párrafos (cadenas divididas en saltos de línea).

Además, cuando utilicé cada párrafo de las novelas como puntos de datos de muestra de entrenamiento, el algoritmo detectó correctamente las lenguas del texto no visto en las condiciones indicadas anteriormente (palabras enteras o n-gramas con n mayor que 2). Sin embargo, cuando utilicé la sección completa de varios párrafos como muestra de entrenamiento, el texto más corto de la novela francesa (aproximadamente la mitad de la longitud del texto en inglés) parece haber provocado que tanto el texto corto en inglés como el de la Wikipedia de Frech sean identificados como franceses.

Actualización: Así pues, parece que la longitud del documento afecta más a los resultados que la aparición de palabras cuando se utiliza la distancia euclidiana. Mientras que en el caso de la similitud del coseno, el uso de un pasaje más largo que contenga un vocabulario/letras/gramas más completos como muestra de entrenamiento mejoró la precisión.

Actualización: Cuando añadí secciones de Mein Kampf como texto de entrenamiento, tanto la métrica de la distancia euclidiana como la de la similitud del coseno detectaron dos textos breves en francés e inglés como alemán cuando se utilizaron 4 gramos O.O. Además, los valores de similitud no parecen diferir mucho.

Así que,

• ¿Por qué la mayoría de las bibliotecas utilizan el clasificador naive Bayes? ¿Es más adecuado para este propósito?
• ¿Es factible utilizar k-NN para la identificación de idiomas? Si la respuesta es afirmativa, ¿hay alguna ventaja en su uso con respecto al clasificador ingenuo de Bayes? En caso negativo, ¿por qué?
• ¿Qué otro tipo de características podría haber utilizado, además de la frecuencia de los términos?
• ¿Bastarían las características del modelo binario (registro de si un término existe o no) para este propósito?
• ¿Cuál es la mejor métrica de similitud/disimilitud que se puede utilizar para este fin concreto?
• ¿Ayudará el árbol k-d o el árbol k-d con el mejor enfoque del bin primero a acelerar la detección cuando hay una gran base de muestras de entrenamiento? (Es probable que haya cientos de miles de dimensiones/características :P)
• Si se utiliza la métrica de la distancia de similitud del coseno, ¿qué estructura de datos/algoritmo podría utilizarse para reducir la complejidad temporal de la detección de idiomas? ¿Se pueden precalcular los ángulos, utilizar el LSH o el árbol k-d?

Por favor, responda a continuación siempre que conozca alguna de las subpreguntas, o pueda aportar un análisis al fenómeno mencionado :)

No estoy seguro de si debo poner todas las preguntas anteriores en una sola. Si no es así, por favor dímelo y moveré las que no estén relacionadas en una pregunta separada.

Answer 1

Quizás una de las razones por las que se utiliza el NB es que es un método muy sencillo que consigue una precisión extremadamente alta. Es decir, extremadamente alta. Detectar una lengua ya no es realmente un "problema abierto". Tal vez, como alguien mencionó, valga la pena intentar mejorar la clasificación entre dialectos muy similares o algo así.

Este es un informe en la investigación para distinguir el serbio del croata, el mandarín de Taiwán de la China continental, el indonesio del malayo, el portugués de Brasil de Portugal, etc. La precisión de la mayoría de estos idiomas se sitúa en torno al 99%.

Answer 2

Un inconveniente de k-NN es que necesita calcular la distancia a todas las observaciones clasificadas para identificar a sus vecinos más cercanos: el enfoque no es paramétrico. El mayor problema que hay que superar con el enfoque k-NN es la velocidad y la memoria. Un experimento puede resultar interesante. Incluso si k-NN resulta más lento, el enfoque podría tener méritos si la detección es más precisa.

Answer 3

Creo que en una variación SAX del enfoque podría funcionar. Tal vez. El irlandés contra el inglés va a ser difícil. El irlandés contra el klingon podría ser de mayor rendimiento.

Si tratas cada letra como un símbolo, y calculas la frecuencia de las siguientes letras. Ensamblados forman una matriz de probabilidades de transición. La probabilidad de transición puede considerarse como una distancia inversa. Uno podría hacer la agrupación en ese espacio. Personalmente, si tuviera una colección de documentos o idiomas que estuviera tratando de identificar de forma única, podría realizar el PCA antes de realizar la agrupación en el espacio. Esto ayudaría a acentuar la señal.

Es probable que las lenguas tengan un fuerte solapamiento. El aparato vocal humano sólo produce 128 fonemas. Esto significa que su matriz de transición máxima es de 128x128. Por ello, es probable que centrar, desdiferenciar y luego rotar en el dominio de la distancia antes de realizar la agrupación dé mejores resultados.

La mejor de las suertes.

EDITAR:

• Cada lengua suele utilizar unos 60 fonemas, así que lo que suelen hacer es ameba (verbo divertido, ¿eh?) los 60 fonemas no utilizados en los utilizados. El problema es que la ameba no es universal. Los dialectos son un caso en el que los sonidos principales son similares, pero la ameba es diferente. Si se trabajara en sonido, no en texto escrito, este sería un enfoque decente. Existen traductores para convertir el texto escrito en texto fonético. Los más avanzados tendrán en cuenta algún subconjunto de la prosodia.
• SAX -- http://www.cs.ucr.edu/~eamonn/SAX.htm
• PCA y distancia mahalanobis -- ¿Explicación de abajo a arriba de la distancia de Mahalanobis?
• centro y escala significa que primero se resta la tendencia central (como la media, la mediana o la moda), luego se ajustan las entradas/salidas a un modelo lineal simple, luego se resta el modelo lineal de los datos, y se trabajan las cosas avanzadas en la diferencia. Esto evita que las herramientas sofisticadas hagan el trabajo simple y piensen que ya han terminado - hace que trabajen, si pueden, para ganarse la vida.

EDIT2:

• ¿Por qué la mayoría de las bibliotecas utilizan el clasificador Bayes ingenuo? ¿Es más adecuado para este propósito?

Supongo que es porque funciona. A los científicos de datos les encantan los métodos que hacen el trabajo.

• ¿Es factible utilizar k-NN para la identificación de lenguas? En caso afirmativo, ¿hay ¿hay alguna ventaja en el uso de este clasificador sobre el Bayes ingenuo? Si no, ¿por qué?

¿Es factible? Creo que mi material anterior da una idea de que podría funcionar. ¿Ventaja? La gente que utiliza Naive Bayes ha dado vueltas a varias piedras para llegar a la solución que tienen. KNN va a ser una "fruta madura". A menos que tengas una transformación novedosa para cambiar el espacio (SAX+PCA) o algo así, no hay muchas posibilidades de superar la herramienta actual.

• ¿Qué otro tipo de características podría haber utilizado, además de la frecuencia?

¿Frecuencia de dos términos? Frecuencia de tres términos. Frecuencia de N términos. Análogos autorregresivos (skip-term) de los anteriores. Combinaciones de las anteriores. Transformación a fonema, luego repetir lo anterior. sabemos que Baidu utiliza Deep Belief Networks. Se podría intentar hacer una "imitación del hombre pobre" entrenándola con bibliotecas de obras conocidas. Podrías utilizar algún tipo de árbol de coseno-distancia con gradiente.

• ¿Serían las características del modelo binario (registro de si un término existe o no) bastarían para este fin?

¿Te refieres a la regresión logística multivariante? Podría tener algún nivel de función. Va a tomar mucho tiempo para "entrenar".

• ¿Cuál es la mejor métrica de similitud/disimilitud a utilizar para este propósito particular?

Hay muchas razas de lo mejor. Algunos "mejores" son mutuamente excluyentes. ¿Qué quiere decir con "mejor"? El mejor camino podría ser el más corto, a menos que vaya a su ejecución, en cuyo caso el camino más largo o el más agradable por el camino más largo podría ser más deseable. Muchos "mejores" son mutuamente excluyentes: el óptimo de tiempo tiende a usar la mayor cantidad de combustible, mientras que el óptimo de combustible tiende a tomar el mayor tiempo. Hay muchas familias con infinitos sub-miembros en las que cada miembro es una variación del "mejor". Consideremos una interpolación lineal ponderada entre el óptimo de tiempo y el óptimo de combustible. La línea que los separa tiene un número infinito de puntos, y cada lugar de esa línea comprende una versión de "óptimo" o "mejor". Añadir restricciones como el tiempo máximo por debajo de un umbral cambia todo el espacio, y hace que el espacio de los mejores sea bidimensional.

• ¿Ayudará el árbol k-d o el árbol k-d con el mejor enfoque de bin primero a acelerar la detección cuando hay una gran base de muestras de entrenamiento? (Es probable que haya cientos de miles de dimensiones/características :P)

Yo pensaría que habría millones de dimensiones. De nuevo, el autocodificador de palabras habladas de Baidu lo sugiere.

• Si se utiliza la métrica de distancia de similitud del coseno, ¿qué datos estructura/algoritmo de datos podría utilizarse para reducir la complejidad temporal de la la detección de idiomas? ¿Se pueden precalcular los ángulos, utilizar LSH o utilizar k-d tree?

Trabajo más con datos de ingeniería que con palabras, así que no puedo responder a esto.