Just another WordPress.com site

最新版本

DDP的背后

这次在NIPS 2010上发表的关于构造Dependent Dirichlet Processes (DDP)的paper在NIPS的官网已经可以下载了。

在这里只是想分享这篇文章背后的研究经历。

认识我的朋友们应该知道,我从本科开始直到现在,主要研究方向一直都是computer vision。但是,在硕士阶段和在博士阶段的研究目标却有着很大的不同,这和导师的风格有着很重要的关系。

在香港读硕士期间,我的导师汤老师是一个非常注重实际应用的人,因此当时做research的主要目标是提高实际性能或者建立新的应用。在方法上,更多地是借用现有的方法,或者略加改进。

到了MIT之后,我的导师Eric Grimson让我在John Fisher的指导下进行研究。John和LIDS的主任Alan Willsky关系很密切,因此我每周都要参加Alan的一个grouplet,并且有幸和Alan讨论学术问题。

Alan Willsky是我非常敬佩的一位教授,他有着很深的数学造诣。在每次grouplet的时候,他都听我们给他讲新的进展,而他则为下一步的研究提供方向性的意见。和汤老师的风格不一样,Alan是一位很典型的理论型的科学家。每次讨论时,他关注的重点不是实验结果,而是理论价值,比如某一个方法是不是能给这个field带来新的insight。在他前几年指导的工作里面,这一点得到了充分的体现,比如Tree reweighted approximation和Walk-sum analysis of Gaussian LBP都是probabilistic inference的重要进展,并且展现了对相关领域的深入而独到的理解。

在他的引导下,我在研究过程中更多地思考一个工作背后的理论基础。在这个过程中,我始终感到在本科和HK时期打下的数学基础并不足以支持在理论方面的深入探索,于是开始系统地学习和我的研究课题有关的数学。和运动分析有关的部分主要是Differential geometry和Lie algebra,和统计模型有关的是Measure theory,Modern probability theory,Stochastic processes和Convex analysis。以及这些学科所共同涉及的General topology和Functional analysis。

MIT要求每个PhD修一门minor,我当时从我的需要出发选择了数学(Course 18)。在这个过程中得到了进行严格数学推导和证明的训练。进行严格的数学分析和推演的能力也许在Computer Vision的大部分工作中并不是特别需要,但是在做NIPS这个工作的时候它的效用就显现出来了。理论上的东西,你要说服别人它是对的,必须给出严格的证明,而不仅仅是实验结果。

回到这篇NIPS paper吧。最初,我们是希望得到一种能随着时间变化的mixture model。在这个过程中,可能回增减其中的component。如果回到硕士的时代,也许,我们会通过工程的方法来解决这个问题——事实上很多现有的工作就是通过工程方法或者算法层面的设计来达到这个目标的。但是,基于我们组的风格,我们并不能满足这样的方法,而是希望每个方法都有一套严格的数学理论去支持。

在mixture演化的过程中component的个数会发生变化,因此Dirichlet Process也就成了很自然的一种选择。一开始的时候,我们也只是希望对原有的基于Polya Urn或者Stick breaking的方法加以改进来满足我们的需求,但是发现这其中在数学上存在很多困难,于是,我们开始尝试另起炉灶,从根源重新理解DP。

在我早前做关于大批运动物体的motion analysis的topic的时候,曾经读过一些关于Random Point processes的书,其中包括Kingman的Poisson processes。这本书中提到了(Spatial) Poisson process的很多很漂亮的数学性质,以及它和Gamma/Dirichlet Process的内在关系。最初读这本书的时候,只是惊叹于Poisson process的数学美,而并没有意识到它的实际价值。当我再次阅读这部书的时候,才形成了是否可以利用Poisson和Dirichlet的关系来建立我们的dynamic mixture model framework的想法。这种想法就是这篇NIPS的源头,paper中的section 2关于数学background的部分就是来自于这本书。

在我早前的blog中曾经论及空间泊松过程和随机测度,其实已经是在一定程度上介绍这篇paper的理论背景。只是当时paper还没有发表,并不便于讲得很深入。

除了Alan的影响,我也感谢John和Eric为我创造的研究环境。一直以来,对于在理论方面的探索,他们都是非常鼓励的,认为这样的探索非常有价值。虽然,我们的funding也需要一些项目来支持,但是,John尽了很大的努力排除这些项目对于研究的干扰——他向sponsor提出一个要求是,我们可以为他们提供新的方法或者模型,但是sponsor不应干扰或者介入具体的研究课题以及课题的选择。

在这次NIPS的会议上,我看到了很多很好的很有启发的工作。跟许多参加会议的学者相比,我目前所做的这些工作(包括这篇paper)其实还是非常有限的。这次提出的方法本身也有着很多的局限有待解决,比如目前只是支持sequential filtering,而且Sampler的efficiency的提高还有很大的空间。让这次提出的方法在领域内产生真正的影响,还需要做很多的事情。

NIPS outstanding student paper award

I am glad to share a good news with all my friends.

My paper with title “Construction of Dependent Dirichlet Processes based on Poisson Processes” receives the outstanding student paper award in NIPS 2010.

Relevant information can be found in the NIPS program booklet. Two papers out of 1200+ are awarded and two others got honorable mentions.

My gratitude is delivered to Prof. Grimson, Fisher, and Willsky, as well as all the friends who have been supporting and encouraging me along my academic exploration.

The basic idea of this work is to exploit the theoretical connections between Poisson, Gamma, and Dirichlet processes in constructing dependent Dirichlet processes. The construction proposed in this paper has essential differences from the traditional constructions that are based on either Polya urn (Chinese restaurant process) or stick breaking. I believe that this work is only a starting point along the line in exploiting this relation, and there remains a lot of room for future exploration. I would be really happy if there could be lots of efforts along this direction that make it into an important methodology in Nonparametric Bayesian learning and estimation. Had this happened, it could be much more significant than this paper itself.

The paper is available by the following link:

https://dahuasky.files.wordpress.com/2010/12/ddp_nips10.pdf

Here is the supplemental document, which contains the description of relevant math concepts as well as the proofs of the theorems in paper:

https://dahuasky.files.wordpress.com/2010/12/supplement_doc.pdf

Any feedback is highly appreciated. Thank you.

Blog搬家了

为 Live Space 默哀。。。。。。这个新家还真不习惯 😦

Learning和Vision中的小进展和大进展

首先祝朋友们中秋节快乐!

因为过去三个月的实习工作很繁忙,这么已经很长时间没有更新了。这个夏天参加了两次会议(CVPR和ECCV),在微软完成了一个新的project,这些经历都给了我新的启发。

不积跬步无以至千里

很多在这个领域做research的朋友抱怨,这个领域在过去相当长的时间没有“突破性”的进展了。在过去,我也一直抱有这样的看法。不过,如果比较最近两年的paper,以及20年前的paper,其实,还是可以看到,在很多具体的方向上,我们都已经取得了长足的进展。很多在当年只是处于雏型阶段的算法和模型,经过整个community这么多年的努力,现在的性能已经接近或者到达实用的水平。

虽然,在每年的各大会议中,非常激动人心的paper很少,可是,如果我们把某个方向过去10年的文章串在一起,我们会发现,这个方向的前沿已经推进了不少。这个过程有点类似于进化。在每年发表的成百上千的paper中,真正有价值的贡献只占很小的比例。但是这小部分的贡献能经历时间的考验,被积淀下来,并且被逐步被广泛地接受。当这样的进展积累到一定程度,整个方向就已是今非昔比。

在这个过程中,不同类型的paper其实发挥着不同的作用。举一个简单的例子,在很多问题的传统模型中,因为建模和计算的方便,都喜欢使用L2 norm来测量与观察数据的匹配程度。而近年来,越来越多的模型开始改用L1 norm来取代L2 norm,并且在性能上获得很大的提高。这样的变化起码经历了10年时间才逐步受到广泛的注意。在较为早期的工作里,部分的researcher在实践中发现似乎用L1 norm性能更好,但是大家并不是一开始就深入了解这背后的原理的。于是,这样的观察也许只散见于不同paper的experiment section或者implementation details里面。随着这种观察被反复验证,就会有人进行系统性的实验比较,使得这些观察形成更为可靠的结论。另一方面,理论分析也随之展开,希望能从更深的层次上来剖析其背后的原理,甚至建立严格的数学模型——于是一个本来只是实验中的heuristic的方法终于具有了稳固的理论根基。这些理论将启发人们提出新的方法和模型。

也许在很多人看来,从L2 norm到L1 norm的变化,只是一字之差,不值一提。但是,这种变化对于全领域的影响非常深远,不仅仅在很多具体的topic上带来性能提高,而且引导了学科的发展趋势——robust fitting, sparse coding / compressed sensing受到热情关注,和这种变化是密切相关的。

我在和一些同学交流的时候,发现有些人特别热衷于解决“根本问题”。壮志固然可嘉,但是,我始终认为,根本问题的解决离不开在具体问题上的积累和深刻理解。这种积累,既包括理论的,也包括实验的。至少,对于像我这样的普通人,我觉得,获得这种积累的唯一途径就是大量的实践,包括阅读paper,建立数学模型,推导求解算法,自己亲手把程序写出来,在实际数据中运行并观察结果。新的idea是思考出来的,但是,这种思考是需要建立在对问题的深刻理解上的。从石头缝里蹦出有价值的idea的概率,和彩票中奖没有什么区别。

什么是有价值的?

每个人对于一个工作的价值会有不同的判断。我在这里只是想说说我个人的看法。Research 和 Engineer 不太一样的地方在于,后者强调work,而且倾向于使用已经proven的方法;而前者更强调novelty——创新是Research的生命。

一直以来,一些paper有这样的倾向,为了显示这个工作的“技术含量”,会在上面列出大段的数学推导,或者复杂的模型图。很多的推导只是把一些众所周知的线性代数结论重新推一遍,或者重新推一下kernel trick,又或者optimization里面的primal dual的变换。可是这些东西再多,在有经验的reviewer看来,只是在做标准作业,对于novelty加分为零。

真正的创新,在于你提出了别人没有提出过的东西。创新的内涵可以是多方面的:

  • 建立了新的数学模型,或者提出了新的解法
  • 提出的新的应用
  • 提出新的框架,用新的方式来整合原有的方法
  • 在比较性实验中获得新的观察
  • 统一本来分开的领域,模型,或者方法

创新可以体现在从理论,建模,求解和实验的各个环节之中。判断创新与否的关键不在于有多高深的数学,不在于使用了多时髦的方法,不在于做一个多热门的topic,而在于是否make a difference。

另外,我觉得,创新的大小不能绝对而论。有一些在实验中用于improve performance的小trick,也许能被有理论基础的researcher开拓成全新的方法论,甚至建立严密的数学基础。很多paper中都埋藏着这样的金子,等待trained eyes的发掘(可能连paper的作者自己都没有意识到~~)

离开加州

在Microsoft Research Silicon Valley的intern结束了。感谢Simon,帮助我创造了一段愉快的工作经历。也要感谢Chen Wei,让这个本来枯燥的暑假增色不少。
 
在今天傍晚,将直接从San Francisco飞往希腊——开始一次让人憧憬的旅程。再见了,加州。
 
 
 
 

From NIPS 2010

We are pleased to inform you that your NIPS 2010 submission "Construction of Dependent Dirichlet Processes based on Compound Poisson Processes," paper ID 71, has been accepted for publication in the conference proceedings, with a full oral presentation at the conference. 

There were a record 1219 submissions to NIPS this year, with many strong submissions. The program committee selected 293 papers for presentation at the conference; among these, only 20 papers were selected for full oral presentation, of which yours is one. Congratulations!

----------

过几天就要离开阳光加州(真是很阳光,三个月居然不见一滴雨~~~),启程参加ECCV了,希望在希腊有一个愉快的旅程,认识新的朋友。

本年度CVPR最有趣的文章

在今年的CVPR,见到了很多朋友,也看到很多Paper。

在这次会议里面让我最喜欢的一篇Paper,却不是在会议中正式发表的,而是在TC Panel派发的。这篇Paper的题目叫Paper Gestalt。文章以诙谐的笔调描述了一个基于vision + learning的自动paper review算法。

参加会议的朋友们可以很幸运的在会场获取这篇文章,至于没有来的朋友,我想只能向作者(这位兄弟(也许是姐妹)在paper中自称Carven von Bearnensquash, bearensquash@live.com)索要了。

这篇论文出炉的背景,就是最近几年CVPR或者ICCV的submission呈现急速的指数增长的趋势(在过去10年翻了三倍)。按照这个速度增长,在 10年后每次会议的投稿量就会超过5000篇!也许最好的办法是采用“货币杠杆”进行“宏观调控”——就是对投稿者收费。比如,对每个 submission征收100美元的费用,我相信对于投稿的数量和质量都会取得立竿见影的效果。一方面,很多纯粹是来碰运气的作者会掂量一下花100块 钱来博取1%的命中机会是不是值得;而持认真态度的作者则会对paper精益求精,免得投稿费白白浪费;而最终文章被录用的作者就可以减免注册费,会议方 面也有更多的funding来给有志于为Computer Vision奋斗的学术青年发放参加会议的路费。一举四得,何乐不为,呵呵。

当然了,涉及到钱的问题,自然要经历很多微妙的利益博弈——这些事情还是让Chair们去担心好了。这里,我们还是继续“奇文共欣赏”吧。文章的算法很简 单(前提是你对Machine Learning或者Computer Vision有一点了解),把8页的pdf文档并排成一张长的image,然后就在上面抽feature。做自然语言处理的朋友们请不要激动,这是 Vision的paper,自然用的是Vision圈子自己的方法。好了,抽什么feature呢?主要是HOG(Histogram of Gradients),这是一种纯粹用于描述视觉观感的feature。显然,大段的文本,曲线图,图像,表格,数学公式,它们的feature应该是不 太一样的。然后作者用AdaBoost做feature selection训练得到一个分类器:纯粹根据paper的视觉观感来判断paper的好坏。

说到训练分类器,自然需要一个训练集。这篇文章的作者收集了CVPR 2008, ICCV 2009和CVPR 2009的全部1196篇paper构成正样本。那么负样本从何而来呢?被拒的paper显然作者是拿不到的。于是他很聪明的利用了一个众所周知但是大家 却不会公开明言的事实:workshop接纳的很多是在主要会议被拒收的paper。这样,很不幸的,workshop上发表的文章被用作负样本。在 Workshop上发表了论文的同志们不要打我——我只是讲述一篇别人的文章,这个主意不是我出的。

最有趣的部分要数实验结果了。从ROC曲线来看,结果其实还是不错的——以拒绝15%的正样本为代价,可以滤除一半的负样本。作者对于正负样本的特征做了 一些总结,也许对于大家以后投paper还是有点指导意义呢。。。

正样本的“视觉”特点:
1. 里面有几段公式,看上去文章显得似乎很专业,也显得作者似乎数学不错;
2. 实验部分里面多少要有几个曲线图,即使那几个曲线图说明不了什么。但是,只要有几个曲线图在那里,起码表示我做的是“科学实验”;
3. 最好在文章开头或者最后一页排列一堆图像。其实,我也注意到很多作者喜欢排列很多dataset里面的图像到paper上——即使那是一个 publically available的standard dataset——我不知道这样做的意义何在——除了审美效果。
4. 最好写满8页,代表分量足够。

负样本的特点:
1. 不够页数。在submission阶段,写不满6页的文章被录用的机会很小。虽然最后很多本来8页的文章还是能很神奇地被压缩到6页,如果作者想省掉 200美元的附加页费。题外话,我也一直不明白为什么多一页要多交100美元注册费。
2. 有很大的数字表,就是m行n列,排满数字那种。这篇文章表明,排列了很多曲线图和柱状图的文章比排列了很多数字表的文章有更大概率被接收。
3. 没有漂亮插图。

这篇文章的结果,我也做一些补充评论。
1. CVPR和ICCV的录用结果,对于文章的视觉观感,有着显著的统计相关。从我自己做Reviewer的经验,以及和其它reviewer的交谈来说,这 个确实在一定程度上影响了reviewer的第一印象,甚至是评价基调。一篇文章在first glance给人以专业和有内涵的感觉,会有利于它在reviewer心中树立良好印象。这与学术无关,但是,很不幸,却是一个普遍存在的事实。

对于NIPS这种理论取向的会议,虽然不需要那么多漂亮的图表,但是,文章要“长得”像这些会议的文章。让人觉得写文章的是一个有经验的研究者,而不是一 个打酱油的。

2. Workshop的文章和CVPR/ICCV主会似乎存在明显差距,以至于一个如此简单的分类器都能够在区分它们的任务中取得不俗的成绩。另外,作者使用 workshop paper作为负样本的做法虽然是个人选择,但是,起码在一定程度上反映了这个community对于workshop的态度。

3. 近年来CV paper的投稿量的高速增长,已经严重影响了review的质量。一方面,会议不得不邀请许多没有很多经验的学生参与到review的过程,即使文章是 发到senior researcher的手中,最终还是会被传递到他的某个刚入行的学生那里作为学习reviewing的“牺牲品”。我甚至听说过有reviewer为了 应付due date,把文章交给秘书或者亲戚来审,其结果可想而知了。另外,reviewer也没有足够的时间来仔细的审读paper。很多情况下,读完 abstract和intro,大概翻翻实验结果以及文章的插图,已经基本形成对文章的定性。如果reviewer喜欢这篇paper,它会根据作者的 claim对文章表示赞赏;如果不喜欢这篇文章,就会找一些似是而非的理由把文章拒掉。

当然了,最后我们还有rebuttal,然后由AC meeting来确定文章的生死。Area Chair大多是成名学者,个人的学术水平还是由一定保证的。但是,他们非常繁忙,AC meeting虽然目的是给每篇文章一个decision,但是在一些AC的心目里,这主要是一个旅游和social的机会。大部分的final decision就是根据review结果照本宣科(一个不成文的规矩是review rating的中位数是2作为录取划线标准)。另外,AC大概会看看abstract和rebuttal,然后酌情裁量。

CVPR 2010 Kick off

CVPR 2010 即将开始了。
 
注册参加会议的人数已经创纪录地突破1800了!Really crazy。。。。我看到好多几年不见的朋友都来开会了,一定很热闹~~这回咱也算是半个东道主了。
 
 

开始在加州的阳光生活

昨天晚上刚到了Mountain View,开始了在加州三个月的internship。这是我第三次回到Microsoft Research,不过这次又换了一个地方——微软硅谷研究院。(把这次算上,微软在全球的六个研究院,已经去过其中一半了~~~)

再见了,Boston的朋友们,我会挂念你们的。。。。。。

Notes on Martingales, Random Walks, and Brownian Motion

 
快到期末了,整理了一下18.445后半段的一些笔记,形成了一份notes。
 
 
这部分的课程主要是关于Martingale(鞅),Random Walk(随机游走),还有Brownian Motion(布朗运动)的基本内容。
重点是在使用Martingale, Optional Stopping Theorem, Reflection Principle, 还有Wald’s Identity,对Random Walk和Brownian Motion进行分析。
希望这份notes对于希望学习或者复习有关内容的朋友有帮助。
 
18.445其实只是MIT数学系对于随机过程理论的入门要求,不过在还是要求对测度理论和现代概率理论的基础有比较扎实的掌握的。
起码应该熟悉Sigma代数的独立性,基于Sigma代数定义的条件期望,以及关于可测函数(随机变量)的不同方式的收敛。