Title :
Learning DNF from random walks
Author :
Bshouty, Nader ; Mossel, Elchanan ; O´Donnell, Ryan ; Servedio, Rocco A.
Author_Institution :
Dept. of Comput. Sci., Technion, Haifa, Israel
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.
Keywords :
Boolean functions; Fourier analysis; computational complexity; decision trees; learning (artificial intelligence); Boolean function; DNF; disjunctive normal form; learning decision tree; passive learning model; polynomial time algorithm; random walk; Algorithm design and analysis; Boolean functions; Computer science; Decision trees; Humans; Knowledge representation; Learning systems; Mathematics; Polynomials; Statistics;
Conference_Titel :
Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on
Print_ISBN :
0-7695-2040-5
DOI :
10.1109/SFCS.2003.1238193
