Learning DNF from random walks
Nader H. Bshouty, Elchanan Mossel, Ryan W. O’Donnell, Rocco A. Servedio · 2004
We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}/sup 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.