VC理论是统计学习理论的一个重要分支，统计学习理论的主要应用之一是为学习算法提供泛化条件。从这个角度来看，VC理论与稳定性有关，这是表征泛化的另一种方法。
根据Vapnik在他的著作提出的学习理论必须要回答的四个问题，VC理论至少包括四个部分：
- 学习过程一致性（consistency）理论：基于经验风险最小化原则，学习过程一致性的（必要且充分的）条件是什么？
- 学习过程收敛速度的非渐近（Nonasymptotic）理论：学习过程的收敛速度有多快？
- 控制学习过程泛化能力（generalization）的理论：如何控制学习过程的收敛速度（泛化能力）？
- 构建学习机器的理论：如何构造可以控制泛化能力的算法？
在VC理论中，最常用的概念为VC维（VC dimension）。VC维度（或Vapnik-Chervonenkis维度）是衡量可以通过统计分类算法学习的函数空间的容量（复杂度，表现力，丰富度或灵活性）的度量。它被定义为算法可以破碎（shatter）的最大点集的基数，在这里破碎（shatter）意为若对于一个假设空间H，如果存在m个数据样本能够被假设空间H中的函数按所有可能的2^h种形式分开，则称假设空间H能够把m个数据样本破碎（shatter），由于目前在中文教材中没有对shatter的通用翻译，下文以shatter代替。
举例来说，假设我们的模型是一个线性分类器，则对于一个只含有三个点的数据集来说，正例和反例的标注可能有2^3=8种可能，如下图所举例：
[图片来源：https://en.wikipedia.org/wiki/VC_dimension]
可以看到数据集只包含三个点时永远是线性可分的，即假设空间H能够shatter数据集，但当数据集包含四个点时则存在线性不可分的情况（xor），如上图右下角所示。
因此，可以得出线性分类器的VC维为3。
[描述来源：Vapnik V. N. (2000). The Nature of Statistical LearningTheory. Information Science and Statistics. Springer-Verlag.]
[描述来源：维基百科 URL: https://en.wikipedia.org/wiki/Vapnik%E2%80%93Chervonenkis_theory]
[描述来源：维基百科 URL: https://en.wikipedia.org/wiki/VC_dimension]
发展历史
描述
1971年，Vapnik和Chervonenkis在发表的论文中提出VC维的概念，但是针对二分类模型而言的，1984年Pollard提出了对非二元函数中的实数函数的情形的一般化方法（Pollard's pseudo-dimension）。1989年Natarajan将VC维的应用范围扩展到了多元分类函数（Natarajan dimension），随后在1992年Ben等学者在发表的论文中研究了多元分类函数的PAC可学习性并且将Natarajan的研究结果再泛化。
VC理论的一个重要应用是VC维可以用来预测预测分类模型的在测试数据上的误差的概率上限，从而可以由理论分析判断模型的泛化能力，Vapnik证明了这个不等式的成立。早于1994年Vapnik等学者就用VC维衡量了一些线性模型的学习能力。1997年Karpinskia和Macintyreb引入了一种新的证明一般泛函网络VC维上界的方法，并首次证明了使用sigmoid激活函数的神经网络的VC维。
此外，VC维还是计算几何（computational geometry）中的ε网（ε-nets）的大小的关键参数之一，从而决定了基于它们的近似算法的复杂度。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1971 | Vapnik和Chervonenkis在发表的论文中提出VC维的概念 | Vapnik, V. N.; Chervonenkis, A. Ya. (1971). On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities. Theory of Probability & Its Applications. 16 (2): 264 |
| 1984 | Pollard提出了针对非二元函数的情形的一般化方法 | Pollard, D. (1984). Convergence of Stochastic Processes. Springer. |
| 1989 | Natarajan提出了Natarajan dimension | Natarajan, B.K. (1989).On Learning sets and functions. Machine Learning. 4: 67–97. |
| 1992 | Ben等学者在发表的论文中研究了多元分类函数的PAC可学习性并且将Natarajan的研究结果再泛化 | Ben-David, S.; Cesa-Bianchi, N.; Long, Philip M. (1992). Characterizations of learnability for classes of {O, …, n}-valued functions.Proceedings of the fifth annual workshop on Computational learning theory - COLT '92. p. 333. |
| 1994 | Vapnik等学者使用VC维衡量了一些线性模型的学习能力 | Vapnik V.; Levin E.; Le Cun Y. (1994). Measuring the VC-Dimension of a Learning Machine. Neural Computation. 6(5): 851-876. |
| 1997 | Karpinskia和Macintyreb首次证明了使用sigmoid激活函数的神经网络的VC维 | Karpinskia M.; Macintyreb A. (1997).Polynomial Bounds for VC Dimension of Sigmoidal and General Pfaffian Neural Networks.Journal of Computer and System Sciences. 54(1):169-176. |
发展分析
瓶颈
根据VC理论推导得出的神经网络的VC维往往很大，即神经网络对数据要求量非常大，很容易过拟合，因而对神经网络的泛化能力持不乐观态度并且缺乏实际指导意义。但在实际表现中深度学习的表现又往往很优秀，因此，在深度学习成为主流的背景下有关深度学习是否应该抛弃VC维的指导的争论一直存在。
未来发展方向
VC理论为基于统计理论的机器学习模型的泛化能力提供了坚实的理论基础，而这正是深度学习所缺乏的理论支持，一直以来都有研究是将VC理论应用在神经网络上进行模型泛化能力分析的。
Contributor: Yuanyuan Li