线性SVM

svm学习笔记，参考《统计学习方法》

线性可分支持向量机与硬间隔最大化

线性可分支持向量机

定义：给定线性可分训练数据集，通过间隔最大化或者等价地求解相应的凸二次规划问题学习得到的分离超平面为

以及相应的分类决策函数

称为线性可分支持向量机。

函数间隔

定义：对于给定训练数据集 T 和超平面 (w,b) (w为法向量，b为截距)，定义超平面 (w,b) 关于样本点 $(x_i,y_i)$ 的函数间隔为

定义超平面 (w,b) 关于训练数据集 T 的函数间隔为超平面 (w,b) 关于 T 中所以样本点 $(x_i,y_i)$ 的函数间隔最小值，即

函数间隔可以表示分类预测的正确性及确信度，但是只要成比例地改变 w 和 b，超平面并没有改变，但是函数间隔却变成原来的几倍，所以我们对分离超平面的法向量 w 进行规范化，使得间隔确定，这时函数间隔就成为了几何间隔。

几何间隔

定义：对于给定训练数据集 T 和超平面 (w,b)，定义超平面 (w,b) 关于样本点 $(x_i,y_i)$ 的几何间隔为

定义超平面 (w,b) 关于训练数据集 T 的几何间隔为超平面 (w,b) 关于 T 中所以样本点 $(x_i,y_i)$ 的几何间隔最小值，即

从函数间隔和几何间隔的定义(式(7.3)～式(7.6)可知，函数间隔和几何间隔有下面的关系：

最大间隔分离超平面

支持向量机学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对线性可分的数据集而言，线性可分分离超平面有无穷多个(等价于感知机)，但是几何间隔最大的分离超平面是唯一的。这里间隔最大化又称为硬间隔最大化。间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说要对最难分的实例点(距离超平面最近的点)也有足够大的确信度将它们分开。

如何求得一个几何间隔最大的分离超平面呢？这个问题可以表示为下面的约束最优化问题：

即我们希望最大化超平面 (w,b) 关于训练数据集的几何间隔 $\gamma$ ，约束条件表示的是超平面 (w,b) 关于每个训练样本点的几何间隔至少是 $\gamma$ 。

考虑几何间隔和函数间隔的关系式(7.8)，可将上式改写为：

函数间隔 $\hat{\gamma}$ 取值并不影响最优化问题的解，因为 w 和 b 按比例改变后 $\hat{\gamma}$ 也成比例变化，所以我们可以取 $\hat{\gamma}=1$ ，带入到上面的最优化问题。另外最大化 $\frac{1}{||w||}$ 和最小化 $\frac{1}{2}||w||^2$ 是等价的,于是得到下面的线性可分支持向量机学习的最优化问题：

这是一个凸二次规划问题(先不管是啥)。

最大间隔法

综上，线性可分支持向量机的学习算法——最大间隔法如下：

支持向量和间隔边界

在线性可分情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量是使约束条件式(7.14)等号成立的点，即 $y_i(w\cdot x+b)-1=0$ ，对 $y_i=+1$ 的正例点，支持向量在超平面 $H_1:w\cdot x+b=1$ 上，对 $y_i=-1$ 的负例点，支持向量在超平面 $H_1:w\cdot x+b=-1$ 上。如下图所示，在 $H_1$ 和 $H_2$ 上的点就是支持向量。

分离超平面与 $H_1$ 和 $H_2$ 平行且位于它们中央， $H_1$ 与 $H_2$ 之间的距离称为间隔。间隔依赖于分离超平面的法向量 w，等于 $\frac{2}{||w||}$ ， $H_1$ 和 $H_2$ 称为间隔边界。

在决定分离超平面时只有支持向量起作用，而其他实例点不起作用。如果改变支持向量将改变所求的解，但是如果在间隔边界以外移动其他实例点，甚至去掉都不会改变解。由于支持向量在确定分离超平面中起着决定性作用，所以将这种分类模型称之为支持向量机。支持向量个数很少，所以支持向量机由很少“重要的”训练样本确定。

学习的对偶算法

将求解线性可分支持向量机的最优化问题作为原始最优化问题，应用拉格朗日对偶性(不知道)，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。这样做的优点，一是对偶问题往往更容易求解，二是自然引入核函数，进而推广到非线性分类问题。

首先构建拉格朗日函数。对每一个不等式约束(7.14)引进拉格朗日乘子 $\alpha_i\geq0,i=1,2,\cdots,N$ ，定义拉格朗日函数：

其中 $\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$ 为拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：

所以，为了得到对偶问题的解，需要先求 $L(w,b,\alpha)$ 对 w，b 的极小，再求对 a 的极大。

1. 求 $min_{w,b}L(w,b,\alpha)$

2. 求 $min_{w,b}L(w,b,\alpha)$ 对 $\alpha$ 的极大即是对偶问题：

   

   将式(7.21)的目标函数由求极大转换成求极小，就得到下面与之等价的对偶最优化问题：

   

定理：

综上，对于给定的线性可分训练数据集，可以先求对偶问题(7.22)~(7.24)的解 ${\alpha}^*$ ，再利用式(7.25)和式(7.26)求得原始问题的解 $w^*,b^*$ ，从而得到分离超平面及分类决策函数。这种算法称为线性可分支持向量机的对偶学习算法：

在线性可分支持向量机中，由式(7.25)、(7.26)可知， $w^*,b^*$ 只依赖于训练数据中对应于 ${\alpha}^*>0$ 的样本点 $(x_i,y_i)$ ，而其他样本点对 $w^*,b^*$ 没有影响。我们将训练数据中对应于 ${\alpha}^*>0$ 的实例点 $x_i\in R^n$ 称为支持向量。

线性支持向量机与软间隔最大化

线性不可分的线性支持向量机

线性不可分的线性支持向量机简称线性支持向量机。现实中大部分数据集都是线性不可分的，这意味着某些样本点不能满足函数间隔大于等于1的约束条件(7.14)，我们可以对每个样本点引入一个大于0的松弛变量(超平面约束条件变宽松了，所以称为软间隔最大化)，同时对每个松弛变量支付一个代价(C是代价的系数)，因此线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题(原始问题):

下面给出线性支持向量机的定义：

学习的对偶算法

支持向量

在线性不可分的情况下，将对偶问题(7.37)~(7.39)的解 ${\alpha}^*=({\alpha}_1^*,{\alpha}_2^*,\cdots,{\alpha}_N^*)^T$ 中对应于 ${\alpha}_i^*>0$ 的样本点 $(x_i,y_i)$ 的实例 $x_i$ 称为支持向量(软间隔的支持向量)。

hinge loss(合页损失函数)

非线性支持向量机与核函数

对于非线性分类问题，我们可以把数据映射到高维特征空间，使得在高维空间中是线性可分的。如何映射就是通过核函数，具体看下一篇非线性svm。

---

• Previous
  A^2-Nets: Double Attention Networks
• Next
  非线性SVM与核函数

---