Em 2018, nossa equipe tradicionalmente participava do RecSys Challenge . Este é um concurso anual sobre sistemas de recomendação, realizado como parte da conferência RecSys. Não é tão grande quanto as competições do Kaggle, mas é considerada uma das competições de maior prestígio em sistemas de recomendação. Dessa vez, a tarefa era musical - era necessário criar um sistema para continuar automaticamente as listas de reprodução. Neste post, falo em detalhes sobre nossa decisão. Convido você a gato.

Sobre o concurso

Este ano, os dados da competição foram fornecidos pelo Spotify , um serviço de streaming de música (que, infelizmente, não está disponível oficialmente na Federação Russa). As recomendações são uma das partes mais importantes do produto no Spotify e permitem que os usuários encontrem novas músicas, criem listas de reprodução ou ouçam rádio com base em suas preferências.

Os participantes do concurso precisavam criar um algoritmo de continuação automática da lista de reprodução. O conjunto de dados Million Playlist, cujo nome fala por si, foi apresentado como dados de treinamento. Além de informações sobre quais faixas estão contidas na lista de reprodução, também foram fornecidas meta-informações sobre as faixas: artista, título, duração, nome do álbum.

Você pode ler mais sobre o concurso aqui .

Desafio da competição

A tarefa da competição é clássica para sistemas de recomendação: gere recomendações de primeira ordem para o usuário, conhecendo o histórico de suas ações, mas, em vez do item de usuário usual, a faixa da playlist aparece aqui. Em termos mais formais, partes das listas de reprodução (doravante denominadas semente) foram fornecidas nos dados de teste e havia várias maneiras diferentes de se formar. Para K = (5, 10, 25, 100), houve sementes com as primeiras K trilhas e K trilhas escolhidas aleatoriamente. Havia também sementes com a primeira faixa e apenas com o nome da lista de reprodução. Faixas que não foram incluídas nos holdouts precisavam ser previstas. Para cada lista de reprodução, eram necessárias exatamente 500 previsões.

Métricas

Uma das características da competição era que a métrica não era uma, como é habitual na maioria das competições, mas várias. Abaixo vou contar sobre cada um deles.

Precisão R

Essa métrica mostra que proporção de faixas relevantes adivinhamos.

$$$R-precision = \ frac {| G \ cap {} R_ {1: | G |} |} {| G |}$

NDCG

Essa é uma métrica clássica de qualidade de classificação. Você pode ler sobre ela, por exemplo, aqui

Cliques

O Spotify possui um mecanismo para continuar a lista de reprodução (você pode vê-la na captura de tela no início do artigo): oferece várias faixas que podem ser usadas para expandir a lista de reprodução e, se nenhuma aparecer, você pode clicar no botão Atualizar e obter o próximo lote de recomendações. O número dessas atualizações para a primeira opção é a métrica Cliques. Mais simplesmente, a posição da primeira recomendação relevante (neste caso, dividida por 10).

Em seguida, as equipes recebem uma classificação para cada uma das métricas. Em seguida, as fileiras são agregadas de acordo com o esquema da estratégia eleitoral do Borda Count. Se $$$p$É o número de participantes, então uma equipe com uma classificação de 1 recebe $$$p-1$pontos, uma equipe com classificação 2 recebe $$$p-2$pontos e assim por diante.

Solução

Esquema de validação

Para reproduzir divisões de trem / teste, dividimos o conjunto de dados original em três partes: a primeira parte continha 980k listas de reprodução, a segunda e terceira partes continham 10k cada. Em seguida, cada lista de reprodução da segunda e terceira partes foi dividida em partes de semente e de reserva, e os tamanhos das partes de semente foram selecionados da mesma maneira que no conjunto de teste fornecido, e as faixas restantes caíram em reserva.

Seleção de candidatos

Os sistemas recomendados geralmente usam uma abordagem de dois estágios: primeiro, usando um modelo mais simples (por exemplo, fatoração de matriz ), os candidatos são selecionados de todo o conjunto de itens e, em seguida, os candidatos são classificados por um modelo mais complexo (por exemplo, aumento de gradiente ) em um conjunto mais amplo de atributos. A seleção de candidatos é necessária, antes de tudo, devido aos recursos de computação limitados: se usarmos todo o conjunto de faixas disponíveis como candidatos, então para uma lista de reprodução, teremos que conduzir cerca de um milhão de objetos através do modelo.

Seleção de candidatos usando fatoração matricial

A fatoração matricial é uma das abordagens mais comuns para a construção de sistemas de recomendação. A idéia principal desse método é apresentar uma matriz esparsa de interações entre usuários e itens na forma de um produto de duas matrizes (U e I) de menor dimensão. Em seguida, podemos obter recomendações para o usuário multiplicando o vetor da matriz U pela matriz I.

Para a fatoração da matriz, usamos a biblioteca LightFM com perda WARP (Weighted Approximate-Rank Pairwise) . Também tínhamos dois modelos diferentes - um para listas de reprodução que possuem uma semente não vazia e outro para listas de reprodução que possuem apenas um nome (partida a frio).

Perda de WARP

Essa função de perda é melhor que outras na tarefa de classificação. Funciona com triplos (usuário, item positivo, item negativo) e possui uma característica muito importante - a seleção de exemplos negativos não acontece por acaso, mas de maneira que os exemplos negativos selecionados "quebrem" a classificação atual do modelo, ou seja, foram superiores a um exemplo positivo.

Portanto, o procedimento para treinar um modelo usando a perda WARP será aproximadamente o seguinte:

1. Para um casal $$$(usuário, positivo \ _item)$escolheremos um exemplo negativo aleatório entre todos os outros itens (é importante entender que isso só é necessário se a probabilidade de escolher um exemplo negativo, que na verdade será positivo, for muito pequena). Calcular a previsão de pares $$$(usuário, positivo \ _item)$e $$$(usuário, negativo \ _item)$e se não houve distúrbio (ou seja, o modelo previu uma pontuação mais alta para um exemplo positivo), continuamos a amostrar exemplos negativos até que a violação ocorra.
2. Se recebemos uma violação na primeira tentativa, podemos dar um grande passo gradiente, pois isso significa que, no momento, o modelo geralmente coloca exemplos negativos acima dos positivos e precisamos atualizar fortemente seus pesos. Se tivéssemos que procurar um exemplo negativo adequado por um longo tempo, daríamos um pequeno passo - o modelo já está bem treinado.

Uma descrição mais formal da perda de WARP pode ser encontrada no artigo original ou nesta postagem .

Lightfm

A primeira versão do modelo usou apenas informações colaborativas: a presença da faixa track_id na playlist playlist_id, apresentada como uma matriz esparsa binária. Um número de matrizes correspondia a uma lista de reprodução, uma coluna a uma faixa.

$$$pontuação (p, t) = b_t + b_t + <q_p, q_t>$

Recursos de texto LightFM +

Este modelo usa incorporação de palavras do nome da lista de reprodução em vez de playlist_id. Uma incorporação de uma lista de reprodução é a soma dos incorporamentos de suas palavras.

$$$pontuação (p, t) = b_p + b_t + <q_p, q_t>$
$$$b_p = \ sum_ {i \ in {f_p}} {b_i}$, $$$q_p = \ sum_ {i \ in {f_p}} {q_i}$,
onde $$$f_p$- Estas são as palavras do nome da lista de reprodução.

Assim, resolvemos o problema de uma partida a frio - podemos fornecer melhores recomendações para listas de reprodução que têm apenas um nome.

Os organizadores do concurso também forneceram informações sobre quantas faixas estavam na parte oculta da lista de reprodução. Se a parte oculta foi $$$k$faixas, em seguida, escolhemos $$$max (k * 15, k + 700)$candidatos. A natureza desses números é uma heurística simples, inventada a partir das seguintes considerações: queremos ter candidatos suficientes para pequenas listas de reprodução (portanto, $$$k + 700$) e também queremos que o conjunto de dados final tenha aproximadamente 10 milhões de linhas por motivos de desempenho em termos de tempo e memória (portanto, k 15, e não k 50, por exemplo).

Ranking

Depois de selecionar os candidatos, podemos considerar a tarefa de construir recomendações como um problema de classificação binária: para cada uma das faixas nos candidatos selecionados, aprendemos a prever se essa faixa realmente estava na lista de reprodução.

Em nosso conjunto de dados de treinamento, cada linha conterá sinais para o par (lista de reprodução, faixa), e o rótulo será 1 se houver uma faixa na lista de reprodução e 0 se não.

Como sinais, vários grupos diferentes foram utilizados.

Recursos baseados no modelo LightFM

Como descrito acima, no modelo LightFM temos vetores $$$q_p, q_t$e escalares $$$b_p, b_t$.
Como sinais, usaremos $$$b_p, b_t$, < $$$q_p, q_t>$e a classificação da faixa t entre todos os candidatos à lista de reprodução p (a classificação foi calculada pela fórmula ). Esses quatro atributos foram obtidos dos modelos LightFM e LightFM Text.

Sinais baseados na co-ocorrência de faixas

Vamos $$$n_ {i, j}$É o número de listas de reprodução que contêm faixas $$$i$e $$$j$juntos também $$$n_i$- número de listas de reprodução que contêm a faixa $$$i$. Esses valores foram calculados em um conjunto fixo de listas de reprodução que consistem em todas as partes de sementes.

Deixe a lista de reprodução $$$p$consiste em faixas $$$t_1, t_2, ..., t_n$. Para a pista $$$t$calcular os valores $$$n_ {t, t_1}, n_ {t, t_2}, ..., n_ {t, t_n}$e para eles calcularemos várias estatísticas: mínima, máxima, média e mediana. Depois calculamos as mesmas estatísticas para as quantidades $$$\ frac {n_ {t, t_1}} {n_ {t_1}}, \ frac {n_ {t, t_2}} {n_ {t_2}}, ..., \ frac {n_ {t, t_n}} { n_ {t_n}}$. No primeiro caso, apenas observamos com que frequência a faixa de destino se encontrou com as faixas da lista de reprodução e, no segundo caso, também normalizamos isso com a frequência de ocorrência de outras faixas. A normalização ajuda o modelo a não treinar novamente as faixas populares e extrair com mais precisão informações sobre o quanto as faixas são realmente semelhantes.

Outros sinais

Todas as características são calculadas para o par. $$$(p, t)$.

• O número de artistas únicos na lista de reprodução $$$p$.
• Número de álbuns únicos na lista de reprodução $$$p$.
• Número e porcentagem de faixas em uma lista de reprodução $$$p$com o mesmo álbum / artista que a faixa $$$t$.
• Quantas vezes a pista se encontrou $$$t$em todas as listas de reprodução.
• Quantas vezes o artista / álbum acompanhou $$$t$em todas as listas de reprodução.
• O número de faixas nas partes inicial e de espera da playlist $$$p$.

Modelo de Recomendação

Para criar as recomendações finais, usamos o XGBoost . O modelo foi treinado em $$$II_ {candidatos}$, os hiperparâmetros foram selecionados em $$$III_ {candidatos}$pela métrica ROC AUC . Essa métrica foi escolhida porque é clássica para problemas de classificação. Nem todos os recursos são igualmente úteis, portanto, será interessante observar os valores de importância dos recursos do modelo.

Observa-se que o sinal de média normalizada de coocorrência se destaca significativamente dos demais. Isso significa que as informações sobre a co-ocorrência de faixas emitem um sinal muito forte, o que, em geral, não é surpreendente. Além disso, esse recurso pode ser usado como uma seleção de candidato em vez do modelo LightFM, e isso não deu resultados piores.

Outros

Ferro

Todos os modelos foram treinados no servidor com Intel Xeon E5-2679 v3 (28 núcleos, 56 threads), 256 GB de RAM. O treinamento final do pipeline levou cerca de 100 horas e consumiu 200 Gb de memória no auge, com uma parte significativa (cerca de 90%) do tempo gasto no treinamento do modelo de seleção de candidatos. O modelo de classificação foi treinado rapidamente - cerca de duas horas (sem contar a seleção dos hiperparâmetros).

Falha

Não sem falhas.

No penúltimo dia da competição, decidimos organizar uma mini-hackathon, no final, coletamos tudo o que tínhamos: seleção de candidatos com base na co-ocorrência, um monte de novos recursos para impulsionar, e parece que poderia ser assim?
Mas a velocidade de validação realmente aumentou um pouco, então cegamos a submissão e a enviamos, planejando que teríamos um dia para corrigir os batentes. Depois de enviarem o envio, descobriram que não era o penúltimo dia, mas o último. E a velocidade do novo envio foi muito menor do que o nosso melhor envio. Não havia tempo para descobrir por que isso aconteceu, então sabotamos a melhor finalização, que permaneceu em terceiro lugar.

Também no último dia, aprendemos que existem dois tipos diferentes de sementes: com as primeiras faixas K e aleatórias, e na validação sempre escolhemos faixas aleatórias, mas é improvável que isso afete muito a tabela de classificação.
Um dia da competição, o valor da métrica R-Precision para todas as equipes na tabela de classificação aumentou bastante. Não demos importância a isso, mas, no final da competição, descobrimos que os organizadores adicionaram mais um componente à métrica - uma partida do artista da faixa. Isso também pode ser adicionado à métrica de validação e, possivelmente, à velocidade aprimorada.

Código

Nossa solução foi projetada na forma de laptops Jupyter e pode ser reproduzida (!) Iniciando-os sequencialmente. Somente para isso, você precisa de uma máquina com 200Gb + RAM e alguns dias.

Decisões de outros participantes

A equipe que conquistou o primeiro lugar também participa regularmente do RecSys Challenge e ocupa lugares altos. A solução deles é semelhante à nossa, mas implementada em Java .

Os segundos finalistas têm uma abordagem bastante interessante - eles usaram o Denoising Autoencoder para restaurar playlists de suas partes .

Conclusão

Se você olhar para a tabela de classificação final, nossa equipe ocupa a sexta e a quarta posição no ranking de métricas (R-Precision e NDCG) e, primeiro, na métrica de cliques. Como isso aconteceu? E isso aconteceu por causa de uma boa solução para o problema de partida a frio usando o modelo de texto LightFM. A métrica de cliques é mais severa quando não achamos uma única faixa em uma lista de reprodução. O uso do modelo de texto LightFM melhorou a métrica média de cliques de 2,2 para 1,78.

A abordagem com a seleção de candidatos usando um modelo mais simples e uma classificação mais aprofundada com um modelo mais complexo ainda é um dos mais bem-sucedidos nos problemas clássicos da construção de recomendações top-K. Mas, ao mesmo tempo, é muito importante construir corretamente o esquema de validação para que os modelos de seleção de candidatos e de classificação possam ser comparados.

Além disso, esse esquema é bastante adequado para sistemas de produção - você pode começar a construir seu sistema de recomendação com base na fatoração da matriz e, em seguida, aprimorá-lo adicionando um segundo estágio.

Se você tiver alguma dúvida sobre o artigo, não hesite em perguntar nos comentários :)

PS Nós escrevemos um artigo mais detalhado sobre isso para o workshop na conferência RecSys. O acesso aos materiais dela no site é limitado; portanto, se você estiver interessado em aprender um pouco mais sobre a nossa solução, escreva-me no PM.