Riepilogo Tecnico: Semivalori Quoziente per l'Attribuzione dei Dati Resistenti ai False-Name

1. Enunciato del Problema

I metodi di valutazione dei dati, come Data Shapley, sono progettati per allocare i pagamenti e verificare il contributo dei dati di formazione alle pipeline di apprendimento automatico. Tuttavia, questi metodi presuppongono tipicamente un insieme fisso di contributori passivi. Nei mercati dei dati reali, i contributori sono agenti strategici che possono manipolare il meccanismo di attribuzione per inflazionare la propria quota.

Il documento identifica la manipolazione false-name come un punto di rottura critico. Un singolo fornitore latente può:

• Dividere un dataset tra molteplici identità pseudonime (attacchi Sybil).
• Duplicare esempi ad alto valore o creare quasi-duplicati (parafrasi, aumentazioni, varianti sintetiche).
• Riciclare varianti sintetiche per sfruttare il set di validazione del valutatore.

Il problema fondamentale è che l'attribuzione equa secondo Shapley standard sulle identità riportate non è compatibile con gli incentivi. Poiché il valore dei dati è spesso non additivo e complementare, la divisione di un dataset in più identità può aumentare la somma dei valori di Shapley ricevuti dall'attaccante rispetto al valore ricevuto da una singola identità onesta.

2. Metodologia

2.1 Modello Formale

Gli autori formalizzano il contesto come un problema di progettazione di meccanismi su fornitori latenti ($N$) e identità sottomesse ($m$).

• Gioco del Valore dei Dati: Un gioco monotono in cui il valore di una coalizione è l'utilità dell'apprenditore addestrato sull'unione dei carichi utili di quella coalizione.
• Classi di Manipolazione:
  • Divisione false-name: Sostituire un'identità con $k \ge 2$ identità che detengono una partizione o una replica dei dati originali.
  • Attacco con varianti: Sottomettere copie trasformate (duplicati, parafrasi, dati sintetici) sotto una o più identità.
• Metrica di Guadagno: Il guadagno additivo o moltiplicativo che un attaccante ottiene manipolando la struttura delle identità rispetto alla segnalazione onesta.

2.2 Risultato di Impossibilità

Il documento dimostra un teorema fondamentale di impossibilità: l'attribuzione esattamente equa secondo Shapley sulle identità riportate è incompatibile con la resistenza illimitata ai false-name.
Anche su giochi binari e monotoni (ad esempio, giochi di unanimità), un fornitore può aumentare il proprio pagamento totale dividendo i propri dati in più pseudonimi. Ad esempio, in un gioco di unanimità a due giocatori dove $v(\{A, B\}) = 1$, il fornitore $A$ riceve $1/2$. Se $A$ si divide in $A_1, A_2$ tale che il valore richieda tutti e tre ($A_1, A_2, B$), i nuovi valori di Shapley sono $1/3$ ciascuno, producendo un totale di $2/3$ per $A$. Questa vulnerabilità strutturale si estende ai semivalori generali (Banzhaf, Beta-Shapley), sebbene l'entità del guadagno vari.

2.3 Il Meccanismo del Semivalore Quoziente

Per risolvere ciò, gli autori propongono il meccanismo del Semivalore Quoziente, che sposta l'unità strategica dalle identità sottomesse grezze ai cluster di attribuzione supportati da prove.

1. Grafo delle Prove e Clustering:
   • Una funzione di prova $e_\theta(u, u')$ determina se due unità (esempi, documenti) sono sufficientemente simili (basandosi su hash, embedding, provenienza, ecc.) da essere trattate come lo stesso oggetto di attribuzione.
   • Questo forma un grafo in cui le componenti connesse sono cluster ($C_1, \dots, C_K$).
2. Operatore Rappresentativo del Cluster ($R_\theta$):
   • Per prevenire la manipolazione tramite duplicazione all'interno del cluster (ad esempio, sottomettere 10 copie di un esempio per dargli più peso), un operatore rappresentativo canonico mappa ogni cluster su un insieme fisso di unità di formazione canoniche.
   • Le strategie includono: collasso dei duplicati esatti, limitazione del numero di unità per cluster o unioni normalizzate per peso.
3. Gioco Quoziente:
   • Viene costruito un nuovo gioco cooperativo in cui i giocatori sono i cluster, non le identità.
   • Il valore di una coalizione di cluster è l'utilità dell'apprenditore addestrato sull'unione dei loro rappresentanti canonici.
4. Calcolo del Semivalore e Allocazione:
   • I semivalori (Shapley, Banzhaf, ecc.) sono calcolati sul gioco quoziente.
   • Allocazione Interna al Cluster: Il pagamento a un cluster è distribuito tra le identità sottomesse al suo interno. Il meccanismo richiede una regola di allocazione neutrale rispetto ai false-name (ad esempio, allocazione proporzionale al conteggio delle unità canoniche contribuite da ciascuna identità) per garantire che la divisione di un'identità all'interno di un cluster non aumenti la quota totale.

3. Contributi Chiave

1. Modello Formale: Un quadro rigoroso per la manipolazione da parte dei fornitori di dati che coinvolge fornitori latenti, identità sottomesse e attacchi di trasformazione.
2. Teorema di Impossibilità: Dimostrazione che nessun meccanismo può essere contemporaneamente esattamente equo secondo Shapley sulle identità riportate e illimitatamente resistente ai false-name.
3. Meccanismo del Semivalore Quoziente: Una soluzione costruttiva che calcola i semivalori su cluster supportati da prove con un operatore rappresentativo canonico.
4. Garanzie Teoriche:
   • Resistenza Esatta ai False-Name: Ottenuta sotto manipolazioni "quoziente-stabili" (dove l'attaccante non può sfuggire al proprio cluster onesto o alterare il rappresentante canonico) e allocazione neutrale rispetto ai false-name.
   • Garanzie Approssimate: Limiti sul guadagno di manipolazione e sulla perdita di equità in termini di tre quantità misurabili: massa del cluster evaso (varianti che formano nuovi cluster), errore di stima del valore e distanza di clustering (deriva del rappresentante).
5. DataMarket-Gym: Un nuovo benchmark per valutare i meccanismi di attribuzione sotto attacchi strategici dei fornitori, che copre duplicati esatti, quasi-duplicati, riciclaggio sintetico e divisione Sybil.

4. Risultati Sperimentali

Gli autori valutano il meccanismo su dataset sintetici e reali (CIFAR-10, AG News, STL-10, IMDB).

• Classificazione Sintetica:
  • La Shapley di base sulle identità grezze ha mostrato un guadagno di manipolazione di 1.74 su attacchi duplicati/Sybil.
  • La Shapley Quoziente con prove a livello di esempio (similarità coseno $\theta=0.99$) ha ridotto questo guadagno a 0.96, neutralizzando efficacemente l'attacco e tornando a livelli quasi onesti.
  • Il meccanismo è robusto rispetto alla scelta del semivalore (Shapley, Banzhaf, Beta-Shapley).
• Sensibilità alla Soglia:
  • La soglia del coseno $\theta$ è critica. Una soglia troppo bassa causa "fusioni false" (fornitori indipendenti raggruppati insieme), che possono amplificare i guadagni Sybil. Una soglia troppo alta non riesce a catturare i quasi-duplicati.
  • Il documento identifica un inversione della soglia specifica del dominio:
    • Nei domini delle immagini (CIFAR-10), norme elevate portano a elevate similarità a coppie; è richiesta una soglia più stretta ($\theta \ge 0.90$) per prevenire attacchi a catena.
    • Nei domini testuali (AG News), gli embedding normalizzati per unità hanno similarità a coppie più basse; una soglia più lasca ($\theta \le 0.90$) è ottimale, poiché soglie rigide non riescono a collegare i quasi-duplicati.
  • La soglia ottimale è prevedibile dalle statistiche degli embedding (p90 a coppie e frazione di componenti miste del pavimento di catena).
• Trasferimento nel Mondo Reale:
  • Il meccanismo si trasferisce a pipeline con caratteristiche congelate (ResNet-18, MiniLM) senza accesso all'oracolo, confermandone la fattibilità pratica.
  • Gli attacchi di pura divisione (dati disgiunti senza sovrapposizione) rimangono indifesi dalle sole prove di similarità, richiedendo provenienza non a livello di esempio (ad esempio, collegamento dell'account, KYC).

5. Significato e Affermazioni

Il documento afferma che l'attribuzione equa dei dati secondo Shapley non è automaticamente compatibile con gli incentivi quando le identità sono endogene. Il significato del lavoro risiede in:

• Spostamento dell'Onere Strategico: Spostare l'unità di attribuzione dalle identità mutabili ai cluster supportati da prove consente un compromesso controllato tra equità in stile Shapley e resistenza agli Sybil.
• Possibilità Condizionale: Sebbene l'equità esatta secondo Shapley sia impossibile sotto manipolazioni illimitate, il meccanismo quoziente recupera un "compromesso controllato" quando i segnali di similarità e provenienza possono affidabilmente collassare le varianti manipolate nella stessa unità.
• Implementazione Pratica: Il meccanismo è "agnostico rispetto al semivalore", il che significa che può essere implementato con vari backend di valutazione (Shapley, Banzhaf, ecc.) ed è robusto al rumore degli stimatori.
• Complementarità: L'approccio completa il lavoro esistente sui "Valori di Shapley di Gruppo Fedeli" (che difendono contro l'aggregazione di società di comodo di dataset fissi) affrontando la costruzione dell'unità di attribuzione stessa quando il contenuto dei dati può essere alterato (duplicato, parafrasato, sintetizzato).

Gli autori concludono che l'unità di attribuzione è una scelta di progettazione di meccanismi, e il semivalore quoziente fornisce un quadro robusto per i mercati dei dati in cui i fornitori sono strategici.