2011/11/04 by Lisa Hellerstein, Hellerstein, Lisa, Devorah Kletenik +6
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #cs.CC #cs.LG
paper · pdf · doi:10.48550/arxiv.1111.1124
arxiv created 2011/11/04 · openalex publication_date 2011/11/04 · arxiv updated 2011/11/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31
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 DNF in Angluin's Equivalence Query (EQ) model. The algorithm has time and query complexity 2^(O√(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.