OIERS 必读：计算机科学趋势之我谈。。。
Posted by: 穿靴子的猫 (65.59.219.133)
Date: August 03, 2006 05:33PM
常有热血青年问我计算机科学还有啥搞头。
首先我们回顾一下计算机科学的“机械黄金时代”——5/60 年代。这个年代是研究“简单机械”数学对象的淘金时代。这些数学对象包括：字符串，数列，集合，树，图等等。它们的特点是：1. 最简单、最机械，就像数学里的"一元一次方程"、物理里的“定滑轮动滑轮”一样初等。同时这个时代的大背景是应用数学的大发展（冷战时代两个阵营要拼谁的军事和生产活动达到最优化），因此 2. 这些对象不同于其他纯数学的基本对象在于他们有强烈的现实应用性。有了什么样的研究对象就决定了会有什么样的研究成果（算法/方法/原理/应用）。比如，如果研究对象是字符串，就很容易发现我们有实际需求的操作有 压缩、加密、查找子串 等，于是大浪淘沙，我们有了 ZIP, RSA, KMP 这些堪称经典的结果；而那些有用但没有有效解法的问题，几乎都被证明是 NPC 的。。。这样，走得通的路都走通了，走不通的路都被证明是走不通的。。
除了简单机械对象的相关算法设计外，过去几十年同时也是人工智能基本问题的黄金时代。这些基本成果在它们所在体系中的“根本性”就像牛顿的成果在经典力学体系中的“根本性”一样，是后人无法再超越的。。。人工智能的一个目的是对“模糊”（非形式化）信息"形式"的理解，也就是说我们表达的内容可以有各种表现形式：自然语言文本，语音，图像，影像。对他们的分析（analysis）往往比合成（synthesis）要困难。我举一个非常典型的例子：语音识别（speech recognition）是对语音数据的分析，语音合成（speech synthesis）是合成，后者的实际成功大得多。要分析我们就不可避免要知道牵涉到的背景知识（分为“规则 (rules)”和“案例 (cases/samples/examples)”两种，一个案例就是一个特殊的经验，可以看作一个适用范围最小的规则），还有如何把这些背景知识用于我们要识别的数据，这又分为两种态度：按逻辑推理 (logic-based reasoning) 和不要求有严密逻辑推理关系的模糊式、统计式联系（statistical methods 或叫 connectivism，就是把“因”和“果”用经验联系起来（知其往往然）而不是用逻辑推理关系联系起来（知其所以然）），比如初中里的几何证明就是严密的逻辑推理，而 Google 仅仅找到那些紧密出现你的 keywords 的文章片断就是统计式、模糊式处理，就像总设计师说的“宜粗不宜细”。根据具体问题的具体条件，两种态度各有所长。人工智能的另一个目的是对信息“内容” 的处理和再创造。前面我们说的是把同一个内容的数据从一种形式变到另一种形式，比如把一句话从语音形式变到文本形式、把一句话从中文翻译到英文，其实内容不变。那么对内容本身我们可以做什么有用的操作呢？一方面，我们可以把内容表示成一种形式化的知识表示，用上面提到的 logic-based reasoning 来推出新的有用结论。这种操作的局限性在于计算机只能用我们给出的知识反复演绎；尽管我们可以加入统计性的因素让推理更灵活（同时降低了结果的准确性），但仍然受限于有限的形式化知识。另一方面，我们可以不拘泥于形式化的知识表示与推理，而是让计算机和人混和起来思考问题。这时，我们不要求概念和概念之间的可能关系被完全形式化，但我们往往还是要求“一个概念只有一个命名”。典型的这种知识表示就是 Wikipedia，它的每个文章都是一个概念，有唯一的命名（或明确声明多个命名等价），而文章之间的超链接（不明确表示的关系）使 Wikipedia 成为一个概念的网络。由于概念之间关系的不明确，我们不说它是一个语义网络（semantic network，知识表示的最重要方法，与 first-order logic、frames 等价），而是一个概念网络（ontology，即一些概念的集合，每个概念都有严格的命名）。概念命名形式化而概念关系非形式化的本性决定了这种东西可以让人和计算机相结合完成某些任务。比如，我心里有一个 idea X，我想知道它是否已经被别人提出过了，如果被别人提出过了那么它的命名是什么。这是一个很有实际意义的问题，比如申请专利之前你要查找前人是否已经公布过类似 idea，比如你不知道一个概念在英语中如何表达（如果这个概念在你的母语中没有一个专门的术语 A 或者虽然有 A 但是你的双语词典不能为你直接建立 A 到英语对应表达 A' 的映射。。。）。此时我们就可以基于一个 ontology 如 Wikipedia 来间接寻找 X 的所在。例如我们要找“热插拔”的英文说法（假设不存在“热插拔”的中文条目），我们可以先想象一下它有什么特别相关的概念，我们想到“即插即用” (plug and play)，因为这两个概念是可比较的两种硬件安装规格。于是我们先进入英文 Wikipedia 条目“plug and play”: http://en.wikipedia.org/wiki/Plug_and_play 然后我们发现该文章中比较了即插即用和一个所谓“true hot swapping”的相同和不同。通过文章对这个 hot swapping 的描述，我们有很大把握认为它就是我们要找的“热插拔”。我们可以进一步用这个关键词在其他文献中确定它就是热插拔。这个问题跟查双语字典正好相反，双语字典是你给出一个已知的母语术语 A，它告诉你 A 对应的未知的外语术语 A' 以及 A' 的未知的定义 Def_A'，而我们刚才说的这个问题是已知一个概念的定义 Def_X，如何知道这个概念在某个语言中的的命名 Name_X。这又叫 reverse dictionary lookup.
综合以上两段，我们想想我们当代应该研究什么。显然我们不应该再去研究简单机械对象，那是口枯井（当然如果你不以“有实际用途”为导向去选择研究对象，你完全可以去研究 100 个方块组成的俄罗斯方块图形有几种（这个美国人 60 年代也研究过了，呵呵）、人为设计一个类似五子棋的棋类游戏然后研究其制胜策略（这就是所谓趣味数学成果，因为研究对象可以无穷制造，所以总有研究的空间；这也是为什么某数学家（好像是丘成桐）教育我们要研究自然界的数学模型而不是那些人工制造出来的数学对象。就算 Knuth 这种至少有 KMP 这样经典的有用简单机械成果的大牛，也在 70 年代百无聊赖之际研究过游戏“大智之人”（Mastermind，又叫“猜数字”）；而且比尔盖茨在 70 年代哈佛退学以后还兴致勃勃地研究过翻烧饼的组合数学问题 [1][2]；MIT 有个很年轻的加拿大计算机教授 Erik Demaine，现在华人学者热衷于提起他，他做的最有特色的研究之一是折纸中的计算机学问。。））。就连在简单机械算法世界里浸淫了几十年的 Knuth 也在 2001 年接受采访说：“如果。。。人生从头来过，我现在愿意做一个研究机器人学或生化的研究生。。。理论计算机科学。。。经过五十年的爆炸性发展后，很难想象还有多少发展空间。我不认为现在对以前的经典结果作小的优化有多大意义。当然我不能完全否定计算机科学继续发展的可能性，但这种可能性跟生物学是无法相提并论的。。。计算机科学经过五十年就发展殆尽，而生物学却很容易就提供给我们足够研究 500 年的问题，两者差距是如此巨大。”[10][12] 有人问，那么计算机科学不是还剩那个圣杯——“P?=NP”么？让我们看看 Knuth 2002 年在奥斯陆大学的“All Questions Answered”演讲中是怎么说的：“。。。就算 P==NP，仅仅知道一个问题有多项式时间算法是没有实际意义的，因为那个指数可能大得超过计算能力。因此也许我们从一开始就不应该提出 P?=NP 这个糟糕的问题。”[11]在这次演讲中 Knuth 还特别强调要“阅读大师的思想” (Read the masters)。在 2001 年慕尼黑大学另一次同名的演讲[12]中，Knuth 干脆认为“P?=NP 可能是 Godel 所说的‘不可证明的定理’之一”。
所以我们可以想到，我们当代要研究的对象必然是更复杂的，或者机械的数学世界以外的活生生的现实问题。比如在劳动人民的生活中，自然语言是全球化背景下一个突出的问题，同时也是足够复杂的对象；比如股票市场的预测（按道理说这需要计算机知道足够多的背景知识和内幕消息，因此我对那些统计学者用统计过分简化整个事情是非常鄙视的）；比如宏观经济/社会；比如自然科学如生物、纳米里的复杂结构和功能；比如复杂工程学如导弹防御系统、机器人、航天；比如经济中的供求双方信息不对称问题（你想找某个很窄的领域的知识或真人专家，你如何跟这个知识或专家接上头？特别是当这个“很窄的领域”尚没有特定学名时？这又回归到了我上面说的 reverse dictionary lookup 问题：在对应的 Wikipedia 页面上留下相关知识和真人专家的联系方式。而作为“卖方”，一个真人专家如何拓展他的业务范围？他可以观察自己当前领域周边的 wiki 文章是否也可以让自己去“坐堂”；一个自主学习的学生如何决定自己下一步学什么/研究什么？也是同样道理。）；比如让计算机半自动的穷举、推理、归纳、联想出新的创新机会。
没有评论:
发表评论