十三、支持向量机SVM

SVM（Support Vector Machines）

近年已被深度学习所替代

SVM寻找区分两类的超平面（hyper plane），使边际（margin）最大

向量内积： $x.y = x_1y_1+x_2y_2+...+x_ny_n$

$x.y = ||x||||y||cos(\theta)$

范数： $||x|| = \sqrt{x.x} = \sqrt{x_1^2+x_2^2+..+x_n^2}$

当 $||x||\neq 0$ 时，可以求余弦相似度： $cos(\theta) = \frac{x.y}{||x||||y||}$

$w.x_1+b=1$

$w.x_2+b=-1$

$w.(x_1-x_2) = 2$

$||w||||x_1-x_2||cos(\theta) = 2$

$||w||*d = 2$

$d = \frac{2}{||w||}$

算法推论：

转化为凸优化问题：

$w.x+b\geq 1,则分类\ y=1$

$w.x+b \leq -1,则分类\ y=-1$

——》 $y(w.x+b)\geq 1$ ，求 $d = \frac{2}{||w||}$ 最大值，即求 $min \frac{||w||^2}{2}$

而凸优化问题一般有三种情况：

1、无约束优化问题： $min(f(x))$ 费马定理

2、带等式约束的优化问题： $minf(x)$

-拉格朗日乘子法：

s.t. $h_i(x) = 0, \ \ \ i=1,2,...,n$

$L(x,\lambda) = f(x)+\sum_{i=1}^{n}\lambda_ih_i(x)$

3、带不等式约束的优化问题： $minf(x)$

-KKT条件

s.t. $h_i(x) = 0,\ \ \ \ i=1,2,...,n$

$g_i(x)\leq 0,\ \ \ \ i=1,2,...,k$

$L(x,\lambda,v) = f(x)+\sum_{i=1}^{k}\lambda_ig_i(x)+\sum_{i=1}^{n}v_ih_i(x)$

而算法是在 $y(w.x+b)\geq 1$ 的条件下求 $min \frac{||w||^2}{2}$

实际上 $min \frac{||w||^2}{2}$ 存在时， $y(w.x+b)$ 取1，即属于第2种情况

广义拉格朗日乘子法：

$L(w,b,a) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

$\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^{n} \alpha_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_iy_i = 0$

而KKT条件（Karush-Kuhn-Tucker最优化条件）

是拉格朗日乘子法的一种推广，可以处理有不等号的约束条件

进一步简化为对偶问题

$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

上述问题可以改写成：

$min_{w,b}\ max_{a_i\geq 0}\ L(w,b,\alpha) = p^*$

可以等价为下列对偶问题：

$max_{a_i\geq 0}\ min_{w,b}\ L(w,b,\alpha) = d^*$

$L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)$

$\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^{n} \alpha_iy_ix_i$

$\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_iy_i = 0$

消除w，b——

$L(w,b,\alpha) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j$

$max_{\alpha_i\geq 0}\ min_{w,b}\ L(w,b,\alpha) = max_\alpha\ [\sum_{i=1}^{k}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

$min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

由此可得最优解 $\alpha^*$ ，带入后得

$w^* = \sum_{i=1}^{n}\alpha_i^*y_ix_i,\ \ \ \ b^* = y_i-(w^*)^Tx_i$

SMO算法

针对线性SVM和稀疏数据时性能更优

$min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

s.t. $C\geq \alpha_i \geq 0,\ \ \ i=1,2,...,n$

基本思路是先根据约束条件随机给 $\alpha$ 赋值，然后每次选举两个 $\alpha$ ，调节这两个 $\alpha$ 使得目标函数最小。然后再选取两个 $\alpha$ ，调节 $\alpha$ 使得目标函数最小。以此类推

线性不可分的情况

引入松弛变量与惩罚函数

松弛变量 $\varepsilon$

$y_i(w_i.x_i+b)\geq 1-\varepsilon _i,\ \ \varepsilon _i\geq 0$

约束条件没有体现错误分类的点要尽量接近分类边界

惩罚函数 $C\sum_{i=1}^{n}\varepsilon _i$

$min\frac{||w||^2}{2}+C\sum_{i=1}^{n}\varepsilon _i$

使得分错的点越少越好，距离分类边界越近越好

线性不可分下的对偶问题：

——》 $min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]$

s.t. $\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n$

s.t. $C\geq \alpha_i \geq 0,\ \ \ i=1,2,...,n$

eg：

可知目标函数为： $min_\alpha f(\alpha)$ ， s.t. $\alpha_1+\alpha_2 - \alpha_3=0$ ， $\alpha_i\geq 0,i=1,2,3$

其中 $f(\alpha) = \frac{1}{2}\sum_{i,j=1}^{3}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{3}\alpha_i$

$=\frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2 - 12\alpha_1\alpha_3-14\alpha_2\alpha_3) - \alpha_1-\alpha_2-\alpha_3$

然后，将 $\alpha_3 = \alpha_1+\alpha_2$ 带入目标函数，得到一个关于 $\alpha_1$ 和 $\alpha_2$ 的函数

$S(\alpha_1,\alpha_2) = 4\alpha_1^2+\frac{13}{2}\alpha_2^2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2$

对 $\alpha_1，\alpha_2$ 求偏导，并令其为0

可知 $S(\alpha_1,\alpha_2)$ 在（1.5，-1）处取极值

而（1.5，-1）不满足 $\alpha_i\geq 0$ 的约束条件，可推断最小值在边界上达到

经计算，

当 $\alpha_1=0$ 时， $S(\alpha_1=0,\alpha_2=\frac{2}{13})=-0.1538$

当 $\alpha_2=0$ 时， $S(\alpha_1=\frac{1}{4},\alpha_2=0)=-0.25$

所以， $S(\alpha_1,\alpha_2)$ 在 $\alpha_1=\frac{1}{4},\alpha_2=0$ 时取最小值

此时可算出 $\alpha_3 = \alpha_1+\alpha_2=\frac{1}{4}$

所以， $\alpha_1,\alpha_3$ 不等于0，所以对应点 $x_1$ 和 $x_3$ 就应该是支持向量

进而

$w^* = \sum_{i=1}^{3}\alpha_i^*y_ix_i = \frac{1}{4}*(3,3)-\frac{1}{4}*(1,1)=(\frac{1}{2},\frac{1}{2})$

即 $w_1 = w_2 = 0.5$ 。进而有

$b^* = 1-(w_1,w_2).(3,3)=-2$

因此最大间隔分类超平面为

$\frac{1}{2}x_1+\frac{1}{2}x_2-2=0$

分类决策函数为

$f(x) = sign(\frac{1}{2}x_1+\frac{1}{2}x_2-2)$

非线性的情况

把低维空间的非线性问题映射到高维空间，变成求解线性问题

映射举例：

3维输入向量 $x=(x_1,x_2,x_3)$

转化到6维空间 $Z$ 中去：

$\phi _1(x) = x_1,\phi _2(x) = x_2,\phi _3(x) = x_3,$

$\phi _4(x) = (x_1)^2,\phi _5(x) = x_1x_2\ and\phi _3(x) = x_1x_3$

新的决策超平面 $d(Z) = WZ+b$ ，其中 $W$ 和 $Z$ 是向量，这个超平面是线性的，解出 $W$ 和 $b$ 之间，并且带回原方程

$d(Z) = W_1x_1+W_2x_2+W_3x_3+W_4(x_1)^2+W_5x_1x_2+W_6x_1x_3+b$

$=W_1Z_1+W_2Z_2+W_3Z_3+W_4Z_4+W_5Z_5+W_6Z_6+b$

存在的问题：

1、维度灾难

2、如何选择合理的非线性转换

核函数

我们可以构造核函数使得运算结果等同于非线性映射，同时运算量要远远小于非线性映射

$K(x_i,x_j) = \phi (x_i).\phi (x_j)$

h次多项式核函数： $K(x_i,x_j) =(x_i,x_j+1)^h$

高斯径向基函数核函数： $K(x_i,x_j) =e^{\frac{-||x_i-x_j||^2}{2\sigma ^2}}$

S型核函数： $K(x_i,x_j) =tanh(kx_i.x_j-\delta )$

SVM优点

-算法复杂度由支持向量的个数决定，而非数据维度，所以不太易产生overfitting

-SVM训练出来的模型完全依赖于支持向量（Support Vectors）即使训练集里面所有非支持向量的点都被去除，重复训练过程，结果仍会一样

-一个SVM如果训练得出的支持向量个数比较小，SVM训练出的模型比较容易泛化

十三、支持向量机SVM