# Building a decision tree to approximate a known function (not to learn an unknown function)

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 ?

• 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.? Jul 13, 2011 at 23:32
• Why did you decide to use decision trees for that problem ? What kind of function do you want to approximate ? Regards.
– user5905
Jul 14, 2011 at 11:12
• in my case $f$ is either a linear function, or more commonly a non-linear svm (rbf, min kernel, etc.) Jul 14, 2011 at 12:21
• 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. Jul 14, 2011 at 12:22

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.