|
NeuroCOLT
Technical Report NC-TR-97-017
Learning
Monotone Term Decision Lists
David
Guijarro, Victor Lavin
Universitat Politecnica de Catalunya
Spain
Vijay
Raghavan
Vanderbilt University
USA
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 \ge 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 \ge 2$) and general monotone decision lists are not learnable
with equivalence queries alone.
Download Compressed Postscript
|