Categories

Calendar

January 2010
M T W T F S S
« Dec   Apr »
 123
45678910
11121314151617
18192021222324
25262728293031

2010 关于

去年写总结的时候用了孙燕姿的一首歌为题,今年继续吧。《关于》这首歌是这么唱的:

关于 生活的选择题
答案在风里

这一年似乎是碰到许许多多“生活的选择题”吧,所谓人生的抉择,似乎到头来还是随心就好呢!另外还有就是这个歌的前奏是闹铃声,所以一直被我用来做手机上的起床闹铃了。

年年岁岁岁岁年年,又是当你还没有习惯 2010 这样书写日期的时候,这一年就已经过去了。实际上这一年发生了很多事情。不知从何说起,但是纵观这一年,大概主要线索变成了出国的事吧,且不再论选择出国的原因了,但是既然选择了要念 PhD ,面临的许许多多的选择题,答案就变了。

GRE 和机器学习

其实是在之前复习 GRE 的时候突然想到的一些好玩的事情,只是一直没有时间写出来,今天圣诞节,决定抽空把它写了。先祝大家圣诞快乐!

但凡是考过 GRE 的同学都知道,复习过程是很痛苦的。不过现在是信息时代,找资料确实很方便,除了各种复习材料之外,网上也不乏各种复习方法总结建议之类的,其中甚至还有帮你把每天的复习细节都具体安排好了的。当然其中也有许多很好的建议和经验,但是无论如何还是自己才知道什么方法适合自己啊。所以闲暇的时候我自己也在想,这个过程究竟是怎么一回事,后来越来越觉得和机器学习其实有相当多的地方。

最典型的就是类比反义了,GRE 里的类比就是给一个词对,让你分析出这两个词之间的关系,然后类比这个关系,在 5 个选项里找出同样关系的词对;反义则要简单得多,就是给一个词,找到它的反义词。其实是很简单的问题,我曾经尝试了一下,如果看着翻译过来的中文做题的话,错误率可以很小,所以最大的瓶颈其实就在词汇量了,词汇也应该是 GRE 笔试复习过程中最大的坎。一般复习方法分为两种,一种是被红宝书,或者其他各种“宝书”,甚至还有看字典的,另外一种则是突击看诸如“猴哥类反”之类的往年题目的正确答案列表,以及最近几年的机经之类的。

巨大的 Matlab 存储数据

好吧,我的标题越来越土了,本来想取个“XX之迷”或者“走进科学”啥的,不过其实是个小问题。总之,最近我在用 matlab 跑一些实验的时候,保存的结果比较大,其实也不算太大,就几百兆,但是由于有很多个这样的文件,所以占用空间还是比较大的,而且几百兆的 .mat 文件每次 load 进来画个图之类的也要等半天,非常不方便。于是我就想能不能有方法处理一下。

一开始我以为是因为我存储的数据里有一些位图,所以才会比较大,于是我写了一个工具来将位图压缩了一下,发现单张图片即使是无损 JPEG 压缩也可以变得比原来小很多,于是赶紧用来处理原来存储的文件,结果发现处理之后基本上没有任何改观。由于很久没有遇到这么神奇的“bug”了,我比较兴奋,把代码相关的地方都检查了一遍,发现其中有一个中间计算结果作为 cache 放在一个 struct 的 field 里,而这个 cache 理论上是可以丢掉的(虽然要再算一遍很耗时,但是基本上不会再重跑这个实验了),于是我果断把它咔嚓掉。再一运行,保存……结果发现居然一丁点改观都没有!

更为诡异地是,我用 whos 看 matlab 里那个 struct 占用的空间,得到的结果其实是很小,但是当我 save 它到文件的时候,它就莫名其妙地占用了大量空间。 -.-bb 我用一个赶紧的 matlab workspace 把这个文件加载进来,逐一删掉其中的变量做测试。

其实一开始我也比较怀疑其中的一个 function_handle 的 field ,我在想不会 matlab 聪明到为了保证 function handle 下次加载进来能够运行,把所有相关的代码和引用到的代码也一应打包了吧?-.-bb 但是 Matlab 的文档说得很清楚就是在其他地方 load function handle 的时候,如果原来的代码文件不存在或者被修改过的话,就会发生 unexpected 结果。但是呢,当我删去 struct 的那个 function handle 的时候,竟然真的就瞬间从几百兆变成几兆了。

虽然是大跌眼镜,但是我突然一下子又想明白了。原来那个 function handle […]

支持向量机: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)问题。凸优化问题有许多优良的性质,例如它的极值是唯一的。不过,这里我们并没有假定需要处理的优化问题是一个凸优化问题。

悼念 Partha Niyogi

突然得到 Partha Niyogi 过世的消息,都说不好自己是什么反应了,又有些震惊吧,又有些伤心吧——虽说我们非亲非故,虽然是导师的导师,但是也从未见过面也没有过任何直接的交流——但是总还是觉得有些难过。其实今年年初听到 Sam Roweis 过世的消息(同样是英年早逝)时都还没有这样强烈的反应,但是后来屡屡在论文中看到 Roweis 的名字,想起来,也有些触动,所以大概这次才会倍感沉重吧!其实我昨天还在读 Niyogi 的一篇论文呢。 >_< 他现在才四十来岁,听说死因是 brain cancer ,我在看到相关的 blog 消息和后面许多认识他的人都说一些和他相处的经历,但是许多人似乎都不知道他原来一直在和如此严重的病魔搏斗。 其他的我也不知道说什么好了。各位各行各业的都要注意身体最要紧呀! >_<

支持向量机:Numerical Optimization

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

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

数学公式识别

在电脑上输入公式一直不是一件很愉快的事情,经历过 Word 的公式编辑器时代,还有 MathType ,只能说输入不方便而且结果非常难看。LaTeX 虽然号称是“所想即所得”,书写数学公式也相对流畅,然而有时候稍微复杂的公式写出来变成一堆结构不明显的代码,实在是比较难以继续——又不是所见即所得的,LaTeX 的错误信息又是那么让人摸不着头脑,遇到复杂的公式总是忍不住写一部分又编译一下看看是不是有问题,结果弄得很麻烦。但总归 LaTeX 渲染出来的公式目前来说还是最好看的,而且所见即所得的公司编辑确实也比较难做。Office 2007 开始有了新的公式编辑器,可以使用类似 LaTeX 的语法,渲染结果也比以前的那种要漂亮许多,不过那个所见即所得的编辑实在是非常难以驾驭,经常出现的结果是写了一大坨公式想要删掉其中的一个符号却删不掉,Office 只准你把这一整坨一起删掉,实在是很恶心,而且有时候还会有一些诡异的 bug 。就目前我尝试过的解决方案来说,我个人觉得 Emacs + CDLaTeX.el 是输入起来最迅速的,各种常用的符号、加粗斜体等操作都可以迅速完成;而最好用的是 LyX ,所见即所得的 LaTeX 公式编辑,总的编辑体验比 TeXmacs 要好。

支持向量机: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$ 维向量空间里一个点实际上是和以原点为起点,该点为终点的一个向量是等价的,所以这些“支撑”的点便叫做支持向量。