Tight Bounds on Proper Equivalence Query Learning of DNF

Details Tight Bounds on Proper Equivalence Query Learning of DNF Tight Bounds on Proper Equivalence Query Learning of DNF

2011-11-04

arxiv.org/abs/1111.1124v1

Computer Science

Learning

Scientific paper

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^{(\tilde{O}{\sqrt{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.

Affiliated with

Also associated with

No associations

Rating

Tight Bounds on Proper Equivalence Query Learning of DNF does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight Bounds on Proper Equivalence Query Learning of DNF, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight Bounds on Proper Equivalence Query Learning of DNF will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-101034