Chámome Pavel Parkhomenko, son un programador de ML. Neste artigo, gustaríame falar sobre a estrutura do servizo Yandex.Zen e compartir melloras técnicas, cuxa implementación permitiu aumentar a calidade das recomendacións. Desde esta publicación aprenderás a atopar os máis relevantes para o usuario entre millóns de documentos en só uns milisegundos; como facer a descomposición continua dunha gran matriz (formada por millóns de columnas e decenas de millóns de filas) para que os novos documentos reciban o seu vector en decenas de minutos; como reutilizar a descomposición da matriz usuario-artigo para obter unha boa representación vectorial para o vídeo.
A nosa base de datos de recomendacións contén millóns de documentos de varios formatos: artigos de texto creados na nosa plataforma e tirados de sitios externos, vídeos, narracións e publicacións curtas. O desenvolvemento deste servizo está asociado a un gran número de retos técnicos. Aquí están algúns deles:
- Divide tarefas informáticas: fai todas as operacións pesadas fóra de liña e en tempo real só realiza unha aplicación rápida de modelos para ser responsable de 100-200 ms.
- Teña en conta rapidamente as accións do usuario. Para iso, é necesario que todos os eventos sexan entregados instantáneamente ao recomendador e inflúan nos resultados dos modelos.
- Fai o feed para que para os novos usuarios se adapte rapidamente ao seu comportamento. As persoas que acaban de unirse ao sistema deberían sentir que os seus comentarios inflúen nas recomendacións.
- Comprender rapidamente a quen recomendar un artigo novo.
- Responde rapidamente á aparición constante de novos contidos. Todos os días publícanse decenas de miles de artigos e moitos deles teñen unha vida útil limitada (por exemplo, noticias). Isto é o que os distingue de películas, música e outros contidos de longa duración e custosos de crear.
- Transferir coñecemento dunha área de dominio a outra. Se un sistema de recomendación ten modelos adestrados para artigos de texto e lle engadimos vídeo, podemos reutilizar os modelos existentes para que o novo tipo de contido se clasifique mellor.
Vouvos contar como resolvemos estes problemas.
Selección de candidatos
Como reducir o número de documentos en consideración miles de veces en poucos milisegundos, sen deteriorar practicamente a calidade da clasificación?
Supoñamos que adestramos moitos modelos de ML, xeramos funcións baseadas neles e adestramos outro modelo que clasifica os documentos para o usuario. Todo estaría ben, pero non podes tomar e calcular todos os sinais de todos os documentos en tempo real, se hai millóns destes documentos, e hai que crear recomendacións en 100-200 ms. A tarefa é seleccionar un determinado subconxunto entre millóns, que se clasificará para o usuario. Esta fase adoita chamarse selección de candidatos. Hai varios requisitos para iso. En primeiro lugar, a selección debe realizarse moi rápido, para que quede o máximo de tempo posible para a propia clasificación. En segundo lugar, ao ter reducido moito o número de documentos para a clasificación, debemos conservar os documentos relevantes para o usuario o máis completo posible.
O noso principio de selección de candidatos evolucionou e, polo momento, chegamos a un esquema de varias etapas:
En primeiro lugar, todos os documentos divídense en grupos e os documentos máis populares tómanse de cada grupo. Os grupos poden ser sitios, temas, clusters. Para cada usuario, en función do seu historial, selecciónanse os grupos máis próximos a el e sácanse deles os mellores documentos. Tamén utilizamos o índice kNN para seleccionar os documentos que están máis próximos ao usuario en tempo real. Hai varios métodos para construír un índice kNN; o noso funcionou mellor (Gráficos xerárquicos de pequenos mundos navegables). Este é un modelo xerárquico que permite atopar os N vectores máis próximos para un usuario a partir dunha base de datos de millóns en poucos milisegundos. Primeiro indexamos toda a nosa base de datos de documentos fóra de liña. Dado que a busca no índice funciona con bastante rapidez, se hai varias incrustacións fortes, podes crear varios índices (un índice para cada incrustación) e acceder a cada un deles en tempo real.
Aínda temos decenas de miles de documentos para cada usuario. Aínda é moito para contar todas as funcións, polo que neste momento usamos a clasificación lixeira, un modelo de clasificación pesada e lixeira con menos funcións. A tarefa é prever que documentos terá un modelo pesado na parte superior. Os documentos co predictor máis alto utilizaranse no modelo pesado, é dicir, na última fase de clasificación. Este enfoque permítelle reducir a base de datos de documentos considerados para o usuario de millóns a miles en decenas de milisegundos.
Paso ALS no tempo de execución
Como ter en conta os comentarios dos usuarios inmediatamente despois dun clic?
Un factor importante nas recomendacións é o tempo de resposta aos comentarios dos usuarios. Isto é especialmente importante para os novos usuarios: cando unha persoa comeza a usar o sistema de recomendación, recibe unha fonte non personalizada de documentos de varios temas. En canto faga o primeiro clic, cómpre telo en conta inmediatamente e adaptarse aos seus intereses. Se calculas todos os factores fóra de liña, unha resposta rápida do sistema será imposible debido ao atraso. Polo que é necesario procesar as accións dos usuarios en tempo real. Para estes efectos, usamos o paso ALS en tempo de execución para construír unha representación vectorial do usuario.
Supoñamos que temos unha representación vectorial para todos os documentos. Por exemplo, podemos crear incrustacións fóra de liña baseándonos no texto dun artigo utilizando ELMo, BERT ou outros modelos de aprendizaxe automática. Como podemos obter unha representación vectorial dos usuarios nun mesmo espazo en función das súas interaccións no sistema?
Principio xeral de formación e descomposición da matriz usuario-documentoTemos m usuarios e n documentos. Para algúns usuarios, é coñecida a súa relación con determinados documentos. Entón esta información pódese representar como unha matriz mxn: as filas corresponden aos usuarios e as columnas a documentos. Dado que a persoa non viu a maioría dos documentos, a maioría das celas da matriz permanecerán baleiras, mentres que outras encheranse. Para cada evento (como, non me gusta, clic) indícase algún valor na matriz, pero consideremos un modelo simplificado no que un gústame corresponde a 1 e un non me gusta corresponde a -1.
Descompoñamos a matriz en dúas: P (mxd) e Q (dxn), onde d é a dimensión da representación vectorial (normalmente un número pequeno). Entón, cada obxecto corresponderá a un vector d-dimensional (para un usuario - unha fila na matriz P, para un documento - unha columna na matriz Q). Estes vectores serán as incrustacións dos obxectos correspondentes. Para predicir se a un usuario lle gustará un documento, pode simplemente multiplicar as súas insercións.
Unha das posibles formas de descompoñer unha matriz é ALS (Alternating Least Squares). Optimizaremos a seguinte función de perda:
Aquí rui é a interacción do usuario u co documento i, qi é o vector do documento i, pu é o vector do usuario u.
Entón o vector óptimo de usuario desde o punto de vista do erro cadrado medio (para vectores de documentos fixos) atópase analíticamente resolvendo a regresión lineal correspondente.
Isto chámase "paso ALS". E o propio algoritmo ALS é que alternativamente arranxamos unha das matrices (usuarios e artigos) e actualizamos a outra, atopando a solución óptima.
Afortunadamente, atopar a representación vectorial do usuario é unha operación bastante rápida que se pode facer en tempo de execución usando instrucións vectoriales. Este truco permítelle ter en conta inmediatamente os comentarios dos usuarios na clasificación. A mesma incorporación pódese usar no índice kNN para mellorar a selección de candidatos.
Filtrado colaborativo distribuído
Como facer a factorización matricial distribuída incremental e atopar rapidamente representacións vectoriais de artigos novos?
O contido non é a única fonte de sinais de recomendación. Outra fonte importante é a información colaborativa. Tradicionalmente pódense obter boas características de clasificación a partir da descomposición da matriz usuario-documento. Pero ao tentar facer tal descomposición, atopamos problemas:
1. Temos millóns de documentos e decenas de millóns de usuarios. A matriz non encaixa completamente nunha máquina e a descomposición levará moito tempo.
2. A maior parte do contido do sistema ten unha vida útil curta: os documentos seguen sendo relevantes só unhas horas. Polo tanto, é necesario construír a súa representación vectorial o máis rápido posible.
3. Se constrúe unha descomposición inmediatamente despois da publicación do documento, un número suficiente de usuarios non terá tempo para avaliala. Polo tanto, a súa representación vectorial probablemente non será moi boa.
4. Se a un usuario lle gusta ou non lle gusta, non poderemos telo en conta inmediatamente na descomposición.
Para resolver estes problemas, implementamos unha descomposición distribuída da matriz usuario-documento con actualizacións incrementais frecuentes. Como funciona exactamente?
Supoñamos que temos un grupo de N máquinas (N está en centos) e queremos facer unha descomposición distribuída dunha matriz sobre elas que non cabe nunha máquina. A cuestión é como realizar esta descomposición para que, por unha banda, haxa datos suficientes en cada máquina e, por outra, para que os cálculos sexan independentes?
Usaremos o algoritmo de descomposición ALS descrito anteriormente. Vexamos como executar un paso ALS de forma distribuída: o resto dos pasos serán similares. Digamos que temos unha matriz fixa de documentos e queremos construír unha matriz de usuarios. Para iso, dividirémolo en N partes por liñas, cada parte conterá aproximadamente o mesmo número de liñas. Enviaremos a cada máquina celas non baleiras das filas correspondentes, así como a matriz de incrustacións de documentos (totalmente). Dado que o seu tamaño non é moi grande e a matriz de documentos de usuario adoita ser moi escasa, estes datos caberán nunha máquina normal.
Este truco pódese repetir durante varias épocas ata que o modelo converxa, alternando a matriz fixa unha por unha. Pero aínda así, a descomposición da matriz pode levar varias horas. E isto non soluciona o problema que precisa para recibir rapidamente incrustacións de novos documentos e actualizar as incrustacións daqueles sobre os que había pouca información ao construír o modelo.
A introdución de actualizacións de modelos incrementais rápidas axudounos. Digamos que temos un modelo adestrado actualmente. Desde a súa formación, houbo novos artigos cos que interactuaron os nosos usuarios, así como artigos que tiveron pouca interacción durante o adestramento. Para obter rapidamente as incrustacións deste tipo de artigos, usamos as incrustacións de usuarios obtidas durante o primeiro adestramento grande do modelo e facemos un paso ALS para calcular a matriz do documento dada unha matriz de usuario fixa. Isto permítelle recibir incrustacións con bastante rapidez -en poucos minutos despois da publicación do documento- e, a miúdo, actualizar as incrustacións dos documentos recentes.
Para facer recomendacións tendo en conta inmediatamente as accións humanas, en tempo de execución non utilizamos as incorporacións de usuarios obtidas sen conexión. Pola contra, facemos un paso ALS e obtemos o vector de usuario real.
Transferir a outra área de dominio
Como usar os comentarios dos usuarios sobre artigos de texto para construír unha representación vectorial dun vídeo?
Inicialmente, recomendabamos só artigos de texto, polo que moitos dos nosos algoritmos están adaptados a este tipo de contido. Pero á hora de engadir outro tipo de contidos, vímonos ante a necesidade de adaptar os modelos. Como resolvemos este problema usando un exemplo de vídeo? Unha opción é reciclar todos os modelos desde cero. Pero isto leva moito tempo, e algúns dos algoritmos esixen o tamaño da mostra de adestramento, que aínda non está dispoñible na cantidade necesaria para un novo tipo de contido nos primeiros momentos da súa vida no servizo.
Fomos por outro lado e reutilizamos os modelos de texto para o vídeo. O mesmo truco de ALS axudounos a crear representacións vectoriais de vídeos. Fixemos unha representación vectorial dos usuarios baseada en artigos de texto e fixemos un paso de ALS usando información de visualización de vídeo. Así que obtivemos facilmente unha representación vectorial do vídeo. E no tempo de execución simplemente calculamos a proximidade entre o vector de usuario obtido dos artigos de texto e o vector de vídeo.
Conclusión
Desenvolver o núcleo dun sistema de recomendación en tempo real implica moitos retos. Debe procesar datos rapidamente e aplicar métodos de ML para utilizar estes datos de forma eficaz; construír sistemas distribuídos complexos capaces de procesar sinais de usuarios e novas unidades de contido nun tempo mínimo; e moitas outras tarefas.
No sistema actual, cuxo deseño describín, a calidade das recomendacións para o usuario crece xunto coa súa actividade e a duración da permanencia no servizo. Pero, por suposto, aquí reside a principal dificultade: é difícil que o sistema comprenda inmediatamente os intereses dunha persoa que ten pouca interacción co contido. Mellorar as recomendacións para novos usuarios é o noso obxectivo fundamental. Seguiremos optimizando os algoritmos para que o contido que sexa relevante para unha persoa entre máis rápido no seu feed e non se mostre o contido irrelevante.
Fonte: www.habr.com