# Machine Unlearning for Random Forests

arXiv: https://arxiv.org/abs/2009.05567 · HTML: https://mlsanity.com/paper/2009.05567/

## Key facts

- Cited by 131 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Sep 2020.

## Built on by (most cited first, 30 of 131)

- [A Survey of Machine Unlearning](https://mlsanity.com/paper/2209.02299/) (2022)
- [Fast Yet Effective Machine Unlearning](https://mlsanity.com/paper/2111.08947/) (2021)
- [Can Bad Teaching Induce Forgetting? Unlearning in Deep Networks using an Incompetent Teacher](https://mlsanity.com/paper/2205.08096/) (2022)
- [Graph Unlearning](https://mlsanity.com/paper/2103.14991/) (2021)
- [Training Data Influence Analysis and Estimation: A Survey](https://mlsanity.com/paper/2212.04612/) (2022)
- [Boundary Unlearning](https://mlsanity.com/paper/2303.11570/) (2023)
- [Zero-Shot Machine Unlearning](https://mlsanity.com/paper/2201.05629/) (2022)
- [Continual Learning and Private Unlearning](https://mlsanity.com/paper/2203.12817/) (2022)
- [The Right to be Forgotten in Federated Learning: An Efficient Realization with Rapid Retraining](https://mlsanity.com/paper/2203.07320/) (2022)
- [Federated Unlearning via Class-Discriminative Pruning](https://mlsanity.com/paper/2110.11794/) (2021)
- [Machine Unlearning: Solutions and Challenges](https://mlsanity.com/paper/2308.07061/) (2023)
- [Towards Adversarial Evaluations for Inexact Machine Unlearning](https://mlsanity.com/paper/2201.06640/) (2022)
- [Fast Model Debias with Machine Unlearning](https://mlsanity.com/paper/2310.12560/) (2023)
- [Learning to Unlearn: Instance-wise Unlearning for Pre-trained Classifiers](https://mlsanity.com/paper/2301.11578/) (2023)
- [Exploring the Landscape of Machine Unlearning: A Comprehensive Survey and Taxonomy](https://mlsanity.com/paper/2305.06360/) (2023)
- [Learn What You Want to Unlearn: Unlearning Inversion Attacks against Machine Unlearning](https://mlsanity.com/paper/2404.03233/) (2024)
- [Hidden Poison: Machine Unlearning Enables Camouflaged Poisoning Attacks](https://mlsanity.com/paper/2212.10717/) (2022)
- [GNNDelete: A General Strategy for Unlearning in Graph Neural Networks](https://mlsanity.com/paper/2302.13406/) (2023)
- [Certifiable Machine Unlearning for Linear Models](https://mlsanity.com/paper/2106.15093/) (2021)
- [Evaluating Machine Unlearning via Epistemic Uncertainty](https://mlsanity.com/paper/2208.10836/) (2022)
- [Machine Unlearning: A Comprehensive Survey](https://mlsanity.com/paper/2405.07406/) (2024)
- [A Duty to Forget, a Right to be Assured? Exposing Vulnerabilities in Machine Unlearning Services](https://mlsanity.com/paper/2309.08230/) (2023)
- [Fast Exact Unlearning for In-Context Learning Data for LLMs](https://mlsanity.com/paper/2402.00751/) (2024)
- [Deep Regression Unlearning](https://mlsanity.com/paper/2210.08196/) (2022)
- [A Review on Machine Unlearning](https://mlsanity.com/paper/2411.11315/) (2024)
- [Inductive Graph Unlearning](https://mlsanity.com/paper/2304.03093/) (2023)
- [Towards Certified Unlearning for Deep Neural Networks](https://mlsanity.com/paper/2408.00920/) (2024)
- [Learning with Recoverable Forgetting](https://mlsanity.com/paper/2207.08224/) (2022)
- [Certified Minimax Unlearning with Generalization Rates and Deletion Capacity](https://mlsanity.com/paper/2312.10336/) (2023)
- [Continual Forgetting for Pre-trained Vision Models](https://mlsanity.com/paper/2403.11530/) (2024)

## Abstract (arXiv)

Responding to user data deletion requests, removing noisy examples, or deleting corrupted training data are just a few reasons for wanting to delete instances from a machine learning (ML) model. However, efficiently removing this data from an ML model is generally difficult. In this paper, we introduce data removal-enabled (DaRE) forests, a variant of random forests that enables the removal of training data with minimal retraining. Model updates for each DaRE tree in the forest are exact, meaning that removing instances from a DaRE model yields exactly the same model as retraining from scratch on updated data. DaRE trees use randomness and caching to make data deletion efficient. The upper levels of DaRE trees use random nodes, which choose split attributes and thresholds uniformly at random. These nodes rarely require updates because they only minimally depend on the data. At the lower levels, splits are chosen to greedily optimize a split criterion such as Gini index or mutual information. DaRE trees cache statistics at each node and training data at each leaf, so that only the necessary subtrees are updated as data is removed. For numerical attributes, greedy nodes optimize over a random subset of thresholds, so that they can maintain statistics while approximating the optimal threshold. By adjusting the number of thresholds considered for greedy nodes, and the number of random nodes, DaRE trees can trade off between more accurate predictions and more efficient updates. In experiments on 13 real-world datasets and one synthetic dataset, we find DaRE forests delete data orders of magnitude faster than retraining from scratch while sacrificing little to no predictive power.