Categories

Calendar

July 2016
M T W T F S S
« Jun    
 123
45678910
11121314151617
18192021222324
25262728293031

支持向量机:Numerical Optimization

本文是“支持向量机系列”的第五篇,参见本系列的其他文章

作为支持向量机系列的基本篇的最后一篇文章,我在这里打算简单地介绍一下用于优化 dual 问题的 Sequential Minimal Optimization (SMO) 方法。确确实实只是简单介绍一下,原因主要有两个:第一这类优化算法,特别是牵涉到实现细节的时候,干巴巴地讲算法不太好玩,有时候讲出来每个人实现得结果还不一样,提一下方法,再结合实际的实现代码的话,应该会更加明了,而且也能看出理论和实践之间的差别;另外(其实这个是主要原因)我自己对这一块也确实不太懂。 :p

先回忆一下我们之前得出的要求解的 dual 问题:

\[
\begin{align}
\max_\alpha &\sum_{i=1}^n\alpha_i – \frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\kappa( x_i,x_j) \\
s.t., &0\leq \alpha_i\leq C, i=1,\ldots,n \\
&\sum_{i=1}^n\alpha_iy_i = 0
\end{align}
\]

对于变量 $\alpha$ 来说,这是一个 quadratic 函数。通常对于优化问题,我们没有办法的时候就会想到最笨的办法——Gradient Descent ,也就是梯度下降。注意我们这里的问题是要求最大值,只要在前面加上一个负号就可以转化为求最小值,所以 Gradient Descent 和 Gradient Ascend 并没有什么本质的区别,其基本思想直观上来说就是:梯度是函数值增幅最大的方向,因此只要沿着梯度的反方向走,就能使得函数值减小得越大,从而期望迅速达到最小值。当然普通的 Gradient Descent 并不能保证达到最小值,因为很有可能陷入一个局部极小值。不过对于 quadratic 问题,极值只有一个,所以是没有局部极值的问题。

另外还有一种叫做 Coordinate Descend 的变种,它每次只选择一个维度,例如 $\alpha=(\alpha_1,\ldots,\alpha_n)$ ,它每次选取 $\alpha_i$ 为变量,而将 $\alpha_1,\ldots,\alpha_{i-1},\alpha_{i+1},\ldots,\alpha_n$ 都看成是常量,从而原始的问题在这一步变成一个一元函数,然后针对这个一元函数求最小值,如此反复轮换不同的维度进行迭代。Coordinate Descend 的主要用处在于那些原本很复杂,但是如果只限制在一维的情况下则变得很简单甚至可以直接求极值的情况,例如我们这里的问题,暂且不管约束条件,如果只看目标函数的话,当 $\alpha$ 只有一个分量是变量的时候,这就是一个普通的一元二次函数的极值问题,初中生也会做,带入公式即可。

然而这里还有一个问题就是约束条件的存在,其实如果没有约束条件的话,本身就是一个多元的 quadratic 问题,也是很好求解的。但是有了约束条件,结果让 Coordinate Descend 变得很尴尬了:比如我们假设 $\alpha_1$ 是变量,而 $\alpha_2,\ldots,\alpha_n$ 是固定值的话,那么其实没有什么好优化的了,直接根据第二个约束条件 $\sum_{i=1}^n\alpha_iy_i = 0$ ,$\alpha_1$ 的值立即就可以定下来——事实上,迭代每个坐标维度,最后发现优化根本进行不下去,因为迭代了一轮之后会发现根本没有任何进展,一切都停留在初始值。

所以 Sequential Minimal Optimization (SMO) 一次选取了两个坐标维度来进行优化。例如(不失一般性),我们假设现在选取 $\alpha_1$ 和 $\alpha_2$ 为变量,其余为常量,则根据约束条件我们有:

\[
\sum_{i=1}^n\alpha_iy_i = 0 \Rightarrow \alpha_2=\frac{1}{y_2}\left(\sum_{i=3}^n\alpha_iy_i-\alpha_1y_1\right) \triangleq y_2\left(K-\alpha_1y_1\right)
\]

其中那个从 3 到 n 的作和由于都是常量,我们统一记作 $K$ ,然后由于 $y\in\{-1,+1\}$ ,所以 $y_2$ 和 $1/y_2$ 是完全一样的,所以可以拿到分子上来。将这个式子带入原来的目标函数中,可以消去 $\alpha_2$ ,从而变成一个一元二次函数,具体展开的形式我就不写了,总之现在变成了一个非常简单的问题:带区间约束的一元二次函数极值问题——这个也是初中就学过求解方法的。唯一需要注意一点的就是这里的约束条件,一个就是 $\alpha_1$ 本身需要满足 $0\leq\alpha_1\leq C$ ,然后由于 $\alpha_2$ 也要满足同样的约束,即:

\[
0\leq y_2 (K-\alpha_1y_1) \leq C
\]

也可以得到 $\alpha_1$ 的一个可行区间,同 $[0,C]$ 交集即可得到最终的可行区间。这个问题可以从图中得到一个直观的感觉。原本关于 $\alpha_1$ 和 $\alpha_2$ 的区间限制构成途中绿色的的方块,而另一个约束条件 $y_1\alpha_1 + y_2\alpha_2 = K$ 实际上表示一条直线,两个集合的交集即是途中红颜色的线段,投影到 $\alpha_1$ 轴上所对应的区间即是 $\alpha_1$ 的取值范围,在这个区间内求二次函数的最大值即可完成 SMO 的一步迭代。

同 Coordinate Descent 一样,SMO 也会选取不同的两个 coordinate 维度进行优化,可以看出由于每一个迭代步骤实际上是一个可以直接求解的一元二次函数极值问题,所以求解非常高效。此外,SMO 也并不是依次或者随机地选取两个坐标维度,而是有一些启发式的策略来选取最优的两个坐标维度,具体的选取方法(和其他的一些细节),可以参见 John C. Platt 的那篇论文 Fast Training of Support Vector Machines Using Sequential Minimal Optimization 。关于 SMO ,我就不再多说了。如果你对研究实际的代码比较感兴趣,可以去看 LibSVM 的实现,当然,它那个也许已经不是原来版本的 SMO 了,因为本来 SVM 的优化就是一个有许多研究工作的领域,在那些主要的优化方法之上,也有各种改进的办法或者全新的算法提出来。

除了 LibSVM 之外,另外一个流行的实现 SVMlight 似乎是用了另一种优化方法,具体可以参考一下它相关的论文 Making large-Scale SVM Learning Practical 。

此外,虽然我们从 dual 问题的推导中得出了许多 SVM 的优良性质,但是 SVM 的数值优化(即使是非线性的版本)其实并不一定需要转化为 dual 问题来完成的,具体做法我并不清楚,不过这方面的文章也不少,比如 2007 年 Neural Computation 的一篇 Training a support vector machine in the primal 。如果感兴趣可以参考一下。 :)

15 comments to 支持向量机:Numerical Optimization

  • Kyle_BC

    在讲SMO的时候Y2是在分母位置上的,怎么一下子又跳上来了?

  • Chrysalis

    OH YEAH 看完啦!

    不错喔!针对那个关于alpha的约束条件。我觉得这条件已经表示了真正的变量其实只有n-1个。这n-1个alpha确定之后,最后那个利用Y belongs to {-1,1} & Alpha > 0 就可以确定下来了。

    我再去看看SMO的那篇论文~

    • 是一个迭代,并不是说“每一步就能完全确定 alpha 的一个分量,最后一个分量根据其他分量推算就可以了”。按照那个迭代的启发式方法的话,每一步迭代会选择哪两个分量都不是事先知道的。

      嗯,你要是看明白了,回来之后给我讲吧(好像要好久啊。。。-.-bb)

  • 你这里的文章将的更是深入简出一些 不错

  • gxf

    终于看完SVM这个系列了,对我来说只是揭开了SVM冰山的一角吧,继续努力!继续关注你的博客!

  • qun

    SVM系列看完了。……^_^

  • ftutor

    很赞啊,校友!

  • HuoHuoHuo

    赞kid学长,看完之后发现之前自己的一些理解原来都是错的TT。。继续努力^^

  • Meng

    大神膜拜!我近期在学习SVM,想修士毕业写一篇关于SVM的论文。读了你的博客觉得再一次透彻了解了很多知识点!非常感谢ORL。但现在我一个问题迫切希望大神可以给些建议,SVM研究范围很大,我想精确一个范围去研究,比如说样本不均衡问题的解决,同时我又很担心自己的数学理解不彻底,不能够深入研究而最终进行不下去而陷入僵局…总体来说,我希望大神能否可以给我一个关于SVM的研究主题方向,这个主题不会牵扯太多太多数学理论问题。非常非常感谢!

    • 你好,如果你编程比较扎实又对优化有兴趣的话,可以考虑研究一下 SVM 的并行或者 GPU 计算之类的。现在 Deep Learning 在用 GPU 计算之后运算速度在比较大规模的数据上也可以接受,而且结果精度也很好,但是现在主要的 SVM 实现像 LibSVM 和 LibLinear 之类的都还是单线程计算,比较起来速度就慢了,如果在这个方面能有所突破的话,应该是非常好的,而且这个方向并不需要太多的数学和理论方面的知识,虽然可能需要对优化的东西比较熟悉。

  • zhu

    学长啥时候写写deep learning的文章啊

  • jwen

    对于alpha_i 和alpha_j的选择有没有什么要求呢。还是任意选择就可以了?

  • ercxk

    希望能看到这篇文章:
    支持向量机:Regression —— 关于如何使用 SVM 来做 Regression 的简介。

Leave a Reply

 

 

 

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>