Categories

Calendar

January 2011
M T W T F S S
« Dec   Feb »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

机器学习物语(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 […]

概率与测度 (4):闲扯大数定理与学习理论

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

在本系列的上一篇文章中,我偷偷留了一个问题:为什么具体试验所得到的频率是趋向于该事件的概率的。这个问题似乎是显而易见的,但是仔细想想似乎也并不显然,并不能一下子得出这个结论来。事实上,历史上有以这个性质作为基础来构建概率论的理论体系的尝试,不过在现在的概率论公理化体系下面,这个可以作为一个结论推导出来,具体来说,它是大数定理的一个特殊情况。不过如本文标题所说,这次只是闲扯,因为我们目前的进度还没有到大数定理那里,所以就不仔细介绍众多形式的大数定理了,下面只给一个常见的形式,并且暂时省略证明:

概率与测度 (3):概率模型

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

系列的前面两篇大致陈述了一下测度论方面的基础,由于这个学期有去旁听《概率论》这门课,所以主要还是按照课程进度来吧,不定期地把课程里一些有意思的内容抽取出来整理在这里。这次就说概率模型。

先从一个例子开始,比如一个盒子里放了 8 个黑球和 2 个白球,从盒子里随机拿一个球,问它是白球的概率是多少,大家都会不假思索地说,1/5 。的确,这似乎是很显然的,不过,实际上我们是用了一个模型来进行概率分析,但是由于这个情况实在太简单了,我们根本就没有注意到模型的存在性,但是换一个稍微简单的例子,要忽略模型“走捷径”有时候就会一下子想不清楚了。比如两个人各掷一个骰子,问 A 得到的点数比 B 大的概率。这个问题就比刚才那个问题要困难一些了。

最早人们在对这类概率问题进行数学抽象的时候,归纳出来的一种模型,现正称为古典概率模型。该模型包由一个包含有限个(设为 $N$)元素的样本空间 $\Omega$ 组成,$\Omega$ 中的每一个元素称为一个基本事件,$\Omega$ 的任意一个子集是一个事件。所有基本事件的概率是相等的,即 $1/N$ ,而任意事件的概率即为该集合的元素个数乘以 $1/N$ ,换句话说:

\[
P(A) = \frac{|A|}{N}
\]

也就是该事件集合的元素个数除以样本空间的总元素个数。对于第一个例子,我们可以这样建立模型:对每一个球编号,一共 1 到 10 号,设 8 号和 9 号是白球,其他的都是黑球,样本空间 $\Omega$ 为 {抽到的是 1 号球、抽到的是 2 号球、……、抽到的是 10 号球} ,而“抽到白球”这个事件集合即 {抽到的是 9 号球、抽到的是 10 号球} ,简单计算立即得到 1/5 的概率。

对于第二个问题,我们用一个 tuple $(x,y)$ 来记两次掷骰子的结果,则整个样本空间集合为 {$(x,y)$, $x=1,\ldots,6$, $y=1,\ldots,6$} 一共 36 […]

同义反复

忘记了之前在哪里看到说数学其实就是同义反复而已。从某种程度上来说,这样的言论也不能说完全是乱说,比如一系列的等价的推导,其实可以说就是在说同一件事情。但是“同义反复”多少有些贬义的意思,具体来说应该是指“不必要的反复”吧,但是数学应该不是这样吧。实际上,来考虑一下什么样的“反复”是“不必要的反复”就可以了,我觉得,那些只要是“不太明显” (non-obvious) 的关系,把这样的关系建立起来,应该也都是有其意义的,而尤其重要的是其中那些“深刻”的关联。

不过“深刻”这样的词是不是太抽象了呢?实际上,最近一年一来,接触了些数学专业的人,在同他们讨论问题的时候——好吧,其实大部分时候是我在听他们讲问题的时候——“深刻”这个词便时常在我脑子里出现。有时候听到他们说一些东西,会觉得很震惊,惊讶“原来如此”,惊讶自己从前的理解是如此的“肤浅”和不得要领。然而我一直想要来描述“深刻”这个词,却一直没有想法。也许应该举一个例子,不过有许多例子一时也想不起来了,也许有很多比较合适的经典的例子,比如 5 次以上方程不可用根式解之于 Galois Theory 的联系,我却又没法讲出来。

实际上大致就是那种感觉,不仅仅存在于数学,也存在于任何学科任何领域。从某一方面来说,世间的万事万物,作为一个个的独立的存在的话,并不是什么重要的存在,反而是它们之间的相互关联更加重要一些。所以,如果看到一个现象,得到的只是一些很明显的联系的话(也就是所谓的 obvious 的东西),也就是所谓肤浅了,这样用处大概并不大;但是如果是能抓住更深层次的东西(也就是 non-obvious 的东西),往往就能把问题看得更透彻——这样的带来的优势是可以比较形象地比喻的。比如说,各大洲上的生物有一些具有非常高的相似性,如果能顺着这个线索最终追查出原来曾经几块大陆是连在一起的,那么不仅为什么相差十万八千里的生物具有很高的相似性的问题变得豁然开朗,而且可以由此得到更多的结论来。

深刻,也就是抓住本质的东西,就好比照妖镜照出妖怪的本来面目。唐僧看不见妖怪的原形,所以妖怪用一些“烟雾弹”轻易就让唐僧上当受骗了;但是孙悟空有火眼金睛,却能看透妖怪的本质。这似乎让看透本质这样的能力越来越虚幻起来。但是神话毕竟只是神话,现实中没有人能有火眼金睛,但是看问题看得深刻——或者说,看到本质的东西,这样的能力却并不是遥不可及的。

久别重逢的 std::bad_alloc

久别重逢是说,自从在教科书上见过它一面之后,这才是第二次碰面。也就是说,在这些年的编程经历中,从来没有遇到过吧——至少在我印象中是这样的。以至于我都开始怀疑在“平常的”程序中,它是否真正存在了。内存分配,C 里的 malloc (或者配套的函数) ,如果分配失败了会返回地址 0 ,所以,“作为良好的编程习惯,每次申请内存之后,应该检查一下返回值是不是 NULL ”,这样的“良好习惯”也许刚开始写几个程序的时候还能坚持,到后来就完全不管了——因为从来没有遇到过 malloc 返回 0 的情况,申请内存怎么会失败呢?如果连内存都申请失败了,那接下去估计也没有什么好做的了,估计系统已经处于崩溃边缘了,与其每次都费力去检查,还不如让它自生自灭好了——反正之后如果尝试去访问这个 0 地址,肯定会碰到段错误 (segment fault) 而挂掉的,当然,一个不好的地方可能就是这个挂掉的位置和最初申请内存失败的位置已经相差了十万八千里,可能追踪起来会比较麻烦。

至于 C++ 里,就更简单了,new 的时候如果申请不到那么多内存的话,会抛出 std::bad_alloc 异常,如果没把这个异常接住,让它一直跳到最顶层的话,程序会立即挂掉。比 C 更加“人性化”——当场挂掉,而不是在某个未知的其他地方 segment fault 。如此一来,就更加熟视无睹了。

总而言之,渐渐地有了这样一种印象:像内存申请失败之类的情况,大概只有在嵌入式设备等非常极端的资源匮乏的平台上编程的时候才会碰到吧。结果这次却在一个内存很大很大(256G 物理内存)的环境里遇到了。果然是和车祸之类的类似,越是在看上去很太平的路段,越会让驾驶员掉以轻心呀。

拓扑空间的紧性

Klein Bottle

参加暑期讨论班其中有一场是我讲,第一次这样子讲数学的东西,有点紧张,于是先在这里整理一下。内容大致是拓扑空间的紧性。

关于空间的紧性,我们在之前的分析中已经见过了:例如在实数轴上的有界闭区间就是典型的紧集,紧集具有很多优良的性质,比如我们知道在有界闭区间上的连续函数一定是一致连续的,并且能取到最大值和最小值。所以,在将空间的概念推广到一般的拓扑空间之后,我们也希望将紧性这一优良性质也带到拓扑空间中来。为此,我们需要找到什么是紧集最本质的东西。在实数轴上的紧集 $K$,有如下的一些等价刻画:

$K$ 是有界闭集
$K$ 的任意无限子集必存在极限点
$K$ 中的任意序列必有收敛子列
$K$ 的任意开覆盖必有有限子覆盖

其中第一条无法在拓扑空间中使用,因为“有界”的概念无法定义。第二或者第三条曾经被认为是实质性的,但是后来由于 Tychonoff 定理,人们发现最后一条才是真正好的定义,因此将其作为拓扑空间紧性的定义,而第二条和第三条分别被叫做“极限点紧(Limit point compact)”和“序列紧(Sequencially compact)”。下面是正式内容,在给出定义之前,我先给出一个提纲:

首先当然是要给出拓扑空间紧性的定义。
接下来当然是会举一些例子,一方面是把枯燥的定义从抽象中拉回来,另一方面也是非常重要的是给出紧空间的存在性的证据,因为定义总是可以随便给的,这样子我可以给出具有任意优良性质的定义来,然而所定义的东西如果是不存在的话,相关的一切性质其实都是空谈。
然后我们将介绍从已有的紧空间构造新的紧空间的方法:包括集合的交、并、补,以及子空间、商空间和积空间——这一系列都是标准套路。在这里将会出现一个大定理,就是刚才提到的 Tychonoff 定理。
接下来将暂时中断一下,讨论一下稍微具体一点的度量空间中的紧性。因为度量空间更加具体一些,所以能得到的性质也更丰富一些。
最后我们将简要介绍一些将非紧空间(non-compact space)转化为紧空间(compactification,紧化)的初步知识。

啊,不过,由于一次报告是两个人一起讲的,这次我大致负责前半部分,因此从度量空间的紧性开始那部分内容就不列在这里了。

MSTC 月刊第三期(十周年特辑)

MSTC 月刊第三期,距离第一期创刊号发布已经快要有两年了,所以说叫“月”刊当然不太合适,当然现在就不去纠结这些细节问题了。这次是第三期,也是特别的一期,因为今年是俱乐部成立十周年,所以是十周年特辑。比较遗憾的是没有能在十周年 party 之前弄完,不过现在既然终于要正式出炉了,那么这些话也不多说了吧,制作过程当然是很辛苦和漫长,当然最需要感谢的是各位供稿人,没有你们提供的内容,月刊是绝对做不出来的啦。

先提供下载吧,顺便附上前两期下载以供怀旧之用(校内下载是 FTP 地址,由于历史原因路径中有中文,如果浏览器无法正确处理,请用 FTP 软件下载):

MSTC 月刊 TechCool Issue 3 (十周年特辑),屏幕阅读预览版(JPEG 普通压缩 dpi 72,对页合并,9.12 MB):校外下载|校内下载
MSTC 月刊 TechCool Issue 3 (十周年特辑),屏幕阅读珍藏版(JPEG 高质量压缩 dpi 144,对页合并,24.5 MB):校外下载|校内下载
MSTC 月刊 TechCool Issue 3 (十周年特辑),可打印版(对页拆分,A4 纸张,103 MB):校外下载|校内下载
MSTC 月刊 TechCool Issue 2:校外下载|校内下载
MSTC 月刊 TechCool Issue 1 (创刊号):校外下载|校内下载

我作为这次月刊的重大苦力,迫不及待地想要提一下这次月刊相对于之前版本的特点:首先是风格比较统一,因为整个排版是由我一个人完成的,首次尝试了采用 Adobe InDesign 来排版——果然是专业的排版软件,比 Word 弄出来的东西看起来更加正规了。一开始就希望做成杂志的样子,就按照双页对开为整个一个版面的方式来排版了,加入了大量的图片元素,所以页数(和文件大小)也比以前的两期增加了许多。除了少数照片是在网上找的之外,大部分图片都是出自俱乐部的照片,此外我还动手为其中一些内容画了插图,虽然有些一下子就看出了功力不足或者偷懒嫌疑,但是也有碰巧自己觉得感觉还不错的——比如游记中的水墨风格的那张。

当然除了排版工作之外,还有众多其他苦力,大家都非常辛苦才有这样的成果啊。而且我很期待这次的版本实际打印出来的效果,俱乐部稍大量打印的可能性团长还在评估中,不过我想回头我自己应该会去印一份的。 总之就是这样啦,要给好评哦亲!给差评我会删帖的哦亲!