转载请注明出处:http://blog.csdn.net/luoshixian099/article/details/51073885

$$\color{Blue}{CSDN-勿在浮沙筑高台}$$
支持向量机(Support Vector Machine)曾经在分类、回归问题中非常流行。支持向量机也称为最大间隔分类器，通过分离超平面把原始样本集划分成两部分。

首先考虑最简单的情况：线性可分支持向量机，即存在一个超平面可以把训练样本分开。

1.线性可分支持向量机

1.考虑一个线性二分类的问题；如下左图，在二维平面上有二种样本点x，目标值分别标记为{-1,1}，可以作出无数条直线$w^Tx+b=0$,直线上方的点标记为{+1}的带入直线公式会得到$w^Tx+b>0$,下方的点，标记为{-1}带入直线公式会得到$w^Tx+b<0$，因此可以用$w^Tx+b$的符号决定点的分类，写成决策函数为$f(x,w,b)=sign(w^Tx+b)$把两类点分开，但是个采用哪个直线最好呢？
2.一般来说，当样本点离直线越远，则分类正确的确信度越大；如下右图所示，A,B,C三个样本点都被预测分类到‘×’类中。但是对于A的分类正确的确信度比C大。因为点C里分类直线$w^Tx+b=0$很近，当直线的斜率稍一点变化，即会导致C被分到另一类中。
$\color{red}{综上，我们想要得到的直线是离样本点最远，同时又能保证正确划分的直线}$。

1.1函数间隔与几何间隔

由二维直线$w^Tx+b=0$扩展到高维被称为超平面$(w,b)$。一个点距离超平面的远近可以表示分类预测的确信程度。在超平面$w^Tx+b=0$确定的情况下，$|w^Tx+b|$能够相对地表示点x距离超平面的远近，而且如果分类正确，则$y^{(i)}$与$w^Tx^{(i)}+b$的符号一致,即$y^{(i)}(w^Tx^{(i)}+b)>0$，同时表示分类的正确性以及确信度。
函数间隔：超平面$(w,b)$关于样本点$(x^{(i)},y^{(i)})$的函数间隔为

$$\color{Green}{函数间隔:}\hat{\gamma}^{(i)}=y^{(i)}(w^Tx^{(i)}+b)$$
定义超平面关于样本集S的函数间隔为超平面(w,b)与S中所有样本点的函数间隔的最小值
$$\hat{\gamma}=min_{i=1,2,...m}\ \hat{\gamma}^{(i)}$$
定义$\hat{\gamma}$是为了最大化间隔，$\hat{\gamma}$表示关于超平面与训练集中样本的函数间隔最小值，下面只要最大化$\hat{\gamma}$即可。
注意到函数间隔实际上并不能表示点到超平面的距离，因为当超平面$(w,b)$参数扩大相同的倍数后，如$(2w,2b)$，超平面的位置并没有改变，但是函数间隔也变大了相同的倍数$2\hat{\gamma}^{(i)}$.
几何间隔：

如上图所示：设样本点A坐标为$x^{(i)}$,点A到超平面的垂直距离记为$\gamma^{(i)}$,分离超平面$w^Tx^{(i)}+b=0$的单位法向量为$\frac{w}{||w||}$,因此点B的坐标为$x^{(i)}-\gamma^{(i)}\frac{w}{||w||}$，且点B在直线上，带入直线公式有：
$$w^T(x^{(i)}-\gamma^{(i)}\frac{w}{||w||})+b=0；解得:\gamma^{(i)}=\frac{(w^Tx^{(i)}+b)}{||w||}$$
如果点被正确分类，$y^{(i)}$与$\frac{(w^Tx^{(i)}+b)}{||w||}$的符号一致，由此
$$同理定义 \color{Green}{几何间隔}:\gamma^{(i)}=y^{(i)}\left(\frac{w^Tx^{(i)}+b}{||w||}\right)$$
$$超平面与样本集S的几何间隔为\gamma=min_{i=1,2,...m}\ \gamma^{(i)}$$
几何间隔不随着超平面参数的变化而变化，例如超平面参数(w,b)变为(2w,2b)，函数间隔$\hat{\gamma}^{(i)}$变为$2 \hat{\gamma}^{(i)}$,而几何间隔$\gamma^{(i)}$保持不变。
函数间隔与几何间隔的关系：$\gamma^{(i)}=\frac{\hat\gamma^{(i)}}{||w||}$；$\gamma=\frac{\hat\gamma}{||w||}$，若||w||=1,函数间隔与几何间隔相同。

1.2间隔最大化

如上所述，支持向量机的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。$\gamma$表示分离超平面与训练集中样本的几何间隔的最小值，为了间隔最大化，只需要最大化$\gamma$，同时所有样本的几何间隔必须满足$\gamma^{(i)}\geq\gamma,i=1,2,...,m$;

$$max_{w,b}\ \gamma$$
$$s.t.\ y^{(i)}\left(\frac{w^Tx^{(i)}+b}{||w||}\right)\geq\gamma$$
上述问题，可以转变为一个凸二次规划问题，这是支持向量机的一个重要属性，局部极值即为全局最值。
考虑函数间隔与几何间隔的关系：

上述优化问题中，当超平面参数(w,b)同时变为(2w,2b)，函数间隔也会变为$2\hat{\gamma}$,目标函数的解并不会变化。即$\hat{\gamma}$的取值不影响优化问题的解。因此令$\hat{\gamma}=1$，目标函数变为最大化$\frac{1}{||w||}$，即最小化$||w||^2$，为了后面的求解方便，添加因子$\frac12$也不影响目标函数的解；

上述问题为一个凸优化问题，通过某些优化算法可以求解。下面继续介绍拉格朗日对偶算法，可以更进一步优化上述问题，同时自然引入核函数，推广到高维数据。

1.3拉格朗日对偶性

有时考虑解决原始问题的对偶问题会更高效。
原始问题
$f(w),g_i(w),h_i(w)$均为连续可微：

写出拉格朗日函数，其中$\alpha_i\geq0,\beta\geq0$称为拉格朗日乘子：

定义关于$w$的函数$\theta_P(w)=max_{\alpha,\beta}L(w,\alpha,\beta)$;可以证明如果$w$满足上述约束条件$g_i(w)\leq0,h_i(w)=0$，则有$\theta_P(w)=f(w)$

由此原始问题的约束最优化问题变为极小极大问题：

设原始问题的最优解记为$p^*=min_wf(w)=min_w\theta_p(w)$.
对偶问题
把上述极小极大问题$min_w\ max_{\alpha,\beta}L(w,\alpha,\beta)$,改为极大极小变为对偶问题，即：
定义：

设此极大极小问题的最优解记为$d^*$,可以证明

为了使得对偶问题与原始问题的最优解相等$d^*=p^*$，必须满足下述几个条件，称为KKT条件

1.4最优间隔分类器

回顾原始问题：

写成拉格朗日函数，由于只有不等式约束所以只包含拉格朗日乘子$\alpha_i$：

原始问题最优解$p^*=min_{w,b}\ max_\alpha L(w,b,\alpha)$;对偶问题的最优解$d^*=max_\alpha\ min_{w,b}L(w,b,\alpha)$
对偶问题先求关于参数w,b的最小值，再求关于参数$\alpha$的最大值。
首先，分别对w,b求偏导数并令为0，得：


把上述结果带入拉格朗日函数$L(w,b,\alpha)$

注意到上述是只关于参数$\alpha$的函数，记为$W(\alpha)$,由对偶函数，下一步即最大化$W(\alpha)$

下面的目的是解决上述优化问题，通常采用SMO算法，本篇文章暂不做介绍。假如已经得到最优解$\alpha=(\alpha_1,\alpha_2,...,\alpha_m)$,带回到上面对w求偏导得到的公式，可以得到$w$的值。下面要求得b得值，考虑KKT条件有：$\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]=0，i=1,2..m$,其中必然存在一个$\alpha_j\neq0$,（否则$w=0$,不是原始解）。当$\alpha_j\neq0$时$y^{(i)}(w^Tx^{(i)}+b)=1$,可以解出$b$的代数式，$b=y^{(j)}-\sum_{i=1}^{m}\alpha_iy^{(i)}(x^{(i)},x^{(j)})$，也可以对所有采用满足条件的$b$加和求平均；然后即可得到最佳分类超平面：

根据KKT条件有$\alpha_i[y^{(i)}(w^Tx^{(i)}+b)-1]=0，i=1,2..m$，当$\alpha_i>0$时,必然有$y^{(i)}(w^Tx^{(i)}+b)=1$，即该样本点的函数间隔为1，如下图所示，落在直线$w^Tx+b=\pm1$上，此向量即称为支持向量。对于落在直线$w^Tx+b=\pm1$以内的点，函数间隔$y^{(j)}(w^Tx^{(j)}+b)>1$,必然有$\alpha_j=0$，当计算函数最优分割超平面参数w,b时，这些点对应的$\alpha_j=0$，所以对参数没有影响。只有支持向量，即落在$w^Tx+b=\pm1$上数据影响着最优超平面的计算。

2.线性支持向量机

以上讨论的内容是建立在数据是线性可分的情况，即存在一个分离超平面可以把训练数据分为两部分。实际上数据并不会这么理想，如下图所示，即存在某些样本点不能满足函数间隔大于等于1这个条件。

这时可以为每个数据点设置一个松弛因子$\xi_i\geq0$,使得函数间隔$\gamma_i$加上松弛因子$\xi_i$大于等于1.即$y^{(i)}(w^Tx^{(i)}+w_0)\geq1-\xi_i$,同时对每个松弛因子$\xi_i$支付一个代价$\xi_i$，由此原始问题变为：

C称为惩罚参数(C>0)，C值越大对误分类的惩罚越大；因为当C为无穷大时，即成为了线性可分问题。
采用与线性可分同样的过程，建立拉格朗日函数：

由对偶函数得，首先分别对$w,b,\xi_i$求偏倒数，并令为0，可以得到上面右式，带回到拉格朗日函数中，由于$\mu_i\geq0$,且$\alpha_i=C-\mu_i$,所以有：

由上述KKT条件可以得到：

3.非线性支持向量机

3.1 概念

如上图所示，原始样本数据线性不可分，即无法用一条直线或分离超平面将两类分开。但是对原始数据采用非线性变换$\phi(x)$，非线性变换将原始数据从低维映射到高维，高维上数据就可能变得线性可分。步骤：首先使用非线性变换将原始数据集映射到新空间中，称为特征空间，在特征空间中数据将变的线性可分，然后采用线性支持向量机的方法训练分离超平面参数。但在高维上计算量会急剧增大，会造成维数灾难，自然引入核技巧(kernal trick)。

3.2 核技巧

观察线性支持向量机的对偶问题为：

上述目标函数中，只包含原始数据的内积形式$<x^{(i)},x^{(j)}>=(x^{(i)})^T(x^{(j)})$。由上述分析，只需要找到一个合适的非线性变换$\phi(x)$，将原始数据$x^{(i)}$映射到高维特征空间$\phi(x^{(i)})$中，内积形式变为为$<\phi(x^{(i)}),\phi (x^{(j)})>$。
定义核函数$K(x,z)=\phi(x)^T\phi(z)$，表示两个原始数据$x,z$分别变换到特征空间中的内积值。核技巧的方法即不用构造非线性映射$\phi(x)$而直接给定一个核函数$K(x,z)$,减少了计算量。如下面例子一个核函数等于两个非线性变换的内积：

$$Eg:x,z\in R^n ,\ K(x,z)=(x^Tz)^2=\sum_{i,j=1}^n(x_ix_j)(z_iz_j),对应\phi(x)=(x_1x_1,x_1x_2...,x_1x_n,x_2x_1,...x_nx_n)^T$$
常用几个核函数：
$$多项式核函数：K(x,z)=(x^Tz+1)^q,q>0$$
$$高斯核函数：K(x,z)=exp\left(-\frac{||x-z||^2}{2\sigma^2}\right),称为高斯径向基函数分类器，即上面图中采用方法$$
$$双曲正切函数：K(x,z)=tanh(\beta x^Tz+\gamma)；为满足Mercer定理，一组可能的参数\beta=2,\gamma=1$$

4.SVM后验概率输出

SVM分类器中判决函数$\hat{y}=sign(f(x))=sign(w^Tx+b)$。可以采用f(x)与sigmoid函数结合，把$f(x)=w^Tx+b$解释成$y=1$的对数几率,SVM分类器概率输出(Platt 2000)：

$$p(\hat{y}=1|x)=\sigma(Af(x)+B)$$
参数A,B通过最大释然的方法求解，为防止过拟合，求解A,B参数的样本数据应独立于训练分类的样本。由于在训练分类器阶段，没有考虑后验概率的问题，因此SVM后验概率结果不可靠。

5.几种损失函数的比较

如图：0-1损失是二分类问题的真正损失函数，合页损失与logistic损失是对0-1的损失函数的近似。最小二乘损失强化了分类点在正确分类边界处。

5.1合页损失函数

对于线性支持向量机，目标函数是最小化$\frac12||w||^2+C \sum_{i=1}^m\xi_i$,其中$\xi_i$为每个样本支付的代价；可以定义$\xi_i=[1-y^{(i)}(w^Tx^{(i)}+b)]_+$；下标’+’表示取正值函数，如果$z>0,[z]_+=z;否则[z]_+=0$，因此目标函数可以定义为：

$$min_{w,b}\ \sum_{i=1}^{m}[1-y^{(i)}(w^Tx^{(i)}+b)]_++\lambda||w||^2$$
第一项关于被称为经验损失，定义$z=y^{(i)}(w^Tx^{(i)}+b)$;损失函数为$E(z)=[1-z]_+$，如上图所示，由于图形像一个合页，被称为合页损失。
$$上述目标函数中，当\lambda=\frac1{2C}时，等价于原目标函数\frac12||w||^2+C \sum_{i=1}^m\xi_i$$

5.2logistic回归损失

为了方便叙述，改变一下标记方法，记原始样本数据为$(x_i,t_i)，t\in [1,-1]$,模型预测值为$y(x_i)=w^Tx_i+b$。结合sigmoid函数，可以把$y(x_i)$带入sigmoid函数中，后验概率输出。即$p(t=1|y)=\sigma(y)$,则$p(t=-1|y)=1-\sigma(y)=\sigma(-y)$，综上两种情况$p(t|y)=\sigma(ty)$。采用最大似然函数：

目标函数可以定义为对数似然的负数，同时加上一个二次正则化因子。

$$\sum_{i=1}^{m}ln[1+exp(-y_it_i)]+\lambda||w||^2$$
第一项即为logistic回归损失函数$E_{LR}(yt)=ln[1+exp(-yt)]$

5.3最小二乘损失

与线下回归类似，可以采用最小二乘损失作为目标函数：

$$\sum_{i=1}^{m}(y_i-t_i)^2+\lambda||w||^2$$

6.SVM多分类问题

1.one-versus-the-rest

对于K个类别的问题，在训练样本上，采用SVM训练出K个分类器。每个分类器将训练样本分成$K_i$类与非$K_i$类，然后采用SVM训练出模型。如上图所示，每个分类器只能回答是否属于$K_i$的答案。此种方法会造成一个样本数据属于多个类别的情况，上左图阴影部分。
也可以采用：$y(x)=max_k\ y_k(x)$，即采用最大的函数间隔的那个类别。但不同的分类器有可能尺度不相同，函数距离自然不能作为判断标准。同时，训练样本的不平衡也可能造成分类器有误差。

2.one-versus-one

在K分类的情况下，训练出$\frac{K(K-1)}{2}$个分类器，即每两个类别训练出一个分类器，然后根据$\frac{K(K-1)}{2}$个分类器的结果，采用投票方法给出预测结果。
此种方法依然造成部分数据不属于任何类的问题，上右图阴影部分所示。

3.其他方法

1.一次训练K分类的SVM。参数多，复杂度高；(Weston and Watkins 1999)
2.DAGSVM ;(Platt 2000)

参考：
1. PRML
2. MLAPP
3. CS 229-Andrew Ng