16
$\begingroup$

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.
  4. jump to step (2)

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – chazisop Jul 31 '11 at 13:09
  • $\begingroup$ @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. $\endgroup$ – Artem Kaznatcheev Jul 31 '11 at 16:42
  • $\begingroup$ 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 $\endgroup$ – Lev Reyzin Aug 25 '11 at 1:37
  • 1
    $\begingroup$ 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 $\endgroup$ – antoine Nov 5 '13 at 20:47
16
$\begingroup$

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

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

Answer 1

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)

Answer 2

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)

Answer 3

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$.

$\endgroup$
  • $\begingroup$ (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? $\;\;\;\;$ $\endgroup$ – user6973 Jul 7 '15 at 0:51
  • $\begingroup$ See bullet point #2 in the abstract here: researcher.watson.ibm.com/researcher/files/us-vitaly/… $\endgroup$ – Lev Reyzin Jul 7 '15 at 11:46
  • $\begingroup$ (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... $\endgroup$ – Marc Jul 8 '15 at 17:03
  • $\begingroup$ 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... $\endgroup$ – Lev Reyzin Jul 8 '15 at 18:24
  • $\begingroup$ 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. $\endgroup$ – Marc Jul 10 '15 at 9:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.