Connecting Interpretability and Robustness in Decision Trees through Separation

Abstract

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_{\infty }$-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 .

References in corpus (15)

• Understanding Black-box Predictions via Influence Functions
• Model-Agnostic Interpretability of Machine Learning
• Certified Adversarial Robustness via Randomized Smoothing
• Sanity Checks for Saliency Maps
• Consistent Individualized Feature Attribution for Tree Ensembles
• Improving the Adversarial Robustness and Interpretability of Deep Neural Networks by Regularizing their Input Gradients
• Evasion and Hardening of Tree Ensemble Classifiers
• Learning Optimized Risk Scores
• Explaining the Explainer: A First Theoretical Analysis of LIME
• Generalized and Scalable Optimal Sparse Decision Trees
• Robustness for Non-Parametric Classification: A Generic Attack and Defense
• ExKMC: Expanding Explainable $k$-Means Clustering
• Quantitative Evaluations on Saliency Methods: An Experimental Study
• On the Optimality of Trees Generated by ID3
• Top-down induction of decision trees: rigorous guarantees and inherent limitations