Learning DNF from Random Walks.
N. Bshouty and E. Mossel and
R.
O'Donnell and
R. Servedio.
Journal of Computer and System Sciences
71(3), 2005, pp. 250-265
(special issue for STOC, FOCS, and COLT 2003).
Preliminary version in
44th Annual Symposium on Foundations
of Computer Science (FOCS), 2003, pp. 189-198.
Abstract:
We consider a model of learning Boolean functions from examples
generated by a uniform random walk on $\{0,1\}^n$. We give a
polynomial time algorithm for learning decision trees and DNF
formulas in this model. This is the first efficient algorithm for
learning these classes in a natural passive learning model where
the learner has no influence over the choice of examples used
for learning.
Postscript or
pdf of conference version
pdf of journal version
Back to
main papers page