支持向量机(SVM)原理分析

版权说明：码字不易，转载请注明出处：http://blog.csdn.net/flying_sfeng/article/details/79055411
支持向量机(SVM)是一种二分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器。支持向量机学习的基本思想是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。
对于下图线性可分的情况，SVM就是为了找到一个最优的超平面，将正负样本尽可能地分开来，也就是说，我们要找到分开样本的最大间隔。

先了解一下函数间隔和几何间隔。
函数间隔：

其中，y(i)$y^{(i)}$为标签(y∈{−1,1})$(y\in \{-1,1\})$
当y(i)=1$y^{(i)}=1$时，为了使间隔最大，wTx+b$w^{T}x+b$必须是一个尽可能大的正数，这样才能确保分类正确的确信度最高。同样地，当y(i)=−1$y^{(i)}=-1$时，为了使间隔最大，wTx+b$w^{T}x+b$必须是一个尽可能大的负数。
而我们的目的是最大化所有训练样本的最小间隔，即给定一个训练集S={(x(i),y(i));i=1,...,m}$S=\{(x^{(i)},y^{(i)});i=1,...,m\}$,我们定义在S下(w,b)$(w,b)$的函数间隔为所有训练样本的函数边界的最小值，则：

几何间隔：
如图，

假设γ(i)${\gamma }^{(i)}$为我们要求的几何间隔，我们知道，w||w||$\frac{w}{||w||}$是w$w$方向上的单位向量，给定A:x(i)$x^{(i)}$,可以得到B：x(i)−γ(i)∗w||w||$x^{(i)}-{\gamma }^{(i)}\ast \frac{w}{||w||}$,又因为B位于决策边界，所以B也满足wTx+b=0$w^{T}x+b=0$，代入得：

移项得到：

这只是一个方向上的，为了满足正负样本y=±1$y=\pm 1$ 的情况，更一般的，我们可以令

因此，几何间隔与函数间隔的关系为：

当||w||=1$||w||=1$ 时，几何间隔就等于函数间隔。
同样地，几何间隔为所有样本距离分界面的间隔的最小值，则

间隔最大化：
间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面，这意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点(离超平面最近的点)也有足够的确信度将它们分开。
下面考虑如何求得一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：

即我们希望最大化超平面(w,b)关于训练数据集的几何间隔γ$\gamma$, γ$\gamma$ 表示的是训练数据集中的最小几何间隔，所以约束条件表示的是超平面(w,b)关于每个训练样本点的几何间隔至少是γ$\gamma$.
考虑到几何间隔与函数间隔的关系，可将这个问题改写为：

将不等式两边的||w||$||w||$ 约去，即：

函数间隔γ^$\hat{\gamma }$的取值并不影响最优化问题的解。为什么呢？事实上，假设将w和b按比例改变成λw$\lambda w$ 和λb$\lambda b$ ,这时函数间隔成为λγ^$\lambda \hat{\gamma }$。把λw$\lambda w$，λb$\lambda b$，λγ^$\lambda \hat{\gamma }$分别代入上面的优化问题可以得到：

两个式子的λ$\lambda$ 都可以约去，因此，函数间隔的这一改变对上述目标函数的优化没有影响，对不等式约束也没有影响。也就是说，它产生了一个等价的最优化问题。所以，我们就可以取γ^=1$\hat{\gamma }=1$, 将γ^=1$\hat{\gamma }=1$ 代入上面的最优化问题中，考虑到最大化1||w||$\frac{1}{||w||}$ 和最小化12||w||2$\frac{1}{2}||w|{|}^2$ 是等价的，于是就得到了下面的线性可分支持向量机学习的最优化问题：

如果求出了上述约束最优化问题的解w∗,b∗$w^{\ast },b^{\ast }$, 那么就可以得到最大间隔超平面w∗x+b∗=0$w^{\ast }x+b^{\ast }=0$ 及分类决策函数f(x)=sign(w∗x+b∗)$f(x)=sign(w^{\ast }x+b^{\ast })$, 即线性可分支持向量机模型。
接下来考虑对偶问题：
我们暂时先不管以上的优化式子，考虑一般化的条件：

这是含有等式约束的最小化问题，可以用拉格朗日乘子方法求解。
以上含等式约束的问题可以转换为以下拉格朗日函数：

其中βi${\beta }_i$ 为拉格朗日乘子，令L$L$的导数等于零：

可以求出w$w$和β$\beta$.
接下来我们看一下含有不等式约束的最优化问题。原问题：

为了解决这个不等式约束问题，我们定义以下的拉格朗日函数：

其中αi,βi${\alpha }_i,{\beta }_i$为拉格朗日乘子。
考虑以下等式：

当违背约束时（即存在i,$i,$ 使得gi(w)>0或者hi(w)≠0$g_i(w)>0或者h_i(w)\ne 0$），

而当不等式约束跟等式约束都满足时，θp(w)=f(w)${\theta }_p(w)=f(w)$,即：

这就是要最大化拉格朗日函数的原因。当不等式约束跟等式约束都满足要求时，θp(w)=f(w);${\theta }_p(w)=f(w);$ 当违背约束时, θp(w)${\theta }_p(w)$ 趋向于无穷大，式子无解，这样做相当于把约束放到了上述式子中了。同时，我们最小化f(w)$f(w)$，就相当于最小化θp(w)${\theta }_p(w)$.即：

p∗$p^{\ast }$即为原问题的解。
接下来我们最小化拉格朗日函数，

由此我们可以列出对偶优化问题：

d∗$d^{\ast }$即为对偶问题的解。
原问题跟对偶问题有什么关系呢？关系如下：

当拉格朗日乘子的解w∗,α∗,β∗$w^{\ast },{\alpha }^{\ast },{\beta }^{\ast }$满足以下的KKT条件时，d∗=p∗$d^{\ast }=p^{\ast }$:

下面，将证明原问题与对偶问题的关系的由来。
我们再次写下拉格朗日函数：

以下式子恒成立(sup$sup$表示上确界，inf$inf$表示下确界)：

令：

所以，有：

因此:

即：

等式成立的条件是：L(w,α,β)$L(w,\alpha ,\beta )$的第二项跟第三项为零，即：

也就是说，当变量满足KKT条件时，对偶问题的解等于原问题的解。

优化问题的求解：
再次写下我们要求解的优化问题：

拉格朗日函数如下：

我们通过求解对偶问题来得到原问题的解，当然前提是必须满足KKT条件。
对偶问题如下：

对于这个问题，我们先通过最小化L(w,α,β)$L(w,\alpha ,\beta )$ 来求出w,b(固定α)$w,b(固定\alpha )$，具体做法是使L对w,b的导数为零。对w求导：

即：

对b求导：

将上述两式代入到拉格朗日函数中，可以得到：

因此，优化问题可写成下列形式：

这就变成了对α$\alpha$ 的单变量优化问题。对α$\alpha$的求解可以使用SMO算法，我们后面会讲到。假设我们已经求解出α$\alpha$， 那么我们可以通过w=∑mi=1αiy(i)x(i)$w=\sum _{i=1}^m{\alpha }_i{y}^{(i)}{x}^{(i)}$求出w，但是b该怎么求解呢？
当i为支持向量时，我们可以得到函数间隔：y(i)(w∗Tx(i)+b)=γ^$y^{(i)}({w^{\ast }}^T{x}^{(i)}+b)=\hat{\gamma }$,即：

以上两式相加可以得到b:

因此，对于一个待预测的样本，我们可以得到：

当wTx+b>0$w^{T}x+b>0$ 时我们把该样本预测为正样本，wTx+b≤0$w^{T}x+b\le 0$ 时预测为负样本。

核函数：
在前面的讨论中，我们假设训练样本时线性可分的，即存在一个划分超平面能将训练样本正确分类。然而在现实任务中，原始样本空间内也许并不存在一个能正确划分两类样本的超平面。对于这样的问题，可将样本从原始空间映射到一个更高维的特征空间，使得样本在这个特征空间内线性可分。幸运的是，如果原始空间是有限维，即属性数有限，那么一定存在一个高维特征空间使样本可分。(参考《机器学习》6.3节 周志华著)
核函数的定义：
设X是原始输入空间，H为特征空间（希尔伯特空间），如果存在一个从X到H 的映射：

使得对所有x,z∈X,$x,z\in X,$ 函数K(x,z)$K(x,z)$满足条件：

则称K(x,z)$K(x,z)$ 为核函数，ϕ(x)$\varphi (x)$ 为映射函数，式中⟨ϕ(x),ϕ(z)⟩$⟨\varphi (x),\varphi (z)⟩$为ϕ(x)$\varphi (x)$和ϕ(z)$\varphi (z)$的内积。
核技巧的想法是：在学习与预测中只定义核函数K(x,z)$K(x,z)$，而不显式地定义映射函数ϕ$\varphi$。通常，直接计算K(x,z)$K(x,z)$ 比较容易，而通过ϕ(x)$\varphi (x)$和ϕ(z)$\varphi (z)$计算K(x,z)$K(x,z)$并不容易。这是因为，ϕ$\varphi$是原始输入空间X到特征空间H地映射，特征空间H一般是高维的，甚至是无穷维的。
通俗点讲，对于在原始空间内线性不可分的情况，我们可以将原始空间映射到高维空间，高维空间的内积计算使用核函数代替。
因此，我们的目标函数的对偶问题可以写成下列形式：

求解后即可得到：

那么，什么样的函数能做核函数呢？我们有下面的定理：
定理：令X$X$为原始输入空间，k(x(i),x(j))$k(x^{(i)},x^{(j)})$ 是定义在X×X$X\times X$ 上的对称函数，则k$k$是核函数当且仅当对于任意数据D=x(1),x(2),...,x(m)$D=x^{(1)},x^{(2)},...,x^{(m)}$, 核矩阵K$K$总是半正定的：

定理表明，只要一个对称函数所对应的核矩阵半正定，它就能作为核函数使用。
定理证明：如果k$k$ 是一个有效的核函数，那么k(x(i),x(j))=ϕ(x(i))Tϕ(x(j))==ϕ(x(j))Tϕ(x(i))=k(x(j),x(i))$k(x^{(i)},x^{(j)})=\varphi (x^{(i)}{)}^T\varphi (x^{(j)})==\varphi (x^{(j)}{)}^T\varphi (x^{(i)})=k(x^{(j)},x^{(i)})$, 因此核函数k$k$必须是对称的。另外，对于任意向量z$z$,我们有：

因此，核矩阵K$K$必须是半正定的。证毕。
常用核函数：

线性不可分的支持向量机
在前面的讨论中，我们一直假定训练样本在样本空间或特征空间中是线性可分的，即存在一个超平面能将不同类的样本完全分开。然而，在现实任务中往往很难确定合适的核函数使得训练样本在特征空间中线性可分；退一步说，即使恰好找到了某个核函数使训练集在特征空间中线性可分，但这样划分的结果会更容易造成过拟合。
线性不可分意味着某些样本点(x(i),y(i))$(x^{(i)},y^{(i)})$ 不能满足函数间隔大于等于1的约束条件。为了解决这个问题，可以对每个样本点(x(i),y(i))$(x^{(i)},y^{(i)})$引进一个松弛变量ξi${\xi }_i$, 使函数间隔加上松弛变量大于等于1，这样，约束条件变为：

同时，对每一个样本，支付一个代价ξi${\xi }_i$， 目标函数由原来的12||w||2$\frac{1}{2}||w|{|}^2$ 变为：

其中，C>0$C>0$称为惩罚因子，C值大时对误分类的惩罚增大。最小化目标函数包含两层含义：为了使目标函数尽可能小，C应该取一个较小的值；同时为了使误分类的样本尽可能少，C应该取一个较大的值。所以，惩罚因子C的取值必须在这两者做个折中。
线性不可分的线性支持向量机的学习问题变成一个凸二次规划问题(原问题)：

该问题的拉格朗日函数是：

其中，αi≥0,μi≥0${\alpha }_i\ge 0,{\mu }_i\ge 0$是拉格朗日乘子。
令L(w,b,α,ξ,μ)$L(w,b,\alpha ,\xi ,\mu )$对w,b,ξ$w,b,\xi$的偏导为零可得：

将以上等式代入拉格朗日函数中可得到对偶问题：

同样地，对于软间隔支持向量机，也必须满足KKT条件：

因此，对任意训练样本(x(i),y(i))$(x^{(i)},y^{(i)})$, 总有αi=0${\alpha }_i=0$或y(i)f(x(i))−1+ξi=0$y^{(i)}f(x^{(i)})-1+{\xi }_i=0$. 若αi=0${\alpha }_i=0$， 则该样本不会对f(x)$f(x)$有任何影响；若αi>0${\alpha }_i>0$，则必有y(i)f(x(i))−1+ξi=0$y^{(i)}f(x^{(i)})-1+{\xi }_i=0$, 则该样本是支持向量：由于C=αi+μi$C={\alpha }_i+{\mu }_i$,若αi<C${\alpha }_i<C$,则μi>0${\mu }_i>0$,进而有ξi=0${\xi }_i=0$，则该样本恰好落在间隔边界上;若αi=C${\alpha }_i=C$,则μi=0${\mu }_i=0$, 此时若0<ξi<1$0<{\xi }_i<1$,则该样本落在间隔边界与分离超平面之间；若ξi=1${\xi }_i=1$,则该样本恰好落在分离超平面上；若ξi>1${\xi }_i>1$,则该样本落在分离超平面误分一侧。同样，软间隔支持向量机的最终模型仅与支持向量有关。
线性支持向量机学习算法步骤：
输入：训练数据集T=(x(1),y(1)),(x(2),y(2)),...,(x(N),y(N))$T=(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),...,(x^{(N)},y^{(N)})$,其中x(i)∈X=Rn,y(i)∈Y={−1,+1}, i=1,2,...,N;$x^{(i)}\in X=R^n,y^{(i)}\in Y=\{-1,+1\},i=1,2,...,N;$
输出：分离超平面核分类决策函数。
（1）选择惩罚参数C>0$C>0$, 构造并求解凸二次规划问题：

求得最优解α∗=(α∗1,α∗2,...,α∗N)T${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast }{)}^T$.
（2）计算w∗=∑Ni=1α∗iy(i)x(i)$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}^{(i)}{x}^{(i)}$
选择α∗${\alpha }^{\ast }$的一个分量α∗j${\alpha }_j^{\ast }$满足条件0<α∗j<C$0<{\alpha }_j^{\ast }<C$,计算

求得分离超平面

分类决策函数：

步骤（2）中，因为存在多个α∗j${\alpha }_j^{\ast }$，所以b$b$的解并不是唯一的，所以实际计算时可以取在所有符合条件的样本点上的平均值。

SMO算法（序列最小最优化算法）：
SMO算法要求解如下凸二次规划的对偶问题：

在这个问题中，变量时拉格朗日乘子，一个变量αi${\alpha }_i$对应于一个样本点(x(i),y(i))$(x^{(i)},y^{(i)})$;变量的总数等于训练样本容量N。
SMO算法时一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解。子问题有两个变量，一个是违反KKT条件最严重的哪一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
因此，在参数初始化后，SMO算法不断执行以下两个步骤直至收敛：
（1）选取一对需要更新的变量αi${\alpha }_i$和αj${\alpha }_j$；
（2）固定αi${\alpha }_i$和αj${\alpha }_j$以外的参数，求解目标函数后获得更新后的αi${\alpha }_i$和αj${\alpha }_j$。（因为存在约束条件∑mi=1αiy(i)=0$\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$，实际的变量只有一个，对该变量求导等于零可以得到该变量的解，将其代入约束条件可以得到另一个变量的解)
整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。时间关系，这里不做展开了，感兴趣的读者可以参阅《统计学习方法》7.4节 （作者：李航），作者讲的很详细，推荐阅读。

花了很长时间，终于把这部分内容总结完了。以上公式纯手打，若有错误或者理解不当的，烦请指出。
参考：
吴恩达 CS229笔记
《统计学习方法》 李航著
《机器学习》 周志华著