OIERS 必讀：計算機科學趨勢之我談。。。 (More! 72 Reads)
Posted by: 穿靴子的貓 (65.59.219.133)
Date: August 03, 2006 05:33PM

常有熱血青年問我計算機科學還有啥搞頭。

首先我們回顧一下計算機科學的“機械黃金時代”——5/60 年代。這個年代是研究“簡單機械”數學對象的淘金時代。這些數學對象包括：字符串，數列，集合，樹，圖等等。它們的特點是：1. 最簡單、最機械，就像數學裡的"一元一次方程"、物理里的“定滑輪動滑輪”一樣初等。同時這個時代的大背景是應用數學的大發展（冷戰時代兩個陣營要拼誰的軍事和生產活動達到最優化），因此這些對象不同於其他純數學的基本對象在於他們有強烈的現實應用性。有了什麼樣的研究對象就決定了會有什麼樣的研究成果（算法/方法/原理/應用）。比如，如果研究對象是字符串，就很容易發現我們有實際需求的操作有 壓縮、加密、查找子串 等，於是大浪淘沙，我們有了 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，現在華人學者熱衷於提起他，他做的最有特色的研究之一是摺紙中的計算機學問。。））。所以我們可以想到，我們當代要研究的對象必然是更複雜的。比如在勞動人民的生活中，自然語言是全球化背景下一個突出的問題，同時也是足夠複雜的對象；比如股票市場的預測（按道理說這需要計算機知道足夠多的背景知識和內幕消息，因此我對那些統計學者用統計過分簡化整個事情時非常鄙視的）；比如宏觀經濟/社會；比如自然科學如生物、納米里的複雜結構和功能；比如複雜工程學如導彈防禦系統、機器人、航天；比如經濟中的供求雙方信息不對稱問題（你想找某個很窄的領域的知識或真人專家，你如何跟這個知識或專家接上頭？特別是當這個“很窄的領域”尚沒有特定學名時？這又回歸到了我上面說的 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 大在求新求異上的競爭，現在看來，還需要一個個個人的帶頭作用。三年來，我越來越認識到自由主義對創新的必要性，這可以在我的研究經歷和成果中體現出來。用一句斬釘截鐵的話說就是：“自由不實現，創新不能談”。

[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

-------------------------
Operation Chinese Freedom