Learning nearly monotone k-term DNF

Consultar RECERCAT

Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: 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.

Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, Vijay

Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, V

Castro Rabal, Jorge; Guijarro Guillem, David

Balcázar Navarro, José Luis; Castro Rabal, Jorge; Guijarro Guillem, David; Simon, Hans-Ulrich

Balcázar Navarro, José Luis; Castro Rabal, Jorge; Guijarro Guillem, David

Coordinació

Patrocini