摘要: Abstract The distribution-independent model of concept learning from examples (“PAC-learning”) due to Valiant (1984) is investigated. It has been shown that the existence an Occam algorithm for a class concepts sufficient condition PAC-learnability (Blumer 1987, 1989). (An randomized polynomial-time that, when given as input sample strings some unknown be learned, outputs small description consistent with sample.) In this paper it many natural classes implies class. More generally, property closure under exception lists defined, and any property, equivalent An interpretation these results classes, data compression.
acm.org
sci-hub.se 参考文章(13)
David Haussler, Learning conjunctive concepts in structural domains national conference on artificial intelligence. ,vol. 4, pp. 466- 470 ,(1987) , 10.1023/A:1022601210986
Robert Hal Sloan, Computational learning theory : new models and algorithms Massachusetts Institute of Technology. ,(1989)
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710
Manfred K. Warmuth, Nick Littlestone, David Haussler, Michael Kearns, Equivalence of models for polynomial learnability conference on learning theory. pp. 42- 55 ,(1988) , 10.5555/93025.93040
Andrzej Ehrenfeucht, David Haussler, Michael Kearns, Leslie Valiant, A general lower bound on the number of examples needed for learning Information & Computation. ,vol. 82, pp. 247- 261 ,(1989) , 10.1016/0890-5401(89)90002-3
Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, Manfred K. Warmuth, Occam's razor Information Processing Letters. ,vol. 24, pp. 377- 380 ,(1987) , 10.1016/0020-0190(87)90114-1
Dana Angluin, Negative Results for Equivalence Queries Machine Learning. ,vol. 5, pp. 121- 150 ,(1990) , 10.1023/A:1022692615781
Robert E. Schapire, The Strength of Weak Learnability Machine Learning. ,vol. 5, pp. 197- 227 ,(1990) , 10.1023/A:1022648800760
Leonard Pitt, Leslie G. Valiant, Computational limitations on learning from examples Journal of the ACM. ,vol. 35, pp. 965- 984 ,(1988) , 10.1145/48014.63140
Manfred K. Warmuth, Towards Representation Independence in PAC Learning AII '89 Proceedings of the International Workshop on Analogical and Inductive Inference. pp. 78- 103 ,(1989) , 10.1007/3-540-51734-0_53