Categories

Calendar

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

机器学习物语(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):闲扯大数定理与学习理论

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

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

GRE 和机器学习

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

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

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