计算机科学趋势介绍

OIERS 必读：计算机科学趋势之我谈。。。（0804062021 加量不加价版） (More! 275 Reads)

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 文章是否也可以让自己去“坐堂”；一个自主学习的学生如何决定自己下一步学什么/研究什么？也是同样道理。）；比如让计算机半自动的穷举、推理、归纳、联想出新的创新机会。

还有一个关键的非技术问题，就是作为学科竞赛中的佼佼者或者感兴趣的小有所成者，如何展开研究？为什么中国出了那么多大牛前辈却少有知名的研究？第一， OI 中获取的知识就是上面说的“简单机械世界中的对象及其操作”。OIERS 不管是中级还是顶级选手，主要擅长的仅限于此，当然我们决不能否定我们向其他空间拓展的潜力。而且我认为大多数 OIERS 都有作出很好研究的潜力。第二，研究的过程不是工程开发或生产，没有固定日程安排，而是一种商业投机行为，因此需要极大的自由、自主权。投机能力可以通过考虑做个商业产品来锻炼。一个对机会主义、个人主义、自由主义没有很好的理论觉悟和运用的人，或者一个受到现实中给定学习方向、研究方向、研究日程所桎梏的人，作不出好研究。为此我专门另起一段。第三，要培养很好的哲学思辩能力，特别是归类、归纳、观察能力，而不仅仅是死板的推理能力。我突然想，如果我们去看看大学的哲学教材，看看它如何把一套歪理邪说讲得头头是道、自圆其说，也是一种哲学思辩能力。培养哲学能力的方法可以是常常思考一些自然的、社会的、没有严格公理的现象，比如自然语言的本质表示，比如民族主义和自由主义本质是什么 [3]，比如当代世界的经济格局以及其背后的技术决定因素。要博学，要有广泛的兴趣，要喜欢百科全书，接受通识、开放的教育而不是应试教育。推理能力在一个基础已经形式化的封闭体系如纯数学里是很重要的，而观察、归类、归纳能力则有助于我们研究开放性的事物，比如我现在已经有了一个点子，但是我发现别人已经提出过了，就这个点子本身其内在关系和本质的研究已经很成熟，已经自成一个独立的系统，那么我如何去发现这个系统做不到、解释不到的现象，从而扩展这个系统？电影《美丽心灵》里就有经典的例子：亚当斯密已经建立了零和博弈的经济学理论，这个理论已经自成系统，甚至已经被形式化，如果你仅仅用逻辑推理想有所新发现，你必然会在这个封闭的体系里打转转。如果你想有所创新，就必然要到盒子外面去想（think outside the box），这就需要观察该系统无法解释的现象，并归类、归纳出新的规律，于是纳什才归纳出“共赢”现象的博弈规律，跳出了亚当斯密设计的盒子。从盒子外面看，亚当斯密的盒子就成了“incomplete”的了。还有一种研究方法叫“没事找事”，就是故意（而且是先于经验观察）跟前人唱反调，比如非欧几何。要善于观察善于表达，比如看看我是怎么写这篇文章并把我要说的内容归类成段的。哲学是凌驾于死板推理的，是一切思想成果的背后机制，哪怕是数学研究也是要有哲学领悟能力的。我国的应试教育强调服从既定方针（就像一个体系里的公理和定理）式的推理能力，打击了我们自由观察、探索、思考体制外的外层空间现象的积极性。而西方由于崇尚自由主义，勇于探索现有知识体系以外的“非理性世界”，做成败莫测的冒险，甚至敢于相信有 beyond 我们观察能力的 God 的存在，有了这种对哲学的坚持，才不断从盒子内的科学走向盒子外的科学。第四，以往的顶级 OIERS，由于一没有投机的经验和物质回报的滋润（最近听说一句话叫“钱是英雄胆”）、二没有自由探索 自主研究方法 的机会（IOI 完了往往上国内大学，学的是古人的最终思想产品（end product）如微积分和简单机械算法而没有学到或者自己悟到思想不断向外发展的哲学和方法论（方法论就是某个哲学思想的具体可操作化），他们高中被高考或 IOI 所驱使、大学本科被出国读研究生所驱使、读研究生时被研究生文凭所驱使，内心并没有时间真正去长期观察盒子外的东西，而到了公司里，又被工作业绩和生存压力所驱使。）因此一直无法改变“大家都不知道怎么研究”的传统、三是某些人本来就没有兴趣投资时间去观察没有把握的事物——他们喜欢走保守稳定的职业生涯（如 CS -> Data Mining -> 搜索引擎公司 -> Statistics -> Accounting -> 华尔街），很大程度上是因为我们的应试教育鼓励了保守稳定的态度——针对我给你的价值观（考试大纲）优化你自己，你就能得最高分。所以，不要指望那些愿意为高分而努力的人会平白无故就突然放弃“稳定压倒一切”去中途追求他们认为风险很大的“改革开放”。有人问，你说的这两种态度（稳定压倒一切 和冒进），难道真的是水火不容、鱼与熊掌不可兼得？非也。关键是：循序渐进，逐步提高投资和回报的高度。首先建议学生们在寒暑假做个信息技术产品（软件、网站）或服务（服务不能太花时间，否则扰乱你的长期研究，最好是时间由你选择的 freelance （打零工）），取得经济独立，然后就能投入自己真正感兴趣的追求。有人还要问“文凭怎么办”。确实，engineering degree 是大多数人出国、工作的必备，这一点我以后再写文章讨论。如果你没有魄力，权宜之计是，争取到香港等地的大学学习，因为虽然都是 degree，过程不同：一个是稳定压倒一切推着你走，一个自由度更大吧。如果你有魄力，且不去说 Bill Gates，就看看我们熟悉的 BitTorrent 的发明者 Bram Cohen 的故事[4]吧。相似的现代故事我还能举出一些，比如 Google 的 Glen Murphy，他的 Blogger Web Comments 表现了一个很有内涵的应用。如果我大张旗鼓的鼓吹 no degree，很多人肯定不认同。但是据我了解，至少在计算机科学和应用数学领域，如果你想做纳什，你必须学着他说“Class will dull your mind, destroy the potential for authentic creativity.”某一次我代一个信息学奥林匹克国际集训队的队员到 comp.theory 上问作业[5]，结果被上面的美国教授们骂得狗血喷头，什么“自己不好好学，到这里来问”云云，美国的计算机大学教育之严格（=不自由）可见一斑。这也难怪 ACM 近年颁发的图灵奖是一年比一年烂。我看过四年的 ACM TechNews [6]，发现美国主流计算机学术界总是沉湎于旧的知识体系不能自拔，总是围绕着 security 等陈旧的话题，或者是 voting machines, RFID 这些所谓新潮的浅薄话题，目的只有一个：好捞联邦政府的研究拨款。所以我最近几个月都不看了。学术界怀旧无能，反倒是 Bram Cohen 这样的毛头小伙能出新意，引得 Microsoft（代表计算机工业界）的研究员去“改进” BitTorrent，结果被他批判为“All talk and no work” [7]，和 Stanford （代表计算机学术界）请他去演讲 [8][9]。

这一段本来要讲自由主义、掌握自主思想的权利（也就是有权胡思乱想），结果很多内容都在上一段讲了。思想就像是一棵棵树，重在不同。你的思想往那个方向长，结果如何我看到了，因此我不想重复你的想法，我要有意无意、有理无理地朝这边长，朝没人长到的空间去分枝。这种思想方法，就是自由主义。我上 F 大时，本想借着独立研究成果来挑起 T 大和 F 大在求新求异上的竞争，现在看来，还需要一个个个人的带头作用。三年来，我越来越认识到自由主义对创新的必要性，这可以在我的研究经历和成果中体现出来。用一句斩钉截铁的话说就是：“自由不实现，创新不能谈”。

后记：莱布尼兹的四大梦想和我的人类四大信息自由

机械计算机理论之父莱布尼兹有四大梦想[13]，其中一些现在已经实现了：

1. Encyclopaedia - 全世界人民集体编写的、用非形式语言（自然语言）表达的一部百科全书。这就是今天的 Wikipedia。

2. Universal Language - 一个全人类普遍使用的非形式语言。关于这个曾经有过 世界语、逻辑语（Lojban）等尝试。

3. The lingua characteristica - Universal Language 的形式化版本，同时也是 Encyclopaedia 的形式化版本。如现在 First Order Logic + Cyc。

4. The calculus ratiocinator - 自动推理一个 lingua characteristica 命题是否成立的机器，如现在的 Prolog。

我认为信息技术应该提供一个现代人以下四大信息自由：

1. 物理上连通的自由——已知一个人/信息资源的地址就能无阻碍的访问这个资源：就是现在的互联网；

2. 跨自然语言沟通的自由——能在软件的辅助下与一个讲自己不懂的自然语言的人准确地沟通，实现方法是消息经过一个形式化语言中转；

3. 跨越说法差异，连接本质相同的思想的自由——不管两个人对一个思想的具体说法（表达形式）有多不同，只要思想语义本质相同，那么这两人就能够建立联系，也就是上面说的 reverse dictionary lookup；

4. 连接问题和解决方案的自由——对于给出的任何问题，计算机都能通过人类现有知识和自动推理给出解答；或者如果计算机无法独立求解，至少告诉我解决此问题牵涉的人类现有知识有哪些。

[1]http://en.wikipedia.org/wiki/Pancake_sorting

[2]http://scholar.google.com/scholar?sourceid=mozclient&ie=utf-8&oe=utf-8&q=Bounds+for+Sorting+by+Prefix+Reversal

[3]http://www.bytecool.com/ioiforum/read.php?1,3695,3695#msg-3695

[4]http://www.wired.com/wired/archive/13.01/bittorrent.html

[5]http://groups.google.com/group/comp.theory/browse_frm/thread/c37b7f0585f8d823/c7c343e8a07028b3?lnk=gst&q=k-ary+tree&rnum=2#c7c343e8a07028b3

[6]http://technews.acm.org/current.cfm

[7]http://bramcohen.livejournal.com/20140.html

[8]http://www.stanford.edu/class/ee380/Abstracts/050216.html

[9]http://stanford-online.stanford.edu/courses/ee380/050216-ee380-100.asx

[10]http://www-helix.stanford.edu/people/altman/bioinformatics.html#12

[11]http://www.tug.org/TUGboat/Articles/tb23-3-4/tb75knuth.pdf

[12]http://www.ams.org/notices/200203/fea-knuth.pdf

[13]http://www.rbjones.com/rbjpub/philos/history/xh003-m.html

我认为信息技术应该提供一个现代人以下四大信息自由：

1. 物理上连通的自由——已知一个人/信息资源的地址就能无阻碍的访问这个资源：就是现在的互联网；

2. 跨自然语言沟通的自由——能在软件的辅助下与一个讲自己不懂的自然语言的人准确地沟通，实现方法是消息经过一个形式化语言中转；

3. 跨越说法差异，连接本质相同的思想的自由——不管两个人对一个思想的具体说法（表达形式）有多不同，只要思想语义本质相同，那么这两人就能够建立联系，也就是上面说的 reverse dictionary lookup；

4. 连接问题和解决方案的自由——对于给出的任何问题，计算机都能通过人类现有知识和自动推理给出解答；或者如果计算机无法独立求解，至少告诉我解决此问题牵涉的人类现有知识有哪些。

整篇都基本没看懂，就最后这几句似懂非懂

中心思想不错，我个人非常赞同。

就是——

在古代，这样长篇大论，耽误陛下时间者，是要处以割小鸡鸡刑罚的。

另外，我个人认为，计算机最终的发展会如同生命一样不断进化一般。

1. 让每个需要的人桌子上都有一台Computer

2. 让每个桌子上的终端连接起来，让全世界能分享彼此

3. 所有的终端遍布世界的每个角落，无线的网络使计算机融入空气

4. 理论上，计算机会成为现实世界的另一个维度，某些人可能会放弃这边的生活，而承认自己的生命是活在网络构成的逻辑世界中的（有点像《Matrix》）

5. 为了更有效的传递信息，我们需要一个能够比光速更快的传递信息方式，网络的覆盖面积会程几何级数增长

6. 生命与智能技术的界限日趋模糊，机械智能开始讨论“生与死”之类的问题。

7. .................................