SVM支持向量机推导过程
SVM是一种二类分类模型,目的是找到一个超平面,使得样本点之间的间隔尽可能的远。样本中距离超平面最近的点的集合叫做支持向量。分类平面仅由这些支持向量决定。当两类样本的最近距离最大,分类器的泛化能力才越强。
推导svm算法,涉及到下面几点知识:
- 点到平面的距离
对于点$x_i$ 到平面$w^Tx+b$的距离为: $d=\frac{w^Tx_i+b} {\parallel w \parallel}$
- 不等式约束极値问题求解(KKT条件)
对于极値问题
可以使用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 。
推导过程参考文档
评论