Learning nearly monotone k-term DNF
Copyright policy )Learning nearly monotone k-term DNF
This note studies the learnability of the class k-term DNF with a bounded number of negations per term. We study the case of learning with membership queries alone, and give tight upper and lower bounds on the number of negations that makes the learning task feasible. We also prove a negative result for equivalence queries. Finally, we show that a slight modification in our algorithm proves that the considered class is also learnable in the Simple PAC model, extending Li and Vitányi result for monotone k-term DNF.
Computational learning theory, Kolmogorov complexity, Algorithmic information theory (Kolmogorov complexity, etc.), :Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC], concept learning, DNF, Learning monotone, Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica, query learning
Computational learning theory, Kolmogorov complexity, Algorithmic information theory (Kolmogorov complexity, etc.), :Informàtica::Informàtica teòrica [Àrees temàtiques de la UPC], concept learning, DNF, Learning monotone, Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica, query learning
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).3 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!