Decision tree approximations of Boolean functions
Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function \(f,\) say as a read-once branching program, one can find a decision tree \(T\) which approximates \(f\) to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent \(f\) and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function \(f\) instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.
- Constructing optimal binary decision trees is NP-complete
- Equivalence of free Boolean graphs can be decided probabilistically in polynomial time
- Exact learning Boolean functions via the monotone theory
- Exact learning when irrelevant variables abound
- Finding small equivalent decision trees is hard
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1306863 (Why is no real title available?)
- Learning decision trees from random examples
- Occam's razor
- On boolean decision trees with faulty nodes
- Partial Occam's Razor and its applications
- Learning decision trees from random examples
- Improved time complexities for learning Boolean networks
- scientific article; zbMATH DE number 6351494 (Why is no real title available?)
- On boolean decision trees with faulty nodes
- On the complexity of problems on simple games
- Algorithmic Learning Theory
- Properly learning decision trees in almost polynomial time
- Learning stochastic decision trees
This page was built for publication: Decision tree approximations of Boolean functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5958322)
