On Learning Monotone Boolean Functions

We consider the problem of learning monotone Boolean functions over {0, 1}/sup n/ under the uniform distribution. Specifically, given a polynomial number of uniform random samples for an unknown monotone Boolean function f, and given polynomial completing time, we would like to approximate f as well as possible. We describe a simple algorithm that we prove achieves error at most 1/2-/spl Omega/(1//spl radic/n), improving on the previous best bound of 1/2-/spl Omega/((log/sup 2/ n)/n). We also prove that no algorithm, given a polynomial number of samples, can guarantee error 1/2-/spl omega/((log n)//spl radic/n), improving on the previous best hardness bound of O(1//spl radic/n). These lower bounds hold even if the learning algorithm is allowed membership queries. Thus this paper settles to an O(log n) factor the question of the best achievable error for learning the class of monotone Boolean functions with respect to the uniform distribution.

Authors

• Avrim Blum
• Carl Burch
• John Langford 0001

Keywords

• Boolean functions
• Polynomials
• Hip
• Radio access networks
• Identity-based encryption
• Circuits
• Approximation algorithms
• Upper bound
• Boolean Function
• Monotone Boolean Function
• Lower Bound
• Uniform Distribution
• Learning Algorithms
• Functional Class
• Polynomial Number
• Proof Of Theorem
• Conditional Distribution
• Positive Index
• Head And Tail
• Probability 1
• Lexicographic
• Strong Learning
• Weak Learners
• Target Concept
• Fraction Of Points