Abstract
We prove a new structural lemma for partial Boolean functions f, which we call the seed lemma for DNF. Using the lemma, we give the first subexponential algorithm for proper learning of poly(n)- Term DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity 2( Õ √ n), which is optimal. We also give a new result on certificates for DNF-size, a simple algorithm for properly PAC-learning DNF, and new results on EQ-learning log n-term DNF and decision trees.
Original language | English (US) |
---|---|
Pages (from-to) | 31.1-31.18 |
Journal | Journal of Machine Learning Research |
Volume | 23 |
State | Published - 2012 |
Event | 25th Annual Conference on Learning Theory, COLT 2012 - Edinburgh, United Kingdom Duration: Jun 25 2012 → Jun 27 2012 |
Keywords
- Certificates
- DNF
- Exact learning
- Proper learning
- Query learning
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Statistics and Probability
- Artificial Intelligence