<p>For bitstring to boolean functions, people usually build <a href="http://en.wikipedia.org/wiki/Binary_decision_diagram" rel="nofollow">binary decision diagrams</a> 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:</p>

<p>Hinsberger, U., Kolla, R., and Kunjan, T. [1997] "<a href="http://en.scientificcommons.org/43429606" rel="nofollow">Approximative Representation of boolean Functions by size controllable ROBDD's</a>"</p>

<p>Ravi, K., McMillan, K.L., Shiple, T.R., and Somenzi, F. [1998] "<a href="http://portal.acm.org/citation.cfm?id=277044.277168" rel="nofollow">Approximation and decomposition of binary decision diagrams</a>"</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-13T14:03:17.297Z
2011-08-13T14:03:17.297Z
Artem Kaznatcheev
<p>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.</p>

CC BY-SA 3.0
2011-07-15T07:11:11.273Z
Not sure how fast is an FFT in a 5000 dimensional space...
rodrigob
CC BY-SA 3.0
2011-07-14T12:57:35.467Z
2011-07-14T12:57:35.467Z
noir
<p>I have a function $f: \mathbb{D} \rightarrow \{0,1\}$ where $\mathbb{D} \in \mathbb{R}^{5000}$.</p>

<p>I would like to approximate $f$ using a decision tree.</p>

<p>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.</p>

<p>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).</p>

<p>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.</p>

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

<p>Thanks for you answers.</p>

CC BY-SA 3.0
2011-07-13T23:32:17.343Z
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.?
Lev Reyzin
CC BY-SA 3.0
2011-07-14T12:21:19.837Z
in my case $f$ is either a linear function, or more commonly a non-linear svm (rbf, min kernel, etc.)
rodrigob
CC BY-SA 3.0
2011-07-14T12:22:34.750Z
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.
rodrigob
<approximation-algorithms><decision-trees>
Building a decision tree to approximate a known function (not to learn an unknown function)
rodrigob
# Building a decision tree to approximate a known function (not to learn an unknown function)

(Asked by: username_0 on 2011-07-13)

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.

**Tags:** approximation-algorithms, decision-trees

> **Comments:**
> **username_1**: 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.?  
> **username_0**: in my case $f$ is either a linear function, or more commonly a non-linear svm (rbf, min kernel, etc.)  
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-08-13. Score: 2

For bitstring to boolean functions, people usually build [binary decision diagrams](http://en.wikipedia.org/wiki/Binary_decision_diagram) 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](http://en.scientificcommons.org/43429606)"

Ravi, K., McMillan, K.L., Shiple, T.R., and Somenzi, F. [1998] "[Approximation and decomposition of binary decision diagrams](http://portal.acm.org/citation.cfm?id=277044.277168)"

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.


---

### Answer by username_3 on 2011-07-14. Score: 1

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.

> **Comments:**
> **username_0**: Not sure how fast is an FFT in a 5000 dimensional space...  

---

