ML-线性 SVM 推导

来源：恒创科技编辑：恒创科技编辑部

2022-08-22 14:40:47

Max Margin

svm 即Suport Vector Machine, 中文意为:支持向量机. 对于二分类问题, 在样本空间中(即便是多维向量, 在空间中可表示为一个点). svm的核心思想就是假设在这2波点的边缘处, 能找到一条直线 $w^Tx + b=0$, 能够把这2波点分开, 且该直线上到这2波点的边界(离对方)的点的距离相等, 约束就是使得这个分隔的距离(margin)尽可能大.

从几何上来说, 其实就是3条平行线

上: $w^Tx + b = 1$中: $w^Tx + b = 0$下: $w^Tx + b = -1$

有两点需要说明:

1 和 -1 的值是没有关系的,w,b可变, 需关注+ -, 换成 c 和 -c 也是一样的用来确定这个"分隔区域" 的边界上的点(构成边界) 就称为支持向量.

我们希望这个"分割区"越宽越好", 即这平行线(边界)的距离越大越好. 转化数学形式, 也就是,假设这两个边界上有2个支持向量(点) x1, x2, 即构成的向量可以表示为:

$x_1 - x_2$

而向量 x1, x2 是满足定义的边界线方程的, 即

$w^Tx_1 + b = 1 \\ w^Tx_2 + b = -1$

相减得:

$(w^Tx_1 + b = 1) - (w^Tx_2 + b) = 2$

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

$||x_1 - x_2||cos \theta = \frac {2} {||w^T||_2}$

假设x1, x2 到中线$w^Tx+b=0$的距离分别为 $d_1, d_2$

即: $d_1 = d_2 = \frac {||x_1 - x_2||cos \theta}{2} = \frac {1}{||w^T||_2^2}$

即欧氏距离margin = $d_1 + d_2 = \frac {2}{||w||_2}$

对于范数来说, $||w||_2 和 ||w^T||_2$

对于$w^T(x_1 - x_2) = 2$ 表示两个向量做内积

内积
首先, 矩阵其实就是广义的向量, 从向量空间定义来看, 也是满足对加法和数乘封闭的内积(点积) 定义为向量左乘其转置, 即$<a, a> = a^Ta; \ <x,y> = x^Ty$几何上, $<x,y> 表示x 在y上$ 的投影向量的长度: $|x||_2| \ ||y||_2 cos \theta$
假设空间的一组基(base) 是$(1,0)^T, (0,1)^T$, 向量x, y 分别在该基下的分分量分别为:
$x = (x_1, x_2) ^T, \ y = (y_1, y_2)^T$
$||x||_2 = length(x) =\sqrt {x_1^2 + x_2^2}, \ ||y||_2 = \sqrt {y_1^2 + y_2^2}$
$<x, y> = x^Ty = y^Tx \\ =x_1y_1 + x_2y_2 \\ = ||x||_2 \ ||y||_2 cos \theta$

SVM 数学模型

是一个典型的带约束条件的凸优化问题, 目标函数就是最大化**margin ** $=\frac {2}{||w||_2^2}$, 也就是 最小化 $||w||$.

$min_{w,b} \ \frac{1}{2} ||w||^2 \\ s.t. \ y_i(w^tx_i + b) >= 1, \ i = 1,2,..n$

优化说明
1/2 的作用是为了后面求导后, 形式美观, 没什么作用约束(上下界考虑): yi = 1或 -1, 当 yi>=1, 则要求 $w^tx+b>=1$; 当 yi<= -1 则 $w^tx+b<=-1$判断(工作原理): 对于每个样本点, 带入$w^tx+b 的值>=1$, 都在边界"上方" 的意思. 或者 <= -1 也是同样道理,只关注 yi 值的正负号

这样如果满足约束, 则我们就构造好了 svm 关于 margin 最大 的优化目标函数了.

将约束条件写为标准形式(:

$g_i(w) = -y_i(w^tx_i + b) + 1 <= 0$

为了转为 dual 的问题, 引入拉格朗日函数:

$L(w, b, a) = \frac {1}{2}||w||^2 - \sum_{i=1}^n a_i [y_i (w^tx_i + b) - 1]$ 这是比较标准的svm Lagrange写法啦

于是要构造dual 问题(只关于a的问题), 对于 $L(w, b, a)$, 我们先优化 w, b , 最后再来整 a, 即先对 w, b 求梯度, 令其等于0.

对 w 求梯度(偏导)=0:

$\nabla _w \ L(w,b, a) = w - \sum _{i=1}^n a_i y_i x_i = 0 \\ 即: w = \sum_{i=1}^n a_i y_i x_i$

同样对 b 求梯度(偏导) = 0:

$\nabla_b L(w,b,a) = - \sum _{i=1}^n a_i y_i = 0 \\ 即: 跟\ b 好像没啥关系趴$

这显然符合我们的设定, b 表示偏置嘛, 然后将 $w = \sum_{i=1}^n a_i y_i x_i$代入拉个朗日函数可得:

$L(w,b, a) =(\frac {1}{2} \sum_{i=1}^n a_i y_i x_i)( \sum_{j=1}^n a_j y_j x_j) - \sum_{i=1}^n a_i y_i \sum_{j=1}^n a_j, y_j x_j x_i -b\sum_{i=1}^n a_i y_i + \sum_{i=1}^n a_i$

由 $ \sum _{i=1}^n a_i y_i = 0$ 可简化为:

$= \sum_{i=1}^n a_i - \frac {1}{2} (\sum_{i=1}^n a_i y_i x_i)( \sum_{j=1}^n a_j y_j x_j)$

$= \sum_{i=1}^n a_i - \frac{1}{2} \sum_{i=1}^n \sum_{j=1}^n y_i y_j a_i a_j <x_i, x_j>$