Riepilogo Tecnico: NASH - Aggregazione Non-lineare di Componenti Informative SHapley

Enunciato del Problema

La selezione dei dati mira a identificare sottoinsiemi di alta qualità dei dati di addestramento per ottimizzare l'utilità del modello (ad esempio, l'accuratezza di validazione $u_V$) sotto vincoli di dimensione. Sebbene Data Shapley e le sue generalizzazioni (semivalori) siano teoricamente fondati sulla teoria dei giochi cooperativi per tenere conto delle interazioni tra i dati, studi empirici recenti indicano che spesso si rivelano inefficaci nella pratica. Nello specifico, selezionare i primi $m$ punti dati basandosi sui valori di Shapley calcolati rispetto a funzioni di utilità complesse (come l'accuratezza di validazione) può produrre sottoinsiemi non migliori, o addirittura peggiori, della selezione casuale.

Il documento individua due ragioni principali per questo fallimento:

1. Mancanza di Informativezza SHapley: Le funzioni di utilità complesse coinvolgono molteplici "ruoli" distinti (ad esempio, diverse classi o sottopopolazioni nel set di validazione). Un singolo valore di Shapley per un dato non riesce a catturare la sua forza unica attraverso questi ruoli. Di conseguenza, dati con forze diverse possono ricevere punteggi di Shapley identici, portando a un trattamento intercambiabile nonostante i loro diversi contributi all'utilità.
2. Aggregazione Inappropriata: Il vero obiettivo (ad esempio, l'accuratezza di validazione) aggrega le prestazioni attraverso questi ruoli in modo non lineare. Tuttavia, l'euristica standard dei primi $m$ si basa su un'aggregazione lineare (somma dei valori di Shapley), che non riesce a catturare le interazioni sinergiche in cui il contributo di un dato dipende da quali altri dati sono già stati selezionati (ad esempio, un dato è più prezioso se copre un ruolo sottorappresentato).

Metodologia: Framework NASH

Gli autori propongono NASH (Aggregazione Non-lineare di Componenti Informative SHapley), un framework che scompone la funzione di utilità complessa in componenti più semplici dove i valori di Shapley sono efficaci, per poi aggregarli in modo non lineare.

1. Informativezza SHapley e Scomposizione

Il documento formalizza l'informativezza SHapley come una proprietà per cui la somma dei valori di Shapley per un sottoinsieme è indicativa della sua effettiva utilità. Gli autori dimostrano che le funzioni di utilità arbitrarie generalmente non sono informative SHapley. Tuttavia, dimostrano che funzioni di utilità più semplici, specificamente la correttezza della previsione su un singolo dato di validazione ($u_v$), sono provatamente informative SHapley sotto l'assunzione di "Giocatore Coerente" (dove un dato è coerentemente buono o cattivo per un specifico punto di validazione).

Invece di calcolare i valori di Shapley per l'accuratezza aggregata di validazione $u_V$, NASH scompone $u_V$ in componenti individuali $u_v$ per ogni dato di validazione $v \in V$. I valori di Shapley $\phi_i(u_v)$ sono calcolati per queste componenti più semplici. Vale la pena notare che il calcolo di questi vettori non comporta costi aggiuntivi di runtime rispetto al calcolo del valore di Shapley per l'aggregato $u_V$, poiché $u_V$ è semplicemente la media di $u_v$.

2. Aggregazione Non-lineare

Per ricostruire l'obiettivo complesso da queste componenti informative, NASH evita la somma lineare (che recupererebbe l'euristica flawed dei primi $m$ basata su Shapley). Invece, ottimizza un obiettivo di aggregazione non-lineare:
$$\max_{M \subseteq N, |M|=m} \sum_{v \in V} F_T(\hat{u}_v(M))$$
dove $\hat{u}_v(M) = \sum_{i \in M} \phi_i(u_v)$ è la somma dei valori di Shapley per la componente $v$, e $F_T$ è una funzione di distribuzione cumulativa (CDF) ispirata alle curve di apprendimento (ad esempio, una legge esponenziale). Questa funzione non lineare garantisce che il processo di selezione privilegi i dati che aiutano a "superare la soglia" per i punti di validazione scarsamente previsti (ruoli non coperti) piuttosto che accumulare punteggi elevati su punti già ben previsti.

3. Ottimizzazione

L'obiettivo NASH è ottimizzato utilizzando un algoritmo greedy. Gli autori mostrano che quando i valori di Shapley sono non negativi, l'obiettivo è monotono e submodulare, garantendo un'approssimazione $(1 - 1/e)$. Anche con valori negativi (derivanti da dati rumorosi), l'algoritmo greedy si comporta bene empiricamente perché i dati dannosi (che causano la non submodularità) vengono naturalmente deprivilegiati. L'algoritmo introduce costi aggiuntivi di runtime minimi, poiché il lavoro pesante (approssimazione di Shapley) è condiviso con i metodi esistenti.

Contributi Chiave

1. Analisi Teorica: Il documento formalizza la proprietà di informativezza SHapley, spiegando perché le complesse funzioni di utilità ML (come l'accuratezza di validazione) non soddisfano tale proprietà, portando alle prestazioni inconsistenti di Data Shapley.
2. Componenti Provatamente Informative: Gli autori identificano e dimostrano che la correttezza della previsione su singoli punti di dati di validazione funge da componenti informative SHapley sotto ipotesi ragionevoli.
3. Framework NASH: Un nuovo framework di selezione dei dati che scompone obiettivi complessi in componenti informative SHapley e li aggrega in modo non lineare per selezionare sottoinsiemi di alta qualità.
4. Validazione Empirica: Esperimenti estesi su dataset standard (regressione logistica, KNN) e sul fine-tuning su larga scala di modelli linguistici (BERT, Llama-2) dimostrano che NASH supera costantemente Data Shapley vanilla, altri semivalori e la selezione casuale.

Risultati

• Selezione Generale dei Dati: In contesti senza rumore iniettato (qualità omogenea), Data Shapley vanilla spesso non performa meglio del caso. NASH aumenta sostanzialmente le prestazioni in questi scenari, superando costantemente le linee di base attraverso vari rapporti di selezione.
• Dataset a Qualità Eterogenea: In contesti con rumore nelle etichette, Data Shapley vanilla migliora (poiché può distinguere i dati scadenti), ma NASH continua a superarlo costantemente. Ciò suggerisce che i benefici di NASH (gestione delle interazioni tra ruoli) sono distinti e complementari alla capacità di Data Shapley di filtrare il rumore.
• Compatibilità: NASH è compatibile con vari semivalori (ad esempio, Beta Shapley, Data Banzhaf) e metodi di approssimazione efficienti (ad esempio, campionamento MC, FreeShap), migliorando costantemente le loro prestazioni di selezione.
• Robustezza: Il metodo è robusto rispetto alla scelta dell'iperparametro $\lambda$ nella funzione di aggregazione e funziona efficacemente con diverse funzioni di utilità (ad esempio, perdita di validazione, MSE).

Significato

Il documento afferma che NASH elimina in gran parte la restrizione secondo cui Data Shapley/semivalori sono efficaci solo su dataset limitati o in contesti specifici (ad esempio, quelli con rumore iniettato). Fornendo un framework che rende la selezione basata su Shapley costantemente affidabile e robusta attraverso dataset diversi e scale di modelli, NASH permette una più ampia adozione di metodi di valutazione dei dati basati su principi. Questo avanzamento supporta la ricerca futura nel migliorare l'efficienza di approssimazione e la selezione dei dati per i modelli fondazionali, assicurando che i benefici teorici dei valori di Shapley (interazione non miope ed equità) siano realizzati nella pratica.