VC维度

对神经网络容量的严格衡量是VC 维度，它直观地是一个数字或界限，用于量化从数据中学习的难度。

样本复杂度是模型（或学习器）为了合理确定给定某些数据做出的预测的准确性而必须暴露的训练实例的数量，与该数量成正比。

Eduardo D. Sontag的论文VC Dimension of Neural Networks (1998) 很好地介绍了神经网络的 VC 维度（尽管这些概念非常抽象，您可能需要阅读数次才能完全掌握它们）。此答案中的信息高度基于该论文。

破碎和VC维度

在第 2 节“概念和 VC 维度”中，他描述了 VC 维度背后的基本概念（不仅适用于神经网络），例如 shattering 的概念（即一组集合粉碎另一个集合是什么意思？），这是计算学习理论中的一个众所周知的概念，用于定义 VC 维度（参见定义 2），因此您肯定需要熟悉这个概念才能理解 VC 维度，从而了解神经网络的容量（用VC维度计算）。

函数和神经网络的 VC 维度

然后，他提供了 VC 维度的等效定义，但针对函数（等式 6）。鉴于神经网络表示函数，那么我们也可以定义神经网络的 VC 维度。神经网络权重的特定组合代表特定函数，可以为其定义 VC 维度。更准确地说，参数化函数（和神经网络）可以表示为

$$\beta : \mathbb{W} \times \mathbb{U} \rightarrow \mathbb{R}$$

在哪里$\mathbb{W} = \mathbb{R}^p$和$p$是神经网络的权重（或参数）的数量，$\mathbb{U}$是输入空间和$\mathbb{R}$输出空间。所以，在这种情况下，$\beta$也可以表示一个神经网络，有一定的参数空间$\mathbb{W}$, 输入空间$\mathbb{U}$和一个输出空间$\mathbb{R}$.

向量$\mathbf{w} = (w_1, \dots, w_p) \in \mathbb{W}$代表神经网络权重的特定组合，因此它代表特定的函数。该权重向量的每个选择的所有函数的集合可以表示为

$$\mathcal{F}_{\beta} = \{ \beta(\mathbf{w}, \cdot) \mid \mathbf{w} \in \mathbb{W} \}$$

VC 维度 (VCD) 的$\beta$那么可以定义为

$$\text{VCD}(\beta) := \text{VCD}(\mathcal{F}_{\beta})$$

因此，VC维度是对具有一定架构的神经网络容量的度量。此外，VC 维是等价地为与神经网络相关的一组函数定义的。

如何计算VC维度？

要计算神经网络的实际 VC 维度，需要更多的创造力。因此，我将仅报告一些神经网络的 VC 维度。有关更多详细信息，您应该完整阅读引用的论文（不止一次）以及其他论文和书籍（尤其是本答案中描述的那些，它们提供了 CLT 概念的介绍）。

感知器的 VC 维度

感知器的 VC 维度是$m + 1$， 在哪里$m$是输入的数量。鉴于感知器表示线性和仿射函数，感知器的 VC 维数也等于参数的数量。但是，请注意，即使感知器的 VC 维度在参数和输入的数量上是线性的，但这并不意味着感知器可以学习任何函数。实际上，感知器只能表示线性函数。有关详细信息，请参阅神经网络的 VC Dimension 的第 3.1 节。

单隐层神经网络的VC维数

让$n$为隐藏单元的个数，则单个隐藏层神经网络的 VC 维数小于等于$n+1$. 有关详细信息，请参阅神经网络的 VC Dimension 的第 3.2 节。

具有二进制激活的多层神经网络的 VC 维度

具有二元激活的多层神经网络 (MLP) 的 VC 维度和$p$权重（或参数）是$\mathcal{O}(p \log p)$. 有关更多详细信息，请参阅论文VC Dimension of Neural Networks的定理 4（和相关部分）。

具有实值激活的 MLP 的 VC 维度

具有实值激活的 MLP 的 VC 维度不再受限于$\mathcal{O}(p \log p)$并且可以是参数数量的指数。请参阅神经网络的 VC Dimension 的 5.3 节。

具有线性激活的 MLP 的 VC 维度

具有线性激活的 MLP 的 VC 维度是$\mathcal{O}(p^2)$. 参见论文VC Dimension of Neural Networks的定理 5 。

笔记

VC 维度通常表示为一个界限（例如使用 big-O 表示法），它可能并不严格。

在任何情况下，VC 维度都是有用的，因为它提供了一些保证。例如，如果您使用 VC 维度来描述学习某项任务所需样本数量的上限，那么您就有一个精确的数学公式，可以保证您不需要比边界表示的样本更多的样本。为了实现一个小的泛化误差，但在实践中，您可能需要比边界表示的样本更少的样本（因为这些边界可能不严格，或者 VC 维度也可能不严格）。

进一步阅读

有一篇更新的论文（发表于 2017 年的 MLR）证明了具有 ReLU 激活函数的深度神经网络的 VC 维度的新的和更严格的上限和下限：分段线性神经网络的近乎紧密的 VC 维度边界。因此，您可能应该先阅读本文。

关于使用代数拓扑表征神经网络容量的论文也可能有用且有趣。另请参阅我一直引用的论文的第 6 节，代数技术：神经网络的 VC 维度。

神经网络的容量显然与其可以表示的函数数量有关，因此它与神经网络的通用逼近定理密切相关。请参阅在哪里可以找到通用逼近定理的证明？.

大多数测量神经网络复杂性的方法都相当粗糙。一种常见的复杂性度量是VC 维度，可以在此处和此处找到讨论。例如，神经网络的VC 维度太大，无法给出模型所需训练样本数量的强上限（VC 分析提供的上限远高于我们观察到的神经网络能够概括自）。

另一个常用的容量度量是参数的数量。我们在 ICLR 发表的论文“ Understanding deep learning requires rethinking generalization ”中看到，引用次数超过 1400 次，参数多于数据的网络通常具有记忆数据的能力。该论文提供了令人信服的证据，证明统计学习理论（VC 维度、Rademacher 复杂度）提供的传统泛化方法无法完全解释神经网络的表观能力。一般来说，神经网络似乎具有很大的容量，因为它在某些任务上表现出明显的良好性能。

除了这些想法之外，通用逼近定理告诉我们，这组神经网络可以任意逼近任何连续函数，这强烈表明任何神经网络都有很大的容量。