5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 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 ♦
    Commented 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
    Commented 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
    Commented 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
    Commented Jul 14, 2011 at 12:22

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

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

Your Answer

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

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