Learning nearly monotone k-term DNF

All of RECERCAT

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

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Castro Rabal, Jorge
dc.contributor.author	Guijarro Guillem, David
dc.contributor.author	Lavín Puente, Víctor Angel
dc.date	1996-09
dc.identifier.citation	Castro, J., Guijarro, D., Lavin, V. "Learning nearly monotone k-term DNF". 1996.
dc.identifier.uri	http://hdl.handle.net/2117/83098
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	DNF
dc.subject	Learning monotone
dc.title	Learning nearly monotone k-term DNF
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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 Vitányi result for monotone k-term DNF.