algorithm - quitar - teclado predictivo huawei

Algoritmo de predicción de palabras

Question

Estoy seguro de que hay una publicación sobre esto, pero no pude encontrar una que haga esta pregunta exacta. Considera lo siguiente:

1. Tenemos un diccionario de palabras disponible
2. Nos alimentan muchos párrafos de palabras, y deseo poder predecir la siguiente palabra en una oración dada esta información.

Digamos que tenemos algunas frases como "Hola, mi nombre es Tom", "Su nombre es Jerry", "Va a donde no hay agua". Verificamos una tabla hash si existe una palabra. Si no lo hace, le asignamos un ID único y lo colocamos en la tabla hash. De esta manera, en lugar de almacenar una "cadena" de palabras como un grupo de cadenas, podemos tener una lista de ID únicas.

Por encima, tendríamos, por ejemplo, (0, 1, 2, 3, 4), (5, 2, 3, 6) y (7, 8, 9, 10, 3, 11, 12). Tenga en cuenta que 3 es "es" y agregamos nuevas ID únicas a medida que descubrimos nuevas palabras. Entonces, digamos que se nos da una frase "su nombre es", esto sería (13, 2, 3). Queremos saber, dado este contexto, cuál debería ser la siguiente palabra. Este es el algoritmo en el que pensé, pero no creo que sea eficiente:

1. Tenemos una lista de N cadenas (oraciones observadas) donde una cadena puede ser ex. 3,6,2,7,8.
2. Cada cadena tiene el tamaño promedio M, donde M es la longitud promedio de la oración
3. Nos dan una nueva cadena de talla S, ej. 13, 2, 3, y deseamos saber cuál es la siguiente palabra más probable?

Algoritmo:

1. Primero escanee la lista completa de cadenas para aquellos que contienen la entrada completa de S (13,2,3, en este ejemplo). Ya que tenemos que escanear N cadenas, cada una de longitud M, y comparar S letras a la vez, su O (N * M * S).

2. Si no hay cadenas en nuestro escaneo que tengan la S completa, haga el siguiente escaneo eliminando la palabra menos significativa (es decir, la primera, así que elimine 13). Ahora, busque (2,3) como en 1 en el caso más desfavorable O (N * M * S) que es realmente S-1.

3. Continúe escaneando de esta manera hasta que obtengamos resultados> 0 (si alguna vez).

4. Sume las siguientes palabras en todas las cadenas restantes que hemos reunido. Podemos usar una tabla hash que cuenta cada vez que agregamos y hace un seguimiento de la palabra más agregada. O (N) construcción en el peor de los casos, O (1) para encontrar la palabra máxima.

5. La palabra máxima encontrada es la más probable, así que devuélvala.

Cada escaneo toma el peor de los casos O (M * N * S). Esto se debe a que hay N cadenas, cada cadena tiene números M y debemos verificar los números S para superponer una coincidencia. Escaneamos S en el peor de los casos (13,2,3, luego 2,3, luego 3 para 3 exploraciones = S). Por lo tanto, la complejidad total es O (S ^ 2 * M * N).

Entonces, si tenemos 100,000 cadenas y una oración promedio de 10 palabras, estamos buscando 1,000,000 * S ^ 2 para obtener la palabra óptima. Claramente, N >> M, ya que la longitud de la oración no se escala con el número de oraciones observadas en general, por lo que M puede ser una constante. Entonces podemos reducir la complejidad a O (S ^ 2 * N). Sin embargo, O (S ^ 2 * M * N) puede ser más útil para el análisis, ya que M puede ser una "constante" considerable.

Este podría ser el enfoque totalmente equivocado que se debe tomar para este tipo de problema, pero quería compartir mis pensamientos en lugar de simplemente pedir ayuda de manera descarada. La razón por la que estoy escaneando de la manera que lo hago es porque solo quiero escanear tanto como tengo que hacerlo. Si nada tiene la S completa, solo mantenga la poda S hasta que algunas cadenas coincidan. ¡Si nunca coinciden, no tenemos idea de qué predecir como la siguiente palabra! ¿Alguna sugerencia sobre una solución de menos tiempo / espacio complejo? ¡Gracias!

Answer 1

Este es el problema del modelado del lenguaje . Para un enfoque de línea base, lo único que necesita es una tabla hash que asigne cadenas de palabras de longitud fija, digamos de longitud k , a la palabra siguiente más probable. (*)

En el momento del entrenamiento, (k+1)-grams la entrada en (k+1)-grams utilizando una ventana deslizante. Así que si te encuentras

The wrath sing, goddess, of Peleus'' son, Achilles

generas, para k = 2,

START START the
START the wrath
the wrath sing
wrath sing goddess
goddess of peleus
of peleus son
peleus son achilles

Esto se puede hacer en tiempo lineal. Para cada 3 gramos, marque (en una tabla hash) la frecuencia con que la tercera palabra sigue a las dos primeras.

Finalmente, recorra la tabla hash y para cada clave (2 gramos) mantenga solo la tercera palabra que aparece con más frecuencia. Tiempo lineal.

En el momento de la predicción, mire solo las k (2) últimas palabras y pronostique la siguiente palabra. Esto lleva solo un tiempo constante, ya que es solo una búsqueda de tabla hash.

Si te estás preguntando por qué deberías mantener solo cadenas secundarias cortas en lugar de cadenas completas, entonces analiza la teoría de las ventanas de Markov . Si su modelo recordara todas las cadenas de palabras que ha visto en su entrada, entonces se overfit mal a sus datos de entrenamiento y solo reproducirá su entrada en el momento de la predicción. Qué tanto depende del conjunto de entrenamiento (más datos es mejor), pero para k > 4 realmente necesitaría smoothing su modelo.

(*) O a una distribución de probabilidad, pero esto no es necesario para su caso de uso de ejemplo simple.

Answer 2

Yeh Whye Teh también tiene algunos trabajos interesantes recientes que abordan este problema. El "Memoizer de secuencia" extiende el esquema tradicional de predicción por coincidencia parcial para tener en cuenta historias arbitrariamente largas.

Aquí hay un enlace al documento original: http://www.stats.ox.ac.uk/~teh/research/compling/WooGasArc2011a.pdf

También vale la pena leer algunos de los trabajos de fondo, que se pueden encontrar en el documento "Una interpretación bayesiana de Kneser-Ney interpolada".