DynFrs: An Efficient Framework for Machine Unlearning in Random Forest

We appreciate the reviewers' efforts to engage with our work in depth and their thoughtful questions, which have helped us strengthen our contributions. Here are the responses to your concerns.

1. My primary concern is the limited novelty of this paper.

Here are the main contributions that make DynFrs stand out. While simple and easy to implement, the OCC subsampling method is (to the best of our knowledge) the first approach to applying subsampling on trees, which benefits unlearning quite a lot. Secondly, LZY makes DynFrs the first tree-based unlearning framework capable of avoiding the need to retrain entire subtrees. We acknowledge that our choice of Extremely Randomized Trees was driven by their minimal dependency on training samples (which is suitable for unlearning). Ultimately, DynFrs may not be theoretical ground-breaking. Still, it is an attempt to make a tree-based model more applicable to real-world applications where sample addition and deletion happen rapidly. The goal of DynFrs is to fit tree-based models into mixed online data streams, allowing the forest to shrink and grow dynamically with the ever-changing real-world data.

2. The clarity of the paper's writing could be further improved.

We would thank the reviewer for writing the thorough and detailed guidelines for how to improve the manuscript's clarity. We will try to adjust our manuscript accordingly.

3. The experimental section focuses solely on binary classification, neglecting multi-class scenarios.

We have now modified a multi-class DynFrs that can handle multi-class classification. Please read the results in the section 2. Is DynFrs capable of conquering multi-class classification? in public comment Frequently Asked Questions.

4. OCC(0.2) sometimes improves the forest's predictive performance. Could the authors provide some insights for latent reasons?

We believe that there are two latent reasons that account for the improvement in predictive performance due to OCC(0.2).

First, OCC(0.2) brings more randomness into the whole forest. As claimed by Breiman [1], randomness is essential to the whole forest's accuracy. To quantify such "randomness", we claim that OCC(0.2) decreases the correlation between trees in the forest since each tree is trained on different small subsets of the whole training set. One can prove that $\mathbf{Var}(\Phi(X)) = \mathbf{Var}(\phi(X)) \left( \frac{1}{T} + \frac{T - 1}{T} \mathbf{Corr}\left( \phi_1(X), \phi_2(X) \right) \right)$ where $\Phi(X)$ is the output of the whole forest given input $X$, and $\phi(X)$ is the output of a single tree, and $\mathbf{Corr}\left( \phi_1(X), \phi_2(X) \right)$ is the correlation between two different trees in the forest.

As OCC(0.2) decreases $\mathbf{Corr}\left( \phi_1(X), \phi_2(X) \right)$ by making each tree train on different subsets of the training set, it may potentially decrease $\mathbf{Var}(\Phi(X))$. The drop in variance might lead to less error in, at least, regression tasks. Through the bias-variance decomposition [2], the expected value for squared error loss is $\mathrm{noise} + \mathrm{bias}^2 + \mathrm{variance}$, where the $\mathrm{variance}$ stands for $\mathbf{Var}(\Phi(X))$.

Second, OCC(0.2) might decrease the pointwise hypothesis stability $\beta$ [3], which is defined as $\forall i,\, 1 \le i \le |S|,\, \mathbb E_S\left[\left| \mathcal M_S(X_i) - \mathcal M_{S \backslash \{ (X_i, Y_i) \}}(X_i) \right|\right] \le \beta$ where $\mathcal M_S(X_i)$ is the output of a model trained on training set $S$ and has an input $X_i$. Intuitively, the stability of a model is how large its output will change when a random sample is removed (unlearned) from its training set.

Suppose that a vanilla Random Forest in which each tree trains on the whole training set has a stability $\beta$, then we suggest that applying OCC(0.2) will have a stability $\beta'$ s.t. $\beta' < \beta$. Since removing one sample $(X_i, Y_i)$ only affects $\lceil qT \rceil$ trees instead of all trees, the contribution of the unaffected trees to $\left| \mathcal M(S, X_i) - \mathcal M(S \backslash \{ (X_i, Y_i) \}, X_i) \right|$ is zero. After applying OCC(0.2), we hypothesize that the stability $q' \approx q\beta$. Intuitively, The limitation that each sample appears in only $\lceil qT \rceil$ trees makes the whole trees more stable when one of the samples is removed, as the remaining $T - \lceil qT \rceil$ trees stay unchanged.

Thank you for your reply. After reading your response, I acknowledge the effectiveness of the DYNFRS framework. However, I still have concerns regarding the novelty of the proposed framework (as mentioned in question 1). There are still some issues that need addressing in the manuscript, such as the lack of sufficient references for certain claims and the inclusion of trivial theorems (as mentioned in question 2). Additionally, some important ablation experiments (as noted in question 5) are still absent. Given these considerations, I maintain my score.

However, I also acknowledge that I am not familiar with this specific field, which may have led to an inaccurate assessment of its innovativeness.

The benefit of having a smaller stability is that it would decrease the generalization error of the model with probability. Suppose that a model $\mathcal M_S$ has a pointwise hypothesis stability $\beta$ and a loss function $\mathcal L$ that is $L$-Lipchitz continuous and has a upper bound $M$, also denote $n = |S|$, then the following holds [3]: $\Pr \left[R(A_S) \le R_{\mathrm{emp}}(A_S) + \sqrt{\delta^{-1}} \sqrt{\frac{M^2}{2n} + 6M\beta} \right] \ge 1 - \delta$ where $R(A_S) \triangleq \mathbb E_{(X_i, Y_i) \sim \mathcal D}[\mathcal L(A_S(X_i), Y_i)]$ and $R_{\mathrm{emp}}(A_S) \triangleq \mathbb E_{(x_i, y_i) \sim S}[\mathcal L(A_S(x_i), y_i)]$. This probability inequality enables us to bound the generalization error from empirical error (the error estimated on the training set), and smaller stability makes the bound tighter. Smaller stability might be the key to why OCC(0.2) sometimes improves the forest's predictive performance.

5. In section 4.3, introducing consideration of only $s$ candidates, although it has a higher chance to remain unchanged when adding or removing data points, it is also entirely possible to not obtain the best split in all possible splits. The authors should discuss this additional loss caused by only $s$ candidates.

It is possible that none of the candidates is the best split among all possible splits. However, it is not true that relying on the best candidate gives the tree a higher accuracy. As finding the optimal decision tree is NP-Hard, deterministic searching methods [4] suggest that finding the split with the optimal empirical criterion score does not always produce the best-performing decision tree. So, not encapsulating the best split among all splits might not be a loss. Always greedily choosing the best split can lead to a good-performing Decision Tree, but selecting the second-best or a relatively good split brings more potential to the tree (think of the tree as not trapped in local minimum). Not choosing the best split may also prevent the tree from overfitting [5]. Also, the trade-offs are analyzed in the original work for Extremely Randomized Trees [6].

References

[1] L. Breiman, "Random Forests," Machine Learning, vol. 45, no. 1, pp. 5–32, Oct. 2001, doi: 10.1023/A:1010933404324.

[2] G. Louppe, "Understanding Random Forests: From Theory to Practice," arXiv, 2015. Accessed: Jun. 23, 2024. [Online]. Available: http://arxiv.org/abs/1407.7502

[3] O. Bousquet and A. Elisseeff, "Stability and Generalization," Journal of Machine Learning Research, vol. 2, no. Mar, pp. 499–526, 2002.

[4] E. Demirović et al., "MurTree: Optimal Decision Trees via Dynamic Programming and Search," Journal of Machine Learning Research, vol. 23, no. 26, pp. 1–47, 2022.

[5] L. Z. You, P. Y. Han, K. Z. B. Kamarudin, O. S. Yin, and H. F. San, "Bayesian Optimization Driven Strategy for Detecting Credit Card Fraud with Extremely Randomized Trees," MethodsX, p. 103055, Nov. 2024, doi: 10.1016/j.mex.2024.103055.

[6] P. Geurts, D. Ernst, and L. Wehenkel, "Extremely randomized trees," Mach Learn, vol. 63, no. 1, pp. 3–42, Apr. 2006, doi: 10.1007/s10994-006-6226-1.

Dear Reviewer THi8,

Thank you for taking the time to provide your thoughtful feedback. We truly appreciate your acknowledgment of the effectiveness of the DynFrs framework and your detailed considerations regarding our manuscript.

We have addressed the specific points you raised, including adding more references to substantiate our claims and incorporating the missing ablation experiments to provide a comprehensive evaluation.

However, we would make the following clarifications:

(1) The sentence

One observation is that if sample $\langle \mathbf x_{i}, y_{i} \rangle \in S$ does not occurs in tree $\varphi_t$ (i.e., $\langle \mathbf x_{i}, y_{i} \rangle \notin S^{(t)}$), then tree $\varphi_t$ is unaffected when unlearning $\langle \mathbf x_{i}, y_{i} \rangle$.

is self-evident and does not require references because if a sample does not appear in the model, then we cannot unlearn it from the model because the model has never learned it. To fix it, we change the phrase one observation to key idea, emphasizing its role as a foundational concept rather than an empirical observation. Also, the observations in Section 4.2 are true for all Random Forests models and its variants, and they are properties of tree-based models. However, we still added the reference you suggested to enrich our manuscript. To be concise, we have changed the description in Section 4.2 from observations on tree-based models to observations on differences between tree-based methods and neural network based methods.

(2) The inclusion of Lemma 1 and Theorem 1 is necessary. As Lemma 1 is the basis for Theorem 2, 3, 4 and it introduce a new fashion for finding the node's best split without sorting all the samples. On the other hand, Theorem 1 is the theoretical back up for DynFrs's unlearning exactness. This guarantees both the model's predictive performance after unlearning and its resistance to privacy leaks, ensuring the theoretical soundness and security of DynFrs.

As you suggested, we ran an ablation experiment regarding the number of candidate split $s$. We tested DynFrs($q = 0.1$) with $s \in \\{1, 5, 10, 20, 30, 50\\}$ and report the predictive performance on all the binary classification datasets (same settings as in the manuscript). The results are summarized in the table below:

From the result, we find that the performance peaks around $s = 20$ in most datasets and the result of $s = 30$ and $s = 50$ has no significant difference. However, in dataset Heart, Diabetes, and NoShow, a smaller $s$ have a even higher predictive performance, suggesting that considering more candidates might not always be the best choice. This ablation study indicates that the optimal $s$ is dataset-specific and can be tuned for improved predictive performance in DynFrs.

Thank you once again for your time and effort in reviewing our submission.

Best regards,

Authors of Submission 9406

Table: Hyperparameters used by DynFrs and DaRE.

2. How much memory does DynFrs consume during training compared to the baselines? How much memory does DynFrs consume during a stream of mixed requests?

The space complexity and memory consumption are discussed in question 1. What are the space complexity and memory consumption of DynFrs? in public comment Frequently Asked Questions; please read it there. Additionally, we tested the maximum resident set size of DynFrs handling a mixed online data stream on Higgs with 100,000 sample additions, 100,000 sample deletions, and 100,000 queries. It turns out that handling the mixed online data stream barely introduces extra space from training as the maximum resident set size is 58327 MB, which is close to the training memory consumption (58263 MB).

3. How many times each experiment is repeated? What differs in each repetition of the experiments?

All experiments in this paper have been repeated 5 times, and all reported statistics (e.g., average, minimum, maximum, and standard deviation) are calculated directly from these 5 outcomes. The random seeds are different each time, and we use the srand(time(NULL)) settings, meaning that the random seed changes with system time. We mention the implementation details in the appendix and will consider moving this part with extra details to the main text to avoid confusion. Thank you for pointing this out!

4. Why are multiclass datasets not used in the experimental evaluation? Does DYNFRS also support multiclass classification tasks?

DynFrs support multi-class classification. The reason that we did not evaluate DynFrs on multi-class classification in the first place is that it is harder to implement a multi-class forest than a binary-class forest. The other two Random Forest unlearning methods (DaRE and HedgeCut) do not have implementation for multi-class classification as well, so it will be hard to find such a baseline. However, we implement a multi-class DynFrs as discussed in question 2. Is DynFrs capable of conquering multi-class classification? in public comment Frequently Asked Questions.

5. In Section 4.1, the speedup is computed as $N_{\text{occ}} / N_{\text{nai}}$. Instead, should it be computed as $N_{\text{nai}} / N_{\text{occ}}$? Moreover, is the speedup achieved by OCC over the naive method $1 / q^2$ or $1 / q$?

We would like to thank the reviewer again for pointing out this typo! The expected unlearning speedup should be calculated as $\mathbb E[N_{\text{nai}} / N_{\text{occ}}] = 1/q^2$. DynFrs will be $1/q$ times faster than the naive approach when training. After being trained, by retraining necessary $\lceil qT \rceil$ trees, the speedup of DynFrs against the naive approach in unlearning one sample is $1/q^2$. It means OCC alone brings a $1/q^2$ boost without LZY or ERTs. We will fix our manuscript later.

We greatly appreciate the reviewers' detailed and constructive feedback, which has helped us improve the quality and clarity of our manuscript. Here are the responses to the unclear points and weaknesses you care about.

1. Do the models trained by each framework in the experimental evaluation have the same hyperparameter values, e.g., number of trees and maximum depth?

No. The hyperparameters used in each model are tuned individually on each dataset so that the number of trees and maximum depths might differ. However, DynFrs tends to have more trees and maximum depths than DaRE. Here, we include the elapsed time for DynFrs with DaRE's hyperparameters (we call it DaFrs) to unlearn 1, 10, 100 samples, and 0.1% and 1% of the whole training set.

Table: The time to simultaneously unlearn $1$, $10$, and $100$ instances of each model with standard deviation shown in a smaller font. "DaFrs" denotes a DynFrs using DaRE's hyperparameters. "/" means the model takes too long to complete the task.

Table: The training time, and 0.1% and 1% training set unlearning time of each model with standard deviation shown in a smaller font. "DaFrs" denotes a DynFrs using DaRE's hyperparameters. "/" means the model takes too long to complete the task.

As shown in the above tables, DaFrs (DynFrs using DaRE's hyperparameters) has a more splendid efficiency than vanilla DynFrs. The reason is that DynFrs has a larger $T$ (number of trees in the forest) and $d_{\max}$ (maximum depth for each tree) in all datasets except dataset NoShow.

Thank you for your response. The new results you provided are convincing, and I am very satisfied with the quality of your response. I encourage you to incorporate these new results and discussions into the next version of your paper. Additionally, please address the indicated typos. I will increase my score as a consequence of your high quality response.

3. In the experiment, what are the detailed settings for the unlearning request in each dataset?

For each dataset, the unlearning settings are the same. For sequential unlearning, we feed the model with training samples one by one in random order. For batch unlearning of size $|S|$, we randomly pick $|S|$ different training samples to form the unlearning batch and feed the batch to the model. We will add this information to our manuscript later. Moreover, for batch unlearning, we explicitly write the batch size $|S|$ in the plot title (Figure 5) for all experiments.

4. In the baselines, this paper chooses four methods corresponding to different tree construction approaches. Thus, does it mean such baselines also contain different initialized well-trained models? In addition, does the random forest stand for the retrained model?

There is no pre-training in our experiments. For all baselines (DaRE, HedgeCut, OnlineBoosting, and Random Forest Classifier implemented by scikit-learn), we trained them thoroughly on our server for experiments. Also, DynFrs does not have back-bone or pre-trained components, so we train repeatedly for each experiment. For the second question, "Random Forest" in Table 2 stands for the vanilla Random Forest Classifier implemented in scikit-learn, and it does not contain specializations for unlearning (Yes, it is the retraining model). We might change "Random Forest" to "Vanilla" in our manuscript for less confusion.

5. In the experiment results in Table 2, why does higher prediction performance stand for better unlearning performance? In addition, in the unlearning of a tree-based method, which has more transparent structures, is it a better way to prove the success of unlearning by showing that the unlearned trees have the same structures as the retrained trees?

It is an interesting question. First of all, higher prediction performance does not stand for better unlearning performance. As mentioned in Clarifications on metrics, predictive performance does not imply anything about unlearning exactness and unlearning efficiency, so higher prediction performance does not stand for better unlearning exactness (or success of unlearning as you mentioned) nor unlearning efficiency. Table 2 only guarantees that DynFrs does not sacrifice accuracy for unlearning efficiency, as the accuracy is measured right after training and before unlearning.

For the second question, we think you are on the right track for checking similar tree structures. However, tree structures can be quite different even for the same building algorithm and same hyperparamters but different random seeds, as Random Forests embrace a fair amount of randomness. So, the idea is to see whether the unlearned model has a similar behavior as the retrained model (i.e., the distribution of their predictions are the same), which is the definition of unlearning exactness (Section 3.1), and your idea is similar to that of goal (A) which has been examined theoretically (Theorem 1) and empirically (Figure 3). Thank you again for raising these points, and we will adjust our manuscript accordingly to avoid further confusion.

6. Addition reply to Weakness 1: However, the proposed method relies on Extremely Randomized Trees instead of the general decision trees, which limits the applicability.

DynFrs can be applied to other trees, such as the vanilla Random Forest and other kinds of trees, by simply substituting the Extremely Randomized Trees with other base learners since OCC and LZY have little requirement for the tree structure. But we choose Extremely Randomized Trees here for its limited dependence on training samples, which is crucial for achieving better unlearning efficiency.

We appreciate the reviewers' constructive feedback and the opportunity to address their thoughtful questions, ensuring our work achieves its full potential. Here is more background information that is helpful in answering your questions.

0. Clarifications on metrics

There are three different metrics to evaluate an unlearning method --- predictive performance (how well can the model predict?), unlearning exactness (does the model forget everything we ask it to forget?), and unlearning efficiency (how fast is the forgetting process?).

Predictive performance evaluates how accurate the model is on classification or regression tasks, and it has nothing to do with unlearning exactness and unlearning efficiency. The goal of evaluating predictive performance is to check whether the framework sacrifices accuracy for unlearning efficiency.

Unlearning exactness evaluates the behavior of the model when processing unlearning requests. An ideal unlearning framework should have the same behavior as the one being retrained from scratch. Exactness ensures that the framework forgets everything about the samples deleted. Unlearning exactness is essential to privacy-sensitive fields where tree-based methods are employed. A detailed definition can be found in Section 3.1 of the manuscript.

Unlearning efficiency indicates how fast the model unlearns one or a batch of samples. Retraining the model ensures good predictive performance and excellent unlearning exactness, but it is time-consuming and resource-demanding, which contradicts the goal of minimizing the time and computational resources required to unlearn samples. In reality, we cannot wait for a long time to just unlearn one single sample, so high unlearning efficiency means better real-world applicability.

The goal of unlearning frameworks is to: (A) achieve a similar (comparative) predictive performance with the retraining model before and after unlearning (achieve exact unlearning); (B) optimize unlearning efficiency to reduce time and resource consumption;

In our manuscript, we check goal (A) in Section 5.2 Table 2, showcasing that DynFrs does not sacrifice accuracy for unlearning efficiency, and in Theorem 1 and Figure 3, demonstrating that DynFrs achieves exact unlearning theoretically and empirically. Moreover, Sections 5.3 and 5.4 present DynFrs's outstanding unlearning efficiency for pursuing goal (B).

Here are the responses to the questions you raised:

1. What are the performance comparisons on the sequential unlearning, batch unlearning, and mixed online stream unlearning settings? The current draft only provides efficiency comparisons.

We argue that performance comparisons on all unlearning settings are not necessary as DynFrs has been proven to have unlearning exactness. If the unlearning model has a higher accuracy than the retraining model, it might indicate that the unlearning model takes advantage of the deleted samples to achieve better accuracy, which is harmful in privacy-sensitive settings. Recall that goal (A) states that the model should have similar (actually "equivalent" for DynFrs) behavior as the retraining model after completing the unlearning task. And we have proven theoretically (Theorem 1) and empirically (Figure 3) that DynFrs enjoys unlearning exactness, so there is no worry about its predictive performance after unlearning. Therefore, our experiments focus on goal (B) --- evaluating DynFrs's unlearning efficiency. Additionally, both baselines DaRE and HedgeCut focus on demonstrating the model's unlearning efficiency. Finally, we would like to thank you for raising such concern, and we will adjust the description in Section 5 to demonstrate the purpose of each experiment.

2. How the proposed method handles the changes of optimal split is not clear. This is the key point about the soundness of the proposed method.

Without the lazy tag, when a change in optimal split happens in node $u$, we simply retrain the whole subtree $u$. But with the presence of lazy tags, we destroy that subtree (delete every node other than $u$) and place a lazy tag on node $u$ to indicate this node is not a normal leaf and should be grown when a query visits this leaf. When a query does visit the said tagged node $u$, we find the optimal split for this node from all stored split candidates, grow two leaves with lazy tags from $u$, and remove $u$'s lazy tag. Then, the query will only visit one of its leaves, and the growing progress continues recursively until a tree path from $u$ to a leaf is constructed. A detailed growing process can be found in Section 4.2, and how a new optimal split is found is in Section 4.3.

Dear Reviewer 7Tpx,

We would like to express our gratitude for your constructive suggestions and thoughtful reviews, which have proven invaluable in enhancing the quality of our paper. As a follow-up to our rebuttal, we would like to kindly remind you that the deadline for discussion closure is rapidly approaching.

During this open response period, we aim to engage in discussions, address any further inquiries, and further enhance the overall quality of our paper. We would appreciate it if you could confirm whether you have had the opportunity to review our rebuttal, in which we made concerted efforts to address all of your concerns. It is of utmost importance to us that our responses have been thorough and persuasive.

Should you require any additional information or clarification, please do not hesitate to let us know. Thank you once again for your time and valuable consideration.

Best regards,

Authors of Submission 9406

We are grateful to the reviewers for their careful reading and valuable suggestions, which have significantly contributed to refining our research. Here are the responses to your points raised in the weakness sections.

1. Standard bootstrapping should be included as a baseline for performance comparison.

As suggested, we constructed DynFrs with standard bootstrapping instead of OCC subsampling (call it BootFrs) and evaluated its unlearning boost. Here are the results compared with DaRE and ordinary DynFrs:

Table: The training time measured, and unlearning boost of each model with standard deviation shown in a smaller font. "BootFrs" denotes a DynFrs with standard bootstrapping.

Thank you again for your idea of the separate comparison. It provides insight into to what extent ERTs and OCC bring incredible unlearning efficiency to DynFrs.

2. Space complexity analysis is missing from the paper.

The space complexity and memory consumption are discussed in question 1. What are the space complexity and memory consumption of DynFrs? in public comment Frequently Asked Questions; please read it there.

3. The evaluation lacks testing on regression datasets.

We have already adopted DynFrs for multi-class classification as discussed in question 2. Is DynFrs capable of conquering multi-class classification? in public comment Frequently Asked Questions. We are still working on modifying DynFrs for regression tasks, which other tree-based unlearning methods have never evaluated, and it will be released in a few days.

Here are the results on Regression tasks, which is not implemented and evaluated by any of the existing tree-based unlearning methods. As the first unlearning framework testing on regression tasks, we compare DynFrs's predictive performance (via mean squared error) and unlearning efficiency (via unlearning boost) against the naive retraining method (the scikit-learn Random Forest Regressor implementation, and we label it as "Vanilla" in the following). We used a large and popular dataset Bike (https://archive.ics.uci.edu/dataset/275/) as the regression task.

Table: Datasets specifications. (#train: number of training samples; #test: number of testing samples; #attr: number of attributes.)

Table: Each model's predictive performance, training time, and unlearning boost with standard deviation shown. "Vanilla" denotes the Random Forest implemented in scikit-learn.

Results show that DynFrs outperforms the vanilla Random Forest in terms of predictive performance and training time. Note that the implementation of DynFrs regressor is rough and poorly optimized due to short time slots. However, DynFrs still shows outstanding unlearning efficiency on regression tasks, as DynFrs achieves an averaged $2368$ unlearning boost in dataset Letter.

We suggest picking $q = 0.5$ for a lower mean squared error in the regression setting. In the experiment, we set the hyperparameters of DynFrs to $T = 100$, $d_{\max} = 15$, and $s = 5$.

Again, We sincerely thank you for your thoughtful and constructive suggestions, which have significantly improved the quality and clarity of our work.