機器學習算法發(fā)展歷程詳解

在科學技術剛剛萌芽的時候，科學家Blaise Pascal和Von Leibniz就想到了有朝一日能夠實現人工智能。即讓機器擁有像人一樣的智能。

機器學習是AI中一條重要的發(fā)展線，在工業(yè)界和學術界都異?；鸨?。企業(yè)、大學都在投入大量的資源來做機器學習方面的研究。最近，機器學習在很多任務上都有了重大的進步，達到或者超越了人類的水平（例如，交通標志的識別[1]，ML達到了98.98%，已超越了人類）。圖1中展示了ML的一個粗略的時間線，標記了很多里程碑。熟悉該圖，閱讀下文會覺得順暢很多。

圖 1 機器學習時間線

推動機器學習流行化的第一個舵手是Hebb，1949年他提出了神經心理學學習范式——Hebbian學習理論。經過簡單的擴展，該理論就開始研究遞歸神經網絡的節(jié)點之間的相關度，它記錄下網絡上的共性然后像記憶一樣工作，正式的表達是這樣：

假設反射活動的持久性或重復性可以誘導細胞發(fā)生變化，以適應這種活動…當神經元細胞A距離神經元細胞B足夠近時，它就可以持續(xù)重復的激活B，那么這兩個細胞之一或者全部就會發(fā)生一些代謝過程或生長變化來提高效率[1]。

1952年，IBM的Arthur Samuel寫出了西洋棋程序，該程序可以通過棋盤狀態(tài)學習一個隱式的模型來為下一步給出較好的走法。Samuel和程序對戰(zhàn)多局后，覺得這個程序經過一定時間的學習后可以達到很高的水平。

用這個程序，Samual駁倒了機器不能像人類那樣可以學習顯式代碼之上的模式。他定義并解釋了一個新詞——機器學習。

1957年，Rosenblatt的感知器算法是第二個有著神經系統(tǒng)科學背景的機器學習模型，它與今天的ML模型已經很像了。在當時，感知器的出現引起了不小的轟動，因為它比Hebbian的想法更容易實現。Rosenblatt用下面的話向大家闡釋感知器算法：

感知器算法的作用是，在不用深入理解只對一些特定生物有機體有效的未知條件的前提下，說明了通用智能系統(tǒng)一些基礎特點[2]。

3年之后，Widrow [4] 因發(fā)明Delta學習規(guī)則而載入ML史冊，該規(guī)則馬上就很好的應用到了感知器的訓練中，對，沒錯，就是現在常見的最小二乘問題。感知器和Delta學習規(guī)則的聯姻著實構造了一個極好的線性分類器。但是，根據后浪拍死前浪的歷史規(guī)律，感知器的熱度在1969被Minskey[3]一盆冷水潑滅了。他提出了著名的XOR問題，論證了感知器在類似XOR問題的線性不可分數據的無力。對神經網絡（NN）社區(qū)來說，形成了幾乎當時看來幾乎不可逾越的鴻溝，史稱“明斯基之印”。然而無論如何，在10年的19世紀80年代，NN學者們還是打破了這個緊箍咒。

圖 2 XOR問題-線性不可分數據示例

被封印后，ML的發(fā)展幾乎停滯，盡管BP的思想在70年代就被Linnainmaa [5] 以“自動微分的翻轉模式”被提出來，但直到1981年才被Werbos [6]應用到多層感知器(MLP)中，直到現在仍是神經網絡架構的關鍵組成部分。多層感知器和BP算法的出現，促成了第二次神經網絡大發(fā)展，1985-1986年NN研究者們成功的實現了實用的BP算法來訓練MLP。（Rumelhart, Hinton, Williams [7]- Hetch, Nielsen[8]）

圖 3 來自Hetch和Nielsen

花開并蒂，各表一枝。另一個同樣很著名的ML算法在1986年被J. R. Quinlan[9]提出，即決策樹算法，具體來說是ID3算法。這是機器學習的另一條主流中一個燈塔式的成就。ID3以其簡單的規(guī)則和明確的推理，解決了很多現實世界的問題，實際上，它就是以一個實用軟件的姿態(tài)出現的，相對于黑箱子般的NN算法。

ID3之后，很多其他的算法或改進如雨后春筍般的出現，例如ID4，回歸樹，CART等等)。直到現在，決策樹仍然是ML界中的熱點。

圖 4 一個簡單的決策樹

接下來就是ML領域最重要的一個突破——支持向量機（SVM）。SVM由大師Vapnik and Cortes[10] 在1995年提出，它有很強的理論論證和實證結果。自此之后，ML社區(qū)就楚河漢界劃分為NN和SVM兩派。2000年左右，隨著核方法的提出，SVM大占上風，在很多領域上都超過了NN模型。除此之外，SVM還發(fā)展了一系列的針對NN模型的基礎理論，包括凸優(yōu)化、泛化間隔理論和核方法?？梢哉f，在這個時段，SVM的發(fā)展無論是理論還是實踐都占盡天時地利，因而發(fā)展速度極快。

圖 5 From Vapnik and Cortes [10]