"What Data Benefits My Classifier?" Enhancing Model Performance and Interpretability through Influence-Based Data Selection

• This paper uses a lot of space to introduce the previous versions of influence functions (Section 2). However, it is not clear that the difference between previous work and this work mathematically.

  • The difference between previous work (such as Koh and Liang's work) is that those provide an approach for computing influence at the sample-level whereas we are trying to derive general "rule sets" at the feature-level for how features affect influence. For example, in Koh and Liang's work, they can obtain influence $I(x_i)$ for a sample $x_i$ (or change in output with sample-level perturbations). In our work, we use a large set of such samples (and their labels) and their influence values, to train an interpretable estimator, such as CART. This can then be used to derive a general interpretation for influence using the feature space-- for example some rules for Accuracy from our 2-D feature space in Figure 1 are: Feature 1 $>= 1.9$ and Feature 2 $< 0.1$ lead to high influence while Feature 1 $< 1.9$ and Feature 2 $< 0.1$ lead to low influence.

  • This sort of feature-level interpretation of performance gain via influence has not been undertaken in the literature previously. This can be useful in many scenarios, some of which we outline below but are not limited to only these:

    (1) When new data needs to be added that we do not have influence scores for yet, we can use the influence estimator to obtain influence scores simply via inference. For Koh and Liang's approach, they would still need to train the model once with all samples under consideration every time a new sample arrives.

    (2) In algorithmic data recourse scenarios [4] such as to describe why an individual was denied a loan, it can be used to provide an interpretable justification for why a decision was made simply by describing the tree rules that were either met or violated by the data sample.

    (3) In active learning, traditional influence computation (such as using Koh and Liang's work) is not viable since there is no access to the sample labels. Previous work such as ISAL [5] (one competitive method in our paper) have still utilized influence in these scenarios, but these do not work as well, since they use the base model itself to generate pseudo-labels for prediction. Our approach using the decision tree serves as an effective and much better alternative, as is evident in the active learning experiments of our paper (Section 5.5 - Figure 6E), where we compare with ISAL.

    (4) In some sense, we are bridging feature-interpretation approaches (such as Shapley values and LIME) with sample-interpretation approaches (such as Data Valuation and Influence), and hence, can accommodate any applications that these are used for.

  ---

• I am confused about the proposed method of this paper, as the paper just combines the influence estimation and decision tree. Also, why do we need this tree?

  Please refer to our response above for our answer to this question. Thank you. If the reviewer raised extra concerns, we are happy to address them.

  ---

• For the method in Section 3.2, what is its time/space complexity?

  Our algorithms are computationally efficient and can scale with large datasets. We provide analytical details on the time complexity below.

  Algorithm 1 Time Complexity: For calculating computational complexity, we need to analyze the two steps of our influence estimation process. First, the influence computation of training samples and a given base model requires $\mathcal{O}(npm)$ time where $n,p$, and $m$ are number of training samples, model parameters, and test samples respectively. Please refer to Section 3 of Koh and Liang's paper for how influence can be computed in $\mathcal{O}(npm)$ using stochastic estimation or conjugate gradients. Second, the cost of training time of the influence estimation tree in the worst case is $\mathcal{O}(n^2 d)$ where $d$ is the number of features. Thus, the overall complexity is $\mathcal{O}(npm) + \mathcal{O}(n^2 d)$. Note that the quadratic dependence of the second term can be made linear in $n$ simply be using more sophisticated tree-building methods [6] which have a time complexity of $\mathcal{O}(nd)$. Since the overall time complexity will then be linear: $\mathcal{O}(n(pm + d))$, the approaches proposed are amenable to large scale datasets (CelebA in our experiments has 104K samples). Furthermore, our approaches work with very high-dimensional data as well. As shown in experiments on the image (CelebA) and NLP (Jigsaw Toxicity) datasets we consider in the paper, we utilize embeddings obtained by deep learning models as a preprocessing step prior to our approach. This significantly reduces the dataset feature size, and at the same time allows for a rich and powerful feature space that can be used to train our models/methods.

We would like to sincerely thank the reviewer for their review, we are appreciative of their efforts, time, and consideration. Below we provide answers to the concerns raised:

• Essentially, this paper studies the problem of "coreset selection", which is not a new problem in machine learning. Coreset selection surely is related to the above topics. Therefore, it seems that there is no need to introduce so much redundant content in the main paper.

  We would like to emphasize here that coreset selection and our work differ in multiple ways and our main motivation is not aligned with the motivation for coreset selection. We provide more details on these differences below:

  Motivation and Research Question: Coreset selection [1,2] is primarily associated with condensing and reducing the size of the training dataset for accelerating training and making training more efficient (for e.g. in deep learning) without sacrificing performance. In contrast, our work is motivated by assessing what type of data is generally beneficial/detrimental for the model by interpreting the feature space, and then using data trimming/selection approaches to minimally modify the training set so as to improve performance with respect to multiple functions of interest. In our paper currently we had already cited both [1] and [2] (coreset selection approaches) and discussed them at a high-level, but we can describe these differences of motivation in comparison with our work in more detail in the revision.

  Other Empirical Justification: To further reinforce the differences in motivation, it can be seen that for coreset selection [1,2] the training data is reduced to be just about 20-30% of the original training dataset size (that is trimming of up to 80%). This is in stark contrast to our work, where we are minimally trimming the training set-- for example, in Figure 2 we only trim up to 5%. Note that we trim minimally in all experiments of our paper, and do not consider removing a large set of samples, as data efficiency is not our main concern.

  Differences in Generality: Different coreset selection methods generally need to be proposed for each function of interest, as it is non-trivial to apply a coreset selection method for accuracy to fairness [3]. This is also in stark contrast to our work, where we seek to have general and simple approaches that can easily be applied to multiple functions of interest (fairness, accuracy, robustness, etc.) in a trivial way. This makes our approaches more general than coreset selection, which would be more specific. This is also observable by the widespread application of our methods to problem scenarios that extend beyond conventional classification, such as online learning and active learning. For instance, it is not immediately clear how coreset selection could be applied to active learning.

  ---

• Could the paper provide more high-level intuitions about the formulas of the overall regression tree prediction and hierarchical shrinkage regularizes?

  We apologize for any lack of clarity and will make these descriptions clearer in the main text.

  Overall Regression Tree Prediction: Since the predictions for a particular node are dependent on where it lies in the tree, the tree model prediction can be denoted as a telescoping sum. We start with the average prediction response at the root node and then keep summing over the individual prediction response at each node (calculated as differences in the average prediction response between successive nodes). This provides us with the prediction at a particular query leaf in the tree.

  Hierarchical Shrinkage Regularization: Without hierarchical shrinkage the tree might have some leaves that noisily influence estimates as they have only a few samples. This can affect both interpretability of the tree as well as predictive capability. To counteract this, hierarchical shrinkage is a powerful yet simple approach. Here, we replace the average prediction response over a leaf with a weighted average of the mean or average responses over the leaf and each of its ancestors. The weights depend on the number of samples in each leaf, and are controlled by the regularization parameter $\lambda$ specified at run-time. Mathematically, this is observable with the slight modification to the summation over individual predictive responses at nodes where we divide the predictive response by the number of samples the node contains as well as $\lambda$, the regularization parameter.

  ---

We would like to thank the reviewer for their detailed review of our work, and are grateful for their time and effort. Below we provide answers to the weaknesses and questions raised:

• Response to Weaknesses:

  • Limitation on model class: The authors provide a discussion on why the influence function evaluations are limited to convex classifiers, possible remedies, and recently applications to deep neural networks. However,

    It seems that perhaps this question was accidentally cut-off. If the reviewer can provide more details, we will aim to provide a targeted response and justification during the discussion phase.

  ---

  • Theoretical analysis: the estimation of the influence function is based on the trees with hierarchical shrinkage regularization. However, there is no analysis on the credibility, time complexity of the proposed Algorithm 1 and Algorithm 2. It seems that these algorithms are not scalable to large-scale datasets.

    Both our proposed algorithms are very computationally efficient and can scale with large datasets. We provide more analytical details on time complexity below.

    Algorithm 1 Time Complexity: For calculating computational complexity, we need to analyze the two steps of our influence estimation process. First, the influence computation of training samples and a given base model requires $\mathcal{O}(npm)$ time where $n,p$, and $m$ are number of training samples, model parameters, and test samples respectively. Please refer to Section 3 of Koh and Liang's paper for how influence can be computed in $\mathcal{O}(npm)$ using stochastic estimation or conjugate gradients. Second, the cost of training time of the influence estimation tree in the worst case is $\mathcal{O}(n^2 d)$ where $d$ is the number of features. Thus, the overall complexity is $\mathcal{O}(npm) + \mathcal{O}(n^2 d)$. Note that the quadratic dependence of the second term can be made linear in $n$ simply be using more sophisticated tree-building methods [1] which have a time complexity of $\mathcal{O}(nd)$. Since the overall time complexity will be linear, the approaches proposed are amenable to large scale datasets (CelebA in our experiments has 104K samples). Furthermore, our approaches work with very high-dimensional data as well. As shown in experiments on the image (CelebA) and NLP (Jigsaw Toxicity) datasets we consider in the paper, we utilize embeddings obtained by deep learning models as a preprocessing step prior to our approach. This significantly reduces the dataset feature size, and at the same time allows for a rich and powerful feature space that can be used to train our models/methods.

    Algorithm 2 Time Complexity: The time complexity of Algorithm 2 is easier to calculate. Note that the influence values provided once at input require $\mathcal{O}(npm)$ to calculate as mentioned before. Then the sorting step requires $\mathcal{O}(n log(n))$ in the worst case. The other operations (lines 8-9) are linear vector operations, leading to a worst case time complexity of $\mathcal{O}(n(pm + log(n))$. This is not a computational bottleneck for large datasets as the time complexity is linear or logarithmic for each factor.

  ---

  • The utility, fairness and adversarial robustness are important performance metrics for a classifier; however, there is a lack of a unifying story to connect all three and therefore the discussion and experiments may seem distracted

    Thank you for the great suggestion, we can do this using our current obtained results. By observing the joint overlapping influence regions (or influence tree rules) for multiple functions of interest we can assess what samples contribute positively or negatively to both the functions of interest being considered (fairness, utility, etc.). In the current version of our paper, we did not do this since visualization for this is somewhat non-trivial and messy; however, in practice this is easy to do using our approach. To exemplify this, we provide new analysis for the synthetic toy dataset of Section 4, for both accuracy + fairness in Figure 25 (Section R1, Page 32) of our revised paper PDF, and for accuracy + robustness in Figure 26 (Section R2, Page 32) of our revised paper PDF. It can be seen that there are certain samples that are beneficial to remove for both accuracy and robustness, but for fairness and accuracy there is no overlap. Through this, we would like to emphasize that making joint improvements along multiple functions of interest is a dataset-dependent property and at times it might not be possible to make improvements along both functions (for e.g. the fairness-accuracy tradeoff [2]).

  ---

• It looks like the authors do one utility at a time. Due to often competing utilities, for example, key features and samples for fairness might not necessarily be the same for accuracy, and in most cases might have a negative influence. It would be interesting to see an interplay of various utilities.

  Thank you for the great suggestion, we can do this using our current obtained results. By observing the joint overlapping influence regions (or influence tree rules) for multiple functions of interest we can assess what samples contribute positively or negatively to both the functions of interest being considered (fairness, utility, etc.). In the current version of our paper, we did not do this since visualization for this is somewhat non-trivial and messy; however, in practice this is easy to do using our approach. To exemplify this, we provide new analysis for the synthetic toy dataset of Section 4, for both accuracy + fairness in Figure 25 (Section R1, Page 32) of our revised paper PDF, and for accuracy + robustness in Figure 26 (Section R2, Page 32) of our revised paper PDF. It can be seen that there are certain samples that are beneficial to remove for both accuracy and robustness, but for fairness and accuracy there is no overlap. Through this, we would like to emphasize that making joint improvements along multiple functions of interest is a dataset-dependent property and at times it might not be possible to make improvements along both functions (for e.g. the fairness-accuracy tradeoff [3]).

  ---

• Although authors use several datasets, all of them are binary settings. Value computation increases with classes, so I am curious to know if this is the reason authors only focused on binary settings or if there is another reason behind this design choice.

  The choice for utilizing binary classification datasets are based on three factors. First, a number of approaches and work in fairness explicitly consider binary classification [3-5] as it is easier to interpret outcomes, and since we wanted to compare with these fairness baselines, we sought to utilize binary datasets throughout the paper. For example for works in both Section 5.1 (fairness distribution shift) and Section 5.2 (fairness poisoning attacks) datasets have binary classes. Second, we believe and hope that since our approaches are general, the binary case can be empirically extended to the multi-class case in future work without too much of a challenge. Third, a minor consideration was to have neater looking trees when visualized. In the binary case, the class label can only take on two values, but in the multi-class case it would take on many different combinations and interplay with features in numerous ways leading to more complex trees.

References:

1. Su, Jiang, and Harry Zhang. "A fast decision tree learning algorithm." AAAI 2006.
2. Northcutt et al. "Confident learning: Estimating uncertainty in dataset labels." Journal of AI Research 2021.
3. Li, Peizhao, and Hongfu Liu. "Achieving fairness at no utility cost via data reweighing with influence." ICML 2022.
4. Roh et al. "Improving fair training under correlation shifts". ICML 2023.
5. Roh et al. "Fairbatch: Batch selection for model fairness." ICLR 2021.

We would like to thank the reviewer for their time, effort, and consideration in reviewing our work, we are very grateful. We provide additional details to answer questions raised:

• I think the authors should be a bit more clear in the writing or presentation. Although section 3 is fairly written, I would recommend that authors revisit abstract+sections 1-3.

  Thank you for the concrete suggestion for improving our paper. We will work to improve the writing and readability, and add a section on Problem Formulation that clarifies the presentation of the problem.

  ---

• Since the authors focus on features and samples, it would have been informative to see the difference in selected/excluded features and samples and the consequential contribution to the utility with and without the authors' method.

  If we are correct in understanding the reviewer's suggestion, you would like to see the difference in performance and utility when our approach is used and when it is not (that is, the performance of the original model). This is currently observable in Figure 2 for each subfigure when the x-axis value = 0 (0% samples trimmed or excluded). Note that this will be a constant value throughout as there is little variance in the output of logistic regression. If the reviewer intended something else, we can provide additional details during the discussion phase.

  ---

• Although influences functions are not affected by retraining-related complexity, they have a high incremental complexity due to the computation of the Hessian matrix for each xi valuation, which might worsen (beyond retraining) when n is large. Additionally, using CART as a sub-module further increases model complexity. I would have appreciated looking at the code specific to section E.1 in the appendix (I couldn't find it in the shared code base)

  • We apologize for not including the Appendix E.1 code with the provided codebase as we primarily used the original code of TMC-Shapley (Ghorbani et al). However, we have added this experiment in the following code repository: https://anonymous.4open.science/r/ICLR_Rebuttal_Experiments for the reviewer to go through. This also has implementations of additional baselines which we discuss in a subsequent response. Next, we discuss analytical details on time complexity of our algorithms.

  • The tree-based influence model of Algorithm 1 is computationally efficient and can scale with large datasets. It has a training time of $\mathcal{O}(npm) + \mathcal{O}(n^2 d)$ in the worst case where $n$, $p$, $m$, and $d$ are the number of training samples, the number of model parameters, the number of test samples, and the number of features, respectively. The first term is for the influence computation step (please refer to Section 3 of Koh and Liang's paper for how influence can be computed in $\mathcal{O}(npm)$ using stochastic estimation or conjugate gradients) and the second is for training and constructing the tree model. The biggest factor here is the quadratic dependence on the number of training samples, which can be made linear in $n$ simply by using more sophisticated tree-building methods [1] that have a time complexity of $\mathcal{O}(nd)$. This would result in an improved overall time complexity of $\mathcal{O}(n(pm + d))$. Thus the model can scale easily to larger datasets on modern hardware. This is also evident in our experiments in the paper on the CelebA dataset that has 104K samples and runs computationally efficiently even with a standard tree-building algorithm such as CART (it takes 2.455 seconds to run on average on a Linux server with an Intel Xeon 2.2GHz CPU).

  ---

• The scale for accuracy on some figures in 2 is not intuitive. Is it possible for authors to adopt similar scales for similar utilities across datasets?

  We understand the reviewer's concern regarding the figure scales; unfortunately, employing same scales across the different subfigures for a function of interest would make it challenging to observe the differences in the trends across different datasets. For example consider accuracy-- for Adult the values vary from 0.826 to 0.832, for Bank they vary from 0.80 to 0.90, and for Jigsaw Toxicity they vary from 0.735 to 0.744. Thus, using the same scale (say 0.735 to 0.90) would make all the trends for datasets except Bank look like a constant line. This is because the metric values are highly dataset-dependent and comparative analysis necessitates individual scales for each dataset.

  ---

I would like to express my gratitude to the authors for addressing the concerns raised by me and other reviewers.

After reviewing the rebuttal responses and the anonymous repository, I conducted experiments to verify specific responses on runtime, TMC-Shapely and random deletion results, and data split questions.

Upon analyzing the Bank data from the authors' anonymized repository (https://anonymous.4open.science/r/ICLR_Rebuttal_Experiments/), I discovered that the data separation did not align with the expected train:80/val:20 split. The train data had a shape of (100, 51), while the test data had a shape of (6098, 51).

I ran several experiments with an error rate of 0.1, including a single run with seed 0 and merged runs of seeds [0, 1, and 2]. The results showed that removing the high-value TMC-Shapely data points decreased the accuracy (graphs labeled hightolow) while removing the low-value TMC-Shapely data points increased performance (graphs labeled lowtohigh). The results were consistent across both cases.

When I used random deletion, the utility values were not linear. Lastly, the single run took 288.0850269794464 seconds, while the three runs altogether took 1477.8369567394257 seconds. In the single run (data_val_rebuttal_v2.ipynb/rebuttal_results2), I used computed TMC-Sahpley, random, and LOO data values, which means the time would have been even smaller. For the 3 runs (data_val_rebuttal.ipynb/rebuttal_results), I computed TMC-Shapley, G-Shapley, random, and LOO data values.

The results and all the code are in the anonymized repository (https://anonymous.4open.science/r/iclr-85E3). The repository contains the data valuation scripts, experimentation notebooks, PKL files, and PDFs.

Lastly, it looks like from this [0.025, 0.05, 0.075, 0.1, 0.125] authors delete [int(i*len(x_train)) for i in l] = [2, 5, 7, 10, 12] data samples (not percentages as indicated in the figure). In my opinion, the percentage of data deleted in the experiments (up to 5% in other figures) is very small to properly assess/compare the algorithms. Additionally, in cases like the random method where the deletion of high-value data points might show the expected trend (worse utility), the deletion of low-value data points might not do as well, as expected. So it might be intuitive to see data deletion (both ways) to properly assess the effectiveness of the algorithm.

I am happy to engage with the authors on these observations and or if I made some mistakes (it's possible).

We would like to thank the reviewer for their thoughtful review and for all their time and effort spent in reviewing our work. Below we answer the questions raised:

• How do the tree-based influence estimation models proposed by the authors scale with very large datasets, and what are the computational costs associated with these models?

  The tree-based influence models are computationally efficient and can scale with large datasets. They have a training time of $\mathcal{O}(npm) + \mathcal{O}(n^2 d)$ in the worst case where $n$, $p$, $m$, and $d$ are the number of training samples, model parameters, test samples, and features, respectively. The first term is for the influence computation step (please refer to Section 3 of Koh and Liang's paper for how influence can be computed in $\mathcal{O}(npm)$ using stochastic estimation or conjugate gradients) and the second is for training and constructing the tree model. The biggest factor here is the quadratic dependence on the number of training samples for constructing the tree, which can be made linear in $n$ simply by using more sophisticated tree-building methods [1], which have a time complexity of $\mathcal{O}(nd)$. This will result in an overall time complexity of $\mathcal{O}(n(pm + d))$. Thus the model can scale easily to larger datasets on modern hardware. This is also evident in our experiments in the paper on the CelebA dataset that has 104K samples and runs computationally efficiently even with a standard tree-building algorithm such as CART (it takes 2.455 seconds to run on average on a Linux server with an Intel Xeon 2.2GHz CPU).

  ---

• Could the authors provide insights into the computational complexity of their influence estimation approach, and are there any strategies they recommend for scaling it to big data applications?

  Our approaches can be used with big data. For calculating computational complexity, please refer to the previous response. As mentioned before, even though the overall time complexity is $\mathcal{O}(npm) + \mathcal{O}(n^2 d)$, using more sophisticated tree-building methods [1] we can improve time complexity to $\mathcal{O}(n(pm + d))$ which is linear in $n$. Furthermore, for very high-dimensional data ($d$ is large), a feature extraction step can reduce time complexity considerably. For the image (CelebA) and NLP (Jigsaw Toxicity) datasets we consider in the paper, we utilize embeddings obtained by deep learning models as a preprocessing step prior to our approach. This significantly reduces the dataset feature size, and at the same time allows for a rich and powerful feature space that can be used to train our models/methods.

  ---

• How does the tree model handle high-dimensional data, such as images, where feature interactions are more complex? Could the authors elaborate on any modifications or extensions to their approach that might be necessary to apply it effectively to image data or other high-dimensional datasets?

  Our approaches can be used efficiently with high-dimensional image and text datasets simply by employing a feature extraction preprocessing step on the raw data such as by obtaining embeddings from a deep learning model or some other approach. This is how we conduct experiments on CelebA and Jigsaw Toxicity datasets. For e.g., we use the Mini-LM transformer model to get embeddings for the Jigsaw Toxicity dataset and then conduct experiments on it. This significantly reduces the dataset feature size which further reduces the overall worst case time complexity. Additionally, we would also like to mention that past work has found that pixel-level interpretation of images is not akin to human interpretation/reasoning, and hence, prototype-based explanations are generally preferred [2]. Hence, for raw image data, using a feature extraction step for preprocessing is a viable option for improved interpretation.

  ---

• The work presented focuses on convex models or convex surrogates for non-convex models. Could the authors discuss the potential limitations of this?

  The most fundamental limitation of the convexity assumption is that for non-convex models it is not possible to derive theoretical guarantees for the efficacy of influence functions. However, despite this lack of provable theoretical guarantee, in practice this does not invalidate the use of influence functions in non-convex models. By adding a damping term to the model's Hessian or using convex surrogates, influence functions can obtain satisfactory results. For instance, in our experiments on non-convex models such as MLPs and (preliminary results on) BERT in the appendix, we obtain performance improvements using our proposed approaches for multiple functions of interest.

References:

1. Su et al. "A fast decision tree learning algorithm." AAAI 2006.
2. Chen et al. "This looks like that: Deep learning for interpretable image recognition." NeurIPS 2019.

We would like to thank the reviewer for their deep analysis of our work, and their time, effort, and consideration. Below, we answer the questions raised by the reviewer:

• Details of the approach: We apologize for any lack of clarity in presenting the approach.

  • I assume that the authors are referring to a model retrained after a subset of examples are deleted?

    Yes, the reviewer is correct.

  • So in Fig. 2, x axis==zero is a model trained on all data points?

    Yes, in Figure 2, x-axis = 0 the model is trained on all data samples.

  • Then you trim a percent of the training samples and then retrain a model on the new dataset?

    Yes, the reviewer is correct, this is precisely what we do.

  • If yes, is it the original model that is used for deciding which samples to trim or is the model changing?

    The original unchanged model is used to decide which samples to trim and then we sequentially trim the samples to the desired percentage.

  Thank you for these details. We will make the above points clearer in the text.

  ---

• What is the motivation behind the CART regression procedure?: Thank you for these insightful questions. We would first like to illustrate our motivation/goal and then address these questions one by one. Our goal is to discover a subset of the training samples that benefit the learning model (via influence functions to trim the samples that are a detriment to the model) and interpret where the benefits come from in the feature space (via CART regression).

  • Are the samples used in the training of the CART model a subset of the original training set for which the influence was estimated?

    Yes, the reviewer is correct, we use an 80-20 split with the original samples (concatenated with their labels) for training the CART model that will then be used to predict the influence value.

  • Since we know that the influence score measures the effect of up(down)weighting the training sample, alone, we also know that the label should not have any effect on predictive quality of the tree. What is the point of then concatenating the label?

    The label implicitly contributes to the computation of the influence function. Since the influence function estimation utilizes the gradient of the loss term $l$, which takes in as input both $x_i$ (training sample) and $y_i$ (class label), the label also contributes to the influence computation. This is evident in Eqs. (1-3) in our paper and Eq. (2) in Koh and Liang's paper, where they use $z_i$ which is a tuple = $(x_i, y_i)$. This is why we concatenate the label for influence estimation.