（十一）Support Vector Machine 理论 (支持向量机SVM 上)

背景：

• 最早期是由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出
• 目前的版本(soft margin)是由Corinna Cortes 和 Vapnik在1993年提出，并在1995年发表
• 深度学习（2012）出现之前，SVM被认为机器学习中近十几年来最成功，表现最好的算法

机器学习的一般框架：

• 获取一个数据集作为训练集 => 从训练集的每一个实例中提取特征向量 => 针对这些特征向量结合一定的算法（分类器：比如 Decision Tree，KNN）=>得到训练好的模型=>有新实例来的时候就可以用得到的模型来预测，对其进行分类

引子

• 假设获取到一个训练集，每个实例有 x1$x_1$,x2$x_2$俩个特征，将其在二维坐标上呈现出来如下，假如现在有俩类实例，我们的目标是在二维的空间中找到一条线，来最好的区分这俩类实例

• 如上图一

• 扩展开，有n（n> 2）个特征向量的训练集，那么如上所要找的这条线变成了Hyperplane（超平面），即如何找到这样一个超平面最好（使边际margin最大，这也是为什么如上H3$H_3$优于H1$H_1$，H2$H_2$的原因，类似如下图）的划分俩类不同的点

• 边际margin最大，也是为了利用这个所选的线,平面或者超平面能够在预测新的属性的时候犯错几率会减少

提出问题

• 总共可以有多少个可能的超平面？无数条
• 如何选取使边际(margin)最大的超平面 (Max Margin Hyperplane)？并且要求超平面到一侧最近点的距离等于到另一侧最近点的距离，两侧的两个超平面平行

介绍两个基本问题 线性可区分(linear separable) 和 线性不可区分 （linear inseparable)

• 如上就是所谓的线性不可区分，而图一就是所谓的线性可区分

当实例是线性可区分(linear separable)的时候，我们如何建造SVM的超平面

• 从数学上将超平面定义成这样的公式
  

  W⋅X+b=0$$W·X+b=0$$

• W是权重向量(weght vector)特征向量的个数也对应着了X的维度,n 是特征的个数，X是训练实例，b就是偏向bias

• W={w1,w2,...,wn}$$W=\{w_1,w_2,...,w_n\}$$

假设一个二维实例特征向量 ： X = （x1,x2$x_1,x_2$）,对于权重W也是个二维的（W1,W2$W_1,W_2$）,此时将b 也当做一个特征维度x0其中(x0=1)$x_0其中(x_0=1)$的特征维度w0$w_0$,此时超平面方程变为如下方程，即所有的点都在超平面上满足此方程：

• 那么所有超平面右上方的点满足：
  
  w0+w1x1+w2x2>0$$w_0+w_1{x}_1+w_2{x}_2>0$$

• 那么所有超平面左上方的点满足：
  

  w0+w1x1+w2x2<0$$w_0+w_1{x}_1+w_2{x}_2<0$$

• 调整 weight , 使超平面定义边际的俩边定义公式如下，其中yi$y_i$表示实例属于哪一类（class label），在这个问题中 ，只有俩类，-1，+1分别代表这俩类

• 当实例满足H1:w0+w1x1+w2x2≥1$H_1:w_0+w_1{x}_1+w_2{x}_2\ge 1$ 时，实例的class label为 y=+1$y_{=}+1$

• 当实例满足H1:w0+w1x1+w2x2≤−1$H_1:w_0+w_1{x}_1+w_2{x}_2\le -1$时，实例的class label为 y=−1$y_{=}-1$
• 如上H1H2$H_1{H}_2$俩公式，分别同时乘以yi=+1,yi=−1$y_i=+1,y_i=-1$，得到如下公式

• 即针对所有实例，都满足如上这个条件，也就是说
  所有坐落在边际的两边的的超平面上的被称作”支持向量(support vectors)”，这些在边际俩边的超平面上的特殊点就是支持向量，因为它们是支撑这个边际区域，以及建立边际区域方程的

分界的超平面和H1或H2上任意一点的距离

• 为 1||W||$\frac{1}{||W||}$(i.e.: 其中||W||是向量的范数(norm))

-所以最大边际距离为:

SVM如何找出最大边际的超平面呢(MMH)？

• 利用一些数学推倒，以上公式 （1）可变为有限制的凸优化问题(convex quadratic optimization)
• 利用 Karush-Kuhn-Tucker (KKT)条件和拉格朗日公式，可以推出MMH可以被表示为以下“决定边界 (decision boundary)”

• 其中，l$l$是支持向量点的个数
• yi$y_i$ 是支持向量点Xi$X_i$的类别标记(class label)，即上例要预测为+1或者-1
• Xi$X_i$，是要支持向量点
• XT$X^T$ ，是要测试的实例

• αi和b0${\alpha }_i和b_0$都是单一数值型参数，由以上拉格朗日公式得出

• 对于任何测试（要归类的）实例，带入以上公式，得出的符号是正还是负决定

例1 根据 支持向量点 求 超平方程

SVM（支持向量机）算法特性

• 训练好的模型的算法复杂度是由支持向量的个数决定的，而不是由数据的维度决定的。所以SVM不太容易产生overfitting
• SVM训练出来的模型完全依赖于支持向量(Support Vectors), 即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍然会得到完全一样的模型。
• 一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易被泛化，即支持向量个数比较多，得到的模型只会针对这个例子的预测实例区分的比较好，对于新的例子的预测就并不是区分的好。

线性不可分的情况（linearly inseparable case)

• 数据集在空间中对应的向量不可被一个超平面区分开
• 两个步骤来解决：
  
  • 利用一个非线性的映射把原数据集中的向量点转化到一个更高维度的空间中 ,如下图
  • 在这个高维度的空间中找一个线性的超平面来根据线性可分的情况处理

- 举个例子 找到区分 下面在一维中的 蓝点和红点的超平面

• 将其左右同时平方得到下面公式

• 这样就容易找到区分 这俩类点的超平面了

利用非线性映射把原始数据转化到高维中

• 将3维输入向量 X=（x1,x2,x3）$X=（x_1,x_2,x_3）$

• 转化到6维空间中去
  

  ϕ1(X)=x1,ϕ2(X)=x2,ϕ3(X)=x3,ϕ4(X)=x21,ϕ5(X)=x1x2,ϕ6(X)=x1x3$${\varphi }_1(X)=x_1,{\varphi }_2(X)=x_2,{\varphi }_3(X)=x_3,{\varphi }_4(X)=x_1^2,{\varphi }_5(X)=x_1{x}_2,{\varphi }_6(X)=x_1{x}_3$$

• 从而构造新的超平面,其中W和b都是向量，这个超平面是线性的

• 解出W和b之后，并且带入回原方程：

此处提出思考问题：

1. 如何选择合理的非线性转化把数据转到高纬度中？

2. 如何解决计算内积时算法复杂度非常高的问题？

---

• 解决上述俩个问题的方法，使用核方法（kernel trick)

核方法（kernel trick)

• 动机
  在线性SVM中转化为最优化问题时求解的公式计算都是以内积(dot product)的形式出现的
  

  ϕ(XI)⋅ϕ(Xj)$$\varphi (X_I)·\varphi (X_j)$$
  
  ，其中
  
  ϕ(X)$$\varphi (X)$$
  
  是把训练集中的向量点转化到高维的非线性映射函数，因为内积的算法复杂
  度非常大，所以我们利用核函数来取代计算非线性映射函数的内积

• 以下核函数和非线性映射函数的内积等同,核函数K(Xi⋅Xj)$K(X_i·X_j)$的运算量算法复杂度，远远低于直接求内积ϕ(Xi)⋅ϕ(Xj)$\varphi (X_i)·\varphi (X_j)$这也是核函数的基本思想

  K(Xi⋅Xj)=ϕ(Xi)⋅ϕ(Xj)$$K(X_i·X_j)=\varphi (X_i)·\varphi (X_j)$$

• 常用的核函数(kernel functions)

1.h度多项式核函数(polynomial kernel of degree h)

2.高斯径向基核函数(Gaussian radial basis function kernel),σ$\sigma$是方差

3.S型核函数(Sigmoid function kernel)

如何选择使用哪个kernel？

• 根据先验知识，比如图像分类，通常使用RBF，文字不使用RBF
• 尝试不同的kernel，根据结果准确度而定

核函数举例:

• 假设定义两个向量：x=(x1,x2,x3);y=(y1,y2,y3)$x=(x_1,x_2,x_3);y=(y_1,y_2,y_3)$
• 定义方程：f(x)=(x1x1,x1x2,x1x3,x2x1,x2x2,x2x3,x3x1,x3x2,x3x3)$f(x)=(x_1{x}_1,x_1{x}_2,x_1{x}_3,x_2{x}_1,x_2{x}_2,x_2{x}_3,x_3{x}_1,x_3{x}_2,x_3{x}_3)$
• 求内积K(x,y)=(<x,y>)2$K(x,y)=(<x,y>{)}^2$

• 假设x=(1,2,3);y=(4,5,6).$x=(1,2,3);y=(4,5,6).$
  

  f(x)=(1,2,3,2,4,6,3,6,9)$$f(x)=(1,2,3,2,4,6,3,6,9)$$
  
  
  f(y)=(16,20,24,20,25,36,24,30,36)$$f(y)=(16,20,24,20,25,36,24,30,36)$$
  
  
  <f(x),f(y)>=16+40+72+40+100+180+72+180+324=1024$$<f(x),f(y)>=16+40+72+40+100+180+72+180+324=1024$$

• 应用核函数 <x,y>=(4+10+18)$<x,y>=(4+10+18)$
  

  K(x,y)=(4+10+18)2=322=1024$$K(x,y)=(4+10+18{)}^2={32}^2=1024$$

• 同样的结果，使用kernel方法计算容易很多

SVM扩展可解决多个类别分类问题

• 对于每个类，有一个当前类和其他类的二类分类器（one-vs-rest)