Skip to content
Last Dictionary
Plane
Mathematics & StatisticsMachine Learning

VC dimension

nounAlso: Vapnik–Chervonenkis dimension, VC theory, shattering, growth function

In plain wordsA measure of how flexible a family of prediction rules is: the largest number of points it can label in every possible way. More flexible families need more data to learn reliably.

  1. A measure of the capacity of a class of binary classifiers: the size of the largest set of points the class can shatter, that is, label in all 2ⁿ possible ways. Linear classifiers in d dimensions have VC dimension d + 1; a class that can shatter arbitrarily large sets has infinite VC dimension. VC theory shows that a class is learnable in the PACPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right. sense exactly when its VC dimension is finite, and bounds the gap between training and test error by a term that grows with the VC dimension and shrinks with sample size, formalizing the trade-off behind overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding. and structural risk minimization. Margin-based capacity control in this tradition motivated support vector machinessupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.. For modern deep networks, whose VC dimension grows with parameter count and dwarfs dataset sizes, such bounds are vacuous and cannot explain why overparameterizedoverparameterization, n.: Giving a model far more adjustable settings than it would seem to need — often more than it has training examples. Classic theory predicted this would backfire; in deep learning it usually helps. networks generalize — a starting point for research on double descentdouble descent, n.: A surprising pattern where a model's error on new data first falls, then rises, then falls again as the model grows bigger — contradicting the old rule that oversized models always do worse. and implicit regularizationimplicit regularization, n.: The hidden preferences of a training method itself: even with no explicit rule against complexity, the way a model is trained tends to steer it toward simpler solutions..

    The network has more parameters than training images, so its VC bound is vacuous, yet it generalizes fine.

errtest≤errtrain+O ⁣(dVClog⁡(n/dVC)+log⁡(1/δ)n)\mathrm{err}_{\text{test}} \le \mathrm{err}_{\text{train}} + O\!\left(\sqrt{\frac{d_{\mathrm{VC}}\log(n/d_{\mathrm{VC}}) + \log(1/\delta)}{n}}\right)

Origin

Defined by Vladimir Vapnik and Alexey Chervonenkis in a 1968 note in Doklady Akademii Nauk SSSR and a fuller 1971 paper on the uniform convergence of relative frequencies to their probabilities (English translation the same year). Anselm Blumer, Andrzej Ehrenfeucht, David Haussler and Manfred Warmuth connected it to PAC learning (conference version 1986; 'Learnability and the Vapnik–Chervonenkis Dimension', 1989) and helped fix the name.

Related

See also
  • PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right.
  • statistical learning theorystatistical learning theory, n.: The mathematics of when and why learning from examples works: how much data is needed, and how well a model trained on some examples will do on new ones.
  • empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data.
  • overfittingoverfitting, n.: When a model learns its training examples too well — quirks and noise included — so it does great on data it has seen but poorly on anything new, like a student who memorizes answers without understanding.
  • support vector machinesupport vector machine, n.: A classic method that separates two groups of examples with the widest possible gap — like laying the broadest possible road between them. A mathematical shortcut lets it draw curved boundaries too.
  • double descentdouble descent, n.: A surprising pattern where a model's error on new data first falls, then rises, then falls again as the model grows bigger — contradicting the old rule that oversized models always do worse.

Sources

  1. 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, 16(2).
  2. Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M. K. (1989). Learnability and the Vapnik–Chervonenkis Dimension. Journal of the ACM, 36(4).

Mentioned in

empirical risk minimizationempirical risk minimization, n.: The basic recipe of most machine learning: from the models on offer, pick the one with the smallest errors on the training examples, trusting that score as a guide to how it will do on new data., generalizationgeneralization, n.: How well a model copes with new examples it has never seen, rather than just memorizing its training data, like a student who understands the method, not just the answers., generalization gapgeneralization gap, n.: The difference between how well a model does on the examples it trained on and how well it does on new ones. A big gap means it memorized rather than learned., learninglearning, n.: Getting better at something through experience. For a machine, it means changing its internal settings based on data so that it performs a task better than before., model capacitymodel capacity, n.: How much a model is able to learn: the variety and complexity of patterns it can represent or memorize. Too little and it misses real patterns; very large models can even memorize pure noise., Vladimir VapnikVladimir Vapnik, prop. n.: A Soviet-born American mathematician who built the statistical theory of how machines learn from examples and co-invented support vector machines, a leading method before deep learning., hypothesis spacehypothesis space, n.: The full menu of possible models a learning method is allowed to choose from — for example, all straight lines. Learning means picking the item on the menu that best fits the data., Leslie ValiantLeslie Valiant, prop. n.: A British computer scientist who in 1984 gave the first rigorous definition of what it means for a computer to learn from examples, founding the theory of machine learning., PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right., statistical learning theorystatistical learning theory, n.: The mathematics of when and why learning from examples works: how much data is needed, and how well a model trained on some examples will do on new ones.