Connecting Interpretability and Robustness in Decision Trees through Separation
Connecting Interpretability and Robustness in Decision Trees through Separation
复制标题
DOI：
--
复制
发表时间：
2021-02
期刊：
影响因子：
--
通讯作者：
Michal Moshkovitz;Yao-Yuan Yang;Kamalika Chaudhuri
中科院分区：
文献类型：
--
作者：
Michal Moshkovitz;Yao-Yuan Yang;Kamalika Chaudhuri
最近的研究已将可解释性和鲁棒性视为可信赖分类的重要特性。奇怪的是，在经验上观察到了鲁棒性与可解释性之间的联系，但是其背后的理论推理仍然难以捉摸。在本文中，我们严格研究了这一联系。具体而言，我们专注于使用决策树和鲁棒性对$ l _ {\ infty} $ - 扰动的解释。以前的作品将$ r $分离的概念定义为鲁棒性的足够条件。如果数据为$ r $分隔，我们证明了树大小的上限和下限。然后，我们证明当数据线性分离时，大小的紧密结合是可能的。我们提供第一种算法，并在决策树的背景下提供可证明的稳定性，解释性和准确性的保证。实验证实，我们的算法产生的分类器既可以解释又稳健，并且具有很高的精度。实验代码可在https://github.com/yangarbiter/interpretable-robust-trees上获得。
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 .