![\"image\"](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/framework.png\")
\n\nComputer systems in today's digital landscape store vast amounts of personal data, facilitated by significant advancements in data storage and transfer technologies. The proliferation of data production, recording, and processing has skyrocketed, exemplified by the staggering number of daily YouTube video views, which exceeds four billion (Sari et al.\n2020). These online personal data encompass digital footprints left by internet users, reflecting their behaviors, interactions, and communication patterns in the real world (Nguyen et al, 2019). Additionally, personal data originates from various sources, including user-generated digital content such as product reviews, blog posts (e.g., Medium), social media status updates (e.g., Instagram), and knowledge sharing platforms (e.g., Wikipedia) (Nguyen et al. 2021). Furthermore, the scope of personal data has expanded to encompass information collected from wearable devices (Ren et al., 2022). While this abundance of data has propelled advancements in artificial intelligence (AI), it also poses threats to user privacy and has contributed to numerous data breaches(Cao and Yang, 2015). Consequently, some users may desire complete removal of their data from systems, particularly in sensitive domains like finance or healthcare (Ren et al., 2022). Recent regulations now mandate organizations to provide users with the \"right to be forgotten,\" granting them the ability to request the deletion of all or part of their data from a system (Dang et al., 2021).\n
\n\n\nAlthough complying with regulations by removing data from back-end databases is a step in the right direction, it falls short in the AI context due to the persistent ‘memory’ of old data by machine learning models. During the training phase of these models, millions, if not billions, of users data are processed. However, unlike humans who grasp general patterns, machine learning models tend to function more like lossy data compression mechanisms (Schelter, 2020), and some become overly specialized to their training data. Notably, the success of deep learning models has recently been attributed to the compression of training data (Tishby et al. 2000; Tishby and Zaslavsky 2015). The existence of this memorization behavior is further substantiated by studies on adversarial attacks, which have demonstrated the extraction of private information from trained models within specific target data (Z.\nRen, Baird, et al. 2020; Chang et al. 2022; Z. Ren, Han, et al.\n2020). However, it is important to recognize that the parameters of a trained model generally lack a clear connection to the data used for training (Shwartz-Ziv and Tishby 2017). Consequently, removing information associated with a particular data item from a machine learning model presents a challenge, making it difficult to ensure that the model forgets a user's data.\n
\n\n\nAddressing the challenge of enabling users to have the option and flexibility to completely delete their data from a machine learning model necessitates a novel approach known as machine unlearning (Q. P. Nguyen et al. 2022; Baumhauer, Schöttle, and Zeppelzauer 2020;\nTahiliani et al. 2021). Ideally, a machine unlearning mechanism would remove the data from the model without requiring a complete retraining process (Q. P. Nguyen et al. 2022). By adhering to users' right to be forgotten, this approach would protect the model owner from repetitive and costly retraining procedures.\n
\n\n\nResearchers have already initiated investigations into various aspects of machine unlearning, including the removal of specific training data and the subsequent analysis of model predictions (Q. P. Nguyen et al. 2022; Thudi, Jia, et al. 2022). However, it has become evident that this problem cannot be fully resolved due to the absence of standardized frameworks and resources (Villaronga,\nKieseberg, and Li 2018; Veale, Binns, and Edwards 2018; Shintre et al.\n2019; Schelter 2020). In order to lay the groundwork in this emerging field, we have undertaken a comprehensive survey of machine unlearning, encompassing its definitions, scenarios, mechanisms, and applications. Our survey findings and accompanying resources are publicly accessible at 1.\n
\n\nThere are various reasons why users might want to delete their data from a system. We can categorize these reasons into four main groups: security, privacy, usability, and fidelity. Each of these reasons is discussed in more detail below.
\n\nSecurity. Deep learning models have recently revealed vulnerabilities to external attacks, particularly adversarial attacks (K. Ren et al., 2020). In an adversarial attack, the attacker generates adversarial data that closely resembles the original data to the point where human perception cannot distinguish between the real and fake data. This adversarial data is purposely crafted to manipulate deep learning models, causing them to generate inaccurate predictions, often leading to significant consequences. For instance, in healthcare, an erroneous prediction could result in misdiagnosis, inappropriate treatment, or even loss of life. Therefore, it is imperative to detect and remove adversarial data to ensure the security of the model. Once an attack is identified, the model must be capable of deleting the adversarial data through a machine unlearning mechanism (Y. Cao and Yang 2015; Marchant, Rubinstein, and Alfeld 2022).
\n\nPrivacy. Numerous privacy-preserving regulations have recently been implemented, encompassing the right to be forgotten (Bourtoule et al., 2021; Dang, 2021), such as the General Data Protection Regulation (GDPR) of the European Union (Mantelero, 2013) and the California Consumer Privacy Act (Pardau, 2018). These regulations grant users the right to request the deletion of their data and related information in order to safeguard their privacy. Such legislation has emerged in response to instances of privacy breaches. For example, cloud systems can inadvertently expose user data due to multiple copies stored by various entities, backup policies, and replication strategies (A. Singh and Anand, 2017). In another scenario, machine learning techniques used in genetic data processing have been found to unintentionally disclose patients' genetic markers (Fredrikson et al., 2014; R. Wang et al., 2009). Hence, it is unsurprising that users seek to remove their data to mitigate the risks of data leaks (Y. Cao and Yang, 2015).
\n\nUsability. People have diverse preferences when it comes to online applications and services, particularly recommender systems. An application's recommendations can be inconvenient if it fails to completely remove incorrect data (e.g., noise, malicious data, out-of-distribution data) associated with a user. For instance, if someone unintentionally searches for an illegal product on their laptop and continues to receive recommendations for that product on their phone, even after clearing their web browser history, it leads to undesired usability (Y. Cao and Yang, 2015). Such persistent data retention not only results in inaccurate predictions but also reduces user satisfaction and engagement.
\n\nFidelity. Biased machine learning models can prompt requests for unlearning. Despite recent advancements, machine learning models are still susceptible to bias, resulting in outputs that unfairly discriminate against specific groups of people (Mehrabi et al., 2021). For instance, COMPAS, a software employed by courts to determine parole cases, demonstrates a higher tendency to assign elevated risk scores to African-American offenders compared to Caucasians, even when ethnicity information is not included as input (Zou and Schiebinger, 2018). Similar instances of bias have been observed in beauty contests judged by AI, which exhibited prejudice against participants with darker skin tones, as well as facial recognition AI systems that inaccurately recognized Asian facial features (Feuerriegel, Dolata, and Schwabe, 2020).
\n\nThe origin of these biases can often be traced back to the data itself. For instance, AI systems trained on public datasets that predominantly feature individuals of white ethnicity, such as ImageNet, are more prone to making errors when processing images of individuals with black ethnicity. Similarly, in an application screening system, the machine learning model might unintentionally acquire inappropriate features, such as gender or race information, during the learning process (Dinsdale, Jenkinson, and Namburete, 2021; Dinsdale, Jenkinson, et al., 2020). Consequently, there is a necessity to unlearn such data, which involves discarding the associated features and affected data items.
\n\nBefore we can fully achieve machine unlearning, there are several challenges that must be addressed in order to selectively remove specific portions of the training data. These challenges can be summarized as follows:
\nStochasticity of training. Due to the stochastic nature of the training process, we lack precise knowledge of the impact of each data point encountered during training on the machine learning model (Bourtoule et al., 2021). For example, neural networks are typically trained on random mini-batches consisting of a fixed number of data samples, and the order of these training batches is also randomized (Bourtoule et al., 2021). This stochasticity poses challenges for machine unlearning since the specific data sample to be removed would need to be eliminated from all batches consistently.
\nIncrementality of training. The training process of a model is incremental, meaning that updates made to the model based on a particular data sample will impact the model's performance on subsequent data samples (Bourtoule et al., 2021). Additionally, a model's performance on a given data sample is influenced by prior data samples. Finding a way to nullify the effects of a targeted training sample on the model's future performance poses a challenge for machine unlearning.
\nCatastrophic unlearning. Typically, an unlearned model performs worse than a model retrained on the remaining data (Q. P. Nguyen, Low, and Jaillet, 2020; Q. P. Nguyen et al., 2022). However, the degradation can become exponential when more data is unlearned, leading to what is commonly known as catastrophic unlearning (Q. P. Nguyen, Low, and Jaillet, 2020). While various studies (Du, Chen, et al., 2019; Golatkar, Achille, and Soatto, 2020a) have explored techniques to mitigate catastrophic unlearning through the design of specialized loss functions, finding natural ways to prevent catastrophic unlearning remains an open question.
","metadata":{}},{"cell_type":"markdown","source":"The aim of this paper is to supply a complete examination of research\nstudies on machine unlearning as well as a discussion on potential new\nresearch directions in machine unlearning. The contributions of our\nsurvey can therefore be summarized as follows.\nFirst, we show how to design an unlearning framework. We discuss the\ndesign requirements, different types of unlearning requests, and how to\nverify the unlearned model.\nSecond, we show how to define an unlearning problem in machine\nlearning systems. This includes the formulation of exact unlearning and\napproximate unlearning as well as the definition of indistinguishability\nmetrics to compare two given models (i.e., the unlearned model and the\nretrained model).\nThird, we introduce a unified taxonomy that categorizes the machine\nunlearning approaches into three branches: model-agnostic methods,\nmodel-intrinsic methods, and data-driven methods.\nFinally, we highlight the findings, trends and the forthcoming\naccording to our survey results.\n
\n\nThe below table\nsummarizes the differences between our survey and existing efforts to\nunify the field. In particular, machine unlearning is different\nfrom data deletion (Garg, Goldwasser, and Vasudevan\n2020). Both topics concern the right to be forgotten legislated\nand exercised across the world (Mantelero 2013). However, the\nlatter focuses only on the data perspective following the General Data\nProtection Regulation (GDPR) (Voigt and Von dem Bussche 2017), while\nmachine unlearning also addresses privacy problems from a model\nperspective.\nOn the other hand, there are some other concepts that might be mistaken as machine\nunlearning, such as data redaction that aims to poison the label\ninformation of the data to be forgotten inside the model
![\"image\"](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/kaggle/surveys.png\")
\nThe unlearning framework in [fig:unlearning_workflow]\npresents the typical workflow of a machine learning model in the\npresence of a data removal request. In general, a model is trained on\nsome data and is then used for inference. Upon a removal request, the\ndata-to-be-forgotten is unlearned from the model. The unlearned model is\nthen verified against privacy criteria, and, if these criteria are not\nmet, the model is retrained, i.e., if the model still leaks some\ninformation about the forgotten data. There are two main components to\nthis process: the learning component (left) and the\nunlearning component (right). The learning component involves\nthe current data, a learning algorithm, and the current model. In the\nbeginning, the initial model is trained from the whole dataset using the\nlearning algorithm. The unlearning component involves an unlearning\nalgorithm, the unlearned model, optimization requirements, evaluation\nmetrics, and a verification mechanism. Upon a data removal request, the\ncurrent model will be processed by an unlearning algorithm to forget the\ncorresponding information of that data inside the model. The unlearning\nalgorithm might take several requirements into account such as\ncompleteness, timeliness, and privacy guarantees. The outcome is an\nunlearned model, which will be evaluated against different performance\nmetrics (e.g., accuracy, ZRF score, anamnesis index). However, to\nprovide a privacy certificate for the unlearned model, a verification\n(or audit) is needed to prove that the model actually forgot the\nrequested data and that there are no information leaks. This audit might\ninclude a feature injection test, a membership inference attack,\nforgetting measurements, etc.
\n\nIf the unlearned model passes the verification, it becomes the new\nmodel for downstream tasks (e.g., inference, prediction, classification,\nrecommendation). If the model does not pass verification, the remaining\ndata, i.e., the original data excluding the data to be forgotten, needs\nto be used to retrain the model. Either way, the unlearning component\nwill be called repeatedly upon a new removal request.
\n\nItem Removal. Requests to remove certain\nitems/samples from the training data are the most common requests in\nmachine unlearning (Bourtoule et al. 2021). The\ntechniques used to unlearn these data are described in detail in
Feature Removal. In many scenarios, privacy leaks\nmight not only originate from a single data item but also in a group of\ndata with the similar features or labels (Warnecke et al. 2021). For\nexample, a poisoned spam filter might misclassify malicious addresses\nthat are present in thousands of emails. Thus, unlearning suspicious\nemails might not enough. Similarly, in an application screening system,\ninappropriate features, such as the gender or race of applicants, might\nneed to be unlearned for thousands of affected applications.
\nIn such cases, naively unlearning the affected data items\nsequentially is imprudent as repeated retraining is computationally\nexpensive. Moreover, unlearning too many data items can inherently\nreduce the performance of the model, regardless of the unlearning\nmechanism used. Thus, there is a need for unlearning data at the feature\nor label level with an arbitrary number of data items.
\nWarnecke et al. (Warnecke et al. 2021) proposed\na technique for unlearning a group of training data based on influence\nfunctions. More precisely, the effect of training data on model\nparameter updates is estimated and formularized in closed-form. As a\nresult of this formulation, influences of the learning sets act as a\ncompact update instead of solving an optimisation problem iteratively\n(e.g., loss minimization). First-order and second-order derivatives are\nthe keys to computing this update effectively (Warnecke et al. 2021).
\nGuo et al. (T.\nGuo et al. 2022) proposed another technique to unlearn a feature\nin the data based on disentangled representation. The core idea is to\nlearn the correlation between features from the latent space as well as\nthe effects of each feature on the output space. Using this information,\ncertain features can be progressively detached from the learnt model\nupon request, while the remaining features are still preserved to\nmaintain good accuracy. However, this method is mostly applicable to\ndeep neural networks in the image domain, in which the deeper\nconvolutional layers become smaller and can therefore identify abstract\nfeatures that match real-world data attributes.
\nClass Removal. There are many scenarios where the\nforgetting data belongs to single or multiple classes from a trained\nmodel. For example, in face recognition applications, each class is a\nperson’s face so there could potentially be thousands or millions of\nclasses. However, when a user opts out of the system, their face\ninformation must be removed without using a sample of their face.
\nSimilar to feature removal, class removal is more challenging than\nitem removal because retraining solutions can incur many unlearning\npasses. Even though each pass might only come at a small computational\ncost due to data partitioning, the expense mounts up. However,\npartitioning data by class itself does not help the model’s training in\nthe first place, as learning the differences between classes is the core\nof many learning algorithms (Tanha et al. 2020). Although some\nof the above techniques for feature removal can be applied to class\nremoval (Warnecke et al. 2021), it is\nnot always the case as class information might be implicit in many\nscenarios.
\nTarun et al. (Tarun\net al. 2021) proposed an unlearning method for class removal\nbased on data augmentation. The basic concept is to introduce noise into\nthe model such that the classification error is maximized for the target\nclass(es). The model is updated by training on this noise without the\nneed to access any samples of the target class(es). Since such impair\nstep may disturb the model weights and degrade the classification\nperformance for the remaining classes, a repair step is needed to train\nthe model for one or a few more epochs on the remaining data. Their\nexperiments show that the method can be efficient for large-scale\nmulti-class problems (100 classes). Further, the method worked\nespecially well with face recognition tasks because the deep neural\nnetworks were originally trained on triplet loss and negative samples so\nthe difference between the classes was quite significant (Masi et al.\n2018).
\nBaumhauer et al. (Baumhauer, Schöttle, and Zeppelzauer\n2020) proposed an unlearning method for class removal based on a\nlinear filtration operator that proportionally shifts the classification\nof the samples of the class to be forgotten to other classes. However,\nthe approach is only applicable to class removal due to the\ncharacteristics of this operator.
\nTask Removal. Today, machine learning models are not\nonly trained for a single task but also for multiple tasks. This\nparadigm, aka continual learning or lifelong learning (Parisi et al.\n2019), is motivated by the human brain, in which learning\nmultiple tasks can benefit each other due to their correlations. This\ntechnique is also used overcome data sparsity or cold-start problems\nwhere there is not enough data to train a single task effectively.
\nHowever, in these settings too, there can be a need to remove private\ndata related to a specific task. For example, consider a robot that is\ntrained to assist a patient at home during their medical treatment. This\nrobot may be asked to forget this assistance behaviour after the patient\nhas recovered (B.\nLiu, Liu, et al. 2022). To this end, temporarily learning a task\nand forgetting it in the future has become a need for lifelong learning\nmodels.
\nIn general, unlearning a task is uniquely challenging as continual\nlearning might depend on the order of the learned tasks. Therefore,\nremoving a task might create a catastrophic unlearning effect, where the\noverall performance of multiple tasks is degraded in a\ndomino-effect (B.\nLiu, Liu, et al. 2022). Mitigating this problem requires the\nmodel to be aware of that the task may potentially be removed in future.\nLiu et al. (B. Liu,\nLiu, et al. 2022) explains that this requires users to explicitly\ndefine which tasks will be learned permanently and which tasks will be\nlearned only temporarily.
\nStream Removal. Handling data streams where a huge\namount of data arrives online requires some mechanisms to retain or\nignore certain data while maintaining limited storage (Tam et al.\n2017). In the context of machine unlearning, however, handling\ndata streams is more about dealing with a stream of removal\nrequests.
\nGupta et el. (Gupta et al. 2021) proposed a\nstreaming unlearning setting involving a sequence of data removal\nrequests. This is motivated by the fact that many users can be involved\nin a machine learning system and decide to delete their data\nsequentially. Such is also the case when the training data has been\npoisoned in an adversarial attack and the data needs to be deleted\ngradually to recover the model’s performance. These streaming requests\ncan be either non-adaptive or adaptive. A non-adaptive request means\nthat the removal sequence does not depend on the intermediate results of\neach unlearning request, whereas and adaptive request means that the\ndata to be removed depends on the current unlearned model. In other\nwords, after the poisonous data is detected, the model is unlearned\ngradually so as to decide which data item is most beneficial to unlearn\nnext.
\n\nCompleteness (Consistency). A good unlearning\nalgorithm should be complete (Y. Cao and Yang 2015), i.e. the\nunlearned model and the retrained model make the same predictions about\nany possible data sample (whether right or wrong). One way to measure\nthis consistency is to compute the percentage of the same prediction\nresults on a test data. This requirement can be designed as an\noptimization objective in an unlearning definition (
Timeliness. In general, retraining can fully solve\nany unlearning problem. However, retraining is time-consuming,\nespecially when the distribution of the data to be forgotten is\nunknown (Y. Cao and Yang 2015;\nBourtoule et al. 2021). As a result, there needs to be a\ntrade-off between completeness and timeliness. Unlearning techniques\nthat do not use retraining might be inherently not complete, i.e., they\nmay lead to some privacy leaks, even though some provable guarantees are\nprovided for special cases (C. Guo et al.\n2020; Marchant, Rubinstein, and Alfeld 2022; Neel, Roth, and\nSharifi-Malvajerdi 2021). To measure timeliness, we can measure\nthe speed up of unlearning over retraining after an unlearning request\nis invoked.
\nIt is also worth recognizing the cause of this trade-off between\nretraining and unlearning. When there is not much data to be forgotten,\nunlearning is generally more beneficial as the effects on model accuracy\nare small. However, when there is much forgetting data, retraining might\nbe better as unlearning many times, even bounded, may catastrophically\ndegrade the model’s accuracy (Y. Cao and Yang 2015).
\nAccuracy. An unlearned model should be able to\npredict test samples correctly. Or at least its accuracy should be\ncomparable to the retrained model. However, as retraining is\ncomputationally costly, retrained models are not always available for\ncomparison. To address this issue, the accuracy of the unlearned model\nis often measured on a new test set, or it is compared with that of the\noriginal model before unlearning (He et al. 2021).
\nLight-weight. To prepare for unlearning process,\nmany techniques need to store model checkpoints, historical model\nupdates, training data, and other temporary data (He\net al. 2021; Bourtoule et al. 2021; G. Liu et al. 2020). A good\nunlearning algorithm should be light-weight and scale with big data. Any\nother computational overhead beside unlearning time and storage cost\nshould be reduced as well (Bourtoule et al. 2021).
\nProvable guarantees. With the exception of\nretraining, any unlearning process might be inherently approximate. It\nis practical for an unlearning method to provide a provable guarantee on\nthe unlearned model. To this end, many works have designed unlearning\ntechniques with bounded approximations on retraining (C. Guo et al.\n2020; Marchant, Rubinstein, and Alfeld 2022; Neel, Roth, and\nSharifi-Malvajerdi 2021). Nonetheless, these approaches are\nfounded on the premise that models with comparable parameters will have\ncomparable accuracy.
\nModel-agnostic. An unlearning process should be\ngeneric for different learning algorithms and machine learning\nmodels (Bourtoule et al. 2021),\nespecially with provable guarantees as well. However, as machine\nlearning models are different and have different learning algorithms as\nwell, designing a model-agnostic unlearning framework could be\nchallenging.
\nVerifiability. Beyond unlearning requests, another\ndemand by users is to verify that the unlearned model now protects their\nprivacy. To this end, a good unlearning framework should provide\nend-users with a verification mechanism. For example, backdoor attacks\ncan be used to verify unlearning by injecting backdoor samples into the\ntraining data (Sommer et al. 2020). If the\nbackdoor can be detected in the original model while not detected in the\nunlearned model, then verification is considered to be a success.\nHowever, such verification might be too intrusive for a trustworthy\nmachine learning system and the verification might still introduce false\npositive due to the inherent uncertainty in backdoor detection.
\n\nThe goal of unlearning verification methods is to certify that one\ncannot easily distinguish between the unlearned models and their\nretrained counterparts (Thudi, Jia, et al. 2022). While\nthe evaluation metrics ([sec:metrics]) are theoretical criteria\nfor machine unlearning, unlearning verification can act as a certificate\nfor an unlearned model. They also include best practices for validating\nthe unlearned models efficiently.
\nIt is noteworthy that while unlearning metrics (in
Feature Injection Test. The goal of this test is to\nverify whether the unlearned model has adjusted the weights\ncorresponding to the removed data samples based on data\nfeatures/attributes (Izzo et al. 2021). The idea is\nthat if the set of data to be forgotten has a very distinct feature\ndistinguishing it from the remaining set, it gives a strong signal for\nthe model weights. However, this feature needs to be correlated with the\nlabels of the set to be forgotten, otherwise the model might not learn\nanything from this feature.
\nMore precisely, an extra feature is added for each data item such\nthat it is equal to zero for the remaining set and is perfectly\ncorrelated with the labels of the set to forget. Izzo et al. (Izzo et al.\n2021) applied this idea with linear classifiers, where the weight\nassociated with this extra feature is expected to be significantly\ndifferent from zero after training. After the model is unlearned, this\nweight is expected to become zero. As a result, the difference of this\nweight can be plotted before and after unlearning as a measure of\neffectiveness of the unlearning process.
\nOne limitation of this verification method is that the current\nsolution is only applicable for linear and logistic models (Izzo et al.\n2021). This is because these models have explicit weights\nassociated with the injected feature, whereas, for other models such as\ndeep learning, injecting such a feature as a strong signal is\nnon-trivial, even though the set to be forgotten is small. Another\nlimitation to these types of methods is that an injected version of the\ndata needs to be created so that the model can be learned (either from\nscratch or incrementally depending on the type of the model).
\nForgetting Measuring. Even after the data to be\nforgotten has been unlearned from the model, it is still possible for\nthe model to carry detectable traces of those samples (Jagielski et al.\n2022). Jagielski et al. (Jagielski et al. 2022)\nproposed a formal way to measure the forgetfulness of a model via\nprivacy attacks. More precisely, a model is said to
Information Leakage. Many machine learning models\ninherently leak information during the model updating process (M. Chen et al.\n2021b). Recent works have exploited this phenomenon by comparing\nthe model before and after unlearning to measure the information\nleakage. More precisely, Salem et al. (Salem et al. 2020) proposed an\nadversary attack in the image domain that could reconstruct a removed\nsample when a classifier is unlearned on a data sample. Brockschmidt et\nal. (Zanella-Béguelin et al. 2020)\nsuggested a similar approach for the text domain. Chen et al. (M. Chen et al.\n2021b) introduced a membership inference attack to detect whether\na removed sample belongs to the learning set. Compared to previous\nworks (Salem et al. 2019;\nShokri et al. 2017), their approach additionally makes use of the\nposterior output distribution of the original model, besides that of the\nunlearned model. Chen et al. (M. Chen et al. 2021b) also proposed\ntwo leakage metrics, namely the degradation count and the degradation\nrate.
\nThe degradation count: is defined as the ratio between the\nnumber of target samples whose membership can be inferred by the\nproposed attack with higher confidence compared to traditional attacks\nand the total number of samples.
\nThe degradation rate: is defined the average improvement\nrate of the confidence of the proposed attack compared to traditional\nattacks.
\nMembership Inference Attacks. This kind of attack is\ndesigned to detect whether a target model leaks data (Shokri\net al. 2017; Thudi, Shumailov, et al. 2022; M. Chen et al.\n2021b). Specifically, an inference model is trained to recognise\nnew data samples from the training data used to optimize the target\nmodel. In (Shokri et al. 2017), a set of\nshallow models were trained on a new set of data items different from\nthe one that the target model was trained on. The attack model was then\ntrained to predict whether a data item belonged to the training data\nbased on the predictions made by shallow models for training as well as\ntesting data. The training set for the shallow and attack models share\nsimilar data distribution to the target model. Membership inference\nattacks are helpful for detecting data leaks. Hence, they are useful for\nverifying the effectiveness of the machine unlearning (M. Chen et al.\n2021b).
\nBackdoor attacks. Backdoor attacks were proposed to\ninject backdoors to the data for deceiving a machine learning\nmodel (B. Wang et al.\n2019). The deceived model makes correct predictions with clean\ndata, but with poison data in a target class as a backdoor trigger, it\nmakes incorrect predictions. Backdoor attacks were used to verify the\neffectiveness of machine unlearning in (Sommer et al. 2020,\n2022). Specifically, the setting begins with training a model\nthat has a mixture of clean and poison data items across all users. Some\nof the users want their data deleted. If the users’ data are not\nsuccessfully deleted, the poison samples will be predicted as the target\nclass. Otherwise, the model will not predict the poison samples as the\ntarget class. However, there is no absolute guarantee that this rule is\nalways correct, although one can increase the number of poison samples\nto make this rule less likely to fail.
\nSlow-down attacks. Some studies focus on the\ntheoretical guarantee of indistinguishability between an unlearned and a\nretrained models. However, the practical bounds on computation costs are\nlargely neglected in these papers (Marchant, Rubinstein, and Alfeld\n2022). As a result, a new threat has been introduced to machine\nunlearning where poisoning attacks are used to slow down the unlearning\nprocess. Formally, let
Interclass Confusion Test. The idea of this test is\nto investigate whether information from the data to be forgotten can\nstill be inferred from an unlearned model (Goel, Prabhu, and Kumaraguru\n2022). Different from traditional approximate unlearning\ndefinitions that focus on the indistinguishability between unlearned and\nretrained models in the parameter space, this test focuses on the output\nspace. More precisely, the test involves randomly selecting a set of\nsamples S ⊂ D from\ntwo chosen classes in the training data
Federated verification. Unlearning verification in\nfederated learning is uniquely challenging. First, the participation of\none or a few clients in the federation may subtly change the global\nmodel’s performance, making verification in the output space\nchallenging. Second, verification using adversarial attacks is not\napplicable in the federated setting because it might introduce new\nsecurity threats to the infrastructure (X. Gao et al. 2022). As a result, Gao\net al. (X. Gao et al.\n2022) proposes a verification mechanism that uses a few\ncommunication rounds for clients to verify their data in the global\nmodel. This approach is compatible with federated settings because the\nmodel is trained in the same way where the clients communicate with the\nserver over several rounds.
\nCryptographic proofs. Since most of existing\nverification frameworks do not provide any theoretical guarantee,\nEisenhofer et al. (Eisenhofer et al. 2022)\nproposed a cryptography-informed protocol to compute two proofs,\ni.e. proof of update (the model was trained on a particular dataset\nD) and proof of unlearning\n(the forget item d is not a\nmember of D). The core idea of\nthe proof of update is using SNARK (Bitansky et al. 2012) data\nstructure to commit a hash whenever the model is updated (learned or\nunlearned) while ensuring that: (i) the model was obtained from the\nremaining data, (ii) the remaining data does not contain any forget\nitems, (iii) the previous forget set is a subset of the current forget\nset, and (iv) the forget items are never re-added into the training\ndata. The core idea of the proof of unlearning is using the Merkle tree\nto maintain the order of data items in the training data so that an\nunlearned item cannot be added to the training data again. While the\napproach is demonstrated on SISA (efficient retraining) (Bourtoule et al.\n2021), it is applicable for any unlearning method.
\n\n","metadata":{}},{"cell_type":"markdown","source":"While the application of machine unlearning can originate from\nsecurity, usability, fidelity, and privacy reasons, it is often\nformulated as a privacy preserving problem where users can ask for the\nremoval of their data from computer systems and machine learning\nmodels (Sekhari\net al. 2021; Ginart et al. 2019; Bourtoule et al. 2021; Garg,\nGoldwasser, and Vasudevan 2020). The forgetting request can be\nmotivated by security and usability reasons as well. For example, the\nmodels can be attacked by adversarial data and produce wrong outputs.\nOnce these types of attacks are detected, the corresponding adversarial\ndata has to be removed as well without harming the model’s predictive\nperformance.
\nWhen fulfilling a removal request, the computer system needs to\nremove all user’s data and ‘forget’ any influence on the models that\nwere trained on those data. As removing data from a database is\nconsidered trivial, the literature mostly concerns how to unlearn data\nfrom a model (C.\nGuo et al. 2020; Izzo et al. 2021; Neel, Roth, and Sharifi-Malvajerdi\n2021; Ullah et al. 2021).
\nTo properly formulate an unlearning problem, we need to introduce a\nfew concepts. First, let us denote 𝒵 as\nan example space, i.e., a space of data items or examples (called\nsamples). Then, the set of all possible training datasets is denoted as\n𝒵*. One can argue that
To support forgetting requests, the computer system needs to have an\nunlearning mechanism, denoted by a function
As mentioned in the Section 1, machine\nunlearning can remove data and data linkages without retraining the\nmachine learning model from scratch, saving time and computational\nresources (J. Wang, Guo, et al.\n2022; K. Chen, Huang, et al. 2021). The specific approaches of\nmachine unlearning can be categorized into model-agnostic,\nmodel-intrinsic, and data-driven approaches.
\n\n![\"image\"](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/kaggle/algorithms.png\")
\nModel-agnostic machine unlearning methodologies include unlearning\nprocesses or frameworks that are applicable to different models.\nHowever, in some cases, theoretical guarantees are only provided for a\nclass of models (e.g., linear models). Nonetheless, they are still\nconsidered to be model-agnostic as their core ideas are applicable to\ncomplex models (e.g. deep neural networks) with practical results.
\n\n![\"https://arxiv.org/abs/2209.02299\"](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/figs/model-agnostic.png\")
\nDifferential Privacy. Differential privacy was first\nproposed to bound a data sample’s influence on a machine learning\nmodel (Dwork\n2008). ϵ-differential\nprivacy unlearns a data sample by setting
Certified Removal Mechanisms. Unlearning algorithms\nfalling into this category are the ones following the original\napproximate definition of machine unlearning (C. Guo et al. 2020; Golatkar,\nAchille, and Soatto 2020a). While Guo et al. (C. Guo et al. 2020) focus\non theoretical guarantees for linear models and convex losses, Golatkar\net al. (Golatkar, Achille, and Soatto\n2020a) introduce a computable upper bound for SGD-based learning\nalgorithms, especially deep neural networks. The core idea is based on\nthe notion of perturbation (noise) to mask the small residue incurred by\nthe gradient-based update (e.g., a one-step Newton update (Koh et al.\n2017)). The idea is applicable to other cases, although no\ntheoretical guarantees are provided (Bourtoule et al. 2021).
\nMore precisely, certified removal mechanisms mainly accommodate those\nlinear models that minimize a standardized empirical risk, which is the\ntotal value of a convex loss function that measures the distance of the\nactual value from the expected one (Marchant, Rubinstein, and Alfeld\n2022). However, one has to rely on a customized learning\nalgorithm that optimizes a perturbed version of the regularized\nempirical risk, where the added noise is drawn from a standard normal\ndistribution. This normalized noise allows conventional convex\noptimization techniques to solve the learning problem with perturbation.\nAs a result, the unlearning request can be done by computing the model\nperturbation towards the regularized empirical risk on the remaining\ndata. The final trick is that this perturbation can be approximated by\nthe influence function (Koh et al. 2017), which is\ncomputed by inverting the Hessian on training data and the gradient of\nthe data to be forgotten (Marchant, Rubinstein, and Alfeld\n2022). However, the error of model parameters in such a\ncomputation can be so large that the added noise cannot mask it.\nTherefore, if the provided theoretical upper bound exceeds a certain\nthreshold, the unlearning algorithm resorts to retraining from\nscratch (Marchant,\nRubinstein, and Alfeld 2022).
\nFollowing this idea, Neel et al. (Neel, Roth, and Sharifi-Malvajerdi\n2021) provided further extensions, namely regularized perturbed\ngradient descent and distributed perturbed gradient descent, to support\nweak convex losses and provide theoretical guarantees on\nindistinguishability, accuracy, and unlearning times.
\nUllah et al. (Ullah et al. 2021) continued\nstudying machine unlearning in the context of SGD and streaming removal\nrequests. They define the notation of total variation stability for a\nlearning algorithm:
Statistical Query Learning. Statistical query\nlearning is a form of machine learning that trains models by querying\nstatistics on the training data rather than itself (Y. Cao and Yang\n2015). In this form, a data sample can be forgotten efficiently\nby recomputing the statistics over the remaining data (Bourtoule et al.\n2021). More precisely, statistical query learning assumes that\nmost of the learning algorithms can be represented as a sum of some\nefficiently computable transformations, called statistical queries (Kearns 1998).\nThese statistical queries are basically requests to an oracle (e.g., a\nground truth) to estimate a statistical function over all training data.\nCao et al. (Y. Cao\nand Yang 2015) showed that this formulation can generalize many\nalgorithms for machine learning, such as the Chi-square test, naive\nBayes, and linear regression. For example, in naive Bayes, these\nstatistical queries are indicator functions that return 1 when the\noutput is a target label and zero otherwise (Y. Cao and Yang 2015). In the\nunlearning process, these queries are simply recomputed over the\nremaining data. The approach is efficient as these statistical functions\nare computationally efficient in the first place. Moreover, statistical\nquery learning also supports adaptive statistical queries, which are\ncomputed based on the prior state of the learning models, including\nk-means, SVM, and gradient descent. Although this time, the unlearning\nupdate makes the model not convergent any more, only a few learning\niterations (adaptive statistical queries) are needed since the model\nstarts from an almost-converged state. Moreover, if the old results of\nthe summations are cached, say, via dynamic programming, then the\nspeedup might be even higher.
\nThe limitation of this approach is that it does not scale with\ncomplex models such as deep neural networks. Indeed, in complex models,\nthe number of statistical queries could become exponentially large (Bourtoule et al.\n2021), making both the unlearning and relearning steps less\nefficient.
\nIn general, statistical query learning supports item removal and can\nbe partially applied to stream removal (Gupta et al. 2021) as well,\nalthough the streaming updates to the summations could be unbounded. It\nsupports exact unlearning, but only partially when the statistical\nqueries are non-adaptive. It also partially supports zero-shot\nunlearning, because only the statistics over the data need to be\naccessed, not the individual training data items.
\nDecremental Learning. Decremental learning\nalgorithms were originally designed to remove redundant samples and\nreduce the training load on the processor for support vector machines\n(SVM) (Y.\nChen et al. 2019; Cauwenberghs et al. 2000; Tveit et al. 2003; Tveit,\nHetland, and Engum 2003; Romero, Barrio, and Belanche 2007; Duan et al.\n2007) and linear classification (Karasuyama\nand Takeuchi 2009, 2010; Tsai, Lin, and Lin 2014). As such, they\nfocus on accuracy rather than the completeness of the machine\nunlearning.
\nGinart et al. (Ginart et al. 2019) developed\ndecremental learning solutions for
Knowledge Adaptation. Knowledge adaptation\nselectively removes to-be-forgotten data samples (Chundawat et al. 2022a). In this\napproach (Chundawat\net al. 2022a), one trains two neural networks as teachers\n(competent and incompetent) and one neural network as a student. The\ncompetent teacher is trained on the complete dataset, while the\nincompetent teacher is randomly initialised. The student is initialised\nwith the competent teacher’s model parameters. The student is trained to\nmimic both competent teacher and incompetent teacher by a loss function\nwith KL-divergence evaluation values between the student and each of the\ntwo teachers. Notably, the competent teacher processes the retained data\nand the incompetent teacher deals with the forgotten data.
\nBeyond Chundwat et al. (Chundawat et al. 2022a), machine\nlearning models have been quickly and accurately adapted by\nreconstructing the past gradients of knowledge-adaptation priors\nin (Khan et al.\n2021). Ideas similar to knowledge-adaptation priors were also\ninvestigated in (Ginart et al. 2019; Y. Wu,\nTannen, and Davidson 2020). In general, knowledge adaptation is\napplicable to a wide range of unlearning requests and scenarios.\nHowever, it is difficult to provide a theoretical guarantee for this\napproach.
\nMCMC Unlearning (Parameter Sampling). Sampling-based\nmachine unlearning has also been suggested as a way to train a standard\nmachine learning model to forget data samples from the training\ndata (Q. P. Nguyen\net al. 2022). The idea is to sample the distribution of model\nparameters using Markov chain Monte Carlo (MCMC). It is assumed that the\nforgetting set is often significantly smaller than the training data\n(otherwise retraining might be a better solution). Thus, the parameter\ndistribution
As a result, a candidate set of model parameters
The model-intrinsic approaches include unlearning methods designed\nfor a specific type of models. Although they are model-intrinsic, their\napplications are not necessarily narrow, as many machine learning models\ncan share the same type.
\n\n\n![\"https://arxiv.org/abs/2209.02299\"](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/figs/model-intrinsic.png\")
\nUnlearning for softmax classifiers (logit-based\nclassifiers). Softmax (or logit-based) classifiers are\nclassification models
Unlearning for linear models. Izzo et al. (Izzo et al.\n2021) proposed an approximate unlearning method for linear and\nlogistic models based on influence functions. They approximated a\nHessian matrix computation with a project residual update (Izzo\net al. 2021; Z. Cao et al. 2022) that combines gradient methods\nwith synthetic data. It is suitable for forgetting small groups of\npoints out of a learned model. Some other studies consider an online\nsetting for machine unlearning (aka online data deletion) (Ginart et\nal. 2019; Li, Wang, and Cheng 2021), in which the removal request\nis a sequence of entries that indicates which data item is to be\nunlearned. In general, this setting is more challenging than normal\nsetting because indistinguishability must hold for any entry and for the\nend of the deletion sequence. The goal is to achieve a lower bound on\namortized computation time (Ginart et al. 2019; Li,\nWang, and Cheng 2021).
\nLi et al. (Li, Wang,\nand Cheng 2021) formulated a special case of the online setting\nwhere data is only accessible for a limited time so there is no full\ntraining process in the first place. More precisely, the system is\nallowed a constant memory to store historical data or a data sketch, and\nit has to make predictions within a bounded period of time. Although the\ndata to be forgotten can be unlearned from a model on-the-fly using a\nregret scheme on the memory, this particular unlearning process is only\napplicable to ordinary linear regression (Li, Wang, and Cheng 2021).
\nUnlearning for Tree-based Models. Tree-based models\nare classification techniques that partition the feature space\nrecursively, where the features and cut-off thresholds to split the data\nare determined by some criterion, such as information gain (Schelter,\nGrafberger, and Dunning 2021). There is a class of tree-based\nmodels, called extremely randomized trees (Geurts, Ernst, et al. 2006),\nthat are built by an ensemble of decision trees. These are very\nefficient because the candidate set of split features and cut-off\nthresholds are randomly generated. The best candidate is selected by a\nreduction in Gini impurity, which avoids the heavy computation of\nlogarithms.
\nSchelter et al. (Schelter, Grafberger, and Dunning\n2021) proposed an unlearning solution for extremely randomized\ntrees by measuring the robustness of the split decisions. A split\ndecision is robust if removing
One limitation of this approach is that if the set to be forgotten is\ntoo large, there might be many non-robust splits. This would lead to\nhigh storage costs for the subtree variants. However, it does give a\nparameterized choice between unlearning and retraining. If there are\nmany removal requests, retraining might be the best asymptotically.\nAlternatively, one might limit the maximum number of removal requests to\nbe processed at a time. Moreover, tree-based models have a highly\ncompetitive performance for many predictive applications (Schelter,\nGrafberger, and Dunning 2021).
\nUnlearning for Bayesian Models. Bayesian models are\nprobabilistic models that approximate a posterior likelihood (Fu,\nHe, et al. 2022; Fu et al. 2021; Jose and Simeone 2021; Q. P. Nguyen,\nLow, and Jaillet 2020). Also known as Bayesian inference, this\nprocess is particularly useful when a loss function is not well-defined\nor does not even exist. Bayesian models cover a wide range of machine\nlearning algorithms, such as Bayesian neural networks, probabilistic\ngraphical models, generative models, topic modeling, and probabilistic\nmatrix factorization (H.\nZhang et al. 2020; Roth and Pernkopf 2018; Pearce, Leibfried, and\nBrintrup 2020).
\nUnlearning for Bayesian models requires a special treatment, as the\ntraining already involves optimizing the posterior distribution of the\nmodel’s parameters. It also often involves optimizing the\nKullback-Leibler divergence between a prior belief and the posterior\ndistribution (Q. P. Nguyen, Low, and Jaillet\n2020). Nguyen et al. (Q. P. Nguyen, Low, and Jaillet\n2020) proposed the notion of exact Bayesian learning:\n
A notion of certified Bayesian unlearning has also been studied,\nwhere the KL divergence between the unlearned model and the retrained\nmodel is bounded (Fu, He, et\nal. 2022; Fu et al. 2021; Jose and Simeone 2021):
Unlearning for DNN-based Models. Deep neural\nnetworks are advanced models that automatically learn features from\ndata. As a result, it is very difficult to pinpoint the exact model\nupdate for each data item (Golatkar,\nAchille, and Soatto 2020b, 2020a; Mehta et al. 2022; He et al. 2021;\nGoyal, Hassija, and Albuquerque 2021). Fortunately, deep neural\nnetworks consist of multiple layers. For layers with convex activation\nfunctions, existing unlearning methods such as certified removal\nmechanisms can be applied (C.\nGuo et al. 2020; Neel, Roth, and Sharifi-Malvajerdi 2021; Sekhari et al.\n2021; Z. Cao et al. 2022). For non-convex layers, Golatkar et\nal. (Golatkar et al.\n2021; Golatkar, Achille, and Soatto 2020b) proposed a caching\napproach that trains the model on data that are known a priori to be\npermanent. Then the model is fine-tuned on user data using some convex\noptimization.
\nSophisticated unlearning methods for DNNs rely primarily on influence\nfunctions (Koh et al. 2017;\nP.-F. Zhang et al. 2022). Here, Taylor expansions are used to\napproximate the impact of a data item on the parameters of black-box\nmodels (Zeng et al.\n2021). Some variants include DeltaGrad (Y. Wu et al. 2020), which stores\nthe historical updates for each data item, and Fisher-based\nunlearning (Golatkar, Achille, and Soatto\n2020a), which we discussed under [sec:model-agnostic]). However,\ninfluence functions in deep neural networks are not stable with a large\nforget set (Basu,\nPope, and Feizi 2021; Mahadevan and Mathioudakis 2021, 2022).
\nMore precisely, after the data to be forgotten has been deleted from\ndatabase, Fisher-based unlearning (Golatkar, Achille, and Soatto\n2020a) works on the remaining training data with the Newton’s\nmethod, which uses a second-order gradient. To mitigate potential\ninformation leaks, noise is injected into the model’s parameters (Cong and Mahdavi\n2022a). As the Fisher-based method aims to approximate the model\nwithout the deleted data, there can be no guarantee that all the\ninfluence of the deleted data has been removed. Although injecting noise\ncan help mitigate information leaks, the model’s performance may be\naffected by the noise (Cong and Mahdavi 2022a).
\nGolatkar et al. (Golatkar, Achille, and Soatto\n2020a) point out that the Hessian computation in certified\nremoval mechanisms is too expensive for complex models like deep neural\nnetworks. Hence, they resorted to an approximation of Hessian via\nLevenberg-Marquardt semi-positive-definite approximation, which turns\nout to correspond with the Fisher Information Matrix (Martens 2020).\nAlthough it does not provide a concrete theoretical guarantee,\nFisher-based unlearning could lead to further information-theoretic\napproaches to machine unlearning (T. Guo et al.\n2022; Golatkar, Achille, and Soatto 2020b).
\n\n| **Paper Title** | **Year** | **Author** | **Venue** | **Model** | **Code** | **Type** |\n| --------------- | :----: | ---- | :----: | :----: | :----: | :----: |\n| [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://arxiv.org/abs/2201.06640) | 2023 | Goel et al. | _arXiv_ | EU-k, CF-k | [[Code]](https://github.com/shash42/Evaluating-Inexact-Unlearning) |\n| [On the Trade-Off between Actionable Explanations and the Right to be Forgotten](https://openreview.net/pdf?id=HWt4BBZjVW) | 2023 | Pawelczyk et al. | _arXiv_ | - | - | |\n| [Towards Unbounded Machine Unlearning](https://arxiv.org/pdf/2302.09880) | 2023 | Kurmanji et al. | _arXiv_ | SCRUB | [[Code]](https://github.com/Meghdad92/SCRUB) | approximate unlearning |\n| [Netflix and Forget: Efficient and Exact Machine Unlearning from Bi-linear Recommendations](https://arxiv.org/abs/2302.06676) | 2023 | Xu et al. | _arXiv_ | Unlearn-ALS | - | Exact Unlearning |\n| [To Be Forgotten or To Be Fair: Unveiling Fairness Implications of Machine Unlearning Methods](https://arxiv.org/abs/2302.03350) | 2023 | Zhang et al. | _arXiv_ | - | [[Code]](https://github.com/cleverhans-lab/machine-unlearning) | |\n| [Sequential Informed Federated Unlearning: Efficient and Provable Client Unlearning in Federated Optimization](https://arxiv.org/abs/2211.11656) | 2022 | Fraboni et al. | _arXiv_ | SIFU | - | |\n| [Certified Data Removal in Sum-Product Networks](https://arxiv.org/abs/2210.01451) | 2022 | Becker and Liebig | _ICKG_ | UNLEARNSPN | [[Code]](https://github.com/ROYALBEFF/UnlearnSPN) | Certified Removal Mechanisms |\n| [Learning with Recoverable Forgetting](https://arxiv.org/abs/2207.08224) | 2022 | Ye et al. | _ECCV_ | LIRF | - | |\n| [Continual Learning and Private Unlearning](https://arxiv.org/abs/2203.12817) | 2022 | Liu et al. | _CoLLAs_ | CLPU | [[Code]](https://github.com/Cranial-XIX/Continual-Learning-Private-Unlearning) | |\n| [Verifiable and Provably Secure Machine Unlearning](https://arxiv.org/abs/2210.09126) | 2022 | Eisenhofer et al. | _arXiv_ | - | [[Code]](https://github.com/cleverhans-lab/verifiable-unlearning) | Certified Removal Mechanisms |\n| [VeriFi: Towards Verifiable Federated Unlearning](https://arxiv.org/abs/2205.12709) | 2022 | Gao et al. | _arXiv_ | VERIFI | - | Certified Removal Mechanisms |\n| [FedRecover: Recovering from Poisoning Attacks in Federated Learning using Historical Information](https://arxiv.org/abs/2210.10936) | 2022 | Cao et al. | _S&P_ | FedRecover | - | recovery method |\n| [Fast Yet Effective Machine Unlearning](https://arxiv.org/abs/2111.08947) | 2022 | Tarun et al. | _arXiv_ | UNSIR | - | |\n| [Membership Inference via Backdooring](https://arxiv.org/abs/2206.04823) | 2022 | Hu et al. | _IJCAI_ | MIB | [[Code]](https://github.com/HongshengHu/membership-inference-via-backdooring) | Membership Inferencing |\n| [Forget Unlearning: Towards True Data-Deletion in Machine Learning](https://arxiv.org/abs/2210.08911) | 2022 | Chourasia et al. | _ICLR_ | - | - | noisy gradient descent |\n| [Zero-Shot Machine Unlearning](https://arxiv.org/abs/2201.05629) | 2022 | Chundawat et al. | _arXiv_ | - | - | |\n| [Efficient Attribute Unlearning: Towards Selective Removal of Input Attributes from Feature Representations](https://arxiv.org/abs/2202.13295) | 2022 | Guo et al. | _arXiv_ | attribute unlearning | - | |\n| [Few-Shot Unlearning](https://download.huan-zhang.com/events/srml2022/accepted/yoon22fewshot.pdf) | 2022 | Yoon et al. | _ICLR_ | - | - | |\n| [Federated Unlearning: How to Efficiently Erase a Client in FL?](https://arxiv.org/abs/2207.05521) | 2022 | Halimi et al. | _UpML Workshop_ | - | - | federated learning |\n| [Machine Unlearning Method Based On Projection Residual](https://arxiv.org/abs/2209.15276) | 2022 | Cao et al. | _DSAA_ | - | - | Projection Residual Method |\n| [Hard to Forget: Poisoning Attacks on Certified Machine Unlearning](https://ojs.aaai.org/index.php/AAAI/article/view/20736) | 2022 | Marchant et al. | _AAAI_ | - | [[Code]](https://github.com/ngmarchant/attack-unlearning) | Certified Removal Mechanisms |\n| [Athena: Probabilistic Verification of Machine Unlearning](https://web.archive.org/web/20220721061150id_/https://petsymposium.org/popets/2022/popets-2022-0072.pdf) | 2022 | Sommer et al. | _PoPETs_ | ATHENA | - | |\n| [FP2-MIA: A Membership Inference Attack Free of Posterior Probability in Machine Unlearning](https://link.springer.com/chapter/10.1007/978-3-031-20917-8_12) | 2022 | Lu et al. | _ProvSec_ | FP2-MIA | - | inference attack |\n| [Deletion Inference, Reconstruction, and Compliance in Machine (Un)Learning](https://arxiv.org/abs/2202.03460) | 2022 | Gao et al. | _PETS_ | - | - | |\n| [Prompt Certified Machine Unlearning with Randomized Gradient Smoothing and Quantization](https://openreview.net/pdf?id=ue4gP8ZKiWb) | 2022 | Zhang et al. | _NeurIPS_ | PCMU | - | Certified Removal Mechanisms |\n| [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://arxiv.org/abs/2203.07320) | 2022 | Liu et al. | _INFOCOM_ | - | [[Code]](https://github.com/yiliucs/federated-unlearning) | |\n| [Backdoor Defense with Machine Unlearning](https://arxiv.org/abs/2201.09538) | 2022 | Liu et al. | _INFOCOM_ | BAERASER | - | Backdoor defense |\n| [Markov Chain Monte Carlo-Based Machine Unlearning: Unlearning What Needs to be Forgotten](https://dl.acm.org/doi/abs/10.1145/3488932.3517406) | 2022 | Nguyen et al. | _ASIA CCS_ | MCU | - | MCMC Unlearning |\n| [Federated Unlearning for On-Device Recommendation](https://arxiv.org/abs/2210.10958) | 2022 | Yuan et al. | _arXiv_ | - | - | |\n| [Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks using an Incompetent Teacher](https://arxiv.org/abs/2205.08096) | 2022 | Chundawat et al. | _arXiv_ | - | - | Knowledge Adaptation |\n| [ Efficient Two-Stage Model Retraining for Machine Unlearning](https://openaccess.thecvf.com/content/CVPR2022W/HCIS/html/Kim_Efficient_Two-Stage_Model_Retraining_for_Machine_Unlearning_CVPRW_2022_paper.html) | 2022 | Kim and Woo | _CVPR Workshop_ | - | - | |\n| [Learn to Forget: Machine Unlearning Via Neuron Masking](https://ieeexplore.ieee.org/abstract/document/9844865?casa_token=_eowH3BTt1sAAAAA:X0uCpLxOwcFRNJHoo3AtA0ay4t075_cSptgTMznsjusnvgySq-rJe8GC285YhWG4Q0fUmP9Sodw0) | 2021 | Ma et al. | _IEEE_ | Forsaken | - | Mask Gradients |\n| [Adaptive Machine Unlearning](https://proceedings.neurips.cc/paper/2021/hash/87f7ee4fdb57bdfd52179947211b7ebb-Abstract.html) | 2021 | Gupta et al. | _NeurIPS_ | - | [[Code]](https://github.com/ChrisWaites/adaptive-machine-unlearning) | Differential Privacy |\n| [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://proceedings.mlr.press/v132/neel21a.html) | 2021 | Neel et al. | _ALT_ | - | - | Certified Removal Mechanisms |\n| [Remember What You Want to Forget: Algorithms for Machine Unlearning](https://arxiv.org/abs/2103.03279) | 2021 | Sekhari et al. | _NeurIPS_ | - | - | |\n| [FedEraser: Enabling Efficient Client-Level Data Removal from Federated Learning Models](https://ieeexplore.ieee.org/abstract/document/9521274) | 2021 | Liu et al. | _IWQoS_ | FedEraser | - | |\n| [Federated Unlearning](https://arxiv.org/abs/2012.13891) | 2021 | Liu et al. | _IWQoS_ | FedEraser | [[Code]](https://www.dropbox.com/s/1lhx962axovbbom/FedEraser-Code.zip?dl=0) | |\n| [Machine Unlearning via Algorithmic Stability](https://proceedings.mlr.press/v134/ullah21a.html) | 2021 | Ullah et al. | _COLT_ | TV | - | Certified Removal Mechanisms |\n| [EMA: Auditing Data Removal from Trained Models](https://link.springer.com/chapter/10.1007/978-3-030-87240-3_76) | 2021 | Huang et al. | _MICCAI_ | EMA | [[Code]](https://github.com/Hazelsuko07/EMA) | Certified Removal Mechanisms |\n| [Knowledge-Adaptation Priors](https://proceedings.neurips.cc/paper/2021/hash/a4380923dd651c195b1631af7c829187-Abstract.html) | 2021 | Khan and Swaroop | _NeurIPS_ | K-prior | [[Code]](https://github.com/team-approx-bayes/kpriors) | Knowledge Adaptation |\n| [PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models](https://dl.acm.org/doi/abs/10.1145/3318464.3380571) | 2020 | Wu et al. | _NeurIPS_ | PrIU | - | Knowledge Adaptation |\n| [Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks](https://arxiv.org/abs/1911.04933) | 2020 | Golatkar et al. | _CVPR_ | - | - | Certified Removal Mechanisms |\n| [Learn to Forget: User-Level Memorization Elimination in Federated Learning](https://www.researchgate.net/profile/Ximeng-Liu-5/publication/340134612_Learn_to_Forget_User-Level_Memorization_Elimination_in_Federated_Learning/links/5e849e64a6fdcca789e5f955/Learn-to-Forget-User-Level-Memorization-Elimination-in-Federated-Learning.pdf) | 2020 | Liu et al. | _arXiv_ | Forsaken | - | |\n| [Certified Data Removal from Machine Learning Models](https://proceedings.mlr.press/v119/guo20c.html) | 2020 | Guo et al. | _ICML_ | - | - | Certified Removal Mechanisms |\n| [Class Clown: Data Redaction in Machine Unlearning at Enterprise Scale](https://arxiv.org/abs/2012.04699) | 2020 | Felps et al. | _arXiv_ | - | - | Decremental Learning |\n| [A Novel Online Incremental and Decremental Learning Algorithm Based on Variable Support Vector Machine](https://link.springer.com/article/10.1007/s10586-018-1772-4) | 2019 | Chen et al. | _Cluster Computing_ | - | - | Decremental Learning |\n| [Making AI Forget You: Data Deletion in Machine Learning](https://papers.nips.cc/paper/2019/hash/cb79f8fa58b91d3af6c9c991f63962d3-Abstract.html) | 2019 | Ginart et al. | _NeurIPS_ | - | - | Decremental Learning |\n| [Lifelong Anomaly Detection Through Unlearning](https://dl.acm.org/doi/abs/10.1145/3319535.3363226) | 2019 | Du et al. | _CCS_ | - | - | |\n| [Learning Not to Learn: Training Deep Neural Networks With Biased Data](https://openaccess.thecvf.com/content_CVPR_2019/html/Kim_Learning_Not_to_Learn_Training_Deep_Neural_Networks_With_Biased_CVPR_2019_paper.html) | 2019 | Kim et al. | _CVPR_ | - | - | |\n| [Efficient Repair of Polluted Machine Learning Systems via Causal Unlearning](https://dl.acm.org/citation.cfm?id=3196517) | 2018 | Cao et al. | _ASIACCS_ | KARMA | [[Code]](https://github.com/CausalUnlearning/KARMA) | |\n| [Understanding Black-box Predictions via Influence Functions](https://proceedings.mlr.press/v70/koh17a.html) | 2017 | Koh et al. | _ICML_ | - | [[Code]](https://github.com/kohpangwei/influence-release) | Certified Removal Mechanisms |\n| [Towards Making Systems Forget with Machine Unlearning](https://ieeexplore.ieee.org/abstract/document/7163042) | 2015 | Cao and Yang | _S&P_ | - | |\n| [Towards Making Systems Forget with Machine Unlearning](https://dl.acm.org/doi/10.1109/SP.2015.35) | 2015 | Cao et al. | _S&P_ | - | - | Statistical Query Learning |\n| [Incremental and decremental training for linear classification](https://dl.acm.org/doi/10.1145/2623330.2623661) | 2014 | Tsai et al. | _KDD_ | - | [[Code]](https://www.csie.ntu.edu.tw/~cjlin/papers/ws/) | Decremental Learning |\n| [Multiple Incremental Decremental Learning of Support Vector Machines](https://dl.acm.org/doi/10.5555/2984093.2984196) | 2009 | Karasuyama et al. | _NIPS_ | - | - | Decremental Learning |\n| [Incremental and Decremental Learning for Linear Support Vector Machines](https://dl.acm.org/doi/10.5555/1776814.1776838) | 2007 | Romero et al. | _ICANN_ | - | - | Decremental Learning |\n| [Decremental Learning Algorithms for Nonlinear Langrangian and Least Squares Support Vector Machines](https://www.semanticscholar.org/paper/Decremental-Learning-Algorithms-for-Nonlinear-and-Duan-Li/312c677f0882d0dfd60bfd77346588f52aefd10f) | 2007 | Duan et al. | _OSB_ | - | - | Decremental Learning |\n| [Multicategory Incremental Proximal Support Vector Classifiers](https://link.springer.com/chapter/10.1007/978-3-540-45224-9_54) | 2003 | Tveit et al. | _KES_ | - | - | Decremental Learning |\n| [Incremental and Decremental Proximal Support Vector Classification using Decay Coefficients](https://link.springer.com/chapter/10.1007/978-3-540-45228-7_42) | 2003 | Tveit et al. | _DaWak_ | - | - | Decremental Learning |\n| [Incremental and Decremental Support Vector Machine Learning](https://dl.acm.org/doi/10.5555/3008751.3008808) | 2000 | Cauwenberg et al. | _NeurIPS_ | - | - | Decremental Learning |\n----------","metadata":{}},{"cell_type":"markdown","source":"![\"https://arxiv.org/abs/2209.02299\"](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/figs/data-driven.png\")
\nData Partitioning (Efficient Retraining). The\napproaches falling into this category uses data partitioning mechanisms\nto speed up the retraining process. Alternatively, they partially\nretrain the model with some bounds on accuracy. Bourtoule et al. (Bourtoule et al.\n2021) proposed the well-known SISA framework (
![](\"https://raw.githubusercontent.com/tamlhp/awesome-machine-unlearning/main/kaggle/partition.png\"\nalt=\"Efficient)
\nData Augmentation (Error-manipulation noise). Data\naugmentation is the process of enriching or adding more data to support\na model’s training (D. Yu\net al. 2021). Such mechanisms can be used to support machine\nunlearning as well. Huang et al. (H. Huang et al. 2021) proposed\nthe idea of error-minimizing noise, which tricks a model into thinking\nthat there is nothing to be learned from a given set of data (i.e., the\nloss does not change). However, it can only be used to protect a\nparticular data item before the model is trained. A similar setting was\nalso studied by Fawkes (Shan et al. 2020), in which a\ntargeted adversarial attack is used to ensure the model does not learn\nanything from a targeted data item.
\nConversely, Tarun et al. (Tarun et al. 2021) proposed\nerror-maximizing noise to impair the model on a target class of data (to\nbe forgotten). However, this tactic does not work on specific data items\nas it is easier to interfere with a model’s prediction on a whole class\nas opposed to a specific data item of that class (Tarun et al. 2021).
\nData influence. This group of unlearning approaches\nstudies how a change in training data impacts a model’s parameters (G. Wu, Hashemi,\nand Srinivasa 2022; Cong and Mahdavi 2022a; Z. Cao et al. 2022),\nwhere impact is computed using influence functions (Mahadevan and\nMathioudakis 2022; Chundawat et al. 2022b). However, influence\nfunctions depend on the current state of a learning algorithm (G. Wu, Hashemi, and Srinivasa\n2022). To mitigate this issue, several works store a training\nhistory of intermediate quantities (e.g., model parameters or gradients)\ngenerated by each step of model training (Graves,\nNagisetty, and Ganesh 2021; Neel, Roth, and Sharifi-Malvajerdi 2021; Y.\nWu et al. 2020; Y. Wu, Tannen, and Davidson 2020). Then, the\nunlearning process becomes one of subtracting these historical updates.\nHowever, the model’s accuracy might degrade significantly due to\ncatastrophic unlearning (Q. P. Nguyen, Low, and Jaillet\n2020) since the order in which the training data is fed matters\nto the learning model. Moreover, the influence itself does not verify\nwhether the data to be forgotten is still included in the unlearned\nmodel (Thudi, Jia, et al.\n2022; Thudi, Deza, et al. 2022).
\nZeng et al. (Zeng et al. 2021) suggested a new\nmethod of modeling data influence by adding regularization terms into\nthe learning algorithm. Although this method is model-agnostic, it\nrequires intervening in the original training process of the original\nmodel. Moreover, it is only applicable to convex learning problems and\ndeep neural networks.
\nPeste et al. (Peste, Alistarh, and Lampert 2021)\nclosed this gap by introducing a new Fisher-based unlearning method,\nwhich can approximate the Hessian matrix. This method works for both\nshallow and deep models, and also convex and non-convex problems. The\nidea is to efficiently compute the matrix inversion of a Fisher\nInformation Matrix using rank-one updates. However, as the whole process\nis approximate, there is no concrete guarantee on the unlearned\nmodel.
\n\n| **Paper Title** | **Year** | **Author** | **Venue** | **Model** | **Code** | **Type** |\n| --------------- | :----: | ---- | :----: | :----: | :----: | :----: |\n| [Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks](https://arxiv.org/abs/2212.10717) | 2022 | Di et al. | _NeurIPS_ | - | [[Code]](https://github.com/Jimmy-di/camouflage-poisoning) | Data Poisoning |\n| [Forget Unlearning: Towards True Data Deletion in Machine Learning](https://arxiv.org/pdf/2210.08911.pdf) | 2022 | Chourasia et al. | _ICLR_ | - | - | Data Influence |\n| [ARCANE: An Efficient Architecture for Exact Machine Unlearning](https://www.ijcai.org/proceedings/2022/0556.pdf) | 2022 | Yan et al. | _IJCAI_ | ARCANE | - | Data Partition |\n| [PUMA: Performance Unchanged Model Augmentation for Training Data Removal](https://ojs.aaai.org/index.php/AAAI/article/view/20846) | 2022 | Wu et al. | _AAAI_ | PUMA | - | Data Influence |\n| [Certifiable Unlearning Pipelines for Logistic Regression: An Experimental Study](https://www.mdpi.com/2504-4990/4/3/28) | 2022 | Mahadevan and Mathioudakis | _MAKE_ | - | [[Code]](https://version.helsinki.fi/mahadeva/unlearning-experiments) | Data Influence |\n| [Zero-Shot Machine Unlearning](https://arxiv.org/abs/2201.05629) | 2022 | Chundawat et al. | _arXiv_ | - | - | Data Influence |\n| [GRAPHEDITOR: An Efficient Graph Representation Learning and Unlearning Approach](https://congweilin.github.io/CongWeilin.io/files/GraphEditor.pdf) | 2022 | Cong and Mahdavi | - | GRAPHEDITOR | [[Code]](https://anonymous.4open.science/r/GraphEditor-NeurIPS22-856E/README.md) | Data Influence |\n| [Fast Model Update for IoT Traffic Anomaly Detection with Machine Unlearning](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=9927728) | 2022 | Fan et al. | _IEEE IoT-J_ | ViFLa | - | Data Partition |\n| [Learning to Refit for Convex Learning Problems](https://arxiv.org/abs/2111.12545) | 2021 | Zeng et al. | _arXiv_ | OPTLEARN | - | Data Influence |\n| [Fast Yet Effective Machine Unlearning](https://arxiv.org/abs/2111.08947) | 2021 | Ayush et al. | _arXiv_ | - | - | Data Augmentation |\n| [Learning with Selective Forgetting](https://www.ijcai.org/proceedings/2021/0137.pdf) | 2021 | Shibata et al. | _IJCAI_ | - | - | Data Augmentation |\n| [SSSE: Efficiently Erasing Samples from Trained Machine Learning Models](https://openreview.net/forum?id=GRMKEx3kEo) | 2021 | Peste et al. | _NeurIPS_ | SSSE | - | Data Influence |\n| [How Does Data Augmentation Affect Privacy in Machine Learning?](https://arxiv.org/abs/2007.10567) | 2021 | Yu et al. | _AAAI_ | - | [[Code]](https://github.com/dayu11/MI_with_DA) | Data Augmentation |\n| [Coded Machine Unlearning](https://ieeexplore.ieee.org/document/9458237) | 2021 | Aldaghri et al. | _IEEE_ | - | - | Data Partitioning |\n| [Machine Unlearning](https://ieeexplore.ieee.org/document/9519428) | 2021 | Bourtoule et al. | _IEEE_ | SISA | [[Code]](https://github.com/cleverhans-lab/machine-unlearning) | Data Partitioning |\n| [How Does Data Augmentation Affect Privacy in Machine Learning?](https://ojs.aaai.org/index.php/AAAI/article/view/17284/) | 2021 | Yu et al. | _AAAI_ | - | [[Code]](https://github.com/dayu11/MI_with_DA) | Data Augmentation |\n| [Amnesiac Machine Learning](https://ojs.aaai.org/index.php/AAAI/article/view/17371) | 2021 | Graves et al. | _AAAI_ | AmnesiacML | [[Code]](https://github.com/lmgraves/AmnesiacML) | Data Influence |\n| [Unlearnable Examples: Making Personal Data Unexploitable](https://arxiv.org/abs/2101.04898) | 2021 | Huang et al. | _ICLR_ | - | [[Code]](https://github.com/HanxunH/Unlearnable-Examples) | Data Augmentation |\n| [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://proceedings.mlr.press/v132/neel21a.html) | 2021 | Neel et al. | _ALT_ | - | - | Data Influence |\n| [Fawkes: Protecting Privacy against Unauthorized Deep Learning Models](https://dl.acm.org/doi/abs/10.5555/3489212.3489302) | 2020 | Shan et al. | _USENIX Sec. Sym._ | Fawkes | [[Code]](https://github.com/Shawn-Shan/fawkes) | Data Augmentation |\n| [PrIU: A Provenance-Based Approach for Incrementally Updating Regression Models](https://dl.acm.org/doi/abs/10.1145/3318464.3380571) | 2020 | Wu et al. | _SIGMOD_ | PrIU/PrIU-opt | - | Data Influence |\n| [DeltaGrad: Rapid retraining of machine learning models](https://proceedings.mlr.press/v119/wu20b.html) | 2020 | Wu et al. | _ICML_ | DeltaGrad | [[Code]](https://github.com/thuwuyinjun/DeltaGrad) | Data Influence |\n\n\n----------","metadata":{}},{"cell_type":"markdown","source":"The most often used metrics for measuring anomaly detection\nperformance include accuracy, completeness, unlearn time, distance, and\nforgetting scores. Their formulas and common usage are summarized in
Accuracy. In machine unlearning, a model’s accuracy\nneeds to be compared on three different datasets: (1) The set to be\nforgotten. Since the expected behaviour of an unlearned model after\nunlearning should mirror that of a retrained model, the accuracy on the\nremaining data should be similar to the retrained model. (2) The\nretained set. The retained set’s accuracy should be close to that of the\noriginal model. (3) The test set. The unlearned model should still\nperform well on a separate test dataset compared to the retrained\nmodel.
\nCompleteness. The influence of the to-be-removed\nsamples on the unlearned model must be completely eliminated.\nCompleteness, hence, measures the degree to which an unlearned model is\ncompatible with a retrained model (Y. Cao and Yang 2015). If the\nunlearned model gives similar predictions to a retrained model for all\nsamples, the operation of feeding samples or observing the model’s\ninformation is impractical to achieve the forgotten data and its\nlineage. The final metric is often calculated as the overlap of output\nspace (e.g., the Jaccard distance) between the unlearned model and the\nretraining. However, computing this metric is often exhaustive.
\nUnlearning time and Retraining time. Timeliness\nquantifies the time saved when using unlearning instead of retraining\nfor model update. The quicker the system restores privacy, security, and\nusefulness, the more timely the unlearning process. In particular,\nretraining uses the whole training set to execute the learning\nalgorithm, whereas unlearning executes the learning algorithm on a\nlimited amount of summations; hence, the speed of unlearning is quicker\ndue to the reduced size of the training data.
\nRelearn time. Relearning time is an excellent proxy\nfor measuring the amount of unlearned data information left in the\nmodel. If a model recovers its performance on unlearned data with just a\nfew steps of retraining, it is extremely probable that the model has\nretained some knowledge of the unlearned data.
\nThe layer-wise distance. The layer-wise distance\nbetween the original and unlearned models helps when trying to\nunderstand the impact of the unlearning on each layer. The weight\ndifference should be comparable to a retrained model given that a\nshorter distance indicates ineffective unlearning. Likewise, a much\nlonger distance may point to a Streisand effect and possible information\nleaks.
\nActivation Distance. The activation distance is the\nseparation between the final activation of the scrubbed weights and the\nretrained model. A shorter activation distance indicates superior\nunlearning.
\nJS-Divergence. When paired with the activation\ndistance, the JS-Divergence between the predictions of the unlearned and\nretrained model provides a more full picture of unlearning. Less\ndivergence results in better unlearning. The formula of JS-Divergence is\n
Membership Inference. The membership inference\nmetric leverages a membership inference attack to determine whether or\nnot any information about the forgotten samples remains in the\nmodel (M. Chen et\nal. 2021b). The set to be forgotten should have reduced the\nattack probability in the unlearned model. The chance of an inference\nattack should be reduced in the unlearned model compared to the original\nmodel for the forgotten class data.
\nZRF score. Zero Retrain Forgetting (ZRF) makes it\npossible to evaluate unlearning approaches independent of\nretraining (Chundawat et al. 2022a). The\nunpredictability of the model’s predictions is measured by comparing\nthem to an unskilled instructor. ZRF compares the set to be forgotten’s\noutput distribution to the output of a randomly initialised model, which\nin most situations is our lousy instructor. The ZRF score ranges between\n0 and 1; it will be near to 1 if the model’s behaviour with the\nforgotten samples is entirely random, and close to 0 if it exhibits a\ncertain pattern. The formula of ZRF score is
Anamnesis Index (AIN). AIN values range between 0\nand 1. The better the unlearning, the closer to 1. Instances where\ninformation from the classes to be forgotten are still preserved in the\nmodel correlate to AIN levels well below 1. A score closer to 0 also\nsuggests that the unlearned model will rapidly relearn to generate\ncorrect predictions. This may be due to the fact that the last layers\ncontain limited reversible modifications, which degrades the performance\nof the model on the forgotten classes. If an AIN score is much greater\nthan 1, it may suggest that the approach causes parameter changes that\nare so severe that the unlearning itself may be detected (Streisand\neffect). This might be due to the fact that the model was pushed away\nfrom the original point and, as a result, is unable to retrieve\npreviously learned knowledge about the forgotten class(es). The formula\nfor calculating an AIN value is $AIN =\n\\frac{r_t (M_u, M_{orig}, \\alpha)}{r_t (M_s, M_{orig}, \\alpha)}$,\nwhere α% is a margin around\nthe initial precision used to determine relearn time.
In the field of machine learning, recommender systems are used to\npredict what a user might want to buy or watch. They often use\ncollaborative filtering to learn a user’s preferences based on their\npast behavior. However, a recommender system may be required to forget\nprivate training points and its complete impact on a model in order to\nprotect user privacy or comply with explicit user removal requests.\nUtility is another reason for unlearning requests. For example, the\naccuracy of a recommendation can be degraded due to out-of-distribution\ndata or poisoning attacks (Marchant, Rubinstein, and\nAlfeld 2022; Du, Chen, et al. 2019). In the latter case, data\nthat is detected as poisoned will need to be removed, while in the\nformer case, old data may need to be removed so that the system keeps up\nwith the new data distribution.
\nUnlearning techniques for machine learning in general cannot be used\ndirectly on recommender systems (C. Chen et al.\n2022; B. L. Wang and Schelter 2022). For example, collaborative\nfiltering recommendation uses the information of similarity across\nusers-item interaction; and thus, arbitrarily partitioning the training\nsets could break such coupling information (Bourtoule et al. 2021). Some\nresearchers have developed unlearning methods for graph data (M. Chen et al.\n2021a) and while recommendation data can be modelled as graphs,\ntheir user-item interactions are not uniform (C. Chen et al. 2022).
\nTo overcome these challenges, Chen et al. (C. Chen et al. 2022)\nproposed a partition-based retraining process, called smart retraining,\nto unlearn the model from the removed user behavior data. The idea is to\ndevelop a strategy to partition the data with regard to the resemblance\nbetween users and items while maintaining the balance between different\npartitions for retraining. Next, the output of the submodels is combined\nusing an attention-based method, each of which is associated with each\ndisjoint partition.
\n\nRecently, federated learning has become popular in the field of\nmachine learning (McMahan et al. 2017). One\ntypical federated learning scenario is building a machine learning model\nfrom healthcare information. Due to privacy regulations, the medical\nrecord data cannot leave the clients’ devices. Here, the clients could\nbe hospitals or personal computers and are assumed to have machine\nlearning environments. The server does not transmit the actual data to\nthe global model. Rather, there is a communication protocol between the\nclients and servers that governs collaborative model training (C. Wu et al.\n2022). In the literature, the communication protocol Federated\nAverage (FedAvg) (McMahan et al. 2017) is\ntypically used for model training. It consists of multiple rounds. Each\nround, the current global model weights are transmitted to the clients.\nBased on these weights, each client uses stochastic gradient descent to\nadjust their local model. Then the local model’s weights are forwarded\nto the server. In the final phase of each loop, the server aggregates\nthe received weights by (weighted) averaging to prepare the global model\nfor the next round (Halimi et al. 2022).
\nGiven such training protocols, machine unlearning cannot be extended\neasily to the federated learning setting. This is because the global\nweights are computed by aggregations rather than raw gradients. These\nare especially mixed up when many clients participate (X. Gao et al. 2022).\nMoreover, these clients might have some overlapping data, making it\ndifficult to quantify the impact of each training item on the model\nweights (Yang Liu et\nal. 2020). Using classic unlearning methods by gradient\nmanipulation may even lead to severe accuracy degradation or new privacy\nthreats (G. Liu et\nal. 2021).
\nAdditionally, current studies on federated unlearning tend to assume\nthat the data to be removed belongs wholly to one client (G.\nLiu et al. 2021; J. Wang, Guo, et al. 2022; C. Wu et al. 2022; Yang Liu\net al. 2020). With this assumption, the historical contributions\nof particular clients to the global model’s training can be logged and\nerased easily. However, erasing historical parameter updates might still\ndamage the global model, but there are many strategies for overcoming\nthis issue. For example, Liu et al. (G. Liu et al. 2021) proposed\ncalibration training to separate the individual contributions of clients\nas much as possible. This mechanism does not work well for deep neural\nnetworks, but it does work well with shallow architectures such as a\n2-layer CNN or a network with two fully-connected layers. In addition,\nthere is a trade-off between scalability and precision due to the cost\nof storing historical information on the federated server. Wu et\nal. (C. Wu et al.\n2022) put forward a knowledge distillation strategy that uses a\nprime global model to train the unlearned model on the remaining data.\nHowever, as the clients’ data is not accessible by the server, some\nunlabeled (synthetic) data that follows the distribution of the whole\ndataset needs to be sampled and extra rounds of information exchange are\nneeded between the clients and server. As a result, the whole process is\ncostly and approximate. Also, it might be further offset when the data\nis non-IID (Yi Liu et\nal. 2022). On another spectrum, Liu et al. (Yi Liu et al. 2022) proposed a smart\nretraining method for federated unlearning without communication\nprotocols. The approach uses the L-BFGS algorithm (Berahas,\nNocedal, et al. 2016; Bollapragada et al. 2018) to efficient\nsolve a Hessian approximation with historical parameter updates for\nglobal model retraining. However, this method is only applicable to\nsmall models (≤ 10K parameters). Plus,\nit involves storing old model snapshots (including historical gradients\nand parameters), which poses some privacy threats.
\n\nSo far the data in machine unlearning settings is assumed to be\nindependent. However, there are many cases where the data samples are\nrelational, such as is the case with graph data. Graph representation\nlearning is a well-established research direction in machine learning,\nspecifically in deep learning (Hamilton 2020; F. Chen et\nal. 2020). However, applying machine unlearning to graph\nrepresentation learning is arguably more challenging. First, the data is\ncorrelated, and it is non-trivial to partition the data, even uniformly.\nSecond, the unlearning requests can happen upon a node or an edge.\nThird, the graph data itself might be non-uniform due to unbalanced\nconnected components in the graph. Therefore, existing graph partition\nmethods might lead to unbalanced data partitions, making the retraining\nprocess non-uniform.
\nTo mitigate these problems, Chen et al. (M. Chen et al. 2021a) proposed a new\ngraph partitioning strategies especially for machine unlearning. The\ngeneral idea is based on the notion of assignment preference that\nrepresents the benefit of a node assigned to a shard (i.e., a data\npartition). Such node-shard pairs are further fine-tuned with neighbor\ncounts, which track down the number of neighbors of a node belonging to\nthe same target shard. The authors also proposed an aggregation method\nto combine different partition strategies. Further, the retraining\nprocess is based on message passing in graph neural networks, which\nfacilitates fast retraining.
\nUnlearning without retraining is also possible for graph embedding.\nHowever, several challenges need to be overcome. The interdependency of\ngraph data, especially across different subgraphs, is non-trivial for\nmodel training. A removal of node and edge could not only cause an\nimpact on its neighbor but also on multi-hops. Cong et al. (Cong and\nMahdavi 2022b, 2022a) proposed a one-shot unlearning solution\nthat only requires access to the data to be forgotten. The idea is\ninspired by the architecture of a linear graph neural network (GNN), in\nwhich non-linearities in a typical GNN are replaced by a single weight\nmatrix between consecutive convolutional layers. Despite its linear span\nover all input node features, such linear-GNNs have shown competent\nperformance, e.g. SGC (F. Wu et al. 2019) and\nAPPNP (Gasteiger, Bojchevski, and\nGünnemann 2019). Using this property, Cong et al. (Cong and\nMahdavi 2022b, 2022a) proposed an exact unlearning process at the\nalgorithmic level based on linear operations such as projection and\nrecombination.
\n\nUnlearning is not always a bad thing for the accuracy of a machine\nlearning model. Machine unlearning has been researched as a\ncountermeasure against catastrophic forgetting in deep neural\nnetworks (Du, Chen,\net al. 2019; Parne et al. 2021; B. Liu, Liu, et al. 2022).\nCatastrophic forgetting is a phenomenon where deep neural networks\nperform badly after learning too many tasks (Kirkpatrick et al. 2017).\nOne naive solution to this problem is training the model on the\nhistorical data again. Clearly, this solution is impractical not only\ndue to computational cost but also because there is no guarantee that\nthe model will converge and nor is there a guarantee that the forgetting\nwill not happen again (Parisi et al. 2019). Du et\nal. (Du, Chen, et al.\n2019) suggested a solution based on unlearning to prevent\ncatastrophic forgetting. The core idea is to unlearn harmful samples\n(e.g., false negatives/positives) and then update the model so that its\nperformance before the forgetting effect is maintained.
\nUnlearning has also been used to handle exploding losses in machine\nlearning. Here, the term loss involves the computation of
Unlearning has been studied for other lifelong settings as well (Parne et al.\n2021). These setting use incremental models, such as decision\ntree and naive Bayes, which allows the model to unlearn data samples\non-the-fly. Liu et al. (B. Liu, Liu, et al. 2022)\nconsidered requests on unlearning specific tasks for lifelong models. In\nparticular, there are three types of requests in lifelong learning: (i)\nto learn a task permanently, (ii) to learn a task temporarily and forget\nit later upon a privacy request, and (iii) to forget a task. Different\nfrom traditional machine unlearning, unlearning in lifelong learning\nneeds to maintain knowledge transfer between tasks but also preserve all\nknowledge for the remaining tasks. Moreover, the setting is more\nchallenging as it depends on the order of tasks as the tasks are learnt\nonline during the model lifetime. Additionally, the model cannot keep\nall previous data (zero-glance unlearning), making the unlearning\nprocess more challenging. Liu et al. (B. Liu, Liu, et al. 2022) proposed\na solution inspired by SISA, the data partitioning mechanism for smart\nretraining (Bourtoule et al. 2021). It\ncreates an isolated temporary model for each task and merges the\nisolated models into the main model.
\n\n\nIn this section, we analyze the current and potential developments in\nmachine unlearning and summarize our findings. In addition, we identify\na number of unanswered research topics that could be addressed to\nprogress the foundation of machine unlearning.
\n\nInfluence functions are dominant methods.\nUnderstanding the impact of a given data item on a model’s parameters or\nmodel performance is the key to machine unlearning (Koh et al. 2017;\nBasu, Pope, and Feizi 2021). Such insights will speed-up the\nunlearning process immensely by simply reversing the model updates\nassociated with the target data. Although there could be some offset in\ndoing so, promising results have shown that this offset can be\nbounded (Mahadevan\nand Mathioudakis 2021, 2022; Chundawat et al. 2022b).
\nReachability of model parameters. Existing works\ndefine unlearning as obtaining a new model with an accuracy as good as\nif the model had retrained without the data to be forgotten (Golatkar,\nAchille, and Soatto 2020b, 2020a; Graves, Nagisetty, and Ganesh 2021;\nThudi, Jia, et al. 2022). We argue that such a parameter-space\nassumption should be taken into serious considerations. As model\nparameters can be reachable with or without some given data, is there\nany case where the original and unlearned models share the same\nparameters? (Thudi, Jia, et al. 2022)\nAlthough some studies use parameter distribution to bound the\nproblem (C. Guo et al.\n2020), there could still be false positive cases, where some\neffects from the forgotten data still exist in the unlearned model.
\nUnlearning verification (Data auditing) is needed.\nUnlearning verification (or data auditing) is the process of determining\nwhether specific data have been eliminated from a model. To fully enable\nregulations over the right to be forgotten, the unlearning effect should\nbe independently verified. There have been only a few works on\nunlearning verification (X. Gao et al. 2022; Y.\nHuang, Li, et al. 2021). However, the definition of a successful\nverification is still controversial as different unlearning solutions\nuse different evaluation metrics, especially when the cutting threshold\nof a verification metric still depends on the application domain (Thudi, Jia, et al.\n2022).
\nFederated unlearning is emerging. Federated learning\nbrings about a unique setting for machine unlearning research (G.\nLiu et al. 2021; J. Wang, Guo, et al. 2022; C. Wu et al. 2022; Yang Liu\net al. 2020). It has separate clients participating in the\nfederated training process. As a result, removing a client out of the\nfederation could be done precisely using historical updates. The\nrational behind this is that the user data on a client mostly helps to\nmake correct predictions about that user. This locality helps to avoid a\ncatastrophic unlearning phenomenon in a traditional machine learning\nsetting. However, we all need to be aware that there are many cases in\nfederated learning where the data is non-IID or the removal request only\ncovers part of the client data.
\nModel repair via unlearning. Machine learning models\ncan be poisoned by adversarial attacks (B. Wang et al. 2019; Yang\nLiu et al. 2022). Intuitively, if the poisonous data is detected\nand removed and then the model is retrained, the new model should be\npoison-free. However, the retraining would be too expensive. This is\nindeed similar to the unlearning setting. Compared to existing defence\nmethods, the models in machine learning determine then update the inner\nproblematic weights through influence functions.
\nA similar application is to remove bias from the model due to some\nbiased feature in the data (Dinsdale,\nJenkinson, and Namburete 2021; Dinsdale, Jenkinson, et al. 2020).\nStatus quo studies on fairness and de-biasing learning mostly focus on\nlearning a fair and unbiased feature representation (Ramaswamy,\nKim, and Russakovsky 2021; Nam et al. 2020; R. Singh et al. 2022; Z.\nWang et al. 2020), where, machine unlearning, e.g. feature\nunlearning (T. Guo\net al. 2022), would ensure the biased features are deleted\nproperly but the model’s quality would still be maintained.
\nIn another setting, machine unlearning can be used to repair\novertrained deep neural networks by actively unlearning useless,\nobsolete, or redundant data samples that could cause catastrophic\nforgetting (Du, Chen, et al. 2019;\nGolatkar, Achille, and Soatto 2020a). Moreover, machine\nunlearning might be used to boost the model’s accuracy as well
There are several open questions that future studies can\naddress. This section will list and discuss those fundamental topics in\nmachine unlearning.
\nUnified Design Requirements. Among the current\nunlearning approaches, there is no absolute winner that satisfies all\ndesign requirements. Most unlearning algorithms focus on approximate\nunlearning scenarios and data item removal (
Unified Benchmarking. Although there have been many\nworks on machine unlearning recently, not many of them have a common\nsetting for benchmarking comparisons. In particular, there is not a lot\nof published source code ([tab:algorithms]) and each of them\ntargets different learning algorithms or different applications\n(e.g. recommender systems, graph embedding). Schelter et al. (Schelter 2020)\nundertook an empirical study but the benchmark was limited to\ndecremental learning methods and focused only on efficiency.
\nAdversarial Machine Unlearning. More studies have\nbeen undertaken on attacking ML systems so that we can gain a better\nunderstanding of and better protect our systems (Veale,\nBinns, and Edwards 2018; B. Wang et al. 2019; K. Ren et al.\n2020). Adversarial machine unlearning is the study of the attacks\non unlearning algorithms to better certify the unlearned models (J. Gao\net al. 2022; Marchant, Rubinstein, and Alfeld 2022). Unlike using\nmachine unlearning to mitigate adversarial attacks (Yang Liu et al.\n2022), adversarial machine unlearning is far stricter, as it\nconcerns not only the model accuracy but also the privacy guarantees.\nFor example, adversarial machine unlearning might not have knowledge of\nthe learning algorithms, but it might have access to the unlearning\nprocess.
\nInterpretable Machine Unlearning. In the future,\nexplanations for machine unlearning can be used to increase confidence\nin human-AI interactions and enable unlearning verification or removed\ndata auditing (X. Gao et al. 2022; Y.\nHuang, Li, et al. 2021). However, the inverted nature of machine\nunlearning might pose problems for explanation methods to be applicable\nat all. Devising techniques aimed at explaining the unlearning process\n(e.g. using influence functions) is still an unsolved task (Koh et al. 2017;\nBasu, Pope, and Feizi 2021).
\nMachine Unlearning in Evolving Data Streams.\nEvolving data streams pose problems to machine learning models,\nespecially neural networks, due to shifts in the data distributions and\nthe model predictions (Haug and Kasneci 2021). Although\nthere are ways to overcome this limitation (Duda et al. 2020), they rely on\nthe changes in the model parameters to detect concept drift (Haug and Kasneci\n2021). However, such detection might be not reliably correct in\nunlearning settings, where the changes in model parameters are\napproximate. Consequently, it is expected that machine learning for\nstreaming removal request may attract more attention in the next few\nyears. It is noteworthy that unlearning might be used to repair obsolete\nmodels by forgetting old data that contradicts with the detected concept\ndrift. However, this requires a contradiction analysis between old and\nnew data (Hu et al.\n2021).
\nA similar setting is the consideration of out-of-distribution (OOD)\ndata in the forget set. For those settings, the unlearning is\nimbalanced. Some data might have no impact while the others have great\ninfluence on the model parameters. There are studies on learning\nalgorithms for OOD data in federated learning (Sattler et al. 2021). Hence, it\nmay be worthwhile investigating novel unlearning algorithms tailored to\nOOD data.
\nCausality in Machine Unlearning. There are cases\nwhere a large amount of data might need to be removed from an machine\nlearning system, even though the portion of data to be forgotten might\nbe insignificant in comparison to all the data. For example, a data\npollution attack might affect millions of data items, but only a few of\nthem can be detected by human experts or SOTA detection methods (Y. Cao et al.\n2018). Causality analysis (R. Guo et al. 2020) could become a\nuseful tool to automatically unlearn the polluted data in this setting\nand guarantee the non-existence of the polluted information in the final\nmodel.
\n\nThis survey is the first to investigate machine unlearning techniques\nin a systematic manner. In this survey, we addressed the primary\ndifficulties and research advancements in conceptualizing, planning, and\nsolving the problems of machine unlearning. In addition, we presented a\nunified taxonomy that divides machine unlearning strategies into three\napproaches: model-agnostic methods, model-intrinsic methods, and\ndata-driven methods. We hope that our taxonomy can help categorize\nfuture studies and gain deeper insight into methodologies as well as\naddress the difficulties in machine unlearning. Also, we expect this\nsurvey can assist researchers in identifying the most optimal unlearning\nstrategies for different applications. The survey provides clear\nsummaries and comparisons between various unlearning methodologies,\ngiving a comprehensive and general view of current work as well as the\ncurrent process of machine unlearning.
","metadata":{}},{"cell_type":"markdown","source":"