机器学习基础(2)-机器学习可行性

问题描述

首先我们回顾机器学习的整个流程。首先我们认为存在一个真实的函数\(f:X \rightarrow Y\)，同时我们存在现有的数据（训练集）\(D={(x_1,y_1),...,(x_N,y_N)}\)。完成机器学习，我们需要有一个假设空间\(H\)，即机器学习的模型，另外还需要有一个Learning Algorithm \(A\)，即机器学习的策略和算法。通过学习算法，从假设空间中选择一个较好的结果映射\(g:X \rightarrow Y\)，使得\(g\)和\(f\)尽可能接近。

更具体地说，在选择\(g\)的过程中，我们会选择经验误差（概论中提到的经验风险或者经验损失）尽可能地小的模型，这里将经验风险记作\(E_{in}(g;D)\)，其中\(D\)表示训练集。另一方面，我们也希望这个模型能够在没有看过的数据上得到很好的表现，也就是说泛化误差（概论中提到的期望风险）尽可能地小，这里将泛化风险记作\(E_{out}(g;X)\)，其中\(X\)是所有可能的输入，也就是输入空间。简单来说，如果机器学习顺利进行，我们会从假设空间\(H\)中选择一个\(E_{in}\)最小的模型，而这个模型能够达到的效果是它在没有看过的数据上也能得到很好的表现，也就是\(E_{out}\)也很小。

那么现在我们提出的问题是，为什么机器学习能够做到这一点，也就是机器学习的可行性。进一步，机器学习的可行性就是要解释下面两个问题：

• 为什么\(E_{in} \approx E_{out}\)，也就是为什么模型能够从训练集向外推广到没有见过的数据上
• 为什么\(E_{out} \approx 0\)，也就是模型的效果怎么能比较好

在下面的分析中，我们以二分类为例讨论机器学习的可行性。在二分类的情况下，我们的输出空间为\(Y=\{+1,-1\}\)，同时经验误差\(E_{in}\)和泛化误差\(E_{out}\)计算如下，它们都是关于映射\(h\)的函数，其中\(h\in H\)。 \[ E_{in} (h) = \frac{1}{N}\sum_{i=1}^{N} I[h(x_i) \neq f(x_i)] \\ E_{out}(h) = P\{ h(x) \neq f(x) \} \] 这里的\(I(x)\)是指示函数，如果\(x\)为真则返回1，如果\(x\)为假则返回0。

有限容量的假设空间

首先我们考虑对于一个固定的\(h\in H\)，我们能够得出什么样的结论。

由于\(E_{in}\)的计算是在训练集上的，\(E_{out}\)的计算是在模型没有看过的数据上的，但是这两部分数据是独立同分布的，对应真实存在的一个数据分布\(P\)，因此根据Hoeffding不等式，我们可以得到下面的结论： \[ P[|E_{in}(h)-E_{out}(h)| \ge \epsilon] \le 2\exp(-2\epsilon^2N) \]

Hoeffding不等式描述如下：

假设\(X_1,X_2,...,X_N\)是独立随机变量，且\(X_i \in [a_i,b_i],i=1,2,...,N\)；那么对任意的\(t>0\)，有下面的不等式成立： \[ P[|\bar{X} -E(\bar{X})| \ge t] \le \exp[-\frac{2N^2t^2}{\sum_{i=1}^{N}(b_i-a_i)^2}] \] 考虑联系到这里的\(E_{in}\)和\(E_{out}\)，则分别可以对应到\(\bar{X},E(\bar{X})\)。同时这里的\(X_i \in[0,1]\)，所以有上面的结论。

上面的式子含义是，对于一个固定的\(h\in H\)来说，坏事发生的机率是比较小的。这里的坏事指的是\(|E_{in}(h)-E_{out}(h)| \ge \epsilon\)，也就是做不到\(E_{in} \approx E_{out}\)。

一般来说，如果\(h\)是固定的，当\(N\)很大的时候，我们能够认为\(E_{in} \approx E_{out}\)。当然这只能保证模型能够外推，并不能保证模型的效果，也就是不能保证\(E_{out} \approx 0\)。这是因为我们的\(h\)是固定的，不能保证这个\(h\)在训练集上的\(E_{in} \approx 0\)。在这种情况下，如果\(h\)在训练集上的效果很糟糕，那么它的确能够外推到没有见过的数据上，只不过表现也是很糟糕。因此，机器学习采用的方法是给定一个假设空间\(H\)，希望能够在这个假设空间中找到一个\(h\)，使得\(E_{in} \approx 0\)。

我们记假设空间的大小\(|H|=M\)，那么\(M\)可能是有限的，可能是无限的。我们首先考虑有限容量的假设空间。

在有限容量的假设空间\(H = \{h_1,h_2,...,h_M\}\)中，学习算法从中选择一个\(h\)作为输出映射。我们来考虑此时坏事发生的概率有多少： \[ \begin{aligned} P[\exists h \in H,s.t. &|E_{in}(h)-E_{out}(h)| \ge \epsilon] \\ & \le \sum_{i=1}^{M} P[|E_{in}(h_i)-E_{out}(h_i)| \ge \epsilon] \\ & \le \sum_{i=1}^{M} 2\exp(-2\epsilon^2N) = 2M\exp(-2\epsilon^2N) \end{aligned} \] 上面的推导很容易理解。因为学习算法选择的\(h\)也是\(h1,h2,...,h_M\)中的一员，它发生坏事的概率一定会小于所有\(h_i\)发生坏事的概率之和（Union Bound）。

考虑上面的不等式，当样本容量\(N\)足够大的时候，坏事发生的概率是比较小的。也就是说面对\(M\)个（有限个）假设函数，学习算法\(A\)可以从中选择一个\(E_{in}\)相对较小的假设函数作为最终的结果映射，并且能够满足\(E_{in}\approx E_{out}\)。同时由于\(E_{in}\)相对较小，所以\(E_{out}\)也相对较小。也就解决了我们在问题描述中提到的两个问题。

至此，我们已经证明了在有限容量的假设空间上，机器学习的可行性。下一步，我们需要证明在无限容量的假设空间上，机器学习的可行性。

无限容量的假设空间

通过上面的描述，我们直到了当\(M\)有限，机器学习是可行的。但是在实际上，我们通常面对的都是无限容量的假设空间。当\(M\)变得无限大，上面的不等式显然也没有什么意义。不过我们可以考虑上面的推导过程中，\(M\)是通过Union Bound进行引入的，我们考虑一个\(h\)发生坏事的概率小于等于所有\(h_i\)发生坏事的概率之和。这样的放缩是合理的，但是这也许是一个过度的估计（over-estimating）。如果考虑概率之和，那也就是认为每个\(h_i\)发生坏事的情况相互独立互不相关，但是实际上很大部分的\(h_i\)，它们发生坏事的情况是互相重叠的。因此在考虑无限容量的假设空间时，我们需要想办法将这个过度估计进行修正。

首先我们引入相关概念Shatter、成长函数、Break Point、Bounding Function，为后续的证明进行铺垫。

成长函数、Shatter、Break Point

我们面对的是无限容量的假设空间\(H\)。既然无限容量较难处理，一种想法是能不能将无限的假设空间划分成有限中假设函数类别，而属于同一类别的假设函数，发生坏事的情况是重叠的。

考虑一个数据集\(D=\{x_1,x_2,...,x_N\}\)，对于一个给定的假设函数\(h\)，它对\(D\)的每一个数据\(x_i\)只能做出+1或者-1的判断。换句话说，在一个给定的数据集\(D\)看来，以假设函数的预测结果\(h(x_i)\)为导向，假设空间中的函数可以分为不同的类别，并且这个类别的个数是有限个。很容易得到类别个数最高不能超过\(2^N\)。当然也会存在达不到\(2^N\)的情况，这是由于对于一些假设空间，某些结果是达不到的，例如对于感知机算法，一些线性不可分的结果是达不到的。

于是，对于一个给定的假设空间\(H\)，以及一个给定的数据\(D=\{x_1,x_2,...,x_N\},x_i\in X\) ，上面的类别数记为\(H(x_1,x_2,...,x_N)\)，它表示\(H\)在\(D\)上能够产生的所有二分类的结果数。很明显地，有\(H(x_1,x_2,...,x_N) \le 2^N\)。

上面的结果数\(H(x_1,x_2,...,x_N)\)，与假设空间\(H\)以及给定数据集\(D\)有关。我们希望排除数据集\(D\)的影响，则引入一个成长函数的概念。成长函数记为\(m_H(N)\)，定义如下： \[ m_H(N) = max_{\{x_1,x_2,...,x_N\}} [H(x_1,x_2,...,x_N)] \] 成长函数\(m_H(N)\)表示对于一个特定的假设空间\(H\)，它在所有大小为N的数据集上能够产生的二分类结果数，其中最大的那一个数量。可以看到，成长函数\(m_H(N)\)在给定假设空间\(H\)的情况下，仅与数据集\(D\)的大小有关。

而Shatter的概念可以描述如下：对于一个给定的假设空间\(H\)来说，如果存在一个数据集\(D=\{x_1,x_2,...,x_N\}，x_i\in X\)，使得\(H(x_1,x_2,...,x_N) = 2^N\)，则称假设空间\(H\)能够Shatter（打散）这个数据集\(D\)。而如果\(H\)不能Shatter \(D\)，它的含义是对于任意的\(D = \{x_1,x_2,...,x_N\} ，x_i\in X\)，假设空间\(H\)都无法产生所有的二分类结果。我们可以得到，如果\(H\) 能够Shatter \(D,(|D| = N，数据集D的大小为N)\)，则表示\(m_H(N) = 2^N\)，否则，则有\(m_H(N) < 2^N\)。

根据Shatter的概念，我们可以知道：对于一个给定的假设空间\(H\)，假如它不能Shatter大小为k的数据集\(D\)，那么对于任意\(k'>k\)，\(H\)也无法Shatter大小为\(k'\)的数据集\(D'\)。换成使用成长函数\(m_H(N)\)的说法，则是如果存在\(m_H(k) < 2^k\)，那么对应任意的\(k'>k\)，也有\(m_H(k')<2^{k'}\)。Break Point则是指这样一个数k，它是第一个不能被\(H\) Shatter的数据集的大小，也就是说，它是满足\(m_H(k) \neq 2^k\)的最小值。它的意义可以解释如下：当Break Point的值为\(k\)时，我们在任选\(k\)个数据\(x_i\)，我们无法得到全部的二分类结果（\(2^k\)个结果）。

Break Point是假设空间\(H\)的一个伴随性质，如果我们确定了假设空间\(H\)，那么对应的Break Point也就能够随之确定。当然存在一种情况是Break Point不存在，那也就是说对于这样的假设空间\(H\)，它对任意的\(N\)都有\(m_H(N) = 2^N\)。

Bounding Function

假设对于一个假设空间\(H\)，它的Break Point值为\(k\)。那么我们可以发现，当\(N>k\)的时候，Break Point限制了成长函数\(m_H(N)\)的大小。综合来说，影响成长函数\(m_H(N)\)的因素主要有两个：

• 抽样数据集的大小\(N\)
• Break Point 的值 \(k\)，这个值伴随假设空间\(H\)的确定而确定

我们可以引入一个新的函数，称为Bounding Function，记为\(B(N,k)\)。它表示当Break Point值为\(k\)的时候，成长函数\(m_H(N)\)可能的最大值。也就是说，\(B(N,k)\)是\(m_H(N)\)的上界，有： \[ m_H(N) \le B(N,k) \] 此时对于这个假设空间H，它的Break Point值为\(k\)。

接下来考虑这个Bounding Function的范围。

当\(k=1\)的时候，有\(B(N,k)=1\)。这是因为对于大小为N的数据集\({x_1,x_2,...,x_N}\)，无论结果如何，我们只能定义一种对应的输出。如果我们想要在这个基础上增加下一种对应的输出，就会与\(k=1\)冲突。因为\(k=1\)的含义是任选1个数据，我们无法得到全部的二分类结果，也就是对于一个\(x_i\)，我们的分类结果只能有一个。

当\(N<k\)的时候，有\(m_H(N) = 2^N\)，所以\(B(N,k)=2^N\)。

当\(N=k\)的时候，由于\(k\)是第一个不能被Shatter的大小，所以能够得到的二分类结果至少要比全部的二分类结果少一个，即\(B(N,k) = 2^N-1\)。

结合上面三种情况，有： \[ B(N,k) = \begin{cases} 1, \quad k=1\\ 2^N, \quad N<k \\ 2^N-1, \quad N=k \end{cases} \] 接下来考虑\(N>k\)的情况。

我们可以在\(N-1\)个数据的基础上考虑\(N\)个数据的由来。\(N\)个数据就可以看作是在\(N-1\)个数据上增加一个数据。即在数据集\(\{x_1,x_2,...,x_{N-1}\}\)的基础上增加一个数据\(x_N\)。从而\(N\)个数据对应的二分类结果也可以从\(N-1\)个数据对应的二分类结果上得来。对于一个特定的二分类结果\(\{h(x_1),h(x_2),...,h(x_{N-1})\}\)，在新判断第\(N\)个数据的时候，有两种情况：

• 第一种是\(h(x_N)\)可以是+1也可以是-1，都可以选择。这种情况出现的个数记为\(\alpha\)
• 第二种是\(h(x_N)\)只能选择+1或者-1的其中一种。这种情况出现的个数记为\(\beta\)

由此，我们可以说\(B(N,k) = 2\alpha + \beta\)。

在上面的\(N\)个点构成的二分类结果集中，由于\(N>k\)，所以应该满足\(H\)无法Shatter 大小为\(k\)的数据集。所以在\(\{x_1,x_2,...,x_{N-1},x_N\}\)任选\(k\)个\(x_i\)，结果集中不能包括所有的二分类结果。因此，在\(\{x_1,x_2,...,x_{N-1}\}\)中任取\(k\)个点，应该满足结果集中不能包括所有的二分类结果，否则就和上面无法Shatter 大小为\(k\)的数据集相悖。而\(\{x_1,x_2,...,x_{N-1}\}\)的所有二分类结果大小为\(\alpha+\beta\)，所以有\(\alpha + \beta \le B(N-1,k)\)。

同时考虑情况1中的\(\{x_1,x_2,...,x_{N-1}\}\)，如果在其中任取\(k-1\)个点，应该满足结果集中不能包括所有的二分类结果，否则的话，我们可以增加对应的\(x_N\)，\(x_N\)的结果既可以是+1又可以是-1，这样就违反了\(H\)无法Shatter 大小为\(k\)的数据集。这一部分的二分类结果集大小为\(\alpha\)，所以有\(\alpha \le B(N-1,k-1)\)。

所以有，当\(N>k\)时，有\(B(N,k) = 2\alpha + \beta = \alpha + \alpha + \beta \le B(N-1,k) + B(N-1,k-1)\)。在\(N \le k\)的情况下，\(B(N,k)\)的值在上面已经提供，经过计算，发现也能满足这个不等式（确切地说在\(N\le k\)的情况下，能够直接满足等式）。因此对于所有的\(N\)和\(k\)，我们都有： \[ B(N,k) \le B(N-1,k) + B(N-1,k-1) \] 而根据这个不等式，我们可以得到下面的不等式： \[ B(N,k) \le \sum_{i=0}^{k-1}\binom{N}{i} \] 这个不等式可以通过数学归纳法来进行证明：

1.当\(N=1\)的时候，有： \[ \begin{cases} B(1,1) = 1 \le \sum_{i=0}^{0} \binom{1}{i} = 1, \quad k=1\\ B(1,k) = 2 \le \sum_{i=0}^{k-1} \binom{1}{i} = 1+1 = 2, \quad k >1 \end{cases} \] 2.当\(N=2\)的时候，有： \[ \begin{cases} B(2,1) = 1 \le \sum_{i=0}^{0} \binom{2}{i} = 1, \quad k=1\\ B(2,2) = 3 \le \sum_{i=0}^{1} \binom{2}{i} = 1+2 = 3, \quad k=2\\ B(2,k) = 4 \le \sum_{i=0}^{k} \binom{2}{i} = 1+2+1 = 4, \quad k>2 \end{cases} \] 3.假设对于任何的\(N<N_0\)，都有结论成立，则当\(N=N_0\)的时候，有： \[ \begin{aligned} B(N,k) &\le B(N-1,k) + B(N-1, k-1)\\ &\le \sum_{i=0}^{k-1} \binom{N-1}{i} + \sum_{i=0}^{k-2} \binom{N-1}{i} \\ &= 1 + \sum_{i=1}^{k-1} \binom{N-1}{i} + \sum_{i=1}^{k-1} \binom{N-1}{i-1}\\ &= 1 + \sum_{i=1}^{k-1} [\binom{N-1}{i} + \binom{N-1}{i-1}]\\ &= 1 + \sum_{i=1}^{k-1} \binom{N}{i}\\ &= \sum_{i=0}^{k-1} \binom{N}{i} \end{aligned} \] 所以我们可以得到如下的结论，如果对于一个假设空间\(H\)来说，Break Point存在且值为\(k\)的话，有如下不等式成立：（如果没有Break Point ，则表示\(k = \infty\)） \[ m_H(N) \le B(N,k) \le \sum_{i=0}^{k-1} \binom{N}{i} \]

不等式代换

回到我们的目标，我们希望能够在当\(M\)为无限的时候证明： \[ P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \le 某个系数 \] 其中这个系数的变化由\(N\)主导。例如在当\(M\)有限的时候，这个系数就是\(2M\exp(-2\epsilon^2N)\)。

实际上，经过一系列证明推导之后，可以该系数为： \[ 2\cdot 2m_H(2N)\cdot\exp{(-2\cdot \frac{1}{16}\epsilon^2N)} \]

具体的数学证明相对比较复杂，本人也没有完全学习。这里仅记录林轩田老师在课程中提到的三个证明要点。

第一点在于需要利用\(E'_{in}\)来代替\(E_{out}\)。这里我们考虑\(E'_{in}\)是一个在验证集verification set \(D'\)上的误差，其中\(|D'| = N\)。也就是说利用验证集来评估模型的效果。如此，$|E_{in}-E_{out}| \(的概率就可以转化成考虑\)|E_{in} - E'_{in}|$的概率，具体的转化结果如下： \[ \frac{1}{2}P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ]\\ \le P[\exists h \in H, s.t. |E_{in}(h) - E'_{in}(h)| \ge \frac{\epsilon}{2} ] \] 第二点在于需要利用成长函数进行放缩。我们仍然是考虑坏事发生的可能性。对于假设空间来说，坏事发生的情况很多都是互相重叠的，最终有如下的结果： \[ \begin{aligned} &P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \\ \le& 2 P[\exists h \in H, s.t. |E_{in}(h) - E'_{in}(h)| \ge \frac{\epsilon}{2}] \\ \le& 2 m_H(2N)P[\text{fixed}\ h \in H, s.t. |E_{in}(h) - E'_{in}(h)| \ge \frac{\epsilon}{2}]\\ \end{aligned} \] 第三点在于再次使用Hoeffding不等式进行替换，从而得到下面的结果： \[ \begin{aligned} &P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \\ \le& 2 m_H(2N)P[\text{fixed}\ h \in H, s.t. |E_{in}(h) - E'_{in}(h)| \ge \frac{\epsilon}{2}] \\ \le& 2m_H(2N)\cdot 2\exp{(-2(\frac{\epsilon}{4})^2N)} \end{aligned} \] 总而言之，整理之后，我们有对于无限容量的假设空间，我们可以得到下面的不等式成立： \[ P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \le 4m_H(2N)\exp{(-\frac{1}{8} \epsilon^2N )} \] 而在前面我们已经证明了，对于一个假设空间\(H\)来说，如果存在Break Point且值为\(k\)，则有： \[ m_H(N) \le B(N,k) \le \sum_{i=0}^{k-1} \binom{N}{i} \] 这表示成长函数的上界是一个多项式，并且是\(N-1\)阶的，因此整体的系数变化主导是\(N\)。于是我们可以推导出，如果假设空间的Break Point存在（用后面的话来说就是VC Dimension存在），当\(N\)足够大的时候，坏事发生的概率是很小的，从而有\(E_{in} \approx E_{out}\)。又因为我们的假设空间无限大，学习算法完全可以从中学习到一个\(E_{in}\)相对较小的作为最终的输出映射，由此我们证明了在无限容量的假设空间上，机器学习的可行性。

VC Bound 和 VC Dimension

在上面的推导中，我们得到了一个不等式： \[ P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \le 4m_H(2N)\exp{(-\frac{1}{8} \epsilon^2N )} \] 这个不等式也就是著名的Vapink-Chervonenkis（VC）不等式。

同时，这里引入一个新的概念，称作VC Dimension，记作\(d_{vc}\)。它和前面Break Point的概念联系紧密。对于一个假设空间\(H\)来说，如果它的Break Point值为\(k\)，那么就有\(d_{vc} = k-1\)。Break Point是第一个满足\(m_H(k) \neq 2^{k}\)的值，VC Dimension则是最后一个满足\(m_H(k) = 2^k\)的值。VC Dimension也是假设空间\(H\)的一个伴随性质，表示该假设空间最大完全正确的分类能力，在一定程度上也反映了假设空间的自由度。这里的\(d_{vc}\)仅与假设空间\(H\)有关，与学习算法\(A\)，输入分布\(P\)，目标映射\(f\)等都没有关系。

有了这个概念，我们可以继续上面不等式的整理： \[ \begin{aligned} &P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \\ \le& 4m_H(2N)\exp{(-\frac{1}{8} \epsilon^2N )} \\ \le & 4B(2N,k)\exp{(-\frac{1}{8} \epsilon^2N )} \\ \le & 4\sum_{i=0}^{k-1}\binom{2N}{i}\exp{(-\frac{1}{8} \epsilon^2N )} \\ \le & 4(2N)^{k-1}\exp{(-\frac{1}{8} \epsilon^2N )} \\ \le & 4(2N)^{d_{vc}}\exp{(-\frac{1}{8} \epsilon^2N )} \end{aligned} \] 通过VC不等式，我们可以大体估计需要的数据量，如果给定一个\(\delta\)>0表示我们能够接受坏事的概率，以及精度\(\epsilon >0\)，那么我们希望\(4(2N)^{d_{vc}}\exp{(-\frac{1}{8} \epsilon^2N )} \le\delta\)，于是则有： \[ N \ge \frac{8}{\epsilon^2}\ln{(\frac{4((2N)^{d_{vc}})}{\delta})} \] 由此就可以根据条件大体估计需要的数据量。但是实际上这个估计通常是一个过度估计，通常在小于这个数据量的时候，也能达到学习效果。这是因为我们在推导这个不等式的时候，利用了很多上界、放缩等技巧，导致这个边界实际上比较宽松。

泛化边界

结合VC Dimension的VC不等式如下： \[ P[\exists h \in H, s.t. |E_{in}(h) - E_{out}(h)| \ge \epsilon ] \le 4(2N)^{d_{vc}}\exp{(-\frac{1}{8} \epsilon^2N )} \] 在这个不等式中，我们利用$\(来表示\)\(，记\)= 4(2N)^{d_{vc}}$，则可以计算得到： \[ \epsilon = \sqrt{\frac{8}{N}\ln{\frac{4(2N)^{d_{vc}}}{\delta}}} \] 重新描述不等式的含义，就是坏事情的概率不超过\(\delta\)，也就是好事情的概率最小为\(1-\delta\)。那么这里什么是好事情呢？就是\(|E_{in}(h) - E_{out}(h)| \le \epsilon\)。所以有超过\(1-\delta\)的概率，有： \[ E_{in}(h) -\sqrt{\frac{8}{N}\ln{\frac{4(2N)^{d_{vc}}}{\delta}}} \le E_{out}(h) \le E_{in}(h) + \sqrt{\frac{8}{N}\ln{\frac{4(2N)^{d_{vc}}}{\delta}}} \] 也就是说我们已经推导出了泛化误差\(E_{out}\)的边界。不过一般来说，我们更加关心泛化误差的上界。记 \[ \Omega(N,H,\delta) = \sqrt{\frac{8}{N}\ln{\frac{4(2N)^{d_{vc}}}{\delta}}} \] 则有泛化误差的上界为$E_{in} + (N,H,) $，或者可以称其为泛化边界。

泛化误差上界告诉我们，我们至少有\(1-\delta\)的把握，可以说泛化误差$E_{out}E_{in} + (N,H,) \(。其中\)(N,H,) \(与样本数量\)N\(，假设空间\)H\(（\)d_{vc}\(）以及\)$有关。这一项被称为模型复杂度，相关变量有如下的变化情况：

随着\(d_{vc}\)的增大，训练误差\(E_{in}\)会减小，但是模型的复杂度\(\Omega\)会增加。这告诉我们模型并不是越复杂越好。模型复杂，虽然\(E_{in}\)降低了，但是与此同时模型复杂度\(\Omega\)会增加。因此好的模型需要综合考虑这两项，这也是正则化中增加惩罚项的缘由。

总结与启示

总结来说，本文主要说明了在有限容量和无限容量的假设空间上，机器学习的可行性。由此引出了VC 不等式以及VC Dimension的概念。这里的VC Bound是一个比较宽松的边界，这是因为我们在推导过程中多次使用上界来进行替代。不过也正是因为这种宽松，VC Bound的适用性很广，它能够适用于所有的机器学习，而与具体的模型、算法无关。

而抛开所有推导的细节，我们考虑结果给我们的启示意义。就是说，VC Dimension基本上能够表征假设空间（模型）\(H\)的复杂程度，复杂程度越高，我们可以得到的训练误差也越低，但是同时也会导致\(\Omega\)项的增大。因此一个优秀的模型需要综合考虑这两部分，才能使得\(E_{out}\)足够小，使得模型具有良好的泛化能力。

参考文章

1. 《机器学习基石》- 林轩田 - Why Can Machine Learn
2. 《机器学习》 - 周志华 - 第十二章 计算学习理论
3. 机器学习理论 - 简书 (jianshu.com)