SVM支持向量机推导过程

28 Feb 2019 Category: 算法

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

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

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

对于极値问题

可以使用KKT条件求解

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

以上三个条件叫做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} $ 边界上的点就是等式成立的点。

因此目标函数为:

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

这里KKT条件为:

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

所以目标函数可以转换成

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

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

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

最小值求完之后,求最大值

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

推导过程参考文档

评论