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

Learning monotone term decision lists
Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, Vijay
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k>0, k-term monotone decision lists are exactly and properly learnable with n^O(k) membership queries in O(n^(k^3)) time. We also show n^Omega(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k>1) and general monotone decision lists are not learnable with equivalence queries alone.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Learning monotone
Decision lists
info:eu-repo/semantics/publishedVersion
Report
         

Show full item record

Related documents

Other documents of the same author

Castro Rabal, Jorge; Guijarro Guillem, David; Lavín Puente, Víctor Angel
Domingo Soriano, Carlos; Lavín Puente, Víctor Angel
Gavaldà Mestre, Ricard; Guijarro Guillem, David
Castro Rabal, Jorge; Guijarro Guillem, David
 

Coordination

 

Supporters