Technische Samenvatting: Constraint-Data-Value-Maximization voor Effectieve Data-Pruning in Omgevingen met Beperkte Data

1. Probleemstelling

Machine learning-modellen, en met name grote taalmodellen, staan voor een onverzadigbare vraag naar data, terwijl de beschikbaarheid van data stagneert. Methoden voor datawaardering beogen de invloed van individuele trainingsinstanties op de modelprestaties toe te schrijven om de datasetgrootte te verkleinen, waardoor energie wordt bespaard en de trainingsefficiëntie wordt verbeterd. Echter, bestaande benaderingen voor data pruning (het verwijderen van data met lage waarde) lijden onder kritieke beperkingen, vooral in omgevingen met beperkte data waar slechts een klein deel van de dataset overblijft.

De auteurs identificeren drie primaire tekortkomingen in huidige state-of-the-art methoden (specifiek Shapley- en Banzhaf-waarde-gebaseerde benaderingen):

1. Cluster-grootte bias: Shapley- en Banzhaf-waarden verdelen de totale bruikbaarheid van een cluster onder zijn leden. Bijgevolg krijgen punten in grotere dataclusters kleinere marginale waarden dan punten in kleinere clusters. Dit leidt tot de voortijdige verwijdering van hele grote clusters, wat scherpe dalingen in modelprestaties veroorzaakt zodra de laatste vertegenwoordiger van een cluster wordt verwijderd.
2. Redundantie bias: Leave-One-Out (LOO) methoden wijzen vaak een waarde van nul toe aan redundante steekproeven, waardoor ze niet onderscheid maken tussen de bruikbaarheid van het behouden van één vertegenwoordiger versus vele.
3. Niet-geneste optimale subsets: De subset van data die de nauwkeurigheid maximaliseert voor een specifiek behoudsbudget (bijvoorbeeld 10%) is niet noodzakelijk een subset van de optimale set voor een ander budget (bijvoorbeeld 5%). Standaard pruningstrategieën die genesteheid veronderstellen, falen in het aanpassen aan deze budget-specifieke optima.

2. Methodologie: Constraint-Data-Value-Maximization (CDVM)

Om deze beperkingen aan te pakken, stellen de auteurs Constraint-Data-Value-Maximization (CDVM) voor, een op optimalisatie gebaseerd kader dat data pruning behandelt als een geconstrueerd optimalisatieprobleem over een data-attributiematrix.

Kernconcepten

• Data Attributiematrix ($T$): In tegenstelling tot scalair datawaarden, maakt CDVM gebruik van een matrix $T \in \mathbb{R}^{n \times m}$ waarbij $n$ het aantal trainingsinstanties is en $m$ het aantal testinstanties. De entiteit $T_{i,j}$ kwantificeert de invloed van trainingsinstantie $i$ op de voorspelling van testinstantie $j$. Deze matrix wordt geschat met behulp van het Maximum Sample Reuse (MSR) principe, waarbij modellen worden getraind op gestrekte subsets om invloed te benaderen zonder volledige hertraining voor elke instantie.
• Optimalisatieformulering: CDVM formuleert pruning als het selecteren van een binaire vector $w \in \{0, 1\}^n$ (aangevend welke $S$ trainingsinstanties behouden moeten blijven) om een bruikbaarheidsfunctie te maximaliseren onderworpen aan constrenties.
  • Doel: Maximaliseer de totale invloed op teststeekproeven terwijl excessieve concentratie van invloed op enkele teststeekproeven wordt bestraft.
  • Constrentie: Het aantal behouden instanties moet gelijk zijn aan het budget $S$.
  • Slackvariabelen: Om het "winner-take-all"-scenario te voorkomen waarbij enkele teststeekproeven de bruikbaarheid domineren, introduceert de methode slackvariabelen $t_j$ die de invloed per teststeekproef begrenzen op een drempelwaarde $\kappa$. Elke invloed die $\kappa$ overschrijdt, wordt bestraft.

Het formele optimalisatieprobleem is:
$$\begin{aligned} \max_{w, t} \quad & \alpha \sum_{j=1}^m v_j - (1-\alpha) \sum_{j=1}^m t_j \\ \text{s.t.} \quad & v = T^\top w \\ & \sum_{i=1}^n w_i = S \\ & t_j \ge 0, \quad t_j \ge v_j - \kappa \\ & w_i \in \{0, 1\} \end{aligned}$$
waarbij $v_j$ de gegenereerde bruikbaarheid is voor teststeekproef $j$, en $\alpha$ de totale bruikbaarheid afweegt tegen de straf voor het overschrijden van de drempel.

Implementatie

De auteurs verzwakken de binaire constrentie $w_i \in \{0, 1\}$ naar $w_i \in [0, 1]$ om het probleem op te lossen als een Mixed-Integer Linear Program (MILP) met behulp van het Disciplined Parametrized Programming-kader. Na het oplossen worden de top-$S$ entiteiten van $w$ behouden. Deze aanpak zorgt voor gebalanceerde dekking, waarbij gegarandeerd wordt dat geen enkele teststeekproef (en dus geen enkele impliciete datacluster) met nul totale invloed wordt achtergelaten zolang het budget dit toelaat.

3. Belangrijkste Bijdragen

Het artikel levert vier primaire bijdragen:

1. Analyse van bestaande beperkingen: De auteurs tonen theoretisch en empirisch aan dat Shapley- en Banzhaf-attributies kleinere marginale bijdragen toekennen aan instanties in grotere dataclusters, wat leidt tot onbalans in verwijderingspatronen en suboptimale pruningprestaties in regimes met beperkte data.
2. Inzicht in budget-specifiteit: Zij tonen aan dat optimale behoudsets budget-specifiek zijn; de subset die de nauwkeurigheid maximaliseert voor één behoudsniveau bevat niet noodzakelijk de subset die is geoptimaliseerd voor een ander.
3. CDVM-algoritme: De introductie van CDVM, dat pruning als een optimalisatie over een attributiematrix beschouwt, en redundantie- en cluster-grootte bias expliciet aanpakt door gebalanceerde invloed over teststeekproeven af te dwingen.
4. Benchmarking: Uitgebreide evaluatie op zes datasets van de OpenDataVal-benchmark, waarbij sterke prestaties en concurrerende runtime worden aangetoond vergeleken met state-of-the-art technieken.

4. Experimentele Resultaten

De auteurs evalueerden CDVM op zes datasets van de OpenDataVal-benchmark (waaronder CIFAR-10, Adult, IMDB, BBC, Pol en Nomao) over behoudsniveaus van 5% tot 30%.

• Prestaties: CDVM behaalde state-of-the-art prestaties in 28 van de 36 configuraties (6 datasets $\times$ 6 pruningpercentages). Het presteerde consequent beter dan willekeurige verwijdering, DataBanzhaf en DataOob/Memorization-methoden.
• Vergelijking met Invloedsoptimalisatie: Hoewel de Invloedsoptimalisatiemethode (Yang et al., 2023) concurrerend presteerde op sommige datasets (met name Nomao), was CDVM de enige methode die consistent willekeurige baselines versloeg over alle zes benchmarks wanneer hyperparameters adequaat werden afgestemd.
• Runtime-efficiëntie: CDVM biedt een superieure snelheid-nauwkeurigheidsafweging. Hoewel het berekenen van de attributiematrix $T$ de primaire bottleneck is (gedeeld door alle semi-waarde-gebaseerde methoden), is de optimalisatiestap snel. CDVM met 5.000 modellen behaalde resultaten die vergelijkbaar waren met of beter waren dan methoden die 10.000 modellen vereisen, met aanzienlijk lagere optimalisatietijd dan Invloedsoptimalisatie (die Hessiaan-inversie vereist).
• Robuustheid: De methode is robuust tegenover keuzes van hyperparameters. Een standaardconfiguratie ($\alpha=0.5$, $\kappa$ afgeleid van datasetstatistieken) presteerde bijna even goed als via grid-search bepaalde parameters, zonder zoekoverhead.

5. Betekenis en Claims

Het artikel beweert dat CDVM een robuuste oplossing biedt voor data pruning in regimes met beperkte data, een scenario waar bestaande Shapley-gebaseerde methoden vaak falen vanwege hun inherente bias. Door over te stappen van scalair datawaarden naar een geconstrueerde optimalisatie over een attributiematrix, zorgt CDVM ervoor dat de resterende dataset een gebalanceerde dekking van de testverdeling behoudt.

De auteurs benadrukken dat hun bevindingen "aanzienlijke ruimte voor verbetering van data pruning" aantonen, wat direct vertaalt naar verlaagde trainingkosten en energieverbruik. Zij merken op dat hoewel CDVM computationeel concurrerend is, de primaire bottleneck blijft het berekenen en opslaan van de attributiematrix $T$. Toekomstig werk zou efficiëntere attributieschatters kunnen verkennen of de sparsiteit van $T$ kunnen benutten om te schalen naar grotere datasets zoals ImageNet.

Het artikel concludeert dat CDVM effectief gebruik maakt van data-attributies om data met lage waarde te verwijderen zonder in te leveren op modelkwaliteit, en een praktisch alternatief biedt voor willekeurige selectie en bestaande waardering-gebaseerde pruningstrategieën.