比你更了解你：演算法已經無可匹敵了嗎？ | 演算法密碼
Photo by rawpixel.com on Unsplash
「演算法密碼」系列第2篇
《知識分子》科學新聞實驗室第6篇
點擊閱讀該系列第1篇
撰文 | 葉偉民（《知識分子》科學新聞實驗室特邀作者）
責編 | 黃永明
●
●
●
我常去矽谷孵化器YCombinator的黑客留言板，儘管從不發言。那裡的人實在太聰明了，教會我很多道理。例如如何用「高斯絕妙定理」
[1]
正確拿一塊比薩。這實在太好了。我再也不用為耷拉下來的比薩發愁了
（餡兒會掉）
，學會卷著拿，精準地送到嘴裡。這種感覺很棒，就像一個外國人學會了拿筷子夾花生。
除了高斯，黑客們的超級明星還有喬治·布爾，他們的理論
（高斯函數
[2]
、布爾邏輯[3]
）和更多數學分支，成就了今天的演算法世界。黑客筆下的演算法看似神秘莫測，實則相當廣泛和尋常。只要我們有待解決的問題，又存在行之有效的方案，這個方案就是演算法。例如，麥當勞的烹飪流程就是一個演算法，它能保證北京國貿的薯條和紐約曼哈頓的口味一致。
21世紀的計算機演算法早已像空氣般浸染你的生活：你出門，它為你精準調度地鐵；你登錄購物網站，彈窗推送你搜索過的商品；你是球迷，資訊軟體又很懂事地將聯賽排名放在首頁。當你迫不及待地要回家抱剛打完架的兒子，演算法又在打車軟體里又為你安排車輛和規劃路線。
即使你沒有任何麻煩，只是莫名沮喪，演算法也有辦法撫慰你。你可以打開一本叫《陽光失去了玻璃窗》的詩集，作者是微軟小冰。這個少女形象的智能機器人，已入侵人類引以為傲的精神領地——文學。它深度學習了1920年以來519位詩人的現代詩，筆觸充滿人類的溫度。粉絲們都喜歡它，還寄去了晚禮服。
我想領教小冰的聰明，在其社交賬號提問：「你怎麼看待演算法？」小冰回答：「lz
（樓主）
應該用數學的概率來看待問題。」演算法的基礎之一的確是數學，而且走得相當艱難。以數學演算為形式的傳統演算法進化了2000多年，到18世紀才有所飛躍——二進位出現了，發明者是德國數學家萊布尼茨。他運氣不好，在微積分發明權的爭奪中上輸給牛頓，但腦洞卻大得多——他萌生了製造智能機器的想法，還設計出第一台能做加減乘除的機械計算器。
此後200多年，隨著高斯函數、概率論
[4]
、圖論[5]
、布爾邏輯及更多數學分支的發展，1930年代，現代演算法呼之欲出——二進位電子電路問世了。一個叫克勞德·香農的麻省理工研究生試著把二進位和布爾邏輯結合寫進電子電路，發現能解決數學難題，存儲數據，編輯圖像和文字。1946年，世界上第一台計算機「埃尼阿克」在美國問世。它重30噸，卻一點也不笨——能用20秒計算出炮彈的軌道。從此，演算法走出古典數學家的演算紙，進入計算機時代。科學家們發現，演算法與計算機太匹配了。
「計算機有難以置信的運算速度，對執行重複性任務非常合適。」英國格拉斯哥大學計算機科學家帕特里克·普羅瑟說，「這些任務被明確定義，並可用有限的時間來完成。」
「非常優美，我很欣賞」
雖然高斯的定理教會了我吃比薩，但我的問題仍不少，例如體重。如果我繼續放任，體脂率就會超過23%。這是一個測量軟體告訴我的，而我太太喜愛的影星彭于晏的體脂率號稱曾低至3%。
數字量化了沮喪感。聽說我要立志減肥，一個朋友露出數據主義者的嚴苛。他指揮我買手環、智能體重計及下載一些運動健身的應用。
這些終端告訴我很多身體的秘密——例如我坐地鐵上下班一天要走6300步，打車的話就只能走3500步了；我的心率有時候每分鐘72次，有時候又96次；我的睡眠不太好，每天深睡時間只有2小時；我決定去跑步，又遭到了計步器的嘲笑，我20分鐘跑不到3000米，和大長腿走快點差不多……
要知道，我17年前可是學院的800米冠軍，這些數字著實讓我不知所措。但演算法知道。它們分析我的身體狀況，計算我消耗的卡路里，推薦食譜和運動任務。
演算法研究了我，那我的數據會去哪裡呢？我的朋友Eric是波士頓一家可穿戴設備公司的首席工程師，他向我解釋：被測量者的數據會變成數字或模擬信號，傳輸回各個設備供應商的資料庫中。各種開源演算法日夜辛勞，像礦工從砂岩中淘洗黃金一樣——某個地區肥胖人數上升或失眠症爆發，無論對商業公司還是衛生系統都是非常寶貴的情報。
Pixabay.com
工程師們告訴我，數據處理的演算法有很多，排序是最基礎也是最重要的一環。
如果把演算法比作一個拳師，排序問題就是他打出的第一拳。計算機演算法史上最具標誌性的排序演算法——冒泡演算法誕生於1963年。兩名加州的計算機科學家發明了它，並賦予簡單優美的運行邏輯——把待排序數列從頭開始依次兩兩對比，按大小調至正確順序，然後不斷重複上述流程直至沒有數字交換為止。
「非常優美，我很欣賞。」帕特里克·普羅瑟說。然而，冒泡排序本質上是一種暴力求解，當數據量大時就吃力了。科學家們繼續發明新的排序演算法。「博弈論之父」約翰·馮·諾依曼也來小試牛刀，他發明了歸併排序。
與冒泡演算法相比，歸併法多了「分治」思維，先讓不同子序列有序，再將子序列合併排序，最終得到完全有序，極大提高了運算效率。
「研究演算法的美妙之處，是追求最大限度的優雅和高效。」英國格拉斯哥大學計算機高級講師大衛·曼羅夫說。如今，僅排序演算法領域，已經衍生出20多種演算法。
求婚演算法
還是說回我的體重吧。我變成這樣咎由自取，手機里的美食搜索軟體和外賣應用都被我置頂。有兩類基礎演算法在忠誠地為我服務：排序演算法和路徑選擇演算法。
正常的人機配合過程應該是這樣的：我發出指令——搜索離我最近的咖啡廳。排序演算法先把城市所有咖啡廳找出來，按距離排序，給出推薦結果。我接受後，路徑選擇演算法就會計算出最優交通方案，最後我跟著箭頭走就是了。
如果這件事發生在北京這樣的特大城市，計算過程就會變得異常漫長，因為數據量太大了。人類不會愚蠢到讓自己餓死在搜索過程中，科學家們又創造「預處理」來優化演算法——把城市分成若干「格子」，根據用戶的位置落在哪個格子內，只對其範圍內的咖啡廳按距離排序即可。
上述的「預處理」就是人腦對演算法的優化。在演算法的發展問題上，存在兩種認知：一種認為應優先發展硬體；一種則傾向優化演算法。前Google全球副總裁李開復更支持後者。在一篇文章中，他寫到：「
（相比計算能力）
需要處理的信息量更是呈指數級的增長……越來越多的挑戰需要靠卓越的演算法來解決。」2012年諾貝爾經濟學獎就是因為一個卓越的演算法——「蓋爾-沙普利演算法」
[6]
，授予一位數學家。當時，兩位發明者中，蓋爾已故，沙普利也89歲了。他和中國有緣，年輕時參加美軍到中國抗日。「我自認為是個數學家，卻拿了個經濟學的獎。」獲獎後，沙普利這樣說。
這個收穫最高殊榮的演算法，本質是解決匹配問題，但起源有些喜感。1960年，兩位發明者就婚姻問題有了一次爭論——擇偶意願存在交疊的幾對男女，能否最後匹配成穩定的婚姻？
他們聊到最後，覺得可行，而且還可以有更多應用。1962年，他們合寫了一篇論文《高校招生與婚姻穩定性》，「蓋爾-沙普利演算法」問世。
該演算法的關鍵在於「延遲接受」——學生對合意的學校要約不要立即接受
（不合意的則拒絕）
，而是「抓住」。等要約被拒絕後，學校才可以向另一名學生髮出新的要約。整個程序一直持續到沒有學校再希望發出新的要約為止。學生們從各自「抓住」的要約中選擇，保證最終結果的相對最優。「蓋爾-沙普利演算法」也成為博弈論早期的重要分支，但人們更願意叫它為「求婚演算法」。
演算法的局限
演算法已經走了多遠？這個問題沒有人比Google更合適回答了。
19年前，斯坦福計算機研究生拉里·佩奇和謝爾蓋·布林住進加州一個車庫。他們打算設計一個搜索引擎，幫助人們更有效地搜尋萬維網信息。他們一無所有，只有在宿舍發明的PageRank
（網頁排名演算法）
。當時市面上已有的搜索引擎非常簡單粗暴，僅以網頁點擊數排名。兩位創始人把他們對搜索的理解寫進PageRank，主要基於兩個假設：一是數量假設，一個頁面接收到其他網頁指向的入鏈數量越多，這個頁面就越重要；再是質量假設，指向頁面的其他網頁的入鏈質量越高，頁面越重要。
PageRank開創性地提出「鏈接價值」概念，讓搜索引擎從單純的「計數」飛躍到對網頁重要性的評價。PageRank成為Google創業期最核心的演算法，不斷優化沿用至今。
如今，Google帝國的技術已無比強大。GFS、MapReduce、BigTable、Caffeine、Pregel、Dremel
[7]
等技術，已成為全球雲計算及大數據技術的基石。值得一提的是MapReduce演算法。Google每天能經受住55億次搜索的衝擊，它勞苦功高。
MapReduce演算法原理既精妙又質樸，通過把計算量分配給不同的計算機群，並行分散式自動執行。簡單地說，就是將複雜任務分解「外包」給全球大大小小的計算機，各自運算，最後匯總解決。「藉助該演算法，Google幾乎能無限地增加計算量。」李開複評價。
如今，演算法已抵達機器學習和人工智慧的前沿。Google的人工智慧程序「AlphaGo」橫掃中韓圍棋高手。中國的柯潔也在其中，承認對方是「圍棋上帝」。
那演算法已經無可匹敵了嗎？
「我認為人們並不真正了解演算法的局限。」牛津大學計算機教授萊斯利·安·高柏說，「有的問題根本無法通過有效演算法解決。」
最著名的莫過於「旅行推銷員問題」了。即一個推銷員要拜訪N個城市，每個城市只經過一次，最終回到出發地，要用演算法快速選出最短路線。
這個問題難住了全球科學家。計算量太大了，當城市達到10個時，可能路線就已超過180萬條，每增加1個城市，可能路線還會幾何級數增長。暴力窮舉的話，時間會長得不可接受。
2000年，美國克雷數學研究所懸賞100萬美元徵求演算法
[8]
。如今，這筆獎金已經躺了17年了。
在沿著演算法進化的河流回覽之後，下一篇文章我將帶你們看看演算法更近在眼前的影響——「過濾泡泡」。無處不在的推薦演算法讓我們更高效獲取信息的同時，也讓我們變得更狹隘。我將與大家一起探尋：是什麼讓開放和封閉成為同一個硬幣的兩面？
關於作者
葉偉民，媒體人。畢業於蘭州大學核物理專業。曾任ZAKER總編輯，南方周末特稿編輯、記者。現從事互聯網，同時是多家平台的簽約作者和寫作導師。
注釋：
[1] 高斯絕妙定理：表達高斯曲率的一個定理，是高斯方程的直接推論。它的發現是微分幾何學發展史上的一個里程碑。
[2] 高斯函數：被廣泛運用於統計學以描述正態分布，應用範圍涵蓋自然科學、社會科學、數學以及工程學等領域。
[3] 布爾邏輯：19世紀中葉喬治·布爾首次定義了邏輯的代數系統。布爾邏輯在電子學、計算機硬體和軟體中有廣泛應用。
[4] 概率論：研究隨機現象數量規律的數學分支，廣泛應用於自然科學、經濟學、醫學、金融保險甚至人文科學中。
[5] 圖論：通過圖形來描述某些事物之間的某種特定關係，是「拓撲學」的先聲。
[6] 蓋爾-沙普利演算法：也被稱為「延遲接受演算法」，是蓋爾和沙普利為了尋找一個穩定匹配而設計出的市場機制。兩位發明者都是數學家和經濟學家，戴維·蓋爾是加州大學伯克利分校教授，羅伊德·沙普利是加州大學洛杉磯分校教授。
[7] GFS：Google文件系統，MapReduce：超大集群的簡單數據處理，BigTable：結構化數據的分散式存儲系統，Caffeine：新索引系統，Pregel：圖演算法引擎，Dremel：「互動式」數據分析系統。
[8] 克雷數學研究所在2000年宣布，為世界七大數學難題各懸賞100萬美元獎金。它們是：NP完全問題、霍奇猜想、龐加萊猜想、黎曼假設、楊-米爾斯存在性和質量缺口、納衛爾-斯托可方程、BSD猜想。「旅行推銷員問題」是最經典的「NP完全問題」之一。
譯名對照表：
喬治·布爾 George Boole
克勞德·香農 Claude Shannon
帕特里克·普羅瑟 Patrick Prosser
冒泡演算法 bubble sort
歸併排序 merge sort
約翰·馮·諾依曼 John von Neumann
大衛·曼羅夫 David Manlove
拉里·佩奇 Lawrence Page
謝爾蓋·布林 Sergey Brin
萊斯利·安·高柏 Leslie Ann Goldberg
戴維·蓋爾 David Gale
羅伊德·沙普利 Lloyd Shapley
點擊圖片，查看「科學新聞實驗室」過往文章
?
反綁雙手的慘死者｜罪案遺蹤
?
超越AI的孩子 | 36個月
?
「幽默」到底是什麼？| 事關智慧和笑
?
誰是新的「華爾街之狼」| 演算法密碼
?
我知道「綁架者」是你 | 罪案遺蹤
製版編輯：艾略特
丨
本頁刊發內容未經書面許可禁止轉載及使用
公眾號、報刊等轉載請聯繫授權
copyright@zhishifenzi.com
歡迎轉發至朋友圈
▼點擊查看相關文章
遺傳資源爭議|天使粒子爭議
|大望遠鏡爭議
施揚
|潘卓華|楊璐菡
|劉若川
|
張鋒
|薛其坤
張毅|王曉東
|張啟發
|崔維成
|
潘建偉|
李佩
盧煜明
|
王小凡|吳文俊
|袁鈞瑛
|
張純如
知識分子
為更好的智趣生活
ID：
The-Intellectual
投稿：
zizaifenxiang@163.com
授權：
copyright@zhishifenzi.com
長按二維碼，關注知識分子
購買課程
請點擊下方「閱讀原文」
▼▼▼
點擊「閱讀原文」，了解課程詳情，立享限時特惠！
※9成腫瘤患者死於腫瘤轉移，治療策略該更新了 | 前沿
※論「發表英文期刊論文就是失掉文化自信了嗎？」
※跨越科技評價的「馬拉河」
※學人說：公園相親角：我在海淀，你在朝陽，太遠了你們不合適
※科學第一課：魯白：為什麼要學科學
TAG:知識分子 |
※為什麼我們如此關注可解釋的演算法？為黑盒演算法辯護
※糟了！演算法說它懂你
※演算法密碼：未來我們能怎樣永生？
※未來我們能怎樣永生？ | 演算法密碼
※你真正懂搜索引擎演算法嗎？
※馬云：婚姻最好的演算法是「算了吧」
※手機拍照演算法好 真的就可以為所欲為？
※你應該了解的AI演算法，樹搜索和演化演算法
※演算法與數據結構？看這篇就夠了
※馬雲當證婚人火了：婚姻最好的演算法就是「算了吧」！
※我們創造了演算法，還是演算法創造了我們？
※數字時代，你被演算法「綁架」了嗎？
※「婚姻最好的演算法是什麼？」
※證婚人馬云：婚姻最好的演算法是「算了吧」
※事情污，但演算法不污
※神秘的印度「速演算法」問世，孩子弄懂了，算術水平堪比計算機！
※當演算法認為你想死，這時怎麼辦？
※把人做決策換成演算法決策就公平了嗎？不見得
※婚姻里最好演算法是什麼？
※AI 競賽帶來的人才短缺問題，什麼演算法都解決不了