SVM支持向量机基本型推导

推导支持向量机的求解。

推导

SVM示意图

假设总共有m个样本。

在上述示意图中,分类的超平面为

\bold{\omega}^T\bold{x} + b = 0

一个样本点到超平面的距离为

d = \frac{|\bold{\omega}^T\bold{x}_i + b|}{||\bold{\omega}||}

支持向量机的分类判定并非以超平面为界限,而是

\bold{\omega}^T\bold{x} + b \geq +1 , y_i = +1

\bold{\omega}^T\bold{x} + b \leq -1 , y_i = -1

使等号成立的几个训练样本点距离超平面最近,它们被称之为“支持向量”(support vector)。最优的SVM应该最大化两个异类支持向量到超平面的距离之和,即间隔(margin)

\gamma = \frac{2}{||\omega||}

整个问题可以简化为

\max \frac{2}{||\omega||}

s.t.\quad y_i(\bold{\omega}^T\bold{x}_i + b) \geq 1,\quad i=1,2,…m

等价于

\min \frac{1}{2} ||\omega||^2

s.t.\quad y_i(\bold{\omega}^T\bold{x}_i + b) \geq 1,\quad i=1,2,…m

这里加入\frac{1}{2}是为了求偏导时抵消。

对这个凸二次规划问题,我们采取拉格朗日法解决。这里先得到它的对偶问题。

拉格朗日函数为

L(\omega, b, \alpha) = \frac{1}{2} ||\omega||^2 + \Sigma_{i=1}^m\alpha_i(1-y_i(\bold{\omega}^T\bold{x}_i + b) )

其中 \alpha_i为拉格朗日乘子。需要满足KKT条件

  1. \nabla_\omega L(\omega, b, \alpha) = ||\omega|| – \Sigma_{i=1}^m\alpha_i(1-y_i(\bold{\omega}^T\bold{x}_i + b) ) = 0
  2. \nabla_b L(\omega, b, \alpha) = \Sigma_{i=1}^m\alpha_i y_i = 0
  3. \nabla_\alpha L(\omega, b, \alpha) = 0 (无意义)
  4. \alpha_i \geq 0,\quad i=1,2,…m
  5. \alpha_i(1-y_i(\omega^T \bold{x}_i+b)) = 0, \quad i=1,2,…m
  6. 1-y_i(\omega^T \bold{x}_i+b) \leq 0, \quad i=1,2,…m

由1、2分别可以得到

  1. \omega = \Sigma_{i=1}^m \alpha_i y_i \bold{x}_i
  2. \Sigma_{i=1}^m\alpha_i y_i = 0

将其带入拉格朗日函数可以得到对偶问题为

\max \Sigma_{i=1}^m\alpha_i – \frac{1}{2}\Sigma_{i=1}^m\Sigma_{j=1}^m \alpha_i\alpha_j y_i y_i \bold{x}_i\bold{x}_j

s.t. \quad \alpha_i \geq 0,\quad \Sigma_{i=1}^m \alpha_i y_i = 0 ,\quad i=1,2,…m

求解出最优解\alpha^*之后,可以得到分类平面为

\bold{\omega}^T\bold{x} + b = (\Sigma_{i=1}^m \alpha^*_i y_i \bold{x}_i )^T \bold{x} + b= 0

分析

  • 为什么要将原问题转化成对偶问题?
  1. 可以将原问题中的不等式约束转化为对偶问题中的等式约束。
  2. 方便核函数的引入。
  3. 改变了问题的复杂度。由求特征向量\omega转化为求比例系数a,在原始问题下,求解的复杂度与样本的维度有关,即\omega的维度。在对偶问题下,只与样本数量有关。
  • 怎么理解最终模型只与支持向量有关?

对于训练样本 (\bold{x}_i, y_i) ,有 \alpha_i = 0 y_i(\omega^T\bold{x}_i+b) = 1

\alpha_i = 0 时,该样本不会出现在最优解中,不会对分类平面产生影响。

\alpha_i > 0 时, y_i(\omega^T\bold{x}_i+b) = 1 ,该样本位于最大间隔边界上,是一个支持向量。

所以训练完成后,大部分训练样本都不需要保留,最终模型只与支持向量有关

参考资料

  1. 周志华. 机器学习[M]. 清华大学出版社, 2016
  2. https://zhuanlan.zhihu.com/p/35755150

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

发表评论

邮箱地址不会被公开。 必填项已用*标注