file.pdf (193.61 kB)
Download file

Learning DNF from Random Walks

Download (193.61 kB)
journal contribution
posted on 01.01.1977, 00:00 by Nader Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A Servedio
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.

History

Publisher Statement

All Rights Reserved

Date

01/01/1977