To access the full text documents, please follow this link: http://hdl.handle.net/2117/83098

Learning nearly monotone k-term DNF
Castro Rabal, Jorge; Guijarro Guillem, David; Lavín Puente, Víctor Angel
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
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.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
DNF
Learning monotone
info:eu-repo/semantics/publishedVersion
Report
         

Show full item record

Related documents

Other documents of the same author

Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, V
Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, Vijay
Balcázar Navarro, José Luis; Castro Rabal, Jorge; Guijarro Guillem, David; Simon, Hans-Ulrich
Castro Rabal, Jorge; Guijarro Guillem, David
Balcázar Navarro, José Luis; Castro Rabal, Jorge; Guijarro Guillem, David
 

Coordination

 

Supporters