Anatomia de sistemas de recomendação. Parte dois

Há uma semana, fiz aqui uma visão geral dos algoritmos de recomendação existentes. Neste artigo, continuarei esta revisão: falarei sobre a variante baseada em itens da filtragem colaborativa, sobre métodos baseados em decomposições de matrizes, problemas de teste e também sobre algoritmos menos "sem torção" (mas não menos interessantes).

Filtragem colaborativa (opção baseada em item)

A abordagem baseada em itens é uma alternativa natural à abordagem clássica baseada no usuário descrita na primeira parte e a repete quase completamente, exceto por um ponto - aplica-se à matriz de preferências transposta. I.e. procurando produtos relacionados, não usuários.

Deixe-me lembrá-lo de que a filtragem colaborativa baseada no usuário (CF baseada no usuário) pesquisa para cada cliente um grupo de clientes mais semelhante a ele (em termos de compras anteriores) e calcula a média de suas preferências. Essas preferências médias servem como recomendações para o usuário. No caso da filtragem colaborativa de mercadorias (CF baseada em itens), os vizinhos mais próximos são pesquisados ​​no conjunto de produtos - colunas da matriz de preferências. E a média ocorre precisamente neles.

De fato, se os produtos são substancialmente similares, é mais provável que sejam apreciados ou não ao mesmo tempo. Portanto, quando vemos que dois produtos têm fortes correlações, isso pode indicar que são produtos semelhantes.

Vantagens do item com base no usuário:

• Quando há muitos usuários (quase sempre), a tarefa de encontrar o vizinho mais próximo se torna pouco computável. Por exemplo, para 1 milhão de usuários, você precisa calcular e armazenar $$$\ frac {1} {2} 10 ^ 6 * 10 ^ 6$~ 500 bilhões de distâncias. Se a distância é codificada com 8 bytes, isso resulta em 4 TB apenas para a matriz de distância. Se fizermos com base em itens, a complexidade dos cálculos diminuirá com $$$O (N ^ 2n)$antes $$$O (n ^ 2N)$e a matriz de distância não tem mais uma dimensão (1 milhão por 1 milhão), mas, por exemplo, (100 por 100) pelo número de mercadorias.
  
• A classificação de proximidade é muito mais precisa que a classificação de proximidade. Isso é uma conseqüência direta do fato de que geralmente há muito mais usuários do que bens e, portanto, o erro padrão no cálculo da correlação de bens é muito menor. Só temos mais informações para tirar uma conclusão.
  
• Na versão baseada no usuário, as descrições do usuário geralmente são muito esparsas (existem muitos produtos, poucas classificações). Por um lado, isso ajuda a otimizar o cálculo - multiplicamos apenas os elementos em que há uma interseção. Mas, por outro lado, quantos vizinhos você não toma, a lista de produtos que você pode eventualmente recomendar é muito pequena.
  
• As preferências do usuário podem mudar com o tempo, mas a descrição do item é muito mais estável.
  

O restante do algoritmo repete quase completamente a opção baseada no usuário: a mesma distância de cosseno que a principal medida de proximidade, a mesma necessidade de normalização de dados. O número de mercadorias vizinhas N é geralmente escolhido na região de 20.

Devido ao fato de a correlação de produtos ser considerada em um número maior de observações, não é tão crítico recalculá-la após cada nova avaliação, e você pode fazer isso periodicamente no modo de batalha.

Várias melhorias possíveis no algoritmo:

• Uma modificação interessante é considerar a “similaridade” dos produtos não como distâncias típicas do cosseno, mas comparando seu conteúdo (similaridade baseada em conteúdo). Se, ao mesmo tempo, as preferências do usuário não forem levadas em consideração, essa filtragem deixará de ser “colaborativa”. Além disso, a segunda parte do algoritmo - obtenção de estimativas médias - não muda de forma alguma.
• Outra modificação possível é avaliar os usuários ao calcular a similaridade do item. Por exemplo, quanto mais usuários fizerem classificações, mais peso terão ao comparar dois produtos.
• Em vez de simplesmente calcular a média das estimativas de produtos vizinhos, os pesos podem ser selecionados fazendo uma regressão linear.

Ao usar a abordagem baseada em itens, as recomendações tendem a ser mais conservadoras. De fato, a dispersão de recomendações é menor e, portanto, menos provável de mostrar produtos fora do padrão.

Se na matriz de preferências usarmos a visualização de descrição do produto como uma classificação, é provável que os produtos recomendados sejam análogos - produtos geralmente vistos juntos. Se calcularmos as classificações na matriz de preferências com base em compras, provavelmente os produtos recomendados serão acessórios - mercadorias que geralmente são compradas juntas.

Avaliação da Qualidade do Sistema

Testar o sistema de recomendação é um processo difícil e sempre levanta muitas questões, principalmente devido à ambiguidade do próprio conceito de “qualidade”.

Em geral, nas tarefas de aprendizado de máquina, existem duas abordagens principais para teste:

• teste off-line do modelo em dados históricos usando retro testes,
• testando o modelo finalizado usando o teste A / B (lançamos várias opções, veja qual fornece o melhor resultado).

Ambas as abordagens são ativamente usadas no desenvolvimento de sistemas de recomendação. Vamos começar com o teste offline.

A principal limitação que você precisa enfrentar é avaliar a precisão da previsão que podemos apenas nos produtos que o usuário já avaliou.

A abordagem padrão é a validação cruzada com os métodos deixar para fora e deixar para fora. A repetição repetida do teste com a média dos resultados permite obter uma avaliação de qualidade mais estável.

• deixar um fora - o modelo é treinado em todos os objetos avaliados pelo usuário, exceto um, e é testado nesse único objeto. Isso é feito para todos os n objetos e a média é calculada entre as n estimativas de qualidade obtidas.
• leave-p-out é o mesmo, mas p pontos são excluídos a cada passo.

Todas as métricas de qualidade podem ser divididas em três categorias:

• Precisão da previsão - avalie a precisão da classificação prevista,
• Suporte à decisão - avalie a relevância das recomendações,
• Métricas de precisão da classificação - avalie a qualidade da classificação das recomendações emitidas.
  

Infelizmente, não existe uma métrica recomendada para todas as ocasiões, e todos os envolvidos no teste do sistema de recomendação a selecionam para seus próprios fins.

Quando as classificações são classificadas em uma escala contínua (0-10), as métricas da classe Precisão da Predição geralmente são suficientes.
As métricas da classe Support Support funcionam com dados binários (0 e 1, sim e não). Se em nossa tarefa as classificações forem inicialmente adiadas em uma escala contínua, elas poderão ser convertidas para o formato binário aplicando a regra decisiva - digamos, se a classificação for menor que 3,5, consideraremos a classificação ruim e, se for maior, então boa.
Como regra, as recomendações são exibidas em uma lista de várias posições (primeira parte superior e depois em ordem decrescente de prioridade). As métricas da classe Precisão da classificação medem a correção na ordem em que as recomendações são mostradas em uma lista classificada.
Se usarmos sistemas de recomendação nos negócios on-line, eles geralmente têm dois objetivos (às vezes conflitantes):

1. informar o usuário sobre um produto interessante,
2. Incentive-o a fazer uma compra (enviando pelo correio, compilando uma oferta pessoal etc.).

Como em qualquer modelo que visa motivar o usuário a agir, apenas um aumento incremental na ação de destino deve ser avaliado. Ou seja, por exemplo, ao calcular compras por recomendação, precisamos excluir aquelas que o próprio usuário teria feito sem o nosso modelo. Se isso não for feito, o efeito da introdução do modelo será superestimado.

A elevação é um indicador de quantas vezes a precisão de um modelo excede um determinado algoritmo da linha de base. No nosso caso, o algoritmo da linha de base pode ser simplesmente a falta de recomendações. Essa métrica captura bem o compartilhamento de compras incrementais e permite comparar efetivamente diferentes modelos.

Teste do usuário

Fonte

O comportamento do usuário é uma coisa mal formalizada e nem uma única métrica descreverá completamente os processos de pensamento em sua mente ao escolher um produto. A decisão é influenciada por muitos fatores. Clicar em um link com um produto recomendado ainda não tem sua classificação alta nem interesse. O teste online ajuda a entender parcialmente a lógica do cliente. A seguir, são apresentados alguns cenários para esses testes.

O primeiro e mais óbvio cenário é a análise dos eventos do site. Nós olhamos para o que o usuário está fazendo no site, ele está prestando atenção às nossas recomendações, está seguindo-os, quais recursos do sistema estão em demanda, quais não, quais produtos são mais recomendados e piores. Para entender qual algoritmo como um todo funciona melhor ou apenas tentar uma nova idéia promissora, fazemos testes A / B e coletamos o resultado.

O segundo cenário é receber feedback dos usuários na forma de pesquisas e pesquisas. Como regra, essas são perguntas gerais para entender como os clientes usam o serviço - o que é mais importante: relevância ou diversidade, se é possível mostrar produtos duplicados ou é muito irritante. A vantagem do script é que ele fornece uma resposta direta a todas essas perguntas.

Esse teste é uma coisa complicada, mas para grandes serviços de recomendação é simplesmente necessário. As perguntas podem ser mais complicadas, por exemplo, “qual das listas parece mais relevante para você”, “quanto a folha parece completa”, “você assistirá este filme / lerá um livro”.

Classificações implícitas e dados unários

No início de seu desenvolvimento, foram utilizados sistemas de recomendação em serviços nos quais o usuário avalia claramente o produto classificando-o - são Amazon, Netflix e outros sites de negociação online. No entanto, com a popularidade dos sistemas de recomendação, houve a necessidade de aplicá-los também onde não há classificações - podem ser bancos, oficinas de automóveis, quiosques com shawarma e outros serviços onde, por algum motivo, é impossível estabelecer um sistema de avaliação. Nesses casos, os interesses do usuário podem ser calculados apenas por sinais indiretos - certas ações com o produto indicam preferências do usuário, por exemplo, visualizar a descrição no site, adicionar o produto à cesta etc. Ele usa o princípio de "comprado - significa amor!". Um sistema de classificação implícito é chamado de classificação implícita.

As classificações implícitas obviamente funcionam pior que as explícitas, pois adicionam uma ordem de magnitude a mais ruído. Afinal, um usuário pode comprar um produto como presente para sua esposa ou ir a uma página com uma descrição do produto, apenas para deixar um comentário no estilo de “que tipo de maldade é a mesma coisa” ou para satisfazer sua curiosidade natural.

Se, no caso de classificações explícitas, tivermos o direito de esperar que pelo menos uma classificação negativa seja não, não e sim, não receberemos uma classificação negativa em nenhum lugar. Se o usuário não comprou o livro "Fifty Shades of Grey", ele poderia fazer isso por dois motivos:

• ela realmente não está interessada nele (esse é um caso negativo),
  
• ela está interessada nele, mas ele simplesmente não a conhece (este é um caso positivo perdido).
  

Mas não temos dados para distinguir o primeiro caso do segundo. Isso é ruim, porque ao treinar um modelo, devemos reforçá-lo em casos positivos e positivos em casos negativos, e, portanto, quase sempre vamos bem e, como resultado, o modelo será tendencioso.

O segundo caso é a capacidade de deixar apenas classificações positivas. Um exemplo impressionante é o botão Curtir nas redes sociais. A classificação aqui já está explicitamente explicada, mas, como no exemplo anterior, não temos exemplos negativos - sabemos quais canais o usuário gosta, mas não sabemos quais eles não gostam.

Nos dois exemplos, a tarefa se transforma em uma tarefa de Classificação de Classe Unária .

A solução mais óbvia é seguir um caminho simples e considerar a ausência de uma classificação como negativa. Em alguns casos, isso é mais justificado, em alguns menos. Por exemplo, se sabemos que o usuário provavelmente viu o produto (por exemplo, mostramos a ele a lista de produtos e ele mudou para o produto que o segue), a falta de transição pode realmente indicar falta de interesse.

Fonte

Algoritmos de Fatoração

Seria ótimo descrever os interesses do usuário em "traços" maiores. Não no formato "ele ama os filmes X, Y e Z", mas no formato "ele ama as comédias russas modernas". Além do fato de que isso aumentará a generalização do modelo, também resolverá o problema de uma grande dimensionalidade dos dados - porque os interesses serão descritos não por um vetor de bens, mas por um vetor de preferências significativamente menor.

Tais abordagens também são chamadas de decomposição espectral ou filtragem passa-alta (já que removemos o ruído e deixamos um sinal útil). Existem muitas decomposições diferentes de matrizes na álgebra, e uma das mais comumente usadas é chamada decomposição SVD (decomposição de valor singular).

O método SVD foi usado no final dos anos 80 para selecionar páginas com significado semelhante, mas não com conteúdo, e depois passou a ser usado nas tarefas de recomendações. O método é baseado na decomposição da matriz inicial de classificações ® em um produto de 3 matrizes:

$$$R = U * D * S$onde os tamanhos das matrizes $$$(k, m) = (k, r) * (r, r) * (r, m$e r é
classificação de decomposição - um parâmetro que caracteriza o grau de detalhe da decomposição.

Aplicando essa decomposição à nossa matriz de preferências, obtemos duas matrizes de fatores (descrições abreviadas):

U - descrição compacta das preferências do usuário,
S é uma descrição compacta dos recursos do produto.

É importante que, com essa abordagem, não saibamos quais características correspondem aos fatores nas descrições reduzidas, pois elas são codificadas com alguns números. Portanto, SVD é um modelo não interpretado.

Para obter uma aproximação da matriz de preferências, basta multiplicar a matriz de fatores. Feito isso, obtemos uma pontuação de classificação para todos os pares cliente-produto.

A família geral de tais algoritmos é chamada NMF (fatoração matricial não negativa). Como regra, o cálculo de tais expansões consome muito tempo; portanto, na prática, elas geralmente recorrem a suas variantes iterativas aproximadas.

O ALS (mínimos quadrados alternados) é um algoritmo iterativo popular para decompor uma matriz de preferência em um produto de 2 matrizes: fatores de usuário (U) e fatores de produto (I). Ele trabalha com o princípio de minimizar o erro padrão das classificações. A otimização ocorre alternadamente, primeiro por fatores do usuário e depois por fatores do produto. Além disso, para contornar a reciclagem, os coeficientes de regularização são adicionados ao erro padrão.


Se suplementarmos a matriz de preferências com uma nova dimensão que contém informações sobre o usuário ou produto, poderemos expandir não a matriz de preferências, mas o tensor. Assim, usaremos mais informações disponíveis e, possivelmente, obteremos um modelo mais preciso.

Outras abordagens

Regras de associação

Regras associativas são geralmente usadas na análise de correlações de produtos (Market Basket Analysis) e são mais ou menos assim: "se houver leite no cheque do cliente, em 80% dos casos haverá pão". Ou seja, se percebermos que o cliente já colocou leite na cesta, é hora de lembrar o pão.

Isso não é o mesmo que analisar as compras espaçadas no tempo, mas se considerarmos toda a história como uma grande cesta, podemos aplicar totalmente esse princípio aqui. Isso pode ser justificado quando, por exemplo, vendemos mercadorias únicas caras (crédito, voo).

RBM (máquinas Bolzman restritas)

Máquinas Boltzmann limitadas são uma abordagem relativamente antiga baseada em redes neurais recorrentes estocásticas. É um modelo com variáveis ​​latentes e é semelhante à decomposição de SVD. Ele também procura a descrição mais compacta das preferências do usuário, que é codificada usando variáveis ​​latentes. O método não foi desenvolvido para procurar recomendações, mas foi usado com sucesso nas principais soluções do Prêmio Netflix e ainda é usado em algumas tarefas.

Autoencoders

É baseado no mesmo princípio de decomposição espectral, razão pela qual essas redes também são chamadas de auto-codificadores denoising. A rede primeiro recolhe os dados do usuário que conhece sobre uma representação compacta, tentando deixar apenas informações significativas e, em seguida, restaura os dados para sua dimensão original. O resultado é um tipo de modelo médio, sem ruídos, pelo qual você pode avaliar o interesse em qualquer produto.

DSSM (modelos de similaridade semântica profunda)

Uma das novas abordagens. Com o mesmo princípio, mas no papel de variáveis ​​latentes, aqui estão as descrições de tensores internos dos dados de entrada (incorporação). Inicialmente, o modelo foi criado para correspondência de consulta com documentos (assim como recomendações baseadas em conteúdo), mas é facilmente transformado na tarefa de correspondência de usuários e produtos.


A variedade de arquiteturas de rede profunda é interminável, e é por isso que o Deep Learning fornece um campo verdadeiramente amplo de experimentação para sistemas de recomendação.

Soluções híbridas

Na prática, apenas uma abordagem é raramente usada. Como regra, vários algoritmos são combinados em um para obter o efeito máximo.

As duas principais vantagens da combinação de modelos são o aumento da precisão e a possibilidade de um ajuste mais flexível para diferentes grupos de clientes. As desvantagens são menos interpretabilidade e maior complexidade de implementação e suporte.

Várias estratégias de combinação:

• Ponderação - leia a previsão média ponderada para várias estimativas,
  
• Empilhamento - as previsões de modelos individuais são entradas de outro (meta) classificador que aprende a ponderar corretamente estimativas intermediárias,
  

• Comutação - aplique algoritmos diferentes para diferentes produtos / usuários,
  
• Mistura - as recomendações sobre diferentes algoritmos são calculadas e, em seguida, simplesmente combinadas em uma lista.
  

Por exemplo, é recomendado o recomendador baseado em conteúdo e como um dos recursos - o resultado da filtragem colaborativa.

Empilhamento Ponderado (Linear):

$$

$$P(u,i) = w_1 P_1(u,i) + w_2 P_2(u,i) + … + w_n P_n(u,i)$$

Pesos $$são treinados na amostra. Como regra, a regressão logística é usada para isso.Empilhamento em geral:$w_1,w_2 … w_n$

$$

$$P(u,i) = f_1(u,i) P_1(u,i) + f_2(u,i) P_2(u,i) + … + f_n(u,i) P_n(u,i)$$

Netflix

O Prêmio Netflix foi um concurso realizado em 2009 que exigia que os usuários previssem as classificações dos usuários da biblioteca de filmes Netflix. Bons US $ 1 milhão em prêmios causaram alvoroço e atraíram um grande número de participantes, incluindo pessoas bastante famosas na IA.

Foi uma tarefa com classificações explícitas, pontuações definidas em uma escala de 1 a 5 e a precisão da previsão foi avaliada pelo RMSE. A maioria dos primeiros lugares foi ocupada por grandes conjuntos de classificadores.

O conjunto vencedor usou modelos das seguintes classes:

• modelo básico - um modelo de regressão baseado em estimativas médias
  
• filtragem colaborativa - filtragem colaborativa
  
• RBM - Limited Boltzmann Machines
  
• florestas aleatórias - modelo preditivo
  

O aumento tradicional do gradiente foi usado como um meta-algoritmo que combinava estimativas de algoritmos locais.

Sumário

A tarefa de gerar recomendações é muito simples - compilamos uma matriz de preferências com estimativas de usuário conhecidas por nós; se isso acontecer, complementamos essas estimativas com informações sobre o cliente e o produto e tentamos preencher os valores desconhecidos.

Apesar da simplicidade da declaração, são publicadas centenas de artigos que descrevem métodos fundamentalmente novos para resolvê-la. Em primeiro lugar, isso se deve a um aumento na quantidade de dados coletados que podem ser usados ​​no modelo e um aumento no papel das classificações implícitas. Em segundo lugar, com o desenvolvimento de aprendizado profundo e o advento de novas arquiteturas de redes neurais. Tudo isso multiplica a complexidade dos modelos.

Mas, em geral, toda essa diversidade se resume a um conjunto muito pequeno de abordagens, que tentei descrever neste artigo.