SVM支持向量机推导过程  

admin  

SVM是一种二类分类模型,目的是找到一个超平面,使得样本点之间的间隔尽可能的远。样本中距离超平面最近的点的集合叫做支持向量。分类平面仅由这些支持向量决定。当两类样本的最近距离最大,分类器的泛化能力才越强。

推导svm算法,涉及到下面几点知识:

  • 点到平面的距离

对于点$x_i$ 到平面$w^Tx+b$的距离为: $d=\frac{w^Tx_i+b} {\parallel w \parallel}$

  • 不等式约束极値问题求解(KKT条件)

对于极値问题

$$\begin{cases}min & f(x), \cr s.t & g(x)\leq 0\end{cases} $$

可以使用KKT条件求解

$$ \mathcal{L} (x,\lambda) = f(x)+\lambda g(x) $$

如果$x ^{*} $ 是极值点,则一定有$\lambda ^{*} $

$$\begin{cases}\bigtriangledown_x\mathcal{L} (x ^{},\lambda ^{})=0, \cr \lambda ^{} \geq 0 \cr \lambda ^{} g(x ^{*})=0 \end{cases} $$

以上三个条件叫做KKT条件,更多内容参考链接

回到SVM当中,目标是最大间隔$max\ margin(w,b)$。间隔由两个分类最近的样本决定。假设存在一个平面$w^Tx_i+b$ 划分两个样本,则两个样本的间隔可以表示为最近样本到平面的距离。

正样本$y_i=1$样本,距离边界点的距离为$ d=\frac{w^Tx_i+b} {\parallel w \parallel}\geq 0 $,负样本$y_i=-1$ 距离边界点的距离$ d=\frac{w^Tx_i+b} {\parallel w \parallel}\leq 0 $ (距离是有方向的) ,对上述距离进行转换为无方向的距离

$r = y_i \frac{w^Tx_i+b} {\parallel w \parallel} $ ,$r$叫做函数距离。

$ max\ margin(w,b) = max \ r=y_i \frac{w^Tx_i+b} {\parallel w \parallel} ,其中x_i是边界上的点$

假设决策边界距离最近样本的距离是1(只当做一个距离单位)

则对于分类器,$\begin{cases}f(x)\geq 1 ,正样本,y_i=1, \cr f(x)\leq -1,负样本 y_i =-1 \end{cases} $ 边界上的点就是等式成立的点。

因此目标函数为: $$ max\ margin(w,b) = max \ r=y_i \frac{w^Tx_i+b} {\parallel w \parallel} =max \ \frac {1} {\parallel w \parallel} $$

$$\Leftrightarrow min \ \frac{1} {2} \parallel w \parallel ^2 \ s.t\ \forall{_i} \ \ y_i(w^Tx_i+b)\leq 1$$

目标函数是一个不等式约束问题的极値问题,由于不等式为$g(x) = - ( y_i(w^Tx_i+b) -1 )\leq 0 $,因此使用拉格朗日有:

$$ \mathcal{L} (w,b,\lambda) = \frac{1} {2} \parallel w \parallel ^2 - \sum_{i=0}{^n}\lambda{_i}(y_i(w^Tx_i+b)-1) $$

这里KKT条件为:

$$\begin{cases}\bigtriangledown_x\mathcal{L} (x_i,\lambda_i ^{})=0, \cr \lambda_i ^{} \geq 0 \cr \lambda_i ^{*} ( y_i(w^Tx_i+b) -1 )=0 \end{cases} $$

因此有$max \ \mathcal{L} (w,b,\lambda) = \frac{1} {2} \parallel w \parallel ^2 $

所以目标函数可以转换成

$$ \mathop{\min}\limits{w,b}\ \ \mathop{\max}\limits{\lambda\geq 0} \mathcal{L} (w,b,\lambda) $$

KKT条件下,对偶问题,因此等价于

$$ \mathop{\max}\limits{\lambda\geq 0}\ \ \mathop{\min}\limits{w,b} \mathcal{L} (w,b,\lambda) $$

因此先求最小值再求最大值。求最小值可以把$\lambda $ 当做常数处理。

$$ \frac{ \partial \mathcal{L} } { \partial w } = w-\sum_{i=0}{^n}\lambda_iy_ixi = 0 \Leftrightarrow \ w = \sum{i=0}{^n}\lambda{_i}y_ix_i $$

$$ \frac{ \partial \mathcal{L} } { \partial b } = -\sum_{i=0}{^n}\lambda_iyi = 0 \Leftrightarrow \sum{i=0}{^n}\lambda{_i}y_i = 0 $$

将上面得到的结果带入拉格朗日算子得到:

$$ \mathcal{L}(\lambda,w,b) = \sum_{i=0}{^n}\lambdai - \frac{1} {2} \sum{i,j}\lambda_i\lambda_jy_iy_jx_i^Tx_j $$

最小值求完之后,求最大值 $$ max\ \sum_{i=0}{^n}\lambdai - \frac{1} {2} \sum{i,j}\lambda_i\lambda_jy_iy_jx_i^tx_j ,s.t \ \lambdai>0 \ and\ \sum{i}\lambda_iy_i=0 $$

通过最大值求解,求出$\lambda$,利用SMO算法求解。根据拉格朗日算子求出 w。求出w后可以根据前面函数距离等于1的假设求出b 。

推导过程参考文档