智能時代的算法發展

我們正在經歷一場智能革命，而這場智能革命建立在算法的基礎上。無論是智慧城市、智能製造、智慧醫療等宏大願景，還是自動駕駛、智能機器、虛擬現實等前沿應用，抑或是智能購物、智慧出行、智能娛樂等生活日常，“智能”的實現都離不開算法。可以說，我們生活在一個算法無所不在的時代。

古代算法思想及其發展

“算法”一詞的英文“algorithm”源於波斯數學家花拉子密（Al Khwarizmi）名字的拉丁化。在數學和計算機科學中，算法是有明確定義、有限步驟且計算機可執行的，通常用於計算、數據處理和自動推理的一組指令序列。算法作爲一個複雜的體系，是數學、邏輯學和計算機科學的集合。儘管第一臺計算機誕生距今不過70多年，但是算法思想源遠流長。

●算法思想的數學源頭

數學起源於人類早期的生產活動對計數、天文、度量甚至貿易的需要。這些需要可以簡單概括爲數學對結構、空間和時間的研究。數學對結構的研究發展出算術和代數，對空間的研究發展出幾何，對時間的研究發展出函數。人類關於數字和算術的概念從史前時代就已存在，如蘇美爾人用黏土保留數字信息和我國古人用結繩計數都是人類對計算的早期實踐。公元前7世紀的古希臘數學家及天文學家泰勒斯（Thales of Miletus）被認爲是最早提出幾何定理的人。公元前4世紀，古希臘數學家歐幾里得（Euclid）所著的《幾何原本》是歷史上第一部系統化的數學理論典籍，而求最大公約數的歐幾里得算法是人類歷史上第一個算法。12世紀至13世紀，阿拉伯數學中的代數思想，尤其是數字“零”的概念隨着十字軍東征傳入歐洲。花拉子密所著的《代數學》是第一本解決一次方程及一元二次方程的系統著作，他也因此被稱爲代數的開創者，他的著作《印度數字計算》在12世紀將十進制和算法思想傳入歐洲。函數的概念最早出現在蘇格蘭數學家及天文學家格雷戈裡（James Gregory）發表於1667年的論文《論圓和雙曲線的求積》中。1673年，德國數學家萊布尼茨（Gottfried Wilhelm Leibniz）在其手稿裡使用了“函數”這一概念，後來又引進“常量”“變量”和“參變量”的概念。函數概念的引入使人們可以從數量上描述運動，伽利略的落體運動定律、牛頓的萬有引力定律和愛因斯坦的質能轉換公式等都是用函數概念表達的。

中國同樣有悠久的數學傳統。數學在中國歷史上稱爲“算學”，起源於仰韶文化，距今已有5 000多年的歷史。在距今3 000年前的周朝，“數”是六藝之一。在春秋時代，十進位制的籌算已經普及。算學的文獻記載最早見於《周髀算經》。《周髀算經》是中國流傳至今最早的天文學和數學著作，其中記載了周公曾問商高如何測量天地高遠，這是勾股定理最早的文字記錄，比古希臘數學家畢達哥拉斯（Pythagoras）的證明早了500多年。中國古代數學把利用算籌進行計算的算法稱爲“術”，中國古代數學的成就多是用術來表述的，如成書於東漢前期的《九章算術》中的方程術、正負術、今有術，三國時期劉徽的割圓術，南宋數學家秦九韶《數術九章》中的大衍求一術等。尤其是大衍求一術，已經是相當複雜的算法，具備了現代算法的基本特徵。

●算法思想的邏輯學脈絡

邏輯學是一門關於推理或論證的學問，主要研究推理的有效性和正確性問題。邏輯學分別發源於古希臘、中國古代和古印度，其中古希臘邏輯最終發展成當前的國際主流邏輯。古希臘邏輯學大約誕生於公元前350年，古希臘哲學家亞里士多德（Aristotle）開創了以“三段論”爲核心的詞項邏輯，這是人類歷史上第一個演繹邏輯體系，他關於邏輯的6篇論文被追隨者彙編成《工具論》，對西方思想史產生了深遠影響。公元前3世紀早期，古希臘哲學家芝諾（Zeno of Citium）創立斯多葛學派，發展了命題邏輯，但是與亞里士多德邏輯的主導地位相比影響較小。

1543年，波蘭數學家及天文學家哥白尼（Nicolas Copernicus）的《天體運行論》和比利時醫生及解剖學家維薩留斯（Andreas Vesalius）的《人體結構》在同一年出版，標誌着現代科學的誕生。自然科學需要根據個別現象概括出一般性結論，以解釋現象間的因果關係，但亞里士多德邏輯無法處理自然科學研究中的因果問題。1620年，英國科學家及哲學家培根（Francis Bacon）提出以觀察和實驗爲基礎的科學認識理論，開創了歸納邏輯。1843年，英國哲學家穆勒（John S. Mill）在培根歸納法基礎上提出判斷因果聯繫的5種邏輯方法。歸納邏輯在17世紀歐洲科學革命中起到了不可估量的作用。1666年，萊布尼茨在《論組合術》中闡述了以符號運算表述推理過程的思想，開創了符號邏輯和數理邏輯的研究。符號邏輯是現代邏輯的基礎，包括命題演算和謂詞演算；數理邏輯是符號邏輯在數學中的應用。1847年，英國數學家布爾（George Boole）提出的布爾邏輯就是一個命題演算系統。1928年，德國數學家希爾伯特（David Hilbert）和阿克曼（Wilhelm Ackermann）在《理論邏輯原理》中提出了現在人們常用的命題演算系統。1879年，德國邏輯學家費雷格通過引入量詞，將命題演算拓展成了謂詞演算系統，最終完成了符號邏輯體系的構建。

人工智能時代的算法

1936年，英國數學家及計算機科學家圖靈（Alan Turing）提出被稱爲“圖靈機”的計算數學模型，其構想是將人的計算行爲抽象爲數學邏輯機器。圖靈機是現代通用計算機的理論基礎，如今所有通用計算機都是圖靈機的一種實現。1943年，美國數學家香農（Claude E. Shannon）和圖靈在貝爾實驗室探討了“人工智能”的可能性。1950年，圖靈在一篇論文中預言了創造出具有真正智能的機器的可能性，並提出了判斷機器是否具有智能的思想實驗——圖靈測試。1956年，明斯基（Marvin Minsky）、麥卡錫（John McCarthy）、香農等13位科學家在美國達特茅斯學院召開會議，標誌着人工智能學科的誕生，算法也由此進入人工智能時代。

●機器學習

機器學習是人工智能和計算機科學的重要分支，是基於樣本數據構建模型並利用模型在沒有明確編程的情況下做出預測或決策的一類算法。監督學習、無監督和強化學習是機器學習的基本方法。

監督學習使用人工標記的訓練樣本將已有知識應用於新數據，以預測未來事件。1936年，英國數學家費希爾（Ronald Fisher）提出的線性判別分析是最早的監督學習算法。20世紀50年代，基於貝葉斯決策理論的貝葉斯分類器開始被用於分類問題。1958年，美國認知心理學家羅森布拉特（Frank Rosenblatt）發明感知器算法，它被認爲是人工神經網絡的前身。1967年，美國信息理論家科弗（Thomas Cover）和計算機科學家哈特（Peter Hart）提出基於模板匹配思想的K-最近鄰算法。20世紀八九十年代，決策樹和神經網絡算法開始興起。1995年，兩種重要算法——支持向量機和AdaBoost誕生。支持向量機是處理線性分類和非線性分類問題的主要方法，而AdaBoost可以將許多其他類型的算法集成起來使用以達到最佳性能。1995年至1997年，德國計算機科學家霍赫賴特（Sepp Hochreiter）和施米德胡貝（Juergen Schmidhuber）提出長短期記憶算法，可以部分處理梯度消失問題。2013年，長短期記憶算法與深度循環神經網絡結合成功應用於語音識別。2001年，美國統計學家布賴曼（Leo Breiman）提出優化的隨機森林算法。隨機森林是一個用隨機方式建立的包含多個決策樹的分類器，對多數據集和高維數據的處理有很大優勢。監督學習的常見應用場景包括評估信用分數、手寫識別、語音識別、信息檢索、財務分析、偵測垃圾郵件等。

無監督學習是基於統計的學習方法，通過對未知數據進行分析來發現數據隱藏特徵。無監督學習包括聚類和數據降維兩種主要算法類型。1963年，美國空軍研究員沃德（Joe Ward）根據方差分析提出了最早的聚類算法——層次聚類算法。1967年，美國數學家麥奎因（James MacQueen）提出的k均值算法是聚類算法中知名度最高的算法，在此基礎上出現了大量的改進算法和成功應用。1977年，美國統計學家登普斯特（Arthur Dempster）提出最大期望算法，被用於聚類問題和極大似然估計問題。1995年，美國辛辛那提大學教授程（Yizong Cheng）提出可用於計算機視覺和圖像處理的均值漂移算法。2000年，美國計算機科學家史建波（Jianbo Shi）推廣了譜聚類算法，可以將聚類問題轉化爲圖的最優切割問題。最早的數據降維算法是1901年英國數學家及生物統計學家皮爾遜（Karl Pearson）提出的主成分分析法，比第一臺真正的計算機的誕生早了40多年。然而，在此後的近100年裡數據降維算法在機器學習領域沒有出現重量級成果。1998年，德國計算機科學家舍爾科普夫（Bernhard Schölkopf）提出基於核方法的核主成分分析算法，可以實現高維數據的非線性降維。2000年以後，流形學習開始成爲熱點，它的主要思想是將高維的數據映射到低維，使該低維的數據能夠反映原高維數據的某些本質結構特徵。基於流行學習出現了局部線性嵌入、拉普拉斯特徵映射、局部保持投影等距映射等新算法。2008年出現的t-分佈式隨機鄰居嵌入算法是降維算法中最年輕的成員。無監督學習的常見應用場景包括反洗錢、客戶分組、廣告推薦、銷售趨勢預測等。

強化學習源於心理學中的行爲主義理論，強調智能體在獎勵或懲罰的環境刺激下如何做出能取得最大化預期利益的行動，也就是說，讓智能體在環境中自我學習。早在1954年，明斯基就提出了“強化學習”的概念和術語。1965年，美國普渡大學教授傅京孫（King-Sun Fu）在研究控制論時提出“智能控制”的概念，明確了“試錯”作爲強化學習的核心機制。1957年，美國應用數學家貝爾曼（Richard Bellman）爲了求解最優控制問題的馬爾可夫決策過程提出了動態規劃法，這一方法採用了類似強化學習的試錯迭代求解機制。最早的強化學習算法是1988年加拿大計算機科學家薩頓（Richard Sutton）提出的時序差分學習，它不需要獲知環境的全部信息就可以直接從實際經驗來獲取信息，同時不需要完整的收益反饋信息就可以實時更新決策。1989年，英國計算機科學家沃特金斯（Chris Watkins）提出的Q學習進一步拓展了強化學習的應用，使得強化學習不再依賴於問題模型，Q學習也因此成爲最廣泛使用的強化學習方法之一。此後近20年的時間裡，強化學習被監督學習的光芒所遮掩而發展緩慢。2010年以後，強化學習結合神經網絡發展出深度強化學習算法，強化學習由此迎來大發展時期。2013年，谷歌公司旗下的深度思維公司（DeepMind）發表了利用強化學習玩雅達利（Atari）遊戲的論文。2015年，深度思維公司開發的AlphaGo程序擊敗了圍棋二段選手樊麾，成爲第一個無須讓子即可以擊敗圍棋職業棋手的計算機圍棋程序。2016年，AlphaGo在一場五番棋比賽中以4:1擊敗頂尖圍棋職業棋手李世石。強化學習的常見應用場景包括無人駕駛、機器翻譯、醫療保健、新聞定製、廣告營銷、機器人控制等。

●深度學習

深度學習是機器學習的一個分支，是一種模擬大腦神經網絡結構對數據進行表徵學習的方法。深度學習源於對人腦工作機制的研究。獲得1981年諾貝爾生理學或醫學獎的美國神經生理學家休伯爾（David Hubel）和維澤爾（Torsten Wiesel）發現人的視覺系統的信息處理是分級的，人類對高層特徵的感知基於低層特徵的組合。例如，對人臉的識別經過瞳孔攝入像素（形狀判斷）抽象出人臉概念——識別爲人臉的過程，從低層到高層的特徵表達越來越抽象和概念化。這一發現意味着大腦是一個深度架構，認知過程也是深度的，而深度學習恰恰就是通過組合低層特徵形成更加抽象的高層特徵。深度學習的發展可以分爲感知器、神經網絡和深度學習等3個階段。

1943年，美國心理學家麥卡洛克（Warren S. McCulloch）和數理邏輯學家皮茨（Walter Pitts）提出人工神經網絡的概念，並構建了人工神經元的數學模型，即MCP模型，從而開創了人工神經網絡研究的時代。1949年，加拿大心理學家赫布（Donald Hebb）描述了突觸可塑性的基本原理，從神經科學理論上解釋了學習過程中大腦神經細胞所發生的變化。赫布理論是人工神經網絡的生物學基礎。1958年，羅森布拉特在康奈爾航空實驗室發明感知器算法，這是世界上第一個具有完整算法描述的神經網絡學習算法。感知器算法是簡單配置的單層神經網絡，可以區分三角形等基本形狀。但是，受限於計算機硬件，感知器算法在當時無法被廣泛應用。1969年，明斯基和佩珀特（Seymour Papert）證明感知器不能解決簡單的異或（XOR）等線性不可分問題，感知器研究隨之在20世紀70年代陷入低谷。

1959年，休伯爾和維澤爾在研究貓的視覺神經系統時發現，在大腦的初級視覺皮層中存在兩種細胞：簡單細胞和複雜細胞，其中，簡單細胞感知光照信息，複雜細胞感知運動信息。受此啓發，1980年日本計算機科學家福島邦彥（Kunihiko Fukushima）提出了一個網絡模型——“神經認知機”（Neocognitron）。這種網絡分成多層，每層由一種神經元組成。在網絡內部，兩種神經元交替出現，分別用來提取圖形信息和組合圖形信息。這兩種神經元后來分別演化成卷積層（Convolution Layer）和提取層（Pooling Layer）。然而，這個網絡的神經元都是人工設計的而不能根據計算結果自動調整，所以只能識別少量簡單數字而不具備學習能力。

1982年，美國物理學家霍普菲爾德（John J. Hopfield）基於統計物理提出了有少量記憶能力的霍普菲爾德神經網絡模型，開創性地論證了按照赫布法則設計權重的神經網絡穩定性問題。同年，芬蘭計算機科學家科霍寧（Teuvo Kohonen）通過模擬大腦神經元的信號處理機制，提出了自組織映射網絡，被用於數據分析和數據探索，其第一個應用領域是語音分析。科霍寧的關鍵發明是引入了一個系統模型，包含一個實現贏家通吃功能的競爭性神經網絡和一個實現可塑性控制的子系統。1987年，美國科學家格羅斯伯格（Stephen Grossberg）和卡彭特（Gail Carpenter）提出了自適應共振理論網絡，通過讓已知信息和未知信息發生“共振”，從已知信息推測未知信息來實現類比學習。然而，這些神經網絡存在學習效率不高、需要不斷優化設計、網絡記憶容量小等不足，實際應用範圍有限。

1986年，美國心理學家魯姆哈特（David Rumelhart）、計算機科學家威廉姆斯（Ronald Williams）和加拿大認知心理學家及計算機科學家欣頓（Geoffrey Hinton）共同提出反向傳播算法（BP算法）。BP算法通過梯度的鏈式法則使輸出結果和真實值之間的差異反饋到每一層的權重中，從而讓每一層函數都能像感知機那樣得到訓練。BP算法階段性解決了神經網絡自適應、自主學習的難題。1989年，貝爾實驗室的法國計算機科學家楊立昆（Yann LeCun）第一次成功實現了神經網絡的實踐應用。他將卷積神經網絡與BP算法結合，提出LeNet網絡。20世紀90年代，美國郵政署將LeNet網絡用於自動讀取信封上的郵政編碼。然而，基於BP算法的神經網絡僅能求解局部最優，而且這種情況隨着網絡層數的增加越來越嚴重，這一問題制約了神經網絡的發展。

2006年，欣頓提出深度學習算法，通過無監督學習和逐層預訓練的方式有效降低了訓練難度，從而解決了BP神經網絡難以達到全局最優的問題。2012年，欣頓的研究小組採用深度學習贏得了ImageNet圖像分類比賽的冠軍，準確率超出第二名10%以上，在計算機視覺領域產生極大震動，引發了深度學習的熱潮。2013年，《麻省理工科技評論》將深度學習列爲年度世界十大技術突破之首。如今，深度學習已經被廣泛用於搜索引擎、語音識別、自動機器翻譯、自然語言處理、自動駕駛、人臉識別等領域，是人工智能最熱門的研究方向之一。

量子時代算法的發展

根據摩爾定律，計算機芯片的性能每18個月翻1番。然而，隨着摩爾定律逼近極限，經典計算的算力增長即將遭遇瓶頸。量子計算是利用量子態的相干性、疊加性、糾纏性等量子力學特性進行信息運算、保存和處理操作的新型計算模式。量子計算可以突破經典計算機的算力極限，被認爲是未來30年最有可能改變世界的顛覆性技術之一。

●量子計算理論

1979年，美國阿貢國家實驗室物理學家貝尼奧夫（Paul Benioff）提出了第一個量子計算機模型。1980年，蘇聯數學家馬寧（Yuri Manin）在其著作《可計算與不可計算》中同樣闡述了量子計算的概念。1981年，貝尼奧夫和美國物理學家費恩曼（Richard Faynman）在麻省理工學院舉行的第一屆計算物理會議上就量子計算髮表演講。貝尼奧夫表示計算機可以在量子力學定律下運行，費恩曼表示使用經典計算機難以有效模擬量子系統的演化，並提出了量子計算機的基本模型。貝尼奧夫、馬寧和費曼奠定了量子計算的理論基礎。

1985年，英國牛津大學教授多伊奇（David Deutsch）首次提出了量子圖靈機模型，並設計了第一個量子算法Deustch算法。然而，Deustch算法沒有確定性，其成功的概率僅有50%。1992年，多伊奇和英國劍橋大學教授喬薩（Richard Jozsa）在早期Deustch算法基礎上提出了有確定性的Deutsch-Jozsa算法，並將其推廣到n個量子比特的Deutsch問題。Deutsch-Jozsa算法首次實現了對經典算法的指數級加速，奠定了量子算法的基本思想。然而，限於當時的理論和技術水平，此時量子算法還停留在紙面設想階段。

●量子計算核心算法

Shor算法、Grover算法和以HHL算法爲代表的對偶量子算法是量子計算的三大核心算法。1994年，貝爾實驗室的美國數學家肖爾（Peter Shor）基於量子傅里葉變換提出了針對整數分解問題的大數質因子分解算法（又稱爲Shor算法）。Shor算法從理論上展示了量子計算機能夠把質因數分解問題的求解從指數時間降到多項式時間，可用於破解目前通用的計算機加密方案——RSA加密算法。假如超級計算機破解一個2048位的RSA密鑰需要數十億年，那麼使用Shor算法的量子計算機僅需要幾分鐘。這意味着依賴RSA密鑰機制的銀行、網絡和電子商務系統在理論上不再安全。然而，Shor算法在量子計算機上的實驗實現一直是國際公認難題。2008年，中國科技大學教授潘建偉的團隊與英國牛津大學合作，首次在光量子計算機上實現了Shor量子分解算法，標誌着我國光學量子計算研究達到了國際領先水平。

1996年，貝爾實驗室的美國計算機科學家格羅弗（Lov K. Grover）基於量子黑盒加速工具提出了針對亂序數據庫的量子搜索算法（又稱爲Grover算法）。Grover算法從本質上解決了函數求逆的任務，使無序數據庫中“大海撈針”成爲可能，其在密碼學上的應用可以加速對稱密鑰算法的破解。然而，原始的Grover算法只能以一定概率輸出正確結果，在一些特殊情況下輸出錯誤結果的概率較大。2001年，清華大學教授龍魯桂利用相位匹配的技巧將Grover算法的成功概率提高到100%，即龍算法。

Shor算法和Grover算法提出之後，量子算法研究進展緩慢。2003年，肖爾發出著名的“肖爾之問”，即爲什麼難以發現更多的量子算法。肖爾對這一問題的解釋是，量子計算機的運行模式與經典計算機不同，以至於經典算法中的構造設計技巧和直覺在量子計算過程中不再成立。

2002年，龍魯桂提出酉算符線性疊加的對偶量子算法。酉算符是泛函分析中定義在希爾伯特空間上的有界線性算符，Shor算法和Grover算法都是通過酉算符對信息進行處理。由於酉算符只允許乘除運算，經典計算中的許多技巧不能用於量子計算。對偶量子算法通過引入輔助比特以實現非酉操作，這使酉算符的加減乘除四則運算成爲可能，從而解決了經典算法轉化爲量子算法的問題。2009年，美國麻省理工學院的哈羅（Aram W. Harrow）、哈希迪姆（Avinatan Hassidim）和勞埃德（Seth Lloyd）基於酉算符線性疊加提出可求解線性方程組的HHL算法。求解線性方程組是很多科學和工程問題的核心，HHL算法相對於經典計算有指數加速的效果，因此在機器學習、數據擬合等多種場景中展示出巨大優勢。

●量子人工智能算法

量子疊加和量子糾纏等量子力學特性使量子算法非常適於解決人工智能和機器學習研究中核心的最優化問題。所謂“最優化”是指在給定預期結果和約束條件的情況下，從一組可能選項中找到問題最優解的過程。最優化問題是應用數學和計算機科學領域的重要基礎研究之一，其理論與方法廣泛用於工業生產、工程設計與管理、交通運輸、經濟決策、市場管理等關乎國計民生的重要領域。1995年，美國計算機科學家卡克（Subhash Kak）首先提出量子神經計算的概念。同年，英國科學家米尼爾（Tamaryn Menneer）和納拉亞南（Ajit Narayanan）將量子信息學中的多體觀點應用到單層人工神經網絡，提出了量子衍生神經網絡，顯示出在處理分類問題上的有效性。2000年，韓國科學家韓國賢（Kuk-Hyun Han）等採用量子比特編碼染色體，提出了具有更強並行搜索能力的量子遺傳算法。2005年，日本科學家幸田典明（Noriaki Kouda）等將量子位引進神經元定義，提出了量子位神經網絡，仿真試驗表明該神經網絡具有良好的學習能力。2006年，谷歌眼鏡項目聯合創始人奈文（Hartmut Neven）在D-Wave量子計算機上開發了第一個結合了量子算法和機器學習的圖像識別系統。近年來，量子人工智能算法發展迅速，出現了量子卷積網絡、量子自然語言處理、量子生成模型等新型算法。以IBM、谷歌爲代表的科技企業紛紛加強了量子人工智能在新材料設計、藥物設計以及化學反應模擬等領域的算法研究。2017年至2020年，IBM、IonQ和谷歌公司先後利用量子計算模擬出氫化鈹、水分子和二氮烯分子，標誌着量子計算在模擬和發現小分子化合物上邁出重要一步。2021年1月，谷歌公司與德國醫藥企業勃林格殷格翰聯合成立量子實驗室，致力於實現對蛋白質、核酸、多糖等生物大分子的模擬，有望開啓在原子、分子層面理解生命和研發新藥的新模式。

算法是人工智能的基礎。當前，數據和算力已經不再是人工智能發展的主要瓶頸，人工智能的創新主要就是算法的創新。隨着人工智能在國家治理、經濟發展、科技創新、醫療保健、教育培訓，乃至日常生活的應用日益廣泛和深入，算法越來越重要。在這樣的背景下，只有不斷探索新的算法機制，發展新的算法應用，開發新的算法模型，發掘和培養算法人才，才能爲推動智能社會發展提供強勁動力。

作者：王楠、王國強，中國科協創新戰略研究院

本文轉載自微信公衆號張江評論，原載於《張江科技評論》2021年05期

產業 | 工業化 | 數字化 | 人才 | 創新創業 | 顛覆性技術 | 科技指標 | 科技政策 | 前沿技術 | 知識產權 | 智庫 |

獲取方法如下：

其他系列將陸續呈現，多多關注哦！

投稿郵箱：nais-research@cnais.org.cn