python machine-learning fuzzy-search spelling

python - ¿Estadísticas de errores de mundo real?



machine-learning fuzzy-search (5)

¿Dónde puedo encontrar estadísticas de errores tipográficos en el mundo real?

Estoy intentando hacer coincidir el texto de entrada de las personas con los objetos internos, y las personas tienden a cometer errores ortográficos.
Hay 2 tipos de errores:

  1. typos : "Helllo" en lugar de "Hello" / "Satudray" en lugar de "Saturday", etc.
  2. Spelling : "Shikago" en lugar de "Chicago"

Utilizo la distancia de Damerau-Levenshtein para los errores tipográficos y Double Metaphone para la ortografía (implementaciones de Python here y here ).

Quiero centrarme en Damerau-Levenshtein (o simplemente edit-distance ). Las implementaciones de libros de texto siempre usan ''1'' para el peso de eliminaciones, sustituciones de inserciones y transposiciones. Si bien esto es simple y permite buenos algoritmos, no coincide con "realidad" / "probabilidades del mundo real".

Ejemplos:

  • Estoy seguro de que la probabilidad de "Helllo" ("Hola") es mayor que "Helzlo", pero ambos están a una distancia de 1 edición.
  • "Gello" está más cerca que "Qello" a "Hola" en un teclado QWERTY.
  • Transliteraciones Unicode: ¿Cuál es la distancia "real" entre "München" y "Munchen"?

¿Cuáles deberían ser los pesos del "mundo real" para las supresiones, inserciones, sustituciones y transposiciones?

Incluso el genial corrector ortográfico de Norvig usa una distancia de edición no ponderada.

Por cierto, estoy seguro de que los pesos deben ser funciones y no simples flotadores (según los ejemplos anteriores) ...

Puedo ajustar el algoritmo, pero ¿dónde puedo "aprender" estos pesos? No tengo acceso a datos de escala de Google ...

¿Debería solo adivinarlos?

EDITAR - tratando de responder preguntas del usuario:

  • Mi algoritmo no ponderado actual falla a menudo cuando se enfrentan errores tipográficos por las razones anteriores. "Regresar el jueves": cada "persona real" puede decir con facilidad que el jueves es más probable que el martes, ¡pero están a una distancia de 1 edición! (Sí, registro y mido mi rendimiento).
  • Estoy desarrollando un motor de búsqueda de viajes NLP, por lo que mi diccionario contiene ~ 25K destinos (se espera que crezca a 100K), Expresiones de tiempo ~ 200 (esperado 1K), Expresiones de personas ~ 100 (esperado 300), Expresiones monetarias ~ 100 (500 esperadas ), "palabras lógicas de pegamento" ("desde", "hermoso", "apartamento") ~ 2K (se espera 10K) y así sucesivamente ...
  • El uso de la distancia de edición es diferente para cada uno de los grupos de palabras anteriores. Intento "autocorregir cuando sea obvio", por ejemplo, 1 edición a una distancia de solo 1 palabra más en el diccionario. Tengo muchas otras reglas ajustadas a mano, por ejemplo, corrección de Double Metaphone que no está a más de 2 horas de distancia de una palabra de diccionario con una longitud> 4 ... La lista de reglas continúa creciendo a medida que aprendo de la información del mundo real.
  • "¿Cuántos pares de entradas de diccionario están dentro de su umbral?": Bueno, eso depende del "sistema de ponderación elegante" y de la entrada del mundo real (futuro), ¿no es así? De todos modos, tengo pruebas unitarias extensas para que cada cambio que haga en el sistema solo lo haga mejor (basado en entradas pasadas, por supuesto). La mayoría de las palabras con letras inferiores a 6 están dentro de una distancia de edición de una palabra que está a una distancia de edición de otra entrada del diccionario.
  • Hoy, cuando hay dos entradas de diccionario a la misma distancia de la entrada, trato de aplicar varias estadísticas para adivinar mejor a qué se refería el usuario (por ejemplo, París, es más probable que aparezca en mi búsqueda que Pārīz, Irán).
  • El costo de elegir una palabra incorrecta es devolver resultados semialeatorios (a menudo ridículos) al usuario final y potencialmente perder un cliente. El costo de no comprender es un poco menos costoso: se le pedirá al usuario que reformule.
  • ¿Vale la pena el costo de la complejidad? Sí, estoy seguro de que así es. No creería la cantidad de errores tipográficos que la gente arroja al sistema y espera que lo entienda, y podría usar el impulso en Precisión y Recuperación .

Algunas preguntas para usted, para ayudarlo a determinar si debe hacer su pregunta "¿dónde encuentro pesos del mundo real?":

¿Has medido realmente la efectividad de la implementación de ponderación uniforme? ¿Cómo?

¿Cuántos "objetos internos" diferentes tiene, es decir, cuál es el tamaño de su diccionario?

¿Cómo está usando realmente la distancia de edición, por ejemplo, John / Joan, Marmaduke / Marmeduke, Featherstonehaugh / Featherstonhaugh: es ese "todo 1 error" o es 25% / 11.1% / 5.9% de diferencia? ¿Qué umbral estás usando?

¿Cuántos pares de entradas de diccionario se encuentran dentro de su umbral (por ejemplo, John vs Joan, Joan vs Juan, etc.)? Si introdujo un sistema de ponderación sofisticado, ¿cuántos pares de entradas de diccionario migrarían (a) desde el interior del umbral al exterior (b) y viceversa?

¿Qué haces si Juan y Juan están en tu diccionario y el usuario escribe Joan?

¿Cuáles son las penalidades / costos de (1) elegir la palabra incorrecta del diccionario (no la que el usuario quiso decir) (2) no reconocer la entrada del usuario?

¿La introducción de un sistema de ponderación complicado realmente reduce las probabilidades de los dos tipos de error anteriores con un margen suficiente para que la complicación y la velocidad más lenta valen la pena?

Por cierto, ¿cómo sabes qué teclado estaba usando el usuario?

Actualizar:

"" "Mi algoritmo no ponderado actual falla a menudo cuando me enfrento a errores tipográficos por las razones anteriores." Regresar el jueves ": cada" persona real "puede decir fácilmente que el jueves es más probable que el martes, sin embargo, ambos son 1-edición-distancia de distancia (Sí, registro y mido mi rendimiento). ""

Sí, jueves -> jueves omitiendo una "h", pero martes -> jueves sustituyendo "r" en lugar de "e". E y R están uno al lado del otro en los teclados qwERTY y azERty. Cada "persona real" puede adivinar fácilmente que el jueves es más probable que el martes. Incluso si las estadísticas y las suposiciones apuntan a que el jueves es más probable que el martes (tal vez omitir h costará 0.5 y e-> r costará 0.75), ¿la diferencia (quizás 0.25) será lo suficientemente significativa como para elegir siempre el jueves? Puede / su sistema preguntará "¿Querías decir martes?" ¿o lo hará / seguirá adelante el jueves?

Si la investigación es de su interés, creo que continuar con ese algoritmo, tratar de encontrar pesos decentes sería fructífero.

No puedo ayudarte con las estadísticas de los errores tipográficos, pero creo que también deberías jugar con difflib de Python. Específicamente, el método de proporción () de SequenceMatcher. Utiliza un algoritmo que la declaración http://docs.python.org/library/difflib.html docs es adecuada para coincidencias que parecen correctas, y puede ser útil para aumentar o probar lo que estás haciendo.

Para los programadores de python que solo buscan errores tipográficos, es un buen lugar para comenzar. Uno de mis compañeros de trabajo ha usado la distancia de edición de Levenshtein y la proporción de SequenceMatcher () y obtuvo resultados mucho mejores a partir de la relación ().

Te aconsejaría que revises el trigrama alogrithm . En mi opinión, funciona mejor para encontrar errores tipográficos y luego editar el algoritmo de distancia. También debería funcionar más rápido y si mantiene el diccionario en la base de datos de postgres, puede utilizar el índice.

Puede encontrar un topic útil sobre sobre google "¿Quiso decir?"

Probability Scoring for Spelling Correction de Church and Gale podría ayudar. En ese documento, los autores modelan los errores tipográficos como un canal ruidoso entre el autor y la computadora. El apéndice tiene tablas de errores tipográficos vistos en un corpus de publicaciones de Associated Press. Hay una tabla para cada uno de los siguientes tipos de errores tipográficos:

  • supresión
  • inserción
  • sustitución
  • transposición

Por ejemplo, al examinar la tabla de inserción, podemos ver que l se insertó incorrectamente después de 128 veces (el número más alto en esa columna). Usando estas tablas, puedes generar las probabilidades que estás buscando.