Machine Unlearning for Random Forests (2020-09-11T00:00:00.000000Z)

TL;DR

Data removal-enabled (DaRE) forests are introduced, a variant of random forests that enables the removal of training data with minimal retraining, and are found to delete data orders of magnitude faster than retraining from scratch while sacrificing little to no predictive power.

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.

Authors

Jonathan Brophy

2 papers

Daniel Lowd

2 papers

TL;DR

Abstract

Authors

References96 items

HedgeCut: Maintaining Randomised Trees for Low-Latency Machine Unlearning

HYDRA: Hypergradient Data Relevance Analysis for Interpreting Deep Neural Networks

Bayesian Inference Forgetting

Coded Machine Unlearning

Mixed-Privacy Forgetting in Deep Networks

Online Continual Learning from Imbalanced Data

DeltaGrad: Rapid retraining of machine learning models

Differentially Private Median Forests for Regression and Classification

SECure: A Social and Environmental Certificate for AI Systems

Optimal Continual Learning has Perfect Memory and is NP-hard

When Machine Unlearning Jeopardizes Privacy

Towards Probabilistic Verification of Machine Unlearning

Forgetting Outside the Box: Scrubbing Deep Networks of Information Accessible from Input-Output Observations

Formalizing Data Deletion in the Context of the Right to Be Forgotten

Approximate Data Deletion from Machine Learning Models: Algorithms and Evaluations

Machine unlearning: linear filtration for logit-based classifiers

Estimating Training Data Influence by Tracking Gradient Descent

Machine Unlearning

Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks

Certified Data Removal from Machine Learning Models

Lifelong Anomaly Detection Through Unlearning

Analyzing Privacy Loss in Updates of Natural Language Models

Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism

Making AI Forget You: Data Deletion in Machine Learning

Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detection

Making Machine Learning Forget

A novel online incremental and decremental learning algorithm based on variable support vector machine

Neural Cleanse: Identifying and Mitigating Backdoor Attacks in Neural Networks

CALIFORNIA

Representer Point Selection for Explaining Deep Neural Networks

The Secret Sharer: Measuring Unintended Neural Network Memorization & Extracting Secrets

Finding Influential Training Samples for Gradient Boosted Decision Trees

Consistent Individualized Feature Attribution for Tree Ensembles

LightGBM: A Highly Efficient Gradient Boosting Decision Tree

Privacy Risk in Machine Learning: Analyzing the Connection to Overfitting

BadNets: Identifying Vulnerabilities in the Machine Learning Model Supply Chain

Humans forget, machines remember: Artificial intelligence and the Right to Be Forgotten

Bayesian regression tree ensembles that adapt to smoothness and sparsity

CatBoost: unbiased boosting with categorical features

Certified Defenses for Data Poisoning Attacks

Understanding Black-box Predictions via Influence Functions

Decision Tree Classification with Differential Privacy: A Survey

Deep Learning with Differential Privacy

Harnessing the Power of the Crowd to Increase Capacity for Data Science in the Social Sector

Differentially Private Random Decision Forests using Smooth Sensitivity

Neural Random Forests

XGBoost: A Scalable Tree Boosting System

Random Forests for Big Data

Differentially Private Random Forest with High Utility

Systematic Poisoning Attacks on and Defenses for Machine Learning in Healthcare

Estimation and Inference of Heterogeneous Treatment Effects using Random Forests

HSpam14: A Collection of 14 Million Tweets for Hashtag-Oriented Spam Research

Towards Making Systems Forget with Machine Unlearning

The Algorithmic Foundations of Differential Privacy

A data-driven approach to predict the success of bank telemarketing

Quantifying Uncertainty in Random Forests via Confidence Intervals and Hypothesis Tests

Impact of HbA1c Measurement on Hospital Readmission Rates: Analysis of 70,000 Clinical Database Patient Records

Searching for exotic particles in high-energy physics with deep learning

Narrowing the Gap: Random Forests In Theory and In Practice

Tree ensembles for predicting structured outputs

Classification and regression trees

Scikit-learn: Machine Learning in Python

Effect of Subsampling Rate on Subbagging and Related Ensembles of Stable Classifiers

Multiple Incremental Decremental Learning of Support Vector Machines

Differentially Private Empirical Risk Minimization

Incremental and Decremental Learning for Linear Support Vector Machines

Signal Reconstruction From Noisy Random Projections

Differential Privacy

Extremely randomized trees

Incremental and Decremental Proximal Support Vector Classification using Decay Coefficients

Canada

Greedy function approximation: A gradient boosting machine.

Efficient noise-tolerant learning from statistical queries

Linear Model Selection by Cross-validation

C4.5: Programs for Machine Learning

The meaning and use of the area under a receiver operating characteristic (ROC) curve.