Hierarchical Partial-Order Models for Ranking

Résumé Technique : Modèles d'Ordres Partiels Hiérarchiques pour le Classement

Énoncé du Problème

L'agrégation de classements vise à combiner des listes ordonnées provenant de sources diverses en une structure de consensus. Les modèles paramétriques classiques, tels que Mallows et Plackett–Luce, supposent que les préférences se concentrent autour d'un ou plusieurs classements de consensus complets (ordres totaux). Cependant, dans de nombreuses applications, l'hypothèse selon laquelle la véritable structure de préférence est un ordre total est injustifiée ; les évaluateurs peuvent considérer certains articles comme incomparables. De plus, les données de préférence présentent souvent des structures de groupe (par exemple, différents évaluateurs, scénarios distincts ou segments de séries temporelles) que les modèles existants peinent à intégrer tout en préservant les structures d'ordre partiel.

Bien que des travaux récents aient assoupli l'hypothèse de l'ordre total pour permettre des ordres partiels (posets), et que d'autres travaux aient introduit des extensions hiérarchiques pour les ordres totaux, il manque un cadre unifié combinant le groupement hiérarchique avec le consensus d'ordre partiel. Les modèles hiérarchiques existants pour les ordres partiels (par exemple, Arcagni et al., 2022) reposent sur des estimations ponctuelles basées sur la perte plutôt que sur l'inférence bayésienne générative.

Méthodologie

Le document présente les modèles de Hiérarchie d'Ordres Partiels (HPO) et leur extension de clustering non supervisé (HCPO).

1. Le Cadre HPO

Le modèle HPO est conçu pour des données de classement arrivant sous forme de groupes étiquetés (par exemple, $A$ évaluateurs). Il est structuré comme un arbre avec un nœud racine représentant un ordre partiel "global" et des nœs feuilles représentant des ordres partiels spécifiques à chaque évaluateur.

• Construction des Variables Latentes : Le modèle paramètre les ordres partiels à l'aide de variables latentes continues. Pour chaque article $j$ dans l'univers de choix, il existe un vecteur de poids de préférence $U_j \in \mathbb{R}^K$. Un ordre partiel est formé par l'intersection de $K$ ordres complets dérivés de ces poids.
• Processus Génératif :
  • Niveau Global : Une matrice de poids latents globale $U^{(0)}$ est tirée d'une distribution normale multivariée avec une structure de corrélation contrôlée par $\rho$.
  • Niveau Local : Pour chaque évaluateur $a$, les poids latents $U^{(a)}$ sont tirés conditionnellement à $U^{(0)}$ via une distribution normale multivariée avec le paramètre de corrélation $\tau$. Ce paramètre $\tau \in (0, 1]$ contrôle le "retrait" (shrinkage) des posets spécifiques à l'évaluateur vers le poset global.
  • Correspondance aux Posets : Les poids latents sont transformés via une construction de Gumbel (en utilisant la fonction de répartition inverse de la distribution de Gumbel appliquée à la fonction de répartition normale) pour générer des scores de préférence $\eta$. L'ordre partiel $h^{(a)}$ est défini par l'intersection des ordres dérivés de ces scores.
• Modèles d'Observation : Le papier propose trois vraisemblances pour observer un classement $y$ étant donné un poset $h$ :
  1. Sans bruit (Noise-free) : Échantillonnage uniforme parmi les extensions linéaires (calcul lourd pour de grands $M$).
  2. Saut de file d'attente (Queue-jumping) : Un modèle de sélection répétée où, avec une probabilité $p$, un article est choisi aléatoirement (bruit), et sinon choisi selon les contraintes du poset.
  3. Saut de file d'attente pondéré (Weighted Queue-jumping) : Une extension où les choix aléatoires sont biaisés par les scores latents $\eta$, rendant les erreurs moins probables pour les articles présentant de grands écarts de préférence.
  4. Frontière-softmax (Frontier-softmax) : Un modèle basé sur l'utilité où les articles sont choisis à partir de la "frontière" (éléments maximaux) du sous-ordre restant, pondérés par le nombre d'articles qu'ils dominent. Il est efficace en termes de calcul ($O(M)$ par étape) et adapté aux grands ensembles de données.

2. Le Cadre HCPO

Lorsque les étiquettes de groupe sont inconnues, le papier étend le HPO au modèle de Clustering Hiérarchique d'Ordres Partiels (HCPO).

• Clustering : Un processus de Pitman-Yor est placé sur la partition des listes (ou évaluateurs) en $G$ groupes latents.
• Inférence : Le nombre de groupes $G$ et les affectations de clusters sont inférés conjointement avec la hiérarchie du poset via l'échantillonnage de Monte Carlo par chaînes de Markov (MCMC).
• Clustering d'Évaluateur vs de Liste : Le modèle peut regrouper les listes individuelles ou les évaluateurs entiers (déplaçant toutes les listes d'un évaluateur ensemble).

3. Inférence Bayésienne

L'inférence est réalisée par MCMC. La distribution a posteriori porte sur les paramètres de corrélation ($\rho, \tau$), les matrices de poids latents ($U$), les coefficients de régression ($\beta$) et la partition ($C$). La dimension de l'espace latent $K$ peut également être inférée à l'aide de l'algorithme MCMC à saut réversible (reversible jump MCMC).

Contributions Clés

1. Modèles HPO et HCPO : L'introduction d'un cadre bayésien génératif pour les données de classement groupées qui modélise explicitement les structures de consensus d'ordre partiel, étendant le modèle Plackett–Luce au domaine des posets.
2. Propriétés Théoriques :
   • Preuve que les modèles Plackett–Luce et leurs variantes hiérarchiques sont des cas particuliers de HPO (lorsque $K=1$).
   • Démonstration que le modèle est marginalement cohérent, garantissant que la distribution a priori sur les sous-ordres est cohérente avec la distribution a priori sur l'univers complet.
   • Preuve que le modèle peut représenter n'importe quelle hiérarchie de posets pourvu que $K \ge \lfloor M/2 \rfloor$.
3. Nouveaux Modèles d'Observation : Le développement des vraisemblances Weighted Queue-jumping et Frontier-softmax, qui permettent de gérer le bruit et l'efficacité de calcul tout en maintenant une interprétation générative.
4. Clustering Non Supervisé : L'extension vers le HCPO pour découvrir les structures de groupe latentes dans les données de classement non étiquetées.

Résultats Expérimentaux

Le papier évalue les modèles sur des données synthétiques et réelles :

• Données Synthétiques (HPO) : Dans les contextes de groupes étiquetés, le HPO réussit à récupérer la hiérarchie latente des posets. La précision de la récupération est principalement pilotée par la longueur des listes observées (taille de l'ensemble de choix) et la force du couplage ($\tau$). La vraisemblance Frontier-softmax offre des accélérations de calcul significatives (mise à l'échelle linéaire avec la longueur de la liste) par rapport aux méthodes exactes d'extensions linéaires, qui échouent pour $M \ge 50$.
• Données Synthétiques (HCPO) : Dans les contextes non étiquetés, le HCPO récupère avec précision à la fois la structure de clustering latente et les posets spécifiques aux clusters. Le bénéfice du clustering est plus marqué lorsque le couplage entre les groupes est faible (forte hétérogénéité).
• Traces de Provisionnement de Cloud (Agents LLM) : Appliqué aux traces d'exécution d'agents LLM (Aliyun Cloud-IaC-6). Le modèle HPO, traitant les différents scénarios comme des groupes, a surpassé les bases de comparaison de single-poset indépendantes pour la récupération des graphes de dépendance sous-jacents (structures de workflow). Le regroupement hiérarchique a amélioré la récupération des contraintes de précédence, particulièrement dans les scénarios à données éparses.
• Données de Préférence Humaine (Son 3D) : Appliqué à des données de préférence de paires acoustiques où les auditeurs présentaient des motifs cycliques (violant les ordres totaux). Le modèle HCPO a nettement surpassé les modèles de mélange de type ordre total (Plackett–Luce et Mallows) en termes de ajustement prédictif (WAIC). Crucialement, les résumés HCPO ont révélé des structures interprétables où les clusters contenaient de larges "couches supérieures" d'éléments incomparables, une caractéristique que les modèles d'ordre total ne pouvaient pas représenter sans imposer des classements stricts arbitraires.

Signification et Revendications

Le papier affirme que les cadres HPO et HCPO proposés fournissent un moyen rigoureux de gérer les données de classement groupées où les préférences peuvent être incomplètes ou incomparables.

• Interprétabilité Structurelle : Les modèles permettent de récupérer des structures d'ordre partiel qui reflètent de véritables incomparabilités, évitant les artefacts introduits par l'imposition d'ordres totaux.
• Partage d'Information : La structure hiérarchique permet un partage d'information (shrinkage) fondé sur des principes entre les groupes, améliorant l'estimation dans les régimes de faibles données tout en préservant les nuances spécifiques à chaque groupe.
• Faisabilité Computationnelle : La vraisemblance Frontier-softmax permet l'application de ces modèles à de plus grands ensembles d'articles là où le comptage exact des extensions linéaires est intraitable.
• Généralité : Le cadre absorbe les modèles hiérarchiques Plackett–Luce existants et étend le domaine des ordres partiels, offrant une approche unifiée pour les données de classement groupées, étiquetées ou non.

Les auteurs soulignent que leur approche est supérieure aux méthodes basées sur la perte pour les ordres partiels en fournissant une distribution a posteriori bayésienne complète, permettant la quantification de l'incertitude et la comparaison de modèles via le WAIC.