機器學習發展簡史

編者按：文章源自《Brief History of Machine Learning》，作者為土耳其初創公司 8bit.ai 的聯合創始人 Eren Golge。在這篇文章中，Golge 向大家粗略地展示了機器學習發展的時間軸。

機器學習的發展時間軸

一直以來，科學家們都希望跟隨布萊茲•帕斯卡（世界首台加法計算機的發明者）和戈特弗里德•萊布尼茨（將二進位應用於計算機）兩位數學家的步伐，建造一台像人類一樣聰明的智能機器。另外，一些作家也在自己的故事裡展開了他們對類人機器的幻想。比如，《綠野仙蹤》的作者 Frank Buam、《科學怪人》的作者 Mary Shelley 和《星球大戰》的導演 George Lucas，他們筆下的機器人幾乎和人類一模一樣，能在複雜環境中執行各式各樣的任務。

1642 年：Pascal 發明的手搖式計算機

而作為實現人工智慧的重要途徑之一，機器學習一直是該領域的研究熱點。不少公司及大學投入了大量資源及精力去提高他們的機器學習演算法。截至目前為止，人工智慧在某些領域中已經可以和人類「並駕齊驅」了（比如 2011 年 IJCNN 舉行的「德國交通標誌識別」比賽中，人工智慧以 98.98%準確率戰勝人類）。

在這裡，我想為大家粗略地介紹一下機器學習的發展歷程，指出一些具有「里程碑式」意義的節點，但不一定能齊全。此外，在這篇文章的每一個觀點前面，你都應該自動加上「據我所知」這四個字。

1949 年，Donald Hebb 提出的赫布理論——解釋了學習過程中大腦神經元所發生的變化，標誌著機器學習領域邁出的第一步。概括來講，赫布理論研究的是循環神經網路（RNN）中各節點之間的關聯性。而裡面提到的 RNN 具有把相似神經網路連接在一起的特徵，並起到類似於記憶的作用。Hebb 是如此描述赫布理論的：

我們可以假定，反射活動的持續與重複（或稱「痕迹」）會引起神經元穩定性的持久性提升……當神經元 A 的軸突與神經元 B 之間距離非常近，且 A 對 B 進行重複持續的刺激時，這兩個神經元或者它們的其中之一便會發生某些生長過程或代謝的變化，從而使得 A 對刺激 B 的效率得到提高。[1]

Arthur Samuel

到了 1952 年，IBM 的 Arthur Samuel（被譽為「機器學習之父」）設計了一款可以學習的西洋跳棋程序。它能通過觀察棋子的走位來構建新的模型，並用其提高自己的下棋技巧。Samuel 和這個程序進行多場對弈后發現，隨著時間的推移 程序的棋藝變得越來越好。

Samuel 用這個程序推翻了以往「機器無法超越人類，不能像人一樣寫代碼和學習」這一傳統認識。而他對「機器學習」的定義是：

不需要確定性編程就可以賦予機器某項技能的研究領域。

F. Rosenblatt

1957 年時，具備神經科學背景的 Rosenblatt 提出了第二個模型——感知器（Perceptron），它更接近於如今的機器學習模型。當時感知器的出現讓不少人為之興奮，因為它的可用性比赫布模型要高。Rosenblatt 是這樣介紹感知機的：

感知器可以在較簡單的結構中表現出智能系統的基本屬性，也就是說研究人員不需要再拘泥於具體生物神經網路特殊及未知的複雜結構中。[2]

而三年之後，Widrow[4] 則提出了差量學習規則，且隨即被應用到感知器模型中。差量學習規則又稱「最小平方」問題，它與感知器結合在一起時可以創建出更精準的線性分類器。不過 1969 年時，Minsky[3] 給予感知器重重一擊，他提出的異或問題揭露出感知器的本質缺陷——無法處理線性不可分問題。此後，神經網路研究陷入了長達十多年的停滯中。

異或問題

儘管 1970 年時，Linnainmaa[5] 首次完整地敘述了反向模式自動微積分演算法（著名的反向傳播演算法 BP 的雛形），但在當時並沒有引起重視。直到 Werbos[6] 於 1981 年提出將 BP 演算法應用於神經網路以建立多層感知器后，神經網路的發展才得以提速。接著在 1985 到 1986 兩年間，多位神經網路學者也相繼提出了使用 BP 演算法來訓練多層感知器的相關想法。（例如 Rumelhart, Hinton, Williams [7] – Hetch, Nielsen[8]）

源自 Hetch, Nielsen 的論文 [8]

在這期間，J. R. Quinlan[9] 於 1986 年提出了著名的 ML 演算法——決策樹，也就是 ID3 演算法，它同時亦是機器學習領域的主流分支之一。另外，與「黑盒派」的神經網路編程器不同，ID3 演算法就如發行軟體一般，你可以運用它的簡單規則及清晰理論找到更多具實際意義的應用場景。

自 ID3 演算法提出以來，有不少研究團隊對其進行了優化改進（如 ID4，回歸樹，CART 等等）。至今，它依舊是機器學習領域的「活躍分子」之一。

源自 Quinlan 的論文 [9]

如果要說機器學習最重要的突破的話，1995 年 Vapnik 和 Cortes[10] 提出的支持向量機（SVM）便是其中之一。這種演算法不但有堅實的理論基礎，還有出色的實驗結果。從那之後，機器學習這一領域便分成了兩大流派，神經網路及支持向量機。不過，自 2000 年內核版的 SVM（我找不到關於這個研究的相關論文）被提出后，神經網路在這場競爭中逐漸處於下風。新版本的 SVM 在此前被神經網路壟斷的領域中都取得亮眼的成績。另外與神經網路相比，SVM 的優勢是具有凸優化、大邊際理論、核函數方面的知識基礎。因此，它能從不同的學科理論中汲取養分，從而加快自身的發展進程。

源自 Vapnik 和 Cortes 的論文 [10]

而在 SVM 持續發展之際，神經網路再次受到了重創。Hochreiter1991 年的學位論文 [40] 及 2001 與其他研究人員合作發表的論文 [11] 中表示，使用 BP 演算法時，當神經網路的單元飽和之後系統會發生梯度損失（又稱梯度擴散）。簡單來說，就是訓練神經網路模型的時候，超過一定的迭代次數模型將會產生過擬合。

在此之前，1997 年時 Freund 和 Schapire 提出了另外一個有效的機器學習模型——Adaboost。它的核心思想是，針對同一訓練集訓練不同的弱分類器，然後將它們集合起來，構建出更強的最終分類器（強分類器）。另外，Adaboost 為兩位研究人員贏得了哥德爾獎。直至目前，Adaboost 依舊被不少領域採用，比如面部識別和檢測等等。同時它也是可能近似正確學習（PAC）理論的實踐模型之一。總的來說，Adaboost 就是把多個不同的決策樹用一種非隨機方式組合的提升樹。他們是這樣介紹 Adaboost 的，

我們研究的模型可以被解釋為，在一般決策場景下對已充分了解的預測模型進行大範圍而抽象的擴展…[11]。

另外一種多決策樹的組合模型，則是 2001 年由 Breiman [12] 提出的。這種模型中單個決策樹由一個隨機子集訓練而得，而決策樹中每一節點則各選自這一隨機子集。正是因為這些特點，所以這種演算法被命名為 Random Forest（RF）。據了解，RF 可以避免過擬合現象的出現，這是 AdaBoost 無法做到的。也就是說，與 AdaBoost 相比 RF 更具優勢（想了解 RF 更多細節可以查閱 我以前發表的文章）。此外，RF 在許多運算任務中都有不錯的變現（比如 Kaggle 比賽）。

RF 是一種樹形集成分類器，森林中每棵決策樹都依賴於獨立採樣的向量值，且具有相同的分佈。當森林中決策樹的數量足夠多是，RF 的泛化誤差將收斂於一個有限制值內 [12]。

時至今日，神經網路已經進入了一個名為「深度學習」的新時代。這種依賴於級聯卷積神經網路的全新演算法的出現預示著神經網路第三次大發展的開始。2005 年前後，包括 Hinton、LeCun、Bengio、Andrew Ng 等等在內的多位研究人員都紛紛發表了相關研究成果，下面我為大家列出了較為重要的幾項（我以後可能會發布一篇討論深度學習的文章）：

•GPU 編程
•卷積神經網路 [18] [20] [40]
解卷積網路 [21]
•最優化演算法
隨機梯度下降 [19] [22]
BFGS 演算法和 L-BFGS 演算法 [23]
共軛梯度法 [24]
反向傳播 [40] [19]
•整流單元
•稀疏編碼 [15] [16]
•Dropout 網路 [26]
Maxout 網路學習 [25]
•無監督神經網路模型 [14]
深度信念置信網路 [13]
堆棧式自動編碼器 [16] [39]
Denoising 神經網路模型 [17]

基於這些以及其他沒有列出的成果，深度學習模型在諸多領域中都完勝當時最先進的演算法，比如物體識別、語音識別、自然語言處理等等。不過，這絕對不代表機器學習將就此終結。儘管深度學習依然持續火熱，但是這一模型同樣存在不少痛點，例如成本、參數調優等等方面的問題。而且，SVM 憑藉著自身的簡潔性，目前依舊活躍於各大領域。（據說如此，但存在爭議）。

在文章結束之前，我想談談機器學習領域裡另一個較為新興的研究趨勢。隨著網路及社交媒體的持續發展，大數據這個新概念開始嶄露頭角，並且對機器學習的研究產生了重大影響。在大數據時代，傳統在小數據上運行的機器學習演算法已不再適用，落得無用武之地的下場（當然，科技巨頭除外）。因此，研究人員現在提出了一類新的演算法——Bandit 演算法 [27-38]（通常稱為在線學習），它具有簡化深度學習及適應大數據背景的潛力。

這篇不成熟的機器學習簡史就說到這裡了。如果你發現其中存在錯誤、不中和沒有引用文獻的地方，歡迎提出。

參考文獻

[1] Hebb D. O., The organization of behaviour.New York: Wiley & Sons.

[2]Rosenblatt, Frank. 「The perceptron: a probabilistic model for information storage and organization in the brain.」 Psychological review 65.6 (1958): 386.

[3]Minsky, Marvin, and Papert Seymour. 「Perceptrons.」 (1969).

[4]Widrow, Hoff 「Adaptive switching circuits.」 (1960): 96-104.

[5]S. Linnainmaa. The representation of the cumulative rounding error of an algorithm as a Taylor
expansion of the local rounding errors. Master』s thesis, Univ. Helsinki, 1970.

[6] P. J. Werbos. Applications of advances in nonlinear sensitivity analysis. In Proceedings of the 10th
IFIP Conference, 31.8 – 4.9, NYC, pages 762–770, 1981.

[7] Rumelhart, David E., Geoffrey E. Hinton, and Ronald J. Williams. Learning internal representations by error propagation. No. ICS-8506. CALIFORNIA UNIV SAN DIEGO LA JOLLA INST FOR COGNITIVE SCIENCE, 1985.

[8] Hecht-Nielsen, Robert. 「Theory of the backpropagation neural network.」 Neural Networks, 1989. IJCNN., International Joint Conference on. IEEE, 1989.

[9] Quinlan, J. Ross. 「Induction of decision trees.」 Machine learning 1.1 (1986): 81-106.

[10] Cortes, Corinna, and Vladimir Vapnik. 「Support-vector networks.」 Machine learning 20.3 (1995): 273-297.

[11] Freund, Yoav, Robert Schapire, and N. Abe. 「A short introduction to boosting.」Journal-Japanese Society For Artificial Intelligence 14.771-780 (1999): 1612.

[12] Breiman, Leo. 「Random forests.」 Machine learning 45.1 (2001): 5-32.

[13] Hinton, Geoffrey E., Simon Osindero, and Yee-Whye Teh. 「A fast learning algorithm for deep belief nets.」 Neural computation 18.7 (2006): 1527-1554.

[14] Bengio, Lamblin, Popovici, Larochelle, 「Greedy Layer-Wise
Training of Deep Networks」, NIPS』2006

[15] Ranzato, Poultney, Chopra, LeCun 」 Efficient Learning of Sparse Representations with an Energy-Based Model 「, NIPS』2006

[16] Olshausen B a, Field DJ. Sparse coding with an overcomplete basis set: a strategy employed by V1? Vision Res. 1997;37(23):3311–25. Available at: http://www.ncbi.nlm.nih.gov/pubmed/9425546.

[17] Vincent, H. Larochelle Y. Bengio and P.A. Manzagol, Extracting and Composing Robust Features with Denoising Autoencoders, Proceedings of the Twenty-fifth International Conference on Machine Learning (ICML『08), pages 1096 – 1103, ACM, 2008.

[18] Fukushima, K. (1980). Neocognitron: A self-organizing neural network model for a mechanism of pattern recognition unaffected by shift in position. Biological Cybernetics, 36, 193–202.

[19] LeCun, Yann, et al. 「Gradient-based learning applied to document recognition.」Proceedings of the IEEE 86.11 (1998): 2278-2324.

[20] LeCun, Yann, and Yoshua Bengio. 「Convolutional networks for images, speech, and time series.」 The handbook of brain theory and neural networks3361 (1995).

[21] Zeiler, Matthew D., et al. 「Deconvolutional networks.」 Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on. IEEE, 2010.

[22] S. Vishwanathan, N. Schraudolph, M. Schmidt, and K. Mur- phy. Accelerated training of conditional random fields with stochastic meta-descent. In International Conference on Ma- chine Learning (ICML 』06), 2006.

[23] Nocedal, J. (1980). 」Updating Quasi-Newton Matrices with Limited Storage.」 Mathematics of Computation 35 (151): 773782. doi:10.1090/S0025-5718-1980-0572855-

[24] S. Yun and K.-C. Toh, 「A coordinate gradient descent method for l1- regularized convex minimization,」 Computational Optimizations and Applications, vol. 48, no. 2, pp. 273–307, 2011.

[25] Goodfellow I, Warde-Farley D. Maxout networks. arXiv Prepr arXiv …. 2013. Available at: http://arxiv.org/abs/1302.4389. Accessed March 20, 2014.

[26] Wan L, Zeiler M. Regularization of neural networks using dropconnect. Proc …. 2013;(1). Available at: http://machinelearning.wustl.edu/mlpapers/papers/icml2013_wan13. Accessed March 13, 2014.

[27] Alekh Agarwal, Olivier Chapelle, Miroslav Dudik, John Langford, A Reliable Effective Terascale Linear Learning System, 2011

[28] M. Hoffman, D. Blei, F. Bach, Online Learning for Latent Dirichlet Allocation, in Neural Information Processing Systems (NIPS) 2010.

[29] Alina Beygelzimer, Daniel Hsu, John Langford, and Tong Zhang Agnostic Active Learning Without Constraints NIPS 2010.

[30] John Duchi, Elad Hazan, and Yoram Singer, Adaptive Subgradient Methods for Online Learning and Stochastic Optimization, JMLR 2011 & COLT 2010.

[31] H. Brendan McMahan, Matthew Streeter, Adaptive Bound Optimization for Online Convex Optimization, COLT 2010.

[32] Nikos Karampatziakis and John Langford, Importance Weight Aware Gradient Updates UAI 2010.

[33] Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, Josh Attenberg, Feature Hashing for Large Scale Multitask Learning, ICML 2009.

[34] Qinfeng Shi, James Petterson, Gideon Dror, John Langford, Alex Smola, and SVN Vishwanathan, Hash Kernels for Structured Data, AISTAT 2009.

[35] John Langford, Lihong Li, and Tong Zhang, Sparse Online Learning via Truncated Gradient, NIPS 2008.

[36] Leon Bottou, Stochastic Gradient Descent, 2007.

[37] Avrim Blum, Adam Kalai, and John Langford Beating the Holdout: Bounds for KFold and Progressive Cross-Validation. COLT99 pages 203-208.

[38] Nocedal, J. (1980). 「Updating Quasi-Newton Matrices with Limited Storage」. Mathematics of Computation 35: 773–782.

[39] D. H. Ballard. Modular learning in neural networks. In AAAI, pages 279–284, 1987.

[40] S. Hochreiter. Untersuchungen zu dynamischen neuronalen Netzen. Diploma thesis, Institut f ̈ur In-
formatik, Lehrstuhl Prof. Brauer, Technische Universit ̈at M ̈unchen, 1991. Advisor: J. Schmidhuber.

粹客網是國內首個關注前沿科技領域的科技新媒體和創業服務平台。我們提供最貼近商業化的前沿科技創業報道、最新最全的科技動態資訊以及深刻獨到的行業觀點。堅持挖掘有價值的創新創業項目，致力於成為創新創業者的前沿陣地。
每月精彩評論將有機會獲得神秘禮品，cheekrnews）或發郵件到粹客網官方郵箱。