CoChat
Sign Up
PreprintCited by 70Privacy-Preserving Technologies in DataMachine Learning and Data ClassificationData Stream Mining Techniques

Machine Unlearning for Random Forests

Open access
Brophy, Jonathan, Lowd, Daniel·2020·arXiv
DOI 10.48550/arxiv.2009.05567arXiv 2009.05567
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2009.05567

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Schelter et al. [57], Brophy et al. [58], and Wu et al. [60] only provide evaluations in terms of runtime and accuracy, and they do not provide reasonable experimental or theoretical verifiability guarantees of their unlearning processes.

    “Schelter et al. [57], Brophy et al. [58], and Wu et al. [60] only provide evaluations in terms of runtime and accuracy, and they do not provide reasonable experimental or theoretical verifiability guarantees of their unlearning processes.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [58]

    The Methodology (§4.1, p. 5) evaluates deletion speed and predictive performance, supporting the runtime-and-accuracy portion. But Theorem 3.1 (§3, p. 2), with its proof in Appendix A.1 (p. 14), states that DaRE forests provide exact deletion, contradicting the claim that Brophy et al. provide no theoretical unlearning guarantee. (LLM, conf=0.94)

    Experimental — accuracy not yet measured

  • The above two schemes (Hedgecut and DaRE) need to compute a large number of possible tree structures in advance, which would cost a large number of storage resources.

    “The above two schemes need to compute a large number of possible tree structures in advance, which would cost a large number of storage resources [57, 58].”

    From Machine Unlearning: A Survey (2024) · cites this paper as [58]

    Section 4.4 (p. 7) confirms substantial storage overhead for DaRE forests: 6–26 times the memory of a standard random forest when training data is included. But Section 3.1 (p. 3) says DaRE stores node statistics and leaf-instance lists, then retrains a subtree if a deletion changes its split; it does not precompute numerous possible tree structures. This paper also does not establish the claim about Hedgecut. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • DaRE is mainly based on the idea of retraining subtrees only as needed.

    “DaRE is mainly based on the idea of retraining subtrees only as needed.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [58]

  • Before the unlearning process in DaRE, most k randomly selected thresholds per attribute are computed, and intermediate statistics data are stored within each node in advance.

    “Before the unlearning process, most k randomly selected thresholds per attribute are computed, and intermediate statistics data are stored within each node in advance.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [58]

  • Brophy et al. [58] proposed DaRE (Data Removal-Enabled) forests, a random forest variant that enables the efficient removal of training samples.

    “For the tree-based models, Brophy et al. [58] also proposed DaRE (Data Removal-Enabled) forests, a random forest variant that enables the efficient removal of training samples.”

    From Machine Unlearning: A Survey (2024) · cites this paper as [58]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 58

  1. Aldaghri, N., Mahdavifar, H., and Beirami, A. Coded machine unlearning. arXiv preprint arXiv:2012.15721 , 2020. · arXiv
  2. Baumhauer, T., Sch¨ ottle, P., and Zeppelzauer, M. Machine unlearning: Linear filtration for logit-based classifiers. arXiv preprint arXiv:2002.02730 , 2020. · arXiv
  3. Bourtoule, L., Chandrasekaran, V., Choquette-Choo, C., et al. Machine unlearning. In IEEE Symposium on Security and Privacy , 2021.
  4. Breiman, L., Friedman, J., Olshen, R. A., and Stone, C. J. Classification and Regression Trees . CRC Press, 1984.
  5. Bull, P., Slavitt, I., and Lipstein, G. Harnessing the power of the crowd to increase capacity for data science in the social sector. In ICML #Data4Good Workshop , 2016.
  6. Cao, Y. and Yang, J. Towards making systems forget with machine unlearning. In IEEE Symposium on Security and Privacy , 2015.
  7. Carlini, N., Liu, C., et al. The secret sharer: Measuring unintended neural network memorization & extracting secrets. arXiv preprint arXiv:1802.08232 , 2018. · arXiv
  8. Cauwenberghs, G. and Poggio, T. Incremental and decremental support vector machine learning. In NeurIPS , 2001.
  9. Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. Differentially private empirical risk minimization. JMLR , 2011.
  10. Chen, M., Zhang, Z., et al. When machine unlearning jeopardizes privacy. arXiv preprint arXiv:2005.02205 , 2020. · arXiv
  11. Chen, T. and Guestrin, C. XGBoost: A scalable tree boosting system. In KDD , 2016.
  12. Chen, Y., Li, B., Yu, H., Wu, P., and Miao, C. Hydra: Hypergradient data relevance analysis for interpreting deep neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence , 2021.
  13. Chrysakis, A. and Moens, M.-F. Online continual learning from imbalanced data. In ICML , 2020.
  14. Consul, S. and Williamson, S. Differentially private median forests for regression and classification. arXiv preprint arXiv:2006.08795 , 2020. · arXiv
  15. Denil, M., Matheson, D., and De Freitas, N. Narrowing the gap: Random forests in theory and in practice. In ICML , 2014.
  16. Dong, Y., Hopkins, S., and Li, J. Quantum entropy scoring for fast robust mean estimation and improved outlier detection. In NeurIPS , 2019.
  17. Fletcher, S. and Islam, M. Z. Decision tree classification with differential privacy: A survey. ACM Computing Surveys , 2019.
  18. Friedman, J. H. Greedy function approximation: a gradient boosting machine. Annals of Statistics , 2001.
  19. Fu, S., He, F., Xu, Y., and Tao, D. Bayesian inference forgetting. arXiv preprint arXiv:2101.06417 , 2021. · arXiv
  20. Garg, S., Goldwasser, S., and Vasudevan, P. N. Formalizing data deletion in the context of the right to be forgotten. arXiv preprint arXiv:2002.10635 , 2020. · arXiv
  21. Golatkar, A., Achille, A., Ravichandran, A., Polito, M., and Soatto, S. Mixed-privacy forgetting in deep networks. arXiv preprint arXiv:2012.13431 , 2020a. · arXiv
  22. Golatkar, A., Achille, A., and Soatto, S. Forgetting outside the box: Scrubbing deep networks of information accessible from input-output observations. arXiv preprint arXiv:2003.02960 , 2020b. · arXiv
  23. Golatkar, A., Achille, A., and Soatto, S. Eternal sunshine of the spotless net: Selective forgetting in deep networks. In CVPR , 2020c.
  24. Gu, T., Dolan-Gavitt, B., and Garg, S. Badnets: Identifying vulnerabilities in the machine learning model supply chain. In Machine Learning and Computer Security Workshop , 2017.
  25. Guo, C., Goldstein, T., Hannun, A., and van der Maaten, L. Certified data removal from machine learning models. In ICML , 2020.
  26. Gupta, A., Lanteigne, C., and Kingsley, S. SECure: A social and environmental certificate for AI systems. In ICML Deploying and Monitoring Machine Learning Systems Workshop , 2020.
  27. Haupt, J. and Nowak, R. Signal reconstruction from noisy random projections. IEEE Transactions on Information Theory , 2006.
  28. Izzo, Z., Smart, M. A., Chaudhuri, K., and Zou, J. Approximate data deletion from machine learning models: Algorithms and evaluations. arXiv preprint arXiv:2002.10077 , 2020. · arXiv
  29. Karasuyama, M. and Takeuchi, I. Multiple incremental decremental learning of support vector machines. In NeurIPS , 2009.
  30. Ke, G., Meng, Q., et al. LightGBM: A highly efficient gradient boosting decision tree. In NeurIPS , 2017.
  31. Kearns, M. Efficient noise-tolerant learning from statistical queries. Journal of the ACM (JACM) , 1998.
  32. Knoblauch, J., Husain, H., and Diethe, T. Optimal continual learning has perfect memory and is NP-hard. In ICML , 2020.
  33. Koh, P. W. and Liang, P. Understanding black-box predictions via influence functions. In ICML , 2017.
  34. Linero, A. R. and Yang, Y. Bayesian regression tree ensembles that adapt to smoothness and sparsity. Journal of the Royal Statistical Society , 2018.
  35. Lloyd, S. Least squares quantization in PCM. IEEE Transactions on Information Theory , 1982.
  36. Lundberg, S. M., Erion, G. G., and Lee, S.-I. Consistent individualized feature attribution for tree ensembles. arXiv preprint arXiv:1802.03888 , 2018. · arXiv
  37. Mentch, L. and Hooker, G. Quantifying uncertainty in random forests via confidence intervals and hypothesis tests. Journal of Machine Learning Research , 2016.
  38. Mozaffari-Kermani, M., Sur-Kolay, S., et al. Systematic poisoning attacks on and defenses for machine learning in healthcare. Journal of Biomedical and Health Informatics , 2014.
  39. Pedregosa, F., Varoquaux, G., Gramfort, A., et al. Scikitlearn: Machine learning in Python. JMLR , 2011.
  40. Prokhorenkova, L., Gusev, G., et al. CatBoost: Unbiased boosting with categorical features. In NeurIPS , 2018.
  41. Pruthi, G., Liu, F., Kale, S., and Sundararajan, M. Estimating training data influence by tracing gradient descent. Advances in Neural Information Processing Systems , 33, 2020.
  42. Quinlan, J. R. C4.5: Programs for Machine Learning . Elsevier, 2014.
  43. Rahmani, M. and Li, P. Outlier detection and robust PCA using a convex measure of innovation. In NeurIPS , 2019.
  44. Rana, S., Gupta, S. K., and Venkatesh, S. Differentially private random forest with high utility. In ICDM , 2015.
  45. Romero, E., Barrio, I., and Belanche, L. Incremental and decremental learning for linear support vector machines. In International Conference on Artificial Neural Networks , 2007.
  46. Schelter, S., Grafberger, S., and Dunning, T. Hedgecut: Maintaining randomised trees for low-latency machine unlearning. In Proceedings of the 2021 ACM SIGMOD International Conference on Management of Data , 2021.
  47. Sedhai, S. and Sun, A. Hspam14: A collection of 14 million tweets for hashtag-oriented spam research. In SIGIR , 2015.
  48. Shao, J. Linear model selection by cross-validation. Journal of the American Statistical Association , 1993.
  49. Sharchilev, B., Ustinovskiy, Y., Serdyukov, P., and de Rijke, M. Finding influential training samples for gradient boosted decision trees. In ICML , 2018.
  50. Shoeybi, M., Patwary, M., et al. Megatron-LM: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv:1909.08053 , 2019. · arXiv
  51. Sommer, D. M., Song, L., Wagh, S., and Mittal, P. Towards probabilistic verification of machine unlearning. arXiv preprint arXiv:2003.04247 , 2020. · arXiv
  52. Steinhardt, J., Koh, P. W. W., and Liang, P. S. Certified defenses for data poisoning attacks. In NeurIPS , 2017.
  53. Tople, S., Brockschmidt, M., et al. Analyzing privacy loss in updates of natural language models. arXiv preprint arXiv:1912.07942 , 2019. · arXiv
  54. Villaronga, E. F., Kieseberg, P., and Li, T. Humans forget, machines remember: Artificial intelligence and the right to be forgotten. Computer Law & Security Review , 2018.
  55. Wager, S. and Athey, S. Estimation and inference of heterogeneous treatment effects using random forests. Journal of the American Statistical Association , 2018.
  56. Wang, B., Yao, Y., et al. Neural cleanse: Identifying and mitigating backdoor attacks in neural networks. In IEEE Symposium on Security and Privacy , 2019.
  57. Wu, Y., Dobriban, E., and Davidson, S. B. DeltaGrad: Rapid retraining of machine learning models. In ICML , 2020.
  58. Yeh, C.-K., Kim, J., et al. Representer point selection for explaining deep neural networks. In NeurIPS , 2018.

Cited by

Sorted by citations

Authors
Brophy, J., & Lowd, D.
Affiliations
University of Oregon (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
Pages
1092-1104
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2009.05567
arXiv
2009.05567
OpenAlex
W3171516653
Cited by
70
References
2
Citations by year
2025: 8 · 2024: 27 · 2023: 21 · 2022: 10 · 2021: 4
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
  • International Conference on Machine Learning
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Privacy-Preserving Technologies in Data
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Data Classification
  • Physical Sciences › Computer Science › Artificial Intelligence › Data Stream Mining Techniques
Keywords
machine unlearning, random forest, data deletion, model updating, threshold optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review