Mi nombre es Pavel Parkhomenko, soy desarrollador de ML. En este artículo me gustaría hablar sobre la estructura del servicio Yandex.Zen y compartir mejoras técnicas, cuya implementación permitió aumentar la calidad de las recomendaciones. En este post aprenderás cómo encontrar los más relevantes para el usuario entre millones de documentos en tan solo unos milisegundos; cómo realizar una descomposición continua de una matriz grande (que consta de millones de columnas y decenas de millones de filas) para que los nuevos documentos reciban su vector en decenas de minutos; cómo reutilizar la descomposición de la matriz usuario-artículo para obtener una buena representación vectorial para video.
Nuestra base de datos de recomendaciones contiene millones de documentos de diversos formatos: artículos de texto creados en nuestra plataforma y extraídos de sitios externos, videos, narrativas y publicaciones breves. El desarrollo de un servicio de este tipo está asociado a una gran cantidad de desafíos técnicos. Éstos son algunos de ellos:
- Divida las tareas informáticas: realice todas las operaciones pesadas sin conexión y en tiempo real solo realice aplicaciones rápidas de modelos para ser responsable de 100 a 200 ms.
- Tenga en cuenta rápidamente las acciones del usuario. Para hacer esto, es necesario que todos los eventos se entreguen instantáneamente al recomendador e influyan en los resultados de los modelos.
- Haz que el feed se adapte rápidamente a su comportamiento para los nuevos usuarios. Las personas que acaban de unirse al sistema deberían sentir que sus comentarios influyen en las recomendaciones.
- Comprenda rápidamente a quién recomendar un nuevo artículo.
- Responda rápidamente a la constante aparición de nuevos contenidos. Cada día se publican decenas de miles de artículos y muchos de ellos tienen una vida útil limitada (digamos, noticias). Esto es lo que los distingue de las películas, la música y otros contenidos duraderos y costosos de crear.
- Transferir conocimientos de un área de dominio a otra. Si un sistema de recomendación tiene modelos entrenados para artículos de texto y le agregamos video, podemos reutilizar los modelos existentes para que el nuevo tipo de contenido se clasifique mejor.
Te diré cómo resolvimos estos problemas.
Selección de candidatos
¿Cómo reducir el número de documentos considerados miles de veces en unos pocos milisegundos, sin prácticamente ningún deterioro en la calidad de la clasificación?
Supongamos que entrenamos muchos modelos de ML, generamos funciones basadas en ellos y entrenamos otro modelo que clasifica documentos para el usuario. Todo estaría bien, pero no se pueden simplemente tomar y calcular todos los signos de todos los documentos en tiempo real, si hay millones de estos documentos y las recomendaciones deben crearse en 100-200 ms. La tarea consiste en seleccionar un subconjunto determinado entre millones, que se clasificará para el usuario. Esta etapa suele denominarse selección de candidatos. Existen varios requisitos para ello. En primer lugar, la selección debe realizarse muy rápidamente, de modo que quede el mayor tiempo posible para la clasificación en sí. En segundo lugar, habiendo reducido considerablemente el número de documentos para clasificar, debemos preservar los documentos relevantes para el usuario de la forma más completa posible.
Nuestro principio de selección de candidatos ha evolucionado y por el momento hemos llegado a un esquema de varias etapas:
Primero, todos los documentos se dividen en grupos y de cada grupo se toman los documentos más populares. Los grupos pueden ser sitios, temas, clusters. Para cada usuario, en función de su historial, se seleccionan los grupos más cercanos a él y de ellos se extraen los mejores documentos. También utilizamos el índice kNN para seleccionar los documentos más cercanos al usuario en tiempo real. Existen varios métodos para construir un índice kNN; el nuestro funcionó mejor (Gráficos jerárquicos de mundos pequeños navegables). Este es un modelo jerárquico que permite encontrar los N vectores más cercanos para un usuario a partir de una base de datos de millones en unos pocos milisegundos. Primero indexamos toda nuestra base de datos de documentos sin conexión. Dado que la búsqueda en el índice funciona con bastante rapidez, si hay varias incrustaciones sólidas, puede crear varios índices (un índice para cada incrustación) y acceder a cada uno de ellos en tiempo real.
Todavía tenemos decenas de miles de documentos para cada usuario. Todavía es mucho para contar todas las funciones, por lo que en esta etapa utilizamos una clasificación ligera, un modelo de clasificación pesado y liviano con menos funciones. La tarea es predecir qué documentos tendrá un modelo pesado en la parte superior. Los documentos con el predictor más alto se utilizarán en el modelo pesado, es decir, en la última etapa de clasificación. Este enfoque le permite reducir la base de datos de documentos considerados por el usuario de millones a miles en decenas de milisegundos.
Paso de ALS en tiempo de ejecución
¿Cómo tener en cuenta los comentarios de los usuarios inmediatamente después de un clic?
Un factor importante en las recomendaciones es el tiempo de respuesta a los comentarios de los usuarios. Esto es especialmente importante para los nuevos usuarios: cuando una persona recién comienza a utilizar el sistema de recomendación, recibe una fuente no personalizada de documentos sobre diversos temas. Tan pronto como haga el primer clic, debes tenerlo en cuenta inmediatamente y adaptarte a sus intereses. Si calcula todos los factores fuera de línea, será imposible una respuesta rápida del sistema debido al retraso. Por eso es necesario procesar las acciones del usuario en tiempo real. Para estos fines, utilizamos el paso ALS en tiempo de ejecución para crear una representación vectorial del usuario.
Supongamos que tenemos una representación vectorial para todos los documentos. Por ejemplo, podemos crear incrustaciones fuera de línea basadas en el texto de un artículo utilizando ELMo, BERT u otros modelos de aprendizaje automático. ¿Cómo podemos obtener una representación vectorial de los usuarios en un mismo espacio en función de sus interacciones en el sistema?
Principio general de formación y descomposición de la matriz usuario-documento.Tengamos m usuarios yn documentos. Para algunos usuarios, se conoce su relación con determinados documentos. Entonces esta información se puede representar como una matriz mxn: las filas corresponden a los usuarios y las columnas corresponden a los documentos. Como la persona no ha visto la mayoría de los documentos, la mayoría de las celdas de la matriz permanecerán vacías, mientras que otras estarán llenas. Para cada evento (me gusta, no me gusta, hacer clic), se proporciona algún valor en la matriz, pero consideremos un modelo simplificado en el que un me gusta corresponde a 1 y un no me gusta corresponde a -1.
Descompongamos la matriz en dos: P (mxd) y Q (dxn), donde d es la dimensión de la representación vectorial (generalmente un número pequeño). Entonces, cada objeto corresponderá a un vector d-dimensional (para un usuario, una fila en la matriz P, para un documento, una columna en la matriz Q). Estos vectores serán las incrustaciones de los objetos correspondientes. Para predecir si a un usuario le gustará un documento, simplemente puede multiplicar sus incrustaciones.
Una de las posibles formas de descomponer una matriz es ALS (Mínimos cuadrados alternos). Optimizaremos la siguiente función de pérdida:
Aquí rui es la interacción del usuario u con el documento i, qi es el vector del documento i, pu es el vector del usuario u.
Luego, el vector de usuario óptimo desde el punto de vista del error cuadrático medio (para vectores de documentos fijos) se encuentra analíticamente resolviendo la regresión lineal correspondiente.
Esto se llama "paso ALS". Y el algoritmo ALS en sí consiste en que alternativamente arreglamos una de las matrices (usuarios y artículos) y actualizamos la otra, encontrando la solución óptima.
Afortunadamente, encontrar la representación vectorial del usuario es una operación bastante rápida que se puede realizar en tiempo de ejecución mediante instrucciones vectoriales. Este truco le permite tener en cuenta inmediatamente los comentarios de los usuarios en la clasificación. La misma incorporación se puede utilizar en el índice kNN para mejorar la selección de candidatos.
Filtrado colaborativo distribuido
¿Cómo realizar una factorización matricial distribuida incremental y encontrar rápidamente representaciones vectoriales de nuevos artículos?
El contenido no es la única fuente de señales de recomendación. Otra fuente importante es la información colaborativa. Tradicionalmente se pueden obtener buenas características de clasificación a partir de la descomposición de la matriz de documentos de usuario. Pero al intentar hacer tal descomposición, encontramos problemas:
1. Tenemos millones de documentos y decenas de millones de usuarios. La matriz no cabe enteramente en una sola máquina y su descomposición tardará mucho tiempo.
2. La mayor parte del contenido del sistema tiene una vida útil corta: los documentos siguen siendo relevantes sólo durante unas pocas horas. Por tanto, es necesario construir su representación vectorial lo más rápido posible.
3. Si crea una descomposición inmediatamente después de la publicación del documento, un número suficiente de usuarios no tendrá tiempo de evaluarlo. Por tanto, lo más probable es que su representación vectorial no sea muy buena.
4. Si a un usuario le gusta o no le gusta, no podremos tenerlo en cuenta inmediatamente en la descomposición.
Para resolver estos problemas, implementamos una descomposición distribuida de la matriz de documentos de usuario con actualizaciones incrementales frecuentes. ¿Cómo funciona exactamente?
Supongamos que tenemos un grupo de N máquinas (N son cientos) y queremos hacer una descomposición distribuida de una matriz en ellas que no cabe en una máquina. La pregunta es ¿cómo realizar esta descomposición para que, por un lado, haya suficientes datos en cada máquina y, por otro lado, para que los cálculos sean independientes?
Usaremos el algoritmo de descomposición ALS descrito anteriormente. Veamos cómo ejecutar un paso de ALS de forma distribuida; el resto de los pasos serán similares. Digamos que tenemos una matriz fija de documentos y queremos construir una matriz de usuarios. Para ello lo dividiremos en N partes por líneas, cada parte contendrá aproximadamente la misma cantidad de líneas. Enviaremos a cada máquina celdas no vacías de las filas correspondientes, así como la matriz de incrustaciones de documentos (completamente). Dado que su tamaño no es muy grande y la matriz de documentos de usuario suele ser muy escasa, estos datos caben en una máquina normal.
Este truco se puede repetir durante varias épocas hasta que el modelo converja, alternando la matriz fija una por una. Pero incluso entonces, la descomposición de la matriz puede tardar varias horas. Y esto no resuelve el problema de que es necesario recibir rápidamente incrustaciones de nuevos documentos y actualizar las incrustaciones de aquellos sobre los que había poca información al construir el modelo.
La introducción de rápidas actualizaciones incrementales del modelo nos ayudó. Digamos que tenemos un modelo actualmente entrenado. Desde su capacitación, ha habido nuevos artículos con los que nuestros usuarios han interactuado, así como artículos que tuvieron poca interacción durante la capacitación. Para obtener rápidamente las incorporaciones de dichos artículos, utilizamos las incorporaciones de usuario obtenidas durante el primer gran entrenamiento del modelo y realizamos un paso de ALS para calcular la matriz del documento dada una matriz de usuario fija. Esto le permite recibir incrustaciones con bastante rapidez (unos pocos minutos después de la publicación del documento) y, a menudo, actualizar las incrustaciones de documentos recientes.
Para hacer recomendaciones, tenga en cuenta inmediatamente las acciones humanas; en tiempo de ejecución no utilizamos incrustaciones de usuarios obtenidas sin conexión. En su lugar, realizamos un paso ALS y obtenemos el vector de usuario real.
Transferir a otra área de dominio
¿Cómo utilizar los comentarios de los usuarios sobre artículos de texto para crear una representación vectorial de un vídeo?
Inicialmente, recomendábamos solo artículos de texto, por lo que muchos de nuestros algoritmos se adaptan a este tipo de contenido. Pero al añadir otro tipo de contenidos nos enfrentamos a la necesidad de adaptar los modelos. ¿Cómo resolvimos este problema usando un ejemplo de video? Una opción es volver a entrenar todos los modelos desde cero. Pero esto lleva mucho tiempo y algunos de los algoritmos exigen el tamaño de la muestra de entrenamiento, que aún no está disponible en la cantidad necesaria para un nuevo tipo de contenido en los primeros momentos de su vida en el servicio.
Fuimos por el otro lado y reutilizamos los modelos de texto para el video. El mismo truco de ALS nos ayudó a crear representaciones vectoriales de vídeos. Tomamos una representación vectorial de los usuarios basada en artículos de texto e hicimos un paso de ALS utilizando información de visualización de video. Entonces obtuvimos fácilmente una representación vectorial del video. Y en tiempo de ejecución simplemente calculamos la proximidad entre el vector de usuario obtenido de los artículos de texto y el vector de vídeo.
Conclusión
Desarrollar el núcleo de un sistema de recomendación en tiempo real implica muchos desafíos. Debe procesar datos rápidamente y aplicar métodos de aprendizaje automático para utilizar estos datos de manera eficaz; construir sistemas distribuidos complejos capaces de procesar señales de usuario y nuevas unidades de contenido en un tiempo mínimo; y muchas otras tareas.
En el sistema actual, cuyo diseño describí, la calidad de las recomendaciones para el usuario crece junto con su actividad y la duración de su permanencia en el servicio. Pero claro, aquí radica la principal dificultad: al sistema le resulta difícil comprender inmediatamente los intereses de una persona que tiene poca interacción con el contenido. Mejorar las recomendaciones para nuevos usuarios es nuestro objetivo clave. Continuaremos optimizando los algoritmos para que el contenido relevante para una persona llegue a su feed más rápido y no se muestre contenido irrelevante.
Fuente: habr.com