Learning DNF from Random Walks

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.

Authors

• Nader H. Bshouty
• Elchanan Mossel
• Ryan O'Donnell
• Rocco A. Servedio

Keywords

• Polynomials
• Computer science
• Boolean functions
• Decision trees
• Statistics
• Humans
• Knowledge representation
• Mathematics
• Algorithm design and analysis
• Learning systems
• Random Walk
• Learning Models
• Decision Tree
• Regression Tree
• Polynomial-time Algorithm
• Boolean Function
• Choice Of Examples
• Uniform Distribution
• Learning Algorithms
• Random Model
• Running Time
• Sum Of Squares
• Correction Algorithm
• Fourier Analysis
• Probability 1
• Fourier Coefficients
• Hyperacusis
• Random Walk Model
• Uniform Model
• Random Bits
• Concept Of Class