{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:40:12Z","timestamp":1769974812120,"version":"3.49.0"},"reference-count":34,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[1994,6,1]],"date-time":"1994-06-01T00:00:00Z","timestamp":770428800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6986,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Computer and System Sciences"],"published-print":{"date-parts":[[1994,6]]},"DOI":"10.1016\/s0022-0000(05)80062-5","type":"journal-article","created":{"date-parts":[[2005,8,20]],"date-time":"2005-08-20T11:18:35Z","timestamp":1124536715000},"page":"464-497","source":"Crossref","is-referenced-by-count":149,"title":["Efficient distribution-free learning of probabilistic concepts"],"prefix":"10.1016","volume":"48","author":[{"given":"Michael J.","family":"Kearns","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert E.","family":"Schapire","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0022-0000(05)80062-5_bib1","series-title":"Proceedings, Fourth Annual Workshop on Computational Learning Theory","first-page":"277","article-title":"Polynomial learnability of probabilistic concepts with respect to the Kullback-Liebler divergence","author":"Abe","year":"1991"},{"key":"10.1016\/S0022-0000(05)80062-5_bib2","series-title":"Proceedings, Second Annual ACM-SIAM Symposium on Discrete Algorithms","article-title":"Learning the Fourier spectrum of probabilistic lists and trees","author":"Aiello","year":"1991"},{"issue":"No. 4","key":"10.1016\/S0022-0000(05)80062-5_bib3","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF00116829","article-title":"Learning from noisy examples","volume":"2","author":"Angluin","year":"1988","journal-title":"Mach. Learning"},{"issue":"No. 2","key":"10.1016\/S0022-0000(05)80062-5_bib4","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","article-title":"Fast probabilistic algorithms for Hamiltonian circuits and matchings","volume":"18","author":"Angluin","year":"1979","journal-title":"J. Comput. System Sc."},{"issue":"No. 6","key":"10.1016\/S0022-0000(05)80062-5_bib5","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","article-title":"Occam's razor","volume":"24","author":"Blumer","year":"1987","journal-title":"Inform. Process. Lett."},{"issue":"No. 4","key":"10.1016\/S0022-0000(05)80062-5_bib6","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik-Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"J. Assoc. Comput. Math."},{"key":"10.1016\/S0022-0000(05)80062-5_bib7","series-title":"Introduction to Algorithms","author":"Cormen","year":"1990"},{"key":"10.1016\/S0022-0000(05)80062-5_bib8","series-title":"An Introduction to Generalized Linear Models","author":"Dobson","year":"1990"},{"key":"10.1016\/S0022-0000(05)80062-5_bib9","series-title":"Pattern Classification and Scene Analysis","author":"Duda","year":"1973"},{"issue":"No. 6","key":"10.1016\/S0022-0000(05)80062-5_bib10","doi-asserted-by":"crossref","first-page":"899","DOI":"10.1214\/aop\/1176995384","article-title":"Central limit theorems for empirical measures","volume":"6","author":"Dudley","year":"1978","journal-title":"Ann. Probab."},{"key":"10.1016\/S0022-0000(05)80062-5_bib11","series-title":"30th Annual Symposium on Foundations of Computer Science","first-page":"40","article-title":"Generalizing the PAC model: Sample size bounds from metric dimension-based uniform convergence results","author":"Haussler","year":"1989"},{"key":"10.1016\/S0022-0000(05)80062-5_bib12","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1016\/0890-5401(92)90010-D","article-title":"Decision theoretic generalization of the PAC model for neural net and other learning applications","volume":"100","author":"Haussler","year":"1992","journal-title":"Inform. and Comput."},{"issue":"No. 2","key":"10.1016\/S0022-0000(05)80062-5_bib13","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0890-5401(91)90042-Z","article-title":"Equivalence of models for polynomial learnability","volume":"95","author":"Haussler","year":"1991","journal-title":"Inform. and Comput."},{"issue":"No. 301","key":"10.1016\/S0022-0000(05)80062-5_bib14","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"J. Amer. Statist. Assoc."},{"key":"10.1016\/S0022-0000(05)80062-5_bib15","series-title":"Fuzzy Techniques in Pattern Recognition","author":"Kandel","year":"1982"},{"key":"10.1016\/S0022-0000(05)80062-5_bib16","series-title":"The Computational Complexity of Machine Learning","author":"Kearns","year":"1990"},{"key":"10.1016\/S0022-0000(05)80062-5_bib17","series-title":"Proceedings, Twentieth Annual ACM Symposium on Theory of Computing","first-page":"267","article-title":"Learning in the presence of malicious errors","author":"Kearns","year":"1988"},{"key":"10.1016\/S0022-0000(05)80062-5_bib18","series-title":"Proceedings, Twenty First Annual ACM Symposium on Theory of Computing","first-page":"433","article-title":"Cryptographic limitations on learning Boolean formulae and finite automata","author":"Kearns","year":"1989"},{"key":"10.1016\/S0022-0000(05)80062-5_bib19","series-title":"Proceedings, Fifth Annual Workshop on Computational Learning Theory","article-title":"Toward efficient agnostic learning","author":"Kearns","year":"1992"},{"key":"10.1016\/S0022-0000(05)80062-5_bib20","series-title":"29th Annual Symposium on Foundations of Computer Science","first-page":"120","article-title":"Results on learnability and the Vapnik-Chervonenkis dimension","author":"Linial","year":"1988"},{"key":"10.1016\/S0022-0000(05)80062-5_bib21","series-title":"Relating data compression and learnability","author":"Littlestone","year":"1987"},{"key":"10.1016\/S0022-0000(05)80062-5_bib22","series-title":"Learning via Fourier transform","author":"Mansour","year":"1990"},{"issue":"No. 4","key":"10.1016\/S0022-0000(05)80062-5_bib23","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","article-title":"Computational limitations on learning from examples","volume":"35","author":"Pitt","year":"1988","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0022-0000(05)80062-5_bib24","series-title":"Convergence of Stochastic Processes","author":"Pollard","year":"1984"},{"issue":"No. 3","key":"10.1016\/S0022-0000(05)80062-5_bib25","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF00058680","article-title":"Learning decision lists","volume":"2","author":"Rivest","year":"1987","journal-title":"Mach. Learning"},{"key":"10.1016\/S0022-0000(05)80062-5_bib26_1","article-title":"Algorithmic Learning of Formal Languages and Decision Trees","author":"Sakakibara","year":"1991"},{"key":"10.1016\/S0022-0000(05)80062-5_bib26_2","series-title":"Research Report IIAS-RR-91-22E, International Institute for Advanced Study of Social Information Science","year":"1991"},{"key":"10.1016\/S0022-0000(05)80062-5_bib27","series-title":"Proceedings, 1988 Workshop on Computational Learning Theory","first-page":"91","article-title":"Types of noise in data for concept learning","author":"Sloan","year":"1988"},{"issue":"No. 11","key":"10.1016\/S0022-0000(05)80062-5_bib28","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1984","journal-title":"Comm. ACM"},{"key":"10.1016\/S0022-0000(05)80062-5_bib29","series-title":"Estimation of Dependences Based on Empirical Data","author":"Vapnik","year":"1982"},{"issue":"No. 2","key":"10.1016\/S0022-0000(05)80062-5_bib30","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","article-title":"On the uniform convergence of relative frequencies of events to their probabilities","volume":"16","author":"Vapnik","year":"1971","journal-title":"Theory Probab. Appl."},{"issue":"No. 4","key":"10.1016\/S0022-0000(05)80062-5_bib31","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1162\/neco.1989.1.4.425","article-title":"Learning in artificial neural networks: A statistical perspective","volume":"1","author":"White","year":"1989","journal-title":"Neural Comput."},{"issue":"No. 2\u20133","key":"10.1016\/S0022-0000(05)80062-5_bib32","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/BF00992676","article-title":"A learning criterion for stochastic rules","volume":"9","author":"Yamanishi","year":"1992","journal-title":"Mach. Learning"},{"issue":"No. 3","key":"10.1016\/S0022-0000(05)80062-5_bib33","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1016\/S0019-9958(65)90241-X","article-title":"Fuzzy sets","volume":"8","author":"Zadeh","year":"1965","journal-title":"Inform. and Control"}],"container-title":["Journal of Computer and System Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800625?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0022000005800625?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,1,22]],"date-time":"2019-01-22T22:27:35Z","timestamp":1548196055000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0022000005800625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,6]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,6]]}},"alternative-id":["S0022000005800625"],"URL":"https:\/\/doi.org\/10.1016\/s0022-0000(05)80062-5","relation":{},"ISSN":["0022-0000"],"issn-type":[{"value":"0022-0000","type":"print"}],"subject":[],"published":{"date-parts":[[1994,6]]}}}