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

Publication | Publication

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.