⏺️ 😙 🐩 Nuevo servicio de sugerencias para buscar hh.ru 👨🏼‍🔬 🚵🏾 🤴🏻

Las sugerencias de búsqueda son geniales. ¿Con qué frecuencia escribimos la dirección completa del sitio en la barra de direcciones? ¿Y el nombre del producto en la tienda en línea? Para consultas tan cortas, escribir unos pocos caracteres suele ser suficiente si las sugerencias de búsqueda son buenas. Y si no tiene veinte dedos o una increíble velocidad de escritura, seguramente los usará.
En este artículo, hablaremos sobre nuestro nuevo servicio de sugerencias de búsqueda hh.ru, que hicimos en la edición anterior de la School of Programmers .

El antiguo servicio tenía varios problemas:

trabajó en consultas de usuarios populares seleccionadas a mano;
no pudo adaptarse a las preferencias cambiantes del usuario;
no se pudieron clasificar las consultas que no están incluidas en la parte superior;
no corrigió errores tipográficos.

En el nuevo servicio, corregimos estas deficiencias (al tiempo que agregamos otras nuevas).

Diccionario de consultas populares

Cuando no hay pistas, puede seleccionar manualmente las consultas de N principales de los usuarios y generar pistas a partir de estas consultas utilizando la aparición exacta de palabras (con o sin orden). Esta es una buena opción: es fácil de implementar, proporciona una buena precisión de las indicaciones y no experimenta problemas de rendimiento. Durante mucho tiempo, nuestra sugestión funcionó así, pero un inconveniente importante de este enfoque es la insuficiente integridad del problema.

Por ejemplo, la solicitud "desarrollador de JavaScript" no se incluyó en dicha lista, por lo que cuando ingresamos "tiempos de JavaScript" no tenemos nada que mostrar. Si complementamos la solicitud, teniendo en cuenta solo la última palabra, veremos "javascript handyman" en primer lugar. Por la misma razón, no será posible implementar la corrección de errores más difícil que el enfoque estándar con la búsqueda de las palabras más cercanas por la distancia Damerau-Levenshtein.

Modelo de idioma

Otro enfoque es aprender a evaluar las probabilidades de consultas y generar las continuaciones más probables para una consulta de usuario. Para hacer esto, use modelos de lenguaje, una distribución de probabilidad en un conjunto de secuencias de palabras.

word_count

Dado que las solicitudes de los usuarios son en su mayoría cortas, ni siquiera probamos modelos de lenguaje de redes neuronales, sino que nos limitamos a n-gram:

P (w_{1} d o t s w_{m}) = p r o d_{i = 1}^{m} P (w_{i} | w_{1} d o t s w_{i - 1}) a p p r o x p r o d_{i = 1}^{m} P (w_{i} | w_{i - (n - 1)} d o t s w_{i - 1})

$P (w_1 \ dots w_m) = \ prod_ {i = 1} ^ mP (w_i | w_1 \ dots w_ {i-1}) \ approx \ prod_ {i = 1} ^ mP (w_i | w_ {i- ( n-1)} \ dots w_ {i-1})$

Como el modelo más simple, podemos tomar la definición estadística de probabilidad, luego

P (w_{i} | w_{1} d o t s w_{i - 1}) = f r a c c o u n t (w_{1} d o t s w_{i}) c o u n t (w_{1} d o t s w_{i - 1})

$P (w_i | w_1 \ dots w_ {i-1}) = \ frac {count (w_1 \ dots w_i)} {count (w_1 \ dots w_ {i-1})}$

Sin embargo, dicho modelo no es adecuado para evaluar consultas que no estaban en nuestra muestra: si no observamos el 'desarrollador junior java', entonces resulta que

P (t e x t j u n i o r d e v e l o p e r j a v a) = f r a c c o u n t (t e x t j u n i o r d e v e l o p e r j a v a) c o u n t (t e x t j u n i o r d e v e l o p e r) = 0

$P (\ text {junior developer java}) = \ frac {count (\ text {junior developer java})} {count (\ text {junior developer})} = 0$

Para resolver este problema, puede usar varios modelos de suavizado e interpolación. Utilizamos Backoff:

P_{b o} (w_{n} | w_{1} d o t s w_{n - 1}) = b e g i n c a s e s P (w_{n} | w_{1} d o t s w_{n - 1}), c u e n t a (w_{1} d o t s w_{n - 1}) > 0 a l p h a P_{b o} (w_{n} | w_{2} d o t s w_{n - 1}), c o u n t (w_{1} d o t s w_{n - 1}) = 0 e n d c a s e s

$P_ {bo} (w_n | w_1 \ dots w_ {n-1}) = \ begin {cases} {P} (w_n | w_1 \ dots w_ {n-1}), cuenta (w_1 \ dots w_ {n- 1})> 0 \\ \ alpha {P_ {bo}} (w_n | w_2 \ dots w_ {n-1}), count (w_1 \ dots w_ {n-1}) = 0 \ end {cases}$

a l p h a = f r a c P (w_{1} p u n t o s w_{n - 1}) 1 - s u m_{w} P_{b o} (w | w_{2} p u n t o s w_{n - 1})

$\ alpha = \ frac {P (w_1 \ puntos w_ {n-1})} {1 - \ sum_wP_ {bo} (w | w_2 \ puntos w_ {n-1})}$

Donde P es la probabilidad suavizada

w_{1} . . . w_{n - 1}

$w_1 ... w_ {n-1}$ (Utilizamos el suavizado de Laplace):

P (w_{n} | w_{1} d o t s w_{n - 1}) = f r a c c o u n t (w_{n}) + d e l t a c o u n t (w_{1} d o t s w_{n - 1}) + d e l t a | V |

$P (w_n | w_1 \ dots w_ {n-1}) = \ frac {count (w_n) + \ delta} {count (w_1 \ dots w_ {n-1}) + \ delta | V |}$

donde V es nuestro diccionario.

Generación de opciones

Entonces, podemos evaluar la probabilidad de una solicitud en particular, pero ¿cómo generar estas mismas solicitudes? Es aconsejable hacer lo siguiente: dejar que el usuario ingrese una consulta

w_{1} . . . w_{n}

$w_1 ... w_n$ , entonces las consultas que son adecuadas para nosotros se pueden encontrar a partir de la condición

w_{1} d o t s w_{m} = u n d e r s e t w_{n + 1} d o t s w_{m} i n V a r g m a x P (w_{1} d o t s w_{n} w_{n + 1} d o t s w_{m})

$w_1 \ dots w_m = \ underset {w_ {n + 1} \ dots w_m \ in V} {argmax} P (w_1 \ dots w_n w_ {n + 1} \ dots w_m)$

Por supuesto, clasificando

| V |^{m - n}, m = 1 p u n t o s M

$| V | ^ {m-n}, m = 1 \ puntos M$ No es posible seleccionar las mejores opciones para cada solicitud entrante, por lo que utilizaremos Beam Search . Para nuestro modelo de lenguaje n-gram, todo se reduce al siguiente algoritmo:

def beam(initial, vocabulary): variants = [initial] for i in range(P): candidates = [] for variant in variants: candidates.extends(generate_candidates(variant, vocabulary)) variants = sorted(candidates)[:N] return candidates def generate_candidates(variant, vocabulary): top_terms = [] #         1, 2, ... n  for n0 in range(n): top_n = sorted(vocabulary, key=lambda c: P(|variant[-n0:]) top_terms.extends(top_n) candidates = [variant + [term] for term in top_terms] #       candidates = sorted(candidates, key=lambda v: P(variant))[:N] return candidates

Aquí los nodos resaltados en verde son las opciones finales seleccionadas, el número delante del nodo

w_{n}

$w_n$ - probabilidad

P (w_{n} | w_{n - 1})

$P (w_n | w_ {n-1})$ , después del nodo -

P (w 1 . . . w_{n})

$P (w1 ... w_n)$ .

Se ha vuelto mucho mejor, pero en generate_candidates necesitas obtener rápidamente N mejores términos para un contexto dado. En el caso de almacenar solo las probabilidades de n-gramos, necesitamos revisar todo el diccionario, calcular las probabilidades de todas las frases posibles y luego ordenarlas. Obviamente, esto no despegará para consultas en línea.

Boro para probabilidades

Para obtener rápidamente las N mejores variantes de probabilidad condicional de la continuación de la frase, usamos boro en términos. En el nodo

w_{1} a w_{2}

$w_1 \ a w_2$ coeficiente almacenado

a l p h a

$\ alpha$ valor

P (w_{2} | w_{1})

$P (w_2 | w_1)$ y ordenado por probabilidad condicional

P (b u l l e t | w_{1} w_{2})

$P (\ bullet | w_1 w_2)$ lista de términos

w_{3}

$w_3$ junto con

P (w_{3} | w_{1} w_{2})

$P (w_3 | w_1 w_2)$ . El término especial eos marca el final de una frase.
trie

Pero hay un matiz

En el algoritmo descrito anteriormente, asumimos que todas las palabras en la consulta se completaron. Sin embargo, esto no es cierto para la última palabra que el usuario ingresa en este momento. Nuevamente necesitamos revisar todo el diccionario para continuar con la palabra actual que se está ingresando. Para resolver este problema, utilizamos un boro simbólico, en los nodos de los cuales almacenamos M términos ordenados por la probabilidad de unigrama. Por ejemplo, este se verá como nuestro bor para java, junior, jupyter, javascript con M = 3:

trie

Luego, antes de comenzar Beam Search, encontramos los mejores candidatos para continuar con la palabra actual

w_{n}

$w_n$ y selecciona los N mejores candidatos para

P (w_{1} p u n t o s w_{n})

$P (w_1 \ puntos w_n)$ .

Errores tipográficos

Bueno, hemos creado un servicio que le permite dar buenos consejos para una solicitud del usuario. Incluso estamos listos para nuevas palabras. Y todo estaría bien ... Pero los usuarios se cuidan y no cambian los teclados hfcrkflre.

¿Cómo resolver esto? Lo primero que viene a la mente es la búsqueda de correcciones mediante la búsqueda de las opciones más cercanas para la distancia Damerau-Levenshtein, que se define como el número mínimo de inserción / eliminación / reemplazo de un carácter o transposición de dos vecinas necesarias para obtener otro de una línea. Desafortunadamente, esta distancia no tiene en cuenta la probabilidad de un reemplazo particular. Entonces, para la palabra ingresada "zapador", entendemos que las opciones "recolector" y "soldador" son equivalentes, aunque intuitivamente parece que tenían en mente la segunda palabra.

El segundo problema es que no tenemos en cuenta el contexto en el que ocurrió el error. Por ejemplo, en la consulta "Order Sapper" aún deberíamos preferir la opción "colector" en lugar de "soldador".

Si aborda la tarea de corregir errores tipográficos desde un punto de vista probabilístico, es bastante natural llegar a un modelo de canal ruidoso :

conjunto de alfabeto $\ Sigma$ ;
conjunto de todas las líneas finales $\ Sigma ^ *$ sobre él
muchas líneas que son palabras correctas $D \ subseteq \ Sigma ^ *$ ;
distribuciones dadas $P (s | w)$ donde $s \ in \ Sigma ^ *, w \ in D$ .

Luego, la tarea de corrección se establece como encontrar la palabra correcta w para la entrada s. Dependiendo de la fuente del error, mida

P

$P$ se puede construir de diferentes maneras, en nuestro caso es aconsejable tratar de estimar la probabilidad de errores tipográficos (llamémoslos reemplazos elementales)

P_{e} (t | r)

$P_e (t | r)$ , donde t, r son n-gramos simbólicos, y luego evalúa

P (s | w)

$P (s | w)$ como la probabilidad de obtener s de w por los reemplazos elementales más probables.

Dejar

P a r t e_{n} (x)

$Parte_n (x)$ - dividiendo la cadena x en n subcadenas (posiblemente cero). El modelo Brill-Moore implica el cálculo de probabilidad

P (s | w)

$P (s | w)$ como sigue:

P (s | w) \ approx \ max_ {R \ en Parte_n (s)} T \ en Parte_n (s)} \ prod_ {i = 1} ^ {n} P_e (T_i | R_i)

$P (s | w) \ approx \ max_ {R \ en Parte_n (s)} T \ en Parte_n (s)} \ prod_ {i = 1} ^ {n} P_e (T_i | R_i)$

Pero necesitamos encontrar

P (w | s)

$P (w | s)$ :

P (w | s) = f r a c P (s | w) P (w) P (s) = c o n s t c d o t P (s | w) c d o t P (w)

$P (w | s) = \ frac {P (s | w) P (w)} {P (s)} = const \ cdot P (s | w) \ cdot P (w)$

Al aprender a evaluar P (w | s), también resolveremos el problema de clasificar las opciones con la misma distancia Damerau-Levenshtein y podremos tener en cuenta el contexto al corregir un error tipográfico.

Calculo $P_e (T_i | R_i)$

Para calcular las probabilidades de las sustituciones elementales, las consultas de los usuarios nos ayudarán nuevamente: compondremos pares de palabras (s, w) que

cerrar en Damerau-Levenshtein;
Una de las palabras es más común que las otras N veces.

Para tales pares, consideramos la alineación óptima según Levenshtein:

Componemos todas las particiones posibles de syw (nos limitamos a longitudes n = 2, 3): n → n, pr → rn, pro → rn, ro → po, m → ``, mm → m, etc. Para cada n-gramo, encontramos

P_{e} (t | r) = f r a c c u e n t a (r t o t) c u e n t a (r)

$P_e (t | r) = \ frac {cuenta (r \ to t)} {cuenta (r)}$

Calculo $P (s | w)$

Calculo

P (s | w)

$P (s | w)$ toma directamente

O (2^{| w | + | s |})

$O (2 ^ {| w | + | s |})$ : necesitamos clasificar todas las particiones posibles de w con todas las particiones posibles de s. Sin embargo, la dinámica en el prefijo puede dar una respuesta para

O (| w | * | s | * n^{2})

$O (| w | * | s | * n ^ 2)$ donde n es la longitud máxima de las sustituciones elementales:

d [i, j] = \ begin {cases} d [0, j] = 0 & j> = k \\ d [i, 0] = 0 & i> = k \\ d [0, j] = P (s [0: j] \ espacio | \ espacio w [0]) & j <k \\ d [i, 0] = P (s [0] \ espacio | \ espacio w [0: i]) & i <k \\ d [i, j] = \ underset {k, l \ le n, k \ lt i, l \ lt j} {max} (P (s [jl: j] \ space | \ space w [ik: i]) \ cdot d [ik-1, jl-1]) \ end {cases}

$d [i, j] = \ begin {cases} d [0, j] = 0 & j> = k \\ d [i, 0] = 0 & i> = k \\ d [0, j] = P (s [0: j] \ espacio | \ espacio w [0]) & j <k \\ d [i, 0] = P (s [0] \ espacio | \ espacio w [0: i]) & i <k \\ d [i, j] = \ underset {k, l \ le n, k \ lt i, l \ lt j} {max} (P (s [jl: j] \ space | \ space w [ik: i]) \ cdot d [ik-1, jl-1]) \ end {cases}$

Aquí P es la probabilidad de la fila correspondiente en el modelo de k-gramos. Si observa de cerca, es muy similar al algoritmo Wagner-Fisher con recorte de Ukkonen. En cada paso que obtenemos

P (w [0 : i] | s [0 : j])

$P (w [0: i] | s [0: j])$ enumerando todas las correcciones

w [i - k : i]

$w [i-k: i]$ en

s [j - l : j]

$s [j-l: j]$ sujeto a

k, l l e n

$k, l \ le n$ y la elección del más probable.

Volver a $P (w | s)$

Entonces, podemos calcular

P (s | w)

$P (s | w)$ . Ahora necesitamos seleccionar varias opciones para maximizar

P (w | s)

$P (w | s)$ . Más precisamente, para la solicitud original

s_{1} s_{2} d o t s s_{n}

$s_1s_2 \ dots s_n$ debes elegir

w_{1} p u n t o s w_{n}

$w_1 \ puntos w_n$ donde

P (w_{1} p u n t o s w_{n} | s_{1} p u n t o s s_{n})

$P (w_1 \ puntos w_n | s_1 \ puntos s_n)$ máximo Desafortunadamente, una elección honesta de opciones no se ajustaba a nuestros requisitos de tiempo de respuesta (y el plazo del proyecto estaba llegando a su fin), por lo que decidimos centrarnos en el siguiente enfoque:

de la consulta original obtenemos varias opciones cambiando las últimas k palabras:
1. corregimos la distribución del teclado si el término resultante tiene una probabilidad varias veces mayor que el original;
2. encontramos palabras cuya distancia Damerau-Levenshtein no excede d;
3. elija entre ellas las mejores opciones para $P (s | w)$ ;
envíe BeamSearch a la entrada junto con la solicitud original;
al clasificar los resultados, descontamos las opciones obtenidas en $\ prod_ {i = 0} ^ {k-1} P (s_ {n-i} | w_ {n-i})$ .

Para la Cláusula 1.2, utilizamos el algoritmo FB-Trie (trie hacia adelante y hacia atrás), basado en la búsqueda difusa en los árboles de prefijos hacia adelante y hacia atrás. Esto resultó ser más rápido que evaluar P (s | w) en todo el diccionario.

Estadísticas de consulta

Con la construcción del modelo de lenguaje, todo es simple: recopilamos estadísticas sobre las consultas de los usuarios (cuántas veces hemos realizado una consulta para una frase determinada, cuántos usuarios, cuántos usuarios registrados), dividimos las solicitudes en n-gramas y creamos burs. Más complicado con el modelo de error: como mínimo, se necesita un diccionario de las palabras correctas para construirlo. Como se mencionó anteriormente, para seleccionar los pares de entrenamiento, utilizamos el supuesto de que dichos pares deberían estar cerca en la distancia Damerau-Levenshtein, y uno debería ocurrir con más frecuencia que el otro varias veces.

Pero los datos siguen siendo demasiado ruidosos: intentos de inyección xss, diseño incorrecto, texto aleatorio del portapapeles, usuarios experimentados con solicitudes "programador c no 1c", ~~solicitudes del gato que pasó por el teclado~~ .

Por ejemplo, ¿qué trató de encontrar con tal solicitud?

Por lo tanto, para borrar los datos de origen, excluimos:

términos de baja frecuencia;
Contiene operadores de lenguaje de consulta
vocabulario obsceno

También corrigieron la distribución del teclado, verificaron las palabras de los textos de vacantes y diccionarios abiertos. Por supuesto, no fue posible arreglarlo todo, pero tales opciones generalmente están completamente cortadas o ubicadas al final de la lista.

En prod

Justo antes de la protección del proyecto, lanzaron un servicio en producción para pruebas internas y, después de un par de días, para el 20% de los usuarios. En hh.ru, todos los cambios que son significativos para los usuarios pasan por un sistema de pruebas AB , que nos permite no solo estar seguros de la importancia y la calidad de los cambios, sino también encontrar errores .

La métrica del número promedio de búsquedas del sujest para solicitantes se ha mejorado (aumentó de 0.959 a 1.1355), y la proporción de búsquedas del sujest de todas las consultas de búsqueda aumentó del 12.78% al 15.04%. Desafortunadamente, las principales métricas del producto no crecieron, pero los usuarios definitivamente comenzaron a usar más consejos.

Al final

No había lugar para una historia sobre los procesos de la escuela, otros modelos probados, las herramientas que escribimos para las comparaciones de modelos y las reuniones donde decidimos qué características desarrollar para obtener una demostración intermedia. Mire los registros de la escuela anterior , deje una solicitud en https://school.hh.ru , complete tareas interesantes y venga a estudiar. Por cierto, el servicio para verificar tareas también fue realizado por los graduados del conjunto anterior.

Nuevo servicio de sugerencias para buscar hh.ru

Diccionario de consultas populares

Modelo de idioma

Generación de opciones

Boro para probabilidades

Pero hay un matiz

Errores tipográficos

Calculo $P_e (T_i | R_i)$

Calculo $P (s | w)$

Volver a $P (w | s)$

Estadísticas de consulta

En prod

Al final

Que leer

More articles:

Nuevo servicio de sugerencias para buscar hh.ru

Diccionario de consultas populares

Modelo de idioma

Generación de opciones

Boro para probabilidades

Pero hay un matiz

Errores tipográficos

Calculo Pe(Ti|Ri) P_e (T_i | R_i)

Calculo P(s|w) P (s | w)

Volver a P(w|s) P (w | s)

Estadísticas de consulta

En prod

Al final

Que leer

More articles:

Calculo $P_e (T_i | R_i)$

Calculo $P (s | w)$

Volver a $P (w | s)$