Finding Influential Training Samples for Gradient Boosted Decision Trees

By Boris Sharchilev, Yury Ustinovsky, Pavel Serdyukov, Maarten de Rijke. 2018

68 citations recorded by the source corpus.

We address the problem of finding influential training samples for a particular case of tree ensemble-based models, e.g., Random Forest (RF) or Gradient Boosted Decision Trees (GBDT). A natural way of formalizing this problem is studying how the model's predictions change upon leave-one-out retraining, leaving out each individual training sample. Recent work has shown that, for parametric models, this analysis can be conducted in a computationally efficient way. We propose several ways of extending this framework to non-parametric GBDT ensembles under the assumption that tree structures remain fixed. Furthermore, we introduce a general scheme of obtaining further approximations to our method that balance the trade-off between performance and computational complexity. We evaluate our approaches on various experimental setups and use-case scenarios and demonstrate both the quality of our approach to finding influential training samples in comparison to the baselines and its computational efficiency.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bo Li
2. Dawn Song
3. Costas J. Spanos
4. Ce Zhang
5. Jonathan Brophy
6. Daniel Lowd
7. Nicholas Hynes
8. Ruoxi Jia

Citations in the corpus

• Towards Efficient Data Valuation Based on the Shapley Value (2019, methodology): “Despite not being used for data valuation, ranking the importance of training data points has been used for understanding model behaviors, detecting dataset errors, etc. Existing methods include using the influence function [16] for smooth parametric models and a variant [28] for non-parametric ones.”
• Machine Unlearning for Random Forests (2020, background): “Instance-Based Interpretability A popular form of interpretability looks at how much each training instance contributes to a given prediction (Koh & Liang, 2017; Yeh et al., 2018; Sharchilev et al., 2018; Pruthi et al., 2020; Chen et al., 2021).”
• DART: Data Addition and Removal Trees (2020, unknown): “…training instances caused by randomness 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).”