Loading...
Loading...

Go to the content (press return)

A Note on learning decision lists

Author
Castro, J.
Type of activity
Report
Date
1995-01
Code
LSI-95-2-R
Repository
http://hdl.handle.net/2117/96750 Open in new window
Abstract
We show an algorithm that learns decision lists via equivalence queries, provided that a set G including all terms of the target list is given. The algorithm runs in time polynomial in the cardinality of G. From this last learning algorithm, we prove that log n-decision lists - the class of decision lists such that all their terms have low Kolmogorov complexity - are simple pac-learnable.
Citation
Castro, J. "A Note on learning decision lists". 1995.
Keywords
Learning algorithm, Learning decision lists
Group of research
LARCA - Laboratory of Relational Algorithmics, Complexity and Learnability

Participants

Attachments