Categories

Calendar

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

留学申请注意事项:心路历程

在这里记录一下自己申请过程中的一些重要的事吧。也算是自己人生的一个巨大的转折点。因为我之前一直是走工程路线的,特别是在本科阶段,一方面是对科研学术方面的东西接触得不多,另一方面是完全没有考虑过出国留学这一条路——或者说其实是考虑了但是立马被我自己彻底否决了:大概很大的原因是因为自己不愿意花时间去弄英语考试这种“没用”的东西以及认定自己肯定搞不定申请过程中的种种复杂繁琐的流程吧。

实际上要说自己当时对未来的规划的话,那就是没有规划。本来嘛我就并不是一个有远大志向要做出什么惊天动地的伟业的人,只是喜欢开开心心地活着做自己喜欢做的事情而已,而且长期浸泡在校园这样轻松自由的环境里(不知道会不会有人冒出来吐槽说“学校哪点轻松哪点自由了?”,反正我是这样觉得的),也让我对校园外的生活的辛苦和残酷变得越来越没有概念,于是就只是沿着眼前的路往前走而已。所以读研其实也是因为基本上没有什么悬念地保研了嘛,而且那阵子也凑热闹随便跑去参加了某公司的一个校园招聘,在几乎没有做过什么准备,就想去打一下酱油熟悉一下流程为将来找工作做准备的情况下,居然从笔试一直到三轮面试最后人家说如果我愿意放弃保研的话是会给我 offer 的。当然保研的协议早已经签了的,但是这件事无疑更加让我对将来的生活或者生计放松了警惕。

所以如果没有认识你的话,我的人生大概就不会在这个时候又变得这样闹腾起来了吧。真正认真开始考虑出国的可能性是在研一下的时候吧,因为看到你那么坚定地朝着自己认定的目标走,让我很感动,也为自己的散漫和悠闲有些惭愧。所以也许我也想尝试去体验一下你的那份坚毅吧;或者也许我只是想追随你而已——至少我在找导师咨询关于出国的事情的时候是这么说的。

» Continue reading 留学申请注意事项:心路历程

2011 当冬夜渐暖

按照惯例每年的总结还是用孙燕姿的一首歌作为标题吧,2011 年的总结写得有点太晚了,既然已经不再是寒冬了,那就用这首新歌《当冬夜渐暖》吧!


当冬夜渐暖 当大海也不再那么蓝
当月色的纯白变得阴暗
那只是代表快乐不再那么简单

当冬夜渐暖 当夏夜的树上不再有蝉
当回忆老去的痕迹斑斑
那只是因为悲伤从来 都不会有答案

当冬夜渐暖 当青春也都烟消云散
当美丽的故事都有遗憾
那只是习惯把爱当作喜欢
重要的是 我们如何 爱过那一段

要给个简洁的总结的话,2011 年大概至少有一半的时间都在忙申请吧,总结拖到这么晚才写也是因为申请的事情告一段落之前,总是仿佛走钢丝走到一半无心去做其他事情的。现在这些事情大致告一段落了,也就可以好好回忆一下过去的这一年了吧。

» Continue reading 2011 当冬夜渐暖

The cost of knowledge: JMLR 的 8g

这一阵子数学家们发起了一场抵制 Elsevier 的运动,建立了一个网站叫做 the cost of knowledge。简而言之,Elsevier 是一个出版商,它旗下有很多期刊,但是在众多恶劣的出版商之中,Elsevier 似乎尤其恶劣,价格高昂,并且搞捆绑销售捆绑一些非常低质量的期刊,而且还被爆参与一些非正当的学术行为,另外还和前一阵子引起很大风波的让 Wikipedia 下线一天的 SOPA 有关。期刊本来的主要作用是传播学术成果,学术论文发表是没有稿费的,并且论文评审和编辑工作完全是有这些科研工作者“志愿”完成的,出版商也不会支付任何费用,他们的收入则主要来源于将期刊集出售给各大学的图书馆之类的机构。而现在呢,随着 Internet 的发展,期刊的主要作用“传播”似乎越发显得不重要了,然而许多出版商却变本加厉,订阅价格越来越贵,许多学校都越来越难以负担,于是几乎是历史必然地,出现了抵制运动,这次首先针对的是据说行为非常恶劣的 Elsevier ,具体可以参见这次运动的 Statement of Purpose,来龙去脉讲得非常清楚。此运动发起之后,各个领域的人也都参与进来,表示支持,抵制的方式就是可以选择 (1) 不投稿;(2) 不引用;(3) 不参与编辑工作。在他们的网站上可以看到已经有各行各业的的公开支持了。

总而言之这是一场非常振奋人心的运动,相信此后科学出版或者说学术界又会有一些好的变化吧。不过这次要 8g 的主角实际上是 Journal of Machine Learning Research (JMLR) ,那已经是十几年前的老故事了。

» Continue reading The cost of knowledge: JMLR 的 8g

时间估计的难题

喜欢看书的同学,放假回家的时候都会带几本书呢?然后开学回学校的时候发现真正打开看了的又有多少本呢?反正我从前回家带的书总是看不完的,不止回家,甚至是去自习室或者图书馆,带的书也总是会超过我的处理能力——而且我还没次都是仔细计划过的。当然造成这样的原因有多方面的,比如多带几本书的话,在一本书看不下去的时候可以换一本;又比如也许是因为执行力不够没有能把计划实施(比如中途开小差去了什么的)。但是似乎有一个重要的原因在生活中其他地方也非常常见——就是我们对于时间或精力的估计上,似乎经常存在相当大的误差。

我想来想去,觉得大部分人进行估计的时候,由于无法预料和处理所有的细节,因此会将注意力集中在几个重要的因素上,然后忽略剩下的那些琐碎的细节。这是非常自然的方法,然而问题出在哪里呢?考虑哪些琐碎细节所占的时间,虽然它们单独都小到可以忽略的情况,但是各种各样的小细节加在一起如果总时间非常多呢?是不是就不成了?

比如,要写一个程序,主要的部分当然是在写代码部分喽,但是琐碎的部分呢?比如配置一下工程环境啊,做个 Makefile/automake/CMake 之类的啊,为编辑器选一个新的字体和配色方案来换一下心情啊,找个工具来高亮和清晰化编译器的编译错误啊,更新某个库到最新版本并解决一下相关的依赖关系带来的麻烦呀,去 reddit/twitter 之类的地方看看呀,去找一个“最适合 coding 的时候听的音乐专辑”之类的,等等等等。似乎根本就列不完,也没有办法事先想到所有的事,但是这些乱七八糟的事情加在一起就会悄悄地占去了想到“可观”的一大段时间,以至于最后计划中的任务可能只完成了一半。

» Continue reading 时间估计的难题

机器学习物语(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$ 上的 binary function ,假设我们试图用 $h$ 去逼近 $c$,我们选择 $X$ 上的一个概率分布 $\mu$ ,则根据以往关于误差(或者风险)的定义,我们有 $\mathcal{E}(h) = \mu(h(X)\neq c(X))$ ,而这个量可以很容易并且很直观第用集合的对称差来表示:

\[
\mathcal{E}(h) = \mu(h\Delta c)
\]

如图所示,误差在这里就很直观地用两个集合的对称差(也就是黄色的部分)的面积(用测度 $\mu$ 衡量)了:

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

机器学习物语(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}$ 上的欧氏度量。

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

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

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

总而言之,我们这次的主角是大数定理 (Law of Large Numbers, LLN),以及它们在学习理论中如何起到关键作用。不妨先来看看大数定理吧:

定理 1:设 $X_1,\ldots,X_n$ 是独立同分布的随机变量,并且 $\mathbb{E}|X_i|< \infty$ ,记 $\mu=\mathbb{E}X_i$ ,$\mu_n = \sum_{i=1}^nX_i/n$ ,则随着 $n\rightarrow\infty$
  1. 强大数定理:$\mu_n$ 几乎处处(逐点)收敛于 $\mu$ ,亦即

    \[
    P(\lim_{n\rightarrow\infty}\mu_n = \mu) = 1
    \]

  2. 弱大数定理:$\mu_n$ 依概率收敛于 $\mu$ ,亦即 $\forall \epsilon>0$

    \[
    \lim_{n\rightarrow\infty}P(|\mu_n-\mu|\geq\epsilon)=0
    \]

直观来说,就是随着 $n$ 增大,由采用数据估计出来的平均值 $\mu_n$ 会越来越接近真实平均值 $\mu$ 。强大数定理可以(用 Egorov 定理)推出弱大数定理。这在机器学习里有什么用呢?上一次我们已经稍微做了一点剧透,这一次让我们来仔细研究一下这个问题,一切还得从 Empirical Risk Minimization (ERM) 说起。

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

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

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

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

回到机器学习,开设 ml-class 的 Andrew Ng 本身也是机器学习领域里的一位新星人物,和许多做纯科研的人不同的是,他的许多工作有“看得见摸得着”的很实际的东西,其中很著名的就是一个叫做 LittleDog 的机器狗,能走能跑能跳,可以应付各种复杂地形,平衡性超好,用脚踹都踹不翻;他的另一个很好玩的项目就是无人驾驶直升机(千万不要因为天上障碍物少、不会堵车,就觉得无人驾驶直升机比无人驾驶汽车要来得简单啊 ^_^),可以完成许多高难度的特技飞行动作。这些 robot/agent 相关的东西和机器学习的一大交集就是一个叫做增强学习 (Reinforcement Learning, RL) 的模型,实际上这已经是一个相当“古老”的 topic 了,理论和算法上都已经有相当的成果,不过传统的 RL 算法通常都有相当 aggressive 的“探索”环境的过程,而这在像机器人控制,特别是直升机控制方面有可能是不太现实的,极端的情况下某个高难度的“探索性”步骤有可能会使直升机 crash 掉。为了解决这个问题,Andrew Ng 提出了所谓的学徒学习 (Apprenticeship learning),通过人类示范的方法来引导机器进行学习。当然这里牵涉到的不仅仅是“模仿”而已,从理论上可以证明,学徒可以学得和老师差不多的 performance ,当老师的示范带有“启发性”的信息的时候,学徒甚至可以超过老师。因为这次并不是专门要讲学徒学习或者增强学习,所以我不得不用非常模糊的词语(“差不多”、“启发性”之类的)糊弄过去,然而实际上模型和各种性能保证都是有严格的数学描述的,如果感兴趣的话,可以去看 Ng 的论文(至少需要先了解一些 Markov Decision Process 的基础知识) 。当然,除了理论保证之外,学徒学习还被成功地应用到了无人驾驶直升机的控制上。无论如何,像这种从实际问题出发,理论结合实践的研究方式,真的是非常令人振奋的啊! :D

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

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

本文属于概率与测度系列

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

» Continue reading 概率与测度 (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 个元素,要计算 A 的点数大于 B 的点数这个事件中基本事件的个数,只要暴力数一遍就好了(当然有更好的办法,例如先去掉相等的点数,然后利用对称性,但是这种具体的细节不是我们这里要关注的东西)。

» Continue reading 概率与测度 (3):概率模型