Generalized Priority-Aware Shapley Value

Probleemstelling

Shapley-waarden en hun prioriteitsbewuste uitbreidingen zijn standaardtools voor het toekennen van waarde aan bijdragers in machine learning (bijvoorbeeld datapunten, kenmerken of modelcomponenten). Echter, bestaande prioriteitsbewuste methoden, zoals de Priority-Aware Shapley Value (PASV), vertrouwen op restrictieve aannames die vaak falen in moderne AI/ML-toepassingen:

1. Binair en Acyclisch Beperkingen: PASV vereist dat paarsgewijze prioriteitsrelaties worden gecodeerd als een Gerichte Acyclische Graaf (DAG). Dit verbiedt cycli (bijvoorbeeld $A \succ B \succ C \succ A$) en behandelt prioriteit als een harde, binaire beperking. Wereldwijde data, zoals geaggregeerde menselijke voorkeuren (Condorcet-cycli) of meer-criteria vergelijkingen, vertonen vaak cyclische structuren.
2. Verlies van Magnitude: PASV gooit de sterkte van prioriteitsbewijs weg. In scenario's zoals toernooi-overwinningstellingen, Bradley-Terry log-odds of ELO-ratings, is de magnitude van de voorkeur belangrijk, maar DAG-gebaseerde methoden vangen alleen het bestaan van een voorrang.
3. Copier-aanvallen: Standaard Shapley-waarden zijn kwetsbaar voor "copier-aanvallen" waarbij een bijdrager die een ander kopieert, evenveel krediet krijgt. Hoewel PASV dit aanpakt via harde prioriteiten, kan het de genuanceerde, gewogen of cyclische aard van wereldwijde voorrang niet hanteren.

Methodologie: Generalized Priority-Aware Shapley Value (GPASV)

De auteurs stellen GPASV voor, een Random Order Value (ROV) gedefinieerd op willekeurige gerichte gewogen grafen die gelijktijdig cyclische structuren, gewogen paarsgewijze prioriteiten en individuele "zachte" prioriteiten verwerkt.

1. Kern Definitie
In tegenstelling tot PASV, dat permutaties beperkt tot die welke consistent zijn met een DAG, definieert GPASV een kansverdeling $p(\lambda, \omega)$ over de volledige set permutaties $\Pi$.

• Paarsgewijze Prioriteit ($\omega$): Weergegeven door een gewogen gerichte graaf waarbij $\omega_{ij} \ge 0$ de sterkte encodeert dat speler $i$ voor $j$ moet komen. Cycli zijn toegestaan.
• Zachte Prioriteit ($\lambda$): Individuele gewichten die vertrouwen, kosten of nalevingsrisico vertegenwoordigen.
• Schendingsstraf: Voor een permutatie $\pi$ is de totale schendingskost $V_\omega(\pi)$ de som van de gewichten voor alle paren waarbij de voorrang wordt geschonden.
• Verdelingsformulering: De verdeling combineert een Gibbs-stijl straf voor schendingen met een stapsgewijze zachte prioriteitsmechanisme:
  $$p(\lambda, \omega)(\pi) \propto \prod_{t=1}^n \left[ \frac{\lambda_{\pi_t} \exp\{-\beta \cdot V_\omega(\pi_t; S_t)\}}{\sum_{k \in S_t} \lambda_k \exp\{-\beta \cdot V_\omega(k; S_t)\}} \cdot \sum_{k \in S_t} \exp\{-\beta \cdot V_\omega(k; S_t)\} \right]$$
  Hierbij is $\beta$ een temperatuurparameter die de strengheid van de paarsgewijze prioriteit controleert. Als $\beta \to \infty$, herstelt de methode PASV op DAG's; als $\beta = 0$, reduceert het tot een Plackett-Luce verdeling.

2. Axiomatische Karakterisering
Het paper vestigt GPASV via een reeks axioma's die die van PASV generaliseren:

• GSCF (Generalized State-Choice Factorization): Zorgt ervoor dat de verdeling een canonieke stapsgewijze vorm volgt die compatibel is met het bemonsteringsschema.
• GWP (Generalized Weight Proportionality): De log-odds van het kiezen van speler $i$ boven $j$ op enig moment hangen af van hun zachte gewichten $\lambda$ en hun relatieve schendingskosten.
• PVF (Pairwise-Violation Factorization): Wanneer zachte gewichten uniform zijn, reduceert de verdeling tot de Gibbs-vorm die totale schendingen straft.
  De auteurs bewijzen dat GPASV de unieke ROV is die aan deze axioma's voldoet.

3. Computatief Kader
Het berekenen van GPASV is uitdagend vanwege de niet-uniforme verdeling over permutaties. De auteurs ontwikkelen:

• Bemonstering: Een nabijgelegen-swaps Metropolis-Hastings (MH) keten met een lokale acceptatieverhouding die de meeste globale termen cancelt, waardoor het efficiënt is.
• Initialisatie: Een stapsgewijze greedy initialisatie (Algoritme 2) die spelers achteruit bemonstert van positie $n$ om het "cold start"-probleem in cyclische grafen te mitigeren waar geen geldige lineaire uitbreiding bestaat.
• Versnelling:
  • Utility Caching: Hergebruik van $U(S)$-evaluaties voor herhaalde deelverzamelingen.
  • SNIS (Self-Normalized Importance Sampling): Hergebruik van permutatiesteekproeven over verschillende temperatuurinstellingen ($\beta$) of schalen voor zachte prioriteiten ($\lambda$) tijdens "priority sweeping".
  • Surrogaat-gesteunde Schatting: Het gebruik van regressie-gebaseerde surrogaten (lineair of kwadratisch) om variantie te verminderen, hoewel de auteurs opmerken dat dit hogere geheugenkosten met zich meebrengt voor GPASV vergeleken met PASV vanwege het onvermogen om interactietermen voor DAG-randen op nul te zetten.

Belangrijkste Resultaten en Empirische Validatie

1. Simulaties

• Mengtijd: De greedy initialisatie versnelt het mengen van de MH-keten aanzienlijk in vergelijking met willekeurige initialisatie, met name in dichte of cyclische grafen.
• Nauwkeurigheid: Directe Monte Carlo-schatting convergeert zoals verwacht. Surrogaat-gesteunde methoden verbeteren de nauwkeurigheid maar introduceren aanzienlijke runtime- en geheugenoverhead, vooral voor kwadratische surrogaten, die geen gebruik kunnen maken van DAG-sparseheid.
• Priority Sweeping: Een diagnostisch hulpmiddel waarbij zachte prioriteiten ($\lambda$) worden gevarieerd. De auteurs vinden dat onder GPASV de impact van zachte prioriteiten aanzienlijk groter is dan onder PASV. Omdat GPASV harde beperkingen "verzacht", kunnen individuele zachte prioriteiten de waardering effectiever herschikken, terwijl PASV's harde DAG-beperkingen hun invloed beperken.

2. Toepassing: LLM Ensemble Waardering
De methode wordt toegepast om 20 Large Language Models (LLM's) te waarderen met behulp van:

• Utility: Prestaties op MT-Bench (geaggregeerd en beoordeeld door een LLM).
• Paarsgewijze Prioriteit: Een cyclische, gewogen graaf afgeleid van Chatbot Arena menselijke voorkeuren.
• Zachte Prioriteit: Een voorkeur voor open-source modellen boven betaalde propriëtaire API's.

Vondsten:

• Niet-unieke Waardering: Waardering is niet één enkel "correct" getal. Verschillende balanspunten tussen paarsgewijze voorkeuren ($\beta$) en zachte prioriteiten ($\alpha$) leveren substantieel verschillende ranglijsten op.
• Dominantie Zachte Prioriteit: In gezamenlijke sweeps neigt de knooppunt-niveau zachte prioriteit (open-source voorkeur) de rand-niveau graafprioriteit te domineren. Bijvoorbeeld, het verhogen van de zachte prioriteit voor open-source modellen kan hen naar de top van de ranglijst tillen, zelfs wanneer de paarsgewijze voorkeursgraaf betaalde modellen bevoordeelt.
• Graafhubs: Bij het prioriteren van alleen paarsgewijze voorkeuren ($\beta$) concentreert de waardering zich op specifieke "hubs" in de voorkeursgraaf (bijvoorbeeld GPT-4), in plaats van waarde te verspreiden over een categorie modellen.

Betekenis en Claims

Het paper claimt dat GPASV een principieel, expressieve uitbreiding is van bestaande Shapley-varianten. De primaire betekenis ligt in:

1. Omgaan met Wereldwijde Complexiteit: Het is de eerste methode die gelijktijdig cyclische, gewogen paarsgewijze prioriteiten en individuele zachte prioriteiten verwerkt, en klassieke Shapley, PSV, WSV en PASV als speciale gevallen omvat.
2. Transparantie in Trade-offs: De auteurs betogen dat prioriteitsbewuste waardering "geen één-knop-operatie" is. GPASV legt de trade-off tussen verschillende bronnen van prioriteitsinformatie (bijvoorbeeld menselijke voorkeursgrafieken versus implementatiebeperkingen) bloot als een expliciete, doorloopbare invoer.
3. Diagnostische Noodzaak: De "priority sweeping" diagnostiek onthult dat zachte prioriteiten een veel grotere impact hebben onder GPASV dan eerder werd gedacht onder PASV, wat suggereert dat metadata over zachte prioriteiten (vertrouwen, kosten, risico) veel consequenter is voor waardering dan eerder werd herkend.

Het paper concludeert dat hoewel GPASV computatie-uitdagingen introduceert, het vermogen om cyclische en gewogen structuren te modelleren het essentieel maakt voor toepassingen zoals LLM-evaluatie waar standaard DAG-aannames worden geschonden.