吃瓜学习5-第六章支持向量机(间隔与支持向量机、对偶问题、软间隔

作者: 曼曼668 | 来源:发表于2021-07-29 23:57 被阅读0次

支持向量机基本概念

支持向量机的基本想法：

从几何角度，对于线性可分数据集，支持向量机就是找位于两类训练样本"正中间"（或者说找距离正负样本都最远）的超平面，相比于感知机，其解是唯一的，且不偏不倚，泛化性能更好（原因是这个超平面对训练样本局部扰动的"容忍性“最好。）。如下图，最粗的那条直线。

存在多个划分超平面将两类训练样本分开

n维超平面有几个特性：(超平面 $w^Tx+b=0$ ,其中w和x的维度相同)

超平面方程不唯一

法向量w和位移项b确定一个唯一超平面

法向量w垂直于超平面(缩放w,b时，若缩放倍数为负数会改变法向量方向)

法向量w指向的那一半空间为正空间，另一半为负空间

任意点x到超平面的距离公式为 $r=\frac{|w^Tx+b|}{||w||}$

几何间隔：

假设超平面（w,b）能将训练样本正确分类，即对于 $（x_{i} ,y_{i}）\epsilon D$ ,若 $y_{i}=+1$ ,则有 $w^Tx+b＞0，$ 若 $y_{i}=-1$ ，则有w^Tx+b<0，如下

6.3

如图6.2所示,距离超平面最近的这几个训练样本点使式(6.3)的等号成立,它们被称为“支持向量”(support vector)，两个异类支持向量到超平面的距离之和为

$\gamma =\frac{2}{||w||}$

$\gamma$ 被称为"间隔"

图6.2 支持向量与间隔

那么到此，支持向量机的基本概念已经解说完毕。

支持向量机过程

支持向量机的模型策略就是：给定线性可分数据集X，支持向量机模型希望求得数据集X关于超平面的几何间隔γ达到最大的那个超平面，然后套上一个sign函数实现分类功能。那如何求w和b？

以下是支持向量机的优化：

支持向量机的主问题：

欲找到具有"最大间隔" 的划分超平面，也就是要找到能满足式(6.3) 中约束的参数w 和b ，使得γ 最大，即

6.5

显然,为了最大化间隔,仅需最大化| $||w||^{-1}$ ，这等价于最小化 $||w||^2$ .于是,式(6.5)可重写为

6.6

这就是支持向量机(Support Vector Machine,简称SVM)的基本型.

支持向量机的拉格朗日函数和对偶函数：

备注：对偶函数是拉格朗日函数的最小值。而对偶函数实际上是求关于 $\alpha$ 的最大值。

关于公式6.11，我们用SMO来解决。

软间隔

以上模型是解决线性可分的数据集，但实际中，更多解决线性不可分的数据集，因此我们允许向量机在一些样本犯点错。为此引入了”软间隔“概念。如下图.

图6.4软间隔示意图.红色圈出了一些不满足约束的样本

从数学角度来说，软间隔就是允许部分样本（但要尽可能少〉不满足下式中的约束条件

因此，可以将必须严格执行的约束条件转化为具有一定灵活性的“损失"，合格的损失函数要求如下:

(1)当满足约束条件时，损失为0

(2)当不满足约束条件时，损失不为0，

(3)(可选)当不满足约束条件时，损失与其违反约束条件的程度成正比

只有满足以上要求，才能保证在最小化 (min)损失的过程中,保证不满足约束条件的样本尽可能的少。

于是，我们的优化目标写为：

6.29

其中C>0是一个常数, $l_{0/1}$ 是“0/1损失函数”，下面的 $z=y_i(w^Tx_i+b)-1$

6.30

C用来调节损失的权重，显然当C→＋oo时，会迫使所有样本的损失为0，进而退化为严格执行的约束条件，退化为硬间隔，因此,本式子可以看作支持向量机的一般化形式。总之，C越大，表示第二项影响值越小，样本犯错很难，C越小，表示第二项影响值越大，更容易允许样本犯错。

然而 $l_{0/1}$ 非凸、非连续,数学性质不太好,使得式(6.29)不易直接求解.于是，人们通常用其他一些函数来代替 $l_{0/1}$ ，称为“替代损失”(surrogate loss).替代损失函数一般具有较好的数学性质,如它们通常是凸的连续函数且是 $l_{0/1}$ 的上界.图6.5给出了三种常用的替代损失函数:

图6.5 三种常见的替代损失函数: hinge损失、指数损失、对率损失

若采用hinge损失,则式(6.29)变成

6.29

引入松弛变量 $\xi _i$ ，上述优化问题便和下述优化问题等价。 $\xi _i=max(0,1-y_i(w^Tx_i+b))$ ，理解损失值

6.35,

通过拉格朗日乘子法可得到式(6.35)的拉格朗日函数

6.36

其中 $\alpha _i≥ 0，u_i≥0$ 是拉格朗日乘子.

支持向量回归

对样本(x, y)，传统回归模型通常直接基于模型输出f(x)与真实输出y之间的差别来计算损失,当且仅当f(x)与y 完全相同时,损失才为零.

与此不同，支持向量回归(Support Vector Regression,简称SVR)假设我们能容忍f(x)与y之间最多有 $\epsilon$ 的偏差，即仅当f(x)与y之间的差别绝对值大于 $\epsilon$ 时才计算损失.如图6.6所示,这相当于以f(x)为中心,构建了一个宽度为2 $\epsilon$ 的间隔带,若训练样本落入此间隔带,则认为是被预测正确的.