Title :
General bounds on statistical query learning and PAC learning with noise via hypothesis boosting
Author :
Aslam, Javed A. ; Decatur, S.E.
Author_Institution :
Lab. for Comput. Sci., MIT, Cambridge, MA, USA
Abstract :
We derive general bounds on the complexity of learning in the statistical query model and in the PAC model with classification noise. We do so by considering the problem of boosting the accuracy of weak learning algorithms which fall within the statistical query model. This new model was introduced by M. Kearns (1993) to provide a general framework for efficient PAC learning in the presence of classification noise
Keywords :
computational complexity; learning (artificial intelligence); PAC learning; complexity; general bounds; hypothesis boosting; noise; statistical query learning; Boosting; Computer science; Contracts; Extraterrestrial measurements; Laboratories; Machine learning; Machine learning algorithms; Noise measurement; Size measurement; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366859
