Machine Unlearning

13 min readDec 20, 2023

Introduction

Dans cet article nous partageons le concept de machine unlearning en commençant par sa définition et les défis qui en découlent. Nous détaillons ensuite les différentes approches existantes ainsi que les méthodes permettant d’évaluer ces approches et de vérifier l’oubli des données.

Définition du problème

Le Machine Unlearning désigne le processus de suppression ou de désapprentissage des connaissances acquises par un modèle de Machine Learning (ML). Lors de la phase d’entraînement, le modèle apprend à partir du jeu de données pour effectuer une tâche spécifique, comme de la classification ou de la prédiction. Le désapprentissage, ou Unlearning, est donc le processus inverse, où l’on tente de supprimer ou d’oublier les informations apprises par le modèle.

La volonté de désapprentissage peut apparaître dans différents scénarios :

Sécurité : Dans le cas d’une attaque adversaire, il est possible de donner au modèle une donnée fortement similaire à une donnée d’entraînement afin d’obtenir une réponse erronée de la part du modèle. On peut modifier ce comportement en oubliant la donnée problématique
Vie privée : Le RGPD stipule qu’un utilisateur peut demander à tout moment le retrait de ses informations afin de protéger sa vie privée.
Performances: Certaines données du jeu d’entraînement peuvent affecter les performances d’un modèle.
Obsolescence : Des données sont devenues obsolètes et il faut les retirer du jeu de données.

Supprimer définitivement des données du jeu d’entraînement nécessite de ré-entraîner le modèle sur un nouveau jeu de données qui exclut les informations à oublier. Cependant, il est important de noter que l’entraînement d’un modèle peut être extrêmement coûteux, comme en témoigne le coût estimé de plus de 4 millions de dollars pour entraîner GPT-3. Par conséquent, l’objectif du Machine Unlearning est de mettre en place un algorithme permettant d’effacer les données indésirables tout en évitant les dépenses substantielles associées au ré-entraînement complet du modèle.

Notations et définitions mathématiques

Notations : Notations utilisées par la suite pour simplifier la lecture.

D : Dataset d’origine → Jeu d’entraînement d’origine
Df : Data to forget → Les données à oublier
Dr : Data remaining → Les données restantes D\Df
A(D) : ML Model → Modèle de ML entraîné sur D
U (D, Df, A(D)) : Unlearned Model → modèle de ML après désapprentissage, fonction de :

Jeu de donnée d’origine D

Données à oublier Df
Modèle d’origine A(D)
R : Retrained Model → modèle ré-entraîné depuis 0 à partir de Dr

Définitions :

Exact Unlearning : On parle de désapprentissage exacte (Exact Unlearning) lorsque le processus de désapprentissage assure un oubli total de la donnée en question. Cela veut dire que l’algorithme de désapprentissage produit un modèle U dont la sortie est identique à celle du modèle R. On peut le formuler mathématiquement par :

*D : Dataset | Df : Dataset à oublier | A(D) : le modèle | U : Unlearned model | Pr(A(D)) : La distribution du modèle A | T : Un ensemble d’hypothèses*

Approximate Unlearning : Comme on peut s’en douter, c’est lorsque le désapprentissage n’est pas exact, mais qu’il produit un modèle U dont la sortie est proche de celle du modèle R. On dit alors que l’algorithme de désapprentissage effectue un oubli des données certifié au degré ε si :

*z : la donnée à oublier, T : un ensemble d’Hypothèses | ε : facteur d’oubli*

Les défis

Comme on peut s’en douter le Machine Unlearning fait face à plusieurs défis de taille :

Le caractère aléatoire de l’entraînement des modèles de ML signifie que l’on ne peut connaître l’impact exact qu’a une donnée sur ce dernier. L’oubli de certaines données peut alors entraîner un phénomène souvent appelé désapprentissage catastrophique, résultant en une diminution significative des performances du modèle.
Le caractère incrémental de l’entraînement implique que l’état du modèle à une étape n dépend de son état à l’étape n-1. On ne peut donc pas tout simplement supprimer l’étape de l’entraînement correspondant à la donnée que l’on souhaite effacer.

Schéma de fonctionnement

Une demande de désapprentissage sur un modèle de ML suit généralement le schéma suivant :

Demande d’oubli de donnée (Removal request) : On reçoit une demande d’oubli d’une donnée ou d’un ensemble de données pouvant prendre différentes formes (explicitées dans la partie suivante).
Algorithme de désapprentissage : (Unlearning Algorithm) : On applique l’algorithme de désapprentissage devant remplir certains critères (également explicité dans la partie suivante).
Evaluation : (Evaluation Metrics) : On évalue les performances du modèle suivant différentes métriques.
Vérification : (Verification) : On s’assure que le modèle a bien oublié les données en question avec différents tests.

Demande d’oubli et exigences

Les demandes d’oubli

Les demandes d’oubli peuvent prendre différentes formes selon la nature de la demande et du modèle en question

Retrait d’une donnée : On souhaite simplement retirer une donnée spécifique du jeu de d’entraînement.
Retrait d’une Feature : On peut souhaiter retirer toute une feature du jeu d’entraînement. ex : COMPAS un modèle utilisé par les tribunaux américains a plus de chance d’assigner un score de risque important au personnes noires qu’à une personne caucasienne. Dans ce cas il peut être intéressant de retirer la feature contenant l’ethnicité de la personne.
Retrait d’une classe : On souhaite retirer une donnée qui forme une classe. ex : Dans le cadre d’un algorithme de reconnaissance faciale, le visage d’un individus (yeux, nez, bouche, …) correspond à une classe pour le modèle.
Retrait d’une tâche : Certains modèles sont entraînés à réaliser plusieurs tâches similaires (parfois parce que le jeu de données d’une seule tâche n’est pas suffisant). Cette mission est particulièrement complexe, Liu et al. [2] ont montré l’importance de spécifier avant la création du modèle quelles tâches risquent d’être oubliées et lesquelles resteront définitivement.
Retrait (non) adaptatif: Lorsque les demandes de retrait s’accumulent au point de former un flux, deux options sont possibles :
— L’oubli (ou non) de la donnée n dépend de l’état du modèle après l’oubli de la donnée n-1 (adaptatif)
— Chaque donnée à oublier provoque l’exécution de l’algorithme de désapprentissage, peu importe l’état du modèle (non adaptatif).

Les exigences

Un modèle de désapprentissage doit remplir certains critères afin de pouvoir être considéré utilisable.

Complétude : U devrait produire les même prédictions que R, que celles-ci soient correctes ou non.
Précision (Accuracy) : Le désapprentissage ne doit pas affecter les performances du modèle sur les données restantes. U doit donc avoir une accuracy proche de celle du modèle d’origine.
Rapidité : L’objectif du désapprentissage est de gagner du temps sur le ré-entraînement. Il peut parfois être plus intéressant de ré-entraîner si les demandes sont trop nombreuses.
Légèreté : Le désapprentissage peut impliquer de sauvegarder des informations supplémentaires (poids du modèle à une étape n par exemple). Il faut donc s’assurer de limiter le stockage additionnel.
Garantie d’oubli : Dans l’idéal un modèle de désapprentissage fourni une preuve/garantie de l’oubli de la donnée en question.

Les différentes approches de désapprentissage

Les techniques de ML étant nombreuses, il existe différentes approches pour leur désapprentissage. Dans cette partie nous allons d’abord étudier quelques exemples de désapprentissage agnostique (s’adaptant à plusieurs types de modèles), intrinsèque (spécifique à un type de modèle de ML) et orienté données.

Approche Agnostique

Les approches Agnostiques visent à définir un algorithme de désapprentissage applicable à plusieurs types de modèle de ML. Dans cette partie nous allons présenter quelques exemples d’approches agnostiques.

Adaptation de connaissances : Chudawat et al. [3] ont mis en place 3 modèles : Smart Teacher, Dumb Teacher et Student. Le Smart Teacher a été pré-entraîné sur le jeu de donnée complet tandis que le Dumb Teacher produit des prédiction aléatoires. Le Student est initialisé avec les poids du Smart Teacher et lors de la phase d’entraînement, il doit imiter la sortie de ce dernier pour les données que l’on souhaite conserver (Dr). A l’inverse, il doit imiter le Dumb Teacher pour les données à oublier (Df). Une fois l’entraînement terminé, le Student devient le modèle mis en production et sera le Smart Teacher d’un nouveau Student à la prochaine demande d’oubli.

Mécanisme de retrait certifié : Ici l’objectif est de rajouter du bruit aux poids du modèle d’origine dans l’objectif d’affecter la capacité de classification du modèle sur Df. Ajouter du bruit ne permet pas pour autant d’assurer l’oubli, mais on peut produire une certification d’oubli à un certain degré en se basant sur la définition de la confidentialité différentielle. Ce mécanisme fonctionne pour différents types de modèles comme la régression linéaire et a été mis en application par Golatkar et al. [4] sur des réseaux de neurones.

Résultats : La précision est proche de celle du modèle ré-entraîné avec un gain de temps important. Les performances restent cependant limitées par la taille du modèle en question car il faut calculer une approximation de la matrice Hessienne (ce qui peut être très coûteux si le modèle a beaucoup de poids).

Approche intrinsèque

Les approches intrinsèques ont pour objectif de concevoir des solutions adaptées à un type de modèle particulier. Cependant, il est important de noter que leur applicabilité ne se limite pas strictement à ce modèle spécifique, mais peut s’étendre également à d’autres modèles partageant des caractéristiques similaires.

Modèles linéaires : Les solutions pour les modèles linéaires se concentrent majoritairement sur les fonctions d’influence [5]. Il s’agit donc de déterminer l’influence qu’a eu Df sur le modèle afin de pouvoir “inverser” cet effet. Pour cela on utilise la matrice Hessienne de la loss function (calcul en O(d2) avec d la dimension des données d’entrée) afin d’obtenir une approximation des poids qu’aurait eu le modèle R.

Résultats : Ces techniques fonctionnent plutôt bien mais sont limité par les coûts de calculs de la matrice Hessienne.

Modèles arborescent : Une bonne solution [6] consiste à estimer la robustesse des noeuds de l’arbre. On dit qu’un noeud est k-robuste si son split n’est pas inversé après k retraits.

→ On met donc les noeuds les plus robustes en haut de l’arbre et les moins robustes en bas en stockant en mémoire les sous-arbres alternatifs avec le gain (Gini Impurity) inférieur le plus proche. De cette façon, le retrait d’une ou d’un ensemble de donnée n’affectera que les noeuds en bas de l’arbre et impliquera de remplacer le noeud affecté par son alternatif (voir schéma ci-dessous).

Schéma du désapprentissage pour structure arborescente tiré de [6]

Résultats : Le seul inconvénient de cette méthode est que si le modèle reçoit beaucoup de demandes d’oubli, les noeuds peuvent tous perdre en robustesse et on se retrouve alors à devoir stocker un grand nombre de sous-arbres alternatifs.

Réseaux de neurones : La majorité des solutions reposent sur des fonctions d’influence dont le but est de déterminer l’impact qu’a une donnée sur l’entraînement du modèle. Par exemple, si les couches sont convexes, on peut appliquer le mécanisme de certification de retrait (limité par le coût de calcul de la matrice Hessienne). Le coût de calcul de la matrice Hessienne pouvant devenir important certaines recherches comme celles de Golatkar et al. [4] visent à en faire une approximation à partir de la matrice d’information de Fisher. Ces recherches sont probablement les plus prometteuses pour le Machine Unlearning dans le domaine des réseaux de neurones.

Résultats : Dans l’ensemble, ces méthodes produisent des résultats assez satisfaisants, mais elles sont entravées par la complexité élevée du calcul de la matrice Hessienne. Les techniques d’approximation offrent une solution pour atténuer cette limitation, bien qu’elles puissent parfois compromettre la précision.

Approche orientée données

Les approches orientées données ont pour objectif de se concentrer plutôt sur l’architecture du jeu de donnée que sur le modèle lui même. Une solution référence qui a donnée naissance à beaucoup d’autres solutions orientées données est le SISA training [7].

SISA Training [7] a pour vocation première d’accélérer le processus de désapprentissage en restreignant l’impact d’une donnée pendant la phase d’entraînement.

L’idée sous-jacente à cette approche consiste à diviser le jeu de données d’entraînement en plusieurs fragments distincts, de sorte qu’un point de données ne figure que dans un seul fragment. Chaque fragment est ensuite utilisé pour entraîner un sous-modèle. Cette stratégie présente l’avantage de ne nécessiter la révision que du sous-modèle associé à la donnée à retirer, plutôt que de ré-entraîner l’ensemble du modèle.

De plus, un partitionnement supplémentaire des fragments peut être envisagé, permettant de conserver en mémoire les valeurs des poids pour chaque partition. Ainsi, lorsqu’une donnée est retirée, il devient possible de récupérer les valeurs des poids correspondant à la partition précédente.

Enfin la dernière étape consiste en l’agrégation entre les sous-modèles pour la classification.

Dans le SISA training, la fragmentation du jeu de donnée et le partitionnement des fragments sont réalisés de manière aléatoire, cependant Zeng et al sont parvenus à de meilleurs résultats avec un ajout de contexte aux données couplé à un système d’attention pour l’agrégation des modèles.

Résultats : Le SISA training produit de bons résultats et permet en plus de cela de faire de l’exact unlearning. Il est cependant limité par la taille du dataset qui, si trop petit, peut résulter en des modèles sous-entraînés (weak learners).

La confidentialité différentielle (Differential Privacy) appliquée au machine Unlearning permet d’encadrer l’influence que peut avoir une donnée sur l’apprentissage du modèle. Concrètement, on n’initie la procédure de désapprentissage que lorsque la confidentialité différentielle atteint ou dépasse un seuil préalablement défini, noté ε. Cette notion peut être formulée à l’aide de l’équation suivante :

Cette approche ne constitue pas une forme directe de Machine Unlearning, mais elle offre plutôt la possibilité de déclencher un processus de désapprentissage lorsque cela est jugé nécessaire. Elle permet ainsi d’implémenter une forme de désapprentissage adaptatif.

L’augmentation des données constitue également une stratégie efficace pour aborder le désapprentissage. Dans ce cadre, l’approche consiste à augmenter la quantité de données disponibles, puis à fixer le coefficient d’apprentissage à zéro pour les données spécifiques qui sont confidentielles ou privées. Il est essentiel de noter que cette solution doit être implémentée avant même le début de l’entraînement du modèle. En réalité, cette approche ne relève pas du désapprentissage à proprement parler, mais plutôt de la prévention de la divulgation de données sensibles tout au long du processus d’apprentissage.

Evaluation

Après que le modèle a été soumis au processus de désapprentissage, il est impératif d’évaluer ses performances pour garantir qu’il satisfait aux critères précédemment énoncés. Dans cet objectif, on va utiliser différentes métriques pour évaluer les performances du modèle. Ci-dessous, quelques exemples de métriques couramment utilisées avec les articles qui les définissent/introduisent.

Formule du ZRF score:

M : modèle après désapprentissage | Td : modèle aléatoire | xi : le ième échantillon de Df | nf : le nombre total d’échantillons dans Df| *JS()* : Divergence de Jensen-Shannon

Vérification

Enfin, pour conclure, il est essentiel de vérifier que le modèle a effectivement oublié les données en question. À cet égard, plusieurs méthodes sont disponibles :

Feature Injection : On rajoute une feature à toutes les données de D. Pour cette nouvelle feature, les données de Df ont une forte corrélation tandis que celle pour les données de Dr est nulle. Une fois le désapprentissage terminé, les poids associés à cette feature devraient être devenus nuls (ou presque).
→ Le problème de cette méthode est qu’elle ne fonctionne qu’avec les modèles linéaires ou logistiques car leur poids sont facilement interprétables. De plus elle implique d’ajouter une feature au modèle.
Mesure de l’oubli : On dit qu’un algorithme a 𝛼-forget une donnée d’entraînement si une série d’attaques sur la confidentialité a un taux de succès 𝛼.
Attaque par inférence d’appartenance : On peut vérifier l’oubli d’une donnée en effectuant une attaque par inférence d’appartenance sur la donnée en question. En pratique c’est la méthode la plus utilisée pour s’assurer de l’oubli des données.
Interclass confusion test : Dans le jeu de données d’entraînement, cette approche consiste à prendre un ensemble de données comprenant différentes classes, puis à procéder à un échange aléatoire des labels. On demande alors l’oubli de ces classes mal labellisées, l’objectif étant d’obtenir un modèle amélioré par rapport à celui d’origine.

Conclusion

Le Machine Unlearning en son essence peut à première vue paraître paradoxal : faire oublier à un modèle ce qu’on s’est efforcé à lui apprendre. Cependant ses domaines d’applications ne cessent de s’étendre et son intérêt en résulte grandissant. Pour preuve, Google a lancé un concours Kaggle (sept. 2023) afin d’approfondir les recherches dans le domaine et pousser son développement en vue de présenter les avancées les plus significatives à la conférence NeurIPS, justifiant ainsi l’importance de s’intéresser de près au Machine Unlearning.

Bien que les solutions soient nombreuses, aucune actuellement publiée ne semble faire l’unanimité et de surcroît aucune ne semble idéalement applicable à tout type de modèle de ML.

Certaines semblent cependant prometteuses, plus particulièrement dans le cas des réseaux de neurones : l’utilisation des matrice Hessiennes et de leur approximation par matrice d’information de Fisher pourraient donner naissance à des désapprentissage efficaces à coûts réduits.

Sources :

[1] A Survey of Machine Unlearning, Thanh Tam Nguyen1 et al.; sept. 2022

[2] Continual learning and private unlearning, Bo Liu et al.; mars 2022

[3] Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks Using an Incompetent Teacher, Chundawat et al.; mai 2022

[4] Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks, Golatkar et al.; nov. 2019

[5] Approximate Data Deletion from Machine Learning Models, Izzo et al.; 2021

[6] HedgeCut: Maintaining Randomised Trees for Low-Latency Machine Unlearning, Shelter et al.; 2021

[7] Machine Unlearning, Bourtoule et al.; dec. 2019

[8] Towards Making Systems Forget with Machine Unlearning, Yinzhi Cao et Junfeng Yang; 2015

[9] Fast Yet Effective Machine Unlearning, Tarun et al.; nov. 2021

Remerciement

Merci à nos collègues Beatrice CHETARD, Lu WANG et Jean-Baptiste BARDIN pour la revue de l’article.

A propos de l’auteur

Alex Dufour a rejoint La Javaness en tant que Stagiaire en Septembre 2023 dans le cadre de son projet de fin d’étude. Pendant son stage, il s’intéressa particulièrement au sujet de la robustesse des modèles IA et des problématique de désapprentissage.