从[1]我们知道，对于 iid 样本，我们在测试和训练误差之间有以下界限：

$$\mathbb{P}\left(R \leqslant R_{emp} + \sqrt{\frac{d\left(\log{\left(\frac{2m}{d}\right)}+1\right)-\log{\left(\frac{\eta}{4}\right)}}{m}}\right) \geqslant 1-\eta$$

$R$是测试误差，$R_{emp}$是训练误差，$m$是训练数据集的大小，并且$d$是假设类的 VC 维度。如您所见，训练和测试错误与数据集的大小有一些关系（$m$） 和$d$.

现在，就 PAC 可学习性而言，我们希望找到一个（下限或上限）$m$使得两者之间的绝对差异$R$和$R_{emp}$将小于给定的$\epsilon$在给定概率至少$1-\eta$. 因此，$m$可以计算为$\epsilon$,$\eta$， 和$d$. 例如，可以证明（[2]）训练一个二元分类器$\epsilon$测试和训练错误之间的差异，概率至少为$1-\eta$， 我们需要$O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon} \right)$iid 样本数据，即$m = O\left(\frac{d + \log\frac{1}{\eta}}{\epsilon}\right)$. 在此处查看更多示例和参考资料。

给定一个假设集$H$, 所有可能映射的集合$X\to Y$在哪里$X$是我们的输入空间和$Y$是我们的二进制映射：$\{-1,1\}$, 增长函数,$\Pi_H(m)$, 定义为生成的最大二分法数$H$在$m$点。这里的二分法是$m$点在$X$代表一个假设。假设只是我们对观点进行分类的一种方式。因此，我们知道有两个标签，

$$\Pi_H(m)\leq 2^m$$

这只是计算所有可能的假设。那么VC维度是最大的$m$在哪里$\Pi_H(m)=2^m$.

考虑一个 2D 感知器，这意味着我们的$X$是$\mathbb{R}^2$我们的分类超车道是一维的：一条线。VC 维度将为 3。这是因为我们可以粉碎（正确分类）所有二分法$m=3$. 我们可以让所有点颜色相同，或者一个点颜色不同——即$2^3=8$二分法。你可能会问，如果我们试图分类的点是共线的怎么办。这无关紧要，因为我们关心的是解决二分法本身，而不是点的位置。我们只需要一组表现出这种二分法的点（无论它们位于何处）。换句话说，我们可以选择这些点，使它们最大化我们可以用一个分类超平面（三角形）打破的二分法的数量：VC 维度是我们模型容量的陈述。

为了清楚起见，请考虑$m=4$. 我们可以将异或门的真值表表示为二分法，但无论我们在哪里选择点的位置（不是线性可分的），感知器都无法解决这个问题。因此，我们最多可以解决 8 个二分法，所以我们的 VC 维度是 3。一般来说，感知器的 VC 维度是$d+1$在哪里$d$是维度$X$和$d-1$是分类超平面的维度。

VC维度表示模型（或者，一般来说，假设类）的容量（相同的Vapnik，VC中的字母V，称之为“容量”），因此具有更高VC维度的模型具有更多容量（即它可以表示更多的功能）比具有较低 VC 维度的模型。

VC 维度通常用于提供理论界限，例如模型在给定不确定性的情况下实现特定测试误差所需的样本数量，或者类似地，用于了解给定特定数据集的估计质量。

只是为了让您了解边界的样子，请查看Vapnik的统计学习理论概述（1999 年）论文第 6 页（pdf）上的定理。

也看看这个答案，我在其中提供了有关 VC 维度的更多信息，特别是在神经网络的背景下。

由于其他答案已经涵盖了数学细节，因此我将尝试提供直观的解释。假设问题的意思，我会回答这个问题$model$并不是$learning$ $algorithm$.

一种思考方式$\mathcal V \mathcal C$维度是它是您可以选择的函数数量（即一组函数）的指标，以在一个域上近似您的分类任务。所以一个模型（这里假设神经网络、线性分离器、圆圈等，其参数可以改变）具有$\mathcal V \mathcal C$尺寸$m$粉碎单个/多个集合的所有子集$m$点它粉碎。

对于学习算法，选择一个函数，该函数从上述函数集（被您的模型粉碎，这意味着它可以用$0$错误）它需要一定的样本量$m$. 为了争论，假设您的函数集（或模型破碎）包含所有可能的映射$\mathcal X \rightarrow \mathcal Y$（认为$\mathcal X$包含$n$点，即有限大小，因此可能的功能数量是$2^n$）。它将破坏的功能之一是执行分类的功能，因此您有兴趣找到它。

任何看到的学习算法$m$样本的数量可以很容易地选择在这些点上达成一致的一组函数。同意这些采样的这些函数的数量$m$点，但不同意$n-m$点是$2^{(n-m)}$. 该算法无法从这些入围函数中进行选择（同意$m$点）作为实际分类器的一个函数，因此它只能猜测。现在增加样本量，不同意的函数数量不断下降，算法成功的概率越来越好，直到你看到所有$n$当你的算法可以准确地识别分类器的映射函数时。

这$\mathcal V \mathcal C$维度与上述论点非常相似，只是它不会破坏整个域$\mathcal X$并且只是其中的一部分。这限制了模型精确逼近分类函数的能力。因此，您的学习算法会尝试从您的模型粉碎的所有函数中选择一个函数，该函数非常接近最佳可能的分类函数，即在您的一组函数中存在最接近的可能（不精确）函数（最优）到分类函数，你的学习算法试图选择一个接近这个最优函数的函数。因此，根据我们之前的论点，需要不断增加样本量以尽可能接近最优函数。确切的数学界限可以在书中找到，但证明相当艰巨。