SVM支持向量机推导过程

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_ix_i = 0 \Leftrightarrow \ w = \sum_{i=0}{^n}\lambda{_i}y_ix_i$$ $$\frac{ \partial \mathcal{L} } { \partial b } = -\sum_{i=0}{^n}\lambda_iy_i = 0 \Leftrightarrow \sum_{i=0}{^n}\lambda{_i}y_i = 0$$

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

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

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

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

推导过程参考文档