{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T16:22:54Z","timestamp":1782577374579,"version":"3.54.5"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[1990,6]]},"DOI":"10.1007\/bf00116037","type":"journal-article","created":{"date-parts":[[2004,11,1]],"date-time":"2004-11-01T01:33:03Z","timestamp":1099272783000},"page":"197-227","source":"Crossref","is-referenced-by-count":1970,"title":["The strength of weak learnability"],"prefix":"10.1007","volume":"5","author":[{"given":"Robert E.","family":"Schapire","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"Angluin, D. (1980). Finding patterns common to a set of strings.J. of Computer and System Sciences,21, 46?62.","journal-title":"J. of Computer and System Sciences"},{"key":"CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and concept learning.Machine Learning,2, 319?342.","journal-title":"Machine Learning"},{"key":"CR3","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"Angluin, D. and Valiant, L.G. (1979). Fast probabilistic algorithms for Hamiltonian circuits and matchings.J. Computer and System Sciences,18, 155?193.","journal-title":"J. Computer and System Sciences"},{"key":"CR4","unstructured":"Baum, E.B. (1989). On learning a union of half spaces. Unpublished manuscript."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1016\/0020-0190(87)90114-1","volume":"24","author":"A. Blumer","year":"1987","unstructured":"Blumer, A., Ehrenfeucht, a., Haussler, D., and Warmuth, M.K. (1987). Occam's razor.Information Processing Letters,24, 377?380.","journal-title":"Information Processing Letters"},{"key":"CR6","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension.J. of the Association for Computing Machinery,36, 929?965.","journal-title":"J. of the Association for Computing Machinery"},{"key":"CR7","volume-title":"Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing","author":"R. Board","year":"1990","unstructured":"Board, R. and Pitt, L. (1990). On the necessity of Occam algorithms. (In press)Proceedings of the Twenty-second Annual ACM Symposium on Theory of Computing. New York, NY: ACM Press."},{"key":"CR8","first-page":"125","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"S. Boucheron","year":"1988","unstructured":"Boucheron, S. and Sallantin, J. (1988). Some remarks about space-complexity of learning, and circuit complexity of recognizing.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 125?138). San Mateo, CA: Morgan Kaufman."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/0890-5401(89)90001-1","volume":"3","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A. and Haussler, D. (1989). Learning decision trees from random examples.Information and Computation,3, 231?246.","journal-title":"Information and Computation"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/B978-0-08-094829-4.50028-3","volume-title":"Proceedings of the Second Annual Workshop on Computational Learning Theory","author":"S. Floyd","year":"1989","unstructured":"Floyd, S. (1989). Space-bounded learning and the Vapnik-Chervonenkis dimension.Proceedings of the Second Annual Workshop on Computational Learning Theory (pp. 349?364). San Mateo, CA: Morgan Kaufman."},{"key":"CR11","series-title":"Technical Report UCSC-CRL-88-2","volume-title":"Space efficient learning algorithms","author":"D. Haussler","year":"1988","unstructured":"Haussler, D. (1988).Space efficient learning algorithms (Technical Report UCSC-CRL-88?2). Santa Cruz, CA: University of California, Baskin Center for Computer Engineering and Information Sciences."},{"key":"CR12","first-page":"42","volume-title":"Proceedings of the 1988 Workshop on Computational Learning Theory","author":"D. Haussler","year":"1988","unstructured":"Haussler, D., Kearns, M., Littlestone, N., and Warmuth, M.K. (1988). Equivalence of models for polynomial learnability.Proceedings of the 1988 Workshop on Computational Learning Theory (pp. 42?55). San Mateo, CA: Morgan Kaufman."},{"key":"CR13","unstructured":"Haussler, D., Littlestone, N., and Warmuth, M.K. (1987). Expected mistake bounds for on-line learning algorithms. Unpublished manuscript."},{"key":"CR14","first-page":"100","volume-title":"Proceedings of the Twenty-Ninth Annual Symposium on Foundations of Computer Science","author":"D. Haussler","year":"1988","unstructured":"Haussler, D., Littlestone, N., and Warmuth, M.K. (1988). Predicting {0, 1}-functions on randomly drawn points.Proceedings of the Twenty-Ninth Annual Symposium on Foundations of Computer Science (pp. 100?109). Washington, DC: IEEE Computer Society Press."},{"key":"CR15","first-page":"xxx","volume":"5","author":"D. Helmbold","year":"1990","unstructured":"Helmbold, D., Sloan, R., and Warmuth, M.K. (1990). Learning nested differences of intersection-closed concept classes.Machine Learning, 5, xxx-xxx.","journal-title":"Machine Learning"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables.J. of the American Statistical Association,58, 13?30.","journal-title":"J. of the American Statistical Association"},{"key":"CR17","unstructured":"Kearns, M. (1988). Thoughts on hypothesis boosting. Unpublished manuscript."},{"key":"CR18","unstructured":"Kearns, M. (1989).The Computational Complexity of Machine Learning. Doctoral dissertation, Department of Computer Science, Harvard University, Cambridge, MA."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/28395.28426","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing","author":"M. Kearns","year":"1987","unstructured":"Kearns, M., Li, M., Pitt, L., and Valiant, L. (1987). On the learnability of Boolean formulae.Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (pp. 285?295). New York, NY: ACM Press."},{"key":"CR20","series-title":"Technical Report TR-14-88","volume-title":"Learning Boolean formulae or finite automata is as hard as factoring","author":"M. Kearns","year":"1988","unstructured":"Kearns, M. and Valiant, L.G. (1988).Learning Boolean formulae or finite automata is as hard as factoring (Technical Report TR-14?88). Cambridge, MA: Harvard University Aiken Computation Laboratory."},{"key":"CR21","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1145\/73007.73049","volume-title":"Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing","author":"M. Kearns","year":"1989","unstructured":"Kearns, M. and Valiant, L.G. (1989). Cryptographic limitations on learning Boolean formulae and finite automata.Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (pp. 433?444). New York, NY: ACM Press."},{"key":"CR22","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L. and Valiant, L.G. (1988). Computational limitations on learning from examples.J. of the Association for Computing Machinery,35, 965?984.","journal-title":"J. of the Association for Computing Machinery"},{"key":"CR23","first-page":"229","volume":"2","author":"R.L. Rivest","year":"1987","unstructured":"Rivest, R.L. (1987). Learning decision lists.Machine Learning,2, 229?246.","journal-title":"Machine Learning"},{"key":"CR24","unstructured":"Schapire, R.E. (1989). Pattern languages are not learnable. Unpublished manuscript."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G. (1984). A theory of the learnable.Communications of the ACM,27, 1134?1142.","journal-title":"Communications of the ACM"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/BF00116037.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/article\/10.1007\/BF00116037\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/content\/pdf\/10.1007\/BF00116037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T21:00:43Z","timestamp":1682802043000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/link.springer.com\/10.1007\/BF00116037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["BF00116037"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1007\/bf00116037","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}