Occam's razor
作者： Anselm Blumer , Andrzej Ehrenfeucht , David Haussler , Manfred K. Warmuth
DOI: 10.1016/0020-0190(87)90114-1
关键词: Simplicity 、 Boolean function 、 Polynomial 、 Sequence 、 Inductive reasoning 、 Mathematics 、 Occam's razor 、 Regular language 、 Algorithm 、 Combinatorics 、 Existential quantification
摘要: Abstract We show that a polynomial learning algorithm, as defined by Valiant (1984), is obtained whenever there exists polynomial-time method of producing, for any sequence observations, nearly minimum hypothesis consistent with these observations.
acm.org
elsevier.com
sci-hub.se 参考文章(6)
Michael R. Garey, David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness ,(1979)
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710
Dana Angluin, Carl H. Smith, Inductive Inference: Theory and Methods ACM Computing Surveys. ,vol. 15, pp. 237- 269 ,(1983) , 10.1145/356914.356918
JUDEA PEARL, ON THE CONNECTION BETWEEN THE COMPLEXITY AND CREDIBILITY OF INFERRED MODELS International Journal of General Systems. ,vol. 4, pp. 255- 264 ,(1978) , 10.1080/03081077808960690
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
L. G. Valiant, A theory of the learnable Communications of the ACM. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/1968.1972