今天我们要讲的是VC Dimension，顾名思义，是和上次讲的VC Bound有关系的。

Definition of VC Dimension

回顾一下上次讲的。我们上次讲的是theory of generalization（一般化、举一反三的理论）：我们确保了\(E_{in} \approx E_{out}\)，当\(m_{H}(N)\)在某个k的地方break，而且N够大： \[m_{H}(N) \le B(N, k) = \sum_{i=0}^{k-1}{N \choose i}\]

将\(B(N, k)\)和\(N^{k-1}\)的表列出，我们有：

从上表中我们可以看到，当N和k很大时（其实也不用很大，\(N \ge 2, k \ge 3\)即可），我们有： \[m_{H}(N) \le B(N, k) = \sum_{i=0}^{k-1}{N \choose i} \le N^{k-1}\]

于是在将来在我们写growth function时，我们就不必再写那么复杂的式子，只需要知道它的增长速率不会超过\(N^{k-1}\)。

根据上节课的内容：

上面最后一步不等式其实是将growth function替换成了它上限的上限的上限，这个代换的条件是N够大，k够大。而N够大早已是我们的条件之一，这里只是引入了k够大这一小小的条件。

这时，如果以下几个条件成立，我们就可以说我们能够举一反三，未来测试的表现和现在训练的表现会是类似的：

• \(m_{H}(N)\)有break point k （好的H）
• N够大（好的D）
• A能够挑选出\(E_{in}\)最小的h为g（好的A）

当然这是比较理想的情况，但是实际上，我们没办法保证这些事情。所以除了这些之外，有时我们还需要一些好的运气，这样我们就大概能够做到学习。

现在我们开始讲VC Dimension。

这里的VC Dimension实际就是我们试图给之前的break point一个正式地名称。但实际上，VC Dimension是指最大的非break point。正式的定义如下：

一个hypothesis set H的VC dimension，一般由\(d_{VC}(H)\)表示，是指使得\(m_{H}(N)=2^N\)成立的最大的N。

• H能够shatter的最多输入点的个数

• \(d_{VC} = min\;k - 1\)

• 如果\(N \le d_{VC}\) \(\Rightarrow\) H能够shatter某些N个输入

• 如果\(k > d_{VC}\) \(\Rightarrow\) k一定是H的break point。

因此我们可以把上面我们的结论换一个说法，用VC dimension去替换k-1，于是有： \[ 当N \ge 2, d_{VC} \ge 2时，m_{H}(N) \le N^{d_{VC}} \]

我们再来回顾一下我们之间看过的几个例子：

这样一来，我们便有了一个新的概念：好的hypothesis set就意味着有有限的VC dimension。

如果我们有一个好的hypothesis set，即它的VC dimension有限，那么这就意味着\(E_{out}(g) \approx E_{in}(g)\)。这个结论成立：

• 与演算法A无关
• 和输入的分布P无关
• 与目标函数f无关

如此一来，我们便有了完整的机器学习流程：

我们做到了，即使在最坏的情况下，\(E_{in}\)和\(E_{out}\)也是接近的。

VC Dimension of Perceptrons

现在有了VC dimension之后，我们回到我们所学过的第一个机器学习算法PLA。

如果在2D的情况下，有这么两个故事轴线：

现在我们还没有解决的问题是：这个演算法是否可以用在多维的情况。那么在多维的情况下，到底发生了什么事情呢？

我们要解决这个问题，可以从多维的 VC dimension下手：

• 1D perceptron: \(d_{VC} = 2\)
• 2D perceptron: \(d_{VC} = 3\)

• 因此我们猜想：d-D perceptron：\(d_{VC} = d+1\)

为了证明这个猜想，我们需要证明两个方向：

• \(d_{VC} \ge d+1\)
• \(d_{VC} \le d+1\)

现在我们给大家看一组特别的数据，可以被我们的perceptron给shatter：

其中，灰色的那个维度就是对应于threshold那个\(x_{0}\)维度。这里值得注意的是：这里的矩阵X是可逆的。

那可逆这件事对我们有什么意义呢？

这样一来，我们便证明了\(d_{VC} \ge d+1\)这个方向。

为了证明\(d_{VC} \le d+1\)，我们要证明对于所有大小为d+2的数据集，我们都无法shatter。这样直接证明当然是有些困难的，接下来我们先在我们前面那个特殊的数据集上加进去一个数据看看：

通过上面我们可以看出：如果我们把\(\mathbf{x}_4\)表示成\(\mathbf{x}_1, \mathbf{x}_2, \mathbf{x}_3\)的线性组合，那么这个线性组合的依赖性会限制我们产生的dichotomy的个数。

对于一般的数据集来说：

我们注意到，这个矩阵的行数d+2大于列数d+1。根据线性代数，我们知道有线性依赖关系的存在，即我们可以把\(\mathbf{x}_{d+2}\)表示成如下格式： \[ \mathbf{x}_{d+2} = a_1\mathbf{x}_1 + a_2\mathbf{x}_2 + \ldots + a_{d+1}\mathbf{x}_{d+1} \] 其中的\(a_{i}\)有的是正的，有的是负的，有的是0，但不会全部是0。

如果现在有一个\(\mathbf{w}\)，在前面d+1个数据上产生的dichotomy与其系数的符号是一致的：

那么可知我们不能产生\((sign(a_1), sign(a_2), \ldots, sign(a_{d+1}), x)\)这个dichotomy。所以我们就证明了任何d+2个点我们都不能shatter，于是我们就证明了\(d_{VC} \le d+1\)。

Physical Intuition of VC Dimension

我们之所以叫它VC dimension，是因为它等于d+1，而其中的d就是perceptron的维度。进一步来说，perceptron中的参数\(\mathbf{w} = (w_0, w_1, \cdots, w_d)\)决定了H的自由度。

我们说H是无限的，是因为假如把每个维度上的数据的值都比作一个“类比式（analog）”的旋钮，那么它们组合起来就会有无限种可能性，因为单单一个旋钮就有无限种可能性：

那我们看VC dimension，其实它是等于effective ‘binary’ degrees of freedom。’binary’是因为我们现在研究的是二元分类问题，而effective是因为那些自由度里有些可能是无效的。这个自由度也就告诉了我们这个H的强度，即最多能够shatter的输入的个数。

我们来看看我们之前看过的positive ray和positive interval的例子：

从中我们大致可以看出，\(d_{VC}\)实际基本就是自由参数的个数（大致上是对的，但不总是这样）。通常我们在估计VC dimension时，只需要看看自由参数的个数就可以了。

现在我们来看看M和\(d_{VC}\)的关系：

这样一来，\(d_{VC}\)就和M一样，成为了我们将来选择learning model和hypothesis set的一个重要的工具。

Interpreting VC Dimension

现在我们想更深入地了解VC dimension的意义是什么。首先，我们把VC bound重新写过：

于是我们得到了\(\epsilon = \sqrt{\frac{8}{N} ln(\frac{4(2N)^{d_{VC}}}{\delta})}\)。这个式子的意义是，有很大的概率： \[ (gen.error)|E_{in}(g) - E_{out}(g)| \le \sqrt{\frac{8}{N} ln(\frac{4(2N)^{d_{VC}}}{\delta})}\] \[ E_{in}(g) - \sqrt{\frac{8}{N} ln(\frac{4(2N)^{d_{VC}}}{\delta})} \le E_{out}(g) \le E_{in}(g) + \sqrt{\frac{8}{N} ln(\frac{4(2N)^{d_{VC}}}{\delta})}\]

这就像一个置信区间，表示\(E_{out}(g)\)以一定的概率落在这个区间内部。其中，我们并不太关心左边部分\(E_{out}(g)\)的下界，而更关心右边的上界，即结果最坏会有多坏。其中，根号下的部分我们称之为model complexity，表示这个hypothesis set的复杂度给我们的generalization带来的惩罚。记为\(\Omega(N,H,\delta)\)。

下面我们通过画图的方式看看VC dimension给我们的信息：

这个图告诉我们，最好的VC dimension是在中间的某个地方。将来我们也会时常看到这种图，只不过横轴可能不是VC dimension而是其他的跟它有关的变量。我们会根据这个图设计更好的机器学习的演算法。

如果我们只是为了降低\(E_{in}\)，一味地增加VC dimension，使得H非常的powerful，那恐怕这不是一个最好的选择，因为会给我们的\(E_{out}\)带来很大的complexity penalty。

VC bound其实还有另外一个意思，就是sample complexity，即资料量的复杂度。

但是在实践中，我们并不需要去找到 \(10000d_{VC}\)这么多的数据，而只需要\(10d_{VC}\)就能够得到还不错的learning表现了。

上面这个问题也说明，VC bound是很宽松的。这个宽松的来源是：

• 使用Hoeffding时不需要知道\(E_{out}\)（对任何分布P，任何target function f都成立）
• 使用\(m_{H}(N)\)而非\(|H(\mathbf{x}_1, (\mathbf{x}_2, \ldots, (\mathbf{x}_N)|\)（对任何一个数据集都成立）
• 使用\(N_{d_{VC}}\)而非\(m_{H}(N)\)（对任何有相同VC dimension的H都成立）
• 使用了union bound确保每一个h的\(E_{in}\)和\(E_{out}\)都不会差太多（对A做出的任何选择都成立）

这些原因就解释了，为什么实践中需要的数据量比理论上的差很多。

虽然VC bound很宽松，而且有很多研究者想让它更紧一点。但是如果要做到和VC bound的包容度一样，很难很难做的比VC bound更好。而且VC bound对不同的learning model是差不多宽松的，于是我们将来就可以使用VC dimension去比较不同的learning model的表现。

这里的VC bound是一个非常理论性的结果，但是我们会拿它告诉我们的“哲学信息”来设计机器学习演算法。

Summary

目前我们讨论的都是没有noise且是binary classification的问题。下一次我们会尝试把VC dimension的概念延伸到更多种类的learning的问题上。