再看SVM

2019-01-29 本文已影响9人 dapenghuang

超平面描述方程
$w^Tx + b = 0 \tag{6.1}$
其中w是法向量。
空间任意点到平面的距离：
$r = \frac{|wx_{0}+b|}{||w||} \tag{6.2}$
假设超平面可以正确分类，则
$\begin{equation} \left\{ \begin{array}{**lr**} w^Tx_{i}+ b \ge +1, && y_{i}= +1\\ w^Tx_{i}+ b \le -1, && y_{i}= -1\\ \end{array} \right. \end{equation} \tag{6.3}$

支持向量到超平面的距离之和为
$\gamma = \frac{2}{||w||}$

期望找到最大间隔的划分超平面
$max_{w,b}\frac{2}{||w||} \\ s.t. \quad y_{i}(wx+b) \ge 1 ,\quad i=1,2,3,...m \tag{6.4}$

公式6.3等价于
$min_{w,b}0.5||w||^2 \\ s.t. \quad y_{i}(wx+b) \ge 1 ,\quad i=1,2,3,...m \tag{6.5}$

公式6.5是SVM的基本型

使用拉格朗日法或KTT条件对公式6.5求值

拉格朗日法
https://baijiahao.baidu.com/s?id=1570175529375716&wfr=spider&for=pc
https://www.cnblogs.com/ooon/p/5721119.html
https://blog.csdn.net/binlin199012/article/details/80275676
https://blog.csdn.net/on2way/article/details/47729419
https://mp.weixin.qq.com/s?__biz=MzI4MDYzNzg4Mw==&mid=2247486230&idx=1&sn=41c3bcbf00b43535e912af1dab2704f5&chksm=ebb433c2dcc3bad45fa784314d4ea6a464538ff19b937b58bd99f12b43ec3c3cf01a269f9124&mpshare=1&scene=23&srcid=11211sArM7yh9Xf0pkvnWaJA#rd
https://blog.csdn.net/Mr_KkTian/article/details/53750424
带有等式约束的方程，极值点取在约束方程和原函数梯度平行的位置上。
对不等式约束：

image.png-165.8kB
条件1对应的是梯度平行
条件2就是原始约束

对公式6.5使用拉格朗日乘子法可得：
$L(w,b,\alpha) = 0.5||w||^2 + \sum_{i=1}^{m}\alpha_{i}(1-y_{i}(w^Tx_{i}+b)) \tag{6.6}$
拉格朗日乘子法的本质是函数的等高线与约束函数相切的点对应两者的梯度平行，再去除等式中的梯度算子得到。
对于不等式约束，那么极值点或者存在于约束方程的边界上，或者在约束方程内，后者的条件可以只对原函数求极值点。

转置求偏导：https://wenku.baidu.com/view/f7fa307a580216fc700afdb9.html

对其中的w和b分别求偏导等于0可得：
$w=\sum_{i=1}^{m}\alpha_{i}y_{i}x_{x} \tag{6.7}$
$0=\sum_{i=1}^{m}\alpha_{i}y_{i} \tag{6.8}$

关于对偶问题的解释：
https://www.quora.com/What-is-an-intuitive-explanation-of-the-KKT-conditions#
https://blog.csdn.net/Mr_KkTian/article/details/53750424

将公式6.7,6.8带入公式6.6,再考虑到 $\alpha_{i} \ge 0$ 得到公式6.6的对偶问题：
$max_{\alpha} \sum_{i=1}^{m} \alpha_{i} - 0.5*\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_{i}\alpha_{j}y_{i}y_{j}x_{i}^Tx_{j} \tag{6.9} \\ s.t. 0=\sum_{i=1}^{m}\alpha_{i}y_{i} \\ \alpha_{i} \ge 0 , \quad i=1,2...,m$

解出 $\alpha_{i}$ 求出w,b即可得到方程。
$f(x) = w^Tx+b \\ =\sum_{i=1}^{m}\alpha_{i}y_{i}x_{i}^Tx+b \tag{6.10}$
注意KTT约束条件
$\begin{equation} \left\{ \begin{array}{**lr**} \alpha_{i} \ge 0\\ y_{i}(wx+b) \ge 1\\ \alpha_{i}(y_{i}(wx+b)-1)=0\\ \end{array} \right. \end{equation} \tag{6.11}$

所以对于任意（x,y），或者 $\alpha_(i)=0$ 或者 $y_{i}(wx+b)-1=0$ .若 $\alpha_(i)=0$ 不会对f(x)产生任何影响。若 $y_{i}(wx+b)-1=0$ ，则该点是支持向量。

SMO算法来求解 $\alpha_{i}$

http://www.cnblogs.com/biyeymyhjob/archive/2012/07/17/2591592.html
https://blog.csdn.net/the_lastest/article/details/78637565
https://www.cnblogs.com/pursued-deer/p/7857783.html
http://cs229.stanford.edu/notes/cs229-notes3.pdf

任选两个 $\alpha_{i} \alpha_{j}$ 假设其他参数都为常数，则根据公式6.8:
$\alpha_{1}y^1 +\alpha_{2}y^2 = -\sum_{i=3}^{m}\alpha_{i}y^i =c \tag{6.12}$