Abstract | ||
---|---|---|
. We prove that log n-decision lists ---the class of decision listssuch that all their terms have low Kolmogorov complexity--- are learnablein the simple PAC learning model. The proof is based on a transformationfrom an algorithm based on equivalence queries (found independently bySimon). Then we introduce the class of simple decision lists, and extendour algorithm to show that simple decision lists are simple-PAC learnableas well. This last result is relevant in that it is, to our... |
Year | DOI | Venue |
---|---|---|
1995 | 10.1007/3-540-60454-5_42 | ALT |
Keywords | Field | DocType |
simple decision lists,simple pac learning,pac learning | Kolmogorov complexity,Computer science,Decision list,Theoretical computer science,Equivalence (measure theory),Artificial intelligence,Machine learning | Conference |
ISBN | Citations | PageRank |
3-540-60454-5 | 8 | 0.69 |
References | Authors | |
7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jorge Castro | 1 | 13 | 1.94 |
José L. Balcázar | 2 | 701 | 62.06 |