{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,14]],"date-time":"2026-10-14T11:11:26Z","timestamp":1791976286548,"version":"4.4.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf00993593","type":"journal-article","created":{"date-parts":[[2005,1,14]],"date-time":"2005-01-14T18:04:23Z","timestamp":1105725863000},"page":"269-304","source":"Crossref","is-referenced-by-count":87,"title":["Sample compression, learnability, and the Vapnik-Chervonenkis dimension"],"prefix":"10.1007","volume":"21","author":[{"given":"Sally","family":"Floyd","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred","family":"Warmuth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"4","key":"CR1","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D. (1988). Queries and concept learning.Machine Learning Vol. 2 No. 4, 319?342, Apr. 1988.","journal-title":"Machine Learning"},{"key":"CR2","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., & Warmuth, M. (1987). Occam's razor.Information Processing Letters Vol. 24, 377?380.","journal-title":"Information Processing Letters"},{"issue":"4","key":"CR3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., A. Ehrenfeucht, D. Haussler, & M. Warmuth. (1989). Learnability and the Vapnik-Chervonenkis dimension.Journal of the Association for Computing Machinery Vol. 36, No. 4, 929?965.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR4","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0166-218X(92)90271-B","volume":"24","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., & Littlestone, N. (1989). Learning faster than promised by the Vapnik-Chervonenkis dimension.Discrete Applied Mathematics 24, p.47?53.","journal-title":"Discrete Applied Mathematics"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Freund, Y., Helmbold, D. P., Haussler, D., Schapire, R. E., & Warmuth, M. K. (1993). How to use expert advice.Proceedings of the 25th ACM Symposium on the Theory of Computation, 382?391.","DOI":"10.1145\/167088.167198"},{"key":"CR6","doi-asserted-by":"crossref","unstructured":"Clarkson, K. L. (1992). Randomized geometric algorithms. In F. K. Hwang and D. Z. Hu (Eds.),Euclidean Geometry and Computers. World Scientific Publishing.","DOI":"10.1142\/9789814355858_0004"},{"key":"CR7","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M., & Valiant, L. (1987). A general lower bound on the number of examples needed for learning.Proceedings of the 1988 Workshop on Computational Learning Theory, Morgan Kaufmann, 139?154."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Floyd, S. (1989).On space-bounded learning and the Vapnik-Chervonenkis dimension. PhD thesis, International Computer Science Institute Technical Report TR-89-061, Berkeley, California.","DOI":"10.1016\/B978-0-08-094829-4.50028-3"},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Freund, Y. (1995). Boosting a weak learning algorithm by majority. To appear inInformation and Computation.","DOI":"10.1006\/inco.1995.1136"},{"issue":"3","key":"CR10","first-page":"271","volume":"14","author":"S. Goldman","year":"1994","unstructured":"Goldman, S., & Sloan, R. (1994). The power of self-directed learning.Machine Learning Vol. 14 No. 3, 271?294.","journal-title":"Machine Learning"},{"key":"CR11","unstructured":"Haussler, D. (1988).Space efficient learning algorithms. Technical Report UCSC-CRL-88-2, University of California Santa Cruz."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E. (1987). Epsilon-nets & simplex range queries.Discrete and Computational Geometry 2 127?151.","journal-title":"Discrete and Computational Geometry"},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Helmbold, D. P., & Warmuth, M. K. (1995). On weak learning.Journal of Computer and System Sciences, to appear.","DOI":"10.1006\/jcss.1995.1044"},{"key":"CR14","first-page":"165","volume":"5","author":"D. Helmbold","year":"1990","unstructured":"Helmbold, D., Sloan, R., & Warmuth, M. (1990). Learning nested differences of intersection-closed concept classes.Machine Learning 5, 165?196, 1990.","journal-title":"Machine Learning"},{"issue":"2","key":"CR15","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1137\/0221019","volume":"21","author":"D. Helmbold","year":"1992","unstructured":"Helmbold, D., Sloan, R., & Warmuth, M. (1992). Learning integer lattices.Siam Journal on Computing Vol. 21 No. 2, 240?266.","journal-title":"Siam Journal on Computing"},{"key":"CR16","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N. (1988). Learning when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning 2 285?318.","journal-title":"Machine Learning"},{"key":"CR17","unstructured":"Littlestone, N. (1989).Mistake bounds and logarithmic linear-threshold learning algorithms. PhD thesis, Technical Report UCSC-CRL-89-11, University of California Santa Cruz."},{"issue":"2","key":"CR18","first-page":"148","volume":"115","author":"N. Littlestone","year":"1994","unstructured":"Littlestone, N., Haussler, D., & Warmuth, M. (1994). Predicting {0, 1}-functions on randomly drawn points.Information and Computation Vol. 115 No. 2, 148?292.","journal-title":"Information and Computation"},{"key":"CR19","unstructured":"Littlestone, N, & Warmuth, M. (1986).Relating data compression and learnability. Unpublished manuscript, University of California Santa Cruz."},{"key":"CR20","unstructured":"Mitchell, T. (1977). Version spaces: a candidate elimination approach to rule learning.Proceedings of the International Joint Committee for Artificial Intelligence 1977. Cambridge, Mass., 305?310."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Pach, J., & Woeginger, G. (1990). Some new bounds for epsilon-nets.Proceedings of the Sixth Annual Symposium on Computational Geometry, Berkeley, California, 10?15.","DOI":"10.1145\/98524.98529"},{"issue":"4","key":"CR22","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., & Valiant, L. (1988). Computational limitations on learning from examples.Journal of the Association for Computing Machinery Vol. 35 No. 4, 965?984.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"CR23","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0890-5401(89)90010-2","volume":"80","author":"J. Quinlan","year":"1989","unstructured":"Quinlan, J., & Rivest, R. (1989). Inferring decision trees using the minimum description length principle.Information and Computation Vol. 80, 227?248.","journal-title":"Information and Computation"},{"issue":"3","key":"CR24","doi-asserted-by":"crossref","first-page":"1080","DOI":"10.1214\/aos\/1176350051","volume":"14","author":"J. Rissanen","year":"1986","unstructured":"Rissanen, J. (1986). Stochastic complexity and modeling.Annals of Statistics Vol. 14 No. 3, 1080?1100.","journal-title":"Annals of Statistics"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"Sauer, N. (1972). On the density of families of sets.Journal of Combinatorial Theory (A) 13, 145?147.","journal-title":"Journal of Combinatorial Theory (A)"},{"issue":"2","key":"CR26","first-page":"197","volume":"5","author":"R. Schapire","year":"1990","unstructured":"Schapire, R. (1990). The strength of weak learnability.Machine Learning Vol. 5 No. 2, 197?227.","journal-title":"Machine Learning"},{"key":"CR27","unstructured":"Shawe-Taylor, J., Anthony, M., & Biggs, N. (1989).Bounding sample size with the Vapnik-Chervonenkis dimension. Technical Report CSD-TR-618, University of London, Royal Halloway and New Bedford College."},{"issue":"11","key":"CR28","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 Association for Computing Machinery Vol. 27, No. 11, 1134?42.","journal-title":"Communications of the Association for Computing Machinery"},{"key":"CR29","volume-title":"Estimation of dependencies based on empirical data","author":"V.N. Vapnik","year":"1982","unstructured":"Vapnik, V.N. (1982).Estimation of dependencies based on empirical data. Springer Verlag, New York."},{"issue":"2","key":"CR30","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V.N. Vapnik","year":"1971","unstructured":"Vapnik, V.N. & Chervonenkis, A.Ya. (1971). On the uniform convergence of relative frequencies of events to their probabilities.Theory of Probability and its Applications Vol. 16, No. 2, 264?280.","journal-title":"Theory of Probability and its Applications"},{"key":"CR31","unstructured":"Welzl, E. (1987).Complete range spaces. Unpublished notes."},{"key":"CR32","unstructured":"Welzl, E., & Woeginger, G. (1987).On Vapnik-Chervonenkis dimension one. Unpublished manuscript, Institutes for Information Processing, Technical University of Graz and Austrian Computer Society, Austria."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993593.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00993593\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00993593","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,29]],"date-time":"2019-04-29T22:58:47Z","timestamp":1556578727000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00993593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF00993593"],"URL":"https:\/\/doi.org\/10.1007\/bf00993593","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}