Technische Samenvatting: Hiërarchische Partiële-Orde Modellen voor Ranking

Probleemstelling

Rangaggregatie beoogt geordende lijsten uit diverse bronnen te combineren tot een consensusstructuur. Klassieke parametrische modellen, zoals Mallows en Plackett–Luce, gaan ervan uit dat voorkeuren concentreren rond één of meer volledige consensusrangschikkingen (totale orden). Echter, in veel toepassingen is de aanname dat de ware voorkeurstructuur een totale orde is, niet gerechtvaardigd; beoordelaars kunnen bepaalde items als onvergelijkbaar beschouwen. Bovendien vertonen voorkeursgegevens vaak groepsstructuren (bijv. verschillende beoordelaars, afzonderlijke scenario's of tijdreekssegmenten) die bestaande modellen moeite hebben om te accommoderen terwijl zij partiële-orde structuren behouden.

Hoewel recent werk de totale-orde aanname heeft versoepeld om partiële orden (posets) toe te staan, en ander werk hiërarchische uitbreidingen voor totale orden heeft geïntroduceerd, is er een gebrek aan een verenigd kader dat hiërarchische groepering combineert met partiële-orde consensus. Bestaande hiërarchische modellen voor partiële orden (bijv. Arcagni et al., 2022) vertrouwen op loss-gebaseerde puntramingen in plaats van generatieve Bayesiaanse inferentie.

Methodologie

Het artikel introduceert Hiërarchische Partiële-Orde (HPO) modellen en hun ongesuperviseerde clustering-extensie (HCPO).

1. Het HPO-raamwerk

Het HPO-model is ontworpen voor rangordegegevens die binnen gelabelde groepen binnenkomen (bijv. $A$ beoordelaars). Het is gestructureerd als een boom met een wortelknooppunt dat een "globale" partiële orde vertegenwoordigt en bladknopen die beoordelaar-specifieke partiële orden vertegenwoordigen.

• Constructie van Latente Variabelen: Het model parametriseert partiële orden met behulp van continue latente variabelen. Voor elk item $j$ in het universum van keuzes is er een vector van voorkeursgewichten $U_j \in \mathbb{R}^K$. Een partiële orde wordt gevormd door de intersectie van $K$ volledige orden afgeleid van deze gewichten.
• Generatief Proces:
  • Globaal Niveau: Een globale latente gewichtsmatrix $U^{(0)}$ wordt getrokken uit een multivariate normale verdeling met een correlatiestructuur die wordt gecontroleerd door $\rho$.
  • Lokaal Niveau: Voor elke beoordelaar $a$ worden latente gewichten $U^{(a)}$ getrokken, geconditioneerd op $U^{(0)}$ via een multivariate normale verdeling met de correlatieparameter $\tau$. Deze parameter $\tau \in (0, 1]$ controleert de "shrinkage" (krimp) van beoordelaar-specifieke posets naar de globale poset.
  • Mapping naar Posets: De latente gewichten worden getransformeerd via een Gumbel-constructie (met behulp van de inverse CDF van de Gumbel-verdeling toegepast op de normale CDF) om voorkeursscores $\eta$ te genereren. De partiële orde $h^{(a)}$ wordt gedefinieerd door de intersectie van orden afgeleid van deze scores.
• Observatiemodellen: Het artikel stelt drie likelihoods voor het observeren van een rangschikking $y$ gegeven een poset $h$:
  1. Ruisvrij: Uniforme bemonstering uit lineaire extensies (computationeel duur voor grote $M$).
  2. Queue-jumping: Een herhaald selectiemodel waarbij, met waarschijnlijkheid $p$, een item willekeurig wordt gekozen (ruis), en anders wordt gekozen op basis van de poset-restricties.
  3. Weighted Queue-jumping: Een uitbreiding waarbij willekeurige keuzes worden beïnvloed door de latente scores $\eta$, waardoor fouten minder waarschijnlijk zijn voor items met grote voorkeursverschillen.
  4. Frontier-softmax: Een utility-gebaseerd model waarbij items worden gekozen uit de "frontier" (maximale elementen) van de resterende suborde, gewogen door het aantal items dat zij domineren. Dit is computationeel efficiënt ($O(M)$ per stap) en geschikt voor grote datasets.

2. Het HCPO-raamwerk

Wanneer groepslabels onbekend zijn, breidt het artikel HPO uit naar Hierarchical Clustering Partial-Order (HCPO) modellen.

• Clustering: Een Pitman-Yor proces prior wordt geplaatst op de partitie van lijsten (of beoordelaars) in $G$ latente groepen.
• Inferentie: Het aantal groepen $G$ en de clusterto assignments worden gezamenlijk met de poset-hiërarchie geïnduceerd via Markov Chain Monte Carlo (MCMC).
• Beoordelaar vs. Lijst Clustering: Het model kan individuele lijsten of volledige beoordelaars clusteren (waarbij alle lijsten van een beoordelaar samen worden behandeld).

3. Bayesiaanse Inferentie

Inferentie wordt uitgevoerd met behulp van MCMC. De posterieure verdeling is over de correlatieparameters ($\rho, \tau$), de latente gewichtsmatrices ($U$), de regressiecoëfficiënten ($\beta$) en de partitie ($C$). De dimensie van de latente ruimte $K$ kan ook worden geïnduceerd met behulp van reversible jump MCMC.

Belangrijkste Bijdragen

1. HPO en HCPO Modellen: De introductie van een generatief Bayesiaans raamwerk voor gegroepeerde ranggegevens dat expliciet de groepsspecifieke partiële-orde consensusstructuren modelleert, waarmee de Plackett–Luce modellen wordt uitgebreid naar het poset-domein.
2. Theoretische Eigenschappen:
   • Bewijs dat Plackett–Luce modellen en hun hiërarchische varianten speciale gevallen zijn van HPO (wanneer $K=1$).
   • Demonstratie dat het model marginaal consistent is, wat garandeert dat de prior op sub-ordes consistent is met de prior op de volledige universe.
   • Bewijs dat het model elke hiërarchie van posets kan representeren mits $K \ge \lfloor M/2 \rfloor$.
3. Nieuwe Observatiemodellen: De ontwikkeling van Weighted Queue-jumping en Frontier-softmax likelihoods, die ruis en computationele efficiëntie mogelijk maken terwijl ze een generatieve interpretatie behouden.
4. Ongesuperviseerde Clustering: De uitbreiding naar HCPO voor het ontdekken van latente groepsstructuren in ongelabelde ranggegevens.

Experimentele Resultaten

Het artikel evalueert de modellen op synthetische en real-world datasets:

• Synthetische Data (HPO): In settings met gelabelde groepen slaagt HPO erin de latente hiërarchie van posets te herstellen. De nauwkeurigheid van de herstel is primair gedreven door de lengte van de geobserveerde lijsten (keuzeset grootte) en de koppelingssterkte ($\tau$). De Frontier-softmax likelihood biedt aanzienlijke computationele versnellingen (lineaire schaling met lijstlengte) vergeleken met exacte lineaire-extensie methoden, die vastlopen voor $M \ge 50$.
• Synthetische Data (HCPO): In ongesuperviseerde settings herstelt HCPO accuraat zowel de latente clusteringstructuur als de cluster-specifieke posets. Het voordeel van clustering is het meest prominent wanneer de koppeling tussen groepen zwak is (hoge heterogeniteit).
• Cloud Provisioning Traces (LLM Agents): Toegepast op executietraces van LLM-agents (Aliyun Cloud-IaC-6). Het HPO-model, waarbij verschillende scenario's als groepen worden behandeld, presteerde beter dan onafhankelijke single-poset baselines in het herstellen van de onderliggende afhankelijkheidsgrafen (workflow-structuren). Hiërarchische pooling verbeterde de herwinning van precedence-restricties, vooral in scenario's met schaarse data.
• Menselijke Voorkeursgegevens (3D Geluid): Toegepast op paarwijze akoestische voorkeurgegevens waarbij luisteraars cyclische patronen vertoonden (wat totale orden schendt). Het HCPO-model presteerde significant beter dan totale-orde baselines (Plackett–Luce en Mallows mixtures) in termen van voorspellende fit (WAIC). Cruciaal is dat de HCPO-samenvattingen interpreteerbare structuren onthulden waar clusters brede "toplagen" van onvergelijkbare items bevatten, een kenmerk dat totale-orde modellen niet konden representeren zonder willekeurige strikte rangschikkingen af te dwingen.

Betekenis en Claims

Het artikel claimt dat de voorgestelde HPO en HCPO raamwerken een fundamentele manier bieden om gegroepeerde ranggegevens te behandelen waarbij voorkeuren incompleet of onvergelijkbaar kunnen zijn.

• Structurele Interpreteerbaarheid: De modellen maken het mogelijk om partiële-orde structuren te herstellen die echte onvergelijkbaarheden reflecteren, waardoor artefacten worden vermeden die ontstaan door data in totale orden te dwingen.
• Informatiedeling: De hiërarchische structuur maakt principiële informatieverdeling (shrinkage) over groepen mogelijk, wat de schatting in situaties met weinig data verbetert terwijl groep-specifieke nuances behouden blijven.
• Computationele Haalbaarheid: De Frontier-softmax likelihood maakt de toepassing van deze modellen op grotere itemsets mogelijk waar exacte lineaire-extensie telling onberekenbaar is.
• Generaliteit: Het raamwerk omvat bestaande hiërarchische Plackett–Luce modellen en breidt deze uit naar het partiële-orde domein, wat een verenigde aanpak biedt voor zowel gelabelde als ongelabelde gegroepeerde ranggegevens.

De auteurs benadrukken dat hun aanpak superieur is aan bestaande loss-gebaseerde methoden voor partiële orden door een volledige Bayesiaanse posterior te bieden, wat onzekerheidskwantificering en principiële modelvergelijking via WAIC mogelijk maakt.