$自如
其实从学术界来讲，人工智能（AI）一直在稳步前进，其应用已渗透到我们生活中的每一个方面，只不过如一个行内的笑话所说：AI一旦在一个应用上取得成功，它就不是AI了。AI的几次低谷主要因为不切实际过高的期望。譬如60‘s机器翻译，70’s语音识别，90s第五代计算机等等，都是因为人们盲目乐观，以为短期内可望解决这些问题。事实上，时至今日，MT，speech recognition等仍是未解决的难题，属于AI－complete（彻底解决先要实现强AI）。
因为历次挫折，AI名声不好，同时大家吸取教训，不会再象以前一样容易过分乐观。事实上，AI最近取得长足进展，而这进展很大程度上来自于它的一个分支：machine learning。ML给工业界带来实实在在的利润，成为一个名副其实的buzz word。有一个做speech recognition的毕业生把简历放上网，没人理睬，改头换面一番换上ML的名词，马上得到不少面试的机会。Google被戏称为ML研究者的黑洞，因为它大肆招聘ML PhD和成名研究者，但是并不鼓励发表论文。Bill Gate在NY Times的一个interview中称ML若取得突破，其价值不亚于10个Microsoft。其实他还是远远低估了ML的潜力。
ML的历史和AI的整体差不多长，最早源于神经网络的研究。因为大脑是最能学习的系统，但大脑和电脑的工作方式大相径庭，在许多应用上却远为成功（譬如图像识别）。从纯计算能力上讲，电脑超过人脑已是指日可待，但AI离人类的智能在总体上仍然相去甚远。神经网（NN）企图模仿人脑来在AI里取得进展。先是Rosenblatt提出Perceptron及一个有效的学习算法，但被指出它只能处理线性可分问题，而多层NN可以处理任意复杂的问题，却缺乏有效的学习算法，NN自此沉寂了十多年。80s有人重新发现了backprop算法，可以有效学习多层NN，带来了一个神经网的热潮。潮退后人们清醒过来，逐步发现NN的困难。BP只能学习局部最优，稍为复杂一些的多层NN却有无数的局部最优值，就像一个到处凹凸不平的地形里，只靠近视的下山法（gradient descent）无法找到全局最低点。NN由此走到了尽头。有一个ML里著名的会议叫Neural Information Processing System （NIPS），源于当年NN的热潮。现在neural却成为这个会议最可能导致论文被拒的一个词。
在AI中，NN属于numeric approach。ML的另一个方向与数学逻辑关系紧密，属于所谓的symbolic approach（符号主义），譬如rule induction，theory revision，inductive logic programming（学习prolog程序），核心是定理证明（theorem proving）。这条路与expert system结合曾名噪一时，但是logic的根本问题是脆弱性。现实生活中每一条规律都有太多的反例，还有噪声，不确定性等等，除非局限在一个非常有限的范围内，纯粹用逻辑根本无法施行。AI最近一次冬天跟这个很有关系。
从计算理论上来说，所有AI关心的问题都至少是NP－hard（也就是说，除非上帝发飙，否则只存在计算量随问题规模指数增长的算法）。有人因此嘲笑数据库的研究者，因为他们最大的问题是他们常常没有问题可做，最近一次是现在，自从XML之后，他们无事可作，只好开始从AI这边借问题，譬如 probabilistic DB，information extraction之类。DB的研究者则反唇相讥，AI有解决过问题吗？其实是有的，虽然离grand goal尚远，但每一小步就足已带来巨大的影响。当然，AI并不能违反计算理论，指望明天发现一个多项式增长的算法。但计算理论是就最坏情况（worst －case）而论，而现实生活中的问题多有结构可资利用。咱们智人本身就是最好的例子。人脑不过是另类的计算机，NP－hard的问题，人类能够在现实生活中应付自如，计算机也就可能做同样的事。（俺是彻底的强AI主义者。进化论已经将形形色色的活力论扫地出门，没有理由相信基于碳原子的智能不能用硅原子重新实现。）
那么最近AI和ML的进展在那里呢？在硬件上，计算能力的指数增长使得一些过去不可想象的方法成为可能；在理论上，统计的应用，逻辑和概率的结合，开辟了一片前所未有的广阔战场。有人戏称NIPS应改名为BIPS，B for Bayesian，指的是统计里贝叶斯方法在ML中的广泛使用（对于统计本身，计算机也使得Bayesian vs frequentist的哲学争论在历史上首次偏向前者）。今天，关系（relation）则成为新的buzz word，其核心是用逻辑表达复杂的关系，用概率统计处理不确定性。这是ML向强AI迈进的一个很有希望的方向。一个很有意思的热点是做machine reading，让机器从网上浩如烟海的资讯中自动学习，获得知识，帮助决策。这需要解决NLP，natural language processing，另一个AI－complete问题。而它一旦成功，我们就有了一个实现强AI切实可行的方法。当然啦，前途是光明了，道路也是曲折的。：）
想了解ML在业界的广泛应用，super cruncher是一本很好的普及读物。
1. 希望把ML定义的清楚一些。根据我的理解，你说的AI失败的例子（MT,语音识别等）都包含ML，而且ML很可能是关键。例如，机器翻译的关键是了解输入句子的意义。这好像就是ML的问题吧？所以，很可能你后面说的成功的ML与我所理解的ML不同。
ML最经典的定义是指从数据中学习输入输出函数，从某种意义上来说，相当于自动生成program，包括几大块：
supervised learning － 数据中包含正确的输出（所谓label)，这是最容易也是最成熟的一块。
unsupervised learning － 只有输入，譬如clustering，比较难，但也在不断进展。现代MT里的word alignment基本是用这一块做的。
semi－supervised learning － 部分有输出label。这是当前一个热门，譬如NLP里，可以先对一小部分数据加label，再利用web上大量的文档。
早期MT的方法基本是从coding theory中来，以至时至今日还沿用后者的许多名词，譬如输出叫decoding。机器翻译的关键的确是了解输入句子的意义，natural language understanding，而做到这一点，需要有常识（common－sense knowledge）以及语义，pragmatics等等，能做到这些，强AI就可以已经在手了。这跟ML的问题在抽象层面上没啥关系，但实现MT需要 ML方法是现在的共识。
2.你说最近逻辑和概率的结合开创了新机会。但是据我所知这个概念是早就有了。Bayesian是老老年的事了。二十年前就有模糊逻辑（Fuzzy Logic），定义了基于概率的逻辑运算。现在的突破在哪里？我是不是漏掉了什么？
Bayesian的主要问题是没有计算机（或计算能力不行时）根本不实用。所以统计历史上frequentist一直占上风，直到最近才扭转。
我说的逻辑是指一阶（first－order）。fuzzy logic的问题是它的定义（与概率相比）不完全能自恰，所以只是在某些特定的应用上取得成功，不能作为一般智能的基础。
3.NP-hard的基本概念我了解，但是我不明白它为什么就是死刑宣判。在算法研究领域，NP-hard的算法不受欢迎是可以理解的：因为允许了NP- hard的算法，很多问题用蛮力就能解决了。算法研究的目的就是要达到比NP-hard更高的效率。但是对于实际应用来说，问题的尺度是有限的。NP- hard不等于计算量无穷大而不能实现。另一方面，在AI中，即使允许NP-hard，得到有效的算法也不是容易的事儿。所以在我看来，是不是NP- hard在这里并不是太重要。我说的有道理吗？
很好的问题！指数增长在理论上不是死刑，但在实际上的确是死刑。围棋是一个例子。2的361次方是有限值，但即使穷尽已知宇宙（假设每一个原子都能作计算）的资源，也不可能用穷举法解决。
“算法研究的目的就是要达到比NP-hard更高的效率” 这并不对。NP！＝P除了幻想家，没有人不相信是事实。所以在最坏情况下，AI的问题只有指数增长的算法。但是也正因如此，这种worst－case分析没有太大用处，算法研究的新热点是提出新框架，譬如randomized算法，interactive proof。