第六章支持向量机

支持向量机(supporyibant Vector Machine)是一种算法，一般被称作SVM，其为处理非线性问题提供了一种更加强大的方法。

间隔与支持向量

首先是决策边界的选择，当我们拿到一些线性可分的数据的时候，将数据分类的决策边界由很多条，例如：

于是我们会选取出最好的决策边界，显然是加粗处于中间那条决策边界是最好的。但是实际上并非如此，我们要找到最好决策边界就必须找到最大边界，即不同类别的最优分隔界，再取两个边界的中间，使得决策边界的容忍性最优，对未知示例的泛化性能达到最强。
于是，我们想要找到离决策边界最近的点以找到决策边界。
在样本空间中，划分超平面可通过如下线性方程来描述：

$w^Tx+b=0$

其中w为法向量，决定超平面方向，b为位移项，决定超平面与原点的距离。

如图，假设决策边界是一个阴影平面，即是划分超平面。假设平面上有两点x'，x''，那么则有:

$w^Tx'+b=0$
$w^Tx''+b=0$
↓
$w^T(x''-x')=0$

通过x'和x两点的长度，求其再垂直方向的投影可求得垂线的距离。于是样本空间任意点x到超平面(w,b)的距离r为：

$r=|\frac{w^T}{||w||}|=\frac{|w^T+b|}{||w||}$

假设超平面可以将训练样本正确分类，则对于 $(x_i,y_i)\in D$ ,若 $y_i=+1$ 则 $w^Tx_i+b>0$ ，若 $y_i=-1$ ，则 $w^Tx_i+b<0$ .(正例为+1，负例为-1)
于是令：

$\begin{cases} w^Tx_i+b \geq +1, &{y_i = +1};\\ w^Tx_i+b \leq -1, &{y_i=-1}. \end{cases}$

即y(x)大于0时， $y_i=+1$ ，y(x)小于0时， $y_i=-1$ ，那么下面我们可以将这个式子合着写成 $y_iy(x)$ . $(y(x)=w^Tx_i+b)$

输入空间x一般不会作为模型的输入，而是要将输入空间通过一定的特征转换算法ϕ(x)，转换到特征空间，最后在特征空间中做算法学习。(即将 $x_i$ 替换为ϕ(x))

如图距离超平面最近的这几个训练样本点使上式等号成立，它们被称作“支持向量”。两异类支持向量到超平面距离之和为：

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

它被称为“间隔”。于是使间隔最大，就是求得使 $\gamma$ 最大的参数 $w$ 和 $b$ 。

$min_{w,b} \frac{1}{2} ||w||^2$
$s.t. y_i(w^Tx_i+b) \geq 1，i=1,2,...,m.$

这便是支持向量机的基本型。

对偶问题

对于上面的式子，如何进行求解其最小值呢？需要用到拉格朗日乘子法可得到其“对偶问题”，需要解决的问题是带约束的拉格朗日乘子法问题：

于是要求得式子可转化为（即对SVM基本型中的约束条件都添加拉格朗日乘子 $\alpha_i \geq 0$ ）：

引入KKT公式：

KKT条件：

于是求极小值，分别对w和b进行偏导，并使偏导为零：

将式子(6.9)代入(6.8)即可把w和b消去，再考虑(6.10)的约束。于是得到SVM基本型式子中的对偶问题：

通过上式，我们把求w转化为求 $\alpha$ 。
求得 $\alpha$ 后，求出w和b即可得到模型：

由于求解式子(6.11)用二次规划算法开销过大，于是使用高效算法，SMO算法便是其中具有代表性的算法。
其基本思路是先固定 $\alpha_i$ 之外的所有参数，然后求 $\alpha_i$ 上的极值，每次选择两个变量 $\alpha_i$ 和 $\alpha_j$ ，并固定其他参数。于是SMO不断执行下面两个步骤直到收敛：

1、选取一对需要更新的 $\alpha_i$ 和 $\alpha_j$ ；
2、固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数，求解式子(6.11)获得更新后的 $\alpha_i$ 和 $\alpha_j$

注意只需选取的 $\alpha_i$ 和 $\alpha_j$ 中有一不满足KKT条件，目标函数就会在迭代之后减小。
其具体就不进行赘述，主要是将(6.11)改写成了（因为只考虑 $\alpha_i$ 和 $\alpha_j$ ）：

所以，可消去或求得更新后的和。
b的确定：使用所有支持向量求解的平均值：

核函数

把低微不可分问题转为高维可分问题。如图：

核函数的定义：
核函数（kernel function）就是指K(x,y)=<f(x),f(y)>，其中x和y是n维的输入，f(·)是n维到m维的映射（m>>n），<x,y>是指x和y的内积。

在支持向量机中，虽然说是映射到高维空间中去求内积，但是实际中计算的时候并没有在高维度下计算。只是假设映射到了高维空间，但实际上要的是计算的结果，这个结果在低维空间中计算就可以，然后把这个值映射到高维空间。所以核函数把高维空间的计算转换为低维空间中计算，实际并没有映射到高维空间中去。

如果核函数选择不合适，意味着样本映射到了一个不合适的特征空间，导致性能不佳。

线性核：

高斯核：

软间隔和正则化

软间隔

如图，我们发现某些样本并不配合，即存在离群点。
而软间隔则是允许这些样本不满足约束：

$y_i(w^Tx_i+b) \geq 1$ .

但是我们要使最大化间隔的同时，也要让这些样本尽可能少。于是优化目标变为：

由于

所以不易于求解，故用“替代损失”函数来进行替换：
1、hinge损失：max(0,1-z)
2、指数损失：exp(-z)
3、对率损失：log(1+exp(-z)).

将损失函数替代之后，我们引入松弛变量 $\varepsilon_i \geq 0$ ，于是目标函数变为：

约束条件：

其解法与上面的基本一致：

正则化

其中称为结构风险，即用来描述超平面间隔大小的，第二项称为经验风险，用来表述训练集上的误差，C用于对两项进行折中。上式又被称为“正则化”问题，被称为正则化项，C为正则化常数，范数是常用的正则化项，其中范数倾向于非零分量个数尽量稠密，和则相反。

把一个向量分解成几个方向的向量的和，那些方向上的向量就叫做该向量（未分解前的向量）的分量。

支持向量回归（SVR）

上面我们考虑的是分类问题，接下来考虑一下回归问题。假设可容忍的偏差为 $\epsilon$ ,即当f(x)和y之间的差别绝对值大于 $\epsilon$ 时才计算损失。

如图，当训练样本落在宽度为 $2 \epsilon$ 的间隔带上，才算预测正确。SVR问题与SVM差不多。只是注意间隔带两边的松弛变量可能不一致。
最终SVR可表示为：

核方法

对于SVM与SVR，若不考虑偏移项b，则学得的模型总能表示成核函数 $\kappa (x,x_i)$ 的线性组合。基于核函数的学习方法，统称为核方法。最常见的是通过引入核函数来将线性学习器拓展为非线性学习器。书本上的一个例子就是线性判别分析通过核化对其进行非线性拓展得到“核线性判别分析”。其过程就不行赘述了（其大概就是使用核函数来隐式地表达映射和特征空间，引入核函数对应的核矩阵，并以其和 $\alpha$ 来表示学习目标函数,最后使用线性判别分析求解 $\alpha$ ，再求得投影函数）。

参考阅读：
支持向量机

第六章 支持向量机

间隔与支持向量

对偶问题

核函数

软间隔和正则化

软间隔

正则化

支持向量回归（SVR）

核方法

第六章支持向量机