计算机视觉
图像处理

支持向量机总结(下)

五、支持向量机:Numerical Optimization

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

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

maxαs.t.,i=1nαi12i,j=1nαiαjyiyjκ(xi,xj)0αiC,i=1,,ni=1nαiyi=0

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

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

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

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

i=1nαiyi=0α2=1y2(i=3nαiyiα1y1)y2(Kα1y1)

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

0y2(Kα1y1)C

也可以得到 α1 的一个可行区间,同 [0,C] 交集即可得到最终的可行区间。这个问题可以从图中得到一个直观的感觉。原本关于 α1α2 的区间限制构成途中绿色的的方块,而另一个约束条件 y1α1+y2α2=K 实际上表示一条直线,两个集合的交集即是途中红颜色的线段,投影到 α1 轴上所对应的区间即是 α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 。如果感兴趣可以参考一下。 

 

六、支持向量机:Duality

在之前关于 support vector 的推导中,我们提到了 dual ,这里再来补充一点相关的知识。这套理论不仅适用于 SVM 的优化问题,而是对于所有带约束的优化问题都适用的,是优化理论中的一个重要部分。简单来说,对于任意一个带约束的优化都可以写成这样的形式:

mins.t.f0(x)fi(x)0,i=1,,mhi(x)=0,i=1,,p

形式统一能够简化推导过程中不必要的复杂性。其他的形式都可以归约到这样的标准形式,例如一个 maxf(x) 可以转化为 minf(x) 等。假如 f0,f1,,fm 全都是凸函数,并且 h1,,hp 全都是仿射函数(就是形如 Ax+b 的形式),那么这个问题就叫做凸优化(Convex Optimization)问题。凸优化问题有许多优良的性质,例如它的极值是唯一的。不过,这里我们并没有假定需要处理的优化问题是一个凸优化问题。

虽然约束条件能够帮助我们减小搜索空间,但是如果约束条件本身就是比较复杂的形式的话,其实是一件很让人头痛的问题,为此我们希望把带约束的优化问题转化为无约束的优化问题。为此,我们定义 Lagrangian 如下:

L(x,λ,ν)=f0(x)+i=1mλifi(x)+i=1pνihi(x)

它通过一些系数把约束条件和目标函数结合在了一起。当然 Lagrangian 本身并不好玩,现在让我们来让他针对 λν 最大化,令:

z(x)=maxλ0,νL(x,λ,ν)

这里 λ0 理解为向量 λ 的每一个元素都非负即可。这个函数 z(x) 对于满足原始问题约束条件的那些 x 来说,其值等于 f0(x) ,这很容易验证,因为满足约束条件的 x 会使得 hi(x)=0 ,因此最后一项消掉了,而 fi(x)0 ,并且我们要求了 λ0 ,因此 λifi(x)0 ,所以最大值只能在它们都取零的时候得到,这个时候就只剩下 f0(x) 了。因此,对于满足约束条件的那些 x 来说,f0(x)=z(x) 。这样一来,原始的带约束的优化问题其实等价于如下的无约束优化问题:

minxz(x)

因为如果原始问题有最优值,那么肯定是在满足约束条件的某个 x 取得,而对于所有满足约束条件的 xz(x)f0(x) 都是相等的。至于那些不满足约束条件的 x ,原始问题是无法取到的,否则极值问题无解。很容易验证对于这些不满足约束条件的 xz(x)=,这也和原始问题是一致的,因为求最小值得到无穷大可以和“无解”看作是相容的。

到这里,我们成功把带约束问题转化为了无约束问题,不过这其实只是一个形式上的重写,并没有什么本质上的改变。我们只是把原来的问题通过 Lagrangian 写作了如下形式:

minx maxλ0,νL(x,λ,ν)

这个问题(或者说原始的带约束的形式)称作 primal problem 。如果你看过之前关于 SVM 的推导,那么肯定就知道了,相对应的还有一个 dual problem ,其形式非常类似,只是把 minmax交换了一下:

maxλ0,ν minxL(x,λ,ν)

交换之后的 dual problem 和原来的 primal problem 并不相等,直观地,我们可以这样来理解:胖子中最瘦的那个都比瘦骨精中最胖的那个要胖。当然这是很不严格的说法,而且扣字眼的话可以纠缠不休,所以我们还是来看严格数学描述。和刚才的 z(x) 类似,我们也用一个记号来表示内层的这个函数,记:

g(λ,ν)=minxL(x,λ,ν)

并称 g(λ,ν) 为 Lagrange dual function (不要和 L 的 Lagrangian 混淆了)。g 有一个很好的性质就是它是 primal problem 的一个下界。换句话说,如果 primal problem 的最小值记为 p ,那么对于所有的 λ0ν ,我们有:

g(λ,ν)p

因为对于极值点(实际上包括所有满足约束条件的点)x,注意到 λ0 ,我们总是有

i=1mλifi(x)+i=1pνihi(x)0

因此

L(x,λ,ν)=f0(x)+i=1mλifi(x)+i=1pνihi(x)f0(x)

于是

g(λ,ν)=minxL(x,λ,ν)L(x,λ,ν)f0(x)=p

这样一来就确定了 g 的下界性质,于是

maxλ0,νg(λ,ν)

实际上就是最大的下界。这是很自然的,因为得到下界之后,我们自然地就希望得到最好的下界,也就是最大的那一个——因为它离我们要逼近的值最近呀。记 dual problem 的最优值为 d的话,根据上面的推导,我们就得到了如下性质:

dp

这个性质叫做 weak duality ,对于所有的优化问题都成立。其中 pd 被称作 duality gap 。需要注意的是,无论 primal problem 是什么形式,dual problem 总是一个 convex optimization 的问题——它的极值是唯一的(如果存在的话),并且有现成的软件包可以对凸优化问题进行求解(虽然求解 general 的 convex optimization 实际上是很慢并且只能求解规模较小的问题的)。这样一来,对于那些难以求解的 primal problem (比如,甚至可以是 NP 问题),我们可以通过找出它的 dual problem ,通过优化这个 dual problem 来得到原始问题的一个下界估计。或者说我们甚至都不用去优化这个 dual problem ,而是(通过某些方法,例如随机)选取一些 λ0ν ,带到 g(λ,ν) 中,这样也会得到一些下界(只不过不一定是最大的那个下界而已)。当然要选 λν 也并不是总是“随机选”那么容易,根据具体问题,有时候选出来的 λν 带入 g会得到 ,这虽然是一个完全合法的下界,然而却并没有给我们带来任何有用的信息。

故事到这里还没有结束,既然有 weak duality ,显然就会有 strong duality 。所谓 strong duality ,就是

d=p

这是一个很好的性质,strong duality 成立的情况下,我们可以通过求解 dual problem 来优化 primal problem ,在 SVM 中我们就是这样做的。当然并不是所有的问题都能满足 strong duality ,在讲 SVM 的时候我们直接假定了 strong duality 的成立,这里我们就来提一下 strong duality 成立的条件。不过,这个问题如果要讲清楚,估计写一本书都不够,应该也有不少专门做优化方面的人在研究这相关的问题吧,我没有兴趣(当然也没有精力和能力)来做一个完整的介绍,相信大家也没有兴趣来看这样的东西——否则你肯定是专门研究优化方面的问题的了,此时你肯定比我懂得更多,也就不用看我写的介绍啦。 

所以,这里我们就简要地介绍一下 Slater 条件和 KKT 条件。Slater 条件是指存在严格满足约束条件的点 x ,这里的“严格”是指 fi(x)0 中的“小于或等于号”要严格取到“小于号”,亦即,存在 x满足

fi(x)<0hi(x)=0i=1,,mi=1,,p

我们有:如果原始问题是 Convex 的并且满足 Slater 条件的话,那么 strong duality 成立。需要注意的是,这里只是指出了 strong duality 成立的一种情况,而并不是唯一情况。例如,对于某些非 convex optimization 的问题,strong duality 也成立。这里我们不妨回顾一下 SVM 的 primal problem ,那是一个 convex optimization 问题(QP 是凸优化问题的一种特殊情况),而 Slater 条件实际上在这里就等价于是存在这样的一个超平面将数据分隔开来,亦即是“数据是可分的”。当数据不可分是,strong duality 不能成立,不过,这个时候我们寻找分隔平面这个问题本身也就是没有意义的了,至于我们如何通过把数据映射到特征空间中来解决不可分的问题,这个当时已经介绍过了,这里就不多说了。

让我们回到 duality 的话题。来看看 strong duality 成立的时候的一些性质。假设 x(λ,ν) 分别是 primal problem 和 dual problem 的极值点,相应的极值为 pd ,首先 p=d ,此时我们可以得到

f0(x)=g(λ,ν)=minx(f0(x)+i=1mλifi(x)+i=1pνihi(x))f0(x)+i=1mλifi(x)+i=1pνihi(x)f0(x)

由于两头是相等的,所以这一系列的式子里的不等号全部都可以换成等号。根据第一个不等号我们可以得到 xL(x,λ,ν) 的一个极值点,由此可以知道 L(x,λ,ν)x 处的梯度应该等于 0 ,亦即:

f0(x)+i=1mλifi(x)+i=1pνihi(x)=0

此外,由第二个不等式,又显然 λifi(x) 都是非正的,因此我们可以得到

λifi(x)=0,i=1,,m

这个条件叫做 complementary slackness 。显然,如果 λi>0,那么必定有 fi(x)=0 ;反过来,如果 fi(x)<0 那么可以得到 λi=0 。这个条件正是我们在介绍支持向量的文章末尾时用来证明那些非支持向量(对应于 fi(x)<0)所对应的系数 αi (在本文里对应 λi )是为零的。 🙂 再将其他一些显而易见的条件写到一起,就是传说中的 KKT (Karush-Kuhn-Tucker) 条件:

fi(x)0,hi(x)=0,λi0,λifi(x)=0,f0(x)+mi=1λifi(x)+pi=1νihi(x)=0i=1,,mi=1,,pi=1,,mi=1,,m

任何满足 strong duality (不一定要求是通过 Slater 条件得到,也不一定要求是凸优化问题)的问题都满足 KKT 条件,换句话说,这是 strong duality 的一个必要条件。不过,当原始问题是凸优化问题的时候(当然还要求一应函数是可微的,否则 KKT 条件的最后一个式子就没有意义了),KKT 就可以升级为充要条件。换句话说,如果 primal problem 是一个凸优化问题,且存在x˜(λ˜,ν˜) 满足 KKT 条件,那么它们分别是 primal problem 和 dual problem 的极值点并且 strong duality 成立。 其证明也比较简单,首先 primal problem 是凸优化问题的话,g(λ,ν)=minxL(x,λ,ν) 的求解对每一组固定的 (λ,ν) 来说也是一个凸优化问题,由 KKT 条件的最后一个式子,知道 x˜minxL(x,λ˜,ν˜) 的极值点(如果不是凸优化问题,则不一定能推出来),亦即:

g(λ˜,ν˜)=minxL(x,λ˜,ν˜)=L(x˜,λ˜,ν˜)=f0(x˜)+i=1mλ˜ifi(x˜)+i=1pνi˜hi(x˜)=f0(x˜)

最后一个式子是根据 KKT 条件的第二和第四个条件得到。由于 gf0 的下界,这样一来,就证明了 duality gap 为零,也就是说,strong duality 成立。 到此为止,做一下总结。我们简要地介绍了 duality 的概念,基本上没有给什么具体的例子。不过由于内容比较多,为了避免文章超长,就挑了一些重点讲了一下。总的来说,一个优化问题,通过求出它的 dual problem ,在只有 weak duality 成立的情况下,我们至少可以得到原始问题的一个下界。而如果 strong duality 成立,则可以直接求解 dual problem 来解决原始问题,就如同经典的 SVM 的求解过程一样。有可能 dual problem 比 primal problem 更容易求解,或者 dual problem 有一些优良的结构(例如 SVM 中通过 dual problem 我们可以将问题表示成数据的内积形式从而使得 kernel trick 的应用成为可能)。此外,还有一些情况会同时求解 dual 和 primal problem ,比如在迭代求解的过程中,通过判断 duality gap 的大小,可以得出一个有效的迭代停止条件。

 

七、支持向量机:Kernel II

在之前我们介绍了如何用 Kernel 方法来将线性 SVM 进行推广以使其能够处理非线性的情况,那里用到的方法就是通过一个非线性映射 ϕ() 将原始数据进行映射,使得原来的非线性问题在映射之后的空间中变成线性的问题。然后我们利用核函数来简化计算,使得这样的方法在实际中变得可行。不过,从线性到非线性的推广我们并没有把 SVM 的式子从头推导一遍,而只是直接把最终得到的分类函数

f(x)=i=1nαiyixi,x+b

中的内积换成了映射后的空间中的内积,并进一步带入了核函数进行计算。如果映射过后的空间是有限维的,那么这样的做法是可行的,因为之前的推导过程会一模一样,只是特征空间的维度变化了而已,相当于做了一些预处理。但是如果映射后的空间是无限维的,还能不能这么做呢?答案当然是能,因为我们已经在这么做了嘛!  但是理由却并不是理所当然的,从有限到无限的推广许多地方都可以“直观地”类比,但是这样的直观性仍然需要严格的数学背景来支持,否则就会在一些微妙的地方出现一些奇怪的“悖论”(例如比较经典的芝诺的那些悖论)。当然这是一个很大的坑,没法填,所以这次我们只是来浮光掠影地看一看核方法背后的故事。

回忆一下原来我们做的非线性映射 ϕ ,它将原始特征空间中的数据点映射到另一个高维空间中,之前我们没有提过,其实这个高维空间在这里有一个华丽的名字——“再生核希尔伯特空间 (Reproducing Kernel Hilbert Space, RKHS)”。“再生核”就是指的我们用于计算内积的核函数,再说“再生”之前,我们先来简单地介绍一下 Hilbert Space ,它其实是欧氏空间的一个推广。首先从基本的向量空间开始,空间中的点具有加法和数乘的操作,在这个向量空间上定义一个内积操作,于是空间将升级为内积空间。根据内积可以定义一个范数:

x2=x,x

从而成为一个赋范向量空间。范数可以用于定义一个度量

d(x1,x2)=x1x2

从而成为一个度量空间。如果这样的空间在这个度量下是完备的,那么这个空间叫做 Hilbert Space 。简单地来说,Hilbert Space 就是完备的内积空间。最简单的例子就是欧氏空间 Rm ,这是一个 m 维的 Hilbert Space ,无穷维的例子比如是区间 [a,b] 上的连续函数所组成的空间,并使用如下的内积定义

f1,f2=baf1(t)f2(t)dt

我们这里的 RKHS 就是一个函数空间。实际上,在这里我们有一个很有用的性质,就是维度相同的 Hilbert Space 是互相同构的——也就是说空间的各种结构(包括内积、范数、度量和向量运算等)都可以在不同的空间之间转换的时候得到保持。有了这样的性质,就可以让我们不用去关心 RKHS 中的点到底是什么。

将映射记为 ϕ:XH ,这里 H 表示 RKHS,用 f 表示里面的元素 ;而 X 是原始特征空间,这里我们甚至不需要要求原始空间必须要是一个欧氏空间或者向量空间(这也是核方法的优点之一),用 x 表示里面的点。由于刚才说了 H 中点的本质是什么对于我们的计算不会产生影响,所以我们可以人为地认为这些点“是什么”——更确切地说,我们认为(或者说定义) H 中的点是定义在 X 上的函数,在一定的条件下(详见 N. Aronszajn, Theory of Reproducing Kernels),我们可以找到对应于这个 Hilbert Space 的一个(唯一的)再生核函数(Reproducing Kernel) K:X×XR (这里只考虑实函数),满足如下两条性质:

  1. 对于任意固定的 x0XK(x,x0) 作为 x 的函数属于我们的函数空间 H
  2. 对于任意 xXf()H ,我们有 f(x)=f(),K(,x)

其中第二条性质就叫做 reproducing property ,也是“再生核”名字的来源。至于字面上为什么这么叫,我也不清楚。也许是说元素 x 经过 kernel 映射之后,由内积一乘,又给冒出来了 -.-bb 。有了这个 kernel 之后,我们可以很自然地把映射 ϕ 定义为:

ϕ(x)=K(,x)

由核的再生性质,我们之前的用于计算 H 中内积的 kernel trick 也自然成立了:

ϕ(x1),ϕ(x2)=K(,x1),K(,x2)=K(x1,x2)

再生核有很多很好的性质,比如正定性(在线性代数里这样的性质通常称为“半正定”),也就是说对任意 x1,,xnXξ1,,ξnR ,都有

i,j=1nK(xi,xj)ξiξj0

这是很好证明的,按照核函数的再生性质写成刚才的内积形式,然后把系数拿到内积里面去,上面那个式子就等于 ni=1ξiK(,xi)2 ,根据范数的性质,也就非负了。

到这里,铺垫已经够多了,于是让我们回到 SVM ,这次我们不是直接偷工减料在最终得到的分类函数上做手脚,而是回到线性 SVM 的最初推导。当然,第一步我们要用刚才定义的映射 ϕ 将数据从原始空间 X 映射到 RKHS H 中,简单起见,我们用 fi() 来表示 K(,xi)

和以前一样,我们使用一个线性超平面来分隔两类不同的点,并且我们假设经过非线性映射到 H中之后数据已经是线性可分的了。这个线性超平面由一个线性函数来表示。这里需要再明确一下线性函数的概念,简单的说,如果 x1x2 是向量,α1α2 是标量,那么线性函数应该满足

F(α1x1+α2x2)=α1F(x1)+α2F(x2)

在这里,由于我们讨论的空间 H 中的元素本身就是函数,因此我们把 H 上的函数改称“泛函 (functional)”。根据 Riesz Representation 定理,Hilbert Space 中的任意一个线性泛函 F ,都有一个 fFH ,使得

F(f)=f,fF,fH

换句话说,线性函数可以由向量内积表示,这和我们熟知的有限维欧氏空间中是一样的。只是要表示超平面还得再加上一个截距 b

F(f)=f,g+b

这个样子的函数(泛函)严格来说称作仿射函数(泛函)。同我们在第一篇中类似,我们可以定义 margin ,得到 geometrical margin 为

γ=y(f,g+b)g

类似于原来的推导,我们最终会得到一个如下的目标函数

min12g2s.t.,yi(fi,g+b)1,i=1,,n

形式上和以前一样,只是把 xi 换成了 fiw 换成了 g ,但是现在我们要求的参数 g 是在 Hilbert Space 中,特别当 H 是无穷维的时候,是没有办法直接使用数值方法来求解的。即使可以转到dual 优化推导,但是里面涉及到对无穷维向量的求导之类的问题,我还不知道是不是能直接推广。不过幸运的是,我们在这里可以再把问题转化到有限维空间中。

这需要借助一个叫做 Representer Theorem 的定理,该定理说明,上面这个目标函数(还包括很大一类其他的目标函数)的最优解 g 可以写成如下的形式:

g=i=1naifi

换句话说,可以由这 n 个训练数据(有限集)张成。定理的证明是很简单的,记 H0{f1,,fn} 张成的子空间,其正交补记为 H0 ,则任意的 fH 都可以唯一地表示成 f=f0+f0 ,其中 f0H0f0H0 ,因此

g=g0+g0

由于 g0 垂直于 f1,,fn ,因此

fi,g=fi,g0+g0=fi,g0+0

因此,g0 部分的取值对于目标函数中的约束条件并不产生影响,可以任意定。另一方面,考虑目标函数本身,我们有

g2=g0+g02=g02+g02

最后一个等式是由于两者相互垂直而得到的(也就是勾股定理的推广啦),得到这个形式之后,再注意到我们是希望最小化 g2 ,其中 g0 是可以任意取值的,而范数 g02 又是非负的,所以在最小值的时候我们必定有 g02=0 ,从而 g0=0 ,也就证明了 gH0

这样一来,问题就从在一个无穷维的 Hilbert Space 中找一个最优的 g 转化为了在一个 n 维的欧氏空间中找一个最优的系数 a ,又回到了我们熟悉的问题,目标函数也变成了下面的样子:

12g2=12∥∥∥i=1naifi∥∥∥2=12i,j=1naiajK(xi,xj)=12aTKa

这里矩阵 (K)ij=K(xi,xj) 就是 Kernel Gram Matrix 。而约束条件也可以相应地写成

1yi(fi,g+b)=yi(fi,j=1najfj+b)=yi(aTKi+b)

这里 i=1,,n ,而 Ki 表示矩阵 K 的第 i 列。所以回到了最初的线性 SVM 的 Quadratic Programming 问题。当然,形式上有一些差别,另外,原来的线性 SVM 的问题的维度是原始数据空间 X 的维度,而这里的问题维度是等于数据点的个数 n ,这是 RKHS H 的一个子空间 H0 。此外,原来的线性 SVM 不能处理 X 中的非线性问题,但是现在经过非线性映射之后,(理想情况下)数据应该变得线性可分了。当然,即使不能完全线性可分,我们也可以使用之前说过的slack variable 的方法来放松约束。而问题的数值求解,也和以前类似,一方面可以直接使用二次优化的包求解,另一方面则可以通过 dual 优化的方式来完成——得到的结果应该跟我们之前偷懒直接在最终结果上把内积进行替换所得的结果是一样的。

最后稍微补充一下:在刚才的介绍中我们看起来好像是先确定了 RKHS 之后再找出对应的再生核的,但是在实际中,通常是先设计出一个核函数(或者说通常都是直接使用几个常见的核函数),然后对应的 RKHS 就自然地确定下来了。关于 RKHS 还有许多的内容,但是没有办法全部讲了。在传统的 Kernel 方法应用中,通常只要注意到是否可以全部表示为内积运算就可以尝试使用 kernel 方法了,许多常见的算法(例如 Least-Square Regression 、PCA 等)都是可以用核方法来扩展的,在这里 Representer Theorem 将会是重要的一环。

除此之外,进来还有不少在 RKHS 里衡量统计独立性的工作,又不是只是像传统的 kernel trick 那么简单了,说明 RKHS 还是包含了不少有趣的话题的。 

转载注明来源:CV视觉网 » 支持向量机总结(下)

分享到:更多 ()
扫描二维码,给作者 打赏
pay_weixinpay_weixin

请选择你看完该文章的感受:

0不错 0超赞 0无聊 0扯淡 0不解 0路过

评论 抢沙发

评论前必须登录!