🤖 machine learning

Generalized Priority-Aware Shapley Value

Dieser Beitrag stellt den generalisierten prioritätsbewussten Shapley-Wert (GPASV) vor, eine neuartige Bewertungsmethode, die den Shapley-Wert auf beliebige gerichtete gewichtete Prioritätsgraphen erweitert, indem sie Ordnungsverletzungen bestraft statt sie zu verbieten, wodurch eine robuste Bewertung in komplexen realen Szenarien wie zyklischen Präferenzen von LLM-Ensembles ermöglicht wird.

Ursprüngliche Autoren: Kiljae Lee, Ziqi Liu, Weijing Tang, Yuan Zhang

Veröffentlicht 2026-05-15

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kiljae Lee, Ziqi Liu, Weijing Tang, Yuan Zhang

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie organisieren ein riesiges Potluck-Essen, bei dem jeder ein Gericht mitbringt, und Sie möchten herausfinden, wer den größten Anteil an der Köstlichkeit der finalen Mahlzeit verdient. In der Welt des maschinellen Lernens nennt man dies Valuation: herauszufinden, wie sehr jeder Datenpunkt, jedes Merkmal oder jedes Modell zum Endergebnis beigetragen hat.

Seit Jahrzehnten ist das Shapley-Wert-Verfahren das Standardwerkzeug für diese Aufgabe. Stellen Sie es sich wie einen fairen Schiedsrichter vor, der zufällig eine Reihenfolge auswählt, in der die Leute zur Party kommen. Wenn Sie früh ankommen, müssen Sie vielleicht mit weniger Zutaten kochen; wenn Sie spät ankommen, haben Sie vielleicht reichlich Auswahl. Der Schiedsrichter berechnet Ihren Beitrag, indem er sieht, wie sehr sich die Mahlzeit verbessert, wenn Sie erscheinen.

Der alte Schiedsrichter hat jedoch einen blinden Fleck: Er geht davon aus, dass alle gleich sind, es sei denn, es gibt eine strikte, unbrechbare Regel, die besagt: „Person A muss vor Person B ankommen."

Das Problem: Das echte Leben ist chaotisch

In der realen Welt sind Prioritäten nicht nur schwarz-weiße „Müssen". Sie sind oft:

Zyklisch: In einer Gruppe von Freunden mag Alice Bobs Kochen lieber als Charlies, Bob mag Charlies lieber als Daves, aber Dave mag Alices Kochen lieber als Bobs. Es ist ein Kreislauf. Der alte Schiedsrichter steckt in einem Kreis fest und kann keine Entscheidung treffen.
Gewichtet: Manchmal ist die Regel „Alice muss vor Bob ankommen" sehr stark (wie ein Gesetz), manchmal ist es nur ein starker Vorschlag (wie eine Präferenz). Der alte Schiedsrichter behandelt alle Regeln als absolute Gesetze und ignoriert die Stärke der Präferenz.
Weich: Manchmal vertrauen wir bestimmten Personen einfach mehr oder wissen, dass es weniger kostet, sie zu engagieren. Der alte Schiedsrichter weiß nicht, wie er dieses „weiche" Vertrauen einbeziehen soll, ohne die harten Regeln zu brechen.

Die Lösung: Der „Generalized Priority-Aware Shapley Value" (GPASV)

Die Autoren dieses Papiers haben einen neuen, superscharfsinnigen Schiedsrichter namens GPASV erfunden. So funktioniert er, unter Verwendung einfacher Analogien:

1. Das „Weiche-Straf"-System (Umgang mit Kreisen und Gewichten)

Stellen Sie sich vor, der alte Schiedsrichter würde jede Sitzordnung verwerfen, bei der die Regeln auch nur im Geringsten gebrochen wurden. GPASV ist flexibler.

Die Metapher: Anstatt eines strengen „Kein Eintritt"-Schildes verwendet GPASV eine Verkehrsberuhigungshöhe. Wenn Sie die Gäste in einer Reihenfolge anordnen, die eine Präferenz verletzt (z. B. den „Chef" nach dem „Praktikanten" setzen), werden Sie nicht ausgeschlossen. Stattdessen erhalten Sie eine „Strafpunktzahl".
Wie es funktioniert: Je stärker Sie eine starke Präferenz verletzen, desto höher ist die Strafe. Der Schiedsrichter berücksichtigt diese Anordnungen weiterhin, aber sie werden weniger wahrscheinlich ausgewählt. Dies ermöglicht es dem System, Zyklen (Präferenzschleifen) und gewichtete Präferenzen (starke vs. schwache Regeln) zu handhaben, ohne stecken zu bleiben.

2. Der „Vertrauens-Score" (Weiche Priorität)

GPASV hört auch auf Ihre „weichen" Gefühle gegenüber den Gästen.

Die Metapher: Stellen Sie sich eine Gästeliste vor, und Sie haben einen „Vertrauens-Score" für jeden. Vielleicht vertrauen Sie dem Kochen Ihrer Großmutter mehr als dem eines Fremden, auch wenn der Fremde technisch „besser" kochen kann.
Wie es funktioniert: GPASV mischt die harten Regeln (die Verkehrsberuhigungshöhen) mit diesen Vertrauensscores. Es entsteht ein ausgewogener Blick, bei dem ein hochvertrauenswürdiger Gast möglicherweise einen besseren Platz in der Aufstellung erhält, auch wenn er eine geringfügige Regel leicht verletzt.

3. Die „Abtastende" Diagnose (Der Regler)

Eine der coolsten Funktionen von GPASV ist, dass es Ihnen nicht nur eine Antwort gibt. Es gibt Ihnen einen Regler.

Die Metapher: Stellen Sie sich einen Radioregler vor. Auf der einen Seite haben Sie „Nur strikte Regeln" (Harte Priorität). Auf der anderen Seite haben Sie „Nur reines Vertrauen/Präferenz" (Weiche Priorität).
Wie es funktioniert: Die Autoren zeigen, dass Sie diesen Regler drehen können, um zu sehen, wie sich die Bewertung ändert. Wenn Sie den Regler in Richtung „Strikte Regeln" drehen, sehen die Ergebnisse so aus. Wenn Sie ihn in Richtung „Vertrauen" drehen, ändern sich die Ergebnisse völlig. Dies beweist, dass es keine einzige „richtige" Antwort gibt; die Antwort hängt davon ab, wie sehr Sie die Regeln im Vergleich zum Vertrauen wertschätzen.

Der Realwelt-Test: Chatbot Arena

Um zu beweisen, dass dies funktioniert, testeten die Autoren es an LLMs (Large Language Models), speziell unter Verwendung von Daten aus der „Chatbot Arena", bei der Menschen abstimmen, welcher KI-Chatbot besser ist.

Die Situation: Menschliche Stimmen erzeugen oft Schleifen (KI A schlägt B, B schlägt C, aber C schlägt A). Die alten Methoden konnten damit nicht umgehen.
Das Experiment: Sie behandelten die KI-Modelle als die „Gäste" beim Potluck. Sie hatten zwei Arten von Prioritäten:
1. Harte Priorität: Wofür Menschen tatsächlich abgestimmt haben (die Stimmzahlen).
2. Weiche Priorität: Ob die KI „Open Source" (kostenlos) oder „Paid" (teuer) ist.
Das Ergebnis: Sie stellten fest, dass sich der „Gewinner" der Bewertung dramatisch änderte, je nachdem, wie sie den Regler drehten.
- Wenn sie sich nur auf menschliche Stimmen konzentrierten, dominierten die teuren, kostenpflichtigen Modelle (wie GPT-4).
- Wenn sie sich auf die „Open Source"-Präferenz konzentrierten, schossen die kostenlosen Modelle an die Spitze.
- Die Lehre: Man kann nicht einfach auf eine „Wert berechnen"-Taste drücken und eine einzige Wahrheit erhalten. Man muss entscheiden, wie viel Gewicht man menschlichen Stimmen im Vergleich zu eigenen Präferenzen (wie der Unterstützung von Open Source) beimisst. GPASV macht diesen Kompromiss sichtbar und anpassbar.

Zusammenfassung

Das Papier stellt GPASV vor, ein neues mathematisches Werkzeug, das die Mängel älterer Methoden behebt durch:

Das Zulassen von Schleifen in Präferenzen (Zyklen), anstatt stecken zu bleiben.
Das Respektieren der Stärke von Präferenzen (Gewichte), anstatt sie alle als absolute Gesetze zu behandeln.
Die Kombination dieser mit persönlichen Vertrauensscores (weiche Priorität).
Das Aufzeigen, dass der finale „Score" davon abhängt, wie man diese verschiedenen Faktoren ausbalanciert, anstatt eine einzelne, feste Zahl zu sein.

Es ist wie der Upgrade von einem starren, regelgebundenen Schiedsrichter zu einem flexiblen, weisen Vermittler, der versteht, dass Prioritäten im echten Leben chaotisch, gewichtet und manchmal zirkulär sind.

Problemstellung

Shapley-Werte und ihre prioritätsbewussten Erweiterungen sind Standardwerkzeuge zur Wertzuweisung an Beiträge im maschinellen Lernen (z. B. Datenpunkte, Merkmale oder Modellkomponenten). Bestehende prioritätsbewusste Methoden, wie der Priority-Aware Shapley Value (PASV), beruhen jedoch auf einschränkenden Annahmen, die in modernen KI/ML-Anwendungen oft versagen:

Binäre und azyklische Einschränkungen: PASV erfordert, dass paarweise Prioritätsbeziehungen als gerichteter azyklischer Graph (DAG) kodiert werden. Dies verbietet Zyklen (z. B. $A \succ B \succ C \succ A$ ) und behandelt Priorität als harte, binäre Einschränkung. Reale Daten, wie aggregierte menschliche Präferenzen (Condorcet-Zyklen) oder Mehrkriterienvergleiche, weisen häufig zyklische Strukturen auf.
Verlust der Magnitude: PASV verwirft die Stärke von Prioritätsbeweisen. In Szenarien wie Turnier-Siegzahlen, Bradley-Terry-Log-Odds oder ELO-Ratings ist die Magnitude einer Präferenz entscheidend, doch DAG-basierte Methoden erfassen nur die Existenz einer Vorreihenfolge.
Kopier-Angriffe: Standard-Shapley-Werte sind anfällig für „Kopier-Angriffe", bei denen ein Beitragender, der einen anderen kopiert, gleich viel Gutschrift erhält. Während PASV dies über harte Prioritäten adressiert, kann es die nuancierte, gewichtete oder zyklische Natur realer Vorreihenfolgen nicht bewältigen.

Methodik: Generalized Priority-Aware Shapley Value (GPASV)

Die Autoren schlagen GPASV vor, einen Random Order Value (ROV), der auf beliebigen gerichteten gewichteten Graphen definiert ist und gleichzeitig zyklische Strukturen, gewichtete paarweise Prioritäten und individuelle „weiche" Prioritäten handhabt.

1. Kern-Definition
Im Gegensatz zu PASV, das Permutationen auf jene beschränkt, die mit einem DAG konsistent sind, definiert GPASV eine Wahrscheinlichkeitsverteilung $p(\lambda, \omega)$ über die gesamte Menge der Permutationen $\Pi$ .

Paarweise Priorität ( $\omega$ ): Dargestellt durch einen gewichteten gerichteten Graphen, wobei $\omega_{ij} \ge 0$ die Stärke kodiert, mit der Spieler $i$ vor $j$ stehen sollte. Zyklen sind erlaubt.
Weiche Priorität ( $\lambda$ ): Individuelle Gewichte, die Vertrauen, Kosten oder Compliance-Risiken repräsentieren.
Verletzungsstrafe: Für eine Permutation $\pi$ ist die gesamte Verletzungskosten $V_\omega(\pi)$ die Summe der Gewichte aller Paare, bei denen die Vorreihenfolge verletzt wird.
Verteilungsformulierung: Die Verteilung kombiniert eine Gibbs-artige Strafe für Verletzungen mit einem stufenweisen weichen Prioritätsmechanismus:
$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]$
Hier ist $\beta$ ein Temperaturparameter, der die Strenge der paarweisen Priorität steuert. Wenn $\beta \to \infty$ , gewinnt die Methode PASV auf DAGs zurück; wenn $\beta = 0$ , reduziert sie sich auf eine Plackett-Luce-Verteilung.

2. Axiomatische Charakterisierung
Das Papier etabliert GPASV durch eine Reihe von Axiomen, die jene von PASV verallgemeinern:

GSCF (Generalized State-Choice Factorization): Stellt sicher, dass die Verteilung einer kanonischen stufenweisen Form folgt, die mit dem Stichprobenverfahren kompatibel ist.
GWP (Generalized Weight Proportionality): Die Log-Odds, Spieler $i$ gegenüber $j$ in einer beliebigen Stufe zu wählen, hängen von ihren weichen Gewichten $\lambda$ und ihren relativen Verletzungskosten ab.
PVF (Pairwise-Violation Factorization): Wenn weiche Gewichte einheitlich sind, reduziert sich die Verteilung auf die Gibbs-Form, die Gesamtkosten für Verletzungen bestraft.
Die Autoren beweisen, dass GPASV der eindeutige ROV ist, der diese Axiome erfüllt.

3. Rechentechnischer Rahmen
Die Berechnung von GPASV ist aufgrund der nicht-uniformen Verteilung über Permutationen herausfordernd. Die Autoren entwickeln:

Stichprobenziehung: Eine benachbarte Swap-Metropolis-Hastings (MH)-Kette mit einem lokalen Akzeptanzverhältnis, das die meisten globalen Terme aufhebt und sie effizient macht.
Initialisierung: Eine stufenweise gierige Initialisierung (Algorithmus 2), die Spieler rückwärts von Position $n$ abwärts abtastet, um das „Cold-Start"-Problem in zyklischen Graphen zu mildern, in denen keine gültige lineare Erweiterung existiert.
Beschleunigung:
- Utility-Caching: Wiederverwendung von $U(S)$ -Auswertungen für wiederholte Teilmengen.
- SNIS (Self-Normalized Importance Sampling): Wiederverwendung von Permutationsstichproben über verschiedene Temperatureinstellungen ( $\beta$ ) oder weiche Prioritätsskalen ( $\lambda$ ) während des „Priority Sweeping".
- Surrogatgestützte Schätzung: Verwendung regressionsbasierter Surrogate (linear oder quadratisch) zur Varianzreduktion, wobei die Autoren jedoch feststellen, dass dies im Vergleich zu PASV höhere Speicherkosten für GPASV mit sich bringt, da Interaktionsterme für DAG-Kanten nicht auf Null gesetzt werden können.

Wichtige Ergebnisse und empirische Validierung

1. Simulationen

Mischzeit: Die gierige Initialisierung beschleunigt die Mischzeit der MH-Kette im Vergleich zur zufälligen Initialisierung erheblich, insbesondere in dichten oder zyklischen Graphen.
Genauigkeit: Die direkte Monte-Carlo-Schätzung konvergiert wie erwartet. Surrogatgestützte Methoden verbessern die Genauigkeit, führen jedoch zu erheblichem Laufzeit- und Speicheraufwand, insbesondere für quadratische Surrogate, die die DAG-Sparsity nicht ausnutzen können.
Priority Sweeping: Ein Diagnosewerkzeug, bei dem weiche Prioritäten ( $\lambda$ ) variiert werden. Die Autoren stellen fest, dass unter GPASV der Einfluss weicher Prioritäten deutlich größer ist als unter PASV. Da GPASV harte Einschränkungen „weicht", können individuelle weiche Prioritäten die Bewertung effektiver umgestalten, wohingegen PASVs harte DAG-Einschränkungen ihren Einfluss begrenzen.

2. Anwendung: LLM-Ensemble-Bewertung
Die Methode wird angewendet, um 20 Large Language Models (LLMs) zu bewerten unter Verwendung von:

Utility: Leistung auf MT-Bench (aggregiert und von einem LLM bewertet).
Paarweise Priorität: Ein zyklischer, gewichteter Graph, abgeleitet aus menschlichen Präferenzen der Chatbot Arena.
Weiche Priorität: Eine Präferenz für Open-Source-Modelle gegenüber kostenpflichtigen proprietären APIs.

Ergebnisse:

Nicht-eindeutige Bewertung: Die Bewertung ist keine einzelne „korrekte" Zahl. Unterschiedliche Balance zwischen paarweisen Präferenzen ( $\beta$ ) und weichen Prioritäten ( $\alpha$ ) ergeben substantiell unterschiedliche Rangfolgen.
Dominanz weicher Prioritäten: Bei gemeinsamen Sweeps neigt die Knoten-Ebene weiche Priorität (Open-Source-Präferenz) dazu, die Kanten-Ebene Graph-Priorität zu dominieren. Beispielsweise können Open-Source-Modelle durch Erhöhung ihrer weichen Priorität in die Top-Ränge aufsteigen, selbst wenn der paarweise Präferenzgraph kostenpflichtige Modelle bevorzugt.
Graph-Hubs: Wenn nur paarweise Präferenzen ( $\beta$ ) priorisiert werden, konzentriert sich die Bewertung auf spezifische „Hubs" im Präferenzgraphen (z. B. GPT-4), anstatt den Wert über eine Kategorie von Modellen zu verteilen.

Bedeutung und Behauptungen

Das Papier behauptet, dass GPASV eine prinzipielle, ausdrucksstarke Erweiterung bestehender Shapley-Varianten ist. Seine primäre Bedeutung liegt in:

Bewältigung realer Komplexität: Es ist die erste Methode, die gleichzeitig zyklische, gewichtete paarweise Prioritäten und individuelle weiche Prioritäten handhabt und klassische Shapley-Werte, PSV, WSV und PASV als Spezialfälle abdeckt.
Transparenz bei Trade-offs: Die Autoren argumentieren, dass prioritätsbewusste Bewertung „kein Ein-Knopf-Operation" ist. GPASV macht den Trade-off zwischen verschiedenen Quellen von Prioritätsinformationen (z. B. menschliche Präferenzgraphen vs. Bereitstellungseinschränkungen) als expliziten, durchsweepten Eingabeparameter sichtbar.
Diagnostische Notwendigkeit: Die „Priority Sweeping"-Diagnose zeigt, dass weiche Prioritäten unter GPASV einen viel größeren Einfluss haben als bisher unter PASV angenommen, was darauf hindeutet, dass Metadaten bezüglich weicher Prioritäten (Vertrauen, Kosten, Risiko) für die Bewertung weit folgenreicher sind als bisher erkannt.

Das Papier schließt, dass GPASV zwar rechnerische Herausforderungen mit sich bringt, seine Fähigkeit jedoch, zyklische und gewichtete Strukturen zu modellieren, es für Anwendungen wie die LLM-Evaluation unverzichtbar macht, bei denen Standard-DAG-Annahmen verletzt werden.