6.1 学习

所谓“学习算法” (Learning algorithms)，指的是能够解决不同领域的问题而不需要太多领域专门知识的通用工具。学习算法的任务是对一些对象进行分类。比如，如果需要一个算法来区分不同的机动车，比如轿车、卡车，以及拖车。如果使用机动车的领域知识，可以先构造一些特征，比如轮子个数，引擎功率，门的个数，车辆的长度，等等。如果有 \(d\) 个特征，则每个对象可以表示为一个 \(d\) 维向量，称为特征向量 (译者注：注意不要与 eigenvector 搞混)，向量的每个分量给出一个特征的取值。目标是要设计一个“预测”算法，使得当给定一个向量后，能够正确预测车辆的类型。早期基于规则的方法使用领域知识来发展出一套规则，比如像这样：如果轮子有四个，则是轿车。预测通过查验规则得到。

如果采用“学习”的方法，则规则开发的过程不再是针对特定领域，而是自动的。在学习阶段，领域专门知识被用来决定特征的选取，把问题变成对特征向量的分类。近一步，领域专家被请来对一些特征向量进行分类，这些向量被称为训练样例。这些训练样例会被作为学习算法的输入。专家的作用到此为止。

学习算法把加标签的训练样本作为输入，并且发展出一套规则，当这套规则应用到训练样本时，会给出正确答案。在机动车的例子中，学习算法完全不需要知道汽车领域的知识。它只是对一些 \(d\) 维向量进行处理，然后生成把 \(d\) 维空间划分成一些区域的规则，每个区域对应了轿车、卡车等。

学习算法的任务是要让规则能正确给出训练样本的分类。当然，对于目前这个有限的任务，它可以把规则设成“对每个训练样本，使用专家提供的标签”。但是，我们这里强调奥卡姆剃刀原理，意思是算法给出的规则必须比所有训练样本组成的表格简洁。这就像发展一个科学理论来解释大量观测一样，理论必须比简单罗列所有观测要简洁。

一般的任务则不只是让规则仅对训练样本正确，而且要对未知的样本正确。直观地讲，如果分类器是使用足够多的训练样本做出，则很可能它也会适用于全体样本。我们会看到，Vapnik-Chervonenkis 维数 (VC 维数) 理论证实了这个直觉。就目前而言，我们的目标是获得一个简洁的规则集合来对训练样本正确分类。这就是“学习”。

本章中我们假定所有标签都是二值的。不难看出分成多个类的问题可以约化为二值分类问题。把车子分类成轿车与非轿车，拖车与非拖车，等等，足以给出车子的类型。所以我们假定标签只有 \(+1\) 和 \(-1\)。

在 \(d\) 维空间中，最简单的规则是对平面上一条直线的推广，也就是半空间。特征的加权和是否超过了一个阈值？这样的规则可以被想象为一个限门，特征取值作为输入，计算加权和，然后基于加权和是否超过阈值来输出是或否。也可以看看交互连接的限门网络，被称为神经网络。限门有时被称为感知器，因为对人类感知的一个模型是认为感知来自大脑里的神经网络。

6.2 线性分离器，感知器算法，边际

对半空间或者说线性分离器的学习包含了 \(d\) 维空间的 \(n\) 个有标记的样本，\(\V{a}_1, \V{a}_2, \ldots, \V{a}_n\)。任务是寻找一个 \(d\) 维向量 \(\V{w}\)，以及阈值 \(b\) 使得 \begin{equation} \begin{split} \V{w}^\trsps \V{a}_i > b, \text{对所有标记为} {+1} 的 \V{a}_i,\\ \V{w}^\trsps \V{a}_i < b, \text{对所有标记为} {-1} 的 \V{a}_i. \end{split} \end{equation} 满足上面不等式的 \((\V{w},b)\) 组成的一对叫做线性分离器。

上面的形式是 \(\V{w}\) 和 \(b\) 的线性规划问题，可用通常的线性规划算法求解。线性规划可在多项式时间内求解，但一个更简单的算法是感知器学习算法，并且在可行解 \(\V{w}\) 存在较多余裕或者说边际时更快，虽然在一般情况下不是多项式时间的。

为了方便，我们引入 \(\hat{\V{a}}_i = (\V{a}_i, 1)\) 以及 \(\hat{\V{w}} = (\V{w}, -b)\)。假定 \(l_i\) 是 \(\V{a}_i\) 上的标签，则前述不等式可写为 \begin{equation} (\hat{\V{w}}^\trsps \hat{\V{a}}_i) l_i > 0 \quad 1\le i\le n \end{equation} 由于右边是 0，我们可以让 \(\norm{\hat{\V{a}}_i} = 1\)。添加额外的坐标让维数增加 1，但现在分离器过原点。为了简化记号，下面我们省略符号上面的帽子。

感知器学习算法

感知器学习算法简单而优美。我们希望寻找 \(\V{w}\) 使得 \begin{equation} (\V{w}^\trsps \V{a}_i) l_i > 0 \quad 1\le i\le n \end{equation} 此处 \(\norm{\V{a}_i}=1\)。从 \(\V{w} = l_1\V{a}_1\) 开始，选取任何满足 \((\V{w}^\trsps \V{a}_i)l_i\le0\) 的 \(\V{a}_i\)，然后把 \(\V{w}\) 替换为 \(\V{w} + l_i\V{a}_i\)。不断重复直到对每个 \(i\) 都满足 \((\V{w}^\trsps \V{a}_i) l_i > 0\)。

这个算法背后的直觉是，每次向 \(\V{w}\) 添加 \(\V{a}_i l_i\) 都让新的 \((\V{w}^\trsps \V{a}_i) l_i\) 增加了 1。对于当前的 \(\V{a}_i\) 来说这是好事，但可能对别的 \(\V{a}_j\) 不好。下面证明这个简单的过程能快速给出一个解 \(\V{w}\)，前提是解存在且拥有好的边际。

\(\def{6.1}\) 对于上述问题的一个解 \(\V{w}\)，且对所有样本都有 \(\norm{\V{a}_i}＝1\)，边际定义为超曲面 \(\{\V{x}|\V{w}^\trsps \V{x}=0\}\) 到所有 \(\V{a}_i\) 的最小距离，即 \(\argmin_i\frac{(\V{w}^\trsps\V{a}_i)l_i}{\norm{\V{w}}}\)。

如果我们不曾约定所有 \(\norm{\V{a}_i}=1\)，则可以通过放大 \(\V{a}_i\) 来人为的提高边际。如果我们不曾在边际的定义中除以 \(\norm{\V{w}}\)，则我们也可以通过放大 \(\V{w}\) 来提高边际。有趣的事情是，算法所需的步骤数只取决于任何解所能达到的最佳边际，而与 \(n\) 和 \(d\) 无关。在实践中，感知器学习算法工作得不错。

\(\theorem{6.1}\) 假定前述问题存在解 \(\V{w}^\ast\)，对应的边际为 \(\delta > 0\)。则感知器算法可以在至多 \(\frac{1}{\delta^2}-1\) 次迭代后得到解 \(\V{w}\) 使得对所有 \(i\) 满足 \((\V{w}^\trsps \V{a}_i)l_i>0\)。

证明：令 \(\norm{\V{w}^\ast}=1\)。考虑当前的 \(\V{w}\) 与 \(\V{w}^\ast\) 的夹角的余弦，也就是 \(\frac{\V{w}^\trsps\V{w}^\ast}{\norm{\V{w}}}\)。在算法执行的每一步，分母至少增加 \(\delta\)，因为 \begin{equation} (\V{w} + \V{a}_i l_i)^\trsps \V{w}^\ast = \V{w}^\trsps \V{w}^\ast + l_i \V{a}_i^\ast\V{w}^\ast \ge \V{w}^\trsps\V{w}^\ast + \delta. \end{equation} 而分母至多增加 1，因为 \begin{equation} \norm{\V{w}+\V{a}_i l_i}^2 = (\V{w} + \V{a}_il_i)^\trsps (\V{w} + \V{a}_il_i) = \norm{\V{w}}^2 + 2(\V{w}^\trsps\V{a}_i)l_i + \norm{\V{a}_i}^2l_i^2 \le \norm{\V{w}}^2 + 1. \end{equation} 注意到这是因为这个算法只对满足 \((\V{w}^\trsps \V{a}_i)l_i\le 0\) 的 \(i\) 执行操作。

经过 \(t\) 次迭代后，\(\V{w}^\trsps\V{w}^\ast \ge (t+1)\delta\)，因为最开始 \(\V{w}^\trsps\V{w}^\ast = l_1(\V{a}_1^\trsps \V{w}^\ast) \ge \delta\) 而每一步都增加了至少 \(\delta\)。类似地，\(t\) 次迭代后 \(\norm{\V{w}}^2 \le t+1\)，因为一开始是 1，而每一步最多增加 1。于是 \(\V{w}\) 和 \(\V{w}^\ast\) 之间的夹角余弦至少是 \(\frac{(t+1)\delta}{\sqrt{t+1}}\)；另外，余弦不可能超过 1，所以 \begin{equation} \sqrt{t+1}\delta\le 1 \quad \Rightarrow\quad t\le\frac{1}{\delta^2}-1. \end{equation} 换句话说，这个算法必须在 \(\frac{1}{\delta^2}-1\) 步内停止，并且在停止的时候 \((\V{w}^\trsps\V{a}_i)l_i>0\) 对所有 \(i\) 成立。证毕。

关于存在边际至少为 \(\delta\) 的分离器的假设有多强？我们暂时假定 \(\V{a}_i\) 是从单位超球面上均匀取出。在第二章中我们看到，对于任何通过原点的固定超平面，单位超球体的多数质量位于这个超平面的 \(O(1/\sqrt{d})\) 距离内。所以，一个固定超平面的边际超过 \(c/\sqrt{d}\) 的概率较小。但这不意味着不存在具有较高边际的超平面。按照并集上界，我们只能说存在拥有较高边际的超平面的几率等于单个超平面具有大边际的几率乘以超平面的个数，而后者是无穷。稍后我们会看到，使用基于 VC 维数的论证，当样本是从超球面随机选出时，存在拥有大边际的超平面的几率很小。因此，关于大边际分离器的存在性对于简单的随机模型来说是不合适的。但从直觉上讲，如果需要学习的东西不是很难，比如是否某个东西是轿车，那么，当模型中存在足够多的特征时，不会有很多“近似轿车”或者“近似非轿车”与真正的轿车混淆。在这样的现实问题中，均匀密度分布不是一个合理的假定。这样，大边际分离器就很有可能存在，并且前面的定理成立。

下一个问题是，边际可以有多小。假定样本 \(\V{a}_1,\ldots,\V{a}_n\) 是些拥有 \(d\) 个坐标的矢量，并且每个坐标取值为 0 或 1，而标记规则是： 如果第一个取值为 1 的坐标序号是奇数，标记为 1；如果第一个取值为 1 的坐标序号是偶数，标记为 \(-1\)。 这个规则可以表达为 \begin{equation} (a_{i1},a_{i2},\ldots,a_{id}) (1,-\frac{1}{2},\frac{1}{4},-\frac{1}{8},\ldots)^\trsps > 0. \end{equation} 对于这个例子，边际可以是指数级的小。比如，对于前 \(d/10\) 个坐标都是 0 的样本，边际是 \(O(2^{-d/10})\)。

边际的最大化

本节提供一种算法来寻找最大边际分离器。边际的定义是，对于问题 \((\V{w}^\trsps\V{a}_i)l_i>0,\ 1\le i\le n\) 的一个解 \(\V{w}\) (这里 \(\norm{\V{a}_i}=1\))，\(\delta \equiv \min_i \frac{l_i (\V{w}^\trsps\V{a}_i)}{\norm{\V{w}}}\)。由于这不是 \(\V{w}\) 的凹函数，计算起来不容易。

凸优化技术一般只适用于处理凸集上凹函数的最大化和凸函数的最小化。但是，通过修改权重矢量，可以把优化目标函数变成凹函数。注意到 \begin{equation} l_i \left(\frac{\V{w}^\trsps\V{a}_i}{\norm{\V{w}}\delta}\right) \ge 1 \end{equation} 对每个 \(\V{a}_i\) 成立。令 \(\V{v} = \frac{\V{w}}{\delta\norm{\V{w}}}\) 为修正后的权重矢量。边际被归一化到 1。最大化 \(\delta\) 等价于最小化 \(\norm{\V{v}}\)。于是优化问题变成 \begin{equation} \min \norm{\V{v}}\ \text{subject to}\ l_i(\V{v}^\trsps\V{a}_i) \ge 1, \forall i. \end{equation} 尽管 \(\norm{\V{v}}\) 是 \(\V{v}\) 的坐标的凸函数，最好还是对 \(\norm{\V{v}}^2\) 进行优化，因为后者可微。于是我们可以把问题重新表述为

最大边际问题：

\begin{equation} \min\ \norm{\V{v}}^2\ \text{subject to}\ l_i(\V{v}^\trsps\V{a}_i)\ge 1. \end{equation} 对这个凸优化问题已有许多研究，有的算法利用了这个问题的特殊结构，因此比一般的凸优化算法效率高。这里我们不讨论这些改进。这个问题的最优解 \(\V{v}\) 拥有如下性质。令 \(V\) 表示让等式 \(l_i(\V{v}^\trsps\V{a}_i)=1\) 成立的那些 \(\V{a}_i\) 张成的空间。我们断言，\(\V{v}\) 在 \(V\) 中。否则 \(\V{v}\) 有垂直于 \(V\) 的分量，把这个分量减小一个无穷小量不会影响这个等式的成立，但会减小 \(\norm{\V{v}}\) 的值，这便与最优性矛盾了。如果 \(V\) 是 \(d\) 维的，则存在 \(d\) 个独立样本使得 \(l_i(\V{v}^\trsps \V{a}_i)=1\) 成立。这 \(d\) 个方程于是拥有唯一解，而 \(\V{v}\) 必定就是那个解。这些样本被称为支持向量，它们唯一确定了最大边际分离器。

对多数样本给出正确分类的线性分离器

对某些线性分离器而言有可能少部分样本被错误分类。回到起初的定义，我们可以问，是否存在 \(\V{w}\) 使得至少那 \(n\) 个不等式里的 \((1-\epsilon)n\) 都被满足。可惜，这个问题是 NP 困难的，并且没有好的算法来解决。思考这件事的一个好办法是，对于每个错误归类的样本，我们承受一份损失，而我们希望最小化这个损失。但这个损失函数不是连续的，而是从 0 到 1 的突跳。但是，借助一个更好的损失函数可以解决这个问题。一个可能性是引入松弛变量 \(y_i,\ i=1,2,\ldots,n\)，这里 \(y_i\) 衡量样本 \(\V{a}_i\) 被错误划分的程度。然后我们把松弛变量加入目标函数 \begin{equation} \begin{split} &\min\ \normtwo{\V{v}} + c\sum_{i=1}^n y_i \\ &\text{subject to}\ \left. \begin{array}{l} (\V{v}^\trsps\V{a}_i)l_i \ge 1 - y_i \\ y_i\ge 0 \end{array} \right\} i = 1,2,\ldots,n \end{split} \end{equation} 如何设置 \(y_i\)? 可以采用 \(y_i = \max(0, 1-l_i(\V{v}^\trsps\V{a}_i))\)，这样 \(y_i\) 相当于对不等式违背的程度。因此，目标函数试图最小化总的违背程度以及边际的倒数的组合。容易看出，这等价于在相同的约束下最小化 \begin{equation} \normtwo{\V{v}} + c\sum_{i} \left(1-l_i(\V{v}^\trsps\V{a}_i)\right)^+, \end{equation} 其中第二项是违背程度之和。(译者注：可以把 \(\normtwo{\vv}\) 看成是最小化误差平方和时使用的正则项。)

6.3 非线性分离器，支持向量机，以及核

有些问题不存在线性分离器，但存在非线性分离器。比如，有可能存在一个多项式 \(p(\cdot)\) 使得 \(p(\V{a}_i)>1\) 对所有标记为 \(+1\) 的样本成立，而 \(p(\V{a}_i)<1\) 对所有标记为 \(-1\) 的样本成立。一个简单的例子是，考虑一个以原点为中心的单位正方形，被分为四份，其中右上和左下被标记为 \(+1\)，而右下和左上被标记为 \(-1\)。对此，\(x_1x_2>0\) 对所有 \(+1\) 样本成立，而 \(x_1x_2<0\) 对所有 \(-1\) 样本成立。于是，多项式 \(p(\cdot) = x_1x_2\) 分离了这些区域。更复杂的例子是棋盘那样交替 \(+1\) 和 \(-1\) 的模式。

若我们知道存在次数至多为 \(D\) 的多项式 \(p\) 使得一个样本 \(\V{a}\) 当且仅当 \(p(\V{a})>0\) 时被标记为 \(+1\)，则问题变成，如何寻找这样的多项式。注意到，任何 \(d\) 元整数组 \((i_1,i_2,\ldots,i_d)\) 只要满足 \(i_1+i_2+\cdots+i_d\le D\) 都决定了一个单项式 \(x_1^{i_1}x_2^{i_2}\cdots x_d^{i_d}\)。所以，多项式 \(p\) 中的单项式个数至多为把 \(d-1\) 个分隔物放入 \(D+d-1\) 个位置中的方法数，而答案是 \(\binom{D+d-1}{d-1}\le (D+d-1)^{d-1}\) (译者注：由于 \(\le\) 的存在，貌似正确答案应该是 \(\sum_{k=0}^D\binom{k+d-1}{d-1}\))。令 \(m=(D+d-1)^{d-1}\) 表示多项式个数的上限。

通过把单项式的系数看成未知数，我们可以构造一个 \(m\) 个变量的线性规划问题，对应的解给出要求的单项式。事实上，假定多项式为 \begin{equation} p(x_1,x_2,\ldots,x_d) = \sum_{\substack{i_1,i_2,\ldots,i_d\\ i_1+i_2+\cdots+i_d\le D}} w_{i_1,i_2,\ldots,i_d}x_1^{i_1}x_2^{i_2}\cdots x_d^{i_d}, \end{equation} 则不等式 \(p(\V{a}_i)>0\) 只是一个关于 \(w_{i_1,i_2,\ldots,i_d}\) 的线性不等式。但是，指数量级的变量个数使得即便在 \(D\) 不大的情形都失去实用价值。无论如何，这个方法理论上有些用处，它相当于把 \(d\) 维空间的样本点嵌入到 \(m\) 维空间了，使得对每个其和至多为 \(D\) 的 \((i_1,i_2,\ldots,i_d)\) 组合，都对应一个坐标，除了 \((0,0,\ldots,0)\) 之外；相应的坐标是 \(x_1^{i_1}x_2^{i_2}\cdot x_d^{i_d}\)。把这个嵌入称为 \(\varphI(\xx)\)。当 \(d=D=2\)，\(\varphI(\xx) = (x_1, x_2, x_1^2, x_2^2, x_1x_2)\)。我们需要找到 \(m\) 维矢量 \(\ww\) 使得 \(\ww\) 与 \(\varphI(\aa_i)\) 的内积当标签为 \(+1\) 时为正，标签为 \(-1\) 时为负。注意到，\(\ww\) 未必可以表达为 \(d\) 维空间某向量的 \(\varphI\) 嵌入。

与其寻找一个普通的 \(\ww\)，我们要寻找最大化边际的 \(\ww\)。相应的规划问题可以写为 \begin{equation} \min\ \normtwo{\ww}\ \text{subject to}\ \left(\ww^\trsps\varphI(\aa_i)\right)l_i \ge 1,\ \text{for all}\ i. \end{equation} 主要的问题是，我们能否避免显式计算嵌入 \(\varphI\) 和矢量 \(\ww\)。实际上我们只需要隐式使用它们。这是基于一个简单但关键的观察，那就是，上述凸规划问题的任何最优解 \(\ww\) 都是 \(\varphI(\aa_i)\) 的线性组合。如果 \(\ww = \sum_i y_i\varphI(\aa_i)\)，那么 \(\ww^\trsps \varphI(\aa_j)\) 可以在不知道 \(\varphI(\aa_i)\) 而只知道 \(\varphI(\aa_i)^\trsps\varphI(\aa_j)\) 的情况下计算出。

\(\lemma{6.2}\) 上述凸规划的任意最优解 \(\ww\) 都是 \(\varphI(\aa_i)\) 的线性组合。

证明：否则的话，\(\ww\) 有垂直于所有 \(\varphI(\aa_i)\) 的分量。去掉这个分量不会影响不等式的成立，但会减小 \(\normtwo{\ww}\)，与最优性矛盾。证毕。

现在，令 \(\ww = \sum_i y_i \varphI(\aa_i)\)，这里 \(y_i\) 都是实数。注意到 \begin{equation} \normtwo{\ww} = \sum_{i,j}y_iy_j\varphI(\aa_i)^\trsps\varphI(\aa_j), \end{equation} 于是凸规划可以重新表述为 \begin{equation} \begin{split} &\min\ \sum_{i,j}y_iy_j\varphI(\aa_i)^\trsps\varphI(\aa_j), \\ &\text{subject to}\ l_i\left(\sum_j y_j\varphI(\aa_j)^\trsps\varphI(\aa_i)\right) \ge 1\ \forall i. \end{split} \end{equation} 重要的是注意到 \(\varphI\) 本身是不需要的，只需要 \(\varphI(\aa_i)\) 之间的内积。核矩阵 \(K\) 定义为 \begin{equation} k_{ij} = \varphI(\aa_i)^\trsps\varphI(\aa_j). \end{equation} 于是凸规划问题可以写为 \begin{equation} \min\ \sum_{i,j} y_iy_j k_{ij}\ \text{subject to}\ l_i\sum_j k_{ij}y_j \ge 1. \end{equation} 这个凸规划被称为支持向量机 (support vector machine; SVM)，尽管它并不是什么机器。\(K\) 的优势在于，它只有 \(n^2\) 个数，而不是 \(O(d^D)\) 个。我们不需要通过 \(\aa_i\) 计算 \(\varphI(\aa_i)\)，而只需要知道如何从 \(\aa_i\) 得到 \(K\)。相应的计算通常用封闭形式给出。比如，“高斯核”由下面式子给出 \begin{equation} k_{ij} = e^{-c\norm{\aa_i-\aa_j}}. \end{equation} 稍后我们证明这的确是个核函数。

首先面临的问题是，给定一个矩阵 \(K\)，比如上面那个高斯核，我们怎么知道它是来自通过嵌入 \(\varphI\) 的两两内积得到的？这通过下面的引理给出。

\(\lemma{6.3}\) \(K\) 是一个核矩阵当且仅当它是个半正定矩阵。

证明：若 \(K\) 是半正定矩阵，则可表示为 \(K = B B^\trsps\)。定义 \(\varphI(\aa_i)\) 为 \(B\) 的第 \(i\) 行，则 \(k_{ij} = \varphI(\aa_i)^\trsps\varphI(\aa_j)\)。反过来也是明显的。证毕。

注意到，函数 \(\sum_{i,j} y_iy_j k_{ij} = y^\trsps K y\) 当且仅当 \(K\) 为半正定时是凸函数。于是支持向量机问题是凸规划问题。可以使用任何半正定矩阵作为核矩阵。

这里给出一个核矩阵的重要例子。定义 \(k_{ij} = (\aa_i^\trsps\aa_j)^p\)，这里 \(p\) 是个正整数。通过直接计算可知 \(K\) 是正定矩阵。

由此得知，对于矢量集合 \(\aa_1, \aa_2,\ldots,\aa_n\)，以及任何非负常数 \(c_1,c_2,\ldots\)，拥有绝对收敛级数展开的矩阵 \(k_{ij} = \sum_{p=0}^\infty c_p\left(\aa_i^\trsps\aa_j\right)^p\) 是正定矩阵。

\(\lemma{6.4}\) 对于矢量集合 \(\aa_1, \aa_2,\ldots,\aa_n\)，由 \(k_{ij} = e^{-\normtwo{\aa_i-\aa_j}/(2\sigma^2)}\) 给出的矩阵对于任何 \(\sigma\) 是半正定的。

证明：\(e^{-\normtwo{\aa_i-\aa_j}/(2\sigma^2)} = e^{-\normtwo{\aa_i}/2\sigma^2}e^{-\normtwo{\aa_j}/2\sigma^2} e^{\aa_i^\trsps\aa_j/\sigma^2} = e^{-\normtwo{\aa_i}/2\sigma^2}e^{-\normtwo{\aa_j}/2\sigma^2} \sum_{t=0}^\infty \left(\frac{(\aa_i^\trsps\aa_j)^t}{t! \sigma^{2t}}\right).\) 矩阵 \(l_{ij} = \sum_{t=0}^\infty \left(\frac{(\aa_i^\trsps\aa_j)^t}{t! \sigma^{2t}}\right)\) 是半正定的，所以 \(K\) 也是。

例子：(高斯核的应用) 考虑下述情形：样本位于平面上两条互相缠绕的曲线上，一条对应的标签是 \(+1\)，另一条对应 \(-1\)。假设样本在每条曲线上的间隔为 \(\delta\)，而两条曲线之间的最小距离是 \(\Delta \gg \delta\)。很明显，不存在一条直线能区分这两类。由于两条曲线互相缠绕，直觉上讲，任何能区分两者的多项式必定次数很高。我们来考虑高斯核。对于同一条曲线上的点，相邻点对应 \(k_{ij}\approx 1\)，而对其它点 \(k_{ij}\approx 0\)。对样本点重新排序，第一条曲线的在前面，第二条的在后面，则 \(K\) 具有块对角形式 \[ K = \left(\begin{array}{cc} K_1 & 0 \\ 0 & K_2\end{array}\right), \] 并且对角元素为 1，然后随着与对角线的距离指数衰减为 0。

这个 SVM 实质上具有下述形式 \begin{equation} \begin{split} &\min\ \V{y}_1^\trsps K_1 \V{y}_1 + \V{y}_2^\trsps K_2 \V{y}_2\\ &\text{subject to}\ K_1\V{y}_1 \ge 1\ \text{and}\ K_2\V{y}_2 \le -1. \end{split} \end{equation} 这样就分成了两个规划问题，一个针对 \(\V{y}_1\)，一个针对 \(\V{y}_2\)。从 \(K_1=K_2\) 可知，\(\V{y}_2 = -\V{y}_1\)。进一步，由于每条曲线的结构除了尾端之外基本没什么变化，\(\V{y}_1\) 的各分量的取值会近乎相等，而\(\V{y}_2\) 也一样。所以，\(\V{y}_1\) 的分量全是 \(1\)，而 \(\V{y}_2\) 的分量全是 \(-1\)。令 \(l_i=\pm1\) 为标签，则 \(y_i\) 的值提供了一个很好的简单分类器，也就是 \(l_iy_i>1\)。 (译者注：对训练样本得出 \(y_j\) 之后，当新来一个样本 \(\aa_i\)，可通过核函数算出 \(k_{ij}\)，这里 \(j\) 是针对训练样本的下标；然后基于从训练样本得出的 \(y_j\) 可计算 \(\sum_j k_{ij} y_j\)，根据这个数大于 \(1\) 还是小于 \(-1\) 即可分类。比如，如果新来的点属于 \(+1\) 类，那么 \(k_{ij}\) 仅在那些离它最近的点上趋近 \(1\)，而在其它点上趋近 \(0\)；而离它近的那些点对应的 \(y_j\) 为 \(+1\)，所以新来的点也应该被归类于 \(+1\)。)

6.4 强弱学习 － Boosting

一个强学习者指的是一个以 \(n\) 个有标记的样本作为输入并且产生出正确标记每个给定样本的分类器的算法。由于学习者获得了给定样本的标签并且只需要对给定样本负责，这看起来是个平凡的任务。只需要把样本和标签保存在一个表里面不就行了？按照奥卡姆剃刀原则，学习者产生的分类器应该比这样的表格精练得多。学习者需要的时间，以及分类器给出输出的长度和复杂度都是我们衡量学习者的参数。目前我们考虑另外一个方面。“强”这个词指的是分类器必须正确标记所有的样本；不允许任何错误。

弱学习者则允许犯错，只需要对严格多数 (\(\frac{1}{2}+\gamma\), \(\gamma>0\)) 的样本正确分类就行了。这看起来很弱。但通过对弱学习稍稍推广，并且使用一种叫做“boosting”的技术，可以通过弱学习达成强学习。

\(\def{6.2}\) (弱学习者) 令 \(U = \{\aa_1, \aa_2, \ldots, \aa_n\}\) 是 \(n\) 个有标记的样本。一个弱学习者指的是一个算法，给定这些样本、标签、以及对应于每个样本 \(\aa_i\) 的权重 \(w_i\) 后，这种算法能给出一个分类器，这个分类器能正确标记样本的一个子集，要求这个子集对应的权重至少为 \((\frac{1}{2} + \gamma)\sum_{i=1}^n w_i\)。

使用被称为 boosting 的方法，可以调用 \(O(\log n)\) 次弱学习者来构建一个强学习者。Boosting 使用了一个直观洞察，那就是，如果一个样本被错误分类，那么应该对它关注更多。

Boosting 算法

  • 第一次调用弱学习者，其中所有 \(w_i\) 设为 \(1\)。
  • 在时间 \(t+1\)，把上一次错误分类的样本的权重乘以 \(1+\varepsilon\)。其它权重保持不变。调用弱学习者。
  • \(T\) 步之后，停止并且输出下面的分类器：
    • 通过对弱学习者的多数投票来给出对 \(\{\aa_1, \aa_2, \ldots, \aa_n\}\) 的标签。假定 \(T\) 是奇数，则不会出现平局的情况。
假设 \(m\) 是最后分类器弄错的样本个数。这 \(m\) 个样本里的每一个至少被弄错 \(T/2\) 次，所以每个的权重至少为 \((1+\varepsilon)^{T/2}\)。也就是说总的权重至少为 \(m(1+\varepsilon)^{T/2}\)。另一方面，在时刻 \(t+1\)，只有那些在 \(t\) 时刻被错误分类的样本的权重被提高了。按照弱学习的性质，\(t\) 时刻被错误分类的样本的总权重至多为总权重的 \(f=(\frac{1}{2}-\gamma)\) 这么大个比例。令 \(\text{weight}(t)\) 表示 \(t\) 时刻的总权重，则 \begin{equation} \begin{split} \text{weight}(t+1) &\le \left[(1+\varepsilon) f + 1-f\right] \times \text{weight}(t) \\ &= (1+\varepsilon f)\times\text{weight}(t) \\ &\le \left(1 + \frac{\varepsilon}{2} - \gamma\varepsilon\right) \times \text{weight}(t). \end{split} \end{equation} 由于 \(\text{weight}(0) = n\)， \begin{equation} m (1+\varepsilon)^{T/2} \le \text{Total weight at end} \le n \left(1+\frac{\varepsilon}{2}-\gamma\varepsilon\right)^T. \end{equation} 两边取对数 \begin{equation} \ln m + \frac{T}{2}\ln(1+\varepsilon) \le \ln n + T \ln\left(1+\frac{\varepsilon}{2}-\gamma\varepsilon\right). \end{equation} 令 \(\varepsilon\) (错误分类的样本提权的比例) 取很小的值，比如 0.01，则在一阶近似下，\(\ln m \le \ln n - T\gamma\varepsilon\)。令 \(T = (1 + \ln n)/\gamma\varepsilon\)，则 \(\ln m \le -1\)，也就是 \(m \le \frac{1}{e}\)。于是，错误分类的样本数小于 1，因此只能是零。

6.5 用于预测所需的样本数：VC 维数

训练与预测

到目前为止，我们只谈论了训练样本以及构建对它们正确分类的分类器的方法。当然，最终的目的是对未来样本的标签的预测。在轿车与非轿车这个例子里，我们要求分类器能基于未来的特征矢量分辨出轿车与非轿车，而无需人类介入。显然，我们不可能预期分类器能对所有样本正确分类。为了衡量分类器的优劣，我们对样本空间赋予一个概率分布，然后度量错误分类的几率。之所以引入概率分布，是因为我们希望分类器能正确分类概率高的样本，而不在乎不太可能出现的样本。

第二个问题是，多大数量的训练样本足以保证一个分类器只要对所有训练样本都正确 (强分类器)，则预测错误大于 \(\varepsilon\) (使用产生训练样本相同的分布函数) 的几率小于 \(\delta\)? 理想情况下，我们希望不管未知的概率分布是什么，这个数字都足够。VC 维数理论提供了一个答案。

动机: 基于采样的讨论

VC 维数的是个基础概念，是学习理论的支柱，并且在其它场景也有用。第一个动机是数据库的例子。考虑包含一个公司全部员工的工资和年龄的数据库，以及下列形式的请求：多少年龄 35 到 45 之间的人工资在 60000 到 70000 之间？每个员工表示为平面上的一个点，坐标是年龄和工资。请求问的是多少数据点落到平行于坐标轴的矩形里。可以在请求到达之前选取数据的一部分，然后通过这部分落到请求的矩形里的比例来估计结果。对于一个矩形，可以通过让样本矩形足够大来让估计值超出 \(\varepsilon\) 的比例的几率小于 \(\delta\)。然而，我们希望样本对所有矩形都适用。乍一看，这样的估计不像是能工作。简单的 union bound 论证给不出有意义的结果。

如果两个长和宽与坐标轴平行的矩形包含相同的数据点，则称它们是等价的。如果有 \(n\) 个数据点，则 \(2^n\) 个子集中仅有 \(O(n^4)\) 个可以对应于位于矩形内的点集。为了看出这点，考虑任何矩形 \(R\)。如果其边不通过其内部的数据点，则平行移动这条边直到碰到内部数据点。显然，\(R\) 内的点组成的集合与新的矩形内的点组成的集合是同一个，因为矩形的边尚未越过任何数据点。通过相同的过程，移动四个边，使得每条边上至少有一个数据点。这样，每条边上至少有一个数据点的矩形的个数是 \(O(n^4)\)。指数 \(4\) 起的作用是重要的；它就是平行于坐标轴的矩形的 VC 维数。

令 \(U\) 是平面上 \(n\) 个点组成的集合，每个点代表一个员工的年龄和薪水。令 \(\varepsilon>0\) 表示一个给定的误差参数。从 \(U\) 中取出大小为 \(s\) 的随机样本 \(S\)。给定一个请求矩形 \(R\)，通过 \(\frac{n}{s}\norm{R\cap S}\) 来估计 \(\norm{R\cap U}\)。我们希望断言，大小为 \(s\) 的随机样本对应的误差对于任何 \(R\) 至多为 \(\varepsilon\)，也就是 \begin{equation} \norm{\norm{R\cap U} - \frac{n}{s}\norm{R\cap S}} \le \varepsilon n \end{equation} 对任何 \(R\) 成立。 当然，这个断言不是绝对的。存在一个小的概率使得样本非典型，比如就算矩形 \(R\) 包含很多个点，\(S\) 也可能不包含其中任何一个点。上述命题只是以较高几率成立，或者说其反面成立的几率很低。也就是说 \begin{equation} \text{Prob}\left(\exists R \norm{\norm{R\cap U} - \frac{n}{s}\norm{R\cap S}} > \varepsilon n\right) \le \delta \label{eqProb} \end{equation} 这里 \(\delta>0\) 是另外一个误差参数。注意到，让我们的样本 \(S\) 对所有可能的请求都适用是重要的，因为我们不能事先知道什么样的请求会出现。

需要多少样本才能保证上式成立？从 \(U\) 的 \(n\) 个点中均匀选出 \(s\) 个样本。对于固定的 \(R\)，其包含的样本数是 \(s\) 个独立 \(0{-}1\) 随机变量之和，每个为 \(1\) 的概率是 \(q = \frac{\norm{R \cap U}}{n}\)。\(\norm{R\cap S}\) 的分布是 \(\text{Binomial}(s,q)\)。使用 Chernoff 上界，对于 \(0\le\varepsilon\le1\)，有 \begin{equation} \prob{\norm{\norm{R\cap U} - \frac{n}{s}\norm{R\cap S}} > \varepsilon n} \le 2 e^{-\varepsilon^2 s / (3q)} \le 2 e^{-\varepsilon^2 s/3}. \end{equation} 使用并集上限并注意到只有 \(O(n^4)\) 个可能的集合 \(R\cap U\)，得到 \begin{equation} \prob{\exists R \norm{\norm{R\cap U} - \frac{n}{s}\norm{R\cap S}} > \varepsilon n} \le c n^4 e^{-\varepsilon^2 s/3}, \end{equation} 这里 \(c\) 是一个充分大的数。令 \begin{equation} s \ge \frac{3}{\varepsilon^2}\left(5\ln n + \ln \frac{1}{\delta}\right). \end{equation} 可以保证方程 \((\ref{eqProb})\) 在 \(n\) 充分大时成立。后面我们会看到就连对 \(n\) 的对数依赖也可被避免。只要 \(s\) 是一个依赖于误差 \(\varepsilon\) 和形状集合的 VC 维数的数，则方程 \((\ref{eqProb})\) 会成立。

在另外的情形，假设我们有一个平面上未知的概率分布 \(p\)，然后想知道一个矩形 \(R\) 的概率质量 \(p(R)\)。我们可以根据分布 \(p\) 取出 \(s\) 个独立样本组成集合 \(S\)，然后看样本估计 \(\norm{S\cap R}/s\) 与概率质量 \(p(R)\) 差多远。我们希望这个估计对任何矩形都是良好的。这是个比估计 \(R\cap U\) 更一般的问题，后者相当于 \(U\) 是由 \(n\) 个点组成的平面点集，而 \(p\) 对应于在每个点上取值为 \(1/n\) 的概率分布。

对于一般的问题，不存在把矩形数限制在 \(O(n^4)\) 的简单论证。移动矩形的边不再有用，因为这会改变包含的概率质量。并且 \(p\) 可能是个连续分布，所以相应的 \(n\) 是无穷大。所以上面采用并集上界的论证不会解决问题。基于 VC 维数的论证会在一般情形给出想要的结果。

除了矩形之外的形状也是有意思的。事实上，\(d\) 维的半空间是一类重要的“形状”，因为它们对应于阈值门。像半空间或矩形这类区域有一个称为 VC 维数的参数，我们可以使用允许的形状的这个参数来描述样本估计和概率质量之间的差异。也就是 \begin{equation} \norm{\text{概率质量} - \text{估计}} < \varepsilon \end{equation} 成立的几率是 \(1-\delta\)，这里 \(\delta\) 依赖于 \(\varepsilon\) 和 VC 维数。

总结：我们希望创造数据的一个样本，而无需知道会面对何种请求，只需要知道请求的类型 (比如矩形)。我们希望我们的样本对任何这类请求都适用。通过这个想法，我们引入 VC 维数的概念，之后将它与学习联系起来。

6.6 Vapnik-Chervonenkis 维数，即 VC 维数

一个集合系统 \((U,\mathbb{S})\) 由一个集合 \(U\) 以及 \(U\) 的子集组成的集合 \(\mathbb{S}\) 构成。集合 \(U\) 可以是有限或无限的。集合系统的一个例子是 \(U = R^2\)，即平面上的点，而 \(\mathbb{S}\) 是长和宽与坐标轴平行的矩形的集合，每个矩形被看成其中的一个点。

令 \((U,\mathbb{S})\) 是一个集合系统。我们称 \(U\) 的子集 \(A\) 被 \(\mathbb{S}\) 粉碎 (shattered)，如果 \(A\) 的每个子集可以被表达为 \(\mathbb{S}\) 的元素与 \(A\) 的交集。集合系统 \((U,\mathbb{S})\) 的 VC 维数是能被 \(\mathbb{S}\) 粉碎的 \(U\) 的任何子集的最大大小。

平面上四个点组成的集合，有些可以被矩形集合粉碎，有些不行。五个点组成的平面点集不可能被长和宽与坐标轴平行的矩形集合粉碎。三个共线点不可能被粉碎，因为每个包含两个终点的矩形必然也包含中间那个点。一般地，由于矩形是凸集合，如果一个点集里有个点位于其它点的闭包内，则这个点集不能被粉碎。

6.6.1 集合系统的例子，及其 VC 维数

长和宽平行于坐标轴的矩形
棱形的顶点可以被这样的集合粉碎。五个点的集合不行。于是这类矩形的 VC 维数是 4。证明如下：假设存在平面上的五个点被一族这样的矩形 (本段中不再重复“这样的”三个字) 粉碎。找到最小的包含五个点的矩形。对于每条边，至少有一个点让其运动中止。对每条边标记出这样的点。如果一个点在矩形的顶点处，则它让两条边运动中止。如果两个或多个点让一条边停止，则标记其中一个点。现在，最多标记了四个点。任何包围标记出的那些点的矩形必定包含未被标记的点。因此，由标记出的几个点组成的子集不能表示为矩形与那五个点的交集。

实数集上的区间
VC 维数是 2，因为没办法粉碎第一个和第三个点。

实数集上的区间对
考虑区间对的集合；这里，区间对理解为两个区间的并集。其 VC 维数是 4。如果有五个点，第一三五点没办法被粉碎。

凸多边形
考虑平面上所有凸多边形组成的集合。对于任何正整数 \(n\)，在单位圆上放置 \(n\) 个点。这些点的任何子集是凸多边形的顶点，这个凸多边形不会包含任何不在这个子集内的点。这表明凸多边形可以粉碎任意大的集合，因此其 VC 维数是无穷。

\(d\) 维半空间
半空间定义为超平面一侧的所有点，即具有 \(\{\mathbf{x}|\mathbf{a}^\trsps\mathbf{x}\ge a_0\}\) 形式的集合。\(d\) 维半空间的 VC 维数是 \(d+1\)。

存在 \(d+1\) 个点能被半空间粉碎。可把这些点取为 \(d\) 个单位坐标矢量，以及原点。假设 \(A\) 是这些点的任意子集，不妨设原点在其中。令矢量 \(\mathbf{a}\) 在对应于不在 \(A\) 中的那些分量为 1，其余分量为 0，则显然 \(A\) 处于半空间 \(\mathbf{a}^\trsps\mathbf{x}\le0\) 中，而 \(A\) 的补集位于这个半空间的补集中。