Categories

Calendar

January 2011
M T W T F S S
« Dec   Feb »
 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
\]

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

绘图板

作为一个 IT 人士,身边有各种数码潮人是很正常的,大家都在“败家”,什么 iphone 、ipad 、M9、Kindle、单反等等……我虽然对这些东西不抵制,但是似乎也一点提不起兴趣来。每次和大家站在一起,我就觉得自己是个摩登原始人呀!结果,那天我突然就有了这个想法,在咨询了小 lam 的意见之后,火速买了一个绘图板,快递也很迅速,第二天就到了,而且还是在早上把我从睡梦中叫醒。

Wacom Bamboo Pen Medium ,很喜欢这个名字,不知道为啥要叫 Bamboo ,听起来很可爱啊!不过在我拆开验货的时候,快递员问我这是什么玩意,我说是绘图的,他一副愤世嫉俗的表情看着我说,就一个画画的板?要那么贵?反而搞得我很不好意思,吞吞吐吐地说:“呃,这个……嗯,大致是……还有其他一些功能?”“能上网?”快递员立刻接过话去。于是我咕哝咕哝着就蒙混过关了…… =.=bb 在这种时候总是显得很无力,总不能说更贵的板子多了去了……

打开之后发现绘图板比我想象中的好用的——我原来以为是要“盲定位”的,结果发现不是这样子的,只要鼻尖不离开板子太远,就能感应到指针的移动。还有就是和鼠标的相对移动不一样的是,板子映射到屏幕是绝对位置的映射,一开始会不太习惯当鼠标来用,结果指针移来移去都还是在那里。当然我也没有指望一开始就适应,两大障碍:一是绘图板毕竟和纸不一样,要看着屏幕画,板子和电脑摆得不正的话经常会线条各种扭曲,桌子也得大,摆得下两个东西;二就是软件啦,我对图像处理的软件可以说是一窍不通…… >_< 不过反正我也没有指望能够一下子上手,这个是用板子画的第一幅图:

求最小的几个特征值

在机器学习中经常都会遇到特征值问题,例如 Laplacian Eigenmaps 或者一大堆的 KernelPCA 派的降维方法,或者谱聚类之类的。通常都是对于一个很大并且比较稀疏的矩阵,求最大或者最小的几个特征值以及对应的特征向量。在 Matlab 里,eig 函数可以用来求得一个矩阵的全部特征值和特征向量,然而,如果我们只需要其中最大或者最小的那几个,用 eig 来求就显得杀鸡用牛刀了,费力还不讨好。而且,eig 还不能处理稀疏矩阵的情况,所以,这个时候通常就需要 eigs 出场了。

eigs 可以只求矩阵的几个最小的或者最大的(或者最接近某一个数值的)特征值和对应的特征向量,并且能够处理稀疏矩阵(如果矩阵规模很大而且稀疏程度有很高的话,使用稀疏矩阵速度会快很多)。当然它使用的算法和 eig 不一样,是迭代的方式(具体的细节我也不是很清楚,记得数值分析课上讲过 power method ,不过也忘得精光了 -.-)。这也造成了一个小缺点,就是当矩阵是 singular 或者 near-singular 的时候,如果求最小的几个特征值,就会有问题。例如下面这个极端的例子,我们造一个 rank 为 1 的矩阵:

a = rand(3,1);
A = a*a';
eigs(A, 2, ‘SM’);

Matlab 就会在这里出错。让人很痛苦,因为有时候会在数据中碰到矩阵 near-singular 的情况。一开始我找不到解决办法,因为 eig 是可以处理 singular 矩阵的,所以干脆在遇到 eigs 出错的时候转由 eig 来计算,然后手工选出最小的几个特征值和特征向量。

人手移动的数据集

有一个人手移动的数据集,就是一个人坐在沙发上,身体不动,手移动到不同的方位。在不少流形学习的论文里都用到了这个数据集,基本上都是根据图像去 predict 人手的位置。最近的实验中希望用到这个数据集,其实之前不知道什么似乎下载到了那个 video 片段,但是人手位置的 label 却一直都没有,找别人要过,也没有要到,于是索性自己来标注一下。这里把标注的结果和标注用的程序都共享一下。