Como trabalhamos a qualidade e rapidez na seleção das recomendações

Meu nome é Pavel Parkhomenko, sou desenvolvedor de ML. Neste artigo gostaria de falar sobre a estrutura do serviço Yandex.Zen e compartilhar melhorias técnicas, cuja implementação permitiu aumentar a qualidade das recomendações. Neste post você aprenderá como encontrar os mais relevantes para o usuário entre milhões de documentos em apenas alguns milissegundos; como fazer a decomposição contínua de uma grande matriz (composta por milhões de colunas e dezenas de milhões de linhas) para que novos documentos recebam seu vetor em dezenas de minutos; como reutilizar a decomposição da matriz usuário-artigo para obter uma boa representação vetorial para vídeo.

Nosso banco de dados de recomendações contém milhões de documentos de diversos formatos: artigos de texto criados em nossa plataforma e retirados de sites externos, vídeos, narrativas e posts curtos. O desenvolvimento de tal serviço está associado a um grande número de desafios técnicos. Aqui estão alguns deles:

• Divida as tarefas de computação: faça todas as operações pesadas offline e em tempo real execute apenas a aplicação rápida de modelos para ser responsável por 100-200 ms.
• Leve rapidamente em consideração as ações do usuário. Para isso, é necessário que todos os eventos sejam entregues instantaneamente ao recomendador e influenciem nos resultados dos modelos.
• Faça o feed de forma que para novos usuários ele se adapte rapidamente ao seu comportamento. As pessoas que acabaram de aderir ao sistema devem sentir que o seu feedback influencia as recomendações.
• Entenda rapidamente para quem recomendar um novo artigo.
• Responda rapidamente ao constante surgimento de novos conteúdos. Dezenas de milhares de artigos são publicados todos os dias, e muitos deles têm uma vida útil limitada (por exemplo, notícias). Isto é o que os distingue de filmes, músicas e outros conteúdos de longa duração e caros de criar.
• Transferir conhecimento de uma área de domínio para outra. Se um sistema de recomendação treinou modelos para artigos de texto e adicionamos vídeo a ele, podemos reutilizar os modelos existentes para que o novo tipo de conteúdo seja melhor classificado.

Vou lhe contar como resolvemos esses problemas.

Seleção de candidatos

Como reduzir milhares de vezes o número de documentos considerados em poucos milissegundos, praticamente sem deterioração na qualidade da classificação?

Suponha que treinamos muitos modelos de ML, geramos recursos com base neles e treinamos outro modelo que classifica documentos para o usuário. Tudo ficaria bem, mas você não pode simplesmente pegar e calcular todos os sinais de todos os documentos em tempo real, se houver milhões desses documentos, e as recomendações precisam ser construídas em 100-200 ms. A tarefa é selecionar um determinado subconjunto entre milhões, que será classificado para o usuário. Esta etapa geralmente é chamada de seleção de candidatos. Existem vários requisitos para isso. Primeiramente, a seleção deve acontecer muito rapidamente, para que reste o máximo de tempo possível para a classificação propriamente dita. Em segundo lugar, tendo reduzido bastante o número de documentos para classificação, devemos preservar os documentos relevantes para o utilizador tão completamente quanto possível.

Nosso princípio de seleção de candidatos evoluiu e, no momento, chegamos a um esquema de vários estágios:

Primeiro, todos os documentos são divididos em grupos e os documentos mais populares são retirados de cada grupo. Os grupos podem ser sites, tópicos, clusters. Para cada usuário, com base em seu histórico, são selecionados os grupos mais próximos dele e deles são retirados os melhores documentos. Também utilizamos o índice kNN para selecionar os documentos mais próximos do usuário em tempo real. Existem vários métodos para construir um índice kNN; o nosso funcionou melhor HNSW (Gráficos Hierárquicos Navegáveis ​​de Pequenos Mundos). Este é um modelo hierárquico que permite encontrar os N vetores mais próximos de um usuário em um banco de dados de milhões em alguns milissegundos. Primeiro indexamos todo o nosso banco de dados de documentos offline. Como a busca no índice funciona de forma bastante rápida, se houver vários embeddings fortes, você pode criar vários índices (um índice para cada embedding) e acessar cada um deles em tempo real.

Ainda temos dezenas de milhares de documentos para cada usuário. Ainda é muito para contar todos os recursos, então nesta fase usamos a classificação leve - um modelo de classificação leve e pesado com menos recursos. A tarefa é prever quais documentos um modelo pesado terá no topo. Os documentos com maior preditor serão utilizados no modelo pesado, ou seja, na última etapa do ranking. Essa abordagem permite reduzir o banco de dados de documentos considerados pelo usuário de milhões para milhares em dezenas de milissegundos.

Etapa ALS em tempo de execução

Como levar em consideração o feedback do usuário imediatamente após um clique?

Um fator importante nas recomendações é o tempo de resposta ao feedback do usuário. Isso é especialmente importante para novos usuários: quando uma pessoa apenas começa a usar o sistema de recomendação, ela recebe um feed não personalizado de documentos de diversos temas. Assim que ele der o primeiro clique, você precisa levar isso imediatamente em consideração e se adaptar aos interesses dele. Se você calcular todos os fatores off-line, uma resposta rápida do sistema se tornará impossível devido ao atraso. Portanto é necessário processar as ações do usuário em tempo real. Para isso, usamos a etapa ALS em tempo de execução para construir uma representação vetorial do usuário.

Vamos supor que temos uma representação vetorial para todos os documentos. Por exemplo, podemos construir embeddings offline com base no texto de um artigo usando ELMo, BERT ou outros modelos de aprendizado de máquina. Como podemos obter uma representação vetorial de usuários no mesmo espaço com base em suas interações no sistema?

Princípio geral de formação e decomposição da matriz usuário-documentoVamos ter m usuários en documentos. Para alguns usuários, sua relação com determinados documentos é conhecida. Então essas informações podem ser representadas como uma matriz mxn: as linhas correspondem aos usuários e as colunas correspondem aos documentos. Como a pessoa não viu a maior parte dos documentos, a maior parte das células da matriz permanecerá vazia, enquanto outras serão preenchidas. Para cada evento (gostei, não gostei, clique) algum valor é fornecido na matriz - mas vamos considerar um modelo simplificado em que gostar corresponde a 1 e não gostar corresponde a -1.

Vamos decompor a matriz em duas: P (mxd) e Q (dxn), onde d é a dimensão da representação vetorial (geralmente um número pequeno). Então cada objeto corresponderá a um vetor d-dimensional (para um usuário - uma linha na matriz P, para um documento - uma coluna na matriz Q). Esses vetores serão os embeddings dos objetos correspondentes. Para prever se um usuário gostará de um documento, você pode simplesmente multiplicar suas incorporações.

Uma das formas possíveis de decompor uma matriz é ALS (Alternating Least Squares). Otimizaremos a seguinte função de perda:

Aqui rui é a interação do usuário u com o documento i, qi é o vetor do documento i, pu é o vetor do usuário u.

Em seguida, o vetor de usuário ideal do ponto de vista do erro quadrático médio (para vetores de documentos fixos) é encontrado analiticamente resolvendo a regressão linear correspondente.

Isso é chamado de "etapa ALS". E o próprio algoritmo ALS é que fixamos alternadamente uma das matrizes (usuários e artigos) e atualizamos a outra, encontrando a solução ideal.

Felizmente, encontrar a representação vetorial do usuário é uma operação bastante rápida que pode ser feita em tempo de execução usando instruções vetoriais. Esse truque permite que você leve em consideração imediatamente o feedback do usuário na classificação. A mesma incorporação pode ser usada no índice kNN para melhorar a seleção de candidatos.

Filtragem Colaborativa Distribuída

Como fazer a fatoração incremental de matrizes distribuídas e encontrar rapidamente representações vetoriais de novos artigos?

O conteúdo não é a única fonte de sinais de recomendação. Outra fonte importante é a informação colaborativa. Tradicionalmente, bons recursos de classificação podem ser obtidos a partir da decomposição da matriz usuário-documento. Mas ao tentar fazer tal decomposição, encontramos problemas:

1. Temos milhões de documentos e dezenas de milhões de usuários. A matriz não cabe inteiramente em uma máquina e a decomposição levará muito tempo.
2. A maior parte do conteúdo do sistema tem vida útil curta: os documentos permanecem relevantes por apenas algumas horas. Portanto, é necessário construir sua representação vetorial o mais rápido possível.
3. Se você construir uma decomposição imediatamente após a publicação do documento, um número suficiente de usuários não terá tempo para avaliá-la. Portanto, sua representação vetorial provavelmente não será muito boa.
4. Se um usuário gostar ou não, não poderemos levar isso em consideração imediatamente na decomposição.

Para resolver esses problemas, implementamos uma decomposição distribuída da matriz usuário-documento com atualizações incrementais frequentes. Como exatamente isso funciona?

Suponha que temos um cluster de N máquinas (N está na casa das centenas) e queremos fazer uma decomposição distribuída de uma matriz nelas que não cabe em uma máquina. A questão é como realizar esta decomposição para que, por um lado, haja dados suficientes sobre cada máquina e, por outro, para que os cálculos sejam independentes?

Usaremos o algoritmo de decomposição ALS descrito acima. Vejamos como executar uma etapa do ALS de maneira distribuída - o restante das etapas será semelhante. Digamos que temos uma matriz fixa de documentos e queremos construir uma matriz de usuários. Para fazer isso, vamos dividi-lo em N partes por linhas, cada parte conterá aproximadamente o mesmo número de linhas. Enviaremos para cada máquina células não vazias das linhas correspondentes, bem como a matriz de incorporações de documentos (inteiramente). Como seu tamanho não é muito grande e a matriz de documentos do usuário geralmente é muito esparsa, esses dados cabem em uma máquina normal.

Este truque pode ser repetido ao longo de várias épocas até que o modelo convirja, alternando a matriz fixa uma por uma. Mas mesmo assim, a decomposição da matriz pode levar várias horas. E isso não resolve o problema de que você precisa receber rapidamente os embeddings de novos documentos e atualizar os embeddings daqueles sobre os quais havia pouca informação na construção do modelo.

A introdução de atualizações incrementais rápidas do modelo nos ajudou. Digamos que temos um modelo atualmente treinado. Desde o seu treinamento, surgiram novos artigos com os quais nossos usuários interagiram, bem como artigos que tiveram pouca interação durante o treinamento. Para obter rapidamente os embeddings de tais artigos, usamos os embeddings do usuário obtidos durante o primeiro grande treinamento do modelo e executamos uma etapa ALS para calcular a matriz do documento dada uma matriz fixa do usuário. Isso permite que você receba incorporações rapidamente - alguns minutos após a publicação do documento - e atualize frequentemente as incorporações de documentos recentes.

Para fazer recomendações que levem imediatamente em consideração as ações humanas, em tempo de execução não usamos embeddings de usuários obtidos offline. Em vez disso, executamos uma etapa ALS e obtemos o vetor do usuário real.

Transferir para outra área de domínio

Como usar o feedback do usuário em artigos de texto para construir uma representação vetorial de um vídeo?

Inicialmente recomendamos apenas artigos de texto, por isso muitos de nossos algoritmos são adaptados para esse tipo de conteúdo. Mas ao adicionar outros tipos de conteúdo, nos deparamos com a necessidade de adaptar os modelos. Como resolvemos esse problema usando um exemplo de vídeo? Uma opção é treinar novamente todos os modelos do zero. Mas isso leva muito tempo e alguns algoritmos são exigentes com o tamanho da amostra de treinamento, que ainda não está disponível na quantidade necessária para um novo tipo de conteúdo nos primeiros momentos de sua vida no serviço.

Fomos por outro caminho e reutilizamos os modelos de texto para o vídeo. O mesmo truque de ALS nos ajudou a criar representações vetoriais de vídeos. Pegamos uma representação vetorial de usuários com base em artigos de texto e executamos uma etapa de ALS usando informações de visualização de vídeo. Assim obtivemos facilmente uma representação vetorial do vídeo. E em tempo de execução simplesmente calculamos a proximidade entre o vetor do usuário obtido dos artigos de texto e o vetor de vídeo.

Conclusão

O desenvolvimento do núcleo de um sistema de recomendação em tempo real envolve muitos desafios. Você precisa processar dados rapidamente e aplicar métodos de ML para usar esses dados de maneira eficaz; construir sistemas distribuídos complexos capazes de processar sinais de usuários e novas unidades de conteúdo em um tempo mínimo; e muitas outras tarefas.

No sistema atual, cujo desenho descrevi, a qualidade das recomendações ao usuário cresce junto com sua atividade e tempo de permanência no serviço. Mas é claro que aqui reside a principal dificuldade: é difícil para o sistema entender imediatamente os interesses de uma pessoa que tem pouca interação com o conteúdo. Melhorar as recomendações para novos usuários é nosso principal objetivo. Continuaremos otimizando os algoritmos para que o conteúdo relevante para uma pessoa chegue ao seu feed com mais rapidez e o conteúdo irrelevante não seja exibido.

Fonte: habr.com