interpretability, learning theory, boosting

1 Introduction↩︎

Many machine learning techniques, such as deep neural networks, produce large and complex models whose inner workings are difficult to grasp. In sectors such as healthcare and law enforcement, where the stakes of automated decisions are high, this is a serious problem: complex models make it hard to explain the rationale behind an outcome, or why two similar inputs produce different outcomes. In those cases, interpretable models may become the preferred choice. Although there is an ongoing debate around the notion of interpretability [1], decision trees are typically considered as the quintessential example of interpretable models [2]: ones that favor a transparent decision-making process, and that allow users to understand how individual features influence predictions. A line of research in this area studies the extent to which small decision trees can approximate some specific learning models, such as neural networks [3] and \(k\)-means classifiers [4]. Inspired by these results, we develop a general theory of interpretability viewed as approximability via simple decision trees. Our guiding principle can be summarized as follows.

In analogy with PAC learning, we focus on binary classification tasks and view a classifier (e.g., a neural network) as a concept \(c \subseteq X\), where \(X\) is the data domain. Now let \(\mathcal{H}\subseteq 2^X\) be a family of simple hypotheses, for instance decision stumps or halfspaces. Our goal is to understand how well \(c\) can be approximated by aggregating a small set of elements in \(\mathcal{H}\). To formalize this goal in the language of decision trees we introduce two notions. First, we say that \(c\) is approximable by \(\mathcal{H}\) if, under any given data distribution, there exists a finite decision tree using splitting functions from \(\mathcal{H}\) that approximates \(c\) arbitrarily well. Moreover, if the approximation can be always achieved using a shallow tree, we say that \(c\) is interpretable by \(\mathcal{H}\). It is easy to see that, depending on \(c\) and \(\mathcal{H}\), one may have interpretability, approximability but not interpretability, or even non-approximability. In 4, we give explicit examples of pairs \((c,\mathcal{H})\) for each one of the three above cases.

Note that in this initial study on the general structure of interpretable approximations we focus on the fundamental question of what conditions ensure the existence of accurate approximations and interpretations. Important topics, such as the informational or computational complexity of obtaining accurate interpretations, are not addressed in this work. Note also that we do not make any specific assumption on the data distribution \(P\). Our approach is thus in line with standard notions and theories in machine learning—e.g., universal Bayes consistency [5], PAC learnability [6], and universal learnability  [7]—as it encompasses both distribution-free and distribution-dependent guarantees.

While our primary focus is not algorithmic, our work reveals profound connections within the algorithmic framework of boosting. Indeed, there is a clear relationship between boosting, which involves the aggregation of weak hypotheses to learn a target concept, and interpretable approximation, which concerns the aggregation of simple hypotheses to approximate a target concept. However, our work uncovers and exploits deeper links at a technical level. In particular, our general construction that gives decision trees whose depth depends logarithmically on the accuracy is based on boosting decision trees, and its analysis uses potential functions from this line of work. Our improved bound for the VC classes, which provides approximating decision trees with constant (accuracy- and distribution-free) depth, is somewhat more subtle; it is also based on a boosting perspective, this time using majority-vote based algorithms and the minimax theorem. However, to eliminate the dependency on the accuracy, we utilize tools from VC theory, particularly uniform convergence.

1.1 Contributions↩︎

Degrees of interpretability (Section 4). We introduce our learning-theoretic notions of approximability and interpretability. Informally speaking, we use the depth of the shallowest approximating tree to measure the extent to which a certain concept \(c\) is interpretable by a given class \(\mathcal{H}\) (e.g., hyperplanes or single features). Approximability is our weakest notion, as we do not constrain the rate at which the rate of the shallowest approximating tree grows as a function of the desired accuracy. Our strongest notion is instead interpretability with a tree depth that is constant with respect to both accuracy and data distribution. In between these two extremes, a wide variety of behaviors is possible, as the tree depth may grow at different rates that may be uniform, or depend on the data distribution (similarly to the distinction between PAC learning and universal learning).

Collapse of the degrees (Section 5). We prove that the range of possible behaviors collapses dramatically, and only three cases are actually possible: \(c\) is uniformly interpretable by \(\mathcal{H}\), \(c\) is approximable but not interpretable by \(\mathcal{H}\), \(c\) is not approximable by \(\mathcal{H}\). If the class \(\mathcal{H}\) of splits has bounded VC dimension, which conforms to our request that \(\mathcal{H}\) be simple, we show that whenever \(c\) is interpretable (possibly with a distribution-dependent rate) then it is uniformly interpretable by \(\mathcal{H}\) at constant depth. This means that, for every data distribution \(P\) and every accuracy \(\varepsilon> 0\), there exists an \(\mathcal{H}\)-based decision tree that approximates \(c\) with accuracy \(\varepsilon\) and whose depth is bounded by a constant depending only on \(c,\mathcal{H}\) (but not on \(P,\varepsilon\)). Thus, whenever \(c\) is interpretable at some arbitrary rate, it is in fact interpretable at a constant rate. We show a similar collapse for classes \(\mathcal{H}\) of unbounded VC dimension: in this case, we show that interpretability collapses to uniform interpretability at logarithmic depth \(\mathcal{O}\bigl(\log \frac{1}{\varepsilon}\bigr)\).

Algebraic characterizations (6). We prove that the trichotomy described above can be characterized in terms of algebras and closures over \(\mathcal{H}\). For example, we show that if \(\mathcal{H}\) has bounded VC dimension, then \(c\) is interpretable at constant depth if and only if \(c\) is in the algebra generated by the closure of \(\mathcal{H}\), i.e., the family of all the concepts that can be approximated arbitrarily well by single hypotheses of \(\mathcal{H}\). We also present a simpler characterization when the domain \(X\) is countable.

Extension to other complexity measures (7). Finally, we exploit the equivalence between \(\mathcal{H}\)-based decision trees and Boolean formulae over \(\mathcal{H}\) to show that the trichotomy above holds for a large class of complexity measures, including not only tree-depth but also, for example, circuit size. In particular, we show that for any complexity measure in our class, interpretability collapses to uniform interpretability at constant complexity rate for VC classes and at polynomial complexity rate for non-VC classes.

2 Related Work↩︎

According to [2], there are different approaches to interpretability in learning. One important distinction is between local explanation, where we explain the prediction of the model on a single data point, and global interpretation, where we explain the model itself. In this work we focus on the latter. A common approach to global interpretation is to use simpler “interpretable” models (e.g., decision trees) to approximate more complex ones [3]. This is known as post-hoc interpretability [2]. For example, [8] used decision trees to interpret convolutional neural networks. Formally, interpretability can be modeled as a property of a classifier. For example, [9] define a variant of empirical risk minimization (ERM), where each classifier in a given class \(\mathcal{H}\) is either interpretable or not, and the task is to learn an interpretable one even though the target concept is not necessarily interpretable. We generalize this setup by assigning a complexity measure to each classifier, e.g., the depth for decision trees. This allows to trade-off the desired accuracy \(\varepsilon\) and the maximum depth of a decision tree one is willing to call interpretable. Learning-theoretic perspectives on interpretability are rare and typically not covered in standard books and surveys. One important line of work initiated by [4] deals with the problem of approximating a given \(k\)-means or \(k\)-median clustering with decision trees. From this perspective, our setup can be seen as a generalization from clusterings to arbitrary concepts. However, that line of work focuses on efficient algorithms to compute decision trees with \(k\) leaves and approximation guarantees in terms of the \(k\)-means or \(k\)-medians cost function, not in terms of classification error under a distribution as we do here. [10] discuss a related problem setup where a given classifier is approximated using a decision tree. Under strong assumptions, the authors state convergence results for the proposed decision tree. However, they do not state bounds on the required depth which is assumed to be given as a hyperparameter. Some algorithmic analyses exist for specific cases of hypothesis spaces and standard explainers. For example, [11] analyse LIME [12], one of the most used explanation techniques. [13] discuss generalization bounds for local explainers. [14] introduce a local variant of our setup with the goal of explaining the classification \(f(x)\) of a single instance \(x\) using a conjunction with small size (i.e., a small decision list). Their results cannot be used for our goal of global interpretation as one would have to take the union of all the local conjunctions for all (potentially infinite) instances \(x\). Closer to our setup, [15] state bounds on the depth of a decision tree required to fit a linear classifier with margin. Similarly to us, they also strongly rely on boosting arguments. [16] give upper bounds on the number of nodes of a single decision tree to approximate an ensemble of trees. While mainly focusing on local explainability, [14] also state bounds on the depth of a decision tree required to fit an arbitrary classifier \(f\colon \{0,1\}^d\to \{0,1\}\) under the uniform distribution on \(\{0,1\}^d\). They do so by relying on classical bounds on the depth in terms of certificate complexity [17], [18]. As we focus instead on general hypothesis classes and distributions, their results are not directly comparable to ours.

3 Preliminaries and Notation↩︎

Let \(X\) be any domain. We denote by \(P\) a distribution¹ on \(X\) and by \(\mathcal{P}(X)\) the set of all distributions on \(X\), by \(\mathcal{H}\subseteq 2^X\) a hypothesis class on \(X\), and by \(\mathop{\mathrm{VC}}(X,\mathcal{H})\) its VC dimension. We denote by \(\mathop{\mathrm{Alg}}(\mathcal{H})\) the algebra generated by \(\mathcal{H}\), i.e., the smallest set system \(\mathcal{A}\subseteq 2^X\) closed under complements and finite unions such that \(\mathcal{H}\subseteq\mathcal{A}\) and \(\emptyset,X\in \mathcal{A}\). The \(\sigma\)-algebra \(\sigma(\mathcal{H})\) is the smallest algebra containing \(\mathcal{H}\) that is closed under countable unions. We denote by \(c \in 2^X\) an arbitrary concept (not necessarily in \(\mathcal{H}\)). As usual we also view \(c\) as a binary classification function \(c\colon X\to\{0,1\}\). Our goal is to understand how well \(c\) can be approximated using aggregations of hypotheses in \(\mathcal{H}\). We let \(\mathbb{N}\) denote the naturals including \(0\), and \(\mathbb{N}^+ = \mathbb{N}\setminus \{0\}\).

A decision tree over \(X\) is a full finite binary tree \(T\) with nodes \(\mathcal{V}(T)\), where every leaf \(z \in \mathcal{L}(T)\) holds a label \(\ell_z \in \{0,1\}\) and every internal node \(v \in \mathcal{V}(T)\setminus \mathcal{L}(T)\) holds a decision stump \(f_v \colon X \to \{0,1\}\). The depth (or height) of \(T\) is denoted as \(\mathop{\mathrm{depth}}(T)\). We say \(T\) is \(\mathcal{H}\)-based if \(f_v \in \mathcal{H}\) for all \(v \in \mathcal{V}(T)\), and we denote by \(\mathcal{T}_{\mathcal{H}}\) the set of all \(\mathcal{H}\)-based decision trees. We also use \(T\) to denote the binary classifier \(T\colon X \to \{0,1\}\) induced by \(T\) in the standard way. Note that \(\mathcal{T}_{\mathcal{H}}\equiv \mathop{\mathrm{Alg}}(\mathcal{H})\), as any \(\mathcal{H}\)-based tree \(T\) can be rewritten as a Boolean formula and vice versa. For every \(d\in\mathbb{N}_+\) we let \(\mathop{\mathrm{Alg}}_d(\mathcal{H}) = \{T \in \mathop{\mathrm{Alg}}(\mathcal{H}) \,:\, \mathop{\mathrm{depth}}(T) \le d \}\). Given \(P\in \mathcal{P}(X)\) and a concept \(c \in 2^X\), the loss of \(T\) with respect to \(c\) under \(P\) is \(L_{P}(T,c) = \mathbb{P}_{x\sim P}(T(x) \neq c(x)) = P\bigl(T^{-1}(1) \triangle c\bigr)\), where \(A \triangle B = (A\setminus B) \cup (B\setminus A)\) is the symmetric difference between \(A\) and \(B\).

An \(\varepsilon\)-accurate \(\mathcal{H}\)-approximation of \(c\) under \(P\) is an \(\mathcal{H}\)-based decision tree \(T\) with \(L_{P}(T,c) \le \varepsilon\). The set of all such trees is denoted as \(\mathcal{T}^{c}_{\mathcal{H}}(\varepsilon\mid P)\), which is also known as the \(\varepsilon\)-Rashomon set [21], and their minimal depth is \[\mathop{\mathrm{depth}}^{c}_{\mathcal{H}}\!\left(\varepsilon\mid P\right) = \inf_{T\in\mathcal{T}^{c}_{\mathcal{H}}(\varepsilon\mid P)}\mathop{\mathrm{depth}}(T) \enspace.\]

4 Approximability and Interpretability↩︎

This section introduces the key definitions used in our results. We start with the definition of approximability.

Approximability is our weakest notion, as it only requires that for any desired accuracy value a tree approximating \(c\) exists under any distribution, without any constraint on its depth. In fact, there may not even exist a function \(f\) such that \(\mathop{\mathrm{depth}}^{c}_{\mathcal{H}}\!\left(\varepsilon\mid P\right)\) is bounded by \(f(\varepsilon)\) for all distributions \(P\).

For example, for \(X=\mathbb{R}^d\) let \(c\) be the unit \(d\)-dimensional Euclidean ball centered at the origin and \(\mathcal{H}\) be the family of affine halfspaces whose boundary is orthogonal to, say, the \(d\)-th dimension. Then, any finite aggregation \(T\) of such halfspaces is unable to discern points that are aligned along the \(i\)-th dimension for any \(i \ne d\) and, thus, necessarily incurs a constant \(L_{P}(T,c)\) for some distribution \(P\). On the other hand, if we extend \(\mathcal{H}\) to be the family of all halfspaces in \(X=\mathbb{R}^d\), then it is possible to show that we can approximate the unit ball \(c\) up to any accuracy under any distribution. Indeed, it is known that a variant of the \(1\)-nearest neighbour (\(1\)-NN) algorithm is universally strongly Bayes consistent in essentially separable metric spaces [22], and any \(1\)-NN classifier corresponds to a finite Voronoi partition which can be represented as an \(\mathcal{H}\)-based decision tree. However, we expect the number of Voronoi cells, and thus the depth of the \(\mathcal{H}\)-based decision tree representing it, to grow larger as the distribution \(P\) concentrates around the decision boundary (that is, the surface of the unit ball \(c\)). Consider, for instance, the family of distributions \(P_\alpha\) with \(\alpha\in(0,1)\), where each \(P_\alpha\) has support corresponding to the spherical shell \(B^d(1+\alpha)\setminus B^d(1-\alpha)\) with inner radius \(1-\alpha\) and outer radius \(1+\alpha\) (here we denote by \(B^d(r) = \{x\in\mathbb{R}^d : \|x\|_2 \le r\}\) the origin-centered Euclidean ball of radius \(r > 0\) in \(\mathbb{R}^d\)). Then, we expect the number of Voronoi cells defining the decision boundary of the \(1\)-NN classifiers that guarantee loss at most \(0<\varepsilon\le 1\) to grow as \(\alpha \to 0^+\). Figures [fig:approx-ball-1] and [fig:approx-ball-2] illustrate these examples in \(\mathbb{R}^2\).

Next, we define interpretability. Recall that we view an interpretation as an approximation via a tree of small depth. We formalize “small” by requiring the existence of a function that bounds the depth of the tree in terms of its accuracy.

Note that interpretability requires the bound on the depth to hold only for values of \(\varepsilon\) that are smaller than a certain threshold \(\varepsilon_{P}\) which may depend on the distribution \(P\). Uniform interpretability, instead, requires the depth bound to hold for all \(\varepsilon\) irrespective of the distribution.

Recalling the above example with the Euclidean space \(X=\mathbb{R}^d\) as domain and the family of halfspaces as the hypothesis class \(\mathcal{H}\), if the concept \(c\) corresponds to the unit Euclidean ball with margin \(\mu>0\) then \(c\) is uniformly interpretable. More formally, such a concept \(c\) can be modeled as a partial function \(c\colon X\to\{0,1\}\) with natural domain \(\widetilde{X}\subset X\), where points in the margin belong to \(X\setminus\widetilde{X} = B^d(1+\mu)\setminus B^d(1)\) and \(c^{-1}(1)=B^d(1)\). Then, without loss of generality, the same definitions and results apply as if the concept \(c\) was a total function by restricting the domain to \(\widetilde{X}\) and, for every distribution \(P\in\mathcal{P}(X)\), considering the distribution \(\widetilde{P}(\cdot) = P(\cdot \mid \widetilde{X})\) instead. This follows from the fact that we incur no mistakes for any labeling of points that do not belong to the domain of the “partial” concept \(c\), and the loss of any \(\mathcal{H}\)-approximation \(T\) of \(c\) is thus given by \(L_{\widetilde{P}}(T,c)\). By reusing geometric results on the approximation of convex bodies, there exists a polytope \(Q\) such that \(B^d(1) \subseteq Q \subseteq B^d(1+\mu)\), whose (finite) number of vertices is bounded from above by a function of \(d\) and \(\mu\) [23]. The polytope \(Q\) thus separates the positively labeled points \(B^d(1)\) from the negatively labeled ones—achieving loss \(0\) under any distribution with support \(\widetilde{X}\)—and it is equivalently representable as an \(\mathcal{H}\)-based decision tree with depth bounded by a function of \(d\) and \(\mu\) only (i.e., the intersection of halfspaces associated to the facets of \(Q\)). See Figure [fig:approx-ball-3] for an illustration of this example in \(\mathbb{R}^2\).

At first glance, our notions of interpretability may appear a little narrow. Suppose that, for every distribution \(P\), a concept \(c\) is interpretable by \(\mathcal{H}\) at polynomial depth rate, but the degree can grow unbounded with \(P\). In other words, for every \(d \in \mathbb{N}_+\) there exists \(P_d\) such that \(c\) is interpretable by \(\mathcal{H}\) at polynomial depth rate with degree \(d\), but not at polynomial depth rate with any smaller degree \(d' < d\). Then \(c\) is not interpretable by \(\mathcal{H}\) according to our definition, but we could still say that \(c\) is interpretable at polynomial depth rate. More formally, we could consider the family \(\mathcal{F}\) of all polynomials, and require that for every \(P\) there is some \(f \in \mathcal{F}\) that bounds \(\mathop{\mathrm{depth}}^{c}_{\mathcal{H}}\!\left(\cdot \mid P\right)\). By varying \(\mathcal{F}\), we obtain a vast range of interpretability rates: logarithmic, sublinear, linear, polynomial, exponential, and so on. Surprisingly, our results show that this hierarchy collapses: an approximable concept \(c\) is either not interpretable at all, or is uniformly interpretable at logarithmic rate.

5 A Trichotomy for Interpretability↩︎

This section states our main result: as soon as a concept is interpretable at some rate, then it is uniformly interpretable at a constant rate for VC classes, and at a logarithmic rate in general.

We emphasize again that Theorem 1 is in stark contrast with the behavior of excess risk in terms of training set size observed in statistical learning, where, in the non-uniform (or universal) setting, both exponential and linear rates are possible. It should also be noted that we do not know if case (3\('\)) collapses into case (3)—that is, if a constant depth rate holds also for non-VC classes—or if a non-constant rate is in general unavoidable. This is one of the questions the present work leaves open.

We further observe that, while point (3) of 1 shows that \(c\) is uniformly interpretable by \(\mathcal{H}\) at a constant depth rate, this does not necessarily imply the existence of a single \(\mathcal{H}\)-based decision tree providing such a guarantee for all values of \(\varepsilon>0\). For example, consider a domain \(\mathcal{X}= \mathbb{N}\), a concept \(c=\{0\}\), and a hypothesis class \(\mathcal{H}= \{ \{1,\dots,n\} : n \in \mathbb{N}^+ \}\). Now let \(P\) be the distribution such that \(P(0)=0.5\) and \(P(x)=2^{-(x+1)}\) for all \(x \in \mathbb{N}^+\). For any \(\varepsilon> 0\) the depth-\(1\) decision tree with splitting criterion \(h=\{1,\ldots,\lceil\log_2(1/\varepsilon)\rceil\}\) is an \(\varepsilon\)-accurate approximation of \(c\) under \(P\), but no \(\mathcal{H}\)-based tree is an \(\varepsilon\)-approximation of \(c\) for all \(\varepsilon\) simultaneously.

Our proof of 1 combines a variety of techniques from different contexts. The first step involves identifying a criterion which can be thought of as a form of “weak interpretability” (items (a) and (b) in the proof). The rest of the proof demonstrates that if a concept \(c\) fails to satisfy this criterion, then it is not interpretable by \(\mathcal{H}\), and if it does, then it is uniformly interpretable by \(\mathcal{H}\). The former impossibility result entails establishing a lower bound on the interpretation rate for an arbitrarily small accuracy with respect to a fixed and carefully tailored distribution. This type of lower bounds are more intricate than distribution-free lower bounds (such as those outlined in the No-Free-Lunch Theorem in the PAC setting) and were studied, e.g., by [24], [25]. In the complementary case, when \(c\) satisfies the weak interpretability criterion with respect to \(\mathcal{H}\), we prove that \(c\) is in fact uniformly interpretable by \(\mathcal{H}\) with logarithmic depth, and if \(\mathcal{H}\) has a finite VC dimension, then \(c\) is interpretable with constant depth. The logarithmic construction and its analysis builds on ideas and techniques originating from boosting algorithms for decision trees [26], [27]. The derivation of constant depth approximation when \(\mathcal{H}\) is a VC class relies on a uniform convergence argument [19] combined with the Minimax Theorem [28]. This derivation is also linked to boosting theory and resembles the boosting-based sample compression scheme by [29].

The proof of case (3\('\)) of 1 uses the following result. Its proof can be found in Appendix 8, and is an adaptation of the results by [26] and [27] on boosting decision trees. The main difference is that, via an adequate modification of the TopDown algorithm [26], we bound the depth rather than the size of the boosted decision tree.

6 Algebraic Characterizations↩︎

In this section we show that the notions of approximability and interpretability admit set-theoretical and measure-theoretical characterizations based on properties of \(\mathcal{H}\) and the algebras it generates.

To begin with, we need a notion of closure of \(\mathcal{H}\). Loosely speaking, we want to include all concepts that, under every distribution, can be approximated arbitrarily well by single elements of \(\mathcal{H}\). In other words, these are the concepts that are approximable by \(\mathcal{H}\) using decision trees of depth \(1\).

Observe that \(\mathop{\mathrm{clos}}(\mathcal{H}) \supseteq \mathcal{H}\) by definition. To illustrate the closure let us discuss the hypothesis class \(\mathcal{H}\) of rational halfspaces in \(\mathbb{R}^2\), i.e., sets of the form \(\bigl\{\{(x,y) \mid ax + by + d\geq 0\}: a,b,d\in\mathbb{Q}\bigr\}\). Every concept \(c\colon \mathbb{R}^2\to \{0,1\}\) is approximable by \(\mathcal{H}\), as before, relying on the \(1\)-NN algorithm. Halfspaces with real coefficients such as \(\{(x,y)\mid x+y\geq \sqrt{2}\}\) are not in \(\mathcal{H}\) but are interpretable by \(\mathcal{H}\) with depth \(1\). In general, the closure is related to the concept of universally measurable sets.

We start with the following lemma, which is derived from well-known results in measure theory (see the proof in Appendix 9).

We now state the algebraic characterization of the concepts that are approximable by a given hypothesis class \(\mathcal{H}\) on some domain \(X\).

Furthermore, we manage to prove an algebraic characterization for the concepts that are uniformly interpretable, given a VC class \(\mathcal{H}\) on some domain \(X\).

If the domain \(X\) is countable, then closure reduces to pointwise convergence and our algebraic characterization becomes simpler. This is formalized in the next theorem, whose proof relies on some technical lemmas and can be found in 9. Namely, we show that \(\mathop{\mathrm{clos}}(\sigma(\mathcal{H}))=\sigma(\mathcal{H})\) and \(\bigcup_{d=1}^\infty \mathop{\mathrm{clos}}(\mathop{\mathrm{Alg}}_d(\mathcal{H})) = \mathop{\mathrm{Alg}}(\mathop{\mathrm{clos}}(\mathcal{H}))\).

7 General Representations↩︎

Although shallow decision trees are the blueprint of interpretable models, our theory naturally extends to ways of measuring the complexity of elements in \(\mathop{\mathrm{Alg}}(\mathcal{H})\) different from the tree depth. Next, we define a set of minimal conditions (satisfied, e.g., by tree depth) that a function must satisfy to be used as a complexity measure for \(\mathop{\mathrm{Alg}}(\mathcal{H})\).

The definitions of approximability, interpretability, and uniform interpretability are readily generalized to an arbitrary graded complexity measure, by simply replacing \(\mathop{\mathrm{depth}}(\cdot)\) with \(\Gamma^{}_{}\!\left(\cdot\right)\). We can then prove the following extension of 1.

Unlike 1, cases (2) and (3) might collapse for certain choices of \(\Gamma\) even when \(\mathcal{H}\) is not a VC class. Indeed, according to our definition, \(\Gamma\) is not forced to grow at any specific rate, and thus \(\Gamma(f)\) might be bounded by some constant uniformly over \(\mathop{\mathrm{Alg}}(\mathcal{H})\). In an extreme case one might in fact set \(\Gamma\equiv 0\), although clearly this would not yield any interesting result.

We remark that the \(\mathcal{O}\bigl(\frac{1}{\varepsilon^d}\bigr)\) bound on the complexity rate for case (3\('\)) is due to the generality of \(\Gamma\); in Appendix 10, we show a more specific condition on \(\Gamma\) that recovers the \(\mathcal{O}(\log(1/\varepsilon))\) rate.

8 Boosting Decision Trees with Bounded Depth↩︎

We use a surrogate loss \(G(q)=\sqrt{q(1-q)}\), where \(0 \le q \le 1\). Since \(\min\{q,1-q\} \le G(q)\), the surrogate loss bounds from above the classification error of the majority vote. For a distribution \(P\in \mathcal{P}(X)\), let \(G_P(c)=G\bigl(P(c=1)\bigr)\). Let the conditional surrogate loss of \(f\colon X \to \{0,1\}\) be \[G_{P}(c \mid f) = P(f=0) G\bigl(P(c=1 \mid f=0)\bigr) + P(f=1) G\bigl(P(c=1 \mid f=1)\bigr) \enspace.\] Finally, given a decision tree \(T\) with leaves \(\mathcal{L}(T)\), define the conditional surrogate loss of \(T\) as \[H_{P}(c \mid T) = \sum_{z\in\mathcal{L}(T)} P(z) G(p_{c\mid z}) \enspace,\] where \(P(z)\) is the probability that \(x\sim P\) is mapped to leaf \(z\) in the tree \(T\) and \(p_{c\mid z} = P(c=1 \mid z)\). Our goal is to construct an \(\mathcal{H}\)-based decision tree \(T\) such that \(H_{P}(c \mid T) \leq \varepsilon\), implying that \(L_{P}(T,c) \le \varepsilon\) because \(G\bigl(p_{c\mid z}\bigr)\) bounds from above the probability that \(T(x) \neq c(x)\) conditioned on \(x\) being mapped to \(z\) in \(T\).

Our variant of TopDown, called TopDownLBL (TopDown Level-By-Level), starts from a single-leaf tree \(T\) with a majority-vote label and works in phases. In each phase, we replace each leaf \(z\in\mathcal{L}(T)\) of the current tree \(T\) with a suitably chosen \(\mathcal{H}\)-based \(d\)-depth tree \(T_{z}\) using the same criterion as TopDown. The main difference is that the weak learners adopted by TopDownLBL consist of \(\mathcal{H}\)-based trees of depth bounded by \(d\), which generalize from the individual decision stumps of \(\mathcal{H}\) as in TopDown (corresponding to the case \(d=1\)). Hence, at the end of each phase, the depth of \(T\) increases by at most \(d\). The algorithm stops if and when \(H_{P}(c \mid T) \le \varepsilon\).

We use the two following lemmas.

We remark that we recover the standard setting of boosting decision trees when \(d=1\). In this special case, our result matches the depth lower bound mentioned by [26], while guaranteeing a \(\mathcal{O}\bigl(2^{\mathop{\mathrm{depth}}^{c}_{\mathcal{H}}\!\left(\varepsilon\mid P\right)}\bigr) = \mathcal{O}\bigl((1/\varepsilon)^{1/(2\gamma^2)}\bigr)\) tree-size upper bound that is analogous to the ones by [26] and [27].

9 Further Proofs for the Algebraic Characterization↩︎

9.1 Algebraic characterization↩︎

9.2 Algebraic characterization for countable domains↩︎

Let \(\mathcal{H}\subseteq 2^X\) and let \(\mathop{\mathrm{clos_{pw}}}(\mathcal{H})\) be the family of all subsets of \(X\) that are the pointwise limit of some sequence in \(\mathcal{H}\). Clearly \(\mathcal{H}\subseteq \mathop{\mathrm{clos_{pw}}}(\mathcal{H}) \subseteq 2^X\).

10 Remarks on the Graded Complexity Measure Results↩︎

In Section 7 we demonstrated more general guarantees for any graded complexity measure \(\Gamma\), given any domain \(X\) and any hypothesis class \(\mathcal{H}\) over \(X\). Observe that, when \(\mathcal{H}\) is a non-VC class, item (3\('\)) of Theorem 4 states an upper bound on the \(\Gamma\)-complexity rate of order \(\mathcal{O}\bigl(\frac{1}{\varepsilon^d}\bigr)\) for a constant \(d\in\mathbb{N}\). This bound is indeed larger compared to the previous guarantee of \(\mathcal{O}(\log(1/\varepsilon))\) on the depth of \(\mathcal{H}\)-based decision trees (Theorem 1) and it has to do with the generality of the definition of graded complexity measure.

Keeping this in mind, we remark that it is possible to recover the \(\mathcal{O}(\log(1/\varepsilon))\) \(\Gamma\)-complexity rate bound under a stronger assumption on the graded complexity measure \(\Gamma\). In particular, it is sufficient for \(\Gamma\) to satisfy \[\Gamma(f_1 \cup f_2) \le 1 + \max\{\Gamma(f_1), \Gamma(f_2)\} \qquad \forall f_1,f_2\in\mathop{\mathrm{Alg}}(\mathcal{H}) \enspace.\] Note that this condition is satisfied when \(\Gamma\) corresponds to the depth of \(\mathcal{H}\)-based decision trees. For example, consider a similar representation of trees as in Equation 7 using directly \(\mathcal{H}\) for the decision rules of the internal nodes.

Thus, we can follow the same steps as in the proof of Theorem 4 with a particular focus on the construction of \(A\) from the decision tree \(T\) in Equation 7 . It immediately follows that \(\Gamma(A_v^T) \le 3 + \Gamma(A_v) + \max\bigl\{\Gamma(A_u^T), \Gamma(A_w^T)\bigr\}\) for any internal node \(v\notin\mathcal{L}(T)\), where \(u\) and \(w\) are, respectively, the left and right child of \(v\). Now, let \(\rho(z) \subseteq \mathcal{V}(T)\) be the nodes along the path from the root of \(T\) to the leaf \(z\in\mathcal{L}(T)\). We can thus show that \[\Gamma(A) = \mathcal{O}\Biggl(\max_{z\in\mathcal{L}(T)} \sum_{v\in\rho(z)} (\Gamma(A_v)+1)\Biggr) = \mathcal{O}\bigl((k+1)\cdot\mathop{\mathrm{depth}}(T)\bigr) = \mathcal{O}\Bigl(\log\frac{1}{\varepsilon}\Bigr) \enspace,\] where we used the fact that \(T\) has \(\mathop{\mathrm{depth}}(T) \le \frac{1}{2\gamma^2}\log\frac{1}{2\varepsilon}\) and that \(\Gamma(A_v)\le k\) for any internal node \(v\) of \(T\).

References↩︎