支持向量机 ----- SVM

摘要：简述在统计学习方法中，这样描述支持向量机，是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，可形式化为一个凸二次规划问题的求解。求将拉格朗日函数分别对求偏导数并令其等于。

在《统计学习方法》中，这样描述：

支持向量机（support vector machines，SVM）是一种二类分类模型，其基本模型定义为特征空间上的间隔最大的线性分类器，其学习策略便是间隔最大化，可形式化为一个凸二次规划（convex quadratic programming）问题的求解。

函数间隔(function margin)定义：对于给定训练数据集T和超平面$(w, b)$,定义超平面$(w,b)$关于样本点$(x_{i},y_{i})$的函数间隔为$$widehat{gamma _{i}}=y_{i}(wcdot x_{i}+b)$$
定义超平面$(w,b)$关于数据集T的几何间隔为超平面$(w,b)$T中所有样本点$(x_{i},y_{i})$的函数间隔之最小值，即$$widehat{gamma}=minwidehat{gamma _{i}}$$
几何间隔(geimetric margin)定义：对于给定训练数据集T和超平面$(w, b)$,定义超平面$(w,b)$关于样本点
$(x_{i},y_{i})$的几何间隔为$$gamma _{i}=y_{i}(frac{w}{left | w ight |}cdot x_{i}+frac{b}{left | w ight |})$$
定义超平面$(w,b)$关于数据集T的几何间隔为超平面$(w,b)$T中所有样本点$(x_{i},y_{i})$的函数间隔之最小值，即$$gamma=mingamma _{i}$$
因为如果超平面参数$w$和$b$成比例改变，虽然超平面不变，但是函数间隔离变了。因此使用几何间隔，并且令$left | w ight |=1$，下图为《机器学习》中的一张插图。

得到的目标函数如下
$$maxfrac{1}{left |w ight |} hspace{0.5cm} s.t., gamma_{i}(w^{T}+b)geq 1$$
$由于求frac{1}{left |w ight |}的最大值相当于求frac{1}{2}left |w ight |^{2}的最小值，所以上面的目标函数等价于$
$$minfrac{1}{2}left |w ight |^{2} hspace{0.5cm} s.t., gamma_{i}(w^{T}+b)geq 1$$

为了更好地理解接下来的内容，这里插入一段有关对偶性(duality)的补充。详情请见这篇文章，已经清楚的伙伴可以跳过。

简单来说，对于任意一个带约束的优化都可以写成这样的形式：

$$ egin{aligned} min&f_0(x) s.t. &f_i(x)leq 0, quad i=1,ldots,m &h_i(x)=0, quad i=1,ldots,p end{aligned} $$

虽然约束条件能够帮助我们减小搜索空间，但是如果约束条件本身就是比较复杂的形式的话，其实是一件很让人头痛的问题，为此我们希望把带约束的优化问题转化为无约束的优化问题。为此，我们定义 Lagrangian 如下:
$$L(x,lambda, u)=f_0(x)+sum_{i=1}^mlambda_if_i(x)+sum_{i=1}^p u_ih_i(x)$$
令：
$$z(x)=max_{lambdasucceq 0, u}L(x,lambda, u)$$
容易证明，对于满足约束条件的 x，有$f_0(x)=z(x)$，因为约束条件$h_i(x)=0$，即式子最后一项为0，又因为$lambdageq 0$且约束条件$f_i(x)leq 0$，因此式子的第二项最大值为0，所以L的最大值即$z(x)=f_0(x)$.
所以，带约束条件的原问题(primal problem)转换为不带约束条件的优化问题，即：
$$min_x z(x)$$
也即(记为$p^*$)：
$$p^*=min_x max_{lambdasucceq 0, u} L(x, lambda, u)$$
因为如果原始问题有最优值，那么肯定是在满足约束条件的某个 x∗ 取得，而对于所有满足约束条件的$ x$ ，$z(x)$ 和 $f_0(x)$ 都是相等的。
这个原问题(primal problem)的对偶问题(dual problem)将$min$和$max$调换了位置(记为$d^*$)：
$$d^*=max_{lambdasucceq 0, u} min_x L(x, lambda, u)$$
可以证明$d^*leq p^*$，此这个性质叫做弱对偶(weak duality) ，对于所有的优化问题都成立。注意，无论原问题是什么形式，它的对偶问题总是凸优化问题(convex optimization)。
强对偶(strong duality)即$d^*=p^*$，在SVM中满足KTT(Karush-Kuhn-Tucker)条件，通过求解对偶问题间接求解原始问题。

根据上面的补充，继续如下推导。
引入拉格朗日乘子(Lagrange multiplier)构造拉格朗日函数 ,( 其中拉格朗日乘子$alpha=(alpha_{1},alpha_{2},...alpha_{n})^{T}$ )
$$L(w, b, alpha)=frac{1}{2}left |w ight |^{2}-sum_{i=1}^nalpha _{i}(gamma_{i}(w^{T}+b)-1)$$
要求解：
$$ min_{w,b} max_{alpha_{i}succeq 0} L(w, b, alpha)=p^*$$
转换为对偶问题：
$$ max_{alpha_{i}succeq 0} min_{w,b} L(w, b, alpha)=d^*$$

先求$L(w, b, alpha)$对 $w$,$b$的极小，再求对$alpha$的极大。

求$min_{w,b} L(w, b, alpha)$ ：将拉格朗日函数$L(w, b, alpha)$分别对$w$,$b$求偏导数并令其等于0。

$$ abla_{w}L(w, b, alpha)=0 hspace{0.6cm}和 hspace{0.6cm} abla_{b}L(w, b, alpha)=0$$
得到
$$w=sum_{i=1}^nalpha_{i}y_{i}x_{i} hspace{0.6cm}和 hspace{0.6cm}sum_{i=1}^nalpha_{i}y_{i}=0$$
将上面两式带入拉格朗日函数L，得到：
$$min_{w,b} L(w, b, alpha)=-frac{1}{2}sum_{i,j=1}^nalpha_{i}alpha_{j}y_{i}y_{j}x_{i}^Tx_{j}+sum_{i=1}^nalpha_{i}$$

详细推导补充如下：

接下来求$min_{w,b} L(w, b, alpha)$对 $alpha$的极大

$$ max-frac{1}{2}sum_{i,j=1}^nalpha_{i}alpha_{j}y_{i}y_{j}x_{i}^Tx_{j}+sum_{i=1}^nalpha_{i} s.t., alpha_{i}geq 0, i=1,...,n sum_{i=1}^nalpha_{i}y_{i}=0$$
将 $alpha^{*}=(alpha_{1},alpha_{2},...alpha_{n})^{T}$ 求解出来之后，即可求出 $w^{*}$ 和 $b^{*}$
$$w^{*}=sum_{i=1}^nalpha_{i}y_{i}x_{i}$$
$$b^{*}=y_{i}-sum_{i=1}^nalpha_{i}^{*}y_{i}(x_{i} cdot x_{j})$$
二次规划求解可以使用更加优化的SMO(Sequential Minimal Optimization)替代，更加高效，暂时自己还没有看懂，先放着。

个人感觉SVM挺难理解的，前前后后参考了很多资料，感谢大神们的总结和指导，自己仍有不足，若有错漏欢迎指出。有引用部分，侵删。
参考如下：
1.SVM三重境界
2.《统计学习方法》 李航
3.支持向量机：Duality
4.《机器学习》 周志华