Categories

Calendar

December 2017
M T W T F S S
« Jun    
 123
45678910
11121314151617
18192021222324
25262728293031

Multiclass Learning with ECOC

ECOC 是 Error-Correcting Output Codes 的缩写。上一篇文章中提到 ECOC 可以用来将 Multiclass Learning 问题转化为 Binary Classification 问题,本文中我们将对这个方法进行介绍。

要了解 ECOC ,可以从 One-vs-Rest 的 Multiclass Learning 策略出发。回忆一下,对于一个 K 类的分类问题,One-vs-Rest 策略为每一个类 $i$ 都训练一个 binary classifier ,用于区分“类别 $i$” 和“非类别 $i$”两类。对于这个策略,可以用下面这样一个图来表示(假设我们有四个类):

这个表中,每一行代表一个类,而每一列代表一个 binary classifier ,其中表格内的元素表示该列所对应的 binary 问题中,该行所对应的类别的数据被当作正例还是负例。例如,第一列表示该 binary classifier 是通过把第一类当作正类 (+1) ,剩余的第二、三、四类当作负类 (-1) 而训练出来的。如此类推。

现在我们将这个表格称作 ECOC codebook ,而把表格的列数称作是 ECOC 的 code length $L$ ,并且不再要求 $L$ 和类别数 […]

Google 代码之夏,Multiclass Learning

虽然各种大小事情和死线依旧是蜂拥而来,但是我想这个假期我“Officially”应该是主要在做 Google Summer of Code 。因为难得的很长的假期,以后又更少有机会回家了,所以理所当然的要呆在家里,但是为了避免一个假期过后荒废得最后连数字都不会数了,我又一直苦恼在家里应该做些什么事情——必须要是有外力来强制进度的事情,否则毫无疑问地会慢慢荒废掉,因为家里本就是一个适合休息堕落的环境呀。最后想到 GSoC 的时候突然眼睛一亮:这不就是为我这种情况量身定做的吗?!

将军 (Shogun) 是众多项目中我比较感兴趣的一个。因为肯定是希望做跟机器学习相关的项目呀,所以实际上 shogun 是项目列表里最相关的一个了。简单地来说就是用 C++ 写的一个机器学习算法库,里面实现了各种常用的算法,并且把许多著名的算法(像 LibSVM、LibLinear、Vowpal Wabbit 等)也都统一的包装起来,然后再提供了各种语言像 Matlab、Python、R 等下面的接口供方便调用。

不过虽然我以前也见到过 Shogun ,但是却并没有实际用过。以前见到这个名字的时候还以为是日本人写的库(因为 Shogun 是日语单词“将军”呀),后来了解了一下才发现实际上是有德国的 Max Planck Institute (MPI) 里的一个组发起的项目(这个 MPI 里有好多机器学习非常强的组呢!),而这个略奇怪的名字实际上是由最初的两个作者 Soeren Sonnenburg 和 Gunnar Raetsch 的名字的开头 So 和 Gun 拼起来再变化得到的。但是究竟是如何查到这个日语单词的呢?嗯,也许是 Google 了一下看到 wikipedia 的页面了吧……不过,Soeren 说你可以给 Shogun 画个好看点的 logo 的……许多年前参加 GSoC 的时候也被叫给当时的项目画了个 Logo ,不过这次就真的完全没有想法了啊,其实我觉得就这样用汉字做 logo 也挺不错的。

机器学习物语(4):PAC Learnability

这次我们要介绍的话题是 PAC Learnability ,直译过来就是 PAC 可学习性。可学习性听起来和计算理论里的可计算性是很类似的,当然其实也确实是类似的,而且这里也包含一些计算理论里的内容。对比来看,这里研究的主要是三个问题:

计算理论研究什么时候一个问题是可被计算的,而 PAC 学习理论,或者说计算学习理论 (Computational Learning Theory) 主要研究的是什么时候一个问题是可被学习的。可计算性在计算理论中已经有定义,而可学习性正是我们待会要定义的内容。
另外,计算理论中还有很大一部分精力花在研究问题是可计算的时候,其复杂度又是什么样的,因此,类似的,在计算学习理论中,也有研究可学习的问题的复杂度的内容,主要是样本复杂度 (Sample Complexity) 。
最后,在可计算的时候,得到实现计算的具体算法也是计算理论中的一个重要部分;而学习理论(或者更多的在“机器学习”这个课题下)当然也会探讨针对可学习的问题的具体的学习算法。

而 PAC 模型在这里的作用相当于提供了一套严格的形式化语言来陈述以及刻画这里所提及的 Learnability 以及 (Sample) Complexity 问题。

虽然也可以扩展用于描述回归以及多分类等问题,不过最初的 PAC 模型是针对 binary classification 问题提出来的,我们这里也采用这种模型,并且可以顺便介绍这种情况下的一些特有的概念。和以前的设定类似,我们有一个输入空间 $X$ ,也称作 Instance Space 。$X$ 上的一个概念 $c$ 是 $X$ 的一个子集,或者用之前用过的语言来说,$c$ 是从 $X$ 到 $\{0,1\}$ 的函数,显然,$c$ 可以用所有函数值等于 1 的那些点 $c^{-1}(1)$ 来刻画,那些点构成 $X$ 的一个子集,并且“子集”和“函数”在这里是一一对应的,于是我们将两个概念直接等同起来。用集合的语言来描述 binary function 的好处是可以用集合操作来对函数进行操作。比如,假设 $h$ 是另一个 $X$ […]

机器学习物语(3):回归问题

上一次讲到 Empirical Risk Minimization (ERM) 算法在有限个函数的空间里学习是可行的,然而这样的结果似乎用处不大,因为许多机器学习中用到的函数空间都是无限的。我们还提到,为了解决这个问题,需要一个“将无限化为有限”的工具。如果是对统计学习理论有一定了解的同学,可能会觉得我应该马上要讲 VC Dimension 了:如果 $\mathcal{F}$ 的 VC 维是有限的,那么即使它本身的元素个数是无限的,我们仍然可以得到合理的 bound 。任何谈到学习理论的文章不提 VC 维都会显得很过分,不过今天我们还暂时不讲这个。回到“无限到有限”的话题,我在这里也曾写过关于拓扑空间的紧性的文章,实际上,Compactness 才是我们这次要用到的工具。回忆一下,紧集的任一开覆盖存在一有限子覆盖,正是把“无限”变成了“有限”。

在进入正题之前,我们先来简单看一下机器学习中的两大问题:分类和回归。分类问题对应于离散的(有限的) $\mathcal{Y}$,例如,二分类问题中,$\mathcal{Y}=\{0,1\}$ (也有用 $\mathcal{Y}=\{-1,+1\}$ 的,不过这只是形式上的不同而已);再比如在手写数字识别(分类)问题中,$\mathcal{Y}=\{0,1,\ldots,9\}$。而回归问题则对应连续的 $\mathcal{Y}$ ,最常见的情况是 $\mathcal{Y}=\mathbb{R}$ 。分类问题关心的是类别是否匹配,代表每个类别的数字只是一个符号而已,可以换成任意其他符号,并且这些符号之间一般没有什么关系,例如,原本是数字 8 ,把它分类成 7 或者 2 都同样是错误的,并不会因为 7 (从数值上)更接近 8 就是一个更好的结果——在这种情况下,0-1 loss 是最自然的损失函数。而回归问题则不一样,比如,今天的气温是 28 度,预测为 25 度很自然地比预测为 2 度要好。说白了就是分类问题中 $\mathcal{Y}$ 是离散的,用了离散度量来衡量相似度,而回归问题中则用了 $\mathcal{R}$ 上的欧氏度量。

机器学习物语(2):大数定理军团

机器学习理论帝国崛起,大数定理军团功不可没,称之为军团毫不夸张,在前军先锋强大数定理和副将弱大数定理后面,是铠甲上刻着“Concentration of Measure”的古老印记的战士们,不妨暂且忽略他们之间乱七八糟的“血缘”关系,而罗列一些名字:Chebyshev 不等式、 Markov 不等式、 Bernstein 不等式、 Hoeffding 不等式、 McDiarmid 不等式、 Chernoff 不等式……虽然他们之间互相关系微妙,但是在战斗中却是各有千秋,特别是在装备了现代化的“大规模杀伤性武器”——

机器学习物语(1):世界观设定

我想如今机器学习 (Machine Learning) 的重要性(不论是在学术界还是在工业界)已经不用再多强调了,比如说 2010 年的图灵奖得主 Leslie Valiant 就是学习理论 (Learning Theory) 的一位先驱大牛,正是他提出了“可能近似正确” (Probably Approximately Correct, PAC) 模型——每次念一念 PAC 的中文翻译就觉得好玩,不过 PAC 模型及其变种确实是如今学习理论里最为广泛使用的框架之一,而且正是 PAC 模型催生了现在应用超级广泛的 boosting 算法。学习理论中的两大巨头: PAC 模型和 Vapnik 的 Statistical Learning Theory (SLT) ,各自都拥有一个在实际中得到广泛认可和应用的算法(boosting 和 SVM),应该也不是偶然吧! 不过这些八卦以后有机会再提吧。

另一个例子则是现在如火如荼的 Stanford 的在线机器学习课程 ml-class ,具体的注册人数是多少我现在找不到统计数字了,不过看起来 Stanford 的这次开创性的尝试确实是非常令人鼓舞的吧!如此的成功也许也是大多数人所始料未及的吧,开设的课程也从原来的机器学习、人工智能和数据库三门一下子增加了诸如自然语言处理、计算机安全、博弈论等课以及其他专业的各种课程。

回到机器学习,开设 ml-class 的 Andrew Ng 本身也是机器学习领域里的一位新星人物,和许多做纯科研的人不同的是,他的许多工作有“看得见摸得着”的很实际的东西,其中很著名的就是一个叫做 LittleDog 的机器狗,能走能跑能跳,可以应付各种复杂地形,平衡性超好,用脚踹都踹不翻;他的另一个很好玩的项目就是无人驾驶直升机(千万不要因为天上障碍物少、不会堵车,就觉得无人驾驶直升机比无人驾驶汽车要来得简单啊 ^_^),可以完成许多高难度的特技飞行动作。这些 robot/agent 相关的东西和机器学习的一大交集就是一个叫做增强学习 (Reinforcement […]

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