I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$.

I would like to approximate $f$ using a decision tree.

Up to now I have only found literature in the context of machine learning, where $f$ is unknown, some samples $(x_i,\ y_i=f(x_i) + \mathrm{noise})$ are available and $f$ is estimated using a decision tree. That is a learning problem.

In my case I have a known (non trivial) expression for $f$ and I want to obtain the shortest binary decision tree for an arbitrarily good approximation (up to a specific error $\epsilon$). This seem to be a different problem than the learning problem (for instance, there is no regularization term to ensure generalization).

I suspect this problem to "hard". I assume some literature must exist on "no guarantees, greedy approaches" or similar, but I have not be able to find any.

Could any of you point me out some paper or book referring to this problem ?

Thanks for you answers.

  • 2
    $\begingroup$ This is not so different from learning, as one could generate samples from the function and use a learning algorithm to "learn" a tree from the samples (you don't even need to add noise). Unfortunately, nobody knows how to learn decision trees (even without noise), but it is not suspected to be "hard." Of course, if you have an expression for $f$, then you might do better, but I suspect it depends on what $f$ is: is it a polynomial, etc.? $\endgroup$
    – Lev Reyzin
    Jul 13, 2011 at 23:32
  • 1
    $\begingroup$ Why did you decide to use decision trees for that problem ? What kind of function do you want to approximate ? Regards. $\endgroup$
    – user5905
    Jul 14, 2011 at 11:12
  • $\begingroup$ in my case $f$ is either a linear function, or more commonly a non-linear svm (rbf, min kernel, etc.) $\endgroup$
    – rodrigob
    Jul 14, 2011 at 12:21
  • 1
    $\begingroup$ the goal to is be able to evaluate $f$ "very fast" in the most common cases and only evaluate the "slow $f$" in the cases nearby the boundaries (hard, uncommon cases). Decision trees are fast to evaluate and can approximate any function, so they seem like good candidates. $\endgroup$
    – rodrigob
    Jul 14, 2011 at 12:22

2 Answers 2


For bitstring to boolean functions, people usually build binary decision diagrams instead of decision trees to represent functions compactly. If you want to find a small BDD and are willing to sacrifice correctness on a few inputs (as your question implies) then you might want to look into approximate BDDs as studied in the following two papers:

Hinsberger, U., Kolla, R., and Kunjan, T. [1997] "Approximative Representation of boolean Functions by size controllable ROBDD's"

Ravi, K., McMillan, K.L., Shiple, T.R., and Somenzi, F. [1998] "Approximation and decomposition of binary decision diagrams"

I am not sure if there is work that generalizes this for $\mathbb{R}^d \supset \mathbb{D} \rightarrow \{0,1\}$ functions, but I would use those papers as a starting point and do a forward-reference search.


In general you could look in basis-expansion approaches like fourier or wavelets. Choose a balance between number of basis functions and approximation error. For boundaries some more effort might be needed. FFT is quite fast too compute nowadays. However, there is no guarantee about speed since you need to evaluate all the basis used.

  • $\begingroup$ Not sure how fast is an FFT in a 5000 dimensional space... $\endgroup$
    – rodrigob
    Jul 15, 2011 at 7:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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