Connecting Interpretability and Robustness in Decision Trees through Separation

Deploying machine learning (ML) models in high-stakes fields like healthcare, transportation, and law, requires the ML models to be trustworthy. Essential ingredients of trustworthy models are explainability and robustness: if we do not understand the reasons for the model’s prediction, we cannot trust the model; if small changes in the input modifies the model’s prediction, we cannot trust the model. Previous works hypothesized that there is a strong connection between robustness and explainability. They empirically observed that robust models lead to better explanations (Chen et al., 2019; Ross & Doshi-Velez, 2017). In this work, we take a rigorous approach towards understanding the connection between robustness and interpretability.

We focus on binary predictions, where each example has $d$ features and the label of each example is in $\{-1,+1\}$, so an ML model is a hypothesis $f:\mathbb{R}^{d}\rightarrow\{-1,1\}.$ We want our model to be (i) robust to adversarial $\ell_{\infty}$ perturbations, i.e., for a small distortion, $\|\delta\|_{\infty}$, the model’s response is similar, $f(x)=f(x+\delta)$, for most examples $x$, (ii) interpretable, i.e., the model itself is simple and so self-explanatory, and (iii) have high-accuracy. A common type of interpretable models are decision trees (Molnar, 2019), which we call tree-based explanation and focus on in this paper.

Prior literature (Yang et al., 2020b) showed that data separation is a sufficient condition for a robust and accurate classifier. A data is $r$-separated if the distance between the two closest examples with different labels is at least $2r$. Intuitively, if $r$ is large, then the data is well-separated. A separated data guarantees that points with opposite labels are far from each other, which is essential to construct a robust model.

In this paper, we examine whether separation implies tree-based explanation. We first show that for a decision tree to have accuracy strictly above $1/2$ (i.e., better than random), the data must be bounded. Henceforth we assume that the data is in $[-1,1]^{d}.$ We start with a trivial algorithm that constructs a tree-based explanation with complexity (i.e., tree size) $2^{O(d/r)}$. For constant $r$, we show a matching lower bound of $2^{\Omega(d)}.$ Thus, we have a matching lower and upper bound on the explanation size of $2^{\Theta(d)}$. Thus, separation implies robustness and interpretability. Unfortunately, for a large number of features, $d$, the explanation size is too high to be useful in practice.

In this paper, we show that designing a simpler explanation is possible with a stronger separability assumption — linear separability with a $\gamma$-margin. This assumption was recently used to gain a better understanding of neural networks (Soudry et al., 2018; Nacson et al., 2019; Shamir, 2020). More formally, this assumption means that there is a vector $w$ with $\|w\|=1$ such that $yw\cdot x\geq\gamma$ for each labeled example $(x,y)\in\mathbb{R}^{d}\times\{-1,1\}$ in the data (Shalev-Shwartz & Ben-David, 2014). Our main building block is a proof that, under the linearity assumption, there is always at least one feature that provides non-trivial information for the prediction. To formalize this, we use the known notion of weak learners (Kearns, 1988), which guarantees the existence of hypothesis with accuracy bounded below by more than $\nicefrac{{1}}{{2}}$.

Our weak-learnability theorem, together with Kearns & Mansour (1999), implies that a popular CART-type algorithm (Breiman et al., 1984) is guaranteed to give a decision tree with size $1/\epsilon^{O(1/\gamma^{2})}$ and accuracy $1-\epsilon$. Therefore, under the linearity assumption, we can design a tree with complexity independent of the number of features. Thus, even if the number of features, $d$, is large, the interpretation complexity is not affected. This achieves our first goal of constructing an interpretable model with provable guarantees.

Recently, several research papers gave a theoretical justification for CART’s empirical success (Brutzkus et al., 2020, 2019; Blanc et al., 2019, 2020; Fiat & Pechyony, 2004). Those papers assume that the underlying distribution is uniform or features chosen independently. For many cases, this assumption does not hold. For example, in medical data, there is a strong correlation between age and different diseases. On the other hand, we give a theoretical justification for CART without resorting to the feature-independence assumption. We use, instead, the linear separability assumption. We believe that our method will allow, in the future, proofs with less restrictive assumptions.

So far, we showed how to construct an interpretable model, but we want a model that will not be just interpretable but also robust. Decision trees are not robust by-default (Chen et al., 2019). For example, a small change at the feature at the root of the decision tree leads to an entirely different model (and thus to entirely different predictions): the model defined by the left subtree and the model defined by the right subtree. We are left with the questions: can robustness and interpretability co-exist? How to construct a model that is guaranteed to be both interpretable and robust? To design such a model, we focus on a specific kind of decision tree — risk score (Ustun & Rudin, 2017). A risk score is composed of several conditions (e.g., $age\geq 75$) and each matched with a weight, i.e., a small integer. A score $s(x)$ of an example $x$ is the weighted sum of all the satisfied conditions. The label is then a function of the score $s(x)$. A risk score is a specific case of decision trees, wherein at each level in the tree, the same feature is queried. The number of parameters required to represent a risk score is much smaller than their corresponding decision trees, hence they might be considered more interpretable than decision trees (Ustun & Rudin, 2017).

We design a new learning algorithm, BBM-RS, for learning risk scores that rely on the Boost-by-Majority (BBM) algorithm (Freund, 1995) and our weak learner theorem. It yields a risk score of size $O(\gamma^{-2}\log(1/\epsilon))$ and accuracy $1-\epsilon$. Thus, we found an algorithm that creates a risk score with provable guarantees on size and accuracy. As a side effect, note that BBM allows to control the interpretation complexity easily. Importantly, we show that risk scores are also guaranteed to be robust to $\ell_{\infty}$ perturbations, by deliberately adding a small noise to dataset (but not too much noise to make sure that the noisy dataset is still linearly separable). Therefore, we design a model that is guaranteed to have high accuracy and be both interpretable and robust, achieving our final goal.

Finally, in Section 6, we test the validity of the separability assumption and the quality of the new algorithm on real-world datasets that were used previously in tree-based explanation research. On most of the datasets, less than $12\%$ points were removed to achieve an $r$-separation with $r\geq 0.05$. For comparison, for binary feature-values $\{-1,1\}$, and $\ell_{\infty}$ distance, the best value for $r$ is $r=1$. The added percentage of points required to be removed for the dataset to be linearly separable is less than $7\%$ on average. Thus, we observe that real datasets are close to being separable and even linearly separable. In the next step, we explored the quality of our new algorithm, BBM-RS. Even though it has provable guarantees only if the data is linearly separable, we run it on real datasets that do not satisfy this property. We compare BBM-RS to different algorithms for learning: decision trees (Quinlan, 1986), small risk scores (Ustun & Rudin, 2017), and robust decision trees (Chen et al., 2019). All algorithms try to maximize accuracy, but different algorithms try to, additionally, minimize interpretation complexity or maximize robustness. None of the algorithms aimed to optimize both interpretability and robustness. We compared the (i) interpretation complexity, (ii) robustness, and (iii) accuracy of all four algorithms. We find that our algorithm provides a model with better interpretation complexity and robustness while having comparable accuracy.

To summarize, our main contributions are:

Interpretability under separability: optimal bounds. We show lower and upper bounds on decision tree size for $r$-separable data with $r=\Theta(1)$, of $2^{\Theta(d)}$. Namely, our upper bound proves that for any separable data, there is a tree of size $2^{O(d)}$, and the lower bound proves that separability cannot guarantee an explanation smaller than $2^{\Omega(d)}$.

Algorithm with provable guarantees on interpretability and robustness. Designing algorithms that have provable guarantees both on interpretability, robustness, and accuracy in the context of decision trees is highly sought-after, yet there was no such algorithm before our work. We design the first learning algorithm that has provable guarantees both on interpretability, robustness, and accuracy of the returned model, under the assumption that the data is linearly separable with a margin.

While the CART algorithm is empirically highly effective, its theoretical analysis has been elusive for a long time. As a side effect, we provide an analysis of CART under the assumption of linear separability. To the best of our knowledge, this is the first proof with a distributional assumption that does not include feature independence.

Experiments. We verify the validity of our assumptions empirically and show that for real datasets, if a small percentage of points is removed then we get a linear separable dataset. We also compare our new algorithm to other algorithms that return interpretable models (Quinlan, 1986; Ustun & Rudin, 2017; Chen et al., 2019) and show that if the goal is to design a model that is both interpretable and robust, then our method is preferable.

Post-hoc explanations. There are two main types of explanations: post hoc explanations (Ribeiro et al., 2016a) and intrinsic explanations (Rudin, 2019b). Algorithms for post hoc explanation take as an input a black-box model and return some form of explanation. Intrinsic explanations are simple models, so the models are self-explanatory. The main advantage of algorithms for post hoc explanations (Lundberg & Lee, 2017; Lundberg et al., 2018; Ribeiro et al., 2016b; Koh & Liang, 2017; Ribeiro et al., 2018; Deutch & Frost, 2019; Li et al., 2020; Boer et al., 2020) is that they can be used on any model. However, they host a variety of problems: they introduce a new source of error stemming from the explanation method (Rudin, 2019b); they can be fooled (Slack et al., 2020); some explanations methods are not robust to common pre-processing steps (Kindermans et al., 2019), and can be independent both of the model and the data generating process (Adebayo et al., 2018). Because of the critics against post hoc explanations, in this paper, we focus on intrinsic explanations.

Explainability and robustness. Different works research the intersection of explanation and robustness of black-box models (Lakkaraju et al., 2020), decision trees (Chen et al., 2019; Andriushchenko & Hein, 2019), and deep neural networks (Szegedy et al., 2013; Goodfellow et al., 2014; Madry et al., 2017; Ross & Doshi-Velez, 2017). Unfortunately, the quality of these methods are only verified empirically. On the theoretical side, most works analyzed explainability and robustness separately. Explainability was researched for supervised learning (Garreau & von Luxburg, 2020b, a; Mardaoui & Garreau, 2020; Hu et al., 2019) and unsupervised learning (Moshkovitz et al., 2020; Frost et al., 2020; Laber & Murtinho, 2021). For robustness, Cohen et al. (2019) showed that the technique of randomized smoothing has robustness guarantees. Ignatiev et al. (2019) connected adversarial examples and a different type of explainability from the point of view of formal logic.

Risk scores. Ustun and Rudin (Ustun & Rudin, 2017) designed a new algorithm for learning risk scores by solving an appropriate optimization problem. They focused on constructing an interpretable model with high accuracy and did not consider robustness, as we do in this work.

We investigate models that are (i) with high-accuracy, (ii) robust, and (iii) interpretable, as formalized next.

High accuracy. We consider the task of binary classification over a domain ${\mathcal{X}}\subseteq{\mathbb{R}}^{d}$. Let $\mu$ be an underlying probability distribution¹¹1In the paper, we will assume that $\mu$ has additional properties, like separation or linear separation. over labeled examples ${\mathcal{X}}\times\{-1,+1\}.$ The input to a learning algorithm $\mathcal{A}$ consists of a labeled sample $S\sim\mu^{m}$, and its output is a hypothesis $h:{\mathcal{X}}\rightarrow\{-1,+1\}.$ The accuracy of $h$ is equal to $\Pr_{(x,y)\sim\mu}(h(x)=y)$. The sample complexity of $\mathcal{A}$ under the distribution $\mu$, denoted $m(\epsilon,\delta):(0,1)^{2}\rightarrow\mathbb{N}$, is a function mapping desired accuracy $\epsilon$ and confidence $\delta$ to the minimal positive integer $m(\epsilon,\delta)$ such that for any $m\geq m(\epsilon,\delta)$, with probability at least $1-\delta$ over the drawn of an i.i.d. sample $S\sim\mu^{m}$, the output $A(S)$ has accuracy of at least $1-\epsilon$.

Robustness. We focus on the $\ell_{\infty}$ ball, ${\mathbb{B}}$, and denote the $r$-radius ball around a point $x\in{\mathcal{X}}$ as ${\mathbb{B}}(x,r)$. A hypothesis $h:{\mathcal{X}}\rightarrow\{-1,+1\}$ is robust at $x$ with radius $r$ if for all $x^{\prime}\in{\mathbb{B}}(x,r)$ we have that $h(x)=h(x^{\prime}).$ In (Wang et al., 2018), the notion of astuteness was introduced to measure the robustness of a hypothesis $h$. The astuteness of $h$ at radius $r>0$ under a distribution $\mu$ is

For a hypothesis to have high astuteness the positive and negative examples need to be separated. A binary labeled data is $r$-separated if for every two labeled examples $(x^{1},+1)$,$(x^{2},-1)$, it holds that $\|x^{1}-x^{2}\|_{\infty}\geq 2r.$

Interpretability. We focus on intrinsic explanations, also called interpretable models (Rudin, 2019a), where the model itself is the explanation. There are several types of interpretable models, e.g., logistic regression, decision rules, and anchors (Molnar, 2019). One of the most fundamental interpretable models, which we focus on in this paper, is decision trees (Quinlan, 1986). In a decision tree, each leaf corresponds to a label, and each inner node corresponds to a threshold and a feature. The label of an example is the leaf’s label of the corresponding path.

In the paper we also focus on a specific type of decision trees, risk scores (Ustun & Rudin, 2019), see Table 1. It is defined by a series of $m$ conditions and a weight for each condition. Each condition compares one feature to a threshold, and the weights should be small integers. A score, $s(x)$, of an example $x$ is the number of satisfied conditions out of the $m$ conditions, each multiplied by the corresponding weight. The prediction of the risk model $f$ is the sign of the score, $f(x)=sign(s(x))$. A risk score can be viewed as a decision tree where at each level there is the same feature-threshold pair. Since the risk-score model has fewer parameters than the corresponding decision tree, it may be considered more interpretable.

We want to understand whether separation implies the existence of a small tree-based explanation. Our first observation is that the data has to be bounded for a tree-based explanation to exist. If the data is unbounded, then to achieve a training error slightly better than random, the tree size must depend on the size of the training data, see Section 4.1, Theorem 1.

In Section 4.2 we investigate lower and upper bounds for decision tree’s size, assuming separation. Specifically, in Theorem 2, we show that if the data is bounded, in $[-1,1]^{d}$, then $r$-separability implies a tree based-explanation with tree depth $O(\nicefrac{{d}}{{r}})$. Importantly, the depth of the tree is independent of the training size, so a tree-based explanation exists. Nevertheless, even for a constant $r$, the size of the tree is exponential in $d$. In Theorem 3, we show that this bound is tight as there is a $1$-separable dataset that requires an exponential size to achieve accuracy even negligibly better than random. The conclusion from this section is that if all we know is that the data is $r$-separability for constant $r$, we understand the interpretation complexity: it is exactly $2^{\Theta(d)}$. However, the explanation is of exponential size in $d$. In Section 5, we improve the interpretation complexity by assuming a stronger separability assumption. We will assume linear separability with a margin. All proofs are in Section A.1.

In the previous section, we showed that $\Theta(1)$-separability implies a decision tree with size exponential in $d$, and we showed a matching lower bound. This section explores a stronger assumption than separability that will guarantee a smaller tree, i.e., a simpler explanation. This assumption is that the data is linearly separable with a margin. More formally, data is $\gamma$-linearly separable if there is $w\in{\mathbb{R}}^{d}$, $\|w\|_{1}=1$, such that for each positive example $x$ it holds that $w\cdot x\geq\gamma$ and for each negative example $x$ it holds that $w\cdot x\leq-\gamma.$ Note that without loss of generality $w_{i}\geq 0$ (if the inequality does not hold, multiply the $i$-th feature in each example by $-1$). Thus, we can interpret $w$ as a distribution over all the features. One might interpret the highest $w_{i}$ as the most important feature. However, this will be misleading. For example, if all that data has the same value at the $i$-th feature, this feature is meaningless. In the experimental section, Section 6, we show that real datasets are close to being linearly separable.

The key step in designing a model which is both interpretable and robust is to show that one feature can provide a nontrivial prediction. In particular, in Section 5.1 we show that the hypotheses class, ${\mathcal{H}}_{t}=\{h_{i,\theta}\}$, is a weak learner, where

This class is similar to the known decision stumps class, but it does not contain hypotheses of the form “if $x_{i}\leq\theta$ then $+1$ else $-1$”. The reason will become apparent in Section 5.3, but for now, we will hint that it helps achieve robustness.

In Section 5.2, we observe that weak learnability immediately implies that the known CART algorithm constructs a tree of size independent of $d$ (Kearns & Mansour, 1999). Unfortunately, decision trees are not necessarily robust. To overcome this difficulty, we focus on one type of decision trees, risk scores, which are interpretable models on their own. In Section 5.3 we show how to use (Freund, 1995) together with our weak learnability theorem to construct a risk score model. We also show that this model is robust. This concludes our quest of finding a model that is guaranteed to be robust, interpretable, and have high-accuracy under the linearity separable assumption. In Section 6 we will evaluate the model on several real datasets.

In previous sections, we designed new algorithms and gave provable guarantees for separated data. We next investigate these results on real datasets. Concretely, we ask the following questions:

• •

  How separated are real datasets?

• •

  How well does BBM-RS perform compared with other interpretable methods?

• •

  How do interpretability, robustness, and accuracy trade-off with one another in BBM-RS?

Datasets. To maintain compatibility with prior work on interpretable and robust decision trees (Ustun & Rudin, 2019; Lin et al., 2020), we use the following pre-processed datasets from their repositories – adult, bank, breastcancer, mammo, mushroom, spambase, careval, ficobin, and campasbin. We also use some datasets from other sources such as LIBSVM (Chang & Lin, 2011) datasets and Moro et al. (2014). These include diabetes, heart, ionosphere, and bank2. All features are normalized to $[0,1]$. More details can be found in Appendix B. The dataset statistics are shown in Table 2.

We found that linear separability is a hidden property of the data that guarantees both interpretability and robustness. We designed an efficient algorithm, BBM-RS, that returns a model, risk-score, which we prove is interpretable, robust, and have high-accuracy. An interesting open question is whether a weaker notion than linear separability can give similar guarantees.

Kamalika Chaudhuri and Yao-Yuan Yang thank NSF under CIF 1719133 and CNS 1804829 for research support.