Machine Unlearning for Random Forests

Jonathan Brophy; Daniel Lowd

Source-linked AI summary

Machine Unlearning for Random Forests

Jonathan Brophy, Daniel Lowd

arXiv:2009.05567v2Sep 11, 2020cs.LGstat.ML

TL;DR

Removing data from machine-learning models is costly when exact retraining must be repeated for growing datasets and deletion requests. The paper introduces DaRE forests, which use exact subtree updates, caching, sampled thresholds, and random upper-level nodes. Across experiments, DaRE forests delete data orders of magnitude faster than naive retraining with little or no accuracy loss.

Problem
Efficient exact deletion is difficult because naive retraining becomes prohibitively expensive as datasets, model complexity, and deletion-request counts increase.
Method
DaRE forests use randomized upper-level splits, sampled thresholds, cached statistics, and selective subtree retraining to update random forests after deletions.
Results
2-3 orders of magnitude faster deletion was achieved on average than naive retraining, with no loss in accuracy.
Takeaways & Limitations
Exact deletion also supports membership-inference resistance for deleted instances and more efficient leave-one-out instance-attribution analysis in random forests.
Takeaways & Limitations
In the worst case, if every tree's root split changes, DaRE deletion is no better than naive retraining; the method also omits bootstrapping.

Abstract

from arXiv · show

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.

1. Introduction

Legal data-deletion requests can require updating models, but retraining from scratch becomes prohibitively expensive. DaRE forests address limited efficient-deletion work for tree-based models with targeted retraining and randomized structures.

Motivation: Legal requirements to remove private user data can require updating models trained on that data.The cost of retraining grows with dataset size, model complexity, and deletion-request frequency.
Motivation: Retraining from scratch on revised data wastes time and computational resources as datasets and models grow.
Background: Decision trees and random forests are widely used because of their predictive performance across classification and regression tasks.
Research gap: Prior efficient-deletion research addressed several model families, but very limited work addressed tree-based models.
Contribution: DaRE forests support efficient instance removal by retraining only necessary subtrees, sampling thresholds, and placing random nodes near tree tops.
Contribution: The paper provides algorithms for training DaRE forests and subsequently removing data from them.

3. We evaluate DaRE RF’s ability to efficiently perform

Across 13 real-world binary-classification datasets and one synthetic dataset, DaRE RF deletes data substantially faster than retraining from scratch while preserving predictive performance closely.

Evaluation: 2-4 orders of magnitude faster deletion was typical for DaRE RF than retraining from scratch, with less than 1% predictive-performance sacrifice.

2. Problem Formulation

The paper defines exact unlearning as removing an instance's influence while matching retraining on the reduced dataset, then reviews the decision-tree and random-forest setting.

2. Problem Formulation: The training dataset is modeled as labeled instances in a p-dimensional attribute space.
2.1. Unlearning: Exact unlearning requires the removal method to be equivalent to applying the training algorithm after deleting an instance.
2.1. Unlearning: For randomized training, equivalence means identical probabilities for every model in the hypothesis space.
2.1. Unlearning: Naive retraining reruns the learning algorithm on the updated dataset, but becomes prohibitively expensive as data, model complexity, and deletion requests increase.
2.2. Random Forests: A decision tree associates binary predictions with leaves and attribute-threshold decisions with internal nodes.
2.2. Random Forests: Tree prediction traverses branches consistent with an input until reaching a leaf whose value supplies the prediction.
2.2. Random Forests: Decision-tree splits recursively choose attributes and thresholds optimizing criteria such as Gini index or entropy.
2.2. Random Forests: Random forests ensemble decision trees and use bootstrap samples plus random attribute subsets to increase tree diversity.

3. DaRE Forests

DaRE forests make exact deletion efficient by caching node and leaf information, limiting threshold candidates, and using random upper-level splits so only affected subtrees are retrained.

3. DaRE Forests: DaRE forests are random-forest variants designed to enable efficient training-instance removal.
3. DaRE Forests: DaRE deletion is exact: removing instances yields exactly the model obtained by retraining from scratch on updated data.
3. DaRE Forests: Each tree trains independently on the full data copy while considering a random subset of attributes at each split.
3. DaRE Forests: DaRE improves deletion efficiency by retraining only changed subtrees, sampling at most k thresholds per attribute, and adding random upper nodes.
3. DaRE Forests: Cached decision-node statistics and leaf instance lists let deletions update criteria and recover subtree training data without scanning all data.
3.2. Sampling Valid Thresholds: Valid continuous thresholds lie between adjacent feature values with opposite labels, and DaRE samples k such thresholds for split selection.
3.3. Random Splits: Random nodes sample attributes and thresholds independently of split criteria, typically requiring retraining only when the threshold leaves its data range.
3.3. Random Splits: Upper random nodes reduce expensive retraining while lower greedy nodes preserve comparable predictive performance; G-DaRE uses drmax=0.

4. Experimental Evaluation

Across 13 real-world and one synthetic dataset, DaRE forests delete training instances substantially faster than naive retraining while preserving predictive performance. Experiments also show tunable trade-offs among deletion efficiency, predictive accuracy, retraining cost, and memory overhead.

Deletion efficiency results: G-DaRE RF is usually at least two orders of magnitude faster than naive retraining under the random adversary, while R-DaRE RF is faster still with typically within 1% test-error difference.R-DaRE performance depends on the tolerance used to tune drmax.
Deletion efficiency results: 17,000+ instances were deleted by R-DaRE RF in the 1.3 hours naive retraining needed to delete one Higgs instance, with only a 0.5% average test-error increase.This corresponds to an average of 0.283s per deletion and over four orders of magnitude speedup.
Deletion efficiency results: 250x is the geometric-mean speedup of G-DaRE RF over naive retraining across 14 datasets under random deletions.R-DaRE models reach 360x to over 1,200x depending on predictive-performance tolerance.
Deletion efficiency results: Against the worst-of-1000 adversary, G-DaRE RF remains more than 50x faster than naive retraining, while R-DaRE RF achieves 80x to 260x speedups.The adversary reduces speedups by forcing more costly retraining, but DaRE retains a substantial advantage.
Effect of drmax and k: Increasing drmax improves deletion efficiency but initially degrades predictive performance gradually; replacing the top ten layers with random nodes increases test error by 0.346%.The worst-of-1000 adversary especially increases retraining cost at larger depths because deeper nodes contain fewer instances and are more sensitive to deletions.
Effect of drmax and k: Increasing k creates a trade-off between predictive performance and deletion efficiency, while modest k values can retain competitive accuracy, high efficiency, and low storage costs.The analysis is reported for the Surgical dataset with drmax fixed at 0, with similar trends on other datasets stated in the caption.
Space overhead: 6–26x is the relative memory overhead of G-DaRE RF, measured after including training data and compared with an SKLearn RF using the same T and dmax.Decision-node statistics usually dominate the overhead, although training-instance pointers dominate for Credit Card and CTR.

5. Related Work

Prior unlearning work spans exact and approximate methods, mitigation techniques, and differential privacy, but efficient deletion for tree-based models remains limited.

Exact unlearning methods have been developed for SVMs and several non-adaptive SQ-learning models.
Approximate unlearning provides an epsilon-certified removal guarantee, while neural-network scrubbing avoids retraining but can have high computational complexity.
Mitigation methods address private, poisoned, or corrupted training data but do not generally guarantee how completely problematic instances are removed from the model.
Differential privacy is sufficient but unnecessarily strict for approximate unlearning, and differentially private random forests often have poor predictive performance.

6. Discussion

DaRE forests support privacy-related deletion and additional model-maintenance applications, including instance attribution, dataset cleaning, continual learning, and reduced retraining costs.

Exact DaRE deletions guarantee unsuccessful membership inference attacks for instances removed from the model.However, access to models before and after deletion can reveal which instances were deleted.
DaRE models can compute the same training-instance attributions as naive leave-one-out retraining more efficiently for random forest predictions.
DaRE methods can efficiently remove outliers and noisy, corrupted, or poisoned training instances.
DaRE methods support adding and removing data for continual learning with streaming data, although hyperparameters may require periodic retuning as data shifts.
Avoiding frequent retraining can spare significant time and computational resources, supporting more economically and environmentally sustainable learning systems.

7. Conclusion

DaRE RF enables efficient updates after repeated training-instance deletions without retraining from scratch. Experiments report substantial speedups with little or no accuracy loss, while allowing further applications and extensions.

DaRE models are 2-3 orders of magnitude faster than naive retraining on average, with no loss in accuracy.
At its best, DaRE RF was more than four orders of magnitude faster than naive retraining.
The authors identify applications spanning user privacy, interpretable models, and data cleaning, and propose extending DaRE forests to boosted trees.

A.1. Exact Deletion: Proof of Theorem 3.1

The exact-deletion proof shows that updating invalidated thresholds and relevant tree components preserves the same model distribution as retraining on the updated data.

A.1. Exact Deletion: Proof of Theorem 3.1: The proof uses a lemma stating that resampling invalidated thresholds after deletion is equivalent to sampling valid thresholds from the updated dataset.
A.1. Exact Deletion: Proof of Theorem 3.1: When multiple thresholds become invalid, the argument reduces to sequential single-threshold invalidations and preserves uniformity by induction.
A.1. Exact Deletion: Proof of Theorem 3.1: The theorem defines DaRE deletion as exact because removing instances yields exactly the same model as retraining on updated data.
A.1. Exact Deletion: Proof of Theorem 3.1: For discrete attributes, updated node statistics produce the same tree structure distribution as initial learning on the revised data.
A.1. Exact Deletion: Proof of Theorem 3.1: For continuous attributes, DaRE samples k thresholds uniformly from valid thresholds and resamples any that become invalid after deletion.
A.1. Exact Deletion: Proof of Theorem 3.1: The threshold-set distribution remains uniform after resampling, matching the distribution obtained by retraining from scratch on updated data.
A.1. Exact Deletion: Proof of Theorem 3.1: Updating all affected decision and leaf nodes yields a tree, and independently updating every tree yields a forest distributed as retraining from scratch.

A.2. Training Complexity: Proof of Theorem 3.2

DaRE forest training scales linearly with the number of trees, sampled attributes, training instances, and maximum depth. Deletion is usually cheap when the tree structure remains valid, but invalid thresholds or changed splits trigger additional work.

Training a DaRE forest takes O(T ˜p n dmax) time.Here, n is the dataset size, T the number of trees, dmax the maximum depth, and ˜p the number of sampled attributes.
At each depth, split selection processes all n instances across the nodes using ˜p sampled attributes.The total work across all nodes at a given depth is O(˜p n).
Deleting one instance takes O(˜p k dmax) when the tree structure and thresholds remain valid.Invalid thresholds add O(|D| log |D|), while retraining a subtree at depth d adds O(˜p |D| (dmax −d)).
Deletion traverses the affected path, updates statistics, optionally retrains a subtree, and removes the instance from its leaf storage.Split scores are recomputed from cached statistics rather than by iterating through all training data.

A.4. Space Complexity: Proof of Theorem 3.4

DaRE forest space usage is driven by cached threshold statistics, tree depth, the number of trees, and stored training-instance pointers. The paper also gives a worst-case bound proportional to dataset size, thresholds, and forest size.

A DaRE forest requires O(k ˜p 2dmax T + n T) space.The first term stores threshold-related metadata across tree nodes; the second stores training-instance pointers across trees.
With at least one instance per leaf, the forest also has the alternate bound O(k˜pnT).This follows from at most n leaves and at most 2n −1 total nodes per tree.
Naive retraining costs O(T ˜p n dmax), while partial retraining is bounded by at most a dmax-fold gain and is smaller in practice.The bound is 10-20 in the reported experiments and excludes additional lower-level retraining costs.
DaRE stores node counts, threshold statistics, and leaf instance pointers to support exact updates without scanning all data.Greedy nodes cache statistics for sampled thresholds, random nodes track branch counts, and leaves retain training-instance pointers.
Batch deletion can retrain each affected node at most once, though waiting to accumulate a batch may be impractical.The algorithms train trees recursively and update affected nodes along deletion paths.
Random and greedy nodes use cached counts and sampled thresholds, updating or retraining only when deletion invalidates their decisions.Greedy nodes resample invalid attributes or thresholds and retrain both child subtrees when the optimal split changes.

B.1. Datasets

The evaluation covers 13 real-world binary-classification datasets and one synthetic dataset, using task-appropriate predictive metrics and comparisons with established tree ensembles. G-DaRE generally matches or exceeds SKLearn RF performance.

The benchmark includes datasets spanning medical, financial, marketing, transportation, social-media, demographic, and synthetic classification tasks.Examples include Surgical, Credit Card, Vaccine, Adult, Bank Marketing, Flight Delays, Twitter, Census, and Synthetic.
Average precision is used below 1% positive labels, AUC between 1% and 20%, and accuracy for the remaining datasets.Datasets without designated splits use an 80% training and 20% testing split after preprocessing.
The comparison includes Random Trees, Extra Trees, SKLearn RF, and SKLearn RF with bootstrapping.Models are tuned using five-fold cross-validation, with forest size and maximum depth searched across specified grids.
G-DaRE and SKLearn RF scores are within 0.2% on 9/14 datasets and within 0.4% on 1/14 datasets.G-DaRE RF is significantly better on Surgical, Flight Delays, Olympics, and Credit Card.
Random Trees and Extra Trees have consistently worse predictive performance than SKLearn and G-DaRE models.The table reports AP, AUC, or accuracy averaged over five runs with standard errors.

C. Additional Experiments

Using entropy instead of Gini produces nearly identical predictive performance and the same deletion-efficiency trends. The corresponding results are summarized in Tables 8 and 9.

Entropy yields nearly identical predictive performance to the Gini-index experiments.The selected entropy-based hyperparameters are reported in Table 8.
Deletion efficiency under entropy follows the same overall trends as the Gini-index results.The entropy-based deletion-efficiency summary is reported in Table 9.