Résumé Technique : Recherche de Voisins Proches Distributionnelle pour la Récupération Sensible à l'Incertitude (dinosaur)

1. Énoncé du Problème

Les systèmes de recommandation modernes à grande échelle s'appuient sur la recherche de Voisins Proches Approximatifs (ANN) pour l'étape de génération de candidats, filtrant des millions d'articles pour en réduire un ensemble gérable pour le classement. Les implémentations standards traitent les représentations des utilisateurs et des articles comme des estimations ponctuelles déterministes (vecteurs uniques) dans un espace latent partagé.

Le papier identifie une faille fondamentale dans ce paradigme :

• Incertitude Inhérente : Les plongements (embeddings) appris à partir de données d'interaction éparses sont intrinsèquement incertains. Cette incertitude est double :
  • Épistémique : Une variance élevée pour les articles de la longue traîne en raison du manque de données d'interaction.
  • Aléatoire : La perte d'information inhérente aux modèles de facteurs latents de faible rang.
• Biais Systématique : La récupération ANN déterministe crée des frontières géométriques rigides. Les articles présentant une incertitude élevée (typiquement le contenu de niche ou de la longue traîne) dont la véritable pertinence pourrait être élevée mais dont l'estimation ponctuelle de la moyenne est légèrement décalée, sont définitivement exclus des $k$ meilleurs candidats.
• Conséquences : Cela conduit à un biais de popularité et à une boucle de rétroaction « riche devient plus riche » où les articles de tête dominent l'exposition, tandis que les créateurs de la longue traîne et les contenus diversifiés sont systématiquement privés d'impressions. Les remèdes existants (par exemple, le re-classement post-hoc ou les objectifs de diversité) sont souvent heuristiques et déconnectés de la cause profonde au stade de la récupération.

2. Méthodologie : Le Cadre dinosaur

Les auteurs proposent dinosaur (Distributional Approximate Nearest Neighbour Search for Uncertainty-Aware Retrieval), un cadre qui incorpore l'incertitude des plongements directement dans le processus de génération de candidats sans modifier l'infrastructure ANN sous-jacente ou les modèles de score.

Mécanisme Central

Au lieu d'indexer une estimation ponctuelle unique $\mu_i$ pour chaque article $i$, dinosaur traite les articles comme des distributions $P(v_i)$ (caractérisées par une moyenne $\mu_i$ et une covariance $\Sigma_i$).

1. Construction de l'Index (Hors ligne) : Pour chaque article $i$, le système tire $S_i$ échantillons indépendants $v_i^{(j)} \sim P(v_i)$ de la distribution d'embedding de l'article. L'index ANN est construit sur cet ensemble augmenté de vecteurs.
2. Exécution de la Requête (En ligne) : Lors du service, un vecteur utilisateur $v_u$ est échantillonné de la distribution de l'utilisateur $P(v_u)$. L'index ANN est interrogé pour trouver les plus proches voisins de ce vecteur échantillonné.
3. Déduplication : Les vecteurs récupérés sont mappés vers leurs identifiants d'articles originaux, et les doublons sont supprimés jusqu'à ce que exactement $k$ articles distincts soient retournés.

Propriétés Clés

• Compatibilité d'Infrastructure : La méthode ne nécessite aucun changement à l'algorithme d'index ANN (par exemple, FAISS, HNSW, ScaNN) ou au modèle de score. Elle nécessite seulement un index capable de gérer un plus grand nombre de vecteurs.
• Deux faces vs Une face : Bien que le cadre supporte l'échantillonnage pour les utilisateurs et les articles, le papier se concentre sur l'incertitude du côté de l'article pour stimuler l'exploration. C'est particulièrement utile dans les places de marché dynamiques où l'échantillonnage des utilisateurs en temps réel pourrait violer les contraintes de latence.
• Échantillonnage Adaptatif : Pour gérer les coûts de mémoire (gonflement de l'index), le papier propose un Échantillonnage Adaptatif, où le budget d'échantillonnage $S_i$ est conditionné par l'incertitude de l'article. Les articles de tête à haute confiance reçoivent $S_i=1$, tandis que les articles incertains de la longue traîne reçoivent $S_i > 1$.

Fondements Théoriques

Le papier fournit des garanties théoriques pour le cadre :

• Convergence : À mesure que la variance de l'embedding s'amenuise ($\sigma^2 \to 0$), dinosaur converge vers la récupération standard par estimation ponctuelle déterministe.
• Expansion Monotone de la Couverture : Pour tout article en dehors du top-$k$ déterministe, la probabilité de récupération augmente strictement avec la variance de son embedding. Cela garantit mathématiquement que les articles incertains reçoivent un « bonus d'exploration lors de la récupération », favorisant structurellement le contenu de la longue traîne sans injection de bruit aléatoire.
• Lien avec l'Échantillonnage de Thompson : Le mécanisme est formellement lié à l'échantillonnage de Thompson, où l'échantillonnage à partir de la distribution postérieure équilibre l'exploration et l'exploitation.

3. Configuration Expérimentale

Les auteurs ont évalué dinosaur sur le jeu de données MovieLens-32M (32 millions d'interactions, ~200k utilisateurs, ~84k articles).

• Baselines : Recherche de produit scalaire exacte (Flat) et recherche approximative (IVFFlat).
• Proxy d'Incertitude : Puisque le modèle de base (iALS) est déterministe, les auteurs ont construit un postérieur épistémique synthétique où l'écart-type $\sigma_i$ est inversement proportionnel au nombre d'interactions de l'article ($n_i$) : $\sigma_i = \alpha / (1 + n_i)^\gamma$.
• Métriques :
  • Recall@K : Métrique d'utilité hors ligne standard.
  • Catalogue Coverage@K : La fraction du catalogue total d'articles apparaissant dans au moins une liste top-$K$ d'un utilisateur.
  • Couverture Stratifiée : Analyse par quintiles de popularité (B0 = plus populaires, B4 = moins populaires).

4. Résultats Clés

• Gains Massifs de Couverture : Augmenter le budget d'échantillonnage de $S=1$ (baseline) à $S=5$ a presque triplé la couverture globale du catalogue (de 23,52 % à 62,97 % à $K=1000$).
• Perte de Rappel Négligeable : Cette expansion de la couverture s'est faite au prix d'un coût minimal pour le rappel hors ligne, avec une réduction de seulement 0,0041 du Recall@1000.
• Exposition de la Longue Traîne :
  • L'IVFFlat standard a atteint une couverture de 0,00 % pour les articles les moins populaires (Bucket B4).
  • dinosaur ($S=5$) a atteint 81,88 % de couverture pour le Bucket B4, garantissant que plus de 13 % des utilisateurs ont reçu des recommandations provenant des articles les plus obscurs.
• Dominance de Pareto : Comparé à une heuristique $\epsilon$-greedy, dinosaur domine strictement la baseline, atteignant un rappel plus élevé pour la même fraction de recommandations exploratoires à travers diverses profondeurs de récupération ($K \in \{100, 500, 1000\}$).

5. Signification et Revendications

Le papier affirme que dinosaur offre une solution principled et compatible avec l'infrastructure au compromis exploration-exploitation dans la récupération.

• Changement de Paradigme : Il déplace la charge de gestion de l'incertitude du re-classement post-hoc ou de la diversification heuristique vers l'étape de la récupération elle-même.
• Briser les Boucles de Rétroaction : En permettant aux articles incertains d'entrer dans l'ensemble des candidats, il brise la boucle de rétroaction algorithmique où les politiques déterministes empêchent les articles de la longue traîne d'être exposés et donc d'apprendre.
• Praticité : La méthode ne nécessite aucun nouvel hyperparamètre au-delà du nombre d'échantillons et fonctionne avec les bibliothèques ANN de production existantes.
• Limites Reconnues : Les auteurs notent que leur proxy d'incertitude est basé sur les comptes d'interactions plutôt que sur des distributions apprises, et que les métriques hors ligne (Recall) sont biaisées par les données MNAR (Missing Not At Random). Ils suggèrent que les travaux futurs devraient combiner une évaluation hors ligne sensible à la propension et des tests A/B en ligne pour mesurer l'impact réel sur le marché.

En résumé, dinosaur démontre que traiter les plongements comme des distributions plutôt que comme des points peut améliorer considérablement la diversité du catalogue et l'exposition de la longue traîne avec une dégradation quasi nulle de l'utilité standard de la récupération.