Categories

Calendar

July 2017
M T W T F S S
« Jun    
 12
3456789
10111213141516
17181920212223
24252627282930
31  

支持向量机:Kernel II

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

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

\[
f(x) = \sum_{i=1}^n\alpha_i y_i \langle x_i, x\rangle + b
\]

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

支持向量机:Duality

本文是“支持向量机系列”的番外篇(1),参见本系列的其他文章。

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

\[
\begin{aligned}
\min&f_0(x) \\
s.t. &f_i(x)\leq 0, \quad i=1,\ldots,m\\
&h_i(x)=0, \quad i=1,\ldots,p
\end{aligned}
\]

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

支持向量机:Numerical Optimization

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

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

支持向量机:Outliers

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

在最开始讨论支持向量机的时候,我们就假定,数据是线性可分的,亦即我们可以找到一个可行的超平面将数据完全分开。后来为了处理非线性数据,使用 Kernel 方法对原来的线性 SVM 进行了推广,使得非线性的的情况也能处理。虽然通过映射 $\phi(\cdot)$ 将原始数据映射到高维空间之后,能够线性分隔的概率大大增加,但是对于某些情况还是很难处理。例如可能并不是因为数据本身是非线性结构的,而只是因为数据有噪音。对于这种偏离正常位置很远的数据点,我们称之为 outlier ,在我们原来的 SVM 模型里,outlier 的存在有可能造成很大的影响,因为超平面本身就是只有少数几个 support vector 组成的,如果这些 support vector 里又存在 outlier 的话,其影响就很大了。例如下图:

用黑圈圈起来的那个蓝点是一个 outlier ,它偏离了自己原本所应该在的那个半空间,如果直接忽略掉它的话,原来的分隔超平面还是挺好的,但是由于这个 outlier 的出现,导致分隔超平面不得不被挤歪了,变成途中黑色虚线所示(这只是一个示意图,并没有严格计算精确坐标),同时 margin 也相应变小了。当然,更严重的情况是,如果这个 outlier 再往右上移动一些距离的话,我们将无法构造出能将数据分开的超平面来。

支持向量机: Kernel

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

前面我们介绍了线性情况下的支持向量机,它通过寻找一个线性的超平面来达到对数据进行分类的目的。不过,由于是线性方法,所以对非线性的数据就没有办法处理了。例如图中的两类数据,分别分布为两个圆圈的形状,不论是任何高级的分类器,只要它是线性的,就没法处理,SVM 也不行。因为这样的数据本身就是线性不可分的。

对于这个数据集,我可以悄悄透露一下:我生成它的时候就是用两个半径不同的圆圈加上了少量的噪音得到的,所以,一个理想的分界应该是一个“圆圈”而不是一条线(超平面)。如果用 $X_1$ 和 $X_2$ 来表示这个二维平面的两个坐标的话,我们知道一条二次曲线(圆圈是二次曲线的一种特殊情况)的方程可以写作这样的形式:

\[
a_1X_1 + a_2X_1^2 + a_3 X_2 + a_4 X_2^2 + a_5 X_1X_2 + a_6 = 0
\]

注意上面的形式,如果我们构造另外一个五维的空间,其中五个坐标的值分别为 $Z_1 = X_1$, $Z_2=X_1^2$, $Z_3=X_2$, $Z_4=X_2^2$, $Z_5=X_1X_2$,那么显然,上面的方程在新的坐标系下可以写作:

支持向量机: Support Vector

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

上一次介绍支持向量机,结果说到 Maximum Margin Classifier ,到最后都没有说“支持向量”到底是什么东西。不妨回忆一下上次最后一张图:

可以看到两个支撑着中间的 gap 的超平面,它们到中间的 separating hyper plane 的距离相等(想想看:为什么一定是相等的?),即我们所能得到的最大的 geometrical margin $\tilde{\gamma}$ 。而“支撑”这两个超平面的必定会有一些点,试想,如果某超平面没有碰到任意一个点的话,那么我就可以进一步地扩充中间的 gap ,于是这个就不是最大的 margin 了。由于在 $n$ 维向量空间里一个点实际上是和以原点为起点,该点为终点的一个向量是等价的,所以这些“支撑”的点便叫做支持向量。

支持向量机: Maximum Margin Classifier

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

支持向量机即 Support Vector Machine,简称 SVM 。我最开始听说这头机器的名号的时候,一种神秘感就油然而生,似乎把 Support 这么一个具体的动作和 Vector 这么一个抽象的概念拼到一起,然后再做成一个 Machine ,一听就很玄了!

不过后来我才知道,原来 SVM 它并不是一头机器,而是一种算法,或者,确切地说,是一类算法,当然,这样抠字眼的话就没完没了了,比如,我说 SVM 实际上是一个分类器 (Classifier) ,但是其实也是有用 SVM 来做回归 (Regression) 的。所以,这种字眼就先不管了,还是从分类器说起吧。

SVM 一直被认为是效果最好的现成可用的分类算法之一(其实有很多人都相信,“之一”是可以去掉的)。这里“现成可用”其实是很重要的,因为一直以来学术界和工业界甚至只是学术界里做理论的和做应用的之间,都有一种“鸿沟”,有些很 fancy 或者很复杂的算法,在抽象出来的模型里很完美,然而在实际问题上却显得很脆弱,效果很差甚至完全 fail 。而 SVM 则正好是一个特例——在两边都混得开。