二、SVM

1、什么是SVM

SVM是一种监督式的二分类模型，它通过寻找最大间隔分类平面wx+b=0$wx+b=0$将正负类样本进行区分，对于线性不可分情况，通过核技法将低维空间映射到高维空间，使其线性可分。

2、线性可分SVM

1、决策面

对于线性可分数据集，下图实点表示+1类（正类），空点表示-1类（负类），xi$x_i$表示第i个特征向量，所以(x(i),y(i))$(x^{(i)},y^{(i)})$称为样本点。

学习的目标：在特征空间中找到一个分离超平面，可以将不同类别的实例进行分类

分离超平面：wTx(i)+b=0$w^T{x}^{(i)}+b=0$，由法向量w和截距b决定，法向量指向的一侧为正类。

• 正样本：wTx(i)+b>0$w^T{x}^{(i)}+b>0$

• 负样本：wTx(i)+b<0$w^T{x}^{(i)}+b<0$
  

分离超平面的唯一性：当训练数据集线性可分时，存在无数个分离超平面，在保证决策面方向不变且不会出现错分的情况下移动决策面，会在两侧找到两个极限位置，越过两个极限位置会出现错分现象，两个极限位置的垂直距离就是分类间隔，我们的目标是找到具有最大间隔的决策面。

分类决策函数：f(x)=sign(wTx(i)+b)$f(x)=sign(w^T{x}^{(i)}+b)$

支持向量：最优分类平面对应的两个极限位置所穿过的样本点。

2、函数间隔和几何间隔

2.1 函数间隔

如果一个超平面wTx(i)+b=0$w^T{x}^{(i)}+b=0$可以将数据集正确分类，那么对于每个样本点来说，其函数间隔都大于0，即：

因为对于正样本y(i)=+1$y^{(i)}=+1$，(wTx(i)+b)>0$(w^T{x}^{(i)}+b)>0$,对于负样本y(i)=−1$y^{(i)}=-1$，(wTx(i)+b)<0$(w^T{x}^{(i)}+b)<0$

故如果一个样本被正确分类了，则：

所以函数间隔：

最大化函数间隔：最大化距离超平面最近的样本的函数间隔，也就是最大化函数间隔最小的点到超平面的函数间隔。

利用函数间隔存在的问题：只要成倍增加w和b，就能无限增大函数间隔。

2.2 几何间隔

点到平面的距离：

所以几何间隔为：

几何间隔的意义：所有样本点到分类平面的几何间隔的最小值

最好的分类平面就是最小几何间隔最大的平面

2.3 最优间隔分类器

1、目标函数和约束条件

2、令γ=1$\gamma =1$，目标函数变为平方

• 为什么是12||w||2$\frac{1}{2}||w|{|}^2$？

  ① 1/2 可以在求导中消除平方

  ② ||w||2$||w|{|}^2$的函数特性更好

3、最终要求的问题

2.4 利用拉格朗日求解有约束的优化问题

有约束的最小化问题可以利用拉格朗日函数转化为无约束的问题，为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可分支持向量机的对偶算法。

我们可以构造一个函数，使其在可行域能与原来的目标函数完全一致，在可行域以外的数值非常大，甚至无穷大，则该无约束的新目标函数就和原来的有约束的问题一致了。获得拉格朗日函数之后，使用求导方法依然求解困难，进而需要将极小极大问题通过对偶转化为极大极小问题。

复习拉格朗日函数：

θp(w)${\theta }_p(w)$是对三项和和求极大，也就是调整α,β$\alpha ,\beta$使得等式达到极大值，其中αi>0${\alpha }_i>0$。之后调整w求θp(w)${\theta }_p(w)$的极小值。

当所有约束都满足，即hi(w)=0,gi(w)≤0$h_i(w)=0,g_i(w)\le 0$，无论如何调整α,β$\alpha ,\beta$，后面两个∑+∑$\sum +\sum$的最大值都是0，所以θp(w)=f(w)${\theta }_p(w)=f(w)$。

当所有约束都不满足的时候，如果hi(w)≠0$h_i(w)\ne 0$，则可以调整β$\beta$使得θp(w)${\theta }_p(w)$无穷大；如果gi(w)≥0$g_i(w)\ge 0$，又αi>0${\alpha }_i>0$，故可以令αi${\alpha }_i$无穷大，θp(w)=∞${\theta }_p(w)=\mathrm{\infty }$，没有极小值。

利用对偶方法来对问题进行简化，也就是将极小极大问题，转化为极大极小问题。

2.5 利用拉格朗日求解最有间隔分类器

将约束条件写成拉格朗日不等式约束的形式，获得拉格朗日方程，也就是最终要求的方程。

如何求解目标方程：利用对偶方法，先调整w极小化目标方程，再调整αi${\alpha }_i$求极大值

求解极大极小问题：

带入L$L$

说明拉格朗日函数只取决于训练集样本点的两两内积，和w无关，所以可以将maxαminwL()$ma{x}_{\alpha }mi{n}_{w}L()$变为maxαL()$ma{x}_{\alpha }L()$，注意约束条件。

α>0$\alpha >0$：是边界线上的向量，也就是支持向量
α=0$\alpha =0$：是非边界上的向量，非支持向量

也就是对于分类模型f(x)=wTx+b=∑αiy(i)x(i)x+b$f(x)=w^{T}x+b=\sum {\alpha }_i{y}^{(i)}{x}^{(i)}x+b$，每个新来的数据点要和所有i个已有的数据点做内积，但是非支持向量点的α=0$\alpha =0$，所以不起作用。

新来的数据点要和所有支持向量做内积

2.6 SMO算法（序列最小最优化算法）

坐标上升法：对于要优化的参数，先固定其他参数，优化一个参数α1${\alpha }_1$，优化到最好，再优化其他参数。

SMO算法：

支持向量机问题可以转化为求解凸二次规划问题，这样的问题具有全局最优解，并且有许多算法可以用于这个问题的求解，但是当训练样本容量很大时，这些算法往往变得非常低效，以至于无法使用。

SMO算法是将大优化问题分解为多个小优化问题来求解的。这些小优化问题往往很容易求解，并且对它们进行顺序求解的结果与将它们作为整体来求解的结果完全一致的。在结果完全相同的同时，SMO算法的求解时间短很多。

因为有约束条件，所以需要选两个变量进行优化，因为如果改变一个α$\alpha$的值，肯定需要调整另一个α$\alpha$的值使得约束条件仍然满足。

举例：假设α1,α2${\alpha }_1,{\alpha }_2$为两个变量，α3,α4,...,αN${\alpha }_3,{\alpha }_4,...,{\alpha }_N$固定，α1y(1)+α2y(2)+∑mi=3αiy(i)=0${\alpha }_1{y}^{(1)}+{\alpha }_2{y}^{(2)}+\sum _{i=3}^m{\alpha }_i{y}^{(i)}=0$

即：α2=y(2)(−∑mi=3αiy(i)−α1y(1))${\alpha }_2=y^{(2)}(-\sum _{i=3}^m{\alpha }_i{y}^{(i)}-{\alpha }_1{y}^{(1)})$

也就是α2${\alpha }_2$确定，α1${\alpha }_1$也随之确定。

SMO算法的目标是求出一系列alpha和b，一旦求出了这些alpha，就很容易计算出权重向量w并得到分隔超平面。

SMO算法的工作原理是：每次循环中选择两个alpha进行优化处理。一旦找到了一对合适的alpha，那么就增大其中一个同时减小另一个。这里所谓的”合适”就是指两个alpha必须符合以下两个条件，条件之一就是两个alpha必须要在间隔边界之外，而且第二个条件则是这两个alpha还没有进行过区间化处理或者不在边界上。

3、核技法

对在低维空间线性不可分的数据集，通过映射到高维空间，从而线性可分

本来做空间变换需要对空间中的所有点都做变换，但是这种计算太复杂，于是我们不显示处理数据，而是从模型上直接体现。

用线性分类方法求解非线性问题分为两步：

1）使用一个变换将原空间的数据映射到新空间
2）在新空间用线性分类学习方法从训练数据中学习分类模型

3.1 核函数

设χ$\chi$为输入空间，又设H$H$为特征空间（希尔伯特空间），如果存在一个从χ$\chi$到H$H$的映射：ϕ(x)=χ→H$\varphi (x)=\chi \to H$

使得所有的x,z∈χ$x,z\in \chi$，函数K(x,z)$K(x,z)$满足条件：K(x,z)=ϕ(x)⋅ϕ(z)$K(x,z)=\varphi (x)\cdot \varphi (z)$

则K(x,z)$K(x,z)$称为核函数，ϕ(x)$\varphi (x)$称为映射函数。

3.2 核技巧的应用：

SVM核函数的选择对于其性能的表现有至关重要的作用，尤其是针对那些线性不可分的数据，因此核函数的选择在SVM算法中就显得至关重要。对于核技巧我们知道，其目的是希望通过将输入空间内线性不可分的数据映射到一个高纬的特征空间内使得数据在特征空间内是可分的，我们定义这种映射为ϕ(x)$\varphi (x)$，那么我们就可以把求解约束最优化问题变为

但是由于从输入空间到特征空间的这种映射会使得维度发生爆炸式的增长，因此上述约束问题中内积ϕi⋅ϕj${\varphi }_i\cdot {\varphi }_j$
的运算会非常的大以至于无法承受，因此通常我们会构造一个核函数

从而避免了在特征空间内的运算，只需要在输入空间内就可以进行特征空间的内积运算。通过上面的描述我们知道要想构造核函数κ ，我们首先要确定输入空间到特征空间的映射，但是如果想要知道输入空间到映射空间的映射，我们需要明确输入空间内数据的分布情况，但大多数情况下，我们并不知道自己所处理的数据的具体分布，故一般很难构造出完全符合输入空间的核函数，因此我们常用如下几种常用的核函数来代替自己构造核函数：

• 线性核函数
  

  k(x,xi)=x⋅xi$$k(x,x_i)=x\cdot x_i$$
  
  线性核，主要用于线性可分的情况，我们可以看到特征空间到输入空间的维度是一样的，其参数少速度快，对于线性可分数据，其分类效果很理想，因此我们通常首先尝试用线性核函数来做分类，看看效果如何，如果不行再换别的

• 多项式核函数
  

  k(x,xi)=((x⋅xi)+1)d$$k(x,x_i)=((x\cdot x_i)+1)d$$

多项式核函数可以实现将低维的输入空间映射到高纬的特征空间，但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大或者无穷小，计算复杂度会大到无法计算。

• 高斯（RBF）核函数

高斯径向基函数是一种局部性强的核函数，其可以将一个样本映射到一个更高维的空间内，该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对于多项式核函数参数要少，因此大多数情况下在不知道用什么核函数的时候，优先使用高斯核函数。

• sigmoid核函数

采用sigmoid核函数，支持向量机实现的就是一种多层神经网络。

因此，在选用核函数的时候，如果我们对我们的数据有一定的先验知识，就利用先验来选择符合数据分布的核函数；如果不知道的话，通常使用交叉验证的方法，来试用不同的核函数，误差最下的即为效果最好的核函数，或者也可以将多个核函数结合起来，形成混合核函数。在吴恩达的课上，也曾经给出过一系列的选择核函数的方法：

• 如果特征的数量大，样本数量较少，则选用LR或者线性核的SVM；

  样本少，但是特征数目大，表示特征空间维度很高，一般认为是线性可分的

• 如果特征的数量小，样本的数量正常，则选用SVM+高斯核函数；

  特征少则疼我特征空间维度较低，可以用高斯核将其映射到高维空间

• 如果特征的数量小，而样本的数量很大，则需要手工添加一些特征从而变成第一种情况。

交叉验证：先拿出来小的数据集应用不同的核来验证哪个核比较好，然后再应用在大数据集上去。

4、软间隔分类器

针对高维空间仍然线性不可分的数据，提出了软间隔分类器，就是给目标函数加惩罚项，允许某些数据点用于小于1的几何间隔，但是这些点要受到惩罚。

ξi${\xi }_i$表示小于1的程度

C表示加载惩罚项的系数：

① C值越大，对误差的惩罚越大，也就是越不能容忍误差，容易出现过拟合。

② C越小，对误差的惩罚越小，不再关注分类是否正确，只要求间隔越大越好，容易欠拟合。

RBF和的σ$\sigma$和参数gamma的关系：

RBF的幅宽为σ$\sigma$，它会影响每个支持向量对应的高斯的作用范围，从而影响泛化性能：

① σ$\sigma$越大，gamma$gamma$越小，作用范围越大，高斯分布覆盖范围越大，对未知样本有较好的泛化能力，但如果σ$\sigma$过大，平滑效果太大，训练集和测试集都没法得到好的结果。
② σ$\sigma$越小，gamma$gamma$越大，作用范围越小，高斯分布是高高瘦瘦的，只会作用于支持向量样本附近，对未知样本分类效果较差，容易过拟合。

软间隔分类器和硬间隔分类器的区别，α$\alpha$的限制条件变多了，0≤αi≤C$0\le {\alpha }_i\le C$。

5、SVM的性质

6、合页损失函数

对于线性支持向量机来说，其模型的分离超平面为wTx+b=0$w^{T}x+b=0$，决策函数f(x)=sign(wTx+b)$f(x)=sign(w^{T}x+b)$，其学习策略为软间隔最大化，学习算法为凸二次规划。

线性支持向量机还有另一种解释，就是最小化以下目标函数：

第一项为经验损失或经验风险，第二项是系数为λ$\lambda$的w的范数，是正则化项。

函数

称为合页损失函数，下标+表示取正值的函数：

也就是说，当样本点被正确分类且函数间隔大于1时，损失为0，否则损失为1−y(wTx+b)$1-y(w^{T}x+b)$。

合页损失函数图示：横轴是函数间隔，纵轴是损失

黑色实线为Hinge Loss：

① 当函数间隔小于1的时候，离1越远，损失越大

② 当函数间隔大于1的时候，损失为0

图中还画出0-1损失函数，可以认为它是二类分类问题的真正的损失函数，而合页损失函数是0-1损失函数的上界。由于0-1损失函数不是连续可导的，直接优化由其构成的目标函数比较困难，可以认为线性支持向童机是优化由0-1损失函数的上界（合页损失函数）构成的目标函数。这时的上界损失函数又称为代理损失函数（surrogate loss function)。

图中虚线显示的是感知机的损失函数支持向量机185.png。这时，当样本点支持向量机122.png被正确分类时，损失是0,否则损失是支持向量机123.png。相比之下，合页损失函数不仅要分类正确，而且确信度足够高时损失才是0。也就是说，合页损失函数对学习有更高的要求。

7、多分类问题

7.1 一对多

one-versus-rest

N类就需要N个分类器

训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。

假如我有四类要划分（也就是4个Label），他们是A、B、C、D。

　　于是我在抽取训练集的时候，分别抽取

　　（1）A所对应的向量作为正集，B，C，D所对应的向量作为负集；

　　（2）B所对应的向量作为正集，A，C，D所对应的向量作为负集；

　　（3）C所对应的向量作为正集，A，B，D所对应的向量作为负集；

　　（4）D所对应的向量作为正集，A，B，C所对应的向量作为负集；

　　使用这四个训练集分别进行训练，然后的得到四个训练结果文件。

　　在测试的时候，把对应的测试向量分别利用这四个训练结果文件进行测试。

　　最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x)。

　　于是最终的结果便是这四个值中最大的一个作为分类结果。

优点：

训练k个分类器，个数较少，其分类速度相对较快。

缺点：

①每个分类器的训练都是将全部的样本作为训练样本，这样在求解二次规划问题时，训练速度会随着训练样本的数量的增加而急剧减慢；

②同时由于负类样本的数据要远远大于正类样本的数据，从而出现了样本不对称的情况，且这种情况随着训练数据的增加而趋向严重。解决不对称的问题可以引入不同的惩罚因子，对样本点来说较少的正类采用较大的惩罚因子C；

③还有就是当有新的类别加进来时，需要对所有的模型进行重新训练。

7.2 一对一

N类需要N(N−1)2$\frac{N(N-1)}{2}$个分类器

其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计k(k−1)/2$k(k-1)/2$个SVM。

当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。

Libsvm中的多类分类就是根据这个方法实现的。

示例：

假设有四类A,B,C,D四类。在训练的时候我选择A,B; A,C; A,D; B,C; B,D;C,D所对应的向量作为训练集，然后得到六个训练结果，在测试的时候，把对应的向量分别对六个结果进行测试，然后采取投票形式，最后得到一组结果。

　　投票是这样的：
　　A=B=C=D=0;
　　(A,B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;
　　(A,C)-classifier 如果是A win,则A=A+1;otherwise, C=C+1;
　　…
　　(C,D)-classifier 如果是A win,则C=C+1;otherwise,D=D+1;
　　The decision is the Max(A,B,C,D)

评价：这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的。

优点：不需要重新训练所有的SVM，只需要重新训练和增加语音样本相关的分类器。在训练单个模型时，相对速度较快。

缺点：所需构造和测试的二值分类器的数量关于k成二次函数增长，总训练时间和测试时间相对较慢。