目录

6.1 间隔与支持向量

6.2 对偶问题

6.3 核函数

6.4 软间隔与正则化

6.4.1 软间隔

6.4.2 正则化

6.5 支持向量回归

6.6 核方法

6.1 间隔与支持向量

分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面,将不同类别的样本分开.但能将训练样本分开的划分超平面可能有很多,如下图所示

“正中间”的:鲁棒性最好,泛化能力最强

超平面方程：

样本空间中任意点到超平面（w,b)的距离可写为：

如图6..1.2所示,距离超平面最近的这几个训练样本点点到超平面的距离为1，它们被称为“支持向量”(support vector)，两个异类支持向量到超平面的距离之和为：

 现在我们需要找到最大间隔的划分超平面，使y最大

6.2 对偶问题

支持向量机本身是一个二次规划问题,能用优化计算包求解,但可以有更高效的办法

拉格朗日乘子法：

• 第一步：引入拉格朗日乘子法0得到拉格朗日函数：

• 第二步：令L(w,b,a)对w和b的偏导为零可得：

• 第三步：回代可得：

最终模型：

 

需要满足KKT条件：

必有或

• 解的稀疏性:

训练完成后,最终模型仅与支持向量有关

这个解法还不够方便，还有更容易的方法：

• SMO：

基本思路：不断执行如下两个步骤直至收敛

• 第一步: 选取一对需更新的变量和
• 第二步: 固定和以外的参数,求解对偶问题更新和

仅考虑和时,对偶问题的约束变为

 用表示，代入对偶问题，这样就有闭式解。

对任意支持向量有，可以解出b

但现实任务中常采用一种更鲁棒的做法:使用所有支持向量求解的平均值

6.3 核函数

若不存在一个能正确划分两类样本的超平面，怎么办?

将样本从原始空间映射到一个更高维的特征空间,使样本在这个特征空间内线性可分

如果原始空间是有限维(属性数有限)，那么—定存在一个高维特征空间使样本线性可分

• 原始问题：

• 对偶问题：

• 预测：

 计算高维的内积非常困难，所以我们设想了一个函数（核函数）：

绕过显式考虑特征映射、以及计算高维内积的困难

Mercer定理: 若一个对称函数所对应的核矩阵半正定,则它就能作为核函数来使用

任何一个核函数，都隐式地定义了一个RKHS(Reproducing Kernel HilbertSpace,再生核希尔伯特空间)
“核函数选择”成为决定支持向量机性能的关键!

6.4 软间隔与正则化

6.4.1 软间隔

现实中很难确定合适的核函数。使训练样本在特征空间中线性可分，即便貌似线性可分,也很难断定是否是因过拟合造成的
引入软间隔(Soft Margin),允许在一些样本上不满足约束

 基本思路: 最大化间隔的同时,让不满足约束≥1的样本尽可能少

 

 障碍：0/1损失函数非凸、非连续、不易优化！

• 采用替代损失函数,是在解决困难问题时的常见技巧
• 求解替代函数得到的解是否仍是原问题的解?理论上称为替代损失的“—致性”(Consistency)问题

 软间隔支持向量机：

• 原始问题：

  

• 引入”松弛量“：

  

• 对偶问题：

  

根据KKT条件可知,最终模型仅与支持向量有关,也即采用hinge损失函数后仍保持了sVM解的稀疏性

6.4.2 正则化

统计学习模型的更一般形式：

 是结构风险（也被称为正则化项），描述模型本身的某些性质，是经验风险，描述模型与训练数据的契合程度

• 正则化可理解为“罚函数法”
• 通过对不希望的结果施以惩罚，使得优化过程趋向于希望目标从贝叶斯估计的角度，则可认为是提供了模型的先验概率

6.5 支持向量回归

基本思路：允许模型输出与实际输出间存在2的差别

 落入2间隔带的样本不计算损失

• 原始问题：

• 对偶问题：

• 预测：

6.6 核方法

• 表示定理：

令H为核函数k对应的再生核希尔伯特空间，优化问题：

解为：

对于一般的损失函数和正则化项,优化问题的最优解h*(z)都可表示为核函数的线性组合

核方法：核函数的学习方法

• 核化：

将线性学习器拓展为非线性学习器，从而得到“核线性判别分析”

通过某种映射将样本映射到一个特征空间，然后进行线性判别分析，求得：

 KLDA学习目标：

用核函数来替代高维的内积，

可得：

最后KLDA学习目标可等价为：