Categories

Calendar

May 2017
M T W T F S S
« Jun    
1234567
891011121314
15161718192021
22232425262728
293031  

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 […]

概率与测度 (2):积分与期望

本文属于概率与测度系列。

上一次我们谈到零测集的概念。之所以提出来,一方面是因为它比较好玩,另一方面是它和另一个重要概念息息相关。这个东西就是“几乎处处 (Almost everywhere)”,经常被缩写为“a.e.”。例如,“函数 $f$ 几乎处处等于零”——当我第一次看到这个样子的话的时候,就被深深地雷到了。 =.=bb 当然,我是后来才知道,这个东西是有严格定义的。把一个听起来就模棱两可的词强行加上一个严格的定义,然后直接拿来用,果然搞数学的人好洒脱!

回到 a.e. ,它的定义其实很简单,我们说某个性质“几乎处处”成立,严格地来说,就是在讲它除了在一个零测集上不成立之外,在其他地方都成立。例如,传说中的 Dirichlet function $\chi_\mathbb{Q}$,它在有理数上取值为 1 ,在无理数上取值为 0 (题外话:这个玩意它还是一个处处不连续的函数)。注意到 $\mathbb{Q}$ 的 (Lebesgue) 测度为零的,因此 $\chi_\mathbb{Q}$ 除了在一个零测集上之外,其他地方都取值为零,那么我们就说它“几乎处处为零”。

和这个对应的概率论里常用的还有一个看起来更雷人的概念,叫做 almost surely (或者叫做 almost certain 、almost always) ,说某件事情 almost surely 成立,就是说这件事情在一个“满测度”集合上成立。所谓“满测度”集就是说它的补集的测度为零,而并不一定要求补集是空集。不过零测集和空集之间的关系,如果不严加定义的话,仅用文字描述起来很难搅清楚,而用上了 almost surely 这样的看起来很模糊的词,就更加雪上加霜了。也许,都是那些数学工作者的错——选了一些表面上看起来很混淆的用词,结果导致一些人在并不知道真正严格含义的情况下纠缠在字面上的意思,最终沦落为民科啊……

当然,抛开用词不说,a.e. 的引入在实分析中是必要的——而并不只是简单的把原来的一些“处处成立”的定理推广为“几乎处处成立”这样一个看上去无关痛痒的扩展。可以想像一下,应该是某个定理在条件中不是 a.e. ,但是结论只能得到 a.e. ,所以说如果去掉 a.e. 这个概念的话,整条路就走不通了。不过,这里暂时还没法详细说这个问题。于是下面以一幅 6 格漫画结束开场白,正式进入这次的主题——“积分”吧!

支持向量机:Kernel II

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

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

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

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

GRE 和机器学习

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

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

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

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