De la heurística al aprendizaje automático: sugerencias de búsqueda en Citymobil

¡Hola! Mi nombre es Mikhail Dyachkov y en Citymobil hago aprendizaje automático. Hoy les hablaré de nuestro nuevo algoritmo para generar sugerencias de búsqueda para destinos finales. Aprenderás cómo una tarea aparentemente sencilla se transformó en un escenario interesante, con la ayuda del cual, esperamos, logramos hacer un poco más fácil la vida de los usuarios. Continuamos monitoreando de cerca el trabajo del nuevo algoritmo y posteriormente lo ajustaremos para mantener la calidad de la clasificación en un nivel alto. Para todos los usuarios, lanzaremos el algoritmo en las próximas semanas, pero ya estamos listos para hablar sobre el largo viaje que hemos recorrido desde la heurística hasta el algoritmo de aprendizaje automático y su implementación.



Creo que vale la pena comenzar por describir la visión del mundo ideal de un escenario de pedido de taxi desde una perspectiva de interfaz de usuario. Me gustaría que nuestra aplicación se entendiera dónde / dónde / cuándo / en qué automóvil el usuario quiere irse. En este artículo, veremos nuestra solución para responder la pregunta "dónde".



Uno de los elementos centrales de la primera pantalla (el que ve el usuario después de iniciar sesión) son las sugerencias de búsqueda. En el equipo de búsqueda geográfica, los llamamos "sajest" (de la sugerencia en inglés). Ofrecen al usuario las direcciones de ruta finales (puntos "B") de su historial de viajes en función de la ubicación actual del pin (es decir, el punto de salida) y la hora del día sin ingresar una consulta de búsqueda. Tratamos de ayudar al usuario a formar un pedido "en un clic" con la ayuda de expertos. En la versión actual de la aplicación cliente de iOS, los sajests se ven así:







La búsqueda geográfica, debido a los algoritmos para generar resultados de búsqueda, puede afectar algunas de las métricas de producto más importantes para la aplicación cliente, como el tiempo dedicado a pedir un taxi ( Time to order , o T2O ), así como el número de acciones que realizó el cliente para formar un pedido ( Acciones a pedido , o A2O). Por lo tanto, decidimos desarrollar un algoritmo que predecirá los puntos finales más probables de la ruta (puntos "B") para una ubicación y hora del día determinadas.

Heurístico

Uno de los desarrolladores de backend del equipo de búsqueda geográfica (vasilesk, hola!) se le ocurrió una heurística bastante simple para generar sajests que funcionaba tanto para el punto de inicio "A" como para el punto final "B". Cabe señalar de inmediato que la heurística no funcionó en el historial de viajes del usuario, sino en el historial de clics en los resultados de búsqueda, lo que conllevó algunos problemas. A estos objetos los llamamos "picos" (del inglés. El pico ). La heurística se veía así:

1. Para el usuario actual, tomamos todos sus picos históricos.
2. Los filtramos, dejando aquellos con el mismo objetivo (desde / dónde).
3. , , 300 ( «» — 300 «», «» — 300 «»). , GPS- .
4. , , , , , .
5. , , 3:00 14:00, , .
6. - (), , - .
7. .

Este algoritmo funcionó durante un tiempo y, en general, fue bueno para los MVP (hablaremos de métricas un poco más adelante), pero tenía una serie de inconvenientes. Además de la lógica bastante primitiva del trabajo, no se basaba en viajes, sino en elecciones de los usuarios. Debido a esto, a veces los usuarios obtienen resultados de búsqueda no evidentes. Y también, debido a la forma "específica" de almacenar el historial de los picos, era bastante difícil realizar análisis rápidos. En base a esto, decidimos intentar aplicar el aprendizaje automático. A continuación, consideraremos la formulación de problemas de clasificación y reduciremos nuestro problema a una clasificación binaria.

Enunciado del problema de clasificación

Antes de hablar de características, métricas y un modelo, debemos averiguar qué tipo de problema estamos tratando de resolver. Vayamos iterativamente y primero intentemos formular una formulación general del problema de clasificación. Se parece a esto:



$$$X$ - muchos objetos.



$$$X^l = \{x_1, \dots, x_l \}$ - muestra de formación. 



$$$i \prec j$ - orden correcto en parejas $$$(i, j)$



Objetivo: construir una función de clasificación $$$a: X \rightarrow ℝ$, con la cual 

$$

$$i \prec j ⇒  a(x_i) < a(x_j)$$

Ahora formulemos la tarea de clasificar los resultados de búsqueda por consulta. Se diferencia del problema de clasificación general en que en lugar del conjunto general de objetos que necesitamos clasificar, aparecen dos conjuntos$$$D$ y $$$Q$ - muchos documentos y solicitudes.



$$$D$ - colección de documentos (respuestas).



$$$Q$ - muchas solicitudes.



$$$D_q \subseteq D$ - el conjunto de documentos encontrados por la consulta q.



$$$X = Q \times D$ - los objetos son pares "solicitud, documento": $$$x \equiv (q, d), q \in Q, d \in D_q$



$$$Y$ - un conjunto ordenado de calificaciones (calificaciones).



$$$y(q, d): X \rightarrow Y$- puntuaciones de relevancia.



Cuanto mayor sea la puntuación$$$y(q, d)$, cuanto más relevante es el documento $$$d$ solicitud $$$q$...



El orden correcto se define solo entre aquellos documentos que fueron encontrados por la misma consulta$$$q$: 

$$

$$(q, d) \prec (q, d') \Leftrightarrow y(q, d) < y(q, d')$$

En nuestra tarea de recomendar puntos finales de ruta, el conjunto de calificaciones es binario. Para el usuario, la dirección sugerida puede ser relevante o irrelevante (excluyendo casos con una ruta compleja con múltiples puntos finales). Si consideramos la tarea en el contexto del usuario, entonces$$$q$- una solicitud al servicio, que contiene la identificación del cliente, la posición geográfica, la fecha y la hora;$$$D_q$- muchos puntos finales históricos "B" para los viajes del usuario (solo hacemos sugerencias basadas en las direcciones de viajes anteriores). Y cada respuesta válida$$$d \in D_q$ bajo pedido $$$q$ puede ser relevante para el usuario (desde el punto actual y en el momento actual, el usuario debe ir exactamente aquí) o irrelevante.



En aras de la exhaustividad, solo queda describir el proceso de creación de una muestra de pares de solicitud-respuesta con un objetivo. Considere, para simplificar, un cliente que haya tenido 5 viajes. Clasifiquemos estos viajes desde el primero hasta el último. Para el primer viaje, no sabemos nada sobre los viajes del usuario, por lo que no podemos ofrecerle un sabio usando el algoritmo de aprendizaje automático descrito (la heurística para nuevos usuarios funciona aquí). Para el segundo viaje, conocemos el destino final del primer viaje y podemos ofrecer esta dirección al usuario si supera con éxito el procedimiento de post-procesamiento (ubicado a más de 1 km de la ubicación actual, en la misma región, etc.). Para el tercer viaje, es posible que ya tengamos de uno a dos posibles sadgets,si la dirección final del segundo viaje era la misma que la dirección final del primero y si las direcciones finales eran diferentes, respectivamente. Si el más sajest coincidió con el punto final "B" (es decir, cayó en el mismo hexágono de un tamaño fijo), entonces establecemos 1 como el objetivo, de lo contrario - 0. De acuerdo con este algoritmo, formamos todo tipo de pares de la forma "solicitud - (posible) respuesta "Para cada cliente.



Por lo tanto, hemos reducido el problema de clasificación a un problema de clasificación binaria. Ahora podemos hablar de métricas de evaluación de la calidad.

Métrica

En la clasificación de problemas, una métrica que muestra la proporción de respuestas correctas de los documentos. $$$D_q$ a la cima $$$n$ lista de clasificación cuando se solicite $$$q$se llaman Precision @ n . Estamos interesados ​​en Precision @ 1/2/3 , ya que la tasa de clics total para las tres primeras posiciones es aproximadamente del 95%. Al mismo tiempo, solo hay una dirección final correcta (naturalmente, si el usuario quiere irse a una dirección de su historial), por lo tanto, esta métrica solo mostrará la proporción de casos en que el punto final "B" correcto cae en las direcciones 1/2/3 superiores que sugirió nuestro algoritmo.



Recuerda que en nuestro problema$$$Y = \{0, 1\},\; y(q, d)$ - Relevancia, $$$a(q, d)$Es la función de clasificación requerida. Entonces Precision @ n se puede escribir como:

$$

$$P_n(q) = \frac{1}{n}\sum_{i=1}^{n} y(q, d_q^{(i)})$$

Signos y modelo

Las características del modelo de nuestro problema se pueden dividir en varios bloques:

• Solo para documento $$$d \in D_q$ (dirección final, punto "B").
• Solo para solicitud $$$q$ (dirección inicial, punto "A").
• Común para solicitar y documentar $$$(q, d)$ (ruta de "A" a "B").
• General para el usuario.

A continuación se muestran algunos ejemplos de cada uno de ellos.



Ejemplos de signos solo para el documento (punto "B"):

1. Número de viajes al punto "B" en los últimos K días.
2. Número de viajes al punto "B" por día de la semana y hora del día.
3. Cuándo fue el viaje anterior al punto “B”.
4. Marcar que el viaje anterior se realizó al punto "B".
5. ¿Es el punto "B" una dirección / casa / trabajo elegidos?

Ejemplos de características solo para solicitud $$$q$ ( «» + /):

1. , .
2. «».
3. «» K .
4. «» .
5. «» //.
6. / $$$q$.
7. «».

, $$$(q, d)$ ( «» “”):

1. , .
2. .
3. .

:

1. K .
2. .
3. Estadísticas históricas de viaje (media, cuantiles, mediana de distancia de viaje, etc.).

Como resultado, obtuvimos más de 100 características que describen un par de objetos de "solicitud-documento". Dado que queremos maximizar la Precisión @ 1/2/3 , es lógico que necesitemos predecir la probabilidad de que un usuario viaje a un destino específico y clasificar a los posibles candidatos de acuerdo con la probabilidad obtenida. Probamos diferentes algoritmos y diferentes funciones de pérdida, y nos decidimos por el aumento de gradiente en árboles y logloss . Los resultados que se obtuvieron al momento de utilizar la heurística:

Producción

Naturalmente, antes de idear algoritmos, funciones y modelos de entrenamiento complejos, debes pensar en cómo funcionará todo esto en combate bajo carga, sin olvidarte de escalar. Habiéndonos reunido con el equipo de desarrollo de backend, esbozamos un esquema general de cómo debería verse nuestro servicio. Decidimos envolver el modelo de aprendizaje automático entrenado en el marco web async-await Sanic, a la que el servicio de búsqueda enviará solicitudes. Además del escalado vertical, hemos implementado la capacidad de implementar en múltiples máquinas. Las solicitudes al servicio se enviarán a la URL del equilibrador de carga y luego se realizará el proxy a esta o aquella máquina mediante el algoritmo Round-robin. Después de implementar el primer prototipo del servicio, nos dimos cuenta de que podíamos reducir significativamente el volumen de consultas en MySQL. Dado que cualquier desplazamiento del pin con la elección del punto de alimentación es una nueva solicitud de búsqueda, y por lo tanto para nuestro servicio, pensamos que podríamos almacenar un caché con el historial de viajes del usuario durante N minutos desde el momento de la solicitud a Redis. Gracias a esto, hemos reducido tres veces la carga sobre la base. Como resultado, el esquema de servicio se puede representar de la siguiente manera:







Almacenamos las solicitudes al servicio y sus respuestas en ElasticSearch, y transferimos y monitoreamos las métricas que son responsables de la estabilidad del trabajo en NewRelic.



El flujo de trabajo general de nuestro servicio:

1. El servicio de búsqueda envía una solicitud al servicio de sugerencias de búsqueda.
2. El equilibrador selecciona una de las máquinas y le envía esta solicitud.
3. Dentro de la máquina, la solicitud se envía a uno de los trabajadores abiertos o ingresa a la cola.
4. Dentro del trabajador:
   1. Validamos la solicitud entrante.
   2. Hacemos una solicitud en Redis, si no hay historial de pedidos para el usuario, vamos a MySQL y escribimos los datos recibidos en Redis.
   3. Realizamos preprocesamiento de datos básicos y recopilamos características para el modelo.
   4. Lo hacemos de predict_proba()acuerdo con todos los sajests generados y los ordenamos por "probabilidad".
   5. Realizamos un posprocesamiento adicional de los datos y formamos la respuesta.
   6. Devolvemos la respuesta al servicio de búsqueda.

¿Que sigue?

Ahora estamos probando activamente nuestro modelo utilizando pruebas de retroceso para sacar conclusiones e implementar complementos adicionales al algoritmo para mejorar la calidad de la clasificación. En el futuro, intentaremos agregar características adicionales al modelo, así como, junto con los diseñadores de productos, preparar una nueva solución para la "exhibición" de los sabios. Por supuesto, sería genial si nuestra propia aplicación entendiera dónde / cuándo / dónde / en qué coche quiere salir el usuario. Trabajamos en todas las direcciones para que un pedido de taxi se realice realmente en un clic.