0%

【图解例说机器学习】支持向量机 (SVM)

支持向量机(Support Vector Machine, SVM),是一种常见的有监督的学习模型,通常用来进行模式识别、分类以及回归分析。本文主要介绍SVM在二分类问题的应用。


线性可分支持向量机

我们还是以【图解例说机器学习】感知机的二分类例子 (Toy Example) 说起。如图1,假设有一个线性可分的训练集,其中有三个样例 ($\mathrm x_1,\mathrm x_2, \mathrm x_3$),分别标记为正例(红色方块),反例(蓝色圆圈)。这里的 $x^{(1)},x^{(2)}$为训练样例的$2$个特征。

图1

感知机的目的就是找到一个超平面 (在二维空间为一条直线) 能够将这三个样例分开。显然,这样的直线有无数条,比如图中的直线 $f(\mathrm x)=x^{(1)}+x^{(2)}-4=0, f(\mathrm x)=2x^{(1)}+x^{(2)}-5=0$ 就是可能得到其中的两条。

感知机的结果,即分类超平面,与参数的初始值有关,也和在每次迭代时选取的误分类样例有关。在上面例子中,得到的两个分类超平面中,直觉上,直线$x^{(1)}+x^{(2)}-4=0$的分类效果要好于$2x^{(1)}+x^{(2)}-5=0$的分类效果好。这是因为,直线$x^{(1)}+x^{(2)}-4=0$位于正负样例的中间位置,其对训练样例的扰动具有较好的鲁棒性。由于训练集的局限性或者噪声,训练集外的样例可能比较接近分类超平面,此时直线$2x^{(1)}+x^{(2)}-5=0$就会使得这些样例错误分类,即泛化能力较差。

为了克服感知机的上述问题,SVM的目的就是找到最佳的分类超平面,而不是仅仅对训练集的样例正确分类,也考虑如何对未见样例具备较强的泛化能力。


SVM 分类模型

间隔

在中学时,我们学过一个点$x$到一条直线$ax+by+c=0$的距离可以为$\lvert ax+by+c\rvert/\sqrt{a^2+b^2}$。类似地,空间中一点$\mathrm x$ 到一个超平面$\omega_0+\mathrm w^{\mathrm T}\mathrm x=0$的距离为:

关于公式(1)的直观表示如下图2所示:

图2

在图2中,$\frac{\mathrm w}{\lvert\mathrm w\rvert}$ 是直线$x^{(1)}+x^{(2)}-3=0$的单位法向量,$\mathrm x_1^\perp, \mathrm x_2^\perp$ 分别为$\mathrm x_1, \mathrm x_2$ 在该直线的投影。此时空间中的任意一点$\mathrm x$可以由其到该直线的投影$\mathrm x^\perp$ 和单位法向量表示:

对于公式(2),我们将其乘以$\mathrm w$ 加上$\omega_0$ 后有:

由于$\mathrm x^{\mathrm T}$ 是直线$\omega_0+\mathrm w^{\mathrm T}\mathrm x=0$ 上的点,由公式(3)可得:

结合图2和公式(2)和(3),我们可以表示$\mathrm x_1,\mathrm x_2$如下:

公式(5)和(6)表明:当$\mathrm x$为正例 (例如 $\mathrm x_1$) 时,$d$为正数;当$\mathrm x$为反例 (例如 $\mathrm x_2$) 时,$d$为负数。也就是说,公式(4)中的距离$d$是有方向的。具体来说,对于例子中的样例$\mathrm x_1$,是正例,即$y=+1$ ,其到直线 $\omega_0+\mathrm w^{\mathrm T}\mathrm x=0$ 的距离为$d=\frac{\mathrm w^{\mathrm T}\mathrm x_1+\omega_0}{\lvert\mathrm w\rvert}>0$; 对于例子中的样例$\mathrm x_2$,是反例,即$y=-1$ ,其到直线$\omega_0+\mathrm w^{\mathrm T}\mathrm x=0$的距离为$d=\frac{\mathrm w^{\mathrm T}\mathrm x_2+\omega_0}{\lvert\mathrm w\rvert}<0$.为此,对于任意样例$\mathrm x$ (无论正例还是反例),其距离分类超平面的无方向距离(始终大于0)为:

注意:公式(7)是公式(6)在考虑样例分类情况下,将有方向的距离$d$化为无方向距离$\lvert d\rvert$的具体表达式。


优化问题

SVM的中心思想就是找出离分类超平面最近的点(又称支持向量),然后最大化这些点与分类超平面的距离。对于一个$M$维特征空间,超平面的表达式为:

为此,我们可以得到如下的优化问题:

直接求解问题(9)比较复杂。这里我们发现,对于一个分类超平面 (例如,上面例子中的直线$\hat y=\omega_0+\mathrm w^{\mathrm T}\mathrm x=0$ ),同时对$\omega_0,\mathrm w$进行缩放并不改变该分类超平面,也就不改变任意点到该分类超平面的距离。为此我们可以将$\omega_0,\mathrm w$进行缩放,使得离分类超平面最近的点 (支持向量)满足$(\omega_0+\mathrm w^{\mathrm T}\mathrm x)y=1$。那么此时,训练集中所有其他样例点肯定满足$(\omega_0+\mathrm w^{\mathrm T}\mathrm x)y>1$。这时,优化问题(9)可以转化为SVM优化问题的标准形式:

注意:问题(9)转为标准形式(10)的主要步骤:1)令支持向量对应的$(\omega_0+\mathrm w^{\mathrm T}\mathrm x)y=1$,从而去掉最小化,并将问题(9)中的分子加入到约束中;2)最小化$\frac{1}{\lvert\mathrm w\rvert}$等效于最大化$\frac{1}{2}{\lvert\mathrm w\rvert^2}$。

从标准化的优化问题可以看出,该问题是凸二次优化问题,可以使用一些已有的工具箱求解,如CVX, Gurobi, CPLEX等。


基于CVX的问题求解

我们还是以本文开始的小例子 (Toy Example) 为例。此时,我们得到的分类超平面应该是一条直线,形式为$\omega_0+\omega_1x^{(1)}+\omega_2x^{(2)}=0$。根据SVM的标准凸优化形式(10),我们有

求解该问题,我们可以得到其最优解为$\omega_0=2,\omega_1=\omega_2=\frac{1}{2}$。此时的分离超平面为直线$\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=0$。此时的决定该直线的支持向量为使得$\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=1,-1$的样例点$\mathrm x_1(3,3)$和$\mathrm x_3(1,1)$。下图3具象地表达了这一结果:

图3

关于CVX算法实现部分,由于这台电脑没有装MATLAB,此部分回学校后再写


至此,最基本的SVM算法已经讲完了。由于上述SVM存在一些难点,下面我们对其进行扩展:

  • SVM标准形式的凸优化问题不易求解,往往我们可以通过其对偶问题求解
  • 当训练集的样例线性不可分,而通过投影到高维空间后线性可分时,我们可以在对偶问题中使用核函数
  • 当训练集及其高维映射都不可分时,我们可以考虑容许部分样例分类错误

对偶问题

为例求解上述标准形式的凸二次优化问题(10),我们除了使用工具箱直接求解外,还可以通过其对偶问题求解。一般来说,相对于求解原始问题,求解其对偶问题一般有以下好处:1)即使原始问题不是凸的,对偶函数仍是关于对偶变量的凸函数;2)具有更好的解释性,适用于分布式算法。对于SVM问题,我们发现求解其对偶问题的过程中可以使用核函数 (下一节提及),可以使用一些启发式算法 (后文提及的SMO) 来加速算法。

对约束引入拉格朗日乘子$\lambda=\{\lambda_i\ge 0\mid i=1,2,\cdots,N\}$,我们得到如下的拉格朗日函数:

此时对应的对偶问题为:

由于原始问题(10)为凸问题,那么对偶问题与原始问题的解的gap为0. 通过求解对偶问题,我们就能得到原始问题的最优解。


求解上述对偶问题 (极大极小问题) 的一般思路为,先固定$\lambda$ ,求解 $\min\nolimits_{\omega_0,\mathrm w}\quad L(\omega_0,\mathrm w\mid \lambda)$得到$\omega_0,\mathrm w$,然后一般通过梯度(或次梯度)更新$\lambda$。幸运地是,在求解 $\min\nolimits_{\omega_0,\mathrm w}\quad L(\omega_0,\mathrm w\mid \lambda)$ 时,我们可以得到其解析解 $\omega_0^\star,\mathrm w^\star$,所以我们不需要迭代,只需要直接求解$\max\nolimits_{\lambda}\quad L(\lambda\mid \omega_0^\star,\mathrm w^\star)$。具体步骤如下:

  • 求解$\min\nolimits_{\omega_0,\mathrm w}\quad L(\omega_0,\mathrm w\mid \lambda)$
    由于该问题为凸二次规划问题,其最优解为一阶微分为0的点,即:

    将公式(14)和(15)带入公式(10),我们有:

  • 求解$\max\nolimits_{\lambda}\quad L(\lambda\mid \omega_0^\star,\mathrm w^\star)$
    在求得参数$\mathrm w^\star$后,我们需要求解如下问题:

    由公式(14)和(16)可以等效成如下问题:

将问题(18)向量化可得:


最终,我们需要求解问题(19),当然由于问题(19)也是一个凸二次函数,我们同样可以利用工具箱求解,在此省略。求解问题(19)得到最优的$\lambda$后,我们将(14)带入超平面的表达式(8)中得到:

当对一个新的测试样例$\mathrm x$ 进行分类时,可以由上式可以判断:当$\hat y\ge1$ 时,判断为正例;当 $\hat y\le -1$ 时, 判断为反例。当然,上述问题在于$\omega_0$ 的值还无法得知。为此,我们可利用KKT条件(这里不具体描述,有需要会后续单独介绍)可得:

由互补松弛条件(23)可知,要么$\lambda_i=0$,要么 $y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1$。从分类超平面的表达式(20)可知,只有当$\lambda_i>0$时,才对分类结果$\hat y$ 有影响,此时的样例点$\mathrm x_i$ 才对决定了分类超平面的表达式,这样的样例点就是我们所说的支持向量。当$\lambda_i>0$时, 由(23)知$y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1=0$,也就是对应了图3所示的支持向量所在的超平面。那么这时,由$y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1=0$ 我们就有


下面我们同样通过上述的小例子来验证对偶算法的可行性:

根据对偶问题的形式(18)或(19),小例子对应的对偶问题可以写成:

为了求解问题(25),我们替换变量$\lambda_3=\lambda_1+\lambda_2$可得

令$L(\lambda_1,\lambda_2)$ 对于$\lambda_1,\lambda_2$ 的偏导为0,可知最优的解为$\lambda_1^\star=\frac{3}{2},\lambda_2^\star=-1$,不满足$\lambda_2\ge 0$。为此,最优解在边界处取得。若$\lambda_1^\star=0$,此时$\lambda_2^\star=\frac{2}{13}$,最优值为$L(\lambda_1^\star,\lambda_2^\star)=-\frac{2}{13}$。若$\lambda_2^\star=0$,此时$\lambda_1^\star=\frac{1}{4}$,最优值为$L(\lambda_1^\star,\lambda_2^\star)=-\frac{1}{4}$。所以,最终得到的最优解为$\lambda_1^\star=\frac{1}{4},\lambda_2^\star=0,\lambda_3^\star=\frac{1}{4}$。

在得到最优解$\lambda^\star=\{\lambda_1^\star,\lambda_2^\star,\lambda_3^\star\}$后,我们可以根据等式(14)求得$\omega_1=\omega_2=\frac{1}{2}$。又由于$\mathrm x_1,\mathrm x_3$为支持向量,由公式(25)我们有:

由(27)或者(28)我们可以得到$\omega_0^\star=-2$。那么我们求得的最优分类超平面为直线$\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=1$。


我们发现,最后需要求解的对偶问题为(19),也是一个凸二次优化问题。一般来说,二次优化问题的算法复杂度为$\mathcal O(K)$,其中$K$为变量的个数。在原始问题(10)中,变量为$\omega_0,\mathrm w$,个数为$M+1$;在对偶问题(19)中,变量为$\lambda$,个数为$N$。注意:这里的$M,N$分别为特征维数和样例个数。一般情况下,样例数大于特征维数,即($N>M$),此时好像更应该直接求解原始问题来降低复杂度。但是由于对偶问题的特性比较适合核函数的使用,我们更倾向于求解对偶问题。


核函数

在上述模型中,我们假设训练集是线性可分的。但一般情况下,原始的特征空间是线性不可分的,如下面的两个例子:

  • 异或问题:假设我们考虑2个特征$x^{(1)},x^{(2)}$,训练集中有两个正例 $\mathrm x_1 (0,1), \mathrm x_2 (1,0)$ 和两个反例 $\mathrm x_3 (0,0), \mathrm x_4 (1,1)$,如图4所示。显然,我们无法在该二维空间中找到一条直线将训练集正确分类。如果我们将这两个特征$x^{(1)},x^{(2)}$映射到三维空间的三个特征$z^{(1)},z^{(2)},z^{(3)}$, 且映射关系为: $z^{(1)}=x^{(1)}x^{(2)}, z^{(2)}=x^{(1)}, z^{(3)}=x^{(2)}$。那么此时训练样例坐标为:$\mathrm x_1 (0,0,1), \mathrm x_2 (0,1,0), \mathrm x_3 (0,0,0), \mathrm x_4 (1,1,1)$,如图5所示。显然,我们可以找到一个分类超平面将该训练集正确分类。

    图4
    图5
  • 圆环问题:假设我们考虑2个特征 $\mathrm x=\{x^{(1)}, x^{(2)}\}$,训练集由两个通过原点的同心圆 $\lvert \mathrm x\rvert^2=C$ 产生正例 ($C=3$) 和反例 ($C=1$),如图6所示。显然,我们无法在该二维空间中找到一条直线将训练集正确分类,此时的最佳分类超平面应该是一个圆环 $\lvert \mathrm x\rvert^2=2$ 。此时,若我们将这两个特征映射成两个新的特征 $z^{(1)},z^{(2)}$,且映射关系为 $z^{(1)}=[x^{(1)}]^2,z^{(2)}=[x^{(2)}]^2$,那么此时对应的最优分类超平面为直线$z^{(1)}+z^{(2)}=2$,如图7所示。

    图6
    图7

上面的两个例子说明,当原始的特征空间线性不可分时,我们可以将原始特征空间映射为新的特征空间,使其线性可分。这里,我们将上述的映射关系用数学表达式定义为

那么此时,经过特征映射后,优化问题(19)转化为:

为简便起见,我们定义

公式(31)就是我们提到的核函数

那么这里难点在于如何找到好的映射函数和核函数,也就是公式(31)的表达式?对于上面的例子,由于十分简单,我们可以很容易的定义映射函数。然而,对于实际中比较复杂的训练集,我们一般采用下面几种比较常见的核函数:

名称 表达式 名称 表达式
线性核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=\mathrm x_i^{\mathrm T}\mathrm x_{i^\prime}$ 高斯核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=\exp(-\frac{\lvert\mathrm x_i-\mathrm x_{i^\prime}\rvert^2}{2\sigma^2})$
多项式核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=(a\mathrm x_i^{\mathrm T}\mathrm x_{i^\prime}+b)^c$ 指数核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=\exp(-\frac{\lvert\mathrm x_i-\mathrm x_{i^\prime}\rvert}{2\sigma^2})$
Sigmoid核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=\tanh(a\mathrm x_i^{\mathrm T}\mathrm x_{i^\prime}+b)$ 拉普拉斯核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=\exp(-\frac{\lvert\mathrm x_i-\mathrm x_{i^\prime}\rvert}{\sigma})$

下面我们以一个具体的多项式核 $\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=(\mathrm x_i^{\mathrm T}\mathrm x_{i^\prime}+1)^2$ 来说明核函数的好处。这里我们考虑原始特征空间为二维,即$\mathrm x=\{x^{(1)},x^{(2)}\}$。那么此时核函数可以表示为:

从公式(31)可以看出我们把原始二维特征空间映射到了六维特征空间。最终计算$\phi(\mathrm x_i)^{\mathrm T}\phi(\mathrm x_{i^\prime})$是两个六维空间向量的内积,需要6次加法和6次乘法。然而,我们可以直接通过核函数$\mathcal k(\mathrm x_i,\mathrm x_{i^\prime})=(\mathrm x_i^{\mathrm T}\mathrm x_{i^\prime}+1)^2$ 计算$\phi(\mathrm x_i)^{\mathrm T}\phi(\mathrm x_{i^\prime})$,此时只需要进行二维空间的内积,总共需要3次加法和3次乘法。也就是说,通过核函数,我们可以直接在原始特征空间计算结果,从而避免在映射后的高维特征空间中计算内积。


线性不可分SVM

最基本的SVM模型可以对原始特征空间线性可分的训练集进行正确分类,如我们开头提到的小例子。利用核函数,我们可以对于原始特征空间,线性不可分,而在映射的特征空间线性可分的训练集进行正确分类,如图4-7提到的例子。然而我们还会遇到原始特征空间线性不可分,映射后的特征空间也线性不可分,或者说我们找不到一个好的核函数使新的特征空间线性可分的情况。下面这部分内容就是考虑线性不可分的情况。

对于线性不可分的情况,一个比较基本的方式,就是不一定需要所有的训练样例都正确分类,我们可以容忍部分样例被错误分类。如图8所示:

图8

在图8中,我们假定分类超平面和支持向量和图3一样,即分类超平面为绿色直线$\hat y=\omega_0+\mathrm w^{\mathrm T}\mathrm x=\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=0$ ,支持向量为$\mathrm x_1, \mathrm x_3$ 。样例点 $\mathrm x_6,\mathrm x_{10},\mathrm x_{11},\mathrm x_{12}$ 位于直线 $\hat y=+1,-1$ 之间,即不满足我们前面提到的正确分类需要满足(10)中的约束, 其中,样例点 $\mathrm x_6,\mathrm x_{12}$ 被错误分类。

为了解决这一问题,我们可以为每一个样例点 $\mathrm x_i$ 引入一个松弛变量 $\xi_i\ge 0$ :

根据公式(33)我们可知:

  • 位于 $\hat y=+1,-1$ 之外的样例点$\mathrm x_i,i=2,4,5,7,8,9$ 对应的松弛变量 $\xi_i=0,i=2,4,5,7,8,9$ 。
  • 位于$\hat y=+1,-1$ 之上的样例点 (支持向量) $\mathrm x_i,i=1,3$ 对应的松弛变量 $\xi_i=0,i=1,3$ 。
  • 位于$\hat y=+1,-1$ 之内的样例点$\mathrm x_i,i=6,10,11,12$ :
    • 若其能正确分类,其对应的松弛变量 $0<\xi_i<1,i=11,12$ ;
    • 若其被错误分类,其对应的松弛变量$\xi_i>1,i=6,10$ 。

此时问题(10)中的约束可变为:

由公式(34)可以看出,当样例$\mathrm x_i$ 被错误分类时,即 $(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)y_i\le 0$ ,此时对应的松弛变量为$\xi_i>1$ 。所以,松弛变量 $\xi_i$的引入是为了让所有的样例点都满足约束,使得带松弛的优化问题有解。但是,引入松弛变量容许样例点被错误分类,这并不是我们想要的结果。为此,我们需要在原问题(10)的目标(最大化间隔)基础上,考虑最小化错误分类带来的影响。这里我们一般最直观地,直接地使用 $\xi_i$作为引入松弛变量$\xi_i$ 带来的误差。因此,在原问题(10)的基础上我们有:

在优化问题(35)中,$C>0$ 是一个权重因子,用于平衡最大化间隔和最小化训练误差(即样例点被错误分类)。当 $ C \to \infty $ 时,相当于我们十分在乎训练误差,不容许训练样例被错误分类,此时所有的$\xi_i=0$。此时,问题(35)退化为问题(10)。


求解带松弛变量的优化问题

问题(35)也是一个凸二次优化问题,所以可以完全按照前面求解问题(10)的方式求解,在此我们只给出解析表达式。同样利用拉格朗日乘子法得到拉格朗日函数并对变量求偏导,令偏导为0,我们有:

在公式(38)中,$\lambda_i,\mu_i$ 分别为(35)中约束对应的拉格朗日乘子。将公式(36), (37)和 (38)带入问题 (35),我们有如下的对偶问题:

对比线性可分原问题(10)的对偶问题(19),这里的对偶问题(39)唯一的差别就是添加了约束 $\lambda_i\le C$。因此,问题(19)的解法与问题(39)的解法基本一致,并且前面所讲的核函数方法也同样适用。

求解问题(39)得到最优的$\lambda$后,我们将(36)带入超平面的表达式(8)中得到:

当对一个新的测试样例$\mathrm x$ 进行分类时,可以由上式可以判断:当$\hat y\ge0$ 时,判断为正例;当 $\hat y\le 0$ 时, 判断为反例。当然,上述问题在于$\omega_0$ 的值还无法得知。为此,我们可利用KKT条件可得:

由互补松弛条件(43)可知,要么$\lambda_i=0$,要么 $y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1+\xi_i=0$ 。从分类超平面的表达式(40)可知,只有当$\lambda_i>0$时,即$y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1+\xi_i=0$,才对分类结果$\hat y$ 有影响,此时的样例点$\mathrm x_i $ 才对决定了分类超平面的表达式,这样的样例点就是我们所说的支持向量,在图8中对应的支持向量为 $\mathrm x_i,i=1,3,6,10,11,12$ 。

当 $0< \lambda_i < C $ 时,由公式(38)知 $ \mu_i > 0 $,又由公式(44)可知,此时$\xi_i=0$,即该样例是位于 $\hat y=+1,-1$ 之上或之外的样例点。当$\lambda_i=C$ 时,有$\mu_i=0$: 此时若$\xi_i>1 $ ,该样例被错误分类,若$\xi_i\le1$,此时样例位于 $\hat y=+1,-1$ 之间,但是被正确分类的样例点. 这里的分析与我们前面对图8的解释一致。当$0<\lambda_i<C$时, 由(43)知 $y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1+\xi_i=0$ ,且$\xi_i=0$。那么这时有 $y_i(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1=0$ 我们就有


SMO算法

虽然对偶问题(19)和(39)都是凸二次函数,我们可以利用工具箱求解,在此省略。但是复杂度与样例成正比。当样例较多时,复杂度很高。为此我们介绍如何利用问题(39)的性质,使用SMO算法进行求解。SMO算法的主要思想本质上与坐标轮询法类似,即以一个变量$\lambda_i$ 为变量,其他$\lambda$ 固定来简化优化问题。也就是说,在参数$\lambda$ 初始化后,不断执行下列步骤直到收敛:

  • 按照一定规则选取需要更新的 $\lambda_i$ 和 $\lambda_{i^\prime}$
  • 固定除$\lambda_i,\lambda_{i^\prime}$的所有其他参数,求解简化后的问题(39)

从上述步骤可以看出,我们的重点在如何选择$\lambda_i,\lambda_{i^\prime}$以及如何求解问题(39)

参数$\lambda_i,\lambda_{i^\prime}$ 的选择

对于一个凸二次优化问题,满足KKT条件是最优解的充要条件。为此,我们可以找一个违背该KKT条件的样例点对应的$\lambda_i$作为需要更新的参数。对于另一个参数$\lambda_{i^\prime}$ ,我们需要选择一个离$\lambda_i$对应样例点较远的样例点,这样$\lambda_i$与$\lambda_{i^\prime}$ 之间差别较大。这时,算法每次迭代都能有效地减少目标函数值。


解析解

当选择$\lambda_i,\lambda_{i^\prime}$作为我们的优化变量,问题(39)可以简化为(为表述简单,我们假定选择的变量为$\lambda_1,\lambda_2$ ) :

对于优化问题(46),我们首先分析其约束条件。由于只有两个变量,我们可以通过图像形象地表示如下:

图9和图10分别表示当$y_1\neq y_2$ 和 $y_1=y_2$时,变量$\lambda_1,\lambda_2$的取值范围和关系。

  • 在图9中,即$y_1\neq y_2$,由问题(46)的约束我们有 $\lambda_1-\lambda_2=\eta$ 或 $-\lambda_1+\lambda_2=\eta$ ,此时$\lambda_2$的最小值$L=\max\{0,-\eta\}$,最大值为$H=\min\{C,C-\eta\}$ 。
  • 在图10中,即$y_1= y_2$,由问题(46)的约束我们有 $\lambda_1+\lambda_2=\eta$ 或 $-\lambda_1-\lambda_2=\eta$ ,此时$\lambda_2$的最小值$L=\max\{0,\eta-C\}$,最大值为$H=\min\{C,\eta\}$ 。

综合起来也就是:


将问题(46)中的约束$\lambda_1y_1+\lambda_2y_2=\eta$ 同时乘以 $y_1$,我们有

当我们不考虑问题(46)中的约束 $0\le\lambda_i\le C$,且将变量$\lambda_1$由自变量$\lambda_2$ 表示后,问题(46)可以表示为:

将问题(49)中的常数项(不含变量$\lambda_2$ 的项 ) 删除不会影响最优解,且$y_1y_1=1$,于是我们有:

问题(50)是一个无约束的凸优化问题,为此,其最优解$\lambda_2^\star$满足: 目标函数关于$\lambda_2$ 导数为0,在此省略求导过程,直接给出最优解的解析表达式:

其中,训练样例误差$E_1=\omega_0+\sum\limits_{i=1}^{N}\lambda_iy_i\sum\limits_{j=1}^{M}x_i^{(j)}x_1^{(j)}-y_1, E_2=\omega_0+\sum\limits_{i=1}^{N}\lambda_iy_i\sum\limits_{j=1}^{M}x_i^{(j)}x_2^{(j)}-y_2$ 。

注意:公式(51)表明当最优的$\lambda_2^\star $ 与当前参数$\lambda_2$ 有关。换句话说,当$\lambda_2$ 不同时,得到的最优解$\lambda_2^\star $ 。这样我们可以通过不断迭代(51)可以最终使得$\lambda_2^\star $不变,即收敛。即,在第$t$ 次迭代初,我们知道所有的参数值$\lambda$ ,然后根据(51)更新$\lambda_2$,重复该迭代过程,直至收敛。另一方面,当我们考虑(47)中$\lambda_2$ 的取值范围,我们有

在每次迭代中,得到最优$\lambda_2^\star$ , 根据问题(46)的等式约束,我们可以得到该次迭代中最优的$\lambda_1^\star$:

当在某次迭代中得到最优的解$\lambda_1^\star,\lambda_2^\star$ 后,根据公式(36)得到最优的$\mathrm w$ ,那么我们只需要更新$\omega_0$的值,从而可以确定分类超平面。我们更新$\omega_0$的宗旨就是使得$\lambda_1,\lambda_2$ 对应的KKT条件(42)满足。当$0<\lambda_i<C,i=1,2$ 时,此时 $\xi_i=0$,$(\omega_0+\mathrm w^{\mathrm T}\mathrm x_i)-1+\xi_i=0$。于是,我们有:

当$\lambda_i=0, C, i=1,2$时,此时$\omega_{0,1},\omega_{0,2}$之间的值都满足KKT条件,为简便起见,我们取两者的中间值$\omega_0=\frac{\omega_{0,1}+\omega_{0,2}}{2}$ 。


坚持原创技术分享,您的支持将鼓励我继续创作!