CoChat
Sign Up
Cited by 1,839Machine Learning and AlgorithmsComputability, Logic, AI AlgorithmsNeural Networks and Applications

Learnability and the Vapnik-Chervonenkis dimension

Open access
Blumer, Anselm, Ehrenfeucht, A., Haussler, David, Warmuth, Manfred K.·1989·Journal of the ACM
DOI 10.1145/76359.76371
Open this paper in CoChat — free accountOpen PDF

Abstract

Valiant's learnability model is extended to learning classes of concepts defined by regions in Euclidean space E n . The methods in this paper lead to a unified treatment of some of Valiant's results, along with previous results on distribution-free convergence of certain pattern recognition algorithms. It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Using this parameter, the complexity and closure properties of learnable classes are analyzed, and the necessary and sufficient conditions are provided for feasible learnability.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/76359.76371

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Blumer-bound arguments indicate that search constrained in this way achieves not only speed improvements but also reduction in out-of-sample error.

    “Blumer-bound arguments are provided which indicate that search constrained in this way achieves not only speed improvements but also reduction in out-ofsample error.”

    From Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited (2015) · cites this paper as Blumer et al., 1989

    The Introduction and Section 2 give VC-dimension bounds on the out-of-sample error of consistent hypotheses, supporting the use of a Blumer bound in a generalization argument. Our copy does not show that the particular search constraint described by the citing paper improves speed or reduces out-of-sample error; those appear to be conclusions of the citing authors' arguments. (LLM, conf=0.84)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

No citation lists for this paper

No citation lists for this paper yet — checked again daily.

References 78 · Cited by 1,839

Research works printed but not linked: 59

  1. AHO, A., HOPCROF-~, J., AND ULLMAN, J. The Design and Analysis of Computer Algorithms. Addison-Wesley, London, 1914.
  2. ANGLUIN, D. Learning regular sets from queries and counterexamples. Inf Compul. 75 (1987), 87-106.
  3. ANGLUIN, D. Queries and concept learning. Mach. Learning 2,2 ( 1988), 3 19-342.
  4. ANGLUIN, D., AND LAIRD, P. D. Learning from noisy examples. Mach. Learning 2, 2 (1988), 343-370.
  5. ANGLUIN, D., AND VALIANT, L. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci. 19 (1979), 155-193.
  6. ASSOUAD, P. DensitC et Dimension. Ann. Inst. Fourier, Grenoble 33, 3 (1983), 233-282.
  7. BEN-DAVID, S., BENEDEK, G., AND MANSOUR, Y. A parameterization scheme for classifying models of learnability. In Proceedings of the 2nd Workshop of Computational Learning Theory (Santa Cruz, Calif., July 3 I-Aug.
  8. BENEDEK, G., AND ITAI, A. Nonuniform learnability. In Proceedings of the 15th International Confirence on Automata, Languages and Programming (July). 1988, pp. 82-92.
  9. BLUM, A., AND RIVEST, R. Training a 3-node neural network is NP-complete. In Proceedings of the 1st Workshop on Computational Learning Theory (Cambridge, Mass., Aug. 3-5).
  10. Morgan Kaufmann, San Mateo, Calif., 1988, pp.9-18.
  11. BLUMER, A., EHRENFEUCHT, A., HAUSSLER, D., AND WARMUTH, M. K. Occam's Razor. Inf Process. Lett. 24 (1987), 377-380.
  12. I I. BOLLOB& B. Combinatorics. Cambridge Univ. Press, Cambridge, Mass., 1986.
  13. BOUCHERON, S., AND SALLANTIN, J. Some remarks about space-complexity of learning and circuit complexity of recognizing. In Proceedings of the 1st Workshop on Computational Learning Theory (Cambridge, Mass., Aug. 3-5).
  14. Morgan Kaufmann, San Mateo, Calif., 1988, pp. l25-138.
  15. COVER, T. Geometrical and statistical properties of systems of linear inequalities with applications to pattern recognition. IEEE Trans. Elect. Comp. 14 (1965), 326-334.
  16. DEVROYE, L. P. Automatic pattern recognition: A study of the probability of error. IEEE Trans. Pattern Analysis and Mach. Intell. 10, 4 (1988), 530-543.
  17. DEVROYE, L. P., AND WAGNER, T. J. A distribution-free performance bound in error estimation. IEEE Trans. Inx Theorem 22 (1976), 586-587.
  18. DUDA, R., AND HART, P. Pattern Classification and Scene Analysis. Wiley, New York, 1973.
  19. DUDLEY, R. M. A course on empirical processes. In Lecture Notes in Mathematics, vol. 1097. Springer-Verlag, New York, 1984.
  20. DUDLEY, R. M. Universal Donsker classes and metric entropy. Ann. Prob. 15, 4 (1987), 1306-1326.
  21. EDELSBRUNNER, H., AND PREPARATA, F. P. Minimal polygonal separation. Inj Comput. 77 (1988), 218-232.
  22. GILL, J. Probabilistic Turing machines. SIAM J. Comput. 6, 4 (1977), 675-695.
  23. GINS, E., AND ZINN, J. Lectures on the central limit theorem for empirical processes. In Lecture Notes in Mathematics, vol. 122 1. Springer-Verlag, New York, 1986.
  24. GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. How to construct random functions. J. ACM 33,4 (Oct. 1986), 792-807.
  25. HAMPSON, S. E., AND VOLPER, D. Linear Function neurons: Structure and training. Biol. Cyber. 53 ( 1986), 203-2 17.
  26. HAUSSLER, D. Applying Valiant's learning framework to AI concept learning problems. In Proceedings of the 4th International Workshop on Machine Learning. Morgan Kaufmann, San Mateo, Calif., 1987, pp. 324-336.
  27. HAUSSLER, D. Quantifying inductive bias: AI learning algorithms and Valiant's learning framework. Art/y Intell. 36 (1988), 177-22 1. 28a. HAUSSLER, D. Generalizing the PAC model: Sample size bounds from metric dimension-based uniform convergence results. In Proceedings of the 30th IEEE Symposium on Foundations of Computer Science (Research Triangle Park, N.C., Oct. 30-Nov. 1). IEEE, New York:, 1989, to appear.
  28. HAUSSLER, D., AND WELZL, E. Epsilon-nets and simplex range queries. Disc. Comput. Geometry 2(1987), 127-151.
  29. I. HAUSSLER, D., LITTLESTONE, N., AND WARMUTH, M. K. Predicting (0, 1)-functions on randomly drawn points. In Proceedings of the 29th IEEE Symposium on Foundations of Computer Science (White Plains, N.Y., Oct.). IEEE, New York, 1988, pp. 100-109.
  30. JOHNSON, D. S. Approximation algorithms for combinatorial problems. .I. Cornput. Syst. Sci. 9 (1974), 256-278.
  31. KARMARKAR, N. A new polynomial-time algorithm for linear programming. Combr'natoricu 4 (1984), 373-395.
  32. KEARNS, M., AND LI, M. Learning in the presence of malicious errors. In Proceedings of the 20th Symposium on Theory of Computing (Chicago, Ill., May 2-4). ACM, New York, 1988, pp. 267-280.
  33. KEARNS, M., AND VALIANT, L. Cryptographic limitations on learning Boolean formulae and finite automata. In Proceedings of the 21st ACM Symposium on Theory qf Computing (Seattle, Wash., May 15-17). ACM, New York, 1989, pp. 433-444.
  34. KEARNS, M., LI, M., PITT, L., AND VALIANT, L. On the learnability of Boolean formulae. In Proceedings of the 19th ACM Symposium on Theory of Computation (New York, N.Y., May 25-27). ACM, New York, 1987, pp. 285-295.
  35. KEARNS, M., LI, M., PITT, L., AND VALIANT, L. Recent results on Boolean concept learning. In Proceedings of the 4th International Workshop on Machine Learning. Morgan-Kaufmann, San Mateo, Calif., 1987, pp. 337-352.
  36. KNUTH, D. E. The Art of Computer Programming, 2nd ed., vol. 1. Addison-Wesley, Reading, Mass., 1973.
  37. LEE, D. T., AND PREPARATA, F. P. Computational geometry-A survey. IEEE Trun.;. Comput. 33, 12 (1984), 1072-l 101.
  38. LINIAL, N., MANSOUR, Y., AND RIVEST, R. Results on learnability and the Vapnik-Chcrvonenkis dimension. In Proceedings of the 29th IEEE Symposium on Foundations of Compuier Science (White Plains, N.Y., Oct.). IEEE, New York, 1988, pp. 120-129.
  39. LITTLESTONE, N. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learning 2, 2 (1988), 285-3 18.
  40. MEGIDDO, N. Linear programming in linear time when the dimension is fixed. J. ACM 31, 1 (Jan. 1984), 114-127.
  41. MUROGA, S. Threshold Logic and Its Applications. Wiley, New York, I97 I.
  42. NATARAJAN, B. K. On learning Boolean functions. In Proceedings of the 19th Annual ACM Symposium on Theory of Computation (New York, N.Y., May 25-27). ACM, New York, 1987, pp. 296-304.
  43. NIGMATULLIN, R. G. The fastest descent method for covering problems (in Russian). In Proceedings qf a Symposium on Questions of Precision and Efficiency of Computer Algorithms, Book 5. Kiev, 1969, pp. 116-126.
  44. PEARL, J. On the connection between the complexity and credibility of inferred models. Int. J. Gen. Syst. 4 (1978), 255-264.
  45. I. PEARL, J. Capacity and error estimates for Boolean classifiers with limited capacity. IEEE Trans. Pattern Analysis Mach. Intell. I, 4 (1979), 350-355.
  46. PITT, L., AND VALIANT, L. G. Computational limitations on learning from examples. J. ACM 35, 4 (Oct. 1988), 965-984.
  47. PITT, L., AND WARMUTH, M. Reductions among prediction problems, on the difficulty of predicting automata. In Proceedings of the 3rd IEEE Structure in Complexity Theory Conference (Washington, D.C.). IEEE, New York, 1988, pp. 62-69.
  48. POLLARD, D. Convergence ofStochastic Processes. Springer-Verlag, New York, 1984.
  49. RIVEST, R. Learning decision-lists. Mach. Learning 2, 3 (1987), 229-246.
  50. SLOAN, R. Types of noise in data for concept learning. In Proceedings of'the 1st Workshop on Computational Learning Theory (Cambridge, Mass., Aug. 3-5).
  51. Morgan Kaufmann, San Mateo, Calif., 1988, pp. 91-96.
  52. VALIANT, L. G. Learning disjunctions of conjunctions. In Proceedings of the 9th International Confirence on ArtiJicial Intelligence (Los Angeles, Calif., Aug.), vol.
  53. Morgan Kaufmann, San Mateo, Calif., 1985, pp. 560-566.
  54. I. VAPNIK, V. N. Estimation oj'Dependences Based on Empirical Data. Springer Verlag, New York, 1982.
  55. VITTER, J., AND LIN, J. H. Learning in parallel. In Proceedings of the 1st Workshop on Computational Leurning Theory (Cambridge, Mass., Aug. 3-5).
  56. Morgan Kaufmann, San Mateo, Calif., 1988, pp. 106-124.
  57. WATANABE, S. Pattern recognition as information compression. In Frontiers of Pattern Recognition, S. Watanabe, Ed. Academic Press, Orlando, Fla., 1972.
  58. WENOCUR, R. S., AND DUDLEY, R. M. Some special Vapnik-Chervonenkis classes. DiscreteMath. 33 (1981), 313-318.
  59. WINSTON, P. Learning structural descriptions from examples. In The Psychology of Computer Vision. McGraw-Hill, New York, 1975.

Authors
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K.
Affiliations
  • Tufts University (US)
  • University of Colorado Boulder (US)
  • University of California, Santa Cruz (US)
ORCID
Venue
Journal of the ACM
Publisher
Association for Computing Machinery (ACM)
Published
1989-10
Volume
36
Issue
4
Pages
929-965
ISSN
  • 0004-5411 (ISSN-L)
  • 1557-735X
DOI
10.1145/76359.76371
OpenAlex
W2154952480
Cited by
1,839
References
78
Citations by year
2026: 14 · 2025: 41 · 2024: 18 · 2023: 35 · 2022: 59 · 2021: 77 · 2020: 78 · 2019: 47 · 2018: 43 · 2017: 41 · 2016: 43 · 2015: 53 · 2014: 28 · 2013: 52 · 2012: 36
FWCI
63.89
Type
journal article
Language
en
Open access
Licence
www.acm.org/publications/policies/copyright_policy#Background (vor)
Locations
Journal of the ACM (publishedVersion)
Funders
  • National Science Foundation (8305245, 8317918)
  • Office of Naval Research (N00014-86-K-0454, N00014)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
Keywords
learnability, VC dimension, pattern recognition algorithms, closure properties

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review