在前⼀部分中，我们研究了许多基于⾮线性核的学习算法。这种算法的⼀个最⼤的局限性是核函数必须对所有可能的训练点对进⾏求值，导致对新的数据点进⾏预测时也会花费过多的时间。本章中，我们会看到具有稀疏解的基于核的算法，其对新数据的预测只依赖于训练集的⼀个⼦集上计算的核函数。

1 最大边缘分类器（SVM）

1.1 硬间隔二分类SVM

对于一个分类问题，假设训练数据是线性可分的，很多算法可以找到能精确分类训练集点的决策平面。以感知器算法为例，该方法使用随机梯度下降算法求解模型参数，当训练数据线性可分，感知器算法可以保证能在有限的步骤内找到一个精确解，但由于可能存在多个解，最终哪个解会被找到依赖于参数的初始化以及数据点出现的顺序。
实际应用中，当存在多个解，由于我们希望模型在新数据点上的表现要尽可能好，即尝试找到泛化误差最小的那个解。

1.1.1 边缘

最大边缘决策面

支持向量机的提出就是为了找到能使得泛化误差尽可能小的决策平面，主要通过引入边缘（margin）——决策平面与任意样本之间的最小距离。这里的最小距离指的是决策平面与最近的训练数据点之间的垂直距离。通过最大化边缘，我们可以从多个能精确分割训练集点的决策平面中（这里假定数据点在特征空间中是线性可分的），找到一个特定的选择。

采⽤最⼤边缘解的动机

可以通过计算学习理论（computational learning theory）或者统计学习理论（statistical learning theory）进⾏理解。
Restricted Bayes Optimal Classifiers.pdf
上述论文中给出了使⽤最⼤边缘解的⼀个简单的原因。文中⾸先使⽤带有共同参数的⾼斯核Parzen密度估计对每个类别的输⼊的分布进⾏建模。通过最⼩化学习到的模型的错误率来寻找最优的超平⾯。在极限的情况下，可以证明最优超平⾯是有着最⼤边缘的超平⾯。这个结果背后的直观含义是，随着的减⼩，距离超平⾯较近的点对超平⾯的控制能⼒逐渐⼤于距离较远的点。在极限情况下，超平⾯会变得与⾮⽀持向量的数据点⽆关。

1.1.2 支持向量机

a. 边缘约束与最优化目标

首先，我们对二分类线性基函数模型进行如下表示

为了便于理解，我们将偏置设置为阈值。如果输入项则输入被分类到中（对应），否则为类别（对应），即决策函数为。此时的决策面直接对应的点集。此前已推导出任意输入到决策面的垂直距离大小为。注意当前我们的要求是：

1. 线性可分情况下，训练集的点均被正确分类，此时对于所有训练集的数据点有；
2. 最大化决策面与最近的训练样本点在输入空间中的距离；

将二者统一在一个式子中，我们将点距离决策面的距离表示为

边缘由训练集中垂直距离最近的点给出，即，我们希望通过最优化参数和来最大化这个距离
但直接求解这个最优化问题相当复杂，因此我们要把它转化为⼀个更容易求解的等价问题。
注意到这里的对于所有样本一致，可以从问题中提出来。进一步简化这个相对复杂的优化问题，因为 对模型参数进行缩放（ w → κw 以及b → κb）并不改变点距离决策⾯的几何距离。利用该性质，我们可以调整模型参数，使得对于距离决策⾯最近的点满足

且整个训练集的数据点满足

这被称为决策超平⾯的标准表⽰。对于使上式取得等号的数据点，我们称限制被激活，对应于距离决策面最近的点，而对于剩余数据点，我们说限制未激活。由于总会有⼀个距离最近的点，因此总会存在⾄少⼀个激活限制，并且⼀旦边缘被最⼤化，会有⾄少两个激活的限制（要最大化则多于一个数据点）。因此我们得到了一个约束条件下的最大化问题
约束条件：

最大化问题（最大化等价于最小化）：

这是一个⼆次规划（quadratic programming）问题，常数因子的引入是为了方便后续计算。

b. 带约束的最优化问题求解

在之前的最大化似然函数求解中，我们会将问题转换为最小化负对数似然或者是等价的平方和误差函数，这类函数通常是凸函数，因此可以通过寻找令该函数导数为零的驻点来直接找到对应的极值点，属于无约束的最优化问题。
由于当前的优化目标中有额外的约束条件，这是一个包含不等式约束的最优化问题，无法直接以上方法。一种解决的思路是将其转化为一系列的无约束问题进行求解，主要通过求解拉格朗日对偶问题来解决。
更多关于Lagrange对偶的内容可参考有约束的优化问题。

c. 最大化边缘的对偶表示

下面我们通过引入拉格朗日乘子来加入惩罚项，令乘数，先将带约束的优化目标函数转化为以下的拉格朗日函数

注意到加入的乘数项前为负号，对于符合约束的项，而非负，和式中对应项，将使得变小，反之不符合约束的样本项将使使增大，给予“惩罚”。这相当于我们隐式地使⽤了⼀个误差函数——当数据点被错误分类时，这个误差函数等于⽆穷⼤，⽽当数据点被正确分类时，这个误差函数等于零。
我们最终的目的是最小化整个拉格朗日函数，对于中的第一项，我们的目标始终是要最小化，而对于后一个惩罚项，我们的需要近似约束项的作用，也就是说当存在违反约束的数据点时，要能够使得惩罚尽可能大，即相应的要尽可能大，从而使得接近于无穷大。因此我们需要关于最小化，且关于最大化。先令关于的导数为零，得

使用这两个条件从中消去，定义核函数，

约束条件为

这称为最大化边缘问题的对偶表示，目标是关于最大化。
M个变量的⼆次规划问题的求解，通常的时间复杂度为。通过将原始问题转化为对偶问题，我们将涉及到M个变量的最⼩化公式的问题转化为了涉及到N 个变量的对偶问题。对于⼀组固定的基函数，其中基函数的数量M⼩于数据点的数量N，转化为对偶问题似乎没有什么好处。但是，对偶问题使得模型能够⽤核函数重新表⽰，因此最⼤边缘分类器可以被⾼效地应⽤于维数超过数据点个数的特征空间，包括⽆穷维特征空间。核公式也让核函数正定这⼀限制条件存在的原因变得更显然，因为这能确保了拉格朗⽇函数有上界，从⽽使得最优化问题可解。

d. 支持向量

假设我们已经完成了对偶问题的求解，想使用模型预测新的数据点类别，可直接使用以下公式

根据KKT条件，需要满足下列三个性质

从第三个性质我们可以知道对于每个数据点，要么，要么。因此在（9）的和式中所有对应的数据点对预测的贡献为零。我们将剩余的对预测结果有影响的数据点称为支持向量（support vector），这些支持向量满足，正对应于特征空间中位于最大边缘超平面上的点，即支持向量点位于超平面或上。
如图7.1所示，这部分点通常只是全量训练数据集的一个很小的子集。这个性质是⽀持向量机在实际应⽤中的核⼼，⼀旦模型被训练完毕，相当多的数据点都可以被丢弃，只有⽀持向量被保留。

上面的图7.2给出了⼀个分类问题的例⼦。分类⽤的模型使⽤⽀持向量机训练，训练数据是⼀个简单的⼈⼯⽣成的数据集，核函数为⾼斯核。虽然数据点在⼆维空间中不是线性可分的，但是它在隐式地由⾮线性核函数定义的⾮线性特征空间中是线性可分的。图中的最⼤边缘超平⾯由⽀持向量的位置定义，其他数据点可以⾃由移动（只要仍然在边缘区域之外）⽽不改变决策边界。

1.2 软间隔二分类SVM

⽬前为⽌，我们假设训练数据点在特征空间中是线性可分的。然⽽在实际情况中，对于固定的基函数而言类别可能是线性不可分的，此时类条件分布可能重叠，这种情况下对训练数据的精确划分会导致较差的泛化能⼒。
因此我们需要修改⽀持向量机，允许⼀些训练数据点被误分类，放宽约束使得数据点允许在边缘边界的“错误侧”，但是增加⼀个惩罚项，这个惩罚项随着与决策边界的距离的增⼤⽽增⼤，对应于约束条件的修改。

1.2.1 松弛变量

为了便于最优化问题的求解，令这个惩罚项是距离的线性函数⽐较⽅便。为此我们引⼊松弛变量，将式（5）中的硬性约束替换为下式

这是因为当训练数据点并非线性可分时，我们需要
此时对于不同位置数据点，我们希望

• 当数据点被正确分类：
  • 若位于边缘平面上，或边缘正确的外侧时，并无惩罚：；
  • 若位于边缘内部，但是在决策面的正确侧时，给予一个较小的惩罚：；
• 当数据点被错误分类：
  • 若位于决策面错误的一侧，被误分时则给予较大的惩罚：；

与硬间隔时的情况不同，此时虽然边缘超平面仍为，但这并非是距离决策面最近的点了，之前在硬约束下，不存在的数据点，而此时我们通过加入非负的松弛变量对约束进行了放宽，所以是存在令的数据点的。而最终我们得到的其实是一个软边缘（soft margin）。需要注意的是，虽然软边缘使得SVM对于线性不可分的数据点仍能给出决策面，但决策面却对异常点十分敏感，尤其是距离真实决策面很远的异常点，这是因为惩罚项随着数据点与决策边界间的距离增大而增大。
此时我们的目标变成了最大化边缘的同时，以一种比较柔和的方式惩罚位于边缘边界错误一侧的数据点
其中惩罚系数C控制了松弛变量惩罚与边缘间的折中，因为最小化上式意味着同时要最小化第一项（等于最大化间隔）和第二项（等于最小化误分类点的数量）。可知C越大则对误分类的惩罚越大，模型也越接近于硬间隔的SVM。

1.2.2 软边缘对偶问题

对于上面提出的软边缘设定，仍然是在求解一个有约束的最优化问题
约束条件：

优化目标函数：

同样可转化为Lagrange函数

以及KKT条件

同样，由此找到相应的对偶问题，根据KKT条件，最终得到

这与硬间隔情况下仅仅是约束条件存在差异。

1.2.3 SMO学习算法

虽然对新输⼊的预测只通过⽀持向量完成，但是训练阶段（即确定参数 a 和b的阶段）使⽤了整个数据集， 因此找到⼀个解决⼆次规划问题的⾼效算法很重要。因为我们⽬标函数是⼆次的，而限制条件定义了⼀个凸区域（根据限制条件的线性性质），那么任意局部最优解也是全局最优解。
使⽤传统的⽅法直接求解⼆次规划问题通常是不可⾏的，因为需要的计算量和存储空间都相当⼤， 因此我们需要寻找更实际的⽅法。⼀种最流⾏的训练⽀持向量机的⽅法被称为顺序最⼩化优化（sequential minimal optimization），或者称为SMO。这种⽅法考虑了分块⽅法的极限情况，每次只考虑两个拉格朗⽇乘数。 这种情况下⼦问题可以解析地求解， 因此避免了数值⼆次规划。选择每⼀步骤中需要考虑的拉格朗⽇乘数对时，使⽤了启发式的⽅法。
TODO

1.3 使用核函数的非线性SVM

核函数对应于特征空间中的内积。特征空间可以是⾼维或⽆穷维的。通过直接对核函数操作，⽽不显式地引⼊特征空间，⽀持向量机或许在⼀定程度上避免了维度灾难的问题。

1.4 多分类问题SVM

参考之前探讨过的关于一般线性分类器如何推广到个类别的情景，通常有“一对多”和“一对一”这两种方案。

*1.5 回归问题SVM

2 相关向量机

⽀持向量机被⽤于⼀系列的分类和回归的应⽤中。尽管这样，⽀持向量机还是有许多局限性，某些局限性已经在本章中讨论过了：

• SVM直接输出⼀个决策结果⽽不是后验概率；
• SVM最开始⽤于处理⼆分类问题，推⼴到K>2类时有很多问题；
• 有⼀个复杂度参数C或者ν（以及回归问题中的参数ϵ ）必须使⽤诸如交叉验证的⽅法确定；
• 预测是⽤核函数的线性组合表示的，核函数以训练数据点为中⼼，并且必须是正定的；

相关向量机（relevance vector machine）RVM是⼀个⽤于回归问题和分类问题的贝叶斯稀疏核⽅法，它具有许多SVM的特征，同时避免了SVM的主要局限性。此外，它通常会产⽣更加稀疏的模型，从⽽使得在测试集上的速度更快，同时保留了可⽐的泛化误差。

2.1 用于回归的RVM

2.2 用于分类的RVM