机器学习 第六章

一、间隔与支持向量

给定训练样本集，分类学习最基本的想法是基于训练集D在样本空间中找到一个划分超平面，将不同类别的样本分开。在样本空间中，划分超平面可通过如下线性方程表示：，w为法向量，决定超平面的方向；b为位移项，决定超平面与原点间的距离。因此可用(w,b)来表示一个超平面。

假设超平面可以对训练样本正确分类，那么可以用下式来表示其分类：

距离超平面最近的几个训练样本点使得上式成立，被叫做支持向量，两个异类支持向量到超平面的距离之和是间隔。想要找到最大间隔的划分超平面，也就是要满足下式：

这就是支持向量机（SVM）的基本型。

二、对偶问题

 SVM的基本型本身是一个凸二次规划问题，能直接用现成的优化计算包求解，但是也可以使用别的方法来求解。这里使用拉格朗日乘子法可以得到其对偶问题。对上式的每个约束添加拉格朗日乘子，可将式子写为：

 经过偏导的计算以及考虑前面的约束，可得上式的对偶问题为：

最终可以得到模型。上述过程满足KKT条件，即要求

支持向量机的一个重要性质为训练完成后，大部分的训练样本都不需保留，最终模型仅与支持向量有关。 对与对偶问题的求解，其中一个著名的算法为SMO。其基本思路为先固定之外的所有参数，然后求上的极值；由于存在约束条件，若固定之外的所有参数，可由其他参数导出。之后将执行下述两个步骤直到收敛：（1）选取一对需更新的变量和（2）固定和以外的参数，求解对偶问题得到新的和。

SMO采用了一个启发式：使选取的两变量所对应样本之间的间隔最大。SMO高效的原因是在固定其他参数后，只优化两个参数。对于偏移量b可以使用所有支持向量求解平均值。

三、核函数

对于原始样本空间中不存在一个能正确划分两类样本的超平面，可将样本从原始样本空间映射到一个更高维的特征空间，使得样本在这个特征空间中线性可分。如果原始样本空间有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。

在特征空间中划分超平面对应的模型可以表示为，表示x映射后的样本空间。w和b是样本参数，其计算类似上面的计算。对于，直接计算比较困难，可以使用一个称为核技巧的方法来进行计算，即和在特征空间的内积等于他们在原始空间中通过函数计算的结果。最后求解可得表达式为：

其中，函数就是核函数， 这一式子也叫做支持向量展式。

核函数的定理为令为输入空间，是定义在*上的对称函数，则是核函数当且仅当对于任意数据，核矩阵K总是半正定的。其表明只要有一个对称函数所对应的核矩阵半正定的，就可以当作核函数使用。任何一个核函数都可以隐式定义一个称为再生核希尔伯特空间（RKHS）的特征空间。其中几种常见的核函数为：

其次，若k1和k2都为核函数那么其线性组合也为核函数； 若k1和k2都为核函数，核函数的直积也为核函数；若k1为核函数，那么对应任意g(x),也为核函数。

四、软间隔与正则化

在现实任务中很难找到一个合适的核函数使得训练样本在特征空间中线性可分。缓解该问题的一个方法是允许支持向量机在一些样本上出错，所以引入了软间隔概念。它允许一些样本不满足约束，其次在最大化间隔的同时，不满足约束的样本应该尽可能少，所以可将优化目标写为：

 其中是0/1损失函数，其非凸、非连续，数学性质不太好，通常使用别的损失函数来替代它。叫做替代损失。其中三种常见的替代函数为：

在引入松弛变量，那么可以得到软间隔支持向量机的公式为：

其与硬间隔下的对偶问题相比，唯一的差别在于对偶变量的约束不同，可以采用上述同样的方法来对软间隔进行求解。软间隔支持向量机的最终模型仅与支持向量相关，即通过采用hinge损失函数仍保持了稀疏度。

支持向量机与对率回归的优化目标相近，通常情形性能也相差不多。对率回归的优势主要在于其输出具有自然的概率意义，即在给出预测标记的同时也给出了概率 。

其次还可以使用别的替代损失函数得到其他的模型，其性质与所用的替代函数直接相关，但共性在于：优化目标中的第一项用来描述划分超平面的间隔大小，另一项用来表述训练集上的误差，可写为

其中的叫做结构风险，用于描述模型f的一些性质；后面的求和式子叫做经验风险，用于描述模型和训练数据的契合程度。上式被叫做正则化问题。

五、支持向量回归 

支持向量回归（SVR）假设能容忍f(x)与y之间最多有的偏差，即仅当f(x)与y之间的差别的绝对值大于时才计算损失。SVR问题可以形式化为：

经过引入松弛变量和拉格朗日变化之后，可以得到其对偶问题的式子为：

 能使得的样本即为SVR的支持向量，必须落在间隔带之外，其解仍然具有稀疏性。对于b的求解通常采用选取多个满足条件的样本求解b之后求解平均值。

六、核方法

给定训练样本若不考虑偏移项b，学得的模型都能表示成核函数的线性组合，既有如下的表示定理：令H为核函数k对应的再生核希尔伯特空间，表示H空间中关于h的范数，对于任意单调递增函数和任意非负损失函数，优化问题的解总可以写为。其对损失函数没有要求，对正则化项要求单调递增。

核方法指的是一系列基于核函数的方法。最常见的是通过"核化" (即引入核函数)来将线性学习器拓展为非线性学习器。核线性判别分析（KLDA）的学习目标是：

经过一系列的变换可将上式转化为：

使用线性判别分析求解方法即可得到，进而得到投影函数h(x)。

总结

 本章详细的介绍了支持向量机的基本原理、优化方法、核函数应用以及扩展模型如SVR。SVM以其强大的分类能力和良好的泛化性能在机器学习领域得到了广泛应用。