Agnostically Learning Decision Trees
- Parikshit Gopalan ,
- Adam Tauman Kalai ,
- Adam R. Klivans
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing (STOC), 2008 |
Published by ACM Press
We consider the problem of learning a decision tree in the presence of arbitrary noise. More formally, we are given black-box access (a type of active learning) to an arbitrary binary function on n bits, and our output is a function whose accuracy is almost as good as that of the best size-s decision tree, where accuracy is measured over the uniform distribution on inputs.