Resumo Técnico: Alocação Restrita de Usuário–Item para Campanhas de Marketing de E-commerce

Definição do Problema: Auto-Targeting (Auto-Segmentação)

O artigo aborda um problema de atribuição combinatória em marketing de e-commerce conhecido como auto-targeting. Diferente das abordagens tradicionais que desacoplam a seleção de itens da atribuição de usuários ou assumem uma estrutura de campanha predefinida, este trabalho formaliza o problema como uma tarefa de otimização conjunta. O objetivo é particionar simultaneamente um conjunto de usuários e um conjunto de itens em $K$ campanhas (grupos) disjuntas de modo que:

1. Coesão: Cada campanha maximize a afinidade total dentro do grupo entre seus usuários e itens atribuídos.
2. Disjuntividade: Cada usuário e item apareça em, no máximo, uma campanha.
3. Restrições: Cada campanha deve conter um número fixo de itens ($I$) e um número de usuários dentro de um intervalo específico ($\tau_{min} \le |U_k| \le \tau_{max}$).

A afinidade entre usuários e itens é derivada de um espaço de embedding compartilhado (aprendido a partir de interações históricas como cliques ou compras), onde a proximidade indica interesse mútuo. A função objetivo busca maximizar a soma das afinidades em todas as campanhas:
$$\max_{\{I_k, U_k\}_{k=1}^K} \sum_{k=1}^K \sum_{i \in I_k} \sum_{u \in U_k} \text{affinity}(i, u)$$

Esta formulação é computacionalmente desafiadora devido ao espaço de busca exponencial e ao acoplamento de restrições, tornando soluções exatas inviáveis para conjuntos de dados de larga escala.

Metodologia

Os autores propõem três estratégias heurísticas complementares para resolver este problema, juntamente com o Simulated Annealing (SA) como baseline:

1. Biclustering Espectral Restrito

Esta abordagem adapta o co-clustering espectral para identificar regiões densas na matriz de afinidade usuário–item.

• Oversampling (Sobreamostragem): Inicialmente, calcula $k' = \alpha k$ biclusters (onde $\alpha \ge 2$) para garantir um pool diversificado de candidatos.
• Pruning (Poda): Os candidatos são podados para satisfazer as restrições de tamanho. Itens e usuários são removidos sequencialmente com base em sua afinidade média dentro do bicluster até que o tamanho máximo seja atingido.
• Seleção: Os candidatos restantes são classificados por densidade (afinidade média), e os $k$ principais biclusters não sobrepostos são selecionados como as campanhas finais.

2. Otimização por Multi-Armed Bandit (MAB)

Este método trata as campanhas como "braços" em uma estrutura de bandit, equilibrando exploração (atribuição de entidades a campanhas de alta afinidade) e explotação (exploração).

• Recompensas Acopladas: As recompensas são endógenas; a afinidade de uma entidade para uma campanha depende da composição atual dessa campanha.
• Estratégias: Os autores implementam dois bônus de exploração:
  • UCB1: Adiciona um limite de confiança ao escore de afinidade.
  • Thompson Sampling: Perturba os escores com ruído Gaussiano que diminui à medida que uma campanha recebe mais atribuições.
• Mecanismo: O algoritmo alterna entre fases de atribuição de usuários e itens, utilizando estatísticas de janela deslizante com decaimento exponencial para se adaptar às mudanças nas composições das campanhas.

3. Busca Local Gananciosa (Greedy Local Search)

Esta estratégia emprega um procedimento ganancioso com restrições de capacidade seguido de refinamento.

• Atribuição Gananciosa: As entidades são atribuídas às campanhas com base no máximo ganho de melhoria, processadas em ordem decrescente de potencial ganho.
• Trocas Pareadas (Swaps): Uma etapa de busca local avalia a troca de entidades entre diferentes campanhas para escapar de ótimos locais. Se uma troca melhorar o objetivo mantendo a viabilidade, ela é executada.
• Iteração: O processo alterna entre atualizações de usuários e itens por um número fixo de iterações.

Baseline: Simulated Annealing Sequencial

Os autores utilizam o Simulated Annealing (SA) como baseline. O problema global é decomposto em $K$ subproblemas sequenciais. Para cada campanha, o SA realiza uma busca local estocástica (usando operações de adicionar, remover e trocar) com uma probabilidade de aceitação controlada por temperatura para aproximar o bicluster ideal.

Principais Contribuições

1. Formalização do Auto-Targeting: O artigo define um novo problema de otimização conjunta que infere tanto a estrutura da campanha quanto as atribuições usuário–item simultaneamente, abordando uma lacuna onde métodos existentes tipicamente fixam um dos lados da atribuição.
2. Adaptação Algorítmica: Os autores adaptam três abordagens distintas (biclustering espectral restrito, busca local gananciosa e multi-armed bandits) para lidar com as restrições específicas de cobertura disjunta e limites de capacidade em um cenário acoplado.
3. Avaliação Abrangente: Os métodos são avaliados em três fontes de dados distintas:
   • Dados Sintéticos: Ambientes controlados com estruturas de verdade fundamental (ground-truth) conhecidas.
   • Benchmarks Públicos: Conjuntos de dados Amazon Reviews (Baby Products, Musical Instruments).
   • Dados Proprietários: Conjuntos de dados comerciais de larga escala (IKEA, Interior Design).

Resultados e Desempenho

A avaliação utiliza métricas incluindo Utilidade (afinidade total), Qualidade (afinidade média), Lift (melhoria sobre a atribuição aleatória) e o Coeficiente de Gini (distribuição de utilidade entre usuários).

• Qualidade da Solução: O Biclustering Espectral Restrito alcança consistentemente os maiores escores em Lift, Qualidade e equidade (menores coeficientes de Gini) em todos os datasets. É particularmente eficaz em recuperar regiões de alta afinidade coerentes, mesmo quando a estrutura subjacente é ruidosa ou sobreposta.
• Trade-off Escalabilidade vs. Qualidade:
  • O Biclustering é altamente eficiente em datasets menores, mas torna-se computacionalmente caro conforme a matriz de afinidade cresce (ex: o tempo de execução aumentou de 1,2 minutos no IKEA para 66,2 minutos no Interior Design).
  • Métodos baseados em Bandits (UCB1 e Thompson Sampling) ofere em uma alternativa escalável para grandes datasets, mantendo um desempenho competitivo com um tempo de execução significativamente menor do que os métodos gananciosos ou SA em escalas muito grandes.
  • A Busca Local Gananciosa é geralmente mais lenta que os métodos de bandit devido às repetidas etapas de busca local.
• Desempenho do Baseline: O Simulated Annealing apresenta um desempenho substancialmente inferior aos métodos propostos em termos de qualidade da solução e incorre no maior custo computacional (frequentmente exigindo horas). Os autores atribuem isso à dificuldade de realizar progressos significativos em espaços combinatórios de alta dimensão usando movimentos de entidade única.

Significância e Alegações

O artigo alega que modelar explicitamente a estrutura conjunta usuário–item é crítico para um design de campanha eficaz. Os resultados sugerem que:

• Otimização Conjunta é Superior: Desacoplar a seleção de itens da atribuição de usuários perde agrupamentos que só emergem da otimização conjunta.
• Biclustering Captura Intenção Latente: A análise qualitativa (ex: no dataset de Musical Instruments) mostra que o biclustering recupera campanhas alinhadas com a intenção latente do usuário (ex: agrupando itens de manutenção de saxofone) em vez de taxonomias superficiais.
• Robustez ao Ruído: O biclustering é robusto ao aumento da variância e do ruído, superando métodos que dependem de sinais individuais de entidades quando o sinal de afinidade está globalmente concentrado em uma pequena fração de pares, mas é difuso por usuário.
• Trade-offs Práticos: Embora o biclustering produza a maior qualidade, os métodos baseados em bandits fornecem uma alternativa viável e escalável para implementações comerciais de escala muito grande, onde o tempo de execução é uma restrição primária.

Os autores concluem que, embora seu framework melhore a relevância e a eficiência do direcionamento, ele depende de embeddings aprendidos a partir de dados comportamentais, necessitando de considerações de transparência e equidade para evitar o reforço de disparidades existentes no direcionamento de usuários.