Vapnik 发明

问题

1、线性模型

简单来说，就是在一个二维平面中用一条直线，分开两类样本。像这样可以用一条直线分开的训练样本集称为线性可分训练样本集。如下图所示：

线性可分与非线性可分

2、最优直线

可以证明，对于线性可分训练样本集，如果存在一条可以分开两类样本的直线，那么这样的直线有无数个。

哪一条直线“更好”

我们通过感觉判断应该是2号线更好一些。而且1、3号线对数据的噪声较为敏感（与样本数据比较靠近），而2号线对与误差的容忍程度会更多一点。

那么，我们如何来定义2号线是怎么画的呢？

我们可以为每条线定义一个“性能指标”，而且上面提到的2号线应该是“性能指标”最大的那一条线。

这里说的“性能指标”，简单来说就是将直线向两侧平移，直到第一次擦到两类样本点为止得到两条新的直线间的距离 d，如图。上面提到的2号线应该为距离 d 最大的那一条线。此外，为了使这条线唯一，还需要加上一个限制：这条线要在两条新直线的中间，即距离两条新直线的距离均为 d/2 。

“性能指标”

数学描述

支持向量机是一种最大化间隔的方法

定义

  • d ：间隔（Margin）

  • 将平行线擦到的向量叫支持向量（Support Vectors）

训练数据以及标签

(X1,y1),(X2,y2),(X3,y3),⋯ ,(XN,yN)(X_1,y_1), (X_2,y_2), (X_3,y_3), \cdots, (X_N,y_N)

其中X为样本向量，y为标签

Xi=[Xi1, Xi2, ⋯ , Xim]T,i∈[1,N]X_i = \left[ X_{i1} , \ X_{i2} , \ \cdots , \ X_{im} \right]^T, i \in [1,N]

yi∈{−1,1},i∈[1,N]y_i \in \{-1, 1\}, i \in [1,N]

线性模型

(ω,b)(\omega,b)

其中

ω=[ω1, ω2, ⋯ , ωm]T\omega = \left[ \omega_1 , \ \omega_2 , \ \cdots , \ \omega_m \right]^T

b=C (常数)b = C \ \text{(常数)}

描述超平面（Hyperplane）的线性方程为

ωTX+b=0\omega^TX+b=0

机器学习的目标：限定模型（超平面的线性模型） -> 留出待定参数（W和b） -> 通过训练样本以及算法确定待定参数（W和b）的具体取值

线性可分的定义

一个训练集线性可分的定义是：

对训练集 {(Xi, yi)}, i=1,2,⋯ ,N\text{对训练集} \ \{(X_i,\,y_i)\}, \ i = 1,2,\cdots,N

存在 (ω,b), s.t. 对 ∀ i=1,2,⋯ ,N ,\text{存在} \ (\omega,b), \ s.t. \ \text{对} \ \forall \ i = 1,2,\cdots,N \ ,

若 yi=1, 则 ωTX+b≥0    (1)\text{若} \ y_i = 1, \ \text{则} \ \omega^TX+b \geq 0 \ \ \ \ (1)

若 yi=−1, 则 ωTX+b<0    (2)\text{若} \ y_i = -1, \ \text{则} \ \omega^TX+b < 0 \ \ \ \ (2)

其中 yi∈{−1,1}时, (1)(2) 也合作 yi[ωTX+b]≥0    (公式1)\text{其中 } y_i \in \{-1, 1\} \text{时, (1)(2) 也合作} \ y_i[\omega^TX+b] \geq 0 \ \ \ \ \text{(公式1)}

支持向量机（Support Vector Machine）

优化问题

1、最小化（Minimize）：

12∣∣ω∣∣2\frac 1 2 ||\omega||^2

2、限制条件（Subject to）：

yi[ωTX+b]≥1, i=1,2,⋯ ,Ny_i[\omega^TX+b] \geq 1, \ i = 1,2,\cdots,N

解释：为什么要最小化？

事实1

ωTX+b=0\omega^TX+b=0

和

aωTX+ab=0, a∈R+a\omega^TX+ab=0, \ a \in \mathbb{R}^+

是同一个平面。

换句话说

(ω,b)(\omega,b)

满足公式1，则

(aω,ab), a∈R+(a\omega,ab), \ a \in \mathbb{R}^+

也满足公式1。

事实2 点到平面的距离公式

点

(x0,y0)(x_0,y_0)

到平面

ω1x+ω2y+b=0\omega_1x+\omega_2y+b=0

的距离

d=∣ω1x0+ω2y0+b∣ω12+ω22d = \frac {|\omega_1x_0+\omega_2y_0+b|} {\sqrt{\omega_1^2+\omega_2^2}}

在高维情况下的推广为：

向量

X0=[X1,X2,⋯ ,Xm]TX_0 = [ X_{1}, X_{2}, \cdots , X_{m} ]^T

到超平面

ωTX+b=0\omega^TX+b=0

的距离

d=∣ωTX0+b∣∣∣ω∣∣d = \frac{|\omega^TX_0+b|}{||\omega||}

其中

∣∣ω∣∣=ω12+ω22+⋯+ωm2||\omega|| = \sqrt{\omega_1^2+\omega_2^2+\cdots+\omega_m^2}

所以，我们可以用 a 去缩放

(ω,b) →(aω,ab), a∈R+(\omega,b) \ \rightarrow (a\omega,ab), \ a \in \mathbb{R}^+

最终使在支持向量

X0=[X1,X2,⋯ ,Xm]TX_0 = [ X_{1}, X_{2}, \cdots , X_{m} ]^T

有

∣ωTX0+b∣=1|\omega^TX_0+b| = 1

此时，支持向量与超平面的距离

d=1∣∣ω∣∣d = \frac{1}{||\omega||}

这样，进行最小化就相当于最大化了 d。

有关限制条件的解释
  1. 小于等于，使得非支持向量的到超平面的距离都要大于支持向量的到超平面的距离。
  2. 小于等于1的1不一定非要是1，改成其他的整数得到的W和b也是一样的，只是在过程中用来缩放的a的值存在差距。
  3. 只要训练集满足线性可分，就一定可以求出W和b；否则训练集非满足线性可分，则找不到这样的W和b来满足限制条件。

凸优化问题，二次规划问题

二次规划（Quadratic Programming）
  1. 目标函数（Objective Function）是二次项

12∣∣ω∣∣2=12(ω12+ω22+⋯+ωm2)\frac 1 2 ||\omega||^2 = \frac 1 2 (\omega_1^2+\omega_2^2+\cdots+\omega_m^2)

  1. 限制条件是一次项

yi[ωTX+b]≥1, i=1,2,⋯ ,Ny_i[\omega^TX+b] \geq 1, \ i = 1,2,\cdots,N

结果：要么无解，要么只有一个极值 （原理：拉格朗日数乘法求解条件极值）

方法：梯度下降法——选定一个初始位置，不断在附近搜索梯度更低的点，直到梯度不再下降