支持向量机Support Vector Machine

2018-05-16 本文已影响0人 Vince_zzhang

支持向量机：是一种监督式学习的方法，可广泛地应用于统计分类以及回归分析。支持向量机属于一般化线性分类器，这族分类器的特点是他们能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。

目标: find largest-margin separating hyperplane

Consider x', x'' on hyperplane:

want： distance(x, b, w), with hyperplane w^(T) x' +b = 0, w is normal vector

(x''-x') vector on hyperplane

设w={x1,x2,x3}, ||w||_2=x1^2+x2^2+x3^2 的开根号。欧几里得范数L2 norm（也叫做向量的模），常用可省略下标2。根据①，w^T * x' = -b 可转换带入得最后结果

向量在向量上的投影，即用来解释向量在法向量上的投影为点到平面距离

SVM目标函数：

数据集（X1，Y1）(X2，Y2) ... (Xn, Yn）

根据分类函数和Y值设定，距离超平面w^Tx+b=0的最近的点一定在|w^Tx+b | = 1 这两条线的外侧（margin最小的情况下是点在线上），所以一定有yi * y(xi) >= 1

备注：此处margin只计算了一半，是为了解释之后的点到直线的距离公式。实际margin应该是2/||w||。

Y的样本类别：

当X为正例：Y = 1; 当X为负例：Y = -1

分类函数

y(xi) >= 1 <=> yi = 1 ①

y(xi) <= -1 <=> yi = -1 ②

可推导出 yi * y(xi) >= 1 ③

在只计算单边的情况下，找到一条线（w和b），使得离该线最近的点能够最远。argmax(w,b)使得min(最近的点到该线的距离)

分子是距离函数由③的转换：w^Tx+b的绝对值可以用yi* (w^Tx+b)表示

距离函数(单边）

对于线（w，b），有条件③：

目标函数，求i使得点最近，求w，b使得距离最大，此时目标函数应该考虑双边情况，即margin是 w^Tx+b = 1 和 w^Tx+b = -1 之间的距离，所以目标函数是上文距离函数的2倍

代入到上式argmax{}可得min方程的最小值就是1，所以目标函数可化简为：

目标函数。且 yi (w^T * φ(xi) + b) >= 1

且 yi (w^T * φ(xi) + b) >= 1

极大值不好求，转换成求最小值:

且 yi (w^T * φ(xi) + b) >= 1。注*：通过平方，可以便于求导得min

拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是用来解决约束优化的问题，在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。前提是：只有当目标函数为凸函数时，使用这两种方法才保证求得的是最优解。

现有一个二维的优化问题：

①. min f(x,y)； s.t.g(x,y)=c

我们可以画图来辅助思考

箭头表示斜率

对于最优值的解，一定是约束函数与目标函数的切点处产生。f和g的法线方向刚好相反（梯度共线），即

②. ▽[f(x,y)+λ(g(x,y)−c)] = 0；λ ≠ 0

而满足②的点同时又是③的解。

③. min F(x,y) = f(x,y)+λ(g(x,y)−c)

所以①和③等价。

新方程F(x,y)在达到极值时与f(x,y)相等，因为F(x,y)达到极值时g(x,y)−c总等于零。

拉格朗日乘子法Lagrange Multiplier：

min f(x)

s.t. hi(x) = 0, i = 1,...,m （等式限制）

min L(a,x) = f(x) + b * hi(x)， b ≠ 0，b是拉格朗日乘子

如果有n个限制式，则多引入n个参数，例：再多一个不等式限制 gi(x) <= 0, 则：

L(a,b,x) = f(x) + b * hi(x) + a * gi(x)

KKT(Karush-Kuhn-Tucker)条件： 是解决最优化问题的时用到的一种方法。最优化问题通常是指对于给定的某一函数，求其在指定作用域上的全局最小值。KKT条件是拉格朗日乘子法的泛化。

1. 各个参数a,b,x的偏导数=0，是拉格朗日函数取到极值的必要条件

2. a * gi(x) = 0， 互补松弛条件

3. a >= 0，对于不等式限制条件。 *解释：因为g(x) <= 0，若使得第二项a * g(x)小于等于0就必须使得系数a >= 0。

4. b ≠ 0，对于等式限制条件

5. 不等式限制条件g(x)"<="0, 必须是"<="符号

6. 等式条件无要求 hi(x) = 0

将目标函数转换成拉格朗日乘子法标准格式：

注* w不方便求解，通过拉格朗日乘子法转换为求a

yi (w^T * φ(xi) + b) >= 1转换为1 - yi (w^T * φ(xi) + b) <= 0

对偶问题Duality ：http://www.cnblogs.com/zhangchaoyang/articles/2726873.html 有更具体的推导。

求最大中最小转换为求最小中最大

将对原问题1/2||⍵||^2的最小化问题转换成了对L(⍵,b,α)的最小化，我们的主要目的是求出参数⍵和b，从而获取到分割超平面的方程。我们将对L(⍵,b,α)进行最小化转换成它的对偶问题，先固定α参数，令对L(⍵,b,α)函数的⍵和b求偏导为0（即令w,b极小，求极大a）可得两个条件：

④

⑤

代入④⑤至L(w,b,a):

完成求解min_w,b L(w,b,a)

求a的极大值：

条件：∑ ai * yi = 0， ai >= 0

不方便求极大值，所以转换为求极小值：

条件：∑ ai * yi = 0， ai >= 0

实例：

有3个点: x1(3,3), x2(4,3), x3(1,1), 已知x1,x2 为正例，所以y1=y2=1, x3为负例，y3=-1。

样本：x1(3,3,1), x2(4,3,1), x3(1,1,-1)

求解：

条件：a1+a2-a3=0; ai>=0, i=1,2,3

xi * xj = 向量的内积：xi1 * xj1 + xi2 * xj2

根据条件可知：a3 = a1 + a2

代入后可得：4a1^2 + 13/2a2^2 + 10a1a2 - 2a1 -2a2

分别对参数进行求导：a1=1.5 a2=-1, 不满足条件ai >= 0, i = 1,2,3

最终的解应该为边界？上的点： a1=0 a2=-2/13, 代入原式a3=-0.154 排除

a1=0.25 a2=0, 代入原式a3=0.25

最小值在 a = (0.25,0,0.25）处取得：

根据 wi = ∑ ai yi φ(xi) 可以求得 w1 = w2 = 0.5

根据 yi = wi^T * φ(xi) + b， w = ∑ ai yi φ(xi), 可以代入 yi = [∑ ai yi φ(xi) ] ^ T φ(xj) 得出b=-2

最终得到的超平面为：0.5 x + 0.5 y - 2 =0

注*：最小值在 a = (0.25,0,0.25），因为a2=0，说明该超平面的建立与a2无关，同时也说明超平面只跟距离超平面最近(不同类y)的点有关。

软间隔soft margin：

特例点左上，o

为了使得分类器更准确，超平面不得不从虚线变成为实线，尽管模型更准确了，但是最近点到分割面的距离却便近了，这里引出软间隔概念，用来解决模型对错误样例的包容性问题

引入松弛因子slack variables ξ，惩罚因子penalty term C（自己确定）:

将原来的假设 yi (w xi + b) >= 1转换为 yi (w xi + b) >= 1- ξi；0 <= ξ <= 1 目的是为目标函数引入一个损失

新的目标函数, 1- ξi -yi (w xi + b) <= 0, -ξ <= 0

惩罚因子的大小决定了对离群点的容忍程度（松弛的程度）

当C趋近于无穷大时：分类严格不能有错误

当C趋近于很小的时候：可以容忍更大错误

解释：C越大，在函数求最小值的前提下，松弛因子ξ就得越小，yi (w xi + b) >= 1- ξi 就越趋近于大于等于1，分类越准确。反之亦然。

拉格朗日乘子法，ai>=0, ui>=0

对w,b,ξ 分别求偏导：

w偏导

b偏导

ξ 偏导。转化为 0 <= ai <= C

代入原式：(引入松弛因子的结果就是在改变了原来式子的限制条件，即从ai >=0 转换为 C >= ai >= 0)

条件：∑ ai * yi = 0，C >= ai >= 0

转换后的KKT条件：

ai = 0, yi(w^T * x - b) > 1

ai = C, yi(w^T * x - b) < 1

0 < ai < 0, yi(w^T * x - b) = 1

φ(x) 表示将x映射后的特征向量he

通过φ(x) 的转化，线性不可分变为线性可分

假设在二维空间中有两个数据，X(x1,x2), Y(y1,y2), 现在无法再该空间下找到一个合适个超平面分隔这两个数据，则需要一个映射函数φ(X) 将原始数据转化到更高维度的空间。

计算目标函数中φ(X)^T *φ(Y) = <φ(X), φ(Y)> ：内积

引入核技巧，核技巧的基本想法是通过一个非线性的变换将输入空间对应于一个新特征空间，使得在输入空间中的超曲面模型对应于新的特征空间中的超平面模型，这样，分类问题的学习任务通过在新特征空间中求解线性支持向量机就可以完成。在学习与预测中只定义K(X, Y)，而不是显式的定义映射函数φ。通常，直接计算K核函数比较容易，而通过φ(X)和φ(Y)计算K(X, Y)较难，因为新的特征空间都是高维的，甚至是无穷维，计算成本会很高。

核技巧：K(X, Y) = <φ(X), φ(Y)> = φ(X)^T·φ(Y), 即X和Y在转换后特征空间的内积等于他们在原始样本空间中通过函数K计算的结果。提前确定核函数即可避免高维度内积运算

Kernel function类型：

线性核Linear Kernel：

实际上就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了(意思是说，咱们有的时候，写代码，或写公式的时候，只要写个模板或通用表达式，然后再代入不同的核，便可以了，于此，便在形式上统一了起来，不用再分别写一个线性的，和一个非线性的)。

多项式核Polynomial Kernel：

径向基函数Radial basis function：取值仅仅依赖于特定点距离的实值函数，也就是φ(x,y)=φ(||x-y||)，标准的一般使用欧氏距离

高斯核函数Gaussian Kernel是RBF核的一种，因为可以看成如下核函数的另外一个种形式：

两个向量的欧式距离（2范数）计算，而且，高斯核函数是两个向量欧式距离的单调函数。σ是带宽width，控制径向作用范围，换句话说，σ控制高斯核函数的局部作用范围。当x和y的欧式距离处于某一个区间范围内的时候，假设固定y，k(x,y)随x的变化而变化的相当显著。

gamma是选择RBF函数作为kernel后，该函数自带的一个参数。隐含地决定了数据映射到新的特征空间后的分布，gamma越大，支持向量越少，gamma值越小，支持向量越多。支持向量的个数影响训练与预测的速度。若gamma越大，σ→0，高斯函数平滑程度越差，则所有训练样本点都是支持向量，且它们全部可以被正确分类，但是容易过拟合。若gamma越小，σ→∞，高斯函数平滑程度越好，则其学习推广能力或对新样本的正确判断能力为零，即它把所有样本点都判定为同一类别。

一维，y=0, k(x,0)随x变化的结果，此时σ = 1

一维，y=0, k(x,0)随x变化的结果，此时σ = 5

二维，y=0, k(x,0)随x变化的结果，此时σ = 1

二维，y=0, k(x,0)随x变化的结果，此时σ = 5

高斯核把原始维度映射到无穷多维：

泰勒展开式

高斯核函数

可以看出公式中的的泰勒展开式其实是0-n维的多项式核函数的和。(核函数K的值就是转化后的特征向量的内积）

Why does the RBF (radial basis function) kernel map into infinite dimensional space?

Maximizing the margin is not the only trick (although it is very important). If a non-linear kernel function is used, then the smoothness of the kernel function also has an effect on the complexity of the classifier and hence on the risk of over-fitting.

If you use a Radial Basis Function (RBF) kernel, for example, and set the scale factor φ (also = 1/2σ) to a very small value (σ very big), more smooth, the SVM will tend towards a linear classifier. If you use a high value(σ very small), the output of the classifier will be very sensitive to small changes in the input, which means that even with margin maximization, you are likely to get over-fitting.

常用的核就是线性核和高斯核

在使用kernel变换之前需要对数据标准化

通常情况，RBF效果会比Linear的好一些，但是时间上RBF会耗费更多，因为需要计算内积，两两样本都得算，所以样本过多的话时间消耗太大，很明显高斯核比线性核复杂得多

Use linear kernel when number of features is larger than number of observations.

Use Gaussian kernel when number of observations is larger than number of features.

If number of observations is larger than 50,000 speed could be an issue when using Gaussian kernel; hence, one might want to use linear kernel.

疑问：样本数目少于特征维度并不一定会导致过拟合。

解：用RBF kernel, 系统的dimension实际上不超过样本数，与特征维数没有一个trivial的关系。

Sigmoid 函数：

SVM算法优点：

(1)非线性映射是SVM方法的理论基础,SVM利用内积核函数代替向高维空间的非线性映射；

(2)对特征空间划分的最优超平面是SVM的目标,最大化分类边际的思想是SVM方法的核心；

(3)支持向量是SVM的训练结果,在SVM分类决策中起决定性作用。因此，模型需要存储空间小，算法鲁棒性（ Robust ）强。

SVM算法缺点：

(1) SVM算法对大规模训练样本难以实施

由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。

(2) 用SVM解决多分类问题存在困难

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。

起初的难点是拉格朗日对偶和SMO，后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题。而SMO里面迭代公式的推导也着实让我花费了不少时间。

之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。

如下有两个链接更加详细的解释了SVM的数学理论基础及实践过程：

零基础学SVM—Support Vector Machine(一)：https://zhuanlan.zhihu.com/p/24638007

零基础学SVM-Support Vector Machine(二)：https://zhuanlan.zhihu.com/p/29865057

SMO(Sequential minimal optimization)优化算法

SMO算法选择同时优化两个参数，固定其他n-2个参数，假设选择的变量为a1,a2，固定其他的参数a3,a4,...,an，这样可以简化目标函数为只关于a1,a2的二元函数: