Technische Samenvatting: NASH - Niet-lineaire Aggregatie van SHapley-informatieve componenten

Probleemstelling

Dataselectie heeft tot doel hoogwaardige subsets van trainingsdata te identificeren om de nuttigheid van het model (bijvoorbeeld validatie-accuraatheid $u_V$) te optimaliseren onder omvangbeperkingen. Hoewel Data Shapley en zijn generalisaties (semiwerten) theoretisch zijn onderbouwd door coöperatieve speltheorie om data-interacties in rekening te brengen, geven recente empirische studies aan dat ze in de praktijk vaak ineffectief presteren. Specifiek kan het selecteren van de top-$m$ datapunten op basis van Shapley-waarden die zijn berekend met betrekking tot complexe nuttigheidsfuncties (zoals validatie-accuraatheid), subsets opleveren die niet beter zijn dan, of zelfs slechter dan, willekeurige selectie.

Het artikel identificeert twee primaire redenen voor dit falen:

1. Gebrek aan Shapley-informativiteit: Complexe nuttigheidsfuncties omvatten meerdere distincte "rollen" (bijvoorbeeld verschillende klassen of subpopulaties in de validatieset). Een enkele Shapley-waarde voor een datapunt faalt in het vastleggen van zijn unieke sterkte over deze rollen heen. Bijgevolg kunnen data met verschillende sterktes identieke Shapley-scores ontvangen, wat leidt tot uitwisselbare behandeling ondanks hun verschillende bijdragen aan de nuttigheid.
2. Ongeschikte Aggregatie: Het ware doel (bijvoorbeeld validatie-accuraatheid) aggregateert prestaties over deze rollen niet-lineair. De standaard top-$m$ heuristiek vertrouwt echter op een lineaire aggregatie (het optellen van Shapley-waarden), wat faalt in het vastleggen van synergetische interacties waarbij de bijdrage van een datapunt afhangt van welke andere data al zijn geselecteerd (bijvoorbeeld: een datapunt is waardevoller als het een ondervertegenwoordigde rol dekt).

Methodologie: NASH Framework

De auteurs stellen NASH (Non-linear Aggregation of SHapley-informative components) voor, een framework dat de complexe nuttigheidsfunctie decomposeert in eenvoudigere componenten waar Shapley-waarden effectief zijn, en deze vervolgens niet-lineair aggregateert.

1. Shapley-informativiteit en Decompositie

Het artikel formaliseert Shapley-informativiteit als een eigenschap waarbij de som van Shapley-waarden voor een subset indicatief is voor zijn werkelijke nuttigheid. De auteurs bewijzen dat willekeurige nuttigheidsfuncties over het algemeen niet Shapley-informatief zijn. Zij tonen echter aan dat eenvoudigere nuttigheidsfuncties, specifiek voorspellingscorrectheid op een enkel validatiepunt ($u_v$), onder de aanname van "Consistent Player" (waarbij een datapunt consequent goed of slecht is voor een specifiek validatiepunt) bewezen Shapley-informatief zijn.

In plaats van Shapley-waarden te berekenen voor de geaggregeerde validatie-accuraatheid $u_V$, decomposeert NASH $u_V$ in individuele componenten $u_v$ voor elk validatiepunt $v \in V$. De Shapley-waarden $\phi_i(u_v)$ worden berekend voor deze eenvoudigere componenten. Opmerkelijk is dat het berekenen van deze vectoren geen extra runtimekosten met zich meebrengt in vergelijking met het berekenen van de Shapley-waarde voor de geaggregeerde $u_V$, aangezien $u_V$ simpelweg het gemiddelde is van $u_v$.

2. Niet-lineaire Aggregatie

Om het complexe doel te reconstrueren vanuit deze informatieve componenten, vermijdt NASH lineaire sommatie (wat de gebrekkige top-$m$ Shapley-heuristiek zou herstellen). In plaats daarvan optimaliseert het een niet-lineaire aggregatie doelstelling:
$$\max_{M \subseteq N, |M|=m} \sum_{v \in V} F_T(\hat{u}_v(M))$$
waarbij $\hat{u}_v(M) = \sum_{i \in M} \phi_i(u_v)$ de som is van Shapley-waarden voor component $v$, en $F_T$ een cumulatieve verdelingsfunctie (CDF) is die is geïnspireerd door leercursussen (bijvoorbeeld een exponentiële wet). Deze niet-lineaire functie zorgt ervoor dat het selectieproces prioriteit geeft aan data die helpen de "drempel" te overschrijden voor slecht voorspelde validatiepunten (ongedekte rollen), in plaats van hoge scores op te stapelen op reeds goed voorspelde punten.

3. Optimalisatie

De NASH-doelstelling wordt geoptimaliseerd met behulp van een gierige algoritme. De auteurs tonen aan dat wanneer Shapley-waarden niet-negatief zijn, de doelstelling monotoon submodulair is, wat een $(1 - 1/e)$ benadering garandeert. Zelfs met negatieve waarden (door ruis in de data) presteert het gierige algoritme empirisch goed, omdat de schadelijke data (die non-submodulariteit veroorzaken) op natuurlijke wijze worden gedeprioritiseerd. Het algoritme introduceert minimale extra runtimekosten, aangezien het zware werk (Shapley-benadering) wordt gedeeld met bestaande methoden.

Belangrijkste Bijdragen

1. Theoretische Analyse: Het artikel formaliseert de eigenschap Shapley-informativiteit en verklaart waarom complexe ML-nuttigheidsfuncties (zoals validatie-accuraatheid) falen om hieraan te voldoen, wat leidt tot de inconsistente prestaties van Data Shapley.
2. Bewezen Informatieve Componenten: De auteurs identificeren en bewijzen dat voorspellingscorrectheid op enkele validatiepunten dient als Shapley-informatieve componenten onder redelijke aannames.
3. NASH Framework: Een nieuw framework voor dataselectie dat complexe doelen decomposeert in Shapley-informatieve componenten en deze niet-lineair aggregateert om hoogwaardige subsets te selecteren.
4. Empirische Validatie: Uitgebreide experimenten op standaard datasets (logistische regressie, KNN) en grootschalige fine-tuning van taalmodellen (BERT, Llama-2) tonen aan dat NASH consequent beter presteert dan standaard Data Shapley, andere semi-waarden en willekeurige selectie.

Resultaten

• Algemene Dataselectie: In situaties zonder ingevoegde ruis (homogene kwaliteit) presteert standaard Data Shapley vaak niet beter dan willekeur. NASH verbetert de prestaties aanzienlijk in deze scenario's en overtreft consistent de basismethoden over verschillende selectieverhoudingen.
• Datasets met Heterogene Kwaliteit: In situaties met labelruis verbetert standaard Data Shapley (aangezien het slechte data kan onderscheiden), maar NASH presteert er nog steeds consequent beter dan. Dit suggereert dat de voordelen van NASH (het hanteren van rol-interacties) verschillend zijn van en complementair aan het vermogen van Data Shapley om ruis te filteren.
• Compatibiliteit: NASH is compatibel met diverse semi-waarden (bijvoorbeeld Beta Shapley, Data Banzhaf) en efficiënte benaderingsmethoden (bijvoorbeeld MC-sampling, FreeShap), en verbetert consequent hun selectieprestaties.
• Robuustheid: De methode is robuust tegen de keuze van de hyperparameter $\lambda$ in de aggregatiefunctie en werkt effectief met verschillende nuttigheidsfuncties (bijvoorbeeld validatieverlies, MSE).

Betekenis

Het artikel beweert dat NASH grotendeels de beperking elimineert dat Data Shapley/semi-waarden alleen effectief zijn op beperkte datasets of specifieke settings (bijvoorbeeld die met ingevoegde ruis). Door een framework te bieden dat Shapley-gebaseerde selectie consequent betrouwbaar en robuust maakt over diverse datasets en modelgroottes, stelt NASH de bredere adoptie van principiële methoden voor datavaluatie mogelijk. Deze vooruitgang ondersteunt toekomstig onderzoek in het verbeteren van benaderingsefficiëntie en dataselectie voor foundation-modellen, en zorgt ervoor dat de theoretische voordelen van Shapley-waarden (niet-mijpische interactie en billijkheid) in de praktijk worden verwezenlijkt.