The History of AI

Vapnik-Chervonenkis theory

Era 2 · AI is born (1943–1979) › Neural networks and learning

Lineage
Data and learning
Kind
Publication

Who

Institute of Control Sciences

What happened

In Moscow, Vladimir Vapnik and Alexey Chervonenkis announce in 1968, and publish in 1971, the conditions under which a classifier's rate of correct answers on its training data approaches the rate it will have on new data.

Why it mattered

They found statistical learning theory: they measure the capacity of a family of classifiers with what is now called the VC dimension and use it to bound the error on new data. It is the theoretical basis of support vector machines.

The full story

A program that learns to classify sees a limited number of examples. Getting those right does not guarantee getting the next ones right: a flexible enough family of classifiers can fit any data set, noise included. The question is when the error measured on the examples is a good estimate of the true error.

Vapnik and Chervonenkis answered with a result on uniform convergence. It is not enough for the observed frequency to approach the probability for one particular classifier: it has to do so simultaneously for every classifier in the family that learning chooses from. That happens when the family has limited capacity, which they measured by counting how many sets of points it can split in every possible way. That measure is the VC dimension.

The results were announced in 1968 in a note in Doklady, the journal of the Soviet Academy of Sciences, based on drafts from 1966, and the full paper came out in Russian in 1971, with an English translation the same year.

The work became known in the West only later. Vapnik developed it for two decades in the Soviet Union and then, at AT&T's laboratories, turned it with Corinna Cortes into the support vector machines of 1995, which dominated machine learning until neural networks returned.

Under the hood

The VC dimension of a family of classifiers is the largest number of points the family can split in every possible way.

Lines in the plane have dimension 3. Three points that are not in a line can be divided into two classes in eight ways, and a line achieves each one. With four points that no longer works: if they sit at the corners of a square and the diagonals belong to opposite classes, which is exclusive OR, no line separates them.

If the dimension is finite, the error measured on n examples approaches the true error simultaneously for every classifier in the family, and the gap is bounded by an expression that grows with the dimension and shrinks with n. That is why a more flexible family needs more examples before getting the training data right means anything.

Leads to

  • Support vector machines (September 1995)

    Documented direct influence

    Support vector machines rest on Vapnik and Chervonenkis's statistical learning theory

Sources

How to cite

“Vapnik-Chervonenkis theory.” The History of AI, revised November 13, 2026. https://thehistoryofai.com/en/milestone/vapnik-chervonenkis-theory

This entry was last reviewed on November 13, 2026.

Open in the interactive timeline