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 heta)
(||x_1 - x_2||cos heta = 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 heta}{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 heta)
假设空间的一组基(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 heta)
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:
( abla _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:
( abla_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 -bsum_{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>)
(<x_i x_j>) 表示内积, 即 (x_i ^T x_j), 实际意义是每个样本都要与其余样本进行点积运算
优化了w之后, 于是对应的 dual 问题即:
再补充一波 KKT 4个条件
拉格不动性: ( abla_x L(x', a, eta) = 0)
原始可行性: (g_i(x') <= 0; h_i(x) =0)
对偶可行性: (a_i >= 0)
互补松弛性: (a_i g_i(x') = 0)
(max_a f_0(a) = sum_{i=1}^n a_i - frac {1}{2} sum_{i,j=1}^n y_i y_j a_i a_j <x_i, x_j> \ s.t.)
(a_i >= 0, i=1,2,...n \ sum_{i=1}^n a_i y_i = 0)
SVM 的决策算子, 值的正负号表示类别:
(w^Tx_{new}+b = (sum_{i=i}^n a_i y_i x_i)^Tx_i + b)
(=sum_{i=1}^na_i y_i <x_i x_{new}> + b)
(a_i y_i) 是一个实数, 可以提出来
小结
线性的svm推导大致便如上了. 最为关键要点在于目标函数及其Lagrange形式
关于margin
((w^Tx_1 + b = 1) - (w^Tx_2 + b) = 2)
关于目标函数:
(min_{w,b} frac{1}{2} ||w||^2 \ s.t. y_i(w^tx_i + b) >= 1, i = 1,2,..n)
关于Lagrange
(L(w, a, b) = = 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>)
why i, j ?
辛辛苦苦推导了大半天, 目的就是将目标函数, 转化为了只关于a 的函数
- 形式上比较美观
- 为后面求解a做铺垫, 方便写代码
像后面的 带松弛变量和核函数, 及求解a的SMO算法, 这些都是要用到的哦.