专栏首页TechFlow机器学习 | 深入理解SVM,详细推导模型原理(三)

机器学习 | 深入理解SVM,详细推导模型原理(三)

今天是机器学习专题第35篇文章,我们继续SVM模型的原理,今天我们来讲解的是SMO算法。

公式回顾

在之前的文章当中我们对硬间隔以及软间隔问题都进行了分析和公式推导,我们发现软间隔和硬间隔的形式非常接近,只有少数几个参数不同。所以我们着重来看看软间隔的处理。

通过拉格朗日乘子法以及对原问题的对偶问题进行求解,我们得到了二次规划:

\begin{align*} &\min_{\alpha}\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_iy_jx_i^Tx_j -\sum_{i=1}^m\alpha_i \tag{1} \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.& \sum_{i=1}^m \alpha_i y_i = 0 \\ & 0 \le \alpha_i \le C,&i=1,2,3\ldots,m\\ \end{array} \end{align*}

它应该满足的KTT条件如下:

\left\{\begin{align*} \alpha_i \ge 0, \beta_i \ge 0\\ y_i(\omega^T x_i + b) - 1 + \xi_i \ge 0\\\alpha_i(y_i(\omega^Tx_i + b) - 1 + \xi_i)=0\\\xi_i \ge0, \beta_i \xi_i = 0 \end{align*}\right.

也就是说我们要在这些条件下去求解(1)式的极值,在这个约束的情况下,虽然我们已经把式子化简成了只有一种参数

\alpha

,但这个极值又应该怎么求呢?为了解决这个问题,我们需要引入一个新的算法,也是今天的文章的主要介绍的内容——SMO算法

SMO算法简介

SMO的全写是Sequential Minimal Optimization,翻译过来是序列最小优化算法。算法的核心思想是由于我们需要寻找的是一系列的

\alpha

值使得(1)取极值,但问题是这一系列的值我们很难同时优化。所以SMO算法想出了一个非常天才的办法,把这一系列的

\alpha

中的两个看成是变量,其它的全部固定看成是常数。

这里有一个问题是为什么我们要选择两个

\alpha

看成是变量而不选一个呢?选一个不是更加简单吗?因为我们的约束条件当中有一条是

\sum y_i\alpha_i=0

,所以如果我们只选择一个

\alpha

进行调整的话,那么显然会破坏这个约束。所以我们选择两个,其中一个变化,另外一个也随着变化,这样就可以保证不会破坏约束条件了。

为了方便叙述,我们默认选择的两个

\alpha

分别是

\alpha_1, \alpha_2

。另外由于我们涉及

x_i^Tx_j

的操作,我们令

K_{ij}=x_i^Tx_j

。这样上面的(1)式可以写成:

\begin{align*} &\min_{\alpha1,\alpha_2}\frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2}K_{22}\alpha_2^2 + y_1y_2\alpha_1\alpha_2 - (\alpha_1 + \alpha_2) + y_1\alpha_1\sum_{i=3}^my_i\alpha_iK_{i1} + y_2\alpha_2\sum_{i=3}^my_i\alpha_iK_{i, 2} + Constant \tag{2} \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.& \alpha_1y_1 + \alpha_2y_2 = -\sum_{i=3}^m y_i\alpha_i \\ & 0 \le \alpha_i \le C,&i=1,2,3\ldots,m\\ \end{array} \end{align*}

其中由于

y_1 = \pm 1

,所以

y_i^2 = 1

,上面的Constant表示除了

\alpha_1, \alpha_2

以外的常数项。我们假设

\alpha_1y_1 + \alpha_2y_2 = k

,其中

\alpha_1, \alpha_2 \in [0, C]

,由于

y_i

只有两个选项1或者-1,所以我们可以分情况讨论。

分情况讨论

首先我们讨论

y_1

y_2

不同号时,无非两种,第一种情况是

\alpha_1 - \alpha_2 = k

,也就是

\alpha_2 = \alpha_1 - k

,我们假设此时k > 0,第二种情况是

\alpha_2 = \alpha_1 + k

,我们假设此时k < 0。我们很容易发现对于第一种情况,如果 k < 0,其实就是第二种情况,同样对于第二种情况,如果k > 0其实就是第一种情况。这变成了一个线性规划问题,我们把图画出来就非常清晰了。

针对第一种情况,我们可以看出来

\alpha_2

的范围是

(0, C - \alpha_2 + \alpha_1)

,第二种情况的范围是

(\alpha_2 - \alpha_1, C)

。这里我们把k又表示回了

\alpha_1,\alpha_2

,由于我们要通过迭代的方法来优化

\alpha_1,\alpha_2

的取值,所以我们令上一轮的

\alpha_1, \alpha_2

分别是

\alpha_{1o}, \alpha_{2o}

。这里的o指的是old的意思,我们把刚才求到的结论综合一下,就可以得到

\alpha_2

下一轮的下界L是

\max(0, \alpha_{2o} - \alpha_{1o})

,上界H是

\min(C+\alpha_{2o} - \alpha_{1o}, C)

同理,我们画出

\alpha_1, \alpha_2

同号时的情况,也有k > 0 和 k < 0两种。

第一种情况是

y_1 = y_2 = 1

,这时

\alpha_1 + \alpha_2 = k

,此时 k > 0,对应的

\alpha_2

的取值是

(0, \alpha_{1o} + \alpha_{2o})

。当k > C的时候,这时候也就是右上角1'的情况,此时过了中间的虚线,

\alpha_2

的范围是

(\alpha_{1o} + \alpha_{2o} - C, C)

第二种情况是

y_1 = y_2 = -1

,此时

\alpha_1 + \alpha_2 = k

,此时k < 0,由于这个时候是不符合约束条件

0\le \alpha_1, \alpha_2 \le C

的,所以此时没有解。这两种情况综合一下,可以得到下界L是

\max(0, \alpha_{1o} + \alpha_{2o} - C)

,上界H是

\min(\alpha_{1o} + \alpha{2o}, C)

我们假设我们通过迭代之后得到的下一轮

\alpha_2

\alpha_{2new, unc}

,这里的unc是未经过约束的意思。那么我们加上刚才的约束,可以得到:

\begin{equation} \alpha_{2new}=\left\{ \begin{aligned} & H &\quad \alpha_{2new, unc} >H \\ & \alpha_{2new, unc} \quad &L \le \alpha_{2new, unc} \le H \\ & L &\quad \alpha_{2new, unc} < L \end{aligned} \right. \end{equation}

这里的

\alpha_{2new,unc}

是我们利用求导得到取极值时的

\alpha_2

,但问题是由于存在约束,这个值并不一定能取到。所以上述的一系列操作就是为了探讨约束存在下我们能够取到的极值情况。如果看不懂推导过程也没有关系,至少这个结论需要搞明白。

代入消元

我们现在已经得到了下一轮迭代之后得到的新的

\alpha_2

的取值范围,接下来要做的就是像梯度下降一样,求解出使得损失函数最小的

\alpha_1

\alpha_2

的值,由于

\alpha_1 + \alpha_2

的值已经确定,所以我们求解出其中一个即可。

我们令

\alpha_1y_1 + \alpha_2y_2 = \xi

,那么我们可以代入得到

\alpha_1 = y_1(\xi - \alpha_2y_2)
\alpha_1 = y_1(\xi - \alpha_2y_2)

我们把这个式子代入原式,得到的式子当中可以消去

\alpha_1

,这样我们得到的就是只包含

\alpha_2

的式子。我们可以把它看成是一个关于

\alpha_2

的函数,为了进一步简化,我们令

v_i = \sum_{j=3}^my_j \alpha_j K{i, j} , E_i = f(x_i ) - y_i = \sum_{j=1}^m \alpha_jy_jK_{i, j} + b - y_i

这里的

E_i

表示的是第i个样本真实值与预测值之间的差,我们把上面两个式子代入原式,化简可以得到:

f(\alpha_2) = \frac12 K_{11}(\xi - \alpha_2y_2) + \frac12K_{22}\alpha_2^2 + y_2K_{12}(\xi- \alpha_2y_2)\alpha_2 - (\xi - \alpha_2y_2)y_1 - \alpha_2 + (\xi - \alpha_2y_2)v_1 + y_2\alpha_2v_2

接下来就是对这个式子进行求导求极值,就是高中数学的内容了。

\frac {\partial W}{\partial\alpha_2}=K_{11}\alpha_2 + K_{22}\alpha_2 - 2K_{12}\alpha_2 - K{11}\xi y_2+K{12}\xi y_2 + y_1y_2 -1 - v_1y_2 + y_2v_2 = 0

我们求解这个式子,最终可以得到:

\alpha_{2new, unc} = \alpha_{2o} + \frac{y_2(E_1 - E_2)}{K_{11}+K_{22} - 2 K_{12}}

我们根据这个式子就可以求出

\alpha_2

下一轮迭代之后的值,求出值之后,我们在和约束的上下界比较一下,就可以得到在满足约束的情况下可以取到的最好的值。最后,我们把

\alpha_2

代入式子求解一下

\alpha_1

。这样我们就同时优化了一对

\alpha

参数,SMO算法其实就是重复使用上面的优化方法不停地选择两个参数进行优化,直到达到迭代次数,或者是不能再带来新的提升为止。

整个算法的逻辑其实是不难理解的,但是中间公式的推导过程实在是多了一些。这也是我把SVM模型放到机器学习专题最后来讲解的原因,在下一篇文章当中,我们将会为大家带来SVM模型核函数的相关内容,结束之后我们机器学习专题就将迎来尾声了,再之后我们将会开始深度学习的专题,敬请期待吧。

今天的文章到这里就结束了,如果喜欢本文的话,请来一波素质三连,给我一点支持吧(关注、在看、点赞)。

- END -

本文分享自微信公众号 - TechFlow(techflow2019),作者:梁唐

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-01

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 高等数学——复杂函数的求导方法

    上一篇文章我们复习了函数求导的定义和一些常见函数的导数,今天这篇文章我们回顾一下复杂函数的求导方法。先强调一下,今天的文章很重要,想要看懂机器学习各种公式推导,...

    TechFlow-承志
  • 原创 | Git操作文件的时候手贱了,怎么恢复?

    我们在使用git的过程当中很难避免的一点就是手贱,因为人嘛总有犯错疏忽的时候,有时候一不小心就操作错了。我也经常遇到这种情况,所以这时候对git的了解和掌握就非...

    TechFlow-承志
  • 机器学习基础——让你一文学会朴素贝叶斯模型

    今天这篇文章和大家聊聊朴素贝叶斯模型,这是机器学习领域非常经典的模型之一,而且非常简单,适合初学者入门。

    TechFlow-承志
  • 一个传统应用的自白:戴姆勒核心系统云原生改造实战

    说明:本文为戴姆勒大中华区架构师朱傲老师在 2020 DevOps 线上峰会的分享整理而成。

    DevOps时代
  • 传统企业疫情期间如何保障工作正常开展

    疫情当下,企业如何高效利用互联网技术手段,解决避免聚集风险,实现企业员工高效协作,远程办公,为企业正常运转保驾护航。通过案例分享通过在线客服、远程协作、智能客服...

    云大学小编
  • 数学,常识和运气:西蒙斯MIT演讲(视频+全文翻译)

    大数据文摘
  • 霍金没有提 AI 威胁论,他的新目标是带领人类移民外星球(上篇)

    今天,第五届腾讯WE大会在京举行,“超级网红”,“黑洞”理论提出者,剑桥大学教授史蒂夫霍金霍金,突破摄星执行董事、前NASA艾姆斯研究中心主任Pete Word...

    AI科技大本营
  • 向宇宙宣告:人类文明未来的信标(I)

    假如我们可以在太阳系周围放上信标(Beacon),这些信标能够在那里待上数十亿年,记录我们的文明历程。它们应该是什么样子?

    WolframChina
  • Repractise简介篇:Web开发的七天里

    本来想着的只是画一个如下面的七天图来说说Web开发的,随后又想了想这似乎是一个非常的Web开发介绍。 ? 第一天:新的开始 我们迎来了我们的新的一个项目,看起来...

    Phodal
  • 学机器学习有必要懂数学吗?深入浅出机器学习与数学的关系

    小黑,Datawhale团队成员,秦时明月十年铁粉,本科就读于山西大学,保研至天津大学并硕博连读,现为2018级博士,研究方向:脑机接口。

    用户1564362

扫码关注云+社区

领取腾讯云代金券