Abstract

1
Introduction
Recent legislation (California 2018; EU 2016; Canada 2018) requiring companies to remove private user data upon request has prompted new discussions on data privacy and owner- ship (Shintre, Roundy, and Dhaliwal 2019). Fulfilling this "right to be forgotten" (Garg, Goldwasser, and Vasudevan 2020; Kwak, Lee et al. 2017) may require updating any mod- els trained on this data (Villaronga, Kieseberg, and Li 2018). Models also need to be updated as new data is acquired, to reflect new patterns and trends. Retraining a model from scratch on a revised dataset becomes prohibitively expensive as the size and complexity of a model increases (Shoeybi, Patwary et al. 2019), taking longer to train a new model and using more computational resources; this problem is exacer- bated as the frequency of data updates or removal requests increases. Decision trees and random forests (Breiman et al. 1984; Friedman 2001) are popular and widely used machine learn- ing models (Lundberg, Erion, and Lee 2018), mainly due to their predictive prowess on many classification and regres- sion tasks (Biau, Scornet, and Welbl 2019; Kocev, Vens et al. 2013; Genuer et al. 2017; Wager and Athey 2018; Linero and Yang 2018). Current work on deleting data from ma- chine learning models has focused mainly on recommender systems (Cao and Yang 2015; Schelter 2020), K-means (Gi- nart et al. 2019), SVMs (Cauwenberghs and Poggio 2001), logistic regression (Guo et al. 2020; Schelter 2020), and deep neural networks (Baumhauer, Schöttle, and Zeppelza- uer 2020; Golatkar, Achille, and Soatto 2020b; Wu, Dobriban, and Davidson 2020) (for a comprehensive list of related work, see Section 6); however, there is currently no work address- ing the problem of efficiently deleting data from decision trees and random forests. Thus, we outline our contributions as follows: ●  We propose DART (Data Addition and Removal Trees), a stochastic variant of decision trees that supports efficient addition and removal of training instances. DART works with discrete tree structures, in contrast to many related works that assume continuous parameters. Our key ideas are to only retrain subtrees as needed and to strategically place completely random nodes near the top of the tree to avoid costly retraining. ● We provide algorithms for training a DART model, and subsequently updating that model given a training example to add or remove. ● We introduce CEDR, a baseline that implements certified removal in decision trees. ● We apply our approach to sequences of additions and dele- tions, evaluated on ten real-world datasets and one syn- thetic dataset, and find that our method can be over 50,000 times faster than retraining from scratch while achieving nearly the same predictive performance.
2
Problem Formulation
This section provides a primer on decision tree models, and introduces the problems faced when attempting to efficiently add or delete data from them. We assume an instance space X with n samples defined over p attributes, { x i,1, x i,2, . . . , x i,p } i =1. Without loss of generality, we assume that all attributes are binary. In bi- nary classification, our goal is to find a function f : X → {−1, +1} that maps each instance to either the positive (+1) or negative (−1) class. A decision tree is a tree-structured model in which each leaf is associated with a categorical or binary-valued pre- diction and each internal node is a decision node associated with an attribute a . The outgoing branches of the decision node define a partition over the values of the chosen attribute. Given x ∈ X , the prediction of a decision tree can be found by traversing the tree, starting at the root and following the branches consistent with the attribute values in x . Traversal ends at one of the leaf nodes, where the prediction is equal to the value of the leaf node. Decision trees are typically learned in a recursive manner, beginning by picking an attribute a for the root to maximize an empirical split criterion such as Gini index (Breiman et al. 1984):
or entropy (Quinlan 2014):
in which D is the dataset input at a given decision node (in this case, the root node), D v are the samples in D where attribute a takes on value v , and D v,c are the samples in D where attribute a takes on value v and class label c . Once an attribute has been chosen for the root node, the data is partitioned into subsets based on the value of the attribute a , and a child node is learned for each data subset. The process terminates when the entire data subset has the same label or the tree reaches a specified maximum depth. A random forest (RF) is an ensemble of decision trees which predicts the mean value . The prediction of the forest is the mean value over the predictions of all trees in the set. Two sources of randomness are used to increase diversity among the trees. The first source of randomness is in the training data: each tree in the ensemble is trained from a bootstrap sample of the original training data, with some examples excluded and some included multiple times. The second source of randomness is in the splits: each decision node is restricted to a random subset of attributes, and the split criterion is maximized over this subset rather than over all attributes. We base our proposed methods on a minor variation of stan- dard RFs, making two changes that simplify implementation without hurting accuracy. First, we do not use bootstrapping. Bootstrapping complicates adding and removing training ex- amples, since one example may appear multiple times in the training data for one tree. There is empirical evidence that bootstrapping does not improve predictive performance (De- nil, Matheson, and De Freitas 2014; Mentch and Hooker 2016; Zaman and Hirose 2009), and indeed our own pre- liminary experiments did not demonstrate any advantage of a tuned bootstrapped model over a tuned non-bootstrapped model. Second, we choose the random subset of attributes once per tree rather than once per node. In our preliminary experiments, we found that the predictive performance was very similar to the standard implementation in scikit-learn. Our methods could be extended to include RF models with bootstrapping and different feature sets at each node, but with some additional bookkeeping to keep track of the examples for each tree and the attributes for each node. Since predictive performance was already similar, we saw no need to add this complexity. Naive Retraining Given an instance x to add/remove from a model, one can always add/delete x from the database and retrain from scratch; we denote this the naive retrain- ing approach. This method is beneficial in that it is agnostic to virtually all machine learning models, and also easy to understand and implement. However, as previously stated, this approach becomes prohibitively expensive as the dataset size and/or model complexity increases, requiring more com- putational resources especially as addition/deletion requests increase.
3
DART
We now describe DART (Data Addition and Removal Trees), an RF variant that supports efficient addition and removal of training examples. Data updates in DART are exact , meaning that adding or removing examples from a DART model yields exactly the same model as retraining from scratch on updated data (assuming a fixed random seed). This is equivalent to certified removal with ε = 0. A DART model is a tree ensemble where each tree is trained independently on a copy of the training data, restricted to a random subset of the attributes to encourage diversity among the trees. Since each tree is trained independently, we describe our methods in terms of training and updating a single tree; the extension to the ensemble is trivial. DART uses two techniques to make updates efficient: the first is to only retrain portions of the model where the struc- ture must change to match the updated database; the second is to introduce random nodes that do not depend on the data and thus never need to be retrained. We describe each of these techniques in the following sections, and highlight the qual- ities and trade-offs they introduce. Pseudocode for training and updating DART models is listed in Algorithms 1 and 3, with full explanations of our methods below.
3.1
Retraining Minimal Subtrees
We first describe how to retrain only the parts of the model that need to be changed to match the updated training data. We do this by storing statistics at each node in the tree. For decision nodes, we store and update counts D v,c for each attribute. This allows us to recompute the split criterion for each attribute without iterating through the data. For leaf nodes, we store and update the number of times each label occurs, along with a list of all training examples that match that leaf. These statistics are initialized when training the tree for the first time. We find this additional overhead has a negligible effect on training time. When adding/deleting a sample x , these statistics are up- dated and used to check if a particular subtree needs re- training. Specifically, decision nodes affected by the addi- tion/deletion of x update the statistics and recompute the split
criterion for each attribute. If a different attribute obtains an improved split criterion over the currently chosen attribute, then we retrain the subtree rooted at this node. The training data for this subtree can be found by concatenating the ex- ample lists from all leaf node descendants. If no retraining occurs at any decision node and a leaf node is reached in- stead, its label counts and example list are updated and the addition/deletion operation is complete. See Algorithm 3 for full pseudocode. However, in the worst case, sequential additions or dele- tions could force a decision node to retrain with every update as the best attribute alternates between two. To reduce the severity of this worst case, we can add randomness.
3.2
Random Splits
Our second technique for efficient model updating is to choose the attribute for some of the decision nodes uniformly at random, independent of the split criterion. We refer to these as "random" nodes, in contrast to "deterministic" decision tree nodes that deterministically maximize the split criterion. Since random nodes do not depend on the statistics of the data, they never need to be retrained. DART uses random nodes for the upper layers of the tree and deterministic nodes for all other layers (excluding leaf nodes). Thus, we introduce topd as a hyperparameter indicating how many layers from the top each tree should use for random nodes. Intuitively, nodes near the top of each tree contain more samples than nodes near the bottom, making them more expensive to retrain if necessary. Thus, we can significantly increase addition/deletion efficiency by replacing those nodes with random ones. We can also maintain comparable predic- tive performance to a model with no random nodes by using deterministic nodes in all subsequent layers, essentially re- sulting in a greedy model built on top of a random projection of the input space (Haupt and Nowak 2006). In our experiments, we compare DART models with ran- dom splits to those without, to evaluate the benefits of adding these random nodes. We refer to DART models with random nodes as random DART (R-DART) and those without as de- terministic DART (D-DART). D-DART can also be viewed as a special case where the number of random layers, topd , is set to zero. Algorithm 2 Creating deterministic, random, and leaf nodes. 2: 3: 4: 5: 6: 7: l:  function DETERMINISTIC_NODE(dataset D ) node ← Node() node.meta ← save_statistics( D ) node.scores ← compute_scores(node.meta) node.best ← find_best_attribute(node.scores) return node 9: 10: 8:  function RANDOM_NODE() node ← Node() node.best ← select„random„attribute() return node 11:

4
Differential Privacy-Inspired Unlearning
Adding randomness is also a popular technique used to train differentially-private (DP) models (Dwork 2006; Chaudhuri, Monteleoni, and Sarwate 2011; Abadi et al. 2016), including decision trees and random forests (Fletcher and Islam 2019). However, DP-trained decision trees often have poor predic- tive performance due to the fact that the privacy budget e must be split among all the trees in the forest, and among the different layers in each tree; the resulting model adds a sig- nificant amount of noise or uses a privacy budget too large to provide any meaningful guarantees (Fletcher and Islam 2015, 2019). Models that have achieved high predictive utility using DP-trained decision trees either have a weakened definition of DP (Rana, Gupta, and Venkatesh 2015) or use totally ran- domized trees (Fletcher and Islam 2017). When using totally randomized trees (Geurts, Ernst, and Wehenkel 2006), effi- cient data deletion becomes trivial; this is because no privacy is lost when all decision nodes are not dependent on the data to make splits, and leaf node statistics can be updated exactly. However, we find that using totally randomized trees does not often result in optimal predictive performance (Section B.2 in the Appendix), and that a middle-ground exists between totally random and totally greedy trees that provides efficient data deletion with high utility. As previous work has noted, differential privacy is a suffi- cient condition for efficient data deletion, but not a necessary one (Ginart et al. 2019). Guo et al. (2020) have developed a framework for designing efficient removal-enabled models called ε -certified removal. The idea is that, given an instance to delete x , the resulting model is "close" to a model trained without x after using a carefully designed deletion mecha- nism M on x . As another baseline, we developed a new DP-inspired ε- certified model that uses the exponential mechanism (Dwork 2006) to provide semi-random decision node splits (for de- tails on this approach, see section B.3 in the appendix). We refer to this method as CEDR (CErtified Data Removal), and include it in our empirical evaluation. However, we generally Require:  Start at the root node. 1:  function UPDATE(node, depth d , add/remove sample x ) 2: 3: 4: 5: 6: 7: 8: 9: 10: 12: 13: 11:
if best ≠ node.best then
25: return node find this approach to add too much noise to be useful, or require a budget too large to be meaningful.
5
Experiments
We attempt to answer the following research questions (RQ) whilst comparing DART to a set of meaningful baselines. Can we use D-DART to efficiently add/delete a signif- RQ1 icant number of examples as compared to naive retraining? RQ2 Can we use R-DART to further increase addi- tion/deletion efficiency over both naive retraining and D- DART while maintaining comparable predictive performance to these models? Datasets Our experiments are conducted on ten publicly- available datasets that represent problems well-suited for tree-based models, and one synthetic dataset we call Syn- thetic. For each dataset, we generate one-hot encodings for any categorical variable; for numeric variables, we first parti- tion their values into 5 quantiles, and then generate one-hot encodings based on these bin values. Also, for any dataset without a designated train and test split, we randomly sample 80% of the data for training and use the rest for testing. A summary of the datasets is in Table 1, and additional dataset details are in Section B.1 of the Appendix. Hyperparameter Tuning    Due to the range of label imbal- ances in our datasets (Appendix: Table 3), we measure the predictive peformance of our models using average precision
(AP) (Zhu 2004) for datasets with a positive label percentage < 1%, AUC (Hanley and McNeil 1982) for datasets between [1%, 20%), and accuracy for the remaining datasets. Using these measures, we tune the following hyperparameters: the maximum depth of each tree D and the number of trees in the forest T . Our protocol for tuning topd is as follows: first, we tune a greedy model (i.e. by keeping topd = 0 fixed) using 5-fold cross-validation. Once the optimal values for D and T are found, we tune topd by incrementing its value from zero to D , stopping when the model's cross-validation score exceeds a specified error tolerance as compared to the greedy model; for these experiments, we tune topd using absolute error tolerances of 0.1%, 0.25%, 0.5%, and 1.0%. The follow- ing experiments use Gini index as the split criterion; however, we find similar results using entropy as well, which can be found in Section C.1 of the Appendix.
5.1
Removing Data
In this section, we focus on removing data and evaluate how efficiently R-DART can delete a sequential stream of training samples. Specifically, we measure how many samples our method can delete in the time it takes the naive retraining approach to delete one sample (i.e. retrain without that sam- ple); the number of samples deleted gives us the speedup over the the naive approach. We also measure the predictive performance of each model prior to deletion and compare their predictive performance to the performance of the greedy model; we then repeat each experiment five times. We determine the order of deletions using two different ad- versaries: Random and Worst-of-1000 . The random adversary selects training samples to be deleted uniformly at random, while the worst-of-1000 adversary selects each sample by first selecting 1,000 candidate samples uniformly at random, and then choosing the sample that causes the greatest number of samples to be retrained across all trees in the forest. Random Adversary We present the results of the deletion experiments using the random adversary in Figure 1 (top). We find that D-DART is at least two orders of magnitude faster than the naive retraining approach, while R-DART is faster than D-DART and all other methods to a varying degree depending on the dataset and error tolerance. We also note that R-DART is able to maintain comparable predictive performance to D-DART, typically staying within a test error difference of 1% depending on which tolerance is used to tune topd (Figure 1: bottom). We also report that the naive retraining approach took roughly 1.25 hours to delete a single example for the Higgs dataset. R-DART with tol = 0.25% (resulting in topd = 2) deleted over 50,000 samples in that time, an average of 0.09s per deletion, while the average test set error increased by only 0.174%. In this case, R-DART provides a speedup of over four orders of magnitude, providing a tractable solution for something previously intractable. Worst-of-1000 Adversary    The results for the deletion ex- periments using the worst-of-1000 adversary are in Fig- ure 1 (middle). First, we notice the efficiency of D-DART drops significantly under this much more challenging adver- sary, often resulting in speedups of over one order of magni- tude as compared to the naive retraining approach. While the R-DART models also decrease in efficiency, they maintain a significant efficiency advantage over D-DART by an order of magnitude for most datasets and by over two orders of magnitude for the Credit Card dataset. Summary of Deletion Results    A summary of the deletion efficiency results are in Table 2. When the instances to delete are chosen randomly, D-DART is more than 600x faster than naively retraining after every deletion (taking the geometric mean over the 11 datasets). By adding randomness, R-DART achieves even larger speedups, from 1,500x up to nearly 6,000x, depending on the performance tolerance (0.1% to 1.0%). A more sophisticated worst-of-1000 adversary that always deletes the worst instance out of a random set of 1,000 can force more frequent retraining. In this case, D- DART is 60x faster than naive retraining, and R-DART ranges from 180x to 1,700x depending on the tolerance. The CEDR baseline was much less effective, averaging only a 15x and 8x speedup over naive retraining for the random and worst- of-1000 adversaries, respectively; more detailed results and analyses of the CEDR baseline are in Section B.3 of the Appendix. Effect of topd on Deletion Efficiency Figure 2 shows a de- tailed analysis of the effect topd has on deletion efficiency un- der each adversary for the Credit Card datastet. As expected, we see that deletion efficiency increases as topd increases. Test error also increases as topd increases, but initially de- grades gracefully, maintaining a low increase in relative test error even as the top ten layers of each tree are replaced with random nodes. Figure 2 also shows the number of retrains that occur at each depth in each tree, across all trees in the model. We immediately notice the increase in retrainings when switching from the random (top-right plot) to the worst-of- 1000 (bottom-right plot) adversary, especially at larger depths. This matches our intuition since nodes deeper in the tree have fewer samples; each sample thus has a larger influence on the resulting split criterion over all attributes at a given node and increases the likelihood that a chosen attribute may change, resulting in more subtree retraining. Table 2: Summary of the deletion efficiency results. Specif- ically, we report the minimum, maximum, and geometric mean of the speedup vs naive retraining method across all datasets.

Adding Data
5.2
To test data addition with R-DART, we perform the same set of experiments as the data removal case, now adding new training samples instead of deleting them. The random adver- sary chooses each training sample to add by sampling from the existing set of training instances uniformly at random, adding a copy of that random instance to the training data. The worst-of-1000 adversary chooses each sample to add by selecting each sample from a pool of 1,000 candidate samples (randomly chosen from the set of existing training instances) that causes the greatest number of samples to be retrained as a result of adding that sample. We find that our results follow the same trends as in the deletion case. On averge, D-DART is 1-2 orders of magnitude faster than the naive retraining approach and R-DART is 2-3 orders of mag- nitude faster than naive depending on the dataset and chosen tolerance, all while incurring small increases in test error. More details on the data addition results can be found in Section B.4 of the appendix.
6
Related Work
Exact Unlearning There have been a number of works that support decremental learning of SVMs (Cauwenberghs and Poggio 2001; Chen et al. 2019; Duan et al. 2007; Karasuyama and Takeuchi 2009; Romero, Barrio, and Belanche 2007; Tveit, Hetland, and Engum 2003), aimed at accelerating leave-one-out cross-validation (Shao 1993). More recently, Cao and Yang (2015) first introduced the concept of model unlearning, recognizing that a certain class of models (e.g. naive Bayes) fall under the umbrella of SQ-learning (Kearns 1998), where data deletion is efficient and exact; Schelter (2020) has also developed decremental update procedures for similar classes of models. Ginart et al. (2019) developed a quantized variant of the k -means (Lloyd 1982) algorithm called Q-k-means that supports exact data deletion; their method relies on the notion of model stability , with the as- sumption that the deletion of a small enough proportion of data should not cause a large change in the learned model. Unlearning for Stochastically-Trained Models Bour- toule et al. (2021) propose SISA (sharded, isolated, sliced, and aggregated) training. Their method breaks the data into shards and then further into slices, from which they train an ensemble of models and save snapshots of each model for every slice. The biggest drawbacks of their approach are the large storage costs and applicability only to iterative learning algorithms. Golatkar, Achille, and Soatto (2020a,b) propose a scrubbing mechanism for deep neural networks that does not require any retraining; however, the computational com- plexity of their approach is currently quite high. Guo et al. (2020), Izzo et al. (2020), and Wu, Dobriban, and Davidson (2020) propose different removal mechanisms for linear and logistic regression models that can be applied to the last fully connected layer of a deep neural network. Mitigation Baumhauer, Schöttle, and Zeppelzauer (2020) propose an output filtering technique that prevents private data from being leaked; however, their approach does not update the model itself, potentially leaking information if the model were still accessible. Wang, Yao et al. (2019) and Du et al. (2019) perform similar unlearning techniques to mitigate backdoor attacks (Gu, Dolan-Gavitt, and Garg 2017) on image classifiers and anomaly detectors, respec- tively. Wang et al. do this by fine-tuning their model on corrected versions of the poisoned training instances; Du et al. update their model by minimizing the probability of false positives in the training data. Although both approaches show promising empirical performance, they provide no guarantees about the extent to which these samples are removed from the model (Sommer et al. 2020). Tople, Brockschmidt et al. (2019) analyze privacy leakage in language model snapshots before and after they are updated.
7
Discussion
Protecting private user data continues to be increasingly im- portant (Shah 2020); for example, Google has implemented a system that removes potentially damaging URLs from their search engine upon request (Bertram et al. 2019). Thus, data deletion from learned models has significant privacy impli- cations, especially as many machine learning models are vulnerable to different types of "model inversion" and "mem- bership inference" attacks (Carlini, Liu et al. 2018; Shokri et al. 2017; Tople, Brockschmidt et al. 2019; Veale, Binns, and Edwards 2018; Yeom, Giacomelli et al. 2018) which can extract private data from a learned model. DART models guar- antee safeguards against these types of classical membership inference attacks and reduce the need for deletion-verification methods (Shintre and Dhaliwal 2019; Sommer et al. 2020); however, if an adversary has access to the updated model and the original model (the model trained on all the data including the data to be added/deleted), there is evidence that suggests some level of privacy leakage, even using the gold standard of retraining from scratch (Chen, Zhang et al. 2020). We have explored the robustness of our method to a small extent by using a simple but effective adversary, but we encourage researchers to develop stronger adversaries, es- pecially ones that emulate plausible scenarios from possi- ble real-world deployments of an addition/deletion-enabled model. In addition to providing strong privacy guarantees, DART (and efficient data deletion in general) can impact a number of different machine learning areas. Sample-Based Interpretability   A popular form of inter- pretability looks at how much each training instance con- tributes toward a given prediction (Koh and Liang 2017; Yeh, Kim et al. 2018; Sharchilev et al. 2018). The naive approach to this task involves leave-one-out retraining for every train- ing sample in order to analyze the effect each training sample has on the target prediction, but this is typically intractable for most machine learning models and datasets. However, when using D-DART, one can more efficiently compute the same instance attributions as the naive approach, turning leave-one- out retraining into a potentially viable option for generating instance-attribution explanations for random forest models. Dataset Cleaning User privacy may not be the only reason for deleting samples; it may also be beneficial to efficiently remove outliers identified by outlier detectors (Rahmani and Li 2019; Dong, Hopkins, and Li 2019). One may also want to remove noisy / problematic training instances caused by ran- domness or dataset poisoning attacks (Mozaffari-Kermani, Sur-Kolay et al. 2014; Steinhardt, Koh, and Liang 2017) which may be more efficiently identified using instance- attribution explanations (Koh and Liang 2017; Sharchilev et al. 2018; Yeh, Kim et al. 2018). Continual Learning  In addition to deleting noisy training instances, our approach can also efficiently add training sam- ples, making it particularly appealing for any online learning setting with streaming data in which continuous updating is desirable (Chrysakis and Moens 2020; Knoblauch, Husain, and Diethe 2020). However, one must be aware that a dif- ferent set of hyperparameters may be become optimal as a distributional shift of the training data may occur as a result of adding/deleting more and more samples. Eco-Friendly Machine Learning   Finally, this line of re- search promotes a more economically and environmentally sustainable approach to building learning systems; if a model can be continuously updated only as necessary and avoid frequent retraining, significant time and computational re- sources can be spared. We believe our work not only has positive implications for user privacy, but also opens up new possibilities for continuous model learning while having a positive impact on the environment (Gupta, Lanteigne, and Kingsley 2020).
8
Conclusion
In this work, we developed DART, a random forest variant that supports efficient updating in response to repeated ad- ditions and deletions of training examples. We find that, on average, DART models are 1-2 orders of magnitude faster than the naive retraining approach with no loss in accuracy, and models 2-3 orders of magnitude faster if slightly worse predictive performance is tolerated. Certified removal meth- ods based on differential privacy have been effective in linear models, but we found them to be much less effective in trees. For future work, there are many exciting opportunities and applications of DART, from maintaining user privacy to building interpretable models to cleaning data, all with- out retraining from scratch. One could even investigate the possibility of extending DART to boosted trees (Chen and Guestrin 2016; Ke, Meng et al. 2017; Prokhorenkova, Gusev et al. 2018). At its best, DART was 50,000 times faster than naive retraining, so it has the potential to enable new applica- tions of model updating that were previously intractable.