网易《机器学习》第10课--学习理论02

机器学习理论 网易机器学习

---

回顾

在上节课，我们讲到了在集合$\mathcal{H}$为有限集的相关情况，结论之一就是"样本复杂度"的公式，即：
假设$|\mathcal{H}| = k$，固定$\gamma,\delta$，为了保证"$\varepsilon(\hat h) \leq \operatorname*{min}_{h \in \mathcal{H} }\varepsilon(h) +2\gamma$"在至少$1-\delta$的概率前提下成立，我们有以下要求：

$$m \leq \frac{1}{2\gamma^2}log\frac{2k}{\delta} = O(\frac{1}{\gamma^2}log\frac{k}{\delta})$$

在$\mathcal{H}$为无限集时的情况

在更多的情况下，我们的假设函数集合是无限集的，即使是在线性分类实参数的前提下。也就是说，此时的$k$会非常大，那么如果依然使用上面的公式，那么就需要有无穷多个训练样本才能够达到性能指标。这显然是不可能的。
可以从另外一个角度来考察这个问题。我们先来考虑一个不那么严谨的结论，有一个基本的认识，然后再来给出正式的结论。
令假设函数集合$\mathcal{H}$是以$c$个实数作为参数（比如logistic模型，如果有$n$个特征，那么模型的参数会有$c = n+1$个）。理论上$c$个参数的取值可以有无穷多个，使得假设函数集合无限大。但是实际上，在计算机表达的时候，每一个实数都用64位来表示，那么共需要64$c$位来表示这个模型集合，考虑到每一位只有0,1两种状态，那么在计算机的表达中，这个无限大的假设函数集合的大小其实是$2^{64c}$。即是上面公式中的$k$。
代入到上面的公式，可得：

$$m \leq \frac{1}{2\gamma^2}log\frac{2·2^{64c}}{\delta} = O(\frac{c}{\gamma^2}log\frac{1}{\delta})$$
这个公式给我们的理解就是：训练样本个数$m$和集合$\mathcal{H}$参数个数$c$成正比。有了这个直观的理解之后，让我们来认真验证这样理解是否正确。正确的表述方式更加正式，它需要大量的数学证明，让我们仅写下重要的部分吧。

VC维

给定一个集合$S=\{x^{(1)},...,x^{(d)}\}$（和训练样本集合无关），我们说一个假设函数集合$\mathcal{H}$能够打散集合$S$，如果$\mathcal{H}$中的某些$h$可以对集合$S$的任意标记组合$\{y^{(1)},...,y^{(d)}\}$都可以实现正确划分，即$h(x^{(i)}) = y^{(i)},i=1,...,d$，若最大能够打散集合的大小为$d$，则称假设函数集合$\mathcal{H}$的VC维为$d$。即$VC(\mathcal{H}) = d$。
让我们来举个例子：假设$\mathcal{H} = \{二维空间中的线性分类器集合\}$，集合$S$中的个数$d=3$（下图是集合$S$的一个分布）。

可以知道，在上图这种情况下，不管给这三个点如何标注（二分类，正负样本标注），线性分类器集合$\mathcal{H}$总能够将它们正确划分。

很有可能立马会有反问：当$d=3$时，集合$S$可以长成下左图模样，这个时候（如下右图）$\mathcal{H}$就不能将这三个点正确划分了。

实际上，这并不要紧。因为只要存在一个三个点的集合分布，不论以任何的标注方式，线性分类器集合$\mathcal{H}$都能够将其正确划分的话，我们就可以认为该集合$\mathcal{H}$能够打散的点的数目为3。
可以证明，上述集合$\mathcal{H} = \{二维空间中的线性分类器集合\}$对$d=4$的任何一个分布都无法打散，这种情况下可得$VC(\mathcal{H}) = 3$。将此结论进一步推广可以得到：如果$\mathcal{H}$是$n$维空间中的线性假设函数集合，那么$VC(\mathcal{H}) = n+1$。

现在，让我们写下学习理论中最为重要的结论：

对于假设函数集合$\mathcal{H}$，设$\mathcal{H}$的VC维$VC(\mathcal{H}) = d$，那么至少有$1-\delta$的概率，对于所有$h \in \mathcal{H}$，以下结论成立：

$$|\varepsilon(h) - \hat\varepsilon(h)| \leq O(\sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta}})$$
同样的，有关ERM解的生成风险的上界问题，我们至少有$1-\delta$的概率，以下结论（一致收敛性）成立：
$$\varepsilon(\hat h) \leq \varepsilon( h^*)+O(\sqrt{\frac{d}{m}log\frac{m}{d}+\frac{1}{m}log\frac{1}{\delta}})$$

从上面两个公式可以看出：当一个假设函数集合的VC维为有限的时候，随着样本数目的增加，训练误差与生成误差将会一直收敛。因此，我们不需要再理会假设函数集合的大小是否是有限还是无限，只需根据VC维即可得到其一致收敛定理。

和上一节课类似，我们可以在保持几个参数不变的前提下，得到剩余一个参数的不等式：
引理一：
为使得"$|\varepsilon(h) - \hat\varepsilon(h)| < \gamma$"对于集合$\mathcal{H}$中的所有$h$都至少以$1-\delta$的概率成立，样本数目m必须满足：

$$m = O_{\delta,\gamma}(d)$$
换句话说，要使模型“较好”的训练，需要的样本数要和假设集的VC维线性相关。而在大多数情况下，VC维的大小和模型的参数是线性相关的，所以，所需的样本数就大体上和模型的参数个数是线性相关的。

有学生提出："根据VC维理论，可根据具体模型的VC维来确定训练样本的个数，这是否可行？"回答是："因为VC维给出的界是非常宽松的，个人不建议那么做。"

SVM的VC维解释

由SVM部分描述可知，SVM使用核的概念将低维特征映射到高维特征（甚至是无限维）。又由引理一的解释描述，我们觉得此时的SVM应该有无限多个参数，那么VC维也接近无穷。那么想要获得较好训练效果的话，训练样本$m$的数目应该也接近无穷才对的。但是实际情况并不是这样，SVM只在原来的数据上就达到了比其他模型更好的效果。这是为什么呢？实际上，具有较大间隔的SVM一般都具有较小的VC维。
假设我们只考虑这样的$\mathcal{H}$集合，该集合内的所有$h$都具有较大的间隔（对于训练样本点）。我们规定：此时的最小间隔定义为$\rho$。如果我的所有训练样本点的二范数$||x^{(i)}||_2 \leq R$ ,那么集合$\mathcal{H}$的VC维可以表示为：

$$VC(\mathcal{H}) \leq \lceil \frac{R^2}{\rho} \rceil +1$$
这个结论的惊人之处在于SVM的VC维的上界并不依赖于训练样本特征的维度。也就是说，虽然你的样本特征处于无限维中，但如果只考虑具有较大间隔的分类器组成的假设函数集合$\mathcal{H}$，那么VC维就存在一个上界。

关于SVM：SVM会自动找到一个具有较小VC维的假设函数集合$\mathcal{H}$，这样可使得数据量变得相对充分，提高了模型的效果。

ERM的直观意义

之前各部分都是以ERM（经验风险最小化）为基础展开分析的，那么ERM的作用到底是什么呢？
回顾之前定义的经验风险的计算公式：

$$\hat \varepsilon(h) = \frac{1}{m}\sum_{i=1}^m \mathbf{1}\{h_{\theta}(x^{(i)}) \neq y^{(i)}\}$$
在这里，我们以单一训练样本为例，其误差函数为$\mathbf{1}\{h_{\theta}(x^{(i)}) \neq y^{(i)}\}$。当该样本标签$y=0$时，有：

很显然，这是一个非凸函数，使用机器学习的方法并不能对其进行很好地优化。因而产生了一些算法对误差函数进行凸性近似，以期待能够更好地优化。以Logistic回归和SVM为例，近似函数图像如下图：

Logistic回归采用的近似函数为Logistic Loss函数$log(1+exp(-y·h_{\theta}(x)))$，相比最原始的Loss函数，该Loss函数平滑了不少。关于Logistic Loss函数的我的个人理解可以戳这里。而SVM采用的则是这样形式的Loss函数：$max([1-y·h_{\theta}(x)],0)$，该Loss函数的图像也可直观看到，由两段组成。

虽然Logistic回归和SVM都不是直接地ERM算法，但都是基于ERM的近似而产生，因而可见ERM的一致性定理在实际应用中的威力。

模型选择

在前面将VC维的时候我们提到过偏差与方差的权衡问题。如果你的数据包含有二次特征，而你选择一次函数模型则会使得偏差bias过高；如果你选择8次函数模型则会使得方差variance过高。所以选择一个合适的模型非常重要。模型选择算法提供了一类方法可以自动地在偏差和方差之间权衡。

例：你正在考虑着多项式模型的阶次到底该选多少较好，有多种选择：

$$\theta_0 +\theta_1x \\ \theta_0 +\theta_1x +\theta_2x^2 \\ \theta_0 +\theta_1x +...+\theta_{10}x^{10}$$
那么，你该选择多项式模型中次数为多少呢？这是模型选择问题。如何选择SVM算法中的参数$C$也是模型选择问题。

介绍一种自动选择模型的方法：
设$\mathbf{M} = \{M_1,M_2,...,M_d\}$是一个有限的模型集合，我们在这一集合中进行模型选择。设$S$为数据集。保留交叉验证（hold-out cross validation）的做法如下：

1. 将训练集$S$随机切分为$S_{train}$(如70%)和$S_{cv}$(如30%)；
2. 在$S_{train}$上训练模型；
3. 在$S_{cv}$上进行测试；
4. 取测试误差最小的那个模型；

通过在非训练集上进行测试，我们得到了一个对模型较好的评估。在实际操作过程中，模型可在全部的数据集上进行训练，以利用更多的数据，达到更好的效果。
以上方法的劣势在于分出过多的数据用于测试。对于实际数据样本数较为稀少的问题来说，这是不能容忍的。因而产生了如下的改进方法，称为$k$重交叉验证：

1. 将数据集$S$随机平均分为$k$份；
2. 对于每一份来说：
   1).以该份作为测试集，其余作为训练集；
   2).在训练集上得到模型；
   3).在测试集上得到生成误差，这样对每一份数据都有一个预测结果；
3. 计算误差结果（取平均）；
4. 取误差最小的那一个模型。

通常$k=10$。此算法的缺点是计算量较大。