Título:
|
Learning monotone term decision lists
|
Autor/a:
|
Guijarro Guillem, David; Lavín Puente, Víctor Angel; Raghavan, Vijay
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
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. |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Learning monotone -Decision lists |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|