從感知機到GAN，簡述機器學習發展史

選自chatbotnewsdaily

機器之心編譯

參與：蔣思源、李亞洲

機器學習是人工智慧的一個重要分支，也是如今學界、產業界的熱門研究。公司、高校傾倒了許多資源發展機器學習。近期的發展也催生了在許多任務上的堅實成果，表現可與人類相媲美。

在這篇文章中，我會分享一下機器學習發展中的重要時間線，還會提一些重要的里程碑，但可能不完整。

Hebb 在 1949 年基於神經心理的學習方式第一次提出了機器學習方法，該方法被稱之為 Hebbian 學習理論。該學習理論通過簡單的解釋展示了循環神經網路（RNN）中結點之間的相關性關係。它記憶住神經網路上任何共性信息，就像後來的記憶一樣。正式地，概念可以表述為下：

若我們假設持續或反覆的反射活動（或「trace」）會傾向於引起持續的細胞變化，並增加其穩定性。那麼當細胞 A 的軸突足夠接近以激發細胞 B，然後反覆或持續地激發它，就會在一個或兩個細胞中發生一些生長過程或代謝改變，如 A 的效率在另一個細胞激發了 B 時提升 [1]

Arthur Samuel

1952 年 Arthur Samuel 在 IBM 開發了一款玩西洋棋的程序。該程序能夠觀察位置並學習一個隱式模型以在後一步棋中獲得更好的策略。Samuel 用該程序下了許多盤棋，並發現程序最後能下得更好。

通過這個程序，Arthur Samuel 反駁了廣義 providence 指令機不能超越所寫的代碼並學習類人模式這一觀點。他還創造了「機器學習」這一術語，並定義為：

在沒有明確指令的情況下賦予計算機能力的一個研究領域。

F. Rosenblatt

Rosenblatt 在 1957 年提出的感知機是擁有神經科學背景的第二個模型，該演算法更像現在的機器學習模型。這一模型是十分重要的發現，實際上它要比 Hebbian 的想法更具適用性。Rosenblatt 通過下面的定義介紹了感知機模型：

感知機旨在說明一般智能系統的一些基本屬性，它不會因為個別特例或通常不知道的東西所束縛住，也不會因為那些個別生物有機體的情況而陷入混亂。

在 3 年後，Widrow [4] 加上了 Delta 學習法則，該學習法則被用作感知機訓練的可實踐過程，其也通常稱之為最小二乘問題。如果結合這兩個觀點，我們就能建立一個很好的線性分類器。然而感知機的流行被 Minsky[3] 在 1969 年提出的問題所終止，他提出了著名的邏輯異或問題（XOR problem），並指出感知機在這種線性不可分的數據分布上是失效的。這是 Minsky 對神經網路社區的攻擊，此後神經網路的研究者進入了寒冬，直到 1980 年才再一次復甦。

邏輯異或問題是線性不可分數據

Minsky 後一段時間並沒有什麼研究結果，直到 Werbos[6]1981 年在神經網路具體的反向傳播（BP）演算法中提出了多層感知機模型（MLP）才出現轉機。雖然 BP 演算法的概念由 Linnainmaa [5] 在 1970 年就已經以「自動微分的反向模型」為名提出來了，但 BP 演算法仍然是當今神經網路架構的重要組成部分。有了這些新概念，神經網路的研究再一次加速。在 1985-1986 年，研究者相繼提出了使用 BP 演算法訓練的多參數線性規劃（MLP）問題（Rumelhart, Hinton, Williams [7]—Hetch, Nielsen[8]）。

來自於 Hetch 和 Nielsen [8]

在另一個譜系中，J.R.Quinlan [9] 於 1986 年提出了一種非常出名的機器學習演算法，我們稱之為決策樹，更具體的說是 ID3 演算法。這是另一個主流機器學習演算法的突破點。此外 ID3 演算法也被發布成為了一款軟體，它能以簡單的規劃和明確的推論找到更多的現實案例，而這一點正好和神經網路黑箱模型相反。

在 ID3 演算法提出來以後，研究社區已經探索了許多不同的選擇或改進（如 ID4、回歸樹、CART 演算法等），這些演算法仍然活躍在機器學習領域中。

來自於 Quinlan [9]

最重要的機器學習突破之一是 Vapnik 和 Cortes[10] 在 1995 年提出的支持向量機（SVM），該演算法具有非常強大的理論地位和實證結果。那一段時間機器學習研究社區也分為 NN 和 SVM 兩派。然而，在 2000 年左右提出了帶核函數的支持向量機後，神經網路已經無力與其競爭。SVM 在許多以前由 NN 佔據的任務中獲得了更好的效果。此外，SVM 相對於 NN 還能利用所有關於凸優化、泛化邊際理論和核函數的深厚知識。因此 SVM 可以從不同的學科中大力推動理論和實踐的改進。

來自於 Vapnik 和 Cortes [10]

通過 1991 年 Hochreiter 的論文 [40] 和 Hochreiter et. al.[11] 在 2001 年的研究，神經網路遭受到又一個質疑。因為他們的研究表明在我們應用 BP 演算法學習時，NN 神經元飽和後會出現梯度損失（gradient loss）的情況。簡單地說，由於神經元飽和，在一定數量的 epochs 後訓練的 NN 神經元是多餘的，因此 NN 非常傾向於在小 epochs 數量上產生過擬合現象。

不久之後，Freund 和 Schapire 在 1997 年提出了另一個著名的機器學習模型，即利用多個弱分類器組合成強分類器的 Adaboost 演算法。該提升方法從弱學習演算法出發，反覆學習，得到一系列弱分類器（又稱為基本分類器），然後組合這些弱分類器，構成一個強分類器。AdaBoost 通過改變訓練數據的概率分布，針對不同的訓練數據分布調用弱學習演算法學習一系列弱分類器。AdaBoost 的做法是提高那些被前一輪弱分類器錯誤分類樣本的權重。所以那些錯誤分類的樣本由於其權重增加而會受到後一輪弱分類器的更大關注，從而利用多個弱分類器解決複雜問題。這種模型仍然是很多不同任務的基礎，如面部識別和檢測。它也是實現 PAC（Probably Approximately Correct）學習理論的方法。Freund 和 Schapire 將 Adaboost 演算法描述為：

我們研究的模型可解釋為將在線預測模型更寬、更抽象地擴展為通用的決策理論設定。

Breiman [12] 在 2001 年探索了另一種集成模型，該模型集成了多棵決策樹，其中每一棵決策樹都由樣本的隨機子集而構建，每一個結點都是從特徵的隨機子集中選擇。由於該演算法的性質，我們稱之為隨機森林（RF）。RF 在過擬合耐性有理論和實證方面的證明。實際上 AdaBoost 顯示了過擬合和數據中的異常值的缺點，而 RF 是針對這些缺點更具魯棒性的模型。RF 在許多不同的任務，如 Kaggle 比賽中也取得了很多的成功。

隨機森林是樹型預測的組合，其中每棵樹取決於獨立採樣的隨機向量值，並且森林中所有的樹都服從相同的分布。森林的泛化誤差隨著樹的數量變多而收斂於一個極限值 [12]。

如今，NN 的一個新紀元由深度學習而引發。深度學習指具有許多廣泛連續層的 NN 模型。NN 模型的第三次崛起大概在 2005 年，其由最近的 Hinton、LeCun、Bengio、Andrew Ng 和其他研究員共同完成。下面是一些深度學習重要的主題：

• GPU programming

• Convolutional NNs [18][20][40]

• Deconvolutional Networks [21]

• 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]

• (GAN) Generative Adversarial Networks [41]

• Variational Auto-Encoders [42]

AlexNet 贏得 ImageNet 挑戰賽，深度學習起飛

結合以上列出的以及未列出的所有思路，神經網路模型能夠在多種不同的人物上取得頂尖成果，例如目標識別、語音識別、NLP 等。然而，這並不意味著其他機器學習流派的終結。即使深度學習增長迅速，但深度學習所需要的訓練成本、調整模型的大量參數上仍多有詬病。此外，SVM 因其簡單性也有了更普遍的運用。

在深度學習潮流下，我們看到了圖像識別要早於 NLP 成為了第一個突破點。這些問題看起來解決地很好，而且我們也看到了許多人工智慧產品。下一個趨勢看起來是在視頻與生成式模型上面。

如果我們把人類視覺感知用時序輸入來模擬，那麼視頻的輸入量會變得更大，在計算和演算法兩方面也是個更難的問題，因此也就比一般的人工智慧任務更重要。

生成式學習以倒序的方式處理問題，給模型一定的線索，它會生成真實的圖像。這樣的模型需要學習如何表達數據，而非只是進行分類。

這兩種趨勢都提供更智能的演算法，並可能減少深度學習解決方案中所需要的大量數據。例如，有了視頻輸入，演算法能夠學習目標的多個不同方面，也能在沒有 ImageNet 這樣的大型數據集的情況下歸納這些信息。而生成式模型在數據稀缺的領域能很好的歸納表徵知識，從而進行分類任務。

在結束之前，我想要提一下另外一個很熱的機器學習話題。隨著互聯網、社交媒體的興起，大數據開始崛起並極大的影響著機器學習的研究。因為源自大數據的許多問題，眾多強大的機器學習演算法開始變得沒用。因此研究人員想出了一系列被稱為 Bandit Algorithm 的新的簡單模型（之前是在線學習），從而使得學習更簡單、更適用於大規模問題。

參考文獻：

[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 ZhangAgnostic 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.

[41] Goodfellow, Ian, et al. 「Generative adversarial nets.」 Advances in neural information processing systems. 2014.

[42] Diederik P Kingma. Auto-Encoding Variational Bayes https://arxiv.org/abs/1312.6114