Résumé Technique : Classements Bradley-Terry pour les Systèmes de Recommandation à travers les Taxonomies de Datasets

Énoncé du Problème

Le classement des algorithmes de recommandation est un défi complexe car la performance des modèles est hautement sensible aux caractéristiques des jeux de données, notamment la parcimonie (sparsity), la structure séquentielle et l'échelle. Par conséquent, un algorithme spécifique peut exceller sur un sous-ensemble de datasets tout en étant moins performant sur d'autres. Cette variabilité rend difficile pour les praticiens la sélection de la méthode la plus appropriée pour une tâche donnée sans subir les coûts élevés d'une comparaison directe et exhaustive.

Les méthodes d'évaluation traditionnelles reposent souvent sur l'agrégation naïve de métriques de performance (par exemple, la moyenne du NDCG sur les benchmarks). Les auteurs soutiennent que de telles approches peuvent produire des classements trompeurs ou instables car elles ne tiennent pas compte de la force variable des adversaires selon les datasets et ne fournissent pas de moyen principled pour gérer les données manquantes ou les contextes spécifiques aux datasets. Il existe un besoin critique pour une méthodologie permettant une comparaison et une sélection d'algorithmes équitables et conscientes du contexte des datasets.

Méthodologie

Le papier propose un cadre de classement fondé sur les données basé sur le modèle de Bradley-Terry (BT) et ses extensions. L'approche centrale consiste à traiter l'évaluation des algorithmes de recommandation comme un tournoi où les algorithmes « s'affrontent » sur divers datasets.

1. Cadre de Comparaison par Paires

Au lieu d'agréger les scores bruts des métriques, les auteurs construisent un tableau de tournoi $W$, où $W_{ij}$ représente le nombre de datasets sur lesquels l'algorithme $i$ surpasse l'algorithme $j$.

• Gestion des Égalités : Si les métriques de performance de deux algorithmes sur un dataset tombent dans des intervalles de confiance chevauchants (définis par $métrique \pm std$), la comparaison est traitée comme une égalité. Les auteurs ajoutent 0,5 à la fois à $W_{ij}$ et $W_{ji}$ dans ces cas.
• Estimation : Les auteurs évaluent trois méthodes d'estimation :
  • Zermelo Classique (MLE) : Maximisation itérative de la vraisemblance.
  • BT Bayésien : Utilise Metropolis-Hastings pour échantillonner les paramètres, fournissant des intervalles de confiance et une quantification de l'incertitude.
  • Rank Centrality (Méthode Spectrale) : Modélise les comparaisons comme une marche aléatoire sur un graphe pour estimer les mesures stationnaires.
  • Note : Sur les données de benchmark complètes, les trois méthodes ont convergé vers des classements identiques. L'approche bayésienne a été choisie pour sa capacité à fournir des intervalles de confiance.

2. Métriques de Validation

Pour évaluer la qualité et la robustesse des classements, les auteurs introduisent la métrique des « triplets transitifs ».

• Un triplet $(i, j, k)$ est transitif si $i \succ j$, $j \succ k$, et $i \succ k$.
• La métrique calcule le ratio des triplets transitifs à travers tous les datasets. Un ratio plus élevé indique un classement plus cohérent et stable.
• Cette métrique est spécifiquement conçue pour évaluer la robustesse face aux données manquantes, une limitation des mesures de corrélation de rang standard comme le $\tau$ de Kendall.

3. Extensions Sensibles au Contexte des Datasets

Pour répondre à la limitation selon laquelle un classement global peut ne pas s'appliquer à des datasets non vus, le papier étend le cadre :

• BT Ajusté par les Covariables : Incorpore les caractéristiques des datasets (covariables) telles que la densité, le ratio utilisateur-item et la séquentialité dans le modèle. La probabilité que $i$ batte $j$ est modélisée comme une fonction des forces des algorithmes et des covariables du dataset : $P(i \succ j | x) = \sigma(\beta_{i0} - \beta_{j0} + \langle x, \beta_i \rangle - \langle x, \beta_j \rangle)$. Une régularisation L1 est utilisée pour éviter le surapprentissage.
• Arbres de Bradley-Terry : Une approche non paramétrique qui partitionne récursivement les datasets basés sur les covariables (ex: séquentialité) pour identifier des groupes avec des échelles de préférence homogènes.

Protocole Expérimental

• Datasets : 89 datasets de recommandation diversifiés provenant du benchmark APS et d'autres sources, pré-traités avec un schéma de filtrage 5-core.
• Algorithmes : 14 algorithmes allant d'heuristiques triviales (Random, PopRandom) à des modèles de voisinage (variantes KNN), de factorisation de matrice (ALS, BPR, PureSVD), de graphes (LightGCN, UltraGCN) et des modèles séquentiels (SASRec, GASATF).
• Protocole : Split temporel global (90/5/5) avec optimisation des hyperparamètres via Optuna. Les métriques ont été moyennées sur 10 graines aléatoires pour établir les intervalles de confiance.

Résultats Clés

1. Supériorité sur les Baselines d'Agrégation

Les classements basés sur BT ont démontré une stabilité et une cohérence nettement supérieures par rapport aux méthodes d'agrégation simples (Moyenne et Somme des métriques).

• Triplets Transitifs : Les modèles BT ont atteint un ratio de triplets transitifs plus élevé (ex: 0,631 avec égalités sur tous les datasets) comparé à la Moyenne (0,613) et la Somme (0,613).
• Robustesse aux Données Manquantes : À mesure que la proportion de comparaisons par paires manquantes augmentait, le ratio de triplets transitifs pour les classements Moyenne et Somme chutait rapidement. En revanche, les classements BT et Plackett-Luce (PL) sont restés stables, maintenant un ratio élevé de triplets transitifs même avec des lacunes de données importantes.

2. Performance Dépendante du Contexte

Les expériences ont révélé qu'aucun algorithme unique n'est universellement optimal ; les classements changent radicalement selon la taxonomie du dataset :

• Séquentialité : Les modèles séquentiels (SASRec, GASATF) dominent les datasets séquentiels (rangs 1 et 2) mais chutent considérablement (rangs 10 et 11) sur les données non séquentielles. Inversement, les modèles traditionnels comme ALS et UltraGCN performent mieux sur les données non séquentielles.
• Longueur de l'Historique : Sur les datasets avec des historiques utilisateurs longs, Seq-KNN et GASATF mènent. Sur les datasets à historique court, LightGCN devient le meilleur performeur.
• Parcimonie (Sparsity) : GASATF et User-KNN montrent une amélioration de la performance relative sur les datasets parcimonieux par rapport aux datasets denses.

3. Capacité Prédictive pour les Datasets Inconnus

Les auteurs ont évalué la capacité de prédire les classements sur des datasets de test sans exécuter les modèles :

• Modèles Ajustés par les Covariables : Le modèle BT ajusté par les covariables et les arbres BT ont surpassé l'agrégation simple et le modèle BT global pour prédire le Top-1 de l'algorithme (Top-1 hits : 0,28 pour Cov. BT contre 0,24 pour le BT global).
• Suffisance de la Sélection de Baselines : Malgré la plus grande précision des modèles de covariables dans le classement précis, les auteurs ont constaté que le classement BT global (sans covariables) est suffisant pour sélectionner un ensemble robuste de 5 baselines (Top-5 overlap ~3,32), ce qui est comparable à la performance de modèles plus complexes.

Signification et Revendications

Le papier prétend fournir une méthodologie fondée sur des principes et théoriquement ancrée pour une comparaison d'algorithmes équitable qui dépasse l'agrégation naïve de métriques. Ses principales contributions sont :

1. Un Cadre de Classement Robuste : Démontrer que les classements basés sur BT sont plus stables et cohérents, particulièrement en présence de données manquantes, que les méthodes d'agrégation traditionnelles.
2. Sélection Dépendante du Contexte : Établir que la performance des algorithmes est hautement dépendante du contexte. Le cadre proposé permet aux praticiens de comprendre quels algorithmes sont adaptés à des taxonomies de datasets spécifiques (ex: parcimonieux vs denses, séquentiels vs non-séquentiels).
3. Utilité Prédictive : Montrer que bien que les modèles ajustés par les covariables offrent des prédictions de classement précises pour les datasets non vus, un classement BT global est souvent suffisant pour identifier un ensemble solide d'algorithmes de base, réduisant ainsi le coût computationnel d'une évaluation exhaustive.
4. Reproductibilité : Les auteurs fournissent un dépôt ouvert contenant les implémentations de 14 algorithmes, un cadre d'optimisation des hyperparamètres et des résultats sur 89 datasets, facilitant la recherche reproductible dans les systèmes de recommandation.

Le travail conclut que l'approche proposée offre une base plus fiable et interprétable pour la comparaison d'algorithmes dans les systèmes de recommandation, répondant aux défis de l'hétérogénéité des datasets et de l'instabilité de l'évaluation.