mlsanityData to 7 Oct 2026

Connecting Interpretability and Robustness in Decision Trees through Separation

arXiv 2102.07048 ↗First posted 14 Feb 2021cs.LG stat.MLcited by 16

Not on the map. Why?

Abstract (arXiv)

Recent research has recognized interpretability and robustness as essential properties of trustworthy classification. Curiously, a connection between robustness and interpretability was empirically observed, but the theoretical reasoning behind it remained elusive. In this paper, we rigorously investigate this connection. Specifically, we focus on interpretation using decision trees and robustness to l∞-perturbation. Previous works defined the notion of r-separation as a sufficient condition for robustness. We prove upper and lower bounds on the tree size in case the data is r-separated. We then show that a tighter bound on the size is possible when the data is linearly separated. We provide the first algorithm with provable guarantees both on robustness, interpretability, and accuracy in the context of decision trees. Experiments confirm that our algorithm yields classifiers that are both interpretable and robust and have high accuracy. The code for the experiments is available at https://github.com/yangarbiter/interpretable-robust-trees .

Key facts. Cited by 16 papers in the map (data through 7 Oct 2026). Builds on 38 of its 68 references that are in the map. First posted on arXiv 14 Feb 2021.

Builds on

38 of 68 references.

References · 38

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,287
  2. 2017A Unified Approach to Interpreting Model Predictionscited by 6,488
  3. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  4. 2013Intriguing properties of neural networkscited by 5,114
  5. 2016"Why Should I Trust You?": Explaining the Predictions of Any Classifiercited by 5,040
  6. 2017Understanding Black-box Predictions via Influence Functionscited by 1,714
  7. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  8. 2018Sanity Checks for Saliency Mapscited by 1,149
  9. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  10. 2019Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methodscited by 440
  11. 2017The (Un)reliability of saliency methodscited by 331
  12. 2018Consistent Individualized Feature Attribution for Tree Ensemblescited by 279
26 more
  1. 2017Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradientscited by 236
  2. 2016Model-Agnostic Interpretability of Machine Learningcited by 219
  3. 2019"How do I fool you?": Manipulating User Trust via Misleading Black Box Explanationscited by 111
  4. 2018Convergence of Gradient Descent on Separable Datacited by 108
  5. 2019Optimal Sparse Decision Treescited by 104
  6. 2020Generalized and Scalable Optimal Sparse Decision Treescited by 98
  7. 2020Explaining the Explainer: A First Theoretical Analysis of LIMEcited by 89
  8. 2020Explainable k-Means and k-Medians Clusteringcited by 67
  9. 2016Learning Optimized Risk Scorescited by 47
  10. 2020Robust and Stable Black Box Explanationscited by 47
  11. 2015Evasion and Hardening of Tree Ensemble Classifierscited by 44
  12. 2019Robust Decision Trees Against Adversarial Examplescited by 40
  13. 2017Analyzing the Robustness of Nearest Neighbors to Adversarial Examplescited by 36
  14. 2020ExKMC: Expanding Explainable k-Means Clusteringcited by 31
  15. 2020Gradient Methods Never Overfit On Separable Datacited by 29
  16. 2019Provably Robust Boosted Decision Stumps and Trees against Adversarial Attackscited by 26
  17. 2020An Analysis of LIME for Text Datacited by 25
  18. 2021On the price of explainability for some clustering problemscited by 21
  19. 2019Top-down induction of decision trees: rigorous guarantees and inherent limitationscited by 17
  20. 2020A Closer Look at Accuracy vs. Robustnesscited by 14
  21. 2019ID3 Learns Juntas for Smoothed Product Distributionscited by 13
  22. 2019Robustness for Non-Parametric Classification: A Generic Attack and Defensecited by 12
  23. 2020Quantitative Evaluations on Saliency Methods: An Experimental Studycited by 10
  24. 2019The Price of Interpretabilitycited by 9
  25. 2020Provable guarantees for decision tree induction: the agnostic settingcited by 6
  26. 2019On the Optimality of Trees Generated by ID3cited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 3; 2024: 1; 2025: 2; 2026: 1.

16 papers.

Sort:

  1. 2022Framework for Evaluating Faithfulness of Local Explanationscited by 55
  2. 2021Provably efficient, succinct, and precise explanationscited by 32
  3. 2022Verification-Aided Deep Ensemble Selectioncited by 18
  4. 2021Unifying Model Explainability and Robustness for Joint Text Classification and Rationale Extractioncited by 11
  5. 2023Tree Variational Autoencoderscited by 10
  6. 2024A Theory of Interpretable Approximationscited by 7
  7. 2022Dynamic Model Tree for Interpretable Data Stream Learningcited by 6
  8. 2022Standardized Evaluation of Machine Learning Methods for Evolving Data Streamscited by 4
  9. 2022There is no Accuracy-Interpretability Tradeoff in Reinforcement Learning for Mazescited by 4
  10. 2025Robustness questions the interpretability of graph neural networks: what to do?cited by 4
  11. 2023Improving Stability in Decision Tree Modelscited by 2
  12. 2021Interpretable Decision Trees Through MaxSATcited by 1
4 more
  1. 2022Finding Safe Zones of policies Markov Decision Processescited by 1
  2. 2023Interpretable Differencing of Machine Learning Modelscited by 1
  3. 2025Surrogate Interpretable Graph for Random Decision Forestscited by 1
  4. 2026Tree of Concepts: Interpretable Continual Learners in Non-Stationary Clinical Domainscited by 1