SMO

SVM基础

SVM是vapnik发明的线性分类器,处理的是标签为{-1,1}的数据,其理论支持为经验风险最小化。经验风险最小化就是VC维最小化,在SVM中的体现为最大化分类间隔,因为线性分类器的VC维与最大分类间隔的平方成反比。具体的VC维表示为下公式

\begin{equation}VC-dimension\leq min\{\frac{R^2}{M^2},n\}+1\end{equation}

其中,R为包围所有数据点的最小球半径,M为分类间隔的一半,n为样本数目大小。下图就比较形象的说明了SVM是干什么用的。

SVM目标

最终SVM得到的线性分类器的公式如下

\begin{equation}u=w^Tx-b\end{equation}

而参数\(w,b\)所遵循的条件为

\begin{equation}\forall i \, y_i(w^Tx_i-b)\geq 1\end{equation}

对于任何一个测试点\(x\),如果\(u\)的值大于等于1,则这个点被标注为1。否则如果\(u\)小于等于-1,则这个点标注为-1.这个分类器的分类间隔为

\begin{equation}\frac{1}{w^Tw}\end{equation}

所以我们如果要最大化分类间隔,则需要最小化\(\frac{1}{2}w^Tw\)。所以当前问题转变为一个凸优化问题

\begin{equation}\begin{split}minimize \quad & \frac{1}{2}w^Tw\\subject\,to \quad &\forall i: y_i(w^Tx_i-b)\geq 1\end{split}\end{equation}

我们可以得到等价的对偶问题

\begin{equation}\begin{split}minimize \quad &\frac{1}{2}w^Tw-\sum{a_i(y_i(w^Tx_i-b)-1)}\\subject \, to \quad & \forall i \ a_i\geq 0\\&\forall i \ y_i(w^Tx_i-b)-1\geq 0\\& \forall i \ a_i(y_i(w^Tx_i-b)-1)=0\end{split}\end{equation}

此时得到最小值的KKT条件为

\begin{equation}\begin{split}w^T-\sum{a_iy_i{x_i}^T}&=0\\\sum{a_iy_i}&=0\\\forall i \ a_i&\geq 0\\\forall i \ y_i(w^Tx_i-b)-1&\leq 0\\\forall i \ a_i(y_i(w^Tx_i-b)-1)&=0\end{split}\end{equation}

将上面的两个等式带入到对偶问题中,从而得到了下面的简化形式,不过问题仍然是等价的。

\begin{equation}\begin{split}minimize \quad &\frac{1}{2}\sum_{i=1}^{n}{}\sum_{j=1}^{n}{y_iy_j{x_i}^Tx_ja_ia_j} -\sum_{i=1}^{n}{a_i}\\subject \ to\quad & \forall i \ a_i\geq 0\\&\sum_{i=1}^{n}y_ia_i=0\end{split}\end{equation}

在得出上述问题的最优解中\(a_i\)的取值之后,我们可以得到\(w,b\)的表达式.

\begin{equation}\begin{split}w&=\sum{a_iy_ix_i}\\b&=w^Tx_k-y_k\quad for\ a_k>0\end{split}\end{equation}

上面所陈述的是线性可分的情况,如果数据并不是线性可分的,则我们需要引入松弛变量\(\xi\)来代表偏离程度。

\begin{equation}\begin{split}minimize \quad & \frac{1}{2}w^Tw+C\sum{{\xi}_i}\\subject\,to \quad &\forall i\ y_i(w^Tx_i-b)\geq 1-{\xi}_i\\&\forall i\ {\xi}_i\geq0\end{split}\end{equation}

上面问题的对偶问题为

\begin{equation}\begin{split}minimize \quad &\frac{1}{2}w^Tw+C\sum{{\xi}_i}-\sum{a_i(y_i(w^Tx_i-b)-1+{\xi}_i)}+\sum{{\mu}_i{\xi}_i}\\subject \, to \quad & \forall i \ a_i\geq 0\\&\forall i \ y_i(w^Tx_i-b)-1+{\xi}_i\geq 0\\& \forall i \ a_i(y_i(w^Tx_i-b)-1+{\xi}_i)=0\\&\forall i\ {\xi}_i\geq0\\&\forall i\ {\mu}_i{\xi}_i=0\\&\forall i \ {\mu}_i\geq 0\end{split}\end{equation}

此时我们根据KKT的最小值条件,可以得到而外的三个等式。

\begin{equation}\begin{split}w&=\sum{a_iy_ix_i}\\0&= \sum{a_iy_i}\\a_i&=C-{\mu}_i\end{split}\end{equation}

将这些等式带入,可以得到下面的等价问题。

\begin{equation}\begin{split}minimize \quad &\frac{1}{2}\sum_{i=1}^{n}{}\sum_{j=1}^{n}{y_iy_j{x_i}^Tx_ja_ia_j} -\sum_{i=1}^{n}{a_i}\\subject \ to\quad & \forall i \ 0\leq\ a_i\leq C\\&\sum_{i=1}^{n}y_ia_i=0\end{split}\end{equation}

可以看出,引入松弛变量与未引入松弛变量所得到的问题基本差不多。令\(u=w^Tx-b\),从得到的结果逆向推理,我们可以得到下面的式子。

\begin{equation}\begin{split}a_i=0&\rightarrow{\mu}_i=C\rightarrow {\xi}_i=0\rightarrow\ u-1+{\xi}_i\geq 0\rightarrow y_iu_i \geq 1\\0< a_i<C&\rightarrow {\mu}_i\neq 0\rightarrow {\xi}_i=0\rightarrow\ u-1+{\xi}_i= 0 \rightarrow y_iu_i=1\\a_i=C&\rightarrow {\mu}_i=0\rightarrow{\xi}_i\geq 0\rightarrow u-1+{\xi}_i= 0\rightarrow y_iu_i \leq 1\end{split}\end{equation}

上面这个性质非常重要,是理解SMO算法的关键(其实是可以左右推导的,这里没有写出来,忘了那个符号怎么写了)。

SMO优化方法

现在我们的问题就是,如何快速的求解下面这个优化问题。

\begin{equation}\begin{split}minimize \quad &\frac{1}{2}\sum_{i=1}^{n}{}\sum_{j=1}^{n}{y_iy_j{x_i}^Tx_ja_ia_j} -\sum_{i=1}^{n}{a_i}\\subject \ to\quad & \forall i \ 0\leq\ a_i\leq C\\&\sum_{i=1}^{n}y_ia_i=0\end{split}\end{equation}

解决带不等式限制的凸优化问题,采取的一般都是内点法。但是内点法的代价太大,需要存储一个\(n^2\)的矩阵,在内存有限的条件下不可行,且每次求全局导数花费时间很多,此外还牵涉到数值问题。而SMO是解决二次优化问题的神器。他每次选择两个拉格朗日乘子 \(a_i,a_j\)来求条件最小值,然后更新\(a_i,a_j\)。由于在其他拉格朗日乘子固定的情况下,\(a_i,a_j\)有如下关系

\begin{equation}\sum{a_iy_i}=0\rightarrow a_iy_i+a_jy_j=t\end{equation}

这样\(a_i\)就可以通过\(a_j\)表示出来,此时优化问题可以转变为一个变量的二次优化问题,这个问题的计算量非常少。所以SMO包括两个过程,一个过程选择两个拉格朗日乘子,这是一个外部循环,一个过程来求解这两个变量的二次优化问题,这个是循环内过程。我们先来解决两个变量的lagrange multipliers问题,然后再去解决乘子的选择问题。

Two Lagrange Multiplier

为了计算两个lagrange Multiplier的优化问题,SMO首先计算这两个乘子的取值范围,然后再这个范围限制下解决二次优化问题。为了书写方便,现在用\(1,2\)来代替\(i,j\)。这两个变量之间的关系我们之前已经给出了\(a_1y_1+a_2y_2=k\),下面这幅图生动形象的解释了这两个变量的关系。

双变量关系

现在我们来讨论在进行双变量二次优化时\(a_2\)的取值范围。如果\(y_1!=y_2\),则\(a_2\)的下界\(L\)和上界\(H\)可以表示为

\begin{equation}L=max(0,a_2-a_1),\quad H=min(C,C+a_2-a_1)\end{equation}

反之,如果\(y_1=y_2\),则\(a_2\)的下界\(L\)和上界\(H\)可以表示为

\begin{equation}L=max(0,a_2+a_1-C),\quad H=min(C,a_2+a_2)\end{equation}

而此时的优化目标为

\begin{equation}\begin{split}& minimize \quad \frac{1}{2}\sum_{i=1}^{n}{}\sum_{j=1}^{n}{y_iy_j{x_i}^Tx_ja_ia_j} -\sum_{i=1}^{n}{a_i}\\&=2{x_1}^Tx_2y_1y_2a_1a_2+a_1y_1{x_1}^TR_1+a_2y_2{x_2}^TR_1-C(a_1+a_2)-R_2\end{split}\end{equation}

这里的\(R_1,R_2\)都是与\(a_1,a_2\)无关的项。事实上,在SVM中经常使用核函数来将输入映射到高维空间,内积只是核函数的一种。在这里,我们做三个步骤:替换内积为核函数,用\(a_2\)表示\(a_1\),同时对目标函数求\(a_2\)的二阶导数。这里我就省略一下过程,最后可以得到下面这个结果。

\begin{equation}\eta=K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2)\end{equation}

在一般情况下,目标函数是正定的。因此在\(a_2\)的变动范围内,目标函数可以取到极小值,而且\(\eta\)会大于0.在这种情况下,SMO可以得到使得目标函数最小的\(a_2^{new}\)

\begin{equation}a_2^{new}=a_2+\frac{y_2(E_1-E_2)}{\eta}\end{equation}

其中\(E_i=u_i-y_i\),即第\(i\)个训练样本的偏移。但是,我们还需要考虑\(a_2\)的取值范围,所以我们最后得到的\(a_2\)的新值为

\begin{equation}a_2^{\text{new,clip}}=\left \{\begin{aligned}H\quad & if \quad a_2^{\text{new}}\geq H\\a_2^{\text{new}} \quad & if\ L<a_2^{\text{new}}<H\\L\quad & if \quad a_2^{\text{new}}\leq L\end{aligned}\right.\end{equation}

同时,我们可以更新\(a_1\),令\(s=y_1y_2\)

\begin{equation}a_1^{\text{new}}=a_1+s(a_2-a_2^{\text{new,clip}})\end{equation}

至此,双变量的二次规划问题基本解决,现在唯一一个遗留的问题就是,如果核矩阵不是正定,那么这个时候怎么办。 当然,有效的核函数所构建的核矩阵一定是正定的,这个是核函数有效的Mercer条件。对于坑爹的非正定核的情况,我们需要手工计算在直线两端的目标函数的值,通过比较来确定如何更新这两个变量。这里我就懒得去写公式了,直接照搬SMO那篇paper里面的说明。

![非正定条件更新]{{attach}image\SVM\anormal_kernal.png}

乘子选择问题

由于对于任何两个乘子,只要其中一个乘子违反了KKT条件,则我们总能通过双变量二次优化使目标函数减小。因此,收敛是一定的,现在需要考虑的是收敛的速度,及如何选取候选的两个乘子来加快收敛。

目前有两种启发式的方法,一种用来寻找第一个乘子,另外一种用来寻找第二个乘子。第一个启发方法构成了SMO的外部循环。这个启发方法首先对整个训练集合进行搜索,寻找那些违反下式KKT条件的样例。

\begin{equation}\begin{split}a_i=0&\rightarrow{\mu}_i=C\rightarrow {\xi}_i=0\rightarrow\ u-1+{\xi}_i\geq 0\rightarrow y_iu_i \geq 1\\0< a_i<C&\rightarrow {\mu}_i\neq 0\rightarrow {\xi}_i=0\rightarrow\ u-1+{\xi}_i= 0 \rightarrow y_iu_i=1\\a_i=C&\rightarrow {\mu}_i=0\rightarrow{\xi}_i\geq 0\rightarrow u-1+{\xi}_i= 0\rightarrow y_iu_i \leq 1\end{split}\end{equation}

如果一个数据样例违反了上述KKT条件,则我们将这个样例数据加入到候选集合。通过这样的判别条件,我们对所有的乘子不为0或\(C\)的数据进行扫描,得到了一个待优化的候选集合。

Published:
2015-04-28 20:09
Category:
Tag: