SVM补充

决策边界

Coursera 上 ML 的课程对 SVM 介绍有限,参看了周志华教授的《机器学习》一书后,补充了当中对于 SVM 的介绍。

首先,我们考虑用更传统的权值定义式来描述我们的 SVM 决策边界(划分超平面):

其中, 表示权值向量,权值向量对应了决策边界的法向量。 则表示偏置,也称位移项,表示了决策边界距坐标原点的距离。我们可以将决策边界记为 ,那么,样本 到决策边界的距离为:

我们将正样本标识为 1,负样本标识为 -1, 则 SVM 的期望预测可以重新描述为:

亦即:

使等号成立的样本称之为“支持向量(Support Vectors)”,两个异类的支持向量到决策边界的距离之和为:

被称之为间隔。

在之前的篇章中我们知道,SVM 就是力图是 足够大,从而获得更好的泛化能力:

我们可以转化为如下的二次优化问题:

硬间隔与软间隔

下图中,红色的决策边界表示了一种较的间隔划分,这种划分,能将所有正、负样本区分开来:

硬间隔并不一定好,就像我们在回归问题中提到的那样,这只是对于训练样本作出了极佳的拟合,但容易造成过度拟合。比如我们现在有了一个新的负样本,他被错误地分类为了正样本:

而下图则展示了一种较的间隔,这样的决策边界允许了一部分分类异常,避免了过拟合问题,但如果过软,也容易造成欠拟合问题:

鉴于此,我们在优化过程中,添加一个参数 来控制间隔的“软硬”:

其中, 是损失函数,其衡量了样本 与真实值 的近似程度,当 取值越大时,为了最优化问题,需要 越小,即各个样本都要尽可能分类正确,这提高了训练准确率,但也面临过拟合的问题。

取值 优势 可能面临问题
提高训练精度 过拟合
解决过拟合问题 欠拟合

故而, 扮演了回归问题中正则化参数 的角色。当 的取值趋于 时,模型就变为了硬间隔支持向量机。

常见的损失函数有:

名称 函数式
0/1 损失
hinge 损失
指数损失
对数损失

若采用 hinge 损失函数,则式 (8) 可以具体为:

引入 “松弛变量(slack variables)” ,可以将式 (9) 改写为:

这就构成 “软间隔支持向量机”。

松弛变量,顾名思义,就是控制每个样本受到约束的程度。 越大,则受约束程度越小(越松弛)。

  • ,则 ,即 异号,分类错误。
  • ,则 ,即 ,样本落在了最大间隔边界上。
  • ,则 ,即 ,样本落在了最大间隔与决策边界之间。

对偶问题

对于式 (10) 的优化模型,应用拉格朗日乘子法获得的拉格朗日函数如下:

其中, 是拉格朗日乘子。

的偏导为 0 可得:

将其带入 (1) 式中,得:

将式 (12) - (14) 代入式 (11) 中,就得到了式 (10) 的 对偶问题

对于软间隔支持向量机,KKT 条件要求:

由式 可得,对于任意训练样本 ,总有 或者

  • ,由 ,进而知

此时, 不会对模型 产生影响。

  • ,则有 ,由 得,,则,综合得:

此时,样本 为支持向量。

  • ,则有 ,由 得,,此时 ,得:

此时,样本 落在最大间隔与决策边界之间(),或者分类错误()。亦即,样本异常,仍然不会被模型 考虑。

综上,我们不但可以将 KKT 条件写为:

并且,还能够知道,采用了 hinge 损失函数的最终模型 仅与支持向量有关。

核函数

假定我们面临的数据呈现下面这样的分布:

显然,这不是一个线性可分的问题,在逻辑回归中,我们会通过多项式扩展来创建新的高维特征,从而将低维度的线性不可分问题转换为了高维度的线性可分问题。

在 SVM 中,仍然是考虑将低维不可分问题转换到高维度可分问题:

对应了 的高维度特征向量。

此时,SVM 优化模型的对偶问题为:

表示 的内积:

函数 即表示了核函数(kernel function),引入核函数后,优化模型可以写为:

求解后,得到模型:

核函数 表达式( 参数
线性核
高斯核 为高斯核带宽
多项式核 为多项式次数
拉普拉斯核
Sigmoid 核 为双曲正切函数,

参考资料

results matching ""

    No results matching ""