Efficient noise-tolerant learning from statistical queries
作者： Michael Kearns
关键词: Theoretical computer science 、 Sample space 、 Computer science 、 Probably approximately correct learning 、 Algorithmic learning theory 、 Machine learning 、 Artificial intelligence 、 Oracle 、 Semi-supervised learning 、 Probabilistic logic 、 Computational learning theory 、 Learnable Evolution Model
摘要: In this paper, we study the problem of learning in presence classification noise probabilistic model Valiant and its variants. order to identify class “robust” algorithms most general way, formalize a new but related from statistical queries. Intuitively, algorithm is forbidden examine individual examples unknown target function, given acess an oracle providing estimates probabilities over sample space random examples.One our main results shows that any functions learnable queries fact with Valiant's model, rate approaching information-theoretic barrier 1/2. We then demonstrate generality query showing practically every variants can also be learned (and thus noise). A notable exception statement parity functions, which prove not queries, for no noise-tolerant known.
acm.org
core.ac.uk
sci-hub.se 参考文章(37)
Marvin Minsky, Seymour A. Papert, Perceptrons: An Introduction to Computational Geometry, Expanded Edition ,(1987)
Robert Elias Schapire, The design and analysis of efficient learning algorithms ,(1992)
Michael J. Kearns, Computational Complexity of Machine Learning ,(1990)
Philip D. Laird, Learning from Good and Bad Data ,(1988)
Umesh V. Vazirani, Michael J. Kearns, An Introduction to Computational Learning Theory ,(1994)
Michael Kearns, Ming Li, Learning in the Presence of Malicious Errors SIAM Journal on Computing. ,vol. 22, pp. 807- 837 ,(1993) , 10.1137/0222052
N. Linial, Y. Mansour, N. Nisan, Constant depth circuits, Fourier transform, and learnability foundations of computer science. pp. 574- 579 ,(1989) , 10.1109/SFCS.1989.63537
David Haussler, Quantifying inductive bias: AI learning algorithms and Valiant's learning framework Artificial Intelligence. ,vol. 36, pp. 177- 221 ,(1988) , 10.1016/0004-3702(88)90002-1
A. Ehrenfeucht, Leslie Valiant, David Haussler, Michael Kearns, A general lower bound on the number of examples needed for learning conference on learning theory. pp. 139- 154 ,(1988) , 10.5555/93025.93068
L. G. Valiant, A theory of the learnable symposium on the theory of computing. ,vol. 27, pp. 1134- 1142 ,(1984) , 10.1145/800057.808710