Algorithm for optimizing decision trees

Background

A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs are labeled by outputs in $\{A,B\}$, and each edge is labeled by $0$ for the left child and $1$ for the right child. To apply a tree to an input $x$:

1. Start at the root
2. if you are at leaf, you output the leaf label $A$ or $B$ and terminate
3. Read the label $j$ of your current node, if $x_j = 0$ then move to the left child and if $x_j = 1$ then move to the right child.

The tree is used as a way to evaluate a functions, in particular we say a tree $T$ represents a total function $f$ if for each $x \in \{0,1\}^n$ we have $T(x) = f(x)$. The query complexity of a tree is its depth, and the query complexity of a function is the depth of the smallest tree that represents it.

Problem

Given a binary decision tree T output a binary decision tree T' of minimal depth such that T and T' represent the same function.

Question

What is the best known algorithm for this? Are any lower bounds known? What if we know that the $\text{depth}(T') = O(\log \text{depth}(T))$? What about if we only require $T'$ to be of approximately minimal depth?

Naive approach

The naive approach is given $d = \text{depth}(T)$ to recursively enumerate all binary decision trees of depth $d - 1$ while testing if they evaluate to the same thing as $T$. This seems to require $O(\frac{d 2^n n!}{(n - d)!})$ steps (assuming that it takes $d$ steps to check what $T(x)$ evaluates to for an arbitrary $x$). Is there a better approach?

Motivation

This question is motivated by a previous question on the trade off between query complexity and time complexity. In particular, the goal is to bound the time separation for total functions. We can make a tree $T$ from a time optimal algorithm with runtime $t$, and then we would like to convert it to a tree $T'$ for a query optimal algorithm. Unfortunately, if $t \in O(n!/(n - d)!)$ (and often $d \in \Theta(n)$) the bottleneck is the conversion. It would be nice if we could replace $n!/(n - d)!$ by something like $2^d$.

• Finding the optimal decision tree is NP-complete. I was taught that in Decision theory and Data mining classes, however those were based on notes and I am not aware of the original paper that introduced the result. – chazisop Jul 31 '11 at 13:09
• @chazisop cool, thanks. It is not obvious to me that finding the optimal decision tree is in NP, but I will think about it/search for it some more. Sometimes knowing the theorem statement is halfway to proving it :D. – Artem Kaznatcheev Jul 31 '11 at 16:42
• I think the earliest reference for this is: Lower Bounds on Learning Decision Lists and Trees. (Hancock et al. 1994) cs.uwaterloo.ca/~mli/dl.ps – Lev Reyzin Aug 25 '11 at 1:37
• The proof that finding the optimal decision tree is a NP-complete problem was given by Laurent Hyafil and Ronald L. Rivest in Constructing optimal binary decision trees is NP-complete (1976). reference: here – antoine Nov 5 '13 at 20:47

I have 3 answers, all giving somewhat different hardness results.

Let $f: \{0,1\}^n \rightarrow \{0,1\}$ be some function.

Given a decision tree $T$ computing $f$ and a number, it is NP-hard to tell if there exists a decision tree $T'$ computing $f$ of size at most that number. (Zantema and Bodlaender '00)

Given a decision tree $T$ computing $f$, it is NP hard to approximate the smallest decision tree computing $f$ to any constant factor. (Sieling '08)

Let $s$ be the size of the smallest decision tree computing $f$. Given a decision tree $T$ computing $f$, assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, one cannot find an equivalent decision tree $T'$ of size $s^k$ for any $k \ge 0$.

I think that this stronger answer (relying on a weaker assumption) can be made from known results in the learning theory of Occam algorithms for decision trees, via the following argument:

1. Is it possible to find a decision tree on $n$ variables in time $n^{\log s}$, where $s$ is the smallest decision tree consistent with examples coming from a distribution (PAC model). (Blum '92)
2. Assuming $NP \subsetneq DTIME(2^{n^\epsilon})$ for some $\epsilon < 1$, we cannot PAC learn size $s$ decision trees by size $s^k$ decision trees for any $k \ge 0$. (Alekhnovich et al. '07)

These two results seem to imply a hardness result for your problem. On the one hand (1), we can find a large decision tree; on the other hand (2), we shouldn't be able to minimize it to get an equivalent "small" one, of size $s^k$, even when one exists of size $s$.

• (I found your answer from this answer, which was posted less than an hour ago.) $\:$ It looks like "$\epsilon < 1$" can be replaced with "positive $\epsilon$, since decreasing $\epsilon$ makes the containment's right-hand-side smaller. $\:$ Also, where in that paper is 2. shown? $\;\;\;\;$ – user6973 Jul 7 '15 at 0:51
• See bullet point #2 in the abstract here: researcher.watson.ibm.com/researcher/files/us-vitaly/… – Lev Reyzin Jul 7 '15 at 11:46
• (coming from the same answer as Ricky Demer) could you detail a bit more how do you get "answer 3" from points 1. and 2.? I am not very familiar with learning theory and have a hard time connecting the parts... – Marc Jul 8 '15 at 17:03
• This consistency problem and learnability are closely related via Occam's razor. The idea is that if you can find a consistent function from a small set, you can succeed in PAC learning. Therefore a hardness of learning result implies a "hardness of consistency" result. I'm not sure how much more I can explain in a comment... – Lev Reyzin Jul 8 '15 at 18:24
• As far as I understand it, the algorithm evoked for 1. does not run in time $Poly(n,s)$ which would be necessary to get a contradiction with 2. (the precise result in the article if I got it correctly says that there is no polytime learning algorithm for decision trees). So there might be a problem with your argumentation. – Marc Jul 10 '15 at 9:09