Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333017 | Journal of Computer and System Sciences | 2005 | 16 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio,