第十讲：交叉验证、特征选择¶

回顾一下上一讲的内容，如果有一个有限的假设类$\lvert\mathcal{H}\rvert=k$，对于给定的$\gamma,\delta$，要保证$\varepsilon(\hat h)\leq\displaystyle\operatorname*{min}_{h\in\mathcal{H}}\varepsilon(h)+2\gamma$成立，并且在事件“训练误差与泛化误差之差小于$\gamma$”的概率至少为$1-\delta$时，需要满足：

$$ \begin{align} m&\geq\frac{1}{2\gamma^2}\log\frac{2k}{\delta}\\ &=O\left(\frac{1}{\gamma^2}\log\frac{k}{\delta}\right) \end{align} $$

这是一个与样本复杂度相关的结论。现在我们想要将这一结论推广到无限假设类中。

4. 若$\mathcal{H}$是无限的¶

我们已经证明了一些在有限假设类下非常有用的理论，然而，包括“任意以实数为参数的假设函数”（如线性分类器）在内的很多的假设类实际上包含了无数个假设函数。我们能否将有限假设类下成立的结论推广到无限假设类中呢？

我们先抛出一个不严谨的论点，也许在某些方面不够“正确”，但它比较直观。之后，我们会给出一个更好且更普遍的结论。

假设我们要将上面关于样本复杂度的式子应用在逻辑回归中，此时我们的假设类是由线性判别边界构成的，所以$\mathcal{H}$是以$d$个实数作为参数（如果我用逻辑回归解决$n$个特征值的问题，则$d=n+1$，此时逻辑回归会找到一个以$n+1$个实数为参数的线性判别边界$g\left(\theta^Tx\right)$）。而我们都知道，计算机通常使用IEEE双精度浮点数（C语言中的double，$64$位）来近似实数，那么在这个逻辑回归的情况下，计算机需要$64d$个比特位（bits）来表示这些参数。那么对我们的假设类就有$k=\lvert\mathcal{H}\rvert=2^{64d}$个不同的假设函数。根据上一讲最后的结论，带入$O$表达式，为了保证样本复杂度中的条件$\varepsilon{\hat h}\leq\varepsilon{h^*}+2\gamma$的概率至少为$1-\delta$，就需要满足 $ m\geq O\left(\frac{1}{\gamma^2}\log\frac{2^{64d}}{\delta}\right) =O\left(\frac{d}{\gamma^2}\log\frac{1}{\delta}\right) =O_{\gamma,\delta}(d) $ （最后一个$O$记号的下标$\gamma,\delta$表明复杂度可能依赖于这两个隐藏参数）。从这里可以大概了解，所需训练样本的数量与模型参数的个数大约最多呈线性关系。

虽然使用$64$位浮点数来推断这个结论并不能完全令人信服，但是这个结论大体上是正确的。如果要保证经验风险最小化生成的假设与最好假设间泛化误差的差距不超过$2\gamma$，则$m$必须大于大$O$记号中的量级，如果我们尝试最小化训练误差，为了保证学习效果我们使用了含有$d$个参数的假设类，则所需要的训练样本的数量大致与我们假设类的参数数目呈线性关系，即$m$与$d$大致呈线性关系。

（到目前为止，这些结论并不能说明一个使用经验风险最小化的算法的价值。因此，虽然多数尝试最小化或估计训练误差的判别学习算法对参数个数$d$为线性复杂度，但这个结论并不是对所有判别学习算法有效。对很多非经验风险最小化使用良好的假设保证仍是热门研究方向。）

上面推导出的结论还有一个不那么令人满意的地方——它依赖参数化$\mathcal{H}$。虽然直观上不容易看出问题，我们将具有$n+1$个参数$\theta_0,\cdots,\theta_n$线性分类器所在的类写作$1\left\{\theta_0^T+\theta_1^Tx_1+\cdots+\theta_n^Tx_n\geq0\right\}$，我们也可以将其写作$h_{u,v}(x)=1\left\{\left(u_0^2-v_0^2\right)+\left(u_1^2-v_1^2\right)x_1+\cdots+\left(u_n^2-v_n^2\right)x_n\geq0\right\}$，此时有$2n+2$个参数。不过，这两个式子表达的是同一个假设类$\mathcal{H}$，即$n$维线性分类器的集合。

为了给出一个更严谨的推导，我们先定义一些新概念。

对于某个由点$x^{(i)}\in\mathcal{X}$构成的集合$S=\left\{x^{(1)},\cdots,x^{(d)}\right\}$（并不要求是训练集），如果$\mathcal{H}$可以实现$S$任意一种标记方式，即对于任意集合$\left\{y^{(1)},\cdots,y^{(d)}\right\}$，存在$h\in\mathcal{H}$能够使$h\left(x^{(i)}\right)=y^{(i)},\ i=1,\cdots,d$成立，我们就称$\mathcal{H}$分散了（shatters）$S$。

对于给定假设类$\mathcal{H}$，我们定义Vapnik-Chervonenkis维度（Vapnik-Chervonenkis dimension），写作$\mathrm{VC}(\mathcal{H})$，表示能够被$\mathcal{H}$分散的最大的集合。（如果$\mathcal{H}$可以分散任意大小的集合，则有$\mathrm{VC}(\mathcal{H})=\infty$）

举个例子，考虑下图中的点：

在两个维度上的（$h(x)=1\left\{\theta_0+\theta_1x_1+\theta_2x_2\geq0\right\}$）线性分类器的集合$\mathcal{H}$可以分散上面的点集吗？答案是肯定的。我们可以直接给出所有可能的八种分类标记的情况，而且对这个例子我们总是能够找到一个具有零训练误差的线性分类器（即完美分类）：

（对于上例的点集$S$，所有可能的分类情况都有对应的二维分类器将点分散）

此外，通过一系列计算能够证明，此假设类（即二维线性分类器）不可能分开任意含有$4$个点的集合（不论这四个点在$x_1,x_2$坐标系上如何排列，我们都无法找到一组能够将“四个点的所有可能的$x,o$的标记情况”分开的直线）。因此，$\mathcal{H}$可以分开的集合的元素总数为$3$，有$\mathrm{VC}(\mathcal{H})=3$。

值得注意的是，虽然$\mathcal{H}$的$\mathrm{VC}$维是$3$，但也存在分不开的布局。比如，如果三点共线（如下方左图所示），则存在二维线性分类器无法分开的标记情况（如下方右图所示）：

（因为已经存在某个$3$个点的集合可以被二维线性分类器分散，所以这并不影响二维线性分类器的$\mathrm{VC}$维为$3$。）

也就是说，从$\mathrm{VC}$维的定义有，为了证明$\mathrm{VC}(\mathcal{H})$至少是$d$，那么我们只需要找到一个大小为$d$的集合可以被$\mathcal{H}$散列即可。

定理，给定$\mathcal{H}$，令$d=\mathrm{VC}(\mathcal{H})$，在保证事件“训练误差与泛化误差在$\gamma$以内”的概率至少为$1-\delta$的条件下，对于$h\in\mathcal{H}$有：

$$ \left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\leq O\left(\sqrt{\frac{d}{m}\log\frac{m}{d}+\frac{1}{m}\log\frac{1}{\delta}}\right) $$

因此，在概率至少为$1-\delta$时可以得到：

$$ \varepsilon\left(\hat h\right)\leq\varepsilon\left(h^*\right)+O\left(\sqrt{\frac{d}{m}\log\frac{m}{d}+\frac{1}{m}\log\frac{1}{\delta}}\right) $$

换句话说，如果一个假设类具有有限的$\mathrm{VC}$维度，则当$m$越来越大时会产生一致收敛。同上一讲一样，我们可以从中得到一个使用$\varepsilon\left(h^*\right)$表示的$\varepsilon(h)$的界限。我们还能够得到下面的推论：

推论，对于$h\in\mathcal{H}$（由于$\varepsilon\left(\hat h\right)\leq\varepsilon\left(h^*\right)+2\gamma$），要保证$\left\lvert\varepsilon(h)-\hat\varepsilon(h)\right\rvert\leq\gamma$的概率至少为$1-\delta$，则必须满足$m=O_{\gamma,\delta}(d)$。

也就是说，要保证从$\mathcal{H}$中选取的假设能够“学的好”，所需的训练样本的个数与$\mathcal{H}$的$\mathrm{VC}$维数呈线性关系。这个结论也可以解释为，对于“大多数”假设类（我们假设”合理的“参数化），其$\mathrm{VC}$维与其参数个数呈大致的线性关系（其实这两者的大小通常差不多，比如使用维度为$n$逻辑回归作为线性分类器时，一共需要$n+1$个参数，而$n$维线性分类器的假设类的$\mathrm{VC}$维是$n+1$）。综合上面的各结论有，（对于一个尝试最小化训练误差）算法所需的训练样本的数量通常与假设类$\mathcal{H}$参数的个数呈大致上的线性关系。这也表明了样本复杂度的上下界都是由$\mathrm{VC}$维给出的。

补充一点别的知识：回忆前几讲中的支持向量机算法，我们知道SVM会使用核函数将输入属性投影在无限维的特征空间中。那么，看起来SVM算法的$\mathrm{VC}$维数是无穷。不过，具有较大间隔的线性分类器通常$\mathrm{VC}$维都不会太大。我们可以做一个非正式的简要解释。给定了一个点集，如果我们只考虑使用具有较大间隔的线性分类器分隔这些点，那么我们的假设类将只包含这些间隔较大的判别边界。现在假设这个间隔就是$\gamma$，那么假设类中将不会有太靠近某个点的判别边界（假设类中的假设函数到各点的距离都不会小于$\gamma$）。如果点集中的点都分布在一个半径为$R$的圆内$\left\lVert x^{(i)}\right\rVert\leq R$，那么对于可以分隔这个点集的分类器$h$（间隔至少为$\gamma$）所在的假设类$\mathcal{H}$，有$\mathrm{VC}(\mathcal{H})\leq\left\lceil\frac{R^2}{4\gamma^2}\right\rceil+1$（$\lceil x\rceil$表示对$x$向上取整）。关于这个结论的证明我们就不展开介绍了。通过这个结论我们可以知道，$\mathrm{VC}$维数的取值范围与输入特征的维数是没有关系的。也就是说，即使输入$x$来自无限维空间，但只要我们令分类器必须满足一个较大的间隔时，$\mathrm{VC}$维实际上是被限制在一个比较小的数字上。所以，如果给定SVM一个需要满足的间隔，SVM将自动找到一个具有较小$\mathrm{VC}$维的假设类，算法并不会发生过拟合的现象。

关于经验风险最小化，如果我们只看其中的一个样本$x$，对于假设函数$h_\theta(x)=g\left(\theta^Tx\right)$，那么指示函数$1\left\{h_\theta(x)\neq y\right\}$将会型为一个阶梯函数，假设我们拿到的是一个负样本$y=0$，那么如果$\theta^Tx\gt0$，也就是误分类，此时阶梯函数值为$1$，如果$\theta^Tx\leq0$，那么就是分类正确，此时阶梯函数值为$0$。我们所要做的就是找到一组$\theta$，能够使这个阶梯函数最小化，也就是能够正确分类训练样本$x$（即令指示函数为$0$）。而这个指示函数是一个非凸函数，使用线性分类器最小化训练误差是一个NP困难问题（中文，英文）。我们前面介绍的逻辑回归和支持向量机都是在使用凸近似逼近经验风险最小化这个NP困难问题。

第七部分：正则化及模型选择¶

有时，遇到一个问题，我们需要在几个不同的模型间取舍。比如，我们在使用多项回归模型$h_\theta(x)=g\left(\theta_0+\theta_1x+\theta_2x^2+\cdots+\theta_kx^k\right)$时，需要确定$k$到底取$1,2,\cdots10$中的那个值最为合适。那么，如何自动的让模型选择过程在偏差与方差间做出权衡？（原文使用”邪恶的双胞胎“来形容偏差与方差，可能使用”异卵双生“更合适）或者说，想要自动选择局部加权回归中的带宽参数$\tau$，或是希望自动确定$\mathscr{l}_1$正则化的SVM中的参数$C$（也就是SVM软边界中在间隔大小与惩罚力度之间做权衡的系数），我们应该如何去做呢？

为了更具体的描述问题，我们在本讲中均假设将要从有限的模型集合$\mathcal{M}=\left\{M_1,\cdots,M_d\right\}$中选取模型。比如说在第一个例子中，$M_i$就表示$i$阶多项回归模型。（推广到无限的$\mathcal{M}$也并不难。如果我们尝试从无限的模型集合中做出，使用带宽参数的例子$\tau\in\mathbb{R}^+$，我们就可以离散化$\tau$，然后令$M_i$为$\tau_i$的函数，再从中选择可能的$M_i$。一般的，本讲描述的算法可以看做是在模型空间中做优化选择，我们同样可以将这个选择过程应用于无限模型集合中。）再比如我们需要在SVM、神经网络和逻辑回归中做出选择，那么$\mathcal{M}$将包含这些模型。

1. 交叉验证（Cross validation）¶

像以前一样，假设有训练集$S$，从前面的经验风险最小化，我们可以得出一个关于模型选择的、乍看起来像个”算法“的步骤：

1. 用$S$训练每一个$M_i$，从而得到相应的假设函数$h_i$；
2. 选择训练误差最小的假设函数。

遗憾的是，这个”算法“并不能符合我们的预期。比如说用这个”算法“要从多项模型集合中选择阶数，我们知道对于多项回归模型，其阶数越高则对训练集的拟合越好，也就是训练误差越小。于是，该”算法“会始终选择阶数高、方差大的多项模型，而我们通常是不会使用这种模型的。

下面是一个比较好的算法，称为保留交叉验证（hold-out cross validation）（有时也称为简单交叉验证（simple cross validation））：

1. 随机把训练集$S$分为两部分，$S_\mathrm{train}$（假设有训练集$70%$的样本）和$S_\mathrm{cv}$（剩下$30%$的样本），而这个$S_\mathrm{cv}$称为保留交叉验证集；
2. 仅使用$S_\mathrm{train}$训练每一个模型$M_i$，进而得到相应的假设函数$h_i$；
3. 使用保留交叉验证集测试$h_i$，选出测试结果$\hat\varepsilon_{S_\mathrm{cv}}(h_i)$最小的假设函数。（$\hat\varepsilon_{S_\mathrm{cv}}(h_i)$表示$h_i$在训练集$S_\mathrm{cv}$上的训练误差。）

通过使用模型没有训练过的样本集$S_\mathrm{cv}$的测试，我们对$h_i$的泛化误差就有了更好的估计，从而选择一个估计泛化误差最小的假设函数。我摸一般使用$\frac{1}{4}$到$\frac{1}{3}$的样本做保留交叉验证集合，而本例中的$30%$是常见的选择。

有时第三步也会选择按照$\mathrm{arg}\displaystyle\operatorname*{min}_i\hat\varepsilon_{S_\mathrm{cv}}(h_i)$直接输出相应的模型$M_i$，然后在使用整个训练集$M$重新训练$M_i$。（这通常是个好点子，不过一些对初始化条件或数据的扰动非常敏感的算法来说，并不能使用这种方法。对这些算法来说，模型在$S_\mathrm{train}$上表现的很好并不能得出它在$S_\mathrm{cv}$上也会表现的很好。所以，对这种算法最好不要使用这个重新训练的步骤。）

不过，保留交叉验证会“浪费”掉那$30%$的训练样本。即使我们使用改进的第三步，用整个训练集重新训练模型，但对于前面的模型选择过程，我们仍旧每次只使用了$0.7m$个训练样本，而不是包含$m$个样本的训练集。这种算法在训练样本有冗余或容易得到时，是没有什么问题的，但对于训练样本稀缺的学习问题（比如一共只有$m=20$个样本），我们就需要更好的算法了。

下面的算法称作$k$重交叉验证（$k$-fold cross validation），该算法每次会保留更少的验证样本：

1. 随机把训练集$S$分为$k$个子集，每个子集有$\frac{m}{k}$个样本，记为$S_1,\cdots,S_k$；
2. 对每个模型$M_i$，我们执行下面的操作：

For $j=1,\cdots,k$ * 使用$S_1\cup\cdots\cup S_{j-1}\cup S_{j+1}\cup\cdots\cup S_k$（即使用除$S_j$以外的所以子集）训练$M_i$模型，从而得到假设$h_{ij}$； * 使用$S_j$测试$h_{ij}$，从而得到$\hat\varepsilon_{S_j}\left(h_{ij}\right)$。

$M_i$的泛化误差估计为$\hat\varepsilon_{S_j}\left(h_{ij}\right)$（对于每个$j$）的平均值。

3. 选择具有最小泛化误差的$M_i$，然后使用整个训练集$S$重新训练模型，这次得到的假设函数就是最终的输出。

我们通常使用$k=10$重交叉验证。在这个算法中，虽然每次保留的数据仅为$\frac{1}{k}$（已经比原始的保留交叉验证小了很多），但整个$k$重计算过程的代价将比原始的保留交叉验证大很多，因为我们需要训练每个模型$k$次。

尽管$k=10$是我们的常用选择，但是在那些样本非常珍贵的学习问题中，我们可能会选择极端的算法——令$k=m$，从而使得每次保留的样本达到最小。在这个算法中，我们将使用$m-1$个样本训练模型，用剩下的$1$个保留样本作为测试，模型的泛化误差将通过求这$m=k$次训练的平均误差得到。由于该算法仅保留一个样本用做测试，它也被称作留一交叉验证（leave-one-out cross validation）。

上面我们介绍了模型选择时交叉验证算法的几个版本，这些算法还有更简单的用途——评估单个模型或算法的效果。举个例子，如果我们实现了一个学习算法，现在想要评估它在应用中的效果（或者我们发明了一个新的学习算法，并想要在论文中说明它在不同测试集上的表现时），那么交叉验证就给出了一个合理的方法。

2. 特征选择¶

特征选择是模型选择的一个非常重要的情形，我们把它拿出来单独介绍。假设有一个特征值$n$非常大（比如$n\gg m$）的监督学习问题，但是我们怀疑这些特征中仅有一小部分与学习问题有关。即使对$n$个特征使用非常简单的线性分类器（比如第三讲介绍的感知算法），假设类的$\mathrm{VC}$维数也会为$O(n)$的量级，除非有对于$n$来说大小相当的训练集，否则模型就会存在过拟合问题。

在这种情况下，我就可以使用特征选择算法减小特征值的数量。对于包含$n$个特征值的集合，有$2^n$种特征值子集（因为$n$个特征值的中的每一个都包含或不包含在子集中这两种状态）。于是，我们可以把特征选择看做一种在$2^n$个可能的模型中做出选择的模型选择问题。不过，对于过大的$n$，直接训练$2^n$个模型并进行比较的代价非常大，所以我们通常使用某种启发式搜索过程来寻找好的特征值子集。下面的搜索过程称为向前搜索（forward search）：

1. 初始化$\mathcal{F}=\emptyset$；
2. 重复{

(a) 循环$i=1,\cdots,n$，如果$i\notin\mathcal{F}$，令$\mathcal{F}_i=\mathcal{F}\cup\{i\}$，然后使用某种交叉验证来估计特征$\mathcal{F}_i$。（即仅使用$\mathcal{F}_i$中的特征训练模型，然后估计模型的泛化误差。）

(b) 令$\mathcal{F}$为步骤(a)中找到的最佳特征子集。

} 3. 选择并输出上面的搜索过程得到的最佳的特征子集。

外层循环的终止条件可以设置为当$\mathcal{F}=\{1,2,\cdots,n\}$变为特征值全集时，也可以设置为当$\left\lvert\mathcal{F}\right\rvert$达到一个阈值时（也就是我们允许算法使用的特征值个数的上限）。

上面的算法称为封装特征选择（wrapper model feature selection），因为算法中对模型有一个“封装”的过程，算法会重复调用模型检查评估不同特征子集的效果。除了向前搜索之外，我们还可以使用别的搜索过程，比如向后搜索（backward search），该算法从全集$\mathcal{F}=\{1,\cdots,n\}$开始，然后每次删除一个特征值（同向前搜索评估每一个特征值的添加一样，向后搜索用相同的方法评估每一个特征值的删除），直到$\mathcal{F}=\emptyset$。

虽然封装特征选择算法通常都很奏效，但这个算法的计算量较大，因为它会不断的调用学习算法评估特征子集。完成整个向前搜索算法（算法在$\mathcal{F}=\{1,\cdots,n\}$时停止）需要调用学习算法大约$O\left(n^2\right)$次。（在计算资源能够满足要求的情况下可以使用这些算法，但是对于诸如文本分类的问题，特征值集合可以轻易达到几万个的数量级，如果再使用搜索算法就有些吃力了。）

（向前/向后搜索通常都不会找到最好的特征子集，实际上寻找最好的特征子集是一个NP困难问题。所以，相比较而言，这种搜索算法的效果通常都挺不错。）

下面介绍过滤特征选择（Filter feature selection）算法，该算法使用启发式且计算量更小的方法选择特征子集（不过，这种算法下相应的泛化误差可能会比搜索算法大）。算法的思路就是使用$S(i)$给特征$x_i$“打分”，看$x_i$能够为标记为$y$的类型提供多少信息，接下来就是简单的选择$k$个$S(i)$最高的特征值了。

“打分”函数$S(i)$的一种可能的定义：测量训练数据中$x_i$与$y$的相关度。该算法可能会使得我们选择的都是与标签$y$强相关的特征值。在实践中，我们通常选择能够表示$x_i$与$y$间的互信息（mutual information）$\mathrm{MI}\left(x_i,y\right)$的$S(i)$：

$$ \mathrm{MI}\left(x_i,y\right)=\sum_{x_i\in\{1,0\}}\sum_{y\in\{1,0\}}p\left(x_i,y\right)\log\frac{p\left(x_i,y\right)}{p\left(x_i\right)p(y)} $$

（上面的式子假设$x_i$和$y$都是二元取值的变量，而更加一般化的式子应该是计算取值域内所有变量的情况之和。）关于$p\left(x_i,y\right)$、$p\left(x_i\right)$和$p(y)$的概率可以从训练集的经验分布中求得。

为了直观的解释这个“打分”函数的作用，应注意到互信息也可以表示成KL散度（Kullback-Leibler divergence，这是信息论中的概念，中文，英文）：

$$ \mathrm{MI}\left(x_i,y\right)=\mathrm{KL}\left(p\left(x_i,y\right) \parallel p\left(x_i\right)p(y)\right) $$

在问题集3中有更多关于KL散度的信息，不过在这里，KL散度给出了衡量$p\left(x_i,y\right)$和$p\left(x_i\right)p(y)$间概率分布的差异程度的方法。如果$x_i$与$y$是独立随机变量，则有$p\left(x_i,y\right)=p\left(x_i\right)p(y)$，则这两个分布的KL散度为$0$。这与“$x_i$与$y$相互独立则$x_i$并不携带与$y$相关的信息”的观点一致。那么此时，$x_i$的得分$S(i)$就应该很小。相反，如果$x_i$携带的信息与$y$高度相关，那它们间的互信息$\mathrm{MI}\left(x_i,y\right)$将会非常大。

现在就有了一个关于特征值$S(i)$的排序，那么我们该选择前多少个特征值呢？其中一个“业界标准方法”就是使用交叉验证来判断究竟该选择多少个特征值。比如当我们使用朴素贝叶斯算法做文本分类时，会遇到词汇表条目数$n$过大的问题，而使用这个方法通常能够非常有效的提高分类器准确性。