Abstract
Today's systems produce a rapidly exploding amount of data, and the data further derives more data, forming a complex data propagation network that we call the data's lineage. There are many reasons that users want systems to forget certain data including its lineage. From a privacy perspective, users who become concerned with new privacy risks of a system often want the system to forget their data and lineage. From a security perspective, if an attacker pollutes an anomaly detector by injecting manually crafted data into the training data set, the detector must forget the injected data to regain security. From a usability perspective, a user can remove noise and incorrect entries so that a recommendation engine gives useful recommendations. Therefore, we envision forgetting systems, capable of forgetting certain data and their lineages, completely and quickly. This paper focuses on making learning systems forget, the process of which we call machine unlearning, or simply unlearning. We present a general, efficient unlearning approach by transforming learning algorithms used by a system into a summation form. To forget a training data sample, our approach simply updates a small number of summations -- asymptotically faster than retraining from scratch. Our approach is general, because the summation form is from the statistical query learning in which many machine learning algorithms can be implemented. Our approach also applies to all stages of machine learning, including feature selection and modeling. Our evaluation, on four diverse learning systems and real-world workloads, shows that our approach is general, effective, fast, and easy to use.
Introduction
In modern data-driven systems, a single user action—such as a movie rating or a search query—propagates through complex pipelines to influence final system behavior. This propagation creates a "data lineage." Traditionally, removing the influence of a specific data point required deleting the source data and retraining the entire model from scratch, a process that is computationally prohibitive for large-scale systems.
The need for "forgetting" systems is driven by three primary factors:
- Privacy: The "right to be forgotten" is increasingly critical as new privacy risks, such as model inversion attacks, are discovered.
- Security: Systems must be able to purge malicious influence from "poisoned" training data used by attackers to create backdoors.
- Usability: Users often need to clear accidental or incorrect entries to correct skewed recommendations or system outputs.
Methodology: The Summation Form
The core innovation of this work is the transformation of standard learning algorithms into a summation form, inspired by Statistical Query (SQ) learning. Instead of the model depending directly on individual raw data samples, the algorithms are modified to depend on a small number of summations of transformed data.
The Unlearning Process
To forget a specific data point, the system calculates the transformation of that point and subtracts it from the global summations. The model is then updated using these new totals.
- Non-adaptive Algorithms: For models like Naive Bayes or Chi-squared tests, unlearning is nearly instantaneous through direct subtraction.
- Adaptive Algorithms: For iterative models like k-means clustering or Support Vector Machines (SVMs), the system uses a "resume" strategy. After updating summations, training restarts from the model's previous converged state. Since the change is typically small, the model reaches its new "clean" state much faster than starting from scratch.
Evaluation and Results
The approach was evaluated on four diverse, real-world systems: LensKit (recommendations), Zozzle (JavaScript malware detection), OSNSF (social network spam filtering), and PJScan (PDF malware detection).
Key Findings
- Massive Speedups: In the Zozzle malware detector, retraining from scratch took over a day. Machine unlearning reduced this to less than one second (987ms)—a speedup of over 90,000x.
- Perfect Completeness: For most systems (LensKit, Zozzle, PJScan), the unlearned model was mathematically identical to a model retrained from scratch (100% completeness).
- Restoring Security: A pollution attack on Zozzle that dropped detection from 93.1% to 37.8% was completely reversed through unlearning, restoring the detection rate exactly to its original level.
- Minimal Implementation Effort: Implementing unlearning required modifying less than 1% of the total lines of code in the tested systems, demonstrating high practicality for existing production environments.
Conclusion and Future Work
Machine unlearning provides a general and efficient framework for making systems forget. By leveraging the summation form, it turns an $O(N)$ retraining problem into a near-constant time update. While highly effective for small batches of data, future work may explore more complex transformations for non-statistical models and automated methods for identifying the specific data points that need to be forgotten.
Summary updated