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

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

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

?

圖 1 機器學習時間線

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

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

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

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

機器學習是給計算機一種不用顯式編程就能獲得能力的領域。

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

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

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

?

圖 2 XOR問題-線性不可分數(shù)據(jù)示例

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

?

圖 3 來自Hetch和Nielsen

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

ID3之后，很多其他的算法或改進如雨后春筍般的出現(xiàn)，例如ID4，回歸樹，CART等等)。直到現(xiàn)在，決策樹仍然是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]

不僅在外部遭到了巨大的挑戰(zhàn)，NN內部也發(fā)生了問題。1991年的Hochreiter[40]和2001年的Hochreiter[11]的工作，都表明在使用BP算法時，NN單元飽和之后會發(fā)生梯度損失。簡單來說，訓練NN模型時，超過一定的迭代次數(shù)后，再迭代NN模型就很容易過擬合。

再往前一點點，另一個堅實的ML模型AdaBoost在1997被Freund和Schapire提出，該算法最大的特點在于組合弱分類器形成強分類器。這個成果為它的作者贏得了Godel獎。Adaboost通過給那些難的樣例更高的權重來對那些容易訓練的分類器進行訓練。該模型在臉部識別和檢測方面應用的很廣。它還是PAC（概率近似正確理論）的一種實現(xiàn)。通常來說，所謂的弱分類器都被Adaboost用來當樹樁——即單個的決策樹節(jié)點。他們這樣來描述Adaboost：

作為一個良好的在線預測模型的抽象擴展，Adaboost可以被解釋為一個通用的決策理論設置…[11]

另外一個可以將多個決策樹組合起來的模型在2001年被Breiman[12]提出。該模型被稱為隨機森林(RF)，因為它的每個組成節(jié)點都是隨機的選擇一組示例和一組特征。RF也擁有理論上和實驗上的抗過擬合的證據(jù)。甚至有些數(shù)據(jù)Adaboost都不能很好的克服過擬合和離群點的時候，RF都能有很好的魯棒性。RF在很多其他不同領域比如Kaggle比賽上都有很成功的表現(xiàn)。

隨機森林是一個樹預測器的組合體，每棵樹都取決于一個獨立同分布的隨機向量。因而整個森林的泛化誤差隨著森林數(shù)目的增多而收斂[12]。

時間終于走到了當下，一個新的NN領域——深度學習出現(xiàn)了。在這個階段，NN模型可以擁有多層。3層的NN模型在2005年被Hinton,LeCun, Bengio, Andrew Ng等諸多大師一一實現(xiàn)。下面列舉了一些深度學習上的重要概念：

GPU programming

Convolutional NNs [18][20][40]

Deconvolutional Networks [21]

Optimization algorithms

Stochastic Gradient Descent [19][22]

BFGS and L-BFGS [23]

Conjugate Gradient Descent [24]

Backpropagation [40][19]

Rectifier Units

Sparsity [15][16]

Dropout Nets [26]

Maxout Nets [25]

Unsupervised NN models [14]

Deep Belief Networks [13]

Stacked Auto-Encoders [16][39]

Denoising NN models [17]

將上面列舉的這些技術和想法綜合到一起，NN模型迎來了又一個春天，在物體識別、語音識別、自然語言處理等方面，均擊敗之前的最高水平的技術。但重要的事，這并不意味著其他ML流派的終結，即使現(xiàn)在深度學習的成功故事還在一個接一個的上演，仍然有著參數(shù)眾多、訓練花費巨大的缺陷。而且，SVM由于其簡單性仍然被廣泛使用。

在結束之前，我們再介紹一個相對年輕的ML趨勢，隨著www和社會媒體的發(fā)展，大數(shù)據(jù)出現(xiàn)且影響了很多ML的研究。因為大數(shù)據(jù)中的問題數(shù)據(jù)量都極大，很多強大的ML算法在機器性能的限制下都變得有些無用（對大公司來說自然不是這樣）。因此，研究人員提出了一套簡單模型——dubbed Bandit Algorithms[27-38]，這些算法都是在線學習算法，都能適應大規(guī)模問題。

這只是一個簡單的ML歷史的介紹，若有問題，歡迎指出。