O remarketing dinâmico (dynrem) no myTarget é uma tecnologia de publicidade direcionada que usa informações sobre ações do usuário em sites e aplicativos móveis de anunciantes. Por exemplo, em uma loja online, um usuário visualiza as páginas de mercadorias ou as adiciona à cesta, e o myTarget usa esses eventos para exibir anúncios precisos dos bens e serviços pelos quais uma pessoa já demonstrou interesse. Hoje falarei mais detalhadamente sobre o mecanismo de gerar recomendações não pessoais, ou seja, item2item-recomendações, que nos permitem diversificar e complementar a produção de publicidade.

Os clientes do dynrem myTarget são principalmente lojas online, que podem ter uma ou mais listas de produtos. Ao criar recomendações, o par “loja - lista de mercadorias” deve ser considerado como uma unidade separada. Mas, por simplicidade, simplesmente usaremos a "loja" a seguir. Se falarmos sobre a dimensão da tarefa de entrada, recomendações devem ser construídas para cerca de mil lojas, e o número de mercadorias pode variar de vários milhares a milhões.

O sistema de recomendação para dynrem deve atender aos seguintes requisitos:

1. O banner contém produtos que maximizam sua CTR.
2. As recomendações são criadas offline por um determinado período.
3. A arquitetura do sistema deve ser flexível, escalável, estável e funcionar em um ambiente de inicialização a frio.

Observe que, desde o requisito de criar recomendações por um tempo fixo e as condições iniciais descritas (assumiremos otimista que o número de lojas está aumentando), um requisito surge naturalmente para o uso econômico dos recursos da máquina.

A seção 2 contém os fundamentos teóricos para a construção de sistemas de recomendação, as seções 3 e 4 discutem o lado prático da questão e a seção 5 resume o resultado geral.

Conceitos básicos

Considere a tarefa de construir um sistema de recomendação para uma loja e liste as abordagens matemáticas básicas.

Decomposição de Valor Singular (SVD)

Uma abordagem popular para a construção de sistemas de recomendação é a abordagem de decomposição singular (SVD). Matriz de classificação $$$R = (r_ {ui})$ representar como um produto de duas matrizes $$$P$ e $$$Q$ para que $$$R \ aprox P Q ^ T$ então classifique a classificação do usuário $$$u$ para mercadorias $$$i$ representado como $$$\ hat {r} _ {ui} = <p_u, q_i>$ [1], onde os elementos do produto escalar são vetores de dimensão $$$k$ (parâmetro principal do modelo). Esta fórmula serve como base para outros modelos SVD. A tarefa de encontrar $$$P$ e $$$Q$ Tudo se resume à otimização da funcionalidade:

(2.1)

$$ $$J (P, Q) = \ sum _ {(u, i)} \ mathcal {L} (r_ {ui}, \ hat {r} _ {ui}) + \ Lambda (P, Q) \ rightarrow \ min_ {P, Q},$$

onde $$$L$ - função de erro (por exemplo, RMSE como na competição da Netflix ), $$$Λ$ - regularização, e o somatório é sobre pares pelos quais a classificação é conhecida. Reescrevemos a expressão (2.1) de forma explícita:

(2.2)

$$ $$J (P, Q) = \ sum _ {(u, i)} (r_ {ui} - <p_u, q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 \ rightarrow \ min_ {P, Q},$$

Aqui $$$λ1$ , $$$λ2$ - Coeficientes de regularização L2 para representações de usuários $$$p_ {u}$ e bens $$$q_ {i}$ em conformidade. O modelo básico para a competição Netflix era:

(2.3)

$$ $$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u, q_i>,$$

(2.4)

$$ $$J (P, Q) = \ sum _ {(u, i)} (r_ {ui} - \ mu - b_u - b_i - <p_u, q_i>) ^ 2 + \ lambda_1 || p_u || ^ 2 + \ lambda_2 || q_i || ^ 2 + \ lambda_3 b_u ^ 2 + \ lambda_4 b_i ^ 2 \ rightarrow \ min_ {P, Q},$$

onde $$$µ$, $$$b_ {u}$e $$$b_ {i}$- vieses para classificação, usuário e produto, respectivamente. O modelo (2.3) - (2.4) pode ser aprimorado adicionando uma preferência implícita do usuário. No exemplo da competição da Netflix, a resposta explícita é a pontuação definida pelo usuário para o filme "a nosso pedido" e outras informações sobre a "interação do usuário com o produto" (exibir o filme, sua descrição e resenhas sobre ele; ou seja, a resposta implícita não dá uma resposta implícita) informações diretas sobre a classificação do filme, mas ao mesmo tempo indica interesse). A contabilidade de resposta implícita é implementada no modelo SVD ++:

(2,5)

$$ $$\ hat {r} _ {ui} = \ mu + b_u + b_i + <p_u + \ frac {1} {\ sqrt {\ sigma_u}} \ sum_ {j \ em S (u)} y_j, \, \ , q_i>,$$

onde $$$S (u)$- um conjunto de objetos com os quais o usuário interagiu implicitamente, $$$σ_ {u} = | S (u) |, y_ {j}$- representação de dimensão $$$k$para um objeto de $$$S (u)$.

Máquinas de Fatoração (FM)

Como pode ser visto nos exemplos com diferentes modelos de SVD, um modelo difere do outro no conjunto de termos incluídos na fórmula de avaliação. Além disso, a expansão do modelo a cada vez representa uma nova tarefa. Queremos que essas alterações (por exemplo, adicionando um novo tipo de resposta implícita, levando em consideração os parâmetros de tempo) sejam facilmente implementadas sem alterar o código de implementação do modelo. Os modelos (2.1) - (2.5) podem ser representados de uma forma universal conveniente usando a seguinte parametrização. Representamos o usuário e o produto como um conjunto de recursos:

(2.6)

$$ $$\ overline {x} ^ U = (x_1 ^ U, x_2 ^ U, \ pontos, x_l ^ U) \ in \ mathbb {R} ^ l,$$

(2,7)

$$ $$\ overline {x} ^ I = (x_1 ^ I, x_2 ^ I, \ pontos, x_m ^ I) \ in \ mathbb {R} ^ m.$$

Fig. 1: Um exemplo de uma matriz de recursos no caso de CF.

Por exemplo, no caso da filtragem colaborativa (CF), quando apenas dados sobre a interação de usuários e produtos são usados, os vetores de recursos se parecem com um código de acesso direto (Fig. 1). Introduzir vetor $$$\ overline {x} = (\ overline {x} ^ U, \ overline {x} ^ I)$, a tarefa de recomendação é reduzida a problemas de regressão com a variável de destino $$$r_ {ui}$:

1. Modelo linear:
   (2.8)
   

   $$ $$h_ {lin} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j$$

2. Poly2:
   (2,9)
   

   $$ $$h_ {poly2} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} w_ {ij} x_i x_j$$

3. FM:
   (2.10)
   

   $$ $$h_ {FM} (\ overline {x}) = w_0 + \ sum_ {j = 1} ^ {l + m} w_jx_j + \ sum_ {i = 1} ^ {l + m} \ sum_ {j = i + 1 } ^ {l + m} x_i x_j <\ overline {v} _i, \ overline {v} _j>$$

onde $$$w_ {j}$- parâmetros do modelo, $$$v_ {i}$São vetores de dimensão $$$k$representando o sinal $$$i$no espaço latente $$$l$e $$$m$- o número de sinais do usuário e do produto, respectivamente. Além dos códigos de acesso único, os recursos baseados em conteúdo (CB, baseados em conteúdo) podem servir como sinalização (Fig. 2), por exemplo, descrições vetorizadas de produtos e perfis de usuário.


Fig. 2: Um exemplo de uma matriz de recursos expandida.

O modelo de FM introduzido em [2] é uma generalização para (2.1) - (2.5), (2.8), (2.10). A essência do FM é que ele leva em consideração a interação pareada de recursos usando um produto escalar $$$<\ overline {v} _i, \ overline {v} _j>$, não usando o parâmetro $$$w_ {ij}$. A vantagem do FM sobre o Poly2 é uma redução significativa no número de parâmetros: para vetores $$$v_ {i}$nós precisaremos $$$(l + m) · k$parâmetros e para $$$w_ {ij}$será necessário $$$lm m$parâmetros. At $$$l$e $$$m$pedidos grandes, a primeira abordagem usa significativamente menos parâmetros.

Observação: se não houver um par específico no conjunto de treinamento $$$(i, j)$, o termo correspondente com $$$w_ {ij}$no Poly2, isso não afeta o treinamento do modelo e a avaliação da classificação é formada apenas na parte linear. No entanto, a abordagem (2.10) nos permite estabelecer relacionamentos através de outros recursos. Em outras palavras, os dados em uma interação ajudam a avaliar os parâmetros de atributos que não estão incluídos neste exemplo.

Com base no FM, é implementado o chamado modelo híbrido, no qual os atributos CB são adicionados aos atributos CF. Ele permite que você resolva o problema de partida a frio, além de levar em consideração as preferências do usuário e fazer recomendações personalizadas.

Lightfm

Na implementação popular do FM , a ênfase está na separação entre as características do usuário e o produto. Matrizes atuam como parâmetros do modelo $$$E ^ U$e $$$E ^ I$Envio de recursos personalizados e do produto:

(2,11)

$$ $$E ^ U = \ begin {pmatrix} \ overline {e} _1 ^ U \\ \ vdots \\ \ overline {e} _l ^ U \ end {pmatrix}, \, \, E ^ I = \ begin {pmatrix } \ overline {e} _1 ^ I \\ \ vdots \\ \ overline {e} _m ^ I \ end {pmatrix}, \ overline {e} _i ^ U \ in \ mathbb {R} ^ k, \ overline { e} _i ^ I \ in \ mathbb {R} ^ k$$

bem como compensações $$$\ overline {b} ^ U, \ overline {b} ^ I \ in \ mathbb {R} ^ k$. Usando visualizações de usuário e produto:

(2,12)

$$ $$\ overline {p} ^ U = \ overline {x} ^ U \ cdot E ^ U = \ sum_ {j = 1} ^ l x_j ^ U \ cdot \ overline {e} _j ^ U,$$

(2,13)

$$ $$\ overline {q} ^ I = \ overline {x} ^ I \ cdot E ^ I = \ sum_ {j = 1} ^ m x_j ^ I \ cdot \ overline {e} _j ^ I,$$

obter a classificação do par $$$(u, i)$:

(2,14)

$$ $$\ hat {r} _ {ui} = <\ overline {p} ^ U, \ overline {q} ^ I> + <\ overline {x} ^ U, \ overline {b} ^ U> + <\ overline {x} ^ I, \ overline {b} ^ I>.$$

Função de perda

No nosso caso, é necessário classificar produtos para um usuário específico, para que um produto mais relevante tenha uma classificação mais alta que um menos relevante. O LightFM possui várias funções de perda:

1. Logística é uma implementação que requer um negativo que não é apresentado explicitamente na maioria das tarefas.
2. O BPR [3] é maximizar a diferença nas classificações entre exemplos positivos e negativos para um usuário em particular. O negativo é obtido usando a amostragem de autoinicialização. A qualidade funcional usada no algoritmo é semelhante ao ROC-AUC.
3. O WARP [4] difere do BPR no método de amostragem de exemplos negativos e na função de perda, que também está classificada, mas ao mesmo tempo otimiza as principais recomendações para o usuário.

Implementação prática

Para criar recomendações por um determinado tempo, é usada uma implementação paralela no Spark. Uma tarefa independente é iniciada para cada loja, cuja execução é controlada pelo luigi.

Pré-processamento de dados

O pré-processamento de dados é realizado por ferramentas Spark SQL escalonáveis ​​automaticamente. Os recursos selecionados no modelo final são descrições textuais de mercadorias e catálogos com conversões padrão.

O que nos ajudou ao interagir com o Spark:

1. Particionamento de dados preparados (matriz de interações de usuários e produtos, sinais para eles) por lojas. Isso permite economizar tempo durante a fase de treinamento na leitura de dados do HDFS. Caso contrário, cada tarefa precisará ler os dados na memória Spark e filtrá-los pelo ID da loja.
2. Salvar / receber dados de / para o Spark é feito em partes. Isso ocorre porque, durante qualquer uma dessas ações, os dados são carregados na memória da JVM. Por que não apenas aumentar a memória da JVM? Primeiramente, a memória disponível para o treinamento do modelo diminui e, em segundo lugar, não há necessidade de armazenar nada na JVM, ela atua nesse caso como um armazenamento temporário.

Modelo de treinamento

O modelo para cada loja é treinado em seu próprio contêiner Spark, para que você possa executar simultaneamente um número arbitrário de tarefas para lojas, limitado apenas pelos recursos do cluster.

O LightFM não possui mecanismos de parada antecipada, portanto, gastamos recursos extras em iterações adicionais de treinamento quando não há aumento na métrica de destino. Escolhemos a AUC como métrica, cuja relação com a CTR é confirmada experimentalmente.

Denotar:

$$$S$- todas as interações conhecidas entre usuários e produtos, ou seja, pares $$$(u, i)$,
$$$I$- muitos de todos os bens $$$i$,
$$$U$- muitos usuários $$$u$.
Para um usuário específico $$$u$também introduzir $$$I_ {u} = {i ∈ I: (u, i) ∈ S}$- Muitos produtos com os quais o usuário interagiu. AUC pode ser calculada da seguinte forma [ref]:

(3.1)

$$ $$AUC (u) = \ frac {1} {| \ mathcal {I} _u || \ mathcal {I} \ setminus \ mathcal {I} _u |} \ sum_ {i \ in \ mathcal {I} _u} \ sum_ {j \ in \ mathcal {I} \ setminus \ mathcal {I} _u} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}),$$

(3.2)

$$ $$AUC = \ frac {1} {| \ mathcal {U} |} \ sum_ {u \ in \ mathcal {U}} AUC (u).$$

Na fórmula (3.1), precisamos calcular a classificação para todos os pares possíveis $$$(u, i)$( $$$u$fixo), bem como comparar classificações para itens de $$$\ mathcal {I} _u$com classificações de $$$\ mathcal {I} \ setminus \ mathcal {I} _u$. Dado que o usuário interage com a parte escassa do sortimento, a complexidade do cálculo é $$$O (| \ mathcal {U} || \ mathcal {I} |)$. Ao mesmo tempo, uma era de treinamento em FM nos custa $$$O (| \ mathcal {U} |)$.

Portanto, modificamos o cálculo da AUC. Primeiro, você deve dividir a amostra em um treinamento $$$\ mathcal {S} ^ {train} \ subconjunto \ mathcal {S}$e validação $$$\ mathcal {S} ^ {val} \ subconjunto \ mathcal {S}$e $$$\ mathcal {S} ^ {val} = \ mathcal {S} \ setminus \ mathcal {S} ^ {train}$. Em seguida, usamos amostragem para criar muitos usuários para validação $$$\ mathcal {U} ^ {val} \ subconjunto \ {u \ in \ mathcal {U}: (u, i) \ in \ mathcal {S} ^ {val} \}$. Para usuário $$$u$de $$$\ mathcal {U} ^ {val}$os elementos da classe positiva serão considerados muitos $$$\ mathcal {I} _u ^ {+} = \ {i \ in \ mathcal {I}: (u, i) \ in \ mathcal {S} ^ {val} \}$similar $$$\ mathcal {I} _u$. Como elementos de uma classe negativa, tomamos uma subamostra $$$\ mathcal {I} _u ^ {-} \ subconjunto \ mathcal {I}$para que nenhum elemento de $$$\ mathcal {I} _u$. O tamanho da subamostra pode ser proporcional ao tamanho. $$$\ mathcal {I} _u ^ {+}$isso é $$$| \ mathcal {I} _u ^ {-} | = c \ cdot | \ mathcal {I} _u ^ {+} |$. Em seguida, as fórmulas (3.1), (3.2) para o cálculo da AUC serão alteradas:

(3.3)

$$ $$AUC (u) = \ frac {1} {| \ mathcal {I} _u ^ {+} || \ mathcal {I} _u ^ {-} |} \ sum_ {i \ in \ mathcal {I} _u ^ {+}} \ sum_ {j \ in \ mathcal {I} _u ^ {-}} \ delta (\ hat {r} _ {ui}> \ hat {r} _ {uj}),$$

(3.4)

$$ $$AUC = \ frac {1} {| \ mathcal {U} ^ {val} |} \ sum_ {u \ in \ mathcal {U} ^ {val}} AUC (u).$$

Como resultado, obtemos um tempo constante para calcular a AUC, uma vez que utilizamos apenas uma parte fixa dos usuários e os conjuntos $$$\ mathcal {I} _u ^ {+}$e $$$\ mathcal {I} _u ^ {-}$tem um tamanho pequeno. O processo de aprendizado para a loja é interrompido após a AUC (3.4) parar de melhorar.

Pesquise objetos semelhantes

Como parte da tarefa item2item, você deve selecionar para cada item $$$n$(ou produtos o mais semelhante possível) àqueles que maximizam a clicabilidade do banner. Nossa suposição: os candidatos ao banner devem ser considerados dos principais $$$k$o mais próximo em casamentos espaciais. Testamos os seguintes métodos para calcular os “vizinhos mais próximos”: Scala + Spark, ANNOY, SCANNs, HNSW.


Para o Scala + Spark em uma loja com 500 mil objetos, foram necessários 15 minutos para calcular uma métrica honesta de cosseno e uma quantidade significativa de recursos de cluster; portanto, testamos métodos aproximados para encontrar vizinhos mais próximos. Ao pesquisar o método das SCANNs, os seguintes parâmetros variaram: bucketLimit , shouldSampleBuckets , NumHashes e setSignatureLength , mas os resultados foram insatisfatórios em comparação com outros métodos (objetos muito diferentes caíram no bucket). Os algoritmos ANNOY e HNSW mostraram resultados comparáveis ​​a um cosseno honesto, mas funcionaram muito mais rápido.

	200k produtos		500k goods		2.2m produtos
Algoritmo	IRRITAR	Hnsw	IRRITAR	Hnsw	IRRITAR	Hnsw
tempo de construção índice (s)	59,45	8.64	258,02	25,44	1190,81	90,45
tempo total (s)	141,23	14/01	527,76	43,38	2081.57	150,92

Devido ao fato de o HNSW funcionar mais rápido que todos os algoritmos, decidimos parar com isso.
Também procuramos os vizinhos mais próximos no contêiner Spark e gravamos o resultado no Hive com o particionamento apropriado.

Conclusão

Lembre-se: usamos o WARP para treinar o modelo, a AUC para a parada antecipada e a avaliação final da qualidade é realizada usando o teste A / B no tráfego ao vivo.

Acreditamos que neste local - na organização do experimento e na seleção da composição ideal do banner - os dados terminam e a ciência começa. Aqui, aprendemos a determinar se faz sentido mostrar recomendações para produtos para os quais o redirecionamento funcionou; exatamente quantas recomendações mostrar; quantos produtos visualizados etc. Falaremos sobre isso nos seguintes artigos.

Outras melhorias no algoritmo - a busca de incorporações universais que permitam que os produtos de todas as lojas sejam colocadas em um espaço - são realizadas dentro da estrutura do paradigma descrito no início do artigo.

Obrigado pela atenção!

Literatura

[1] Ricci F., Rokach L., Shapira B. Introdução ao manual de sistemas de recomendação
// Manual de sistemas de recomendação. - Springer, Boston, MA, 2011 - S. 147160.

[2] Rendle S. Factorization machines // Conferência Internacional IEEE de 2010 sobre Mineração de Dados. - IEEE, 2010 - S. 995-1000.

[3] Rendle S. et al. BPR: Classificação Bayesiana personalizada a partir de feedback implícito
// Anais da vigésima quinta conferência sobre incerteza em inteligência artificial.
- AUAI Press, 2009 - S. 452-461.

[4] Weston J., Bengio S., Usunier N. Wsabie: Ampliando a anotação de imagem de grande vocabulário // Vigésima Segunda Conferência Internacional Conjunta sobre Inteligência Artificial. - 2011.