💝 👩🏾‍🎓 🗑️ Anatomia de sistemas de recomendação. Parte um 👏🏼 🦊 ▫️

Eu trabalho como cientista de dados na CleverDATA . Estamos envolvidos em projetos de aprendizado de máquina, e uma das solicitações mais frequentes para o desenvolvimento de soluções de marketing baseadas em aprendizado de máquina é o desenvolvimento de modelos de recomendação.

Neste artigo, falarei sobre sistemas de recomendação, tentarei fornecer uma visão geral mais completa das abordagens existentes e explicarei nos dedos como os algoritmos funcionam. Parte do material é baseado em um bom curso nos sistemas de recomendação do laboratório MovieLens (com o qual a maioria das pessoas está familiarizada com o mesmo conjunto de dados para recomendações de teste), o restante é da experiência pessoal. O artigo consiste em duas partes. O primeiro descreve a declaração do problema e fornece uma visão geral dos algoritmos de recomendação simples (mas populares). No segundo artigo, falarei sobre métodos mais avançados e alguns aspectos práticos da implementação.

Fonte

Revisão e declaração do problema

A tarefa do sistema de recomendação é informar o usuário sobre um produto no qual ele possa estar mais interessado em um determinado momento. O cliente recebe informações e o serviço ganha dinheiro com a prestação de serviços de qualidade. Os serviços não são necessariamente vendas diretas dos produtos oferecidos. O serviço também pode ganhar comissões ou simplesmente aumentar a lealdade do usuário, o que se traduz em publicidade e outras receitas.

Dependendo do modelo de negócios, as recomendações podem ser sua base, como, por exemplo, no TripAdvisor, ou podem ser apenas um serviço adicional conveniente (como, por exemplo, em algumas lojas de roupas on-line), projetado para melhorar a Experiência do Cliente e tornar a navegação no catálogo mais confortável.

A personalização do marketing online é uma tendência óbvia da última década. Segundo a McKinsey , 35% da receita da Amazon ou 75% da receita da Netflix são provenientes de produtos recomendados, e esse percentual provavelmente crescerá. Os sistemas de referência são sobre o que oferecer ao cliente para fazê-lo feliz.

Para ilustrar toda a variedade de serviços de recomendação, darei uma lista das principais características com as quais você pode descrever qualquer sistema de recomendação.

Assunto da recomendação - o que é recomendado.

Há muita variedade aqui - podem ser produtos (Amazon, Ozon), artigos (Arxiv.org), notícias (Surfingbird, Yandex.Zen), imagens (500px), vídeos (YouTube, Netflix), pessoas (Linkedin, LonelyPlanet), música (Last.fm, Pandora), listas de reprodução e muito mais. Em geral, você pode recomendar qualquer coisa.
O objetivo da recomendação é o motivo pelo qual é recomendado.

Por exemplo: comprar, informar, treinar, fazer contatos.
O contexto da recomendação é o que o usuário está fazendo no momento.

Por exemplo: assistindo mercadorias, ouvindo música, conversando com pessoas.
A fonte da recomendação é quem recomenda:

- audiência (classificação média dos restaurantes no TripAdvisor),
- Usuários interessados
- comunidade de especialistas (às vezes quando se trata de um produto complexo, como, por exemplo, vinho).
O grau de personalização .

Recomendações não pessoais - quando você é recomendado da mesma forma que todos os outros. Eles permitem a segmentação por região ou horário, mas não levam em consideração suas preferências pessoais.

Uma opção mais avançada é quando as recomendações usam dados da sua sessão atual. Você examinou vários produtos e, na parte inferior da página, oferece produtos similares.

As recomendações pessoais usam todas as informações disponíveis sobre o cliente, incluindo o histórico de suas compras.
Transparência

As pessoas confiam mais na recomendação se entenderem exatamente como ela foi recebida. Portanto, há menos risco de se deparar com sistemas "inescrupulosos" que promovem bens pagos ou colocam produtos mais caros mais altos no ranking. Além disso, um bom sistema de recomendação deve ser capaz de lidar com críticas e truques de vendas comprados.

Manipulações, a propósito, também não são intencionais. Por exemplo, quando um novo sucesso de público é lançado, a primeira coisa que os fãs fazem é, portanto, a classificação pode ser superestimada nos primeiros dois meses.
O formato da recomendação .

Pode ser uma janela pop-up, uma lista classificada que aparece em uma seção específica do site, uma faixa de opções na parte inferior da tela ou qualquer outra coisa.
Algoritmos

Apesar dos muitos algoritmos existentes, todos eles se resumem a várias abordagens básicas, que serão descritas mais adiante. Os mais clássicos são os algoritmos baseados em resumo (não pessoais), baseados em conteúdo (modelos baseados na descrição do produto), filtragem colaborativa (filtragem colaborativa), fatoração de matriz (métodos baseados na decomposição de matriz) e outros.

Fonte

No centro de qualquer sistema de recomendação está a chamada matriz de preferências. Essa é uma matriz, em um eixo no qual todos os clientes do serviço (Usuários) são separados e, por outro, objetos da recomendação (Itens). Na interseção de alguns pares (usuário, item), essa matriz é preenchida com classificações (classificações) - este é um indicador conhecido do interesse do usuário neste produto, expresso em uma determinada escala (por exemplo, de 1 a 5).

Os usuários geralmente avaliam apenas uma pequena parte dos produtos que estão no catálogo, e a tarefa do sistema de recomendação é resumir essas informações e prever a atitude do cliente em relação a outros produtos sobre os quais nada se sabe. Em outras palavras, você precisa preencher todas as células vazias na imagem acima.

Os padrões de consumo das pessoas são diferentes e novos produtos não precisam ser recomendados. Você pode mostrar posições repetidas, por exemplo, para reabastecer o estoque. De acordo com este princípio, dois grupos de mercadorias são distinguidos.

Repetível . Por exemplo, xampus ou aparelhos de barbear sempre necessários.
Único . Por exemplo, livros ou filmes que raramente são readquiridos.

Se o produto não puder ser atribuído explicitamente a uma das classes, faz sentido determinar a admissibilidade de compras repetidas individualmente (alguém vai à loja apenas para uma pasta de amendoim de uma determinada marca e para alguém é importante tentar tudo o que está no catálogo).

O conceito de "interesse" também é subjetivo. Alguns usuários precisam apenas de itens de sua categoria favorita (recomendações conservadoras), enquanto alguém, pelo contrário, é mais responsivo a produtos ou grupos de produtos não padrão (recomendações arriscadas). Por exemplo, a hospedagem de vídeo pode recomendar ao usuário apenas novos episódios de suas séries favoritas e periodicamente oferecer a ele novos programas ou até novos gêneros. Idealmente, você deve escolher uma estratégia para exibir recomendações para cada cliente separadamente, usando a modelagem de uma categoria de cliente.

As classificações do usuário podem ser obtidas de duas maneiras:

classificações explícitas - o usuário coloca a classificação do produto, deixa um comentário, gosta da página,
classificações implícitas - o usuário não expressa explicitamente sua atitude, mas pode-se tirar uma conclusão indireta de suas ações: ele comprou o produto - isso significa que ele gosta, lê a descrição por um longo tempo - significa que há interesse etc.

Obviamente, as preferências explícitas são melhores - o próprio usuário diz que gostou. No entanto, na prática, nem todos os sites oferecem a oportunidade de expressar explicitamente seu interesse, e nem todos os usuários desejam fazê-lo. Ambos os tipos de classificações são mais frequentemente usados de uma só vez e se complementam bem.

Também é importante distinguir entre os termos Previsão (previsão do grau de interesse) e a própria Recomendação (mostrando a recomendação). O que e como mostrar é uma tarefa separada que usa as estimativas obtidas na etapa de Previsão, mas pode ser implementada de maneiras diferentes.

Às vezes, o termo “recomendação” é usado em um sentido mais amplo e refere-se a qualquer otimização, seja uma seleção de clientes para correspondência de publicidade, determinando o preço ideal da oferta ou simplesmente escolhendo a melhor estratégia de comunicação com o cliente. No artigo, limito-me à definição clássica desse termo, denotando a escolha do produto mais interessante para o cliente.

Recomendações não personalizadas

Vamos começar com recomendações não personalizadas, pois são as mais fáceis de implementar. Neles, o interesse potencial do usuário é simplesmente determinado pela classificação média do produto: "Todo mundo gosta, então você vai gostar". A maioria dos serviços trabalha com esse princípio quando o usuário não está conectado ao sistema, por exemplo, o mesmo TripAdvisor.

As recomendações podem ser mostradas de diferentes maneiras - como um banner ao lado da descrição do produto (Amazon), como resultado de uma solicitação classificada por um parâmetro específico (TripAdvisor) ou de alguma outra forma.

As classificações do produto também podem ser exibidas de várias maneiras. Pode haver estrelas próximas ao produto, número de curtidas, diferença entre votos positivos e negativos (como geralmente é feito nos fóruns), proporção de classificações altas ou mesmo um histograma de classificações. Os histogramas são a maneira mais informativa, mas eles têm uma desvantagem - são difíceis de comparar entre si ou de classificar, quando você precisa listar produtos.

Problema de partida a frio

Uma partida a frio é uma situação típica em que ainda não foram acumulados dados suficientes para o sistema recomendador funcionar corretamente (por exemplo, quando um produto é novo ou raramente é comprado). Se a classificação média for calculada pelas estimativas de apenas três usuários (igor92, xyz_111 e oleg_s), essa avaliação claramente não será confiável e os usuários entenderão isso. Frequentemente, nessas situações, as classificações são ajustadas artificialmente.

A primeira maneira é mostrar não o valor médio, mas a média suavizada (média amortecida). O significado é o seguinte: com um pequeno número de classificações, a classificação exibida é mais inclinada a algum tipo de indicador "médio" seguro e, assim que um número suficiente de novas classificações é obtido, o ajuste "médio" deixa de funcionar.

Outra abordagem é calcular intervalos de confiança para cada classificação. Matematicamente, quanto mais estimativas, menor variação da média e, portanto, mais confiança em sua correção. E como uma classificação, você pode exibir, por exemplo, o limite inferior do intervalo (limite baixo do IC). Ao mesmo tempo, fica claro que esse sistema será bastante conservador, com tendência a subestimar as classificações de novos produtos (a menos que, é claro, isso seja um sucesso).

Como as estimativas são limitadas a uma determinada escala (por exemplo, de 0 a 1), a maneira usual de calcular o intervalo de confiança é pouco aplicável aqui: devido às caudas de distribuição que vão ao infinito e à simetria do próprio intervalo. Existe uma maneira alternativa e mais precisa de calculá-lo - Wilson Confidence Interval . Nesse caso, são obtidos intervalos assimétricos aproximadamente desse tipo.

Na figura acima, a classificação horizontal da classificação média é plotada e a vertical é o spread em torno da média. A cor indica diferentes tamanhos de amostra (obviamente, quanto maior a amostra, menor o intervalo de confiança).

O problema do arranque a frio é igualmente relevante para recomendações não personalizadas. A abordagem geral aqui é substituir o que não pode ser contado no momento por várias heurísticas (por exemplo, substituir por uma classificação média, usar um algoritmo mais simples ou não usar um produto até que os dados sejam coletados).

Relevância das recomendações

Em alguns casos, também é importante considerar o "frescor" da recomendação. Isto é especialmente verdade para artigos ou postagens em fóruns. Entradas novas frequentemente devem chegar ao topo. Para fazer isso, use fatores de amortecimento. Abaixo estão algumas fórmulas para calcular a classificação de artigos em sites de mídia.

Exemplo de cálculo de classificação na revista Hacker:

onde U = upvotes, D = downvotes e P (Penalty) - ajuste adicional para a implementação de outras regras de negócios

Cálculo de classificação no Reddit:

onde U = número de votos a favor, D = número de votos contra, T = tempo de gravação. O primeiro termo estima a "qualidade da gravação" e o segundo faz uma correção pelo tempo.

Obviamente, uma fórmula universal não existe e cada serviço inventa a fórmula que melhor resolve seu problema - é verificada empiricamente.

Recomendações baseadas em conteúdo

As recomendações pessoais sugerem o uso máximo de informações sobre o próprio usuário, principalmente sobre suas compras anteriores. Uma das primeiras foi a abordagem de filtragem baseada em conteúdo. Na estrutura dessa abordagem, a descrição do produto (conteúdo) é comparada com os interesses do usuário obtidos de suas classificações anteriores. Quanto mais o produto atende a esses interesses, maior o interesse potencial do usuário é avaliado. O requisito óbvio aqui é que todos os produtos no catálogo tenham uma descrição.

Historicamente, o assunto das recomendações baseadas em conteúdo costuma ser uma descrição não estruturada: filmes, livros, artigos. Tais sinais podem ser, por exemplo, descrições de texto, críticas, elenco e muito mais. No entanto, nada impede o uso de sinais numéricos ou categóricos comuns.

Recursos não estruturados são descritos de maneira típica para os vetores de texto no espaço das palavras ( modelo de espaço vetorial ). Cada elemento desse vetor é um recurso que potencialmente caracteriza o interesse do usuário. Da mesma forma, um produto é um vetor no mesmo espaço.

À medida que o usuário interage com o sistema (digamos, ele compra filmes), as descrições vetoriais dos bens comprados por ele são combinadas (resumidas e normalizadas) em um único vetor e, assim, um vetor de seus interesses é formado. Além disso, basta encontrar um produto cuja descrição seja mais próxima do vetor de interesses, ou seja, resolver o problema de encontrar n vizinhos mais próximos.

Nem todos os elementos são igualmente significativos: por exemplo, palavras aliadas, obviamente, não carregam carga útil. Portanto, ao determinar o número de elementos correspondentes em dois vetores, todas as medidas devem primeiro ser pesadas por sua significância. Essa tarefa é resolvida pela transformação TF-IDF , bem conhecida em Text Mining , que atribui mais peso a interesses mais raros. A coincidência de tais interesses é mais importante na determinação da proximidade de dois vetores do que a coincidência dos populares.

O princípio TF-IDF aqui é igualmente aplicável a atributos nominais comuns, como, por exemplo, gênero, diretor, idioma. TF - uma medida da importância do atributo para o usuário, IDF - uma medida da "raridade" do atributo.

Existe toda uma família de transformações semelhantes (por exemplo, BM25 e similares), mas, em substância, todas repetem a mesma lógica que o TF-IDF: atributos raros devem ter mais peso ao comparar produtos. A imagem abaixo ilustra como o peso do TF-IDF depende do TF e do IDF. O eixo horizontal mais próximo é DF: frequência de atributo entre todos os produtos, o eixo horizontal distante é TF: logaritmo de frequência de atributo do usuário.

Alguns pontos que podem ser levados em consideração durante a implementação.

Ao formar uma apresentação de mercadorias no espaço vetorial, em vez de palavras individuais, você pode usar telhas ou n gramas (pares consecutivos de palavras, triplos etc.). Isso tornará o modelo mais detalhado, mas serão necessários mais dados para o treinamento.
Em locais diferentes da descrição do produto, o peso das palavras-chave pode ser diferente (por exemplo, uma descrição de filme pode consistir em um título, uma breve descrição e uma descrição detalhada).
As descrições de produtos de diferentes usuários podem ter pesos diferentes. Por exemplo, podemos dar mais peso aos usuários ativos que possuem muitas classificações.
Da mesma forma, você pode pesar e produzir. Quanto maior a classificação média de um objeto, maior o seu peso (semelhante ao PageRank ).
Se a descrição do produto permitir links para fontes externas, você poderá ficar confuso e analisar também todas as informações de terceiros relacionadas ao produto.

Pode-se ver que a filtragem baseada em conteúdo repete quase completamente o mecanismo de correspondência de documentos de consulta usado em mecanismos de pesquisa como Yandex e Google. A única diferença está na forma de uma consulta de pesquisa - aqui está um vetor que descreve os interesses do usuário e há as palavras-chave do documento solicitado. Quando os mecanismos de pesquisa começaram a adicionar personalização, a distinção foi apagada ainda mais.

Como medida da proximidade de dois vetores, a distância do cosseno é mais frequentemente usada.

Quando uma nova avaliação é adicionada, o vetor de interesses é atualizado de forma incremental (apenas para os elementos que foram alterados). Ao recontar, faz sentido atribuir novas estimativas um pouco mais de peso, pois as preferências podem variar.

Filtragem colaborativa (opção baseada no usuário)

Essa classe de sistemas começou a se desenvolver ativamente nos anos 90. Como parte da abordagem, as recomendações são geradas com base nos interesses de outros usuários semelhantes. Tais recomendações são o resultado de uma "colaboração" de muitos usuários. Daí o nome do método.

A implementação clássica do algoritmo é baseada no princípio de k vizinhos mais próximos. Nos dedos - para cada usuário, procuramos k mais parecido com ele (em termos de preferências) e complementamos as informações sobre o usuário com dados conhecidos de seus vizinhos. Por exemplo, se você sabe que seus vizinhos estão muito satisfeitos com o filme "Sangue e Concreto" e não o assistiu por algum motivo, esta é uma excelente ocasião para oferecer a você este filme para exibição no sábado.

A figura acima ilustra o princípio do método. Na matriz de preferências, o usuário é destacado em amarelo para o qual queremos determinar as classificações para novos produtos (pontos de interrogação). Três de seus vizinhos mais próximos são destacados em azul.

“Semelhança” é, neste caso, sinônimo de “correlação” de interesses e pode ser considerado de várias maneiras (além da correlação de Pearson, há também uma distância cosseno, há uma distância de Jacquard, distância de Hamming, etc.).

A implementação clássica do algoritmo tem um óbvio menos - é pouco aplicável na prática devido à complexidade quadrática.De fato, como qualquer método do vizinho mais próximo, requer o cálculo de todas as distâncias entre pares entre usuários (e pode haver milhões de usuários). É fácil calcular que a complexidade do cálculo da matriz de distância será

O (n^{2} m)

$O(n^2m)$ onde n é o número de usuários e m é o número de produtos. Com um milhão de usuários, é necessário um mínimo de 4 TB para armazenar a matriz de distância bruta.

Esse problema pode ser parcialmente resolvido com a compra de ferro de alto desempenho. Mas se você se aproximar com sabedoria, é melhor introduzir correções no algoritmo:

atualize as distâncias não em todas as compras, mas em lotes (por exemplo, uma vez por dia),
Não recalcule completamente a matriz de distância, mas atualize-a gradualmente,
optar por algoritmos iterativos e aproximados (por exemplo, ALS).

Para que o algoritmo seja eficaz, é importante que algumas suposições sejam cumpridas.

O gosto das pessoas não muda com o tempo (ou muda, mas para todos da mesma forma).
Se os gostos das pessoas coincidem, eles coincidem em tudo.

Por exemplo, se dois clientes preferem os mesmos filmes, eles também gostam dos mesmos livros. Isso geralmente acontece quando os produtos recomendados são homogêneos (por exemplo, apenas filmes). Se não for assim, alguns clientes podem ter as mesmas preferências alimentares, e as opiniões políticas são diretamente opostas - aqui o algoritmo será menos eficaz.

A vizinhança do usuário no espaço de preferências (seus vizinhos), que analisaremos para gerar novas recomendações, pode ser escolhida de diferentes maneiras. Podemos trabalhar com todos os usuários do sistema em geral, podemos definir um certo limite de proximidade, podemos selecionar vários vizinhos aleatoriamente ou pegar os n vizinhos mais semelhantes (essa é a abordagem mais popular).

Os autores do MovieLens como número ideal de vizinhos fornecem números de 30 a 50 vizinhos para filmes e 25 a 100 para recomendações arbitrárias. É claro aqui que, se levarmos muitos vizinhos, teremos mais chances de ruídos aleatórios e vice-versa, se tomarmos muito pouco, obteremos recomendações mais precisas, mas menos produtos podem ser recomendados.

Uma etapa importante na preparação dos dados é a normalização das estimativas.

Padronização de dados (dimensionamento)

Como todos os usuários avaliam de forma diferente - alguém coloca cinco em uma linha e você raramente espera quatro de alguém - é melhor normalizar os dados antes de calcular, ou seja, levar a uma escala única para que o algoritmo possa compará-los corretamente entre si.

Naturalmente, a estimativa prevista precisará ser convertida na escala original pela transformação inversa (e, se necessário, arredondar para o número inteiro mais próximo).

Existem várias maneiras de normalizar:

centralização (centralização média) - das classificações do usuário, subtraímos a classificação média

* relevante apenas para matrizes não binárias
padronização (z-score) - além da centralização, dividimos sua classificação pelo desvio padrão do usuário,

* aqui, após a conversão reversa, a classificação pode ir além da escala (ou seja, por exemplo, 6 em uma escala de cinco pontos), mas tais situações são bastante raras e eles são resolvidos simplesmente arredondando para a estimativa aceitável mais próxima.
padronização dupla - na primeira vez em que normalizamos as classificações dos usuários, na segunda vez - nas classificações do produto.

Se o filme "O Melhor Filme" tem uma classificação média de 2,5 e o usuário atribui 5, então esse é um fator forte que indica que esses filmes são claramente do seu gosto.

A “similaridade” ou correlação das preferências de dois usuários pode ser considerada de maneiras diferentes. De fato, precisamos apenas comparar dois vetores. Listamos alguns dos mais populares.

— , .

— , .

50 / min(50, Rating intersection) damping factor, .
— , .. , . .
. , — , .

— , (.. ), . , .

Um desenvolvimento interessante da abordagem colaborativa são as chamadas recomendações baseadas em confiança, que levam em conta não apenas a proximidade das pessoas de acordo com seus interesses, mas também a proximidade "social" e o grau de confiança entre elas. Se, por exemplo, vemos que no Facebook uma garota visita periodicamente uma página com gravações em áudio de sua amiga, confia em seu gosto musical. Portanto, as recomendações para a garota podem misturar completamente novas músicas da lista de reprodução do amigo.

Justificação das recomendações

É importante que o usuário confie no sistema de recomendação e, para isso, deve ser simples e compreensível. Se necessário, uma explicação compreensível da recomendação deve estar sempre disponível (na explicação da terminologia em inglês).

Como parte da explicação, é bom mostrar a avaliação do produto dos vizinhos, de acordo com qual atributo (por exemplo, ator ou diretor), houve uma coincidência, bem como a confiança do sistema na avaliação (confiança). Para não sobrecarregar a interface, você pode colocar todas essas informações no botão "Mais informações".

Por exemplo:

"Você pode gostar do filme ... porque ele toca lá ... e ..."
"Usuários com gostos musicais semelhantes classificaram o álbum ... 4.5 em 5."

Sumário

Isso terminará a primeira parte do artigo. Examinamos a declaração geral do problema, conversamos sobre recomendações não pessoais, descrevemos duas abordagens clássicas (filtragem baseada em conteúdo e colaborativa) e também abordamos o tópico de recomendações substanciadas. Em geral, essas duas abordagens são suficientes para criar um sistema de recomendação pronto para produção. Na próxima parte, continuarei a revisão e falarei sobre métodos mais modernos, incluindo aqueles que envolvem redes neurais e aprendizado profundo, bem como sobre modelos híbridos.

Enquanto isso, veja nossas vagas.

Anatomia de sistemas de recomendação. Parte um