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.

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.