Less Noise, Same Certificate: Retain Sensitivity for Unlearning

Deze paper introduceert het concept van 'retain sensitivity' om in plaats van de conservatieve differentieel-private gevoeligheid te gebruiken, waardoor er bij gecertificeerd machine unlearning minder ruis kan worden toegevoegd terwijl dezelfde certificaten worden behouden en de modelnuttigheid verbetert.

De kern

Stel je voor dat je een enorme, slimme kok hebt die een fantastisch gerecht (een AI-model) heeft bereid met duizenden ingrediënten (trainingsdata). Nu vraagt een klant: "Ik wil dat je die ene specifieke tomaat uit het recept verwijdert, want ik heb er allergie voor."

De traditionele manier om dit op te lossen? De hele keuken slopen, alle ingrediënten opnieuw sorteren en het gerecht vanaf nul opnieuw koken zonder die tomaat. Dit is eerlijk, maar het kost enorm veel tijd, energie en geld.

Deze paper introduceert een nieuwe, slimme manier om die "tomaat" te verwijderen zonder het hele gerecht opnieuw te maken. Ze noemen dit Certified Machine Unlearning (Gecertificeerd Vergeten van Machines), maar met een nieuwe twist: Retain Sensitivity (Retentie-Gevoeligheid).

Hier is de uitleg in simpele taal, met een paar creatieve metaforen:

1. Het oude probleem: De "Worst-Case" Paniek

Vroeger, als je wilde garanderen dat de tomaat echt weg was, keken de koks naar het slechtst mogelijke scenario. Ze dachten: "Wat als die tomaat de smaak van het hele gerecht totaal veranderde? Wat als het de enige was die het gerecht eetbaar maakte?"

Om zeker te zijn dat niemand kon raden of die tomaat erin zat of niet, voegden ze een enorme hoeveelheid zout toe aan het gerecht. Dit zout is in de AI-wereld ruis (noise).

• Het probleem: Dit zout maakt het gerecht vaak onsmakelijk (het model wordt minder nauwkeurig). Ze voegden te veel zout toe omdat ze bang waren voor het allerergste geval, zelfs als het in de praktijk zelden voorkomt.

2. Het nieuwe inzicht: Kijk naar wat er blijft

De auteurs van deze paper zeggen: "Wacht even! We hoeven niet te verbergen wat er in het gerecht zit, we hoeven alleen maar te verbergen dat die ene tomaat eruit is gehaald. De rest van de ingrediënten (de 'retain set') blijven immers gewoon staan!"

Stel je voor dat je een muur hebt gebouwd van duizend stenen. Je wilt één steen verwijderen.

• De oude methode: Je denkt: "Als ik die ene steen haal, kan de hele muur instorten!" Dus je voegt duizend extra steunen toe (ruis) om de muur veilig te houden.
• De nieuwe methode (Retain Sensitivity): Je kijkt naar de muur zonder die steen. Je ziet dat de muur eigenlijk heel stabiel is. De andere stenen houden elkaar goed vast. Je hoeft dus maar één klein steuntje toe te voegen om de stabiliteit te garanderen.

Dit is Retain Sensitivity: het meten van hoe erg het gerecht verandert als je alleen die ene tomaat verwijdert, terwijl je kijkt naar de specifieke combinatie van de andere duizenden ingrediënten die je wel houdt.

3. Waarom is dit zo slim?

Het grootste voordeel is dat je minder ruis nodig hebt.

• Minder ruis = Beter gerecht. Het model blijft nauwkeuriger en nuttiger.
• Hetzelfde certificaat. Je kunt nog steeds bewijzen (wiskundig garanderen) dat de tomaat weg is, maar dan zonder het gerecht te bederven met overbodig zout.

De paper toont dit aan bij verschillende "recepten":

• MST (Minimale Spanboom): Stel je een netwerk van wegen voor. Als je één weg verwijdert, verandert de kortste route misschien niet veel als er andere goede alternatieven zijn. De oude methode deed alsof de hele kaart instortte; de nieuwe methode kijkt naar de daadwerkelijke alternatieven.
• PCA (Gegevens comprimeren): Stel je voor dat je een foto inkleurt. Als je één pixel verwijdert, verandert de foto nauwelijks als de rest van de foto helder en duidelijk is.
• SVM & ERM (Leren van fouten): Als een model al heel goed is getraind op de resterende data, heeft het verwijderen van één fout voorbeeld weinig invloed. De "kracht" van de resterende data (de stabiliteit) zorgt ervoor dat je weinig extra ruis nodig hebt om het verschil te verbergen.

4. Twee manieren om te koken (Passief vs. Actief)

De paper bespreekt twee manieren om dit toe te passen:

1. Passief (De "Stille" Verwijdering): Je voegt direct een beetje zout toe aan het originele gerecht en zegt: "Hier is het, zonder tomaat." Met de nieuwe methode heb je veel minder zout nodig dan voorheen.
2. Actief (De "Bewuste" Aanpassing): Je past het recept eerst iets aan (bijvoorbeeld door de kruiden een beetje te herschikken) om de tomaat te compenseren, en voegt dan pas een heel klein beetje zout toe. De paper laat zien dat als je kijkt naar de stabiliteit van de resterende kruiden, je veel minder kruiden hoeft te herschikken en minder zout nodig hebt.

Conclusie

Kortom: Deze paper leert ons dat we niet hoeven te panikeren en alles "op de safe" moeten doen door het ergste scenario aan te nemen. In plaats daarvan kunnen we kijken naar de specifieke situatie van de data die we houden.

Als die data stabiel is (zoals een goed gebouwd muurtje of een goed bereid gerecht), dan is het verwijderen van één stukje data veel makkelijker en goedkoper dan we dachten. We hoeven minder "ruis" toe te voegen, waardoor de AI-modellen slimmer blijven en we toch kunnen voldoen aan de regels voor privacy en het recht om vergeten te worden.

In één zin: Je hoeft niet de hele kamer te verduisteren om te verbergen dat je één kaars hebt uitgedoofd; je kunt gewoon kijken hoe het licht van de andere kaarsen het donker opvangt.

Technische samenvatting

1. Probleemstelling

Machine learning-modellen worden steeds vaker ingezet in omgevingen waar trainingdata later moet worden verwijderd, bijvoorbeeld vanwege het recht op vergetelheid (GDPR), het verwijderen van vergiftigde data, of auteursrechtelijke schendingen. De "gouden standaard" voor het verwijderen van data is het volledig hertrainen van het model op de resterende dataset ($R = S \setminus U$, waarbij $S$ de originele dataset is en $U$ de te verwijderen set). Dit is echter vaak computationeel onhaalbaar.

Certified Machine Unlearning (Gecertificeerd Machine Vergeten) biedt een oplossing: het doel is om een model te produceren dat statistisch ononderscheidbaar is van een hertraind model, maar dit te doen met veel minder rekenkracht. Bestaande methoden baseren zich vaak op Differential Privacy (DP). Ze voegen ruis toe die is gekalibreerd op de globale gevoeligheid (Global Sensitivity, GS). Globale gevoeligheid meet de maximale verandering in output tussen twee datasets die slechts één datapunt verschillen, over alle mogelijke datasets.

Het artikel stelt dat deze DP-benadering voor unlearning vaak te conservatief is. DP vereist bescherming tegen het onderscheiden van elk paar buren datasets. Bij unlearning is de situatie echter anders: de "retained set" ($R$) is vast en bekend. We hoeven alleen de invloed van de verwijderde set $U$ te verbergen, niet de eigenschappen van $R$ zelf. De huidige methoden voegen daarom vaak onnodig veel ruis toe, wat de bruikbaarheid (utility) van het model vermindert.

2. Methodologie: Retain Sensitivity

De kern van het artikel is de introductie van een nieuw concept: Retain Sensitivity (RS).

• Definitie: Retain Sensitivity ($RS_f(R)$) is de maximale verandering in de output van een algoritme wanneer er één punt wordt toegevoegd aan een vastgehouden dataset $R$. Formeel:
  $$RS_f(R) = \max_{Z \subseteq \mathcal{Z}, |Z|=1} \|f(R \cup Z) - f(R)\|$$
• Verschil met Global Sensitivity (GS):
  • GS kijkt naar het worst-case scenario over alle mogelijke datasets $S$ en $S'$.
  • RS kijkt specifiek naar de stabiliteit rondom de reeds bekende dataset $R$.
  • Omdat $R$ vaststaat, is de RS altijd kleiner dan of gelijk aan de GS ($RS \leq GS$). In veel gevallen is $RS$ aanzienlijk kleiner omdat de dataset $R$ vaak goed geconditioneerd is (bijv. grote marges, goede eigengaps), waardoor het toevoegen van één nieuw punt de output weinig verandert.
• Theoretische Basis: Het artikel bewijst dat het kalibreren van ruis op basis van $RS(R)$ (in plaats van $GS$) voldoende is om een $(\varepsilon, \delta)$-unlearning garantie te bieden. Omdat beide scenario's (verwijdering vs. hertraining) conditioneren op dezelfde $R$, kan dezelfde ruisverdeling worden gebruikt zonder dat de privacy van $R$ wordt geëxploiteerd.

3. Belangrijkste Bijdragen

1. Formele Definitie en Garantie: De auteurs definiëren Retain Sensitivity formeel en bewijzen dat het een voldoende (en in sommige gevallen noodzakelijke) maatstaf is voor het kalibreren van ruis in zowel passieve (alleen ruis toevoegen) als actieve (model update + ruis) unlearning algoritmen.
2. Theoretische Analyse van Standaard Problemen: Ze leiden RS-bounds af voor fundamentele problemen:
   • Mediaan: RS hangt af van de lokale afstand tussen waarden rond de mediaan, niet van het domein.
   • Minimum Spanning Tree (MST): RS wordt bepaald door de zwaarste "bottleneck" in de resterende graaf, wat vaak veel lager is dan de globale grens.
   • PCA (Principal Component Analysis): RS hangt af van de eigengap (het verschil tussen eigenwaarden) in de resterende dataset. Een grote eigengap leidt tot zeer lage RS.
   • SVM en ERM (Empirical Risk Minimization): RS wordt bepaald door de kromming (curvature) en de empirische sterkte van de convexiteit van de resterende dataset, in plaats van een globale ondergrens.
3. Verbetering van Bestaande Algoritmen: De auteurs passen twee populaire actieve unlearning-algoritmen toe met RS:
   • Descent-to-Delete: Door gebruik te maken van de data-afhankelijke conditienummer van $R$ in plaats van een globale schatting, kan het algoritme minder iteraties uitvoeren om dezelfde garantie te bereiken.
   • Newton Update: Door de kromming van de Hessian op $R$ te gebruiken, wordt de benodigde ruis verkleind met een factor die kubisch afhangt van de verhouding tussen globale en lokale kromming.

4. Resultaten

De auteurs valideren hun theorie zowel theoretisch als empirisch:

• Passief Unlearning: In experimenten met mediaan, MST, PCA, SVM en ERM tonen ze aan dat de verhouding $RS/GS$ vaak orders of magnitude kleiner is dan 1.
  • Bijvoorbeeld, bij SVM's met een grote marge of ERM met een kleine regularisatieparameter ($\lambda$), kan de benodigde ruis drastisch worden verminderd.
  • Voor PCA met een goede eigengap is de ruisvermindering aanzienlijk, terwijl naive DP-methoden hier vaak onbruikbare ruis zouden toevoegen.
• Actief Unlearning:
  • Voor Descent-to-Delete laten ze zien dat het aantal benodigde gradient-steps om de unlearning-garantie te halen, exponentieel daalt wanneer de data-afhankelijke conditienummer wordt gebruikt.
  • Voor de Newton Update wordt de ruisvermindering nog groter (kubisch effect).
  • In experimenten met MNIST en ACSIncome datasets blijkt dat modellen die gebruikmaken van RS-calibratie een vergelijkbare nauwkeurigheid behalen als exacte hertraining, maar met veel minder ruis dan modellen die op GS zijn gebaseerd.

5. Betekenis en Conclusie

Dit artikel biedt een fundamenteel nieuw perspectief op machine unlearning door de scheidslijn tussen Differential Privacy en Unlearning scherper te trekken:

• DP moet de aanwezigheid van elk individueel punt verbergen (worst-case over alle datasets).
• Unlearning moet alleen de invloed van de verwijderde punten verbergen, terwijl de resterende data ($R$) bekend en vaststaat.

De conclusie is dat het gebruik van Retain Sensitivity leidt tot een aanzienlijke verbetering in de bruikbaarheid (utility) van gecertificeerde unlearning-systemen zonder in te leveren op de privacy-garanties. Dit maakt gecertificeerd vergeten veel praktischer voor real-world toepassingen, vooral in scenario's waar de resterende dataset goed geconditioneerd is. De auteurs benadrukken dat de volgende stap het ontwikkelen van efficiënte methoden is om deze data-afhankelijke statistieken (zoals lokale kromming of eigengaps) snel te berekenen zonder volledige hertraining.