Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: 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
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, Vijay
Castro Rabal, Jorge; Guijarro Guillem, David
Domingo Soriano, Carlos; Lavín Puente, Víctor Angel
Gavaldà Mestre, Ricard; Guijarro Guillem, David
Balle Pigem, Borja de; Castro Rabal, Jorge; Gavaldà Mestre, Ricard