Decision tree heuristics can fail, even in the smoothed setting

Greedy decision tree learning heuristics are among the earliest and most basic algorithms in machine learning. Well-known examples include ID3 [Qui86], its successor C4.5 [Qui93], and CART [BFSO84], all of which continue to be widely employed in everyday ML applications. These simple heuristics build a decision tree for labeled dataset $S$ in a greedy, top-down fashion. They first identify a “good” attribute to query as the root of the tree. This induces a partition of $S$ into $S_{0}$ and $S_{1}$, and the left and right subtrees are built recursively using $S_{0}$ and $S_{1}$ respectively.

In more detail, each heuristic is associated with an impurity function $\mathscr{G}:[0,1]\to[0,1]$ that is concave, symmetric around $\frac{1}{2}$, and satisfies $\mathscr{G}(0)=\mathscr{G}(1)=0$ and $\mathscr{G}(\frac{1}{2})=1$. Examples include the binary entropy function $\mathscr{G}(p)=\textnormal{H}(p)$ that is used by ID3 and C4.5, and the Gini impurity function $\mathscr{G}(p)=4p(1-p)$ that is used by CART; Kearns and Mansour [KM96] proposed and analyzed the function $\mathscr{G}(p)=2\sqrt{p(1-p)}$. For a target function $f:\mathbb{R}^{n}\to\{0,1\}$ and a distribution $\mathcal{D}$ over $\mathbb{R}^{n}$, these heuristics build a decision tree hypothesis for $f$ as follows:

1. 1.

   Split: Query $\mathds{1}[x_{i}\geq\theta]$ as the root of the tree, where $x_{i}$ and $\theta$ are chosen to (approximately) maximize the purity gain with respect to $\mathscr{G}$:

   $$\mathscr{G}\text{-}\mathrm{purity}\text{-}\mathrm{gain}_{\mathcal{D}}(f,x_{i})\coloneqq\mathscr{G}(\operatorname*{\mathbb{E}}\left[f\right])-\big{(}\Pr\left[x_{i}\geq\theta\right]\cdot\mathscr{G}(\operatorname*{\mathbb{E}}\left[f_{x_{i}\geq\theta}\right])+\Pr\left[x_{i}<\theta\right]\cdot\mathscr{G}(\operatorname*{\mathbb{E}}\left[f_{x_{i}<\theta}\right])\big{)},$$

   where the expectations and probabilities above are with respect to randomly drawn labeled examples $(x,f(x))$ where $x\sim\mathcal{D}$, and $f_{x_{i}\geq\theta}$ denotes the restriction of $f$ to inputs satisfying $x_{i}\geq\theta$ (and similarly for $f_{x_{i}<\theta}$).

2. 2.

   Recurse: Build the left and right subtrees by recursing on $f_{x_{i}\geq\theta}$ and $f_{x_{i}<\theta}$ respectively.

3. 3.

   Terminate: The recursion terminates when the depth of the tree reaches a user-specified depth parameter. Each leaf $\ell$ of the tree is labeled by $\mathrm{round}(\operatorname*{\mathbb{E}}\left[f_{\ell}\right])$, where we associate $\ell$ with the restriction corresponding to the root-to-$\ell$ path within the tree and $\mathrm{round}(p)\coloneqq\mathds{1}[p\geq\frac{1}{2}]$.

Given the popularity and empirical success of these heuristics¹¹1CART and C4.5 were named as two of the “Top 10 algorithms in data mining” by the International Conference on Data Mining (ICDM) community [WKQ⁺08]; other algorithms on this list include $k$-means, $k$-nearest neighbors, Adaboost, and PageRank, all of whose theoretical properties are the subjects of intensive study. C4.5 has also been described as “probably the machine learning workhorse most widely used in practice to date” [WFHP16]., it is natural to seek theoretical guarantees on their performance:

Let $f:\mathbb{R}^{n}\to\{0,1\}$ be a target function and $\mathcal{D}$ be a distribution over $\mathbb{R}^{n}$. Can we obtain a high-accuracy hypothesis for $f$ by growing a depth-$k^{\prime}$ tree using these heuristics, where $k^{\prime}$ is not too much larger than $k$, the optimal decision tree depth for $f$? ($\diamondsuit$)

Recall that an impurity function $\mathscr{G}:[0,1]\to[0,1]$ is concave, symmetric with respect to $\frac{1}{2}$, and satisfies $\mathscr{G}(0)=\mathscr{G}(1)=0$ and $\mathscr{G}(\frac{1}{2})=1$. We further quantify the concavity and smoothness of $\mathscr{G}$ as follows:

For a boolean function $f:\{0,1\}^{n}\to\{0,1\}$ and index $i\in[n]$, we write $f_{x_{i}=0}$ and $f_{x_{i}=1}$ to denote the restricted functions obtained by fixing the $i$-th input bit of $f$ to either $0$ or $1$. Formally, each $f_{x_{i}=b}$ is a function over $\{0,1\}^{n}$ defined as $f_{x_{i}=b}(x)=f(x^{i\to b})$, where $x^{i\to b}$ denotes the string obtained by setting the $i$-th bit of $x$ to $b$. More generally, a restriction $\pi$ is a list of constraints of form “$x_{i}=b$” in which every index $i$ appears at most once. For restriction $\pi=(x_{i_{1}}=b_{1},x_{i_{2}}=b_{2},\ldots)$, the restricted function $f_{\pi}:\{0,1\}^{n}\to\{0,1\}$ is similarly defined as $f_{\pi}(x)=f(x^{i_{1}\to b_{1},i_{2}\to b_{2},\ldots})$.

In a decision tree, each node $v$ naturally corresponds to a restriction $\pi_{v}$ formed by the variables queried by the ancestors of $v$ (excluding $v$ itself). We use $f_{v}$ as a shorthand for $f_{\pi_{v}}$. We say that a decision tree learning algorithm is impurity-based if, in the tree returned by the algorithm, every internal node $v$ queries a variable that maximizes the purity gain with respect to $f_{v}$.

The above definition assumes that the algorithm exactly maximizes the $\mathscr{G}$-purity gain at every split, while in reality, the purity gains can only be estimated from a finite dataset. We therefore consider an idealized setting that grants the learning algorithm with infinitely many training examples, which, intuitively, strengthens our lower bounds. (Our lower bounds show that in order for an algorithm to recover a good tree—a high-accuracy hypothesis whose depth is close to that of the target—it would need to query a variable that has exponentially smaller purity gain than that of the variable with the largest purity gain. Hence, if purity gains are estimated using finitely many random samples as is done in reality, the strength of our lower bounds imply that with extremely high probability, impurity-based heuristics will fail to build a good tree; see Remark 5 for a detailed discussion.)

When a decision tree queries variable $x_{i}$ on function $f$, it naturally induces two restricted functions $f_{x_{i}=0}$ and $f_{x_{i}=1}$. The following lemma states that the purity gain of querying $x_{i}$ is roughly the squared difference between the averages of the two functions, up to a factor that depends on the impurity function $\mathscr{G}$ and the data distribution $\mathcal{D}$. We say that a product distribution over $\{0,1\}^{n}$ is $\delta$-balanced if the expectation of each of the $n$ coordinates is in $[\delta,1-\delta]$.

Our lower bounds hold with respect to all $\delta$-balanced product distributions. We compare this to the definition of a $c$-smoothened $\delta$-balanced product distribution from [BDM20].

Since our lower bounds hold against all $\delta$-balanced product distributions, it also holds against all $c$-smoothened $\delta$-balanced product distributions.

Our goal is to construct a target function that can be computed by a depth-$k$ decision tree, but on which impurity-based algorithms must build to depth $2^{\Omega(k)}$ or have large error. To do so, we construct a decision tree target $T$ where the variables with largest purity gain are at the bottom layer of $T$ (adjacent to its leaves). Intuitively, impurity-based algorithms will build their decision tree hypothesis for $T$ by querying all the variables in the bottom layer of $T$ before querying any of the variables higher up in $T$. Our construction will be such that until the higher up variables are queried, it is impossible to approximate the target with any nontrivial error. Summarizing informally, we show that impurity-based algorithms build its decision tree hypothesis for our target by querying variables in exactly the “wrong order”.

The starting point of our construction is the well known addressing function. For $k\in\mathbb{N}$, the addressing function $f:\{0,1\}^{k+2^{k}}\to\{0,1\}$ is defined as follows: Given “addressing bits” $z\in\{0,1\}^{k}$ and “memory bits” $y\in\{0,1\}^{2^{k}}$, the output $f(y,z)$ is the $z^{\text{th}}$ bit of $y$, where “$z^{\text{th}}$ bit” is computed by interpreting $z$ as a base-2 integer. Note that the addressing function is computable by a decision tree of depth $k+1$ that first queries the $k$ addressing bits, followed by the appropriate memory bit.

For our lower bound, we would like the variables with the highest purity gain to be the memory bits. However, for smoothed product distributions, the addressing bits might have higher purity gain than the memory bits, and impurity-based algorithms might succeed in learning the addressing function. We therefore modify the addressing function by making each addressing bit the parity of multiple new bits. We show that by making each addressing bit the parity of sufficiently many new bits, we can drive the purity gain of these new bits down to the point where the memory bits have the highest purity gain as desired—in fact, larger than the addressing bits by a multiplicative factor of $e^{\Omega(k)}$. (Making each addressing bit the parity of multiple new bits increases the depth of the target, so this introduces technical challenges we have to overcome in order to achieve the strongest parameters.)

Our main theorem is formally restated as follows.

An extension of our construction and its analysis shows that the guarantees of Brutzkus et al. for targets that are $k$-juntas cannot extend to the agnostic setting. Roughly speaking, while our variant of the addressing function from Theorem 4 is far from all $k$-juntas, it can be made close to one by fixing most of the memory bits. We obtain our result by showing that our analysis continues to hold under such a restriction.

We start by giving a simplified construction that proves a weaker version of Theorem 4, in which the $O(k/\delta)$ depth in condition (1) is relaxed to $O(k^{2}/\delta)$. For integers $c,k\geq 1$, we define a boolean function $f_{c,k}:\{0,1\}^{ck^{2}+2^{k}}\to\{0,1\}$ as follows. The input of $f_{c,k}$ is viewed as two parts: $ck^{2}$ addressing bits $x_{i,j}$ indexed by $i\in[k]$ and $j\in[ck]$, and $2^{k}$ memory bits $y_{a}$ indexed by $a\in\{0,1\}^{k}$. The function value $f_{c,k}(x,y)$ is defined by first computing $z_{i}(x)=\bigoplus_{j=1}^{ck}x_{i,j}$ for every $i\in[k]$, and then assigning $f_{c,k}(x,y)=y_{z(x)}$.

In other words, $f_{c,k}$ is a disjoint composition of the $k$-bit addressing function and the parity function over $ck$ bits. Given addressing bits $x$ and memory bits $y$, the function first computes a $k$-bit address by taking the XOR of the addressing bits in each group of size $ck$, and then retrieves the memory bit with the corresponding address. Clearly, $f_{c,k}$ can be computed by a decision tree of depth $ck^{2}+1$ that first queries all the $ck^{2}$ addressing bits and then queries the relevant memory bit in the last layer.

When proving the weaker version of Theorem 4, each hard instance $f_{c,k}$ has $\Theta(k^{2})$ addressing bits grouped into $k$ disjoint subsets, and the $k$-bit address is defined by the XOR of bits in each subset. We will prove Theorem 4 using a slightly different construction that computes address from $k$ overlapping subsets of only $O(k)$ addressing bits.

For integers $c,k\geq 1$ and a list of $k$ sets $S=(S_{1},S_{2},\ldots,S_{k})$ where each $S_{i}\subseteq[ck]$, we define a boolean function $f_{c,k,S}:\{0,1\}^{ck+2^{k}}\to\{0,1\}$ as follows. The input of $f_{c,k,S}$ is again divided into two parts: $ck$ addressing bits $x_{1},x_{2},\ldots,x_{ck}$ and $2^{k}$ memory bits $y_{a}$ indexed by a $k$-bit address $a$. The function value $f(x,y)$ is computed by taking $z_{i}(x)=\bigoplus_{j\in S_{i}}x_{j}$ and then $f(x,y)=y_{z(x)}$. Clearly, $f_{c,k,S}$ can be computed by a decision tree of depth $ck+1$ that first queries all the $ck$ addressing bits $x_{1},x_{2},\ldots,x_{ck}$, and then queries the relevant memory bit $y_{z(x)}$.

Let $\operatorname*{\triangle}_{i=1}^{k}S_{i}$ denote the $k$-ary symmetric difference of sets $S_{1}$ through $S_{k}$, i.e., the set of elements that appear in an odd number of sets. We say that a list of sets $S=(S_{1},S_{2},\ldots,S_{k})$ has distance $d$, if any non-empty collection of sets has a symmetric difference of size at least $d$, i.e., $\left|\operatorname*{\triangle}_{i\in I}S_{i}\right|\geq d$ for every non-empty $I\subseteq[k]$. In the following, we prove analogs of Lemmas 2 and 4 for function $f_{c,k,S}$ assuming that $S$ has a large distance; Theorem 4 would then follow immediately.