algorithm - ¿Cómo funciona el algoritmo “¿Quiso decir?” De Google?

machine-learning nlp (18)

¿Quieres decir corrector ortográfico? Si es un corrector ortográfico en lugar de una frase completa, entonces tengo un enlace sobre el corrector ortográfico donde se desarrolla el algoritmo en Python. Revisa este enlace

Mientras tanto, también estoy trabajando en un proyecto que incluye búsquedas en bases de datos usando texto. Supongo que esto resolvería tu problema.

He estado desarrollando un sitio web interno para una herramienta de gestión de cartera. Hay muchos datos de texto, nombres de compañías, etc. Me ha impresionado mucho la capacidad de algunos motores de búsqueda para responder rápidamente a las consultas con "¿Quiso decir: xxxx"?

Necesito poder tomar de forma inteligente una consulta de usuario y responder no solo con resultados de búsqueda en bruto, sino también con un "¿Quiso decir?" Respuesta cuando hay una respuesta alternativa muy probable, etc.

[Me estoy desarrollando en ASP.NET (VB - ¡no lo pongas en mi contra!)]

ACTUALIZACIÓN: OK, ¿cómo puedo imitar esto sin los millones de ''usuarios no pagados''?

¿Genera errores tipográficos para cada término ''conocido'' o ''correcto'' y realiza búsquedas?
¿Algún otro método más elegante?

Además de las respuestas anteriores, en caso de que desee implementar algo por su cuenta rápidamente, aquí hay una sugerencia:

Algoritmo

Puede encontrar la implementación y la documentación detallada de este algoritmo en GitHub .

Crear una cola de prioridad con un comparador.
Cree un árbol de búsqueda de Ternay e inserte todas las palabras en inglés (de la publicación de Norvig ) junto con sus frecuencias.
Comience a atravesar la TST y para cada palabra encontrada en la TST, calcule su Distancia Levenshtein ( LD ) desde input_word
Si LD ≤ 3, póngalo en una cola de prioridad.
Al final, extraiga 10 palabras de la cola de prioridad y visualice.

Aparentemente, Google sugiere consultas con mejores resultados, no con las que están escritas correctamente. Pero en este caso, probablemente sería más factible un corrector ortográfico. Por supuesto, podría almacenar algo de valor para cada consulta, en función de alguna métrica de los buenos resultados que obtiene.

Asi que,

Necesitas un diccionario (inglés o basado en tus datos)
Genere una palabra enrejado y calcule las probabilidades para las transiciones usando su diccionario.
Agregue un decodificador para calcular la distancia de error mínima usando su enrejado. Por supuesto, debe ocuparse de las inserciones y eliminaciones al calcular las distancias. Lo divertido es que el teclado QWERTY maximiza la distancia si golpeas las teclas cerca una de la otra (cae cae en el auto, cay gira en el gato)
Devuelve la palabra que tiene la distancia mínima.
Luego, puede comparar eso con su base de datos de consultas y verificar si hay mejores resultados para otras coincidencias cercanas.

Aquí está la mejor respuesta que encontré , corrector ortográfico implementado y descrito por el Director de Investigación de Google, Peter Norvig.

Si desea leer más sobre la teoría detrás de esto, puede leer el capítulo de su libro .

La idea de este algoritmo se basa en el aprendizaje estadístico de máquina.

Aquí está la explicación directamente de la fuente (casi)

Busqueda 101!

a las 22:03 min

¡Vale la pena ver!

Básicamente y según Douglas Merrill, ex director de tecnología de Google, es así:

1) Escribes una palabra (mal escrita) en google

2) No encuentra lo que buscaba (no haga clic en ningún resultado)

3) Te das cuenta de que escribiste mal la palabra y la reescribes en el cuadro de búsqueda.

4) Encuentra lo que quieres (haz clic en los primeros enlaces)

Este patrón se multiplicó millones de veces, muestra cuáles son los errores ortográficos más comunes y cuáles son las correcciones más "comunes".

De esta manera, Google puede, casi instantáneamente, ofrecer corrección ortográfica en todos los idiomas.

Además, esto significa que, de la noche a la mañana, todos comienzan a deletrear la noche como "novedad", Google sugerirá esa palabra en su lugar.

EDITAR

@ThomasRutter: Douglas lo describe como "aprendizaje estadístico de máquina".

Saben quién corrige la consulta, porque saben qué consulta proviene de qué usuario (mediante cookies)

Si los usuarios realizan una consulta, y solo el 10% de los usuarios hacen clic en un resultado y el 90% regresa y escribe otra consulta (con la palabra corregida) y esta vez ese 90% hace clic en un resultado, entonces saben que han encontrado una corrección.

También pueden saber si esas son consultas "relacionadas" de dos diferentes, porque tienen información de todos los enlaces que muestran.

Además, ahora están incluyendo el contexto en la revisión ortográfica, por lo que incluso pueden sugerir diferentes palabras dependiendo del contexto.

Vea esta demostración de google wave (@ 44m 06s) que muestra cómo se tiene en cuenta el contexto para corregir automáticamente la ortografía.

Here se explica cómo funciona ese procesamiento de lenguaje natural.

Y finalmente, aquí hay una demostración impresionante de lo que se puede hacer al agregar la traducción automática (@ 1h 12m 47s) a la mezcla.

_{He agregado anclas de minutos y segundos a los videos para saltar directamente al contenido; si no funcionan, intente volver a cargar la página o desplazarse manualmente hasta la marca.}

Como una conjetura ... podría

buscar palabras
si no se encuentra, use algún algoritmo para tratar de "adivinar" la palabra.

Podría ser algo de la IA, como la red Hopfield o la red de propagación inversa, o algo más "identificar huellas digitales", restaurar datos rotos o correcciones ortográficas como ya mencionó Davide ...

Encontré este artículo hace algún tiempo: Cómo escribir un corrector ortográfico , escrito por Peter Norvig (Director de investigación de Google Inc.).

Es una lectura interesante sobre el tema "corrección ortográfica". Los ejemplos están en Python, pero es claro y fácil de entender, y creo que el algoritmo se puede traducir fácilmente a otros idiomas.

A continuación sigue una breve descripción del algoritmo. El algoritmo consta de dos pasos, preparación y verificación de palabras.

Paso 1: Preparación - configuración de la base de datos de palabras

Lo mejor es si puedes usar palabras de búsqueda reales y su aparición. Si no tienes eso, puedes usar un gran conjunto de texto. Cuenta la ocurrencia (popularidad) de cada palabra.

Paso 2. Verificación de palabras: búsqueda de palabras similares a las marcadas

Similar significa que la distancia de edición es baja (normalmente 0-1 o 0-2). La distancia de edición es el número mínimo de inserciones / eliminaciones / cambios / intercambios necesarios para transformar una palabra en otra.

Elija la palabra más popular del paso anterior y sugiérala como una corrección (si no es la palabra en sí).

Esta es una pregunta antigua, y me sorprende que nadie haya sugerido el OP utilizando Apache Solr.

Apache Solr es un motor de búsqueda de texto completo que, además de muchas otras funciones, también ofrece ortografía o sugerencias de consulta. De la documentation :

Por defecto, los revisores Lucene Spell clasifican las sugerencias primero por la puntuación del cálculo de la distancia de la cadena y luego por la frecuencia (si está disponible) de la sugerencia en el índice.

Existe una estructura de datos específica, el árbol de búsqueda ternario , que naturalmente soporta coincidencias parciales y coincidencias de vecinos cercanos.

Hmm ... pensé que Google usó su vasto corpus de datos (Internet) para hacer un poco de PNL (Procesamiento de Lenguaje Natural) serio.

Por ejemplo, tienen tantos datos de todo Internet que pueden contar el número de veces que se produce una secuencia de tres palabras (conocida como trigrama ). Entonces, si ven una frase como: "Pink frugr concert", podrían ver que tiene pocos éxitos, y luego encontrar el más probable "pink * concert" en su corpus.

Sin embargo, aparentemente solo hacen una variación de lo que Davide Gualano estaba diciendo, así que definitivamente lean ese enlace. Por supuesto, Google utiliza todas las páginas web que conoce como un corpus, por lo que hace que su algoritmo sea particularmente efectivo.

La forma más fácil de averiguarlo es a través de la programación dinámica de Google.

Es un algoritmo que se ha tomado de la recuperación de información y se usa en gran medida en la bioinformática de hoy en día para ver cómo son similares dos secuencias de genes.

La solución óptima utiliza programación dinámica y recursión.

Este es un problema muy resuelto con muchas soluciones. Solo busca en Google hasta encontrar un código de código abierto.

Mi conjetura es que utilizan una combinación de un algoritmo de distancia Levenshtein y las masas de datos que recopilan con respecto a las búsquedas que se ejecutan. Podrían extraer un conjunto de búsquedas que tengan la distancia Levenshtein más corta de la cadena de búsqueda ingresada, y luego elegir la que tenga más resultados.

Normalmente, un corrector ortográfico de producción utiliza varias metodologías para proporcionar una sugerencia de ortografía. Algunos son:

Decida la manera de determinar si se requiere la corrección ortográfica. Estos pueden incluir resultados insuficientes, resultados que no son lo suficientemente específicos o precisos (según alguna medida), etc. Luego:
Use un gran cuerpo de texto o un diccionario, donde se sabe que todos, o la mayoría, están correctamente escritos. Estos se encuentran fácilmente en línea, en lugares como LingPipe . Luego, para determinar la mejor sugerencia, busque una palabra que sea la coincidencia más cercana en función de varias medidas. El más intuitivo son los personajes similares. Lo que se ha demostrado a través de la investigación y la experimentación es que dos o tres coincidencias de secuencia de caracteres funcionan mejor. (Bigramas y trigramas). Para mejorar aún más los resultados, pese una puntuación más alta en una coincidencia al principio o al final de la palabra. Por razones de rendimiento, indexe todas estas palabras como trigramas o bigramas, de modo que cuando realice una búsqueda, convierta a n-gramo y busque a través de hashtable o trie.
Utilice heurísticas relacionadas con posibles errores de teclado en función de la ubicación del personaje. De modo que "hwllo" debería ser "hola" porque ''w'' está cerca de ''e''.
Use una clave fonética (Soundex, Metaphone) para indexar las palabras y buscar posibles correcciones. En la práctica, esto normalmente devuelve resultados peores que el uso de la indexación de n-gramas, como se describe anteriormente.
En cada caso debe seleccionar la mejor corrección de una lista. Esta puede ser una métrica de distancia como levenshtein, la métrica del teclado, etc.
Para una frase de varias palabras, solo una palabra puede estar mal escrita, en cuyo caso puede usar las palabras restantes como contexto para determinar la mejor coincidencia.

Para la teoría del algoritmo de "quiso decir", puede consultar el Capítulo 3 de Introducción a la recuperación de información. Está disponible en online de forma gratuita. La sección 3.3 (página 52) responde exactamente a tu pregunta. Y para responder específicamente a su actualización, solo necesita un diccionario de palabras y nada más (incluidos millones de usuarios).

Sencillo. Tienen toneladas de datos. Tienen estadísticas para cada término posible, en función de la frecuencia con la que se consulta, y qué variaciones de él suelen dar resultados en los que los usuarios hacen clic ... así que, cuando ven que escribe errores frecuentes para un término de búsqueda, siguen adelante y proponen La respuesta más habitual.

En realidad, si la palabra mal escrita es, en efecto, el término de búsqueda más frecuente, el algoritmo lo tomará por el correcto.

Vi algo sobre esto hace unos años, así que puede haber cambiado desde entonces, pero aparentemente lo comenzaron analizando sus registros para los mismos usuarios que envían consultas muy similares en un corto espacio de tiempo, y utilizaron el aprendizaje automático basado en cómo los usuarios habían corregido sí mismos.

con respecto a su pregunta sobre cómo imitar el comportamiento sin tener toneladas de datos, ¿por qué no usar toneladas de datos recopilados por google? Descargue los resultados de Google Sarch para la palabra mal escrita y busque "Quiso decir:" en el HTML.

Supongo que eso se llama mashup hoy en día :-)

Use la distancia Levenshtein , luego cree un árbol métrico (o árbol delgado) para indexar palabras. Luego ejecuta una consulta de Vecino más cercano y obtendrás el resultado.