Generalized Priority-Aware Shapley Value

Enunciato del Problema

I valori di Shapley e le loro estensioni consapevoli delle priorità sono strumenti standard per l'attribuzione del valore ai contributori nel machine learning (ad esempio, punti dati, caratteristiche o componenti del modello). Tuttavia, i metodi esistenti consapevoli delle priorità, come il Priority-Aware Shapley Value (PASV), si basano su ipotesi restrittive che spesso falliscono nelle moderne applicazioni di AI/ML:

1. Vincoli Binari e Aciclici: Il PASV richiede che le relazioni di priorità a coppie siano codificate come un Grafo Diretto Aciclico (DAG). Questo vieta i cicli (ad esempio, $A \succ B \succ C \succ A$) e tratta la priorità come un vincolo rigido e binario. I dati del mondo reale, come le preferenze umane aggregate (cicli di Condorcet) o i confronti multi-criterio, presentano frequentemente strutture cicliche.
2. Perdita della Magnitudine: Il PASV scarta la forza dell'evidenza della priorità. In scenari come i conteggi delle vittorie nei tornei, i log-odds di Bradley-Terry o i punteggi ELO, la magnitudine della preferenza è importante, ma i metodi basati su DAG catturano solo l'esistenza di una precedenza.
3. Attacchi del Copiatore: I valori di Shapley standard sono vulnerabili agli "attacchi del copiatore" in cui un contribuente che copia un altro riceve un credito uguale. Sebbene il PASV affronti questo problema tramite priorità rigide, non può gestire la natura sfumata, ponderata o ciclica della precedenza nel mondo reale.

Metodologia: Generalized Priority-Aware Shapley Value (GPASV)

Gli autori propongono il GPASV, un Random Order Value (ROV) definito su grafi diretti pesati arbitrari che gestisce simultaneamente strutture cicliche, priorità a coppie ponderate e priorità individuali "soft".

1. Definizione Principale
A differenza del PASV, che limita le permutazioni a quelle coerenti con un DAG, il GPASV definisce una distribuzione di probabilità $p(\lambda, \omega)$ sull'intero insieme delle permutazioni $\Pi$.

• Priorità a Coppie ($\omega$): Rappresentata da un grafo diretto pesato dove $\omega_{ij} \ge 0$ codifica la forza con cui il giocatore $i$ dovrebbe precedere $j$. I cicli sono permessi.
• Priorità Soft ($\lambda$): Pesi individuali che rappresentano fiducia, costo o rischio di conformità.
• Penalità per Violazione: Per una permutazione $\pi$, il costo totale di violazione $V_\omega(\pi)$ è la somma dei pesi per tutte le coppie in cui la precedenza è violata.
• Formulazione della Distribuzione: La distribuzione combina una penalità in stile Gibbs per le violazioni con un meccanismo di priorità soft fase-per-fase:
  $$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]$$
  Qui, $\beta$ è un parametro di temperatura che controlla la rigidità della priorità a coppie. Quando $\beta \to \infty$, il metodo recupera il PASV sui DAG; quando $\beta = 0$, si riduce a una distribuzione Plackett-Luce.

2. Caratterizzazione Assiomatica
Il documento stabilisce il GPASV attraverso un insieme di assiomi che generalizzano quelli del PASV:

• GSCF (Generalized State-Choice Factorization): Garantisce che la distribuzione segua una forma canonica fase-per-fase compatibile con lo schema di campionamento.
• GWP (Generalized Weight Proportionality): I log-odds di scegliere il giocatore $i$ rispetto a $j$ in qualsiasi fase dipendono dai loro pesi soft $\lambda$ e dai loro costi di violazione relativi.
• PVF (Pairwise-Violation Factorization): Quando i pesi soft sono uniformi, la distribuzione si riduce alla forma Gibbs che penalizza le violazioni totali.
  Gli autori dimostrano che il GPASV è l'unico ROV che soddisfa questi assiomi.

3. Framework Computazionale
Il calcolo del GPASV è impegnativo a causa della distribuzione non uniforme sulle permutazioni. Gli autori sviluppano:

• Campionamento: Una catena Metropolis-Hastings (MH) con scambio adiacente e un rapporto di accettazione locale che annulla la maggior parte dei termini globali, rendendola efficiente.
• Inizializzazione: Un'inizializzazione greedy fase-per-fase (Algoritmo 2) che campiona i giocatori all'indietro dalla posizione $n$ per mitigare il problema del "freddo iniziale" nei grafi ciclici dove non esiste alcuna estensione lineare valida.
• Accelerazione:
  • Cache delle Utilità: Riutilizzo delle valutazioni $U(S)$ per sottoinsiemi ripetuti.
  • SNIS (Self-Normalized Importance Sampling): Riutilizzo dei campioni di permutazione attraverso diverse impostazioni di temperatura ($\beta$) o scale di priorità soft ($\lambda$) durante la "scansione delle priorità".
  • Stima Assistita da Surrogati: Utilizzo di surrogati basati sulla regressione (lineari o quadratici) per ridurre la varianza, sebbene gli autori notino che ciò comporta costi di memoria più elevati per il GPASV rispetto al PASV a causa dell'impossibilità di azzerare i termini di interazione per gli archi DAG.

Risultati Chiave e Validazione Empirica

1. Simulazioni

• Tempo di Miscelazione: L'inizializzazione greedy accelera significativamente la miscelazione della catena MH rispetto all'inizializzazione casuale, in particolare nei grafi densi o ciclici.
• Accuratezza: La stima Monte Carlo diretta converge come previsto. I metodi assistiti da surrogati migliorano l'accuratezza ma introducono un sovraccarico sostanziale di tempo di esecuzione e memoria, specialmente per i surrogati quadratici, che non possono sfruttare la sparsità del DAG.
• Scansione delle Priorità: Uno strumento diagnostico in cui le priorità soft ($\lambda$) vengono variate. Gli autori riscontrano che, sotto il GPASV, l'impatto delle priorità soft è sostanzialmente maggiore rispetto al PASV. Poiché il GPASV "ammorbidisce" i vincoli rigidi, le priorità soft individuali possono rimodellare più efficacemente la valutazione, mentre i vincoli rigidi del DAG nel PASV limitano la loro influenza.

2. Applicazione: Valutazione di Ensemble di LLM
Il metodo viene applicato per valutare 20 Large Language Models (LLM) utilizzando:

• Utilità: Prestazioni su MT-Bench (aggregato e giudicato da un LLM).
• Priorità a Coppie: Un grafo ciclico e pesato derivato dalle preferenze umane di Chatbot Arena.
• Priorità Soft: Una preferenza per i modelli open-source rispetto alle API proprietarie a pagamento.

Risultati:

• Valutazione Non Unica: La valutazione non è un singolo numero "corretto". Diversi bilanciamenti tra le preferenze a coppie ($\beta$) e le priorità soft ($\alpha$) producono classifiche sostanzialmente diverse.
• Dominanza della Priorità Soft: Nelle scansioni congiunte, la priorità soft a livello di nodo (preferenza open-source) tende a dominare la priorità del grafo a livello di arco. Ad esempio, aumentare la priorità soft per i modelli open-source può elevarli ai primi posti anche quando il grafo di preferenza a coppie favorisce i modelli a pagamento.
• Hub del Grafo: Quando si danno priorità alle preferenze a coppie ($\beta$) da sole, la valutazione si concentra su specifici "hub" nel grafo delle preferenze (ad esempio, GPT-4), piuttosto che distribuire il valore su una categoria di modelli.

Significato e Affermazioni

Il documento afferma che il GPASV è un'estensione fondata e espressiva delle varianti di Shapley esistenti. Il suo significato principale risiede in:

1. Gestione della Complessità Reale: È il primo metodo a gestire simultaneamente priorità a coppie cicliche e ponderate e priorità individuali soft, includendo il Shapley classico, PSV, WSV e PASV come casi particolari.
2. Trasparenza nei Trade-off: Gli autori sostengono che la valutazione consapevole delle priorità non è un'"operazione a un pulsante". Il GPASV espone il compromesso tra diverse fonti di informazioni sulla priorità (ad esempio, grafi di preferenze umane vs vincoli di distribuzione) come un input esplicito e variabile.
3. Necessità Diagnostica: La diagnostica di "scansione delle priorità" rivela che le priorità soft hanno un impatto molto maggiore sotto il GPASV rispetto a quanto precedentemente pensato sotto il PASV, suggerendo che i metadati relativi alle priorità soft (fiducia, costo, rischio) sono molto più consequenziali per la valutazione di quanto precedentemente riconosciuto.

Il documento conclude che, sebbene il GPASV introduca sfide computazionali, la sua capacità di modellare strutture cicliche e ponderate lo rende essenziale per applicazioni come la valutazione degli LLM, dove le ipotesi standard sui DAG sono violate.