感知機

出自集智百科
跳轉到: 導覽搜尋

該詞條由 NeverMoes 翻譯編輯,由flynn審校,張江總審校,翻譯自Wikipedia詞條:Perceptron

機器學習中,感知機 有監督學習中的一種二元分類器(一種輸入一個實值向量,判斷其是否屬於某一個類的函數[1])。


這是一種線性分類器,即一種基於線性預測函數將一組權值與特徵向量相結合的分類演算法。

機器學習和數據挖掘


目錄

歷史

參見:人工智慧、感知機歷史和聯結主義的黑暗時代History of artificial intelligence § Perceptrons and the dark age of connectionism人工智慧寒冬AI winter § The abandonment of connectionism in 1969

Mark 1 感知機是第一個感知機演算法的應用。這個機器與一個使用20x20硫化鎘電池的相機相連,能夠生成一張400像素的圖片。它主要的可視特徵就是一塊插板,允許不同的輸入組合進行試驗。右邊是電位計,實現權重的更新。[2]

感知機演算法由Frank Rosenblatt[3]在1957年在Cornell Aeronautical Laboratory(康奈爾航空實驗室)發明,由美國The Office of Naval Research(海軍研辦公室)資助[4]


感知機的目的是成為一台機器,而不是一個程序,雖然它的第一個實現是在IBM 704的軟體中完成的,但是它後來在定製的硬體中實現為"Mark 1 感知機"。這台機器是為圖像識別而設計的:它有一個由400個光電池組成的陣列,隨機與「神經元」相連。權重在電位器中編碼,權重的更新是由電動馬達完成的[2]

在1958年由美國海軍組織的新聞發布會上,Rosenblatt發表了關於感知機的說明,感知機在新興的人工智慧社區中引起了激烈的討論。根據Rosenblatt的說明,紐約時報報道這個感知機是一個電子計算機的胚胎,(海軍)希望它能夠行走、說話、寫字、看見。複製自己並意識到自己的存在。[4]


雖然感知機起初看起來前途無量,但是感知機很快就被證明不能被訓用來識別很多其他的模式。這使得神經網路的研究領域停滯了很多年直到人們認識到一個有兩層及以上的前饋神經網路(也稱為多層感知機),其處理能力遠遠大於單層的(也稱為單層感知機)。單層感知機只能學習線性可分的模式。1969年Marvin Minsky和Seymour Papert出版的一本著名的著作《感知機》表明,單層感知機學習一個XOR函數是不可能的。於是人們錯誤的認為以及推測對於多層感知機也會有類似的結果。然而,這是不對的。因為Minsky 和 Papert 都已經知道多層的感知機可以構造XOR函數。三年後,Stephen Grossberg發布了一系列的論文,介紹了能夠對微分,對比增強和XOR函數進行建模的網路。然而,Minsky 和 Papert研究成果中的誤導導致了神經網路研究的興趣下降和資金大幅減少。直到十多年以後的十九世紀八十年代,神經網路研究才又迎來了一次復興。該書也在1987年進行修訂和再版,新版本的《感知機-修訂版》對原文中的一些錯誤進行了說明和指正。

早在1964年,Aizerman等人[5] 就提出了核感知機演算法。感知機演算法的間距下界的保證首先由Yoav FreundRobert Schapire(1998)[1]在不可分的情況下給出了,最近Mehryar Mohri and Rostamizadeh (2013)推廣了先前的結論並給出了新的L1下界[6]


感知機是一個簡化的生物神經元模型。雖然生物神經元模型的複雜性是通常是理解神經行為所必須的。但研究表明,類感知機的線性模型也可以產生一些在真實神經元中看到的行為。[7][8].

定義

在現代,感知機是一種二分類學習演算法:用一個函數將輸入 x(一個實值向量)映射到輸出值f(x)(一個二元值):


f(x) = \begin{cases}1 & \text{if }\ \mathbf{w} \cdot \mathbf{x} + b > 0\\0 & \text{otherwise}\end{cases}

這裡的 w 是一個實值構成的權重向量,\mathbf{w} \cdot \mathbf{x}是一個點積操作即 \sum_{i=1}^m w_i x_im 是感知機輸入值的個數,其中 b 是偏置項。偏置項決定了決策邊界相對原點的偏移量,且不依賴於任何輸入值。

在二分類問題中,f(x) 的值(0或1)用來將 x 分為正例或者負例。如果 b 是負的,那麼輸入和權重的結合生成的正值必須比 |b|大,從而使得分類的神經元大於0閾值。從空間上來說,偏置項改變了決策邊界的位置(而不是方向)。如果訓練集不是線性可分的,那麼感知機學習演算法就不會停止。如果向量不是線性可分的,那麼學習將永遠不會收斂到所有向量都分類正確的結果。感知機演算法的局限性的最著名的例子就是線性不可分的情況,比如XOR問題。對於所有二分類函數的決策邊界解的空間和學習表現的研究都在這個參考中[9]

在神經網路的場景中,感知機是一個以單位階躍函數為激活函數的人工神經元。感知機演算法也被稱為單層感知機。這個術語用於區分多層感知機即一個更加複雜的神經網路。作為一個線性分類器,單層感知機是一類最簡單的前饋神經網路

學習演算法

下面是一個介紹單層感知機學習演算法的例子。對於存在隱層的多層感知機,必須使用諸如反向傳播等更加複雜的演算法。儘管下面的方法也是可行,但如果在函數是非線性且可微的情況下,那麼可以使用鏈式法則等方法解決問題。

當多個感知機在一個人工神經網路中組合應用時,每個輸出神經元都獨立於其他神經元運行。因此,學習的每一個輸出都可以單獨考慮。
一副圖展示了感知機演算法在新的訓練數據加入時是如何更新它的線性邊界的。

定義

我們先定義這些變數:

  • y = f(\mathbf{z}) 表示感知對於某個輸入向量 \mathbf{z} 的輸出。
  • D = \{(x_1,d_1),\dots,(x_s,d_s)\} 訓練集 s 的樣本, 其中:
    • x_jn維 輸入向量。
    • d_j 是感知對應輸入的期望輸出值。

我們用如下方式表示特徵值:

  • x_{j,i} 是輸入向量的第 j 個樣本的第 i 個特徵。
  • x_{j,0} = 1 .

權重的表示:

  • w_i 是權重向量的第 i 個值,這是為了表示和第 i 個輸入特徵相乘。
  • 因為 x_{j,0} = 1 w_0 實際上表示的是偏置項也就是常量 b

為了表示每一輪獨立的 \mathbf{w} ,這裡使用如下符號:

  • w_i(t) 是第 t 輪訓練中的權重 i

不像Logistic回歸這樣的線性分類演算法,在感知機學習演算法中沒有學習速率 。這是因為通過乘以常數的更新只是放縮了權重,但不會改變預測結果的符號[10]

適當的權重被應用到輸入,然後產生加權和傳遞給一個生成輸出o的函數。

步驟

  1. 初始化權重與閾值。權重初始化為全0或者一個很小的隨機值。在下面的例子中我們使用0作為初始化值。
  2. 對於數據集 D 中每一個樣本 j ,對輸入 x_j 執行以下的步驟,並得到期望的輸出 d_j
    1. 計算以下的輸出:\begin{align}
y_j(t) &= f[\mathbf{w}(t)\cdot\mathbf{x}_j] \\
&= f[w_0(t)x_{j,0} + w_1(t)x_{j,1} + w_2(t)x_{j,2} + \dotsb + w_n(t)x_{j,n}]
\end{align}
    2. 更新權重:w_i(t+1) = w_i(t) + r\cdot(d_j - y_j(t)) x_{j,i}, 0 < i < n,其中 r是學習速率。
  3. 對於離線學習,第二步需要重複直到迭代誤差\frac{1}{s} \sum_{j=1}^s |d_j - y_j(t)| 小於一個用戶定於的誤差閾值\gamma,或者預定於的迭代輪數已經完成,這裡的 s 是是樣本集的大小。

這個演算法在2.1和2.2步驟後更新了權重。這些權重會立即反應到訓練數據中,並且隨後進行更新,並不是等所有步驟結束後才更新的。

收斂性

感知機是一種線性分類器,因此如果數據集 D 是非線性可分的話,那麼它永遠無法讓所以的輸入向量分類正確,即正負的樣本不能被一個線性超平面所分割。標準演算法在這種情況下時是無法逐漸達到一個近似解的,並導致學習過程會直接失效。所以,如果我們不能事先知道數據集是否是線性可分的,則應該使用下面的變種。

如果訓練集是線性可分的,那麼感知機可以確保其收斂性。此外,感知機在訓練過程中調整自身權重的次數是有上限的。

假設分屬於兩個類的輸入向量可以被一個線性超平面分割成兩個類,且樣本到超平面的間距為 \gamma 。即存在一個權重向量 \mathbf{w}||\mathbf{w}||=1,以及一個偏置項 b 使得對於所有的 d_j=1 對應 j 有 \mathbf{w}\cdot\mathbf{x}_j > \gamma  d_j=0對應的 j 有 \mathbf{w}\cdot\mathbf{x}_j < -\gamma 。且如果引入 R 表示輸入向量最大的維度。Novikoff (1962)證明了感知機可以在 O(R^2 \gamma^2)輪迭代中完成收斂。證證明的思路是權重向量可以被有負點積的約束值在一個方向上修正,因此可以被 Osqrt{t} 的下界約束,這裡的 t 是權重向量更新的次數。然而,它也可以被  O(t) 的上界約束。因為如果存在一個未知的滿足條件的權重向量,那麼在這個方向上每一次權重向量的改變都只取決於輸入向量。

當感知機演算法在訓練集線性可分的條件下會在某個解中達到收斂,而且會在多個質量不同且滿足條件的解中任意選一個。[11]最佳穩定性感知機現在一般稱為SVM支持向量機,就是設計用來解決這個問題的。[12]

兩種種類的點和無限多的可以分割它們的線性邊界。即使這兩條線性邊界是直角相對的,感知機演算法也無法從其中選擇。

變種

漸進的pocket演算法(Gallant, 1990)通過保留最近的最佳解解決了感知機學習過程中的穩定性問題。pocket演算法接下來返回保存最佳的解而不是迭代的最後一個解。它也可以被用於線性不可分的數據集,那麼感知機的學習目的就是找一個使得誤分類數量最小的解。然而這些解是完全隨機出現的,因此pocket演算法不能在學習的過程中最終得到這些解也不能保證在給定的迭代次數中找到這些解。

Maxover演算法 (Wendemuth, 1995)[13] 在某種意義上是穩健的(robust),因為無論是否事先知道數據集線性可分,它都會達到收斂。在線性可分的情況下,即使具有最佳的穩定性(即類之間達到最大間距)也能很好解決訓練問題。對於線性不可分的數據集,它會返回一個少量誤分類的解。在所有的情況下,該演算法在學習過程中會逐漸接近解而不會存儲先前的狀態,也不會隨機跳躍。收斂性是指線性可分數據集的全局最優解和非線性可分數據的局部最優解。

投票感知機 (Freund and Schapire, 1999),是一種使用多權重的感知機的變種。每當一個例子被錯誤的分類時,演算法會啟動一個新的感知機,然後使用最後的感知機的權重作為現在感知機的初始化權重。每次分類錯誤感知機都會被給予另外的權重直到所以樣本分類正確。最後得到所有感知機加權投票的結果。

在線性可分問題中,感知機的訓練目標在於在樣本之間找到最大的間距分割兩個類。所謂的最優穩定性感知機可以通過迭代訓練和優化策略來確定,比如Min-Over演算法 (Krauth and Mezard, 1987)[12] 或者AdaTron演算法 (Anlauf and Biehl, 1989))。[14] AdaTron利用了問題對應的二次優化是凸的這一條件。最佳穩定性感知機加上核方法,這是SVM支持向量機概念的基礎。

\alpha-感知機使用了帶有閾值輸出單元的固定隨機權重的預處理層。這使得感知機能夠通過投影二元空間類似的模式進行分類。實際上對於一個維度足夠高的的投影空間,模式就會變得線性可分了。

解決線性不可分問題的另一種方法是使用高階的網路(sigma-pi unit)。在這種類型的網路中,每個輸入向量的元素都會使用複雜輸入(二階)組合來拓展到高緯。這可以使其拓展到一個n階網路。

但是,我們應該牢記,最好的分類器不需要完美分類所有訓練數據。實際上,如果我們有先驗性的約束,即數據據來自於高斯分布。那麼輸入空間的線性解是最佳的,而非線性解是過擬合的。

其他的線性分類演算法包括了WinnowSVM支持向量機,和Logistic回歸

多分類感知機

類似於其他訓練線性分類器的技巧,感知機可以很自然地泛化成多分類分類器。這裡的輸入 x 和輸出 y 是從任意集合中得到的。特徵表示函數f(x,y)將每一個可能的輸入/輸出對映射到一個有限維的實值特徵向量上。與之前相同,特徵向量乘以一個權重向量 w,但是現在該結果的值將被用於選擇許多可能輸出結果的其中之一:

\hat y = \operatorname{argmax}_y f(x,y) \cdot w.

同樣通過在樣本的迭代來完成學習,預測每一個輸出的結果,當預測和實際結果匹配時不更新權重,反之則更新。更新方式就是:

 w_{t+1} = w_t + f(x, y) - f(x,\hat y).

x 是一個實值向量,這個多分類的更新公式會退化到原始的感知機的更新公式。即 y\{0,1\}中的一個,f(x,y) = y x

對於某些問題,可以選擇輸入/輸出和特徵的表示。所以即使 y 是一個非常大或者無限集合中的元素。 \mathrm{argmax}_y f(x,y) \cdot w 也可以被高效地找到。

在最近的幾年,感知機的訓練已經成為了自然語言處理的熱門話題,比如語音標記語法分析等任務(Collins, 2002)。

參考

  1. 1.0 1.1 Freund, Y.; Schapire, R. E.(1999), "Large margin classification using the perceptron algorithm" . Report 37 (3): 277–296, doi:10.1023/A:1007662407062.
  2. 2.0 2.1 Bishop, Christopher M. (2006), Pattern Recognition and Machine Learning. Springer.
  3. Rosenblatt, Frank (1957), The Perceptron--a perceiving and recognizing automaton. Report 85-460-1, Cornell Aeronautical Laboratory.
  4. 4.0 4.1 Mikel Olazaran (1996). " A Sociological Study of the Official History of the Perceptrons Controversy". Social Studies of Science. 26 (3): 611–659 doi:10.1177/030631296026003005. JSTOR 285702.
  5. Aizerman, M. A.; Braverman, E. M.; Rozonoer, L. I. (1964). "Theoretical foundations of the potential function method in pattern recognition learning". Automation and Remote Control 25: 821–837.
  6. Mohri, Mehryar and Rostamizadeh, Afshin (2013). Perceptron Mistake Bounds arXiv:1305.0208, 2013.
  7. Morel, D., Singh, C. & Levy, W.B. J Comput Neurosci (2018). http://rdcu.be/FDUo
  8. Cash, Sydney, and Rafael Yuste. "Linear summation of excitatory inputs by CA1 pyramidal neurons." Neuron 22.2 (1999): 383-394.APA
  9. Liou, D.-R.; Liou, J.-W.; Liou, C.-Y. (2013). Learning Behaviors of Perceptron. iConcept Press. ISBN978-1-477554-73-9.
  10. Genevieve B. Orr. "The Perceptron". Willamette University. Retrieved 3 March 2017.
  11. Bishop, Christopher M. "Chapter 4. Linear Models for Classification". Pattern Recognition and Machine Learning. Springer Science+Business Media, LLC. p. 194. ISBN 978-0387-31073-2.
  12. 12.0 12.1 W. Krauth and M. Mezard. Learning algorithms with optimal stability in neural networks. J. of Physics A: Math. Gen. 20: L745-L752 (1987)
  13. A. Wendemuth. Learning the Unlearnable. J. of Physics A: Math. Gen. 28: 5423-5436 (1995)
  14. J.K. Anlauf and M. Biehl. The AdaTron: an Adaptive Perceptron algorithm. Europhysics Letters 10: 687-692 (1989)

深入閱讀

  • Aizerman, M. A. and Braverman, E. M. and Lev I. Rozonoer. Theoretical foundations of the potential function method in pattern recognition learning. Automation and Remote Control, 25:821–837, 1964.
  • Rosenblatt, Frank (1958), The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain, Cornell Aeronautical Laboratory, Psychological Review, v65, No. 6, pp. 386–408. doi:10.1037/h0042519.
  • Rosenblatt, Frank (1962), Principles of Neurodynamics. Washington, DC:Spartan Books.
  • Minsky M. L. and Papert S. A. 1969. Perceptrons. Cambridge, MA: MIT Press.
  • Gallant, S. I. (1990). Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
  • Mohri, Mehryar and Rostamizadeh, Afshin (2013). Perceptron Mistake Bounds arXiv:1305.0208, 2013.
  • Novikoff, A. B. (1962). On convergence proofs on perceptrons. Symposium on the Mathematical Theory of Automata, 12, 615-622. Polytechnic Institute of Brooklyn.
  • Widrow, B., Lehr, M.A., "30 years of Adaptive Neural Networks: Perceptron, Madaline, and Backpropagation," Proc. IEEE, vol 78, no 9, pp. 1415–1442, (1990).
  • Collins, M.2002. Discriminative training methods for hidden Markov models: Theory and experiments with the perceptron algorithm in Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP '02).
  • Yin, Hongfeng (1996), Perceptron-Based Algorithms and Analysis, Spectrum Library, Concordia University, Canada

外部鏈接

本詞條內容翻譯自 wikipedia.org,遵守 CC3.0協議。

個人工具
名字空間
動作
導覽
工具箱