|
NeuroCOLT
Technical Report NC-TR-97-018
Learning nearly
monotone k-term DNF
Jorge
Castro, David Guijarro, Victor Lavin
Universitat Politecnica de Catalunya
Spain
Abstract
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 Vitanyi result for monotone k-term DNF.
Download Compressed Postscript
|