Resumo Técnico: Busca de Vizinhos Próximos Aproximados Distribuicional para Recuperação Consciente de Incerteza (dinosaur)

1. Definição do Problema

Os sistemas de recomendação modernos de larga escala dependem da busca de Vizinhos Próximos Aproximados (ANN) na etapa de geração de candidatos, filtrando milhões de itens para um conjunto gerenciável para o ranqueamento. Implementações padrão tratam as representações de usuários e itens como estimativas de ponto determinísticas (vetores únicos) em um espaço latente compartilhado.

O artigo identifica uma falha fundamental neste paradigma:

• Incerteza Inerente: Embeddings aprendidos a partir de dados de interação esparsos são inerentemente incertos. Esta incerteza é dupla:
  • Epistêmica: Alta variância para itens de cauda longa devido à falta de dados de interação.
  • Aleatória: Perda de informação inerente aos modelos de fatores latentes de baixo posto.
• Viés Sistemático: A recuperação ANN determinística cria fronteiras geométricas rígidas. Itens com alta incerteza (tipicamente conteúdo de nicho ou de cauda longa) cuja relevância real pode ser alta, mas cuja estimativa de ponto média está ligeiramente deslocada, são permanentemente excluídos dos $k$ candidatos principais.
• Consequências: Isso leva ao viés de popularidade e a um ciclo de feedback de "rico fica mais rico", onde itens de topo (head items) dominam a exposição, enquanto criadores de cauda longa e conteúdos diversos são sistematicamente privados de impressões. Remédios existentes (ex: re-ranqueamento post-hoc ou objetivos de diversidade) são frequentemente heurísticos e desconectados da causa raiz no estágio de recuperação.

2. Metodologia: O Framework dinosaur

Os autores propõem o dinosaur (Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval), um framework que incorpora a incerteza do embedding diretamente no processo de geração de candidatos sem alterar a infraestrutura de ANN subjacente ou os modelos de pontuação.

Mecanismo Central

Em vez de indexar uma única estimativa de ponto $\mu_i$ para cada item $i$, o dinosaur trata os itens como distribuições $P(v_i)$ (caracterizadas por uma média $\mu_i$ e uma covariância $\Sigma_i$).

1. Construção do Índice (Offline): Para cada item $i$, o sistema extrai $S_i$ amostras independentes $v_i^{(j)} \sim P(v_i)$ de sua distribuição de embedding. O índice ANN é construído sobre este conjunto aumentado de vetores.
2. Execução da Consulta (Online): No momento do serviço, um embedding de usuário $v_u$ é amostrado da sua distribuição $P(v_u)$. O índice ANN é consultado para encontrar os vizinhos mais próximos deste vetor amostrado.
3. Deduplicação: Os vetores recuperados são mapeados de volta para seus identificadores originais de item, e duplicatas são removidas até que exatamente $k$ itens distintos sejam retornados.

Propriedades Principais

• Compatibilidade de Infraestrutura: O método não requer mudanças no algoritmo de índice ANN (ex: FAISS, HNSW, ScaNN) ou no modelo de pontuação. Requer apenas um índice capaz de lidar com um número maior de vetores.
• Lado Duplo vs. Lado Único: Embora o framework suporte amostragem tanto para usuários quanto para itens, o artigo foca na incerteza do lado do item para impulsionar a exploração. Isso é particularmente útil em marketplaces dinâmicos onde a amostragem de usuário em tempo real pode violar restrições de latência.
• Amostragem Adaptativa: Para gerenciar custos de memória (inchaço do índice), o artigo propõe Amostragem Adaptativa, onde o orçamento de amostras $S_i$ é condicionado à incerteza do item. Itens de topo com alta confiança recebem $S_i=1$, enquanto itens de caça longa incertos recebem $S_i > 1$.

Fundamentos Teóricos

O artigo fornece garantias teóricas para o framework:

• Recuperação: À medida que a variância do embedding desaparece ($\sigma^2 \to 0$), o dinosaur converge para a recuperação determinística padrão de estimativa de ponto.
• Expansão de Cobertura Monotônica: Para qualquer item fora do top-$k$ determinístico, a probabilidade de recuperação aumenta estritamente com a variância de seu embedding. Isso garante matematicamente que itens incertos recebam um "bônus de exploração de fase de recuperação", favorecendo estruturalmente o conteúdo de cauda longa sem a injeção de ruído aleatório.
• Conexão com Thompson Sampling: O mecanismo é formalmente vinculado ao Thompson Sampling, onde a amostragem da distribuição posterior equilibra exploração e explotação.

3. Configuração Experimental

Os autores avaliaram o dinosaur no dataset MovieLens-32M (32M interações, ~200k usuários, ~84k itens).

• Baselines: Busca de Produto Interno Exata (Flat) e Busca Aproximada (IVFFlat).
• Proxy de Incerteza: Como o modelo base (iALS) é determinístico, os autores construíram um posterior epistêmico sintético onde o desvio padrão $\sigma_i$ é inversamente proporcional ao número de interações do item ($n_i$): $\sigma_i = \alpha / (1 + n_i)^\gamma$.
• Métricas:
  • Recall@K: Métrica de utilidade offline padrão.
  • Cobertura do Catálogo@K: A fração do catálogo total de itens que aparece em pelo menos uma lista top-$K$ de um usuário.
  • Cobertura Estratificada: Análise por quintis de popularidade (B0 = mais populares, B4 = menos populares).

4. Resultados Principais

• Ganhos Massivos de Cobertura: Aumentar o orçamento de amostras de $S=1$ (baseline) para $S=5$ quase triplicou a cobertura global do catálogo (de 23,52% para 62,97% em $K=1000$).
• Perda de Recall Negligenciável: Esta expansão na cobertura veio com um custo mínimo para o recall offline, com uma redução de apenas 0,0041 no Recall@1000.
• Exposição de Cauda Longa:
  • O IVFFlat padrão alcançou 0,00% de cobertura para os itens menos populares (Bucket B4).
  • O dinosaur ($S=5$) alcançou 81,88% de cobertura para o Bucket B4, garantindo que mais de 13% dos usuários recebessem recomendações de itens extremamente obscuros.
• Dominância de Pareto: Quando comparado contra uma heurística $\epsilon$-greedy, o dinosaur dominou estritamente o baseline, alcançando maior recall para a mesma fração de recomendações exploratórias através de várias profundidades de recuperação ($K \in \{100, 500, 1000\}$).

5. Significância e Alegações

O artigo afirma que o dinosaur oferece uma solução fundamentada e compatível com a infraestrutura para o compromisso entre exploração e explotação na recuperação.

• Mudança de Paradigma: Ele transfere o fardo de lidar com a incerteza do re-ranqueamento post-hoc ou da diversificação heurística para a própria etapa de recuperação.
• Quebra de Ciclos de Feedback: Ao permitir que itens incertos entrem no conjunto de candidatos, ele quebra o ciclo de feedback algorítmico onde políticas determinísticas impedem que itens de cauda longa sejam expostos e, portanto, aprendam.
• Praticidade: O método não requer novos hiperparâmetros além da contagem de amostras e funciona com bibliotecas de ANN de nível de produção já existentes.
• Limitações Reconhecidas: Os autores observam que seu proxy de incerteza é baseado em contagens de interação, em vez de distribuições aprendidas, e que as métricas offline (Recall) são enviesadas por dados MNAR (Missing Not At Random). Eles sugerem que trabalhos futuros combinem avaliação offline consciente de propensão com testes A/B online para medir o verdadeiro impacto no mercado.

Em resumo, o dinosaur demonstra que tratar embeddings como distribuições em vez de pontos pode melhorar significativamente a diversidade do catálogo e a exposição da cauda longa com quase nenhuma degradação na utilidade de recuperação padrão.