老赛,机器学习要能光靠记忆就好了,或者对我们来说糟了:)


所有跟贴·加跟贴·新语丝读书论坛

送交者: 自如 于 2010-03-29, 16:13:00:

因为要是穷举就能搞定的话,俺们早已失业,转行内蒙古学送外卖去了。

这两天反正procrastinate了,干脆多说两句,也算抛砖引玉,请内行们指正。(鸡横扫内行要来“扒裤子装X”作义演也无任欢迎:=)

CS101:现实世界里大部分的问题都是NP-hard或#P-hard的。译成中文就是说计算量随着问题size指数增长(除非你相信P=NP,P for polynomial)。

指数增长为啥可怕呢?举围棋为例。3X3的棋盘有3^9棋局~20k,不多;而9X9的棋盘就剧增为3^81~10^40;到19X19是3^361,超过了估算的宇宙所有原子的数目。也就是说,即使在鸡头虚拟现实里每个原子都变成一部奔5,也算不过来。这也是为什么下chess的方法无法解决围棋的一个主要原因。早期AI(尤其是MIT school)的许多智能系统都是在小问题里出彩,却无法用到真正的问题上。

一个相关的数字,人脑的神经元大概有一百亿,就是10^10,听起来很多,可就算9X9围棋死记硬背也做不到。电脑的计算量虽然有Moore定律,但现在还赶不上这个数(有估计还要5-10年),而量子效应注定Moore定律也快到尽头了。

咋办呢?造原子弹第一颗最难,因为不知道能成不,后来的就容易多了。俺们也有个后来的优势,因为进化已经把人脑造成了,所以至少智能是可能用机械过程实现的,问题是怎样去做。

最早的突破是发现一些表面上指数的问题有多项式算法。Dynamic programming是这类算法最重要的一个framework。基本思想是大事化小,本来指数式的大树其实是许多相同的小枝桠组成的,把这些小问题的中间结果记下,把重复的计算量省下,如此recursive的进行,就能用多项式时间(譬如n^2,n^3,n为size)解决问题。

DP无处不在,是许多CS算法的基础,但是基本问题没有解决,因为理论证明NP-hard问题是不可能有多项式算法(whether use DP or not)。AI圈有个笑话:database老是run out of problems,成天从AI里找新领域(譬如XML,semantic web,现在是information extraction,probabilistic DB)。而DB圈就反唇相讥,AI有解决过问题吗?:)

从理论上讲,我们关心的问题是不可能解决的(除非P=NP,或者quantum computer, DNA computing有一天实现了)。那么AI/ML人大概都该散伙分行李了吧。且慢!计算理论有一个明显的局限,因为它是worst-case analysis。也就是说在冥冥中平行宇宙里肯定有一个是要指数增长的,但俺们生活的现实世界呢,却未必如此。Carl Sagan在一部纪录片里曾经在夜幕的繁星下面说了一段意味深长的话:如果世界变化太慢,不会有今天的多姿多彩,反过来如果变化太快,我们又不可能去认识它的规律(大意,可能被俺的意识加工了)。

对于我们来说,人脑的智能是铁板钉钉的,there must be at least one way out。问题是where,how。

一个可能的出路就是自然现象里的结构。譬如game tree的alpha-beta pruning,利用的就是对分支的估计,将无希望的分支早早剪掉。剪得越早,节省的计算量越大。由此发展出早期AI的重点,搜索。上述的pruning可以推广到叫A* search的framework,既能保证找到最优解,又可以通过pruning(或者priority queue)大大减少计算量。但A*的成功系于对分支的估计(admissible heuristic),问题的结构越明显,估计越准确,节省就越大,否则又会退化成指数的梦魇。

另一个强有力的工具是概率统计。许多由复杂细节导致无法model而产生的不确定性(uncertainty),可以用概率模型来拟合。譬如扔一枚骰子,很难准确预计抛出的点数,但可以估算各种可能的概率。倘若问题有一定规律性,所用的模型类(model class)得法,就有可能通过拟合数据来找到能用来预测的model。

在机器学习里,一个与此相关的理论突破是valiant 84年创立的PAC learning。PAC learning是一个框架,研究抽象的统计学习问题如何能用多项式(P)算法实现。类似的分析还发展出随机算法(randomized algorithms)。核心的思想是,通过概率绕过NP-hard。算法不保证在worst case获得最优解,但保证倒霉的概率可以变得任意小(当然计算量相应增加,但是多项式的增加而非指数)。

上述理论属于传统的统计领域。它们关心的问题跟AI/ ML面临的现实问题有明显差异。传统的统计关心iid(independently and identically distributed)问题,一个重要的问题是如何设计实验,使得这个假定是合理的。而AI/ML里(尤其是后互联网时代),数据大大的有,可无法保证是iid,因为产生的过程往往是有一定规律的,e.g., query log。更严重的是,iid假定会把大量的信息泼掉。譬如对网页的分类,传统的做法是关注单个页面里的信息(e.g.,bag of words)。然而网页之间的连接其实包含了丰富的信息。一个极端的例子就是google赖以在web search上后来居上的pagerank算法。这个算法的核心完全无视网页里的内容,而只利用连接来算relevance。

于是乎,在最近10年里,AI/ML的一片新边疆渐渐浮现。像所有的新事物一样,它有很多名字e.g., statistical relational learning, structured prediction, Bayesian logic programming …而其核心内容就是把上述的两类方法结合起来。通过逻辑语言来描述明显的结构,通过概率模拟不确定性。现在要预测它能走到哪里,走得多快,还为时过早,但它是一个最有希望的方向(I’m biased, of course :=)。




所有跟贴:


加跟贴

笔名: 密码: 注册笔名请按这里

标题:

内容: (BBCode使用说明