感知器

感知器（Perceptron）是弗蘭克·羅森布拉特在1957年就職於康奈爾航空實驗室（Cornell Aeronautical Laboratory）時所發明的一種人工神經網路。它可以被視為一種最簡單形式的前饋神經網路，是一種二元線性分類器。

羅森布拉特給出了相應的感知機學習演算法，常用的有感知機學習、最小二乘法和梯度下降法。譬如，感知機利用梯度下降法對損失函數進行極小化，求出可將訓練數據進行線性劃分的分離超平面，從而求得感知機模型。

感知機是生物神經細胞的簡單抽象。神經細胞結構大致可分為：樹突、突觸、細胞體及軸突。單個神經細胞可被視為一種只有兩種狀態的機器——激動時為『是』，而未激動時為『否』。神經細胞的狀態取決於從其它的神經細胞收到的輸入信號量，及突觸的強度（抑制或加強）。當信號量總和超過了某個閾值時，細胞體就會激動，產生電脈衝。電脈衝沿著軸突並通過突觸傳遞到其它神經元。為了模擬神經細胞行為，與之對應的感知機基礎概念被提出，如權量（突觸）、偏置（閾值）及激活函數（細胞體）。

在人工神經網絡領域中，感知機也被指為單層的人工神經網絡，以區別於較複雜的多層感知機（Multilayer Perceptron）。作為一種線性分類器，（單層）感知機可說是最簡單的前向人工神經網絡形式。儘管結構簡單，感知機能夠學習並解決相當複雜的問題。感知機主要的本質缺陷是它不能處理線性不可分問題。

## 歷史

1943年，心理學家沃倫·麥卡洛克和數理邏輯學家沃爾特·皮茨在合作的《A logical calculus of the ideas immanent in nervous activity》論文中提出並給出了人工神經網絡的概念及人工神經元的數學模型，從而開創了人工神經網絡研究的時代。1949年，心理學家唐納德·赫布在《The Organization of Behavior》論文中描述了神經元學習法則——赫布型學習。

人工神經網絡更進一步被美國神經學家弗蘭克·羅森布拉特所發展。他提出了可以模擬人類感知能力的機器，並稱之為『感知機』。1957年，在Cornell航空實驗室中，他成功在IBM 704機上完成了感知機的仿真。兩年後，他又成功實現了能夠識別一些英文字母、基於感知機的電腦——Mark I perceptron，並於1960年6月23日，展示與眾。

為了『教導』感知機識別圖像，羅森布拉特在赫布理論的基礎上，發展了一種迭代、試錯、類似於人類學習過程的學習演算法——感知機學習。除了能夠識別出現較多次的字母，感知機也能對不同書寫方式的字母圖像進行概括和歸納。但是，由於本身的局限，感知機除了那些包含在訓練集裡的圖像以外，不能對受干擾（半遮蔽、不同大小、平移、旋轉）的字母圖像進行可靠的識別。

首個有關感知機的成果，由羅森布拉特於1958年發表在《The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain》的文章里。1962年，他又出版了《Principles of Neurodynamics: Perceptrons and the theory of brain mechanisms》一書，向大眾深入解釋感知機的理論知識及背景假設。此書介紹了一些重要的概念及定理證明，例如感知機收斂定理。

雖然最初被認為有著良好的發展潛能，但感知機最終被證明不能處理諸多的模式識別問題。1969年，馬文·閔斯基和西摩爾·派普特在《Perceptrons》書中，仔細分析了以感知機為代表的單層神經網路系統的功能及局限，證明感知機不能解決簡單的異或（XOR）等線性不可分問題，但羅森布拉特和閔斯基及派普特等人在當時已經了解到多層神經網路能夠解決線性不可分的問題。

由於羅森布拉特等人沒能夠及時推廣感知機學習演算法到多層神經網路上，又由於《Perceptrons》在研究領域中的巨大影響，及人們對書中論點的誤解，造成了人工神經領域發展的長年停滯及低潮，直到人們認識到多層感知機沒有單層感知機固有的缺陷及反向傳播算法在80年代的提出，才有所恢復。1987年，書中的錯誤得到了校正，並更名再版為《Perceptrons - Expanded Edition》。

近年，在Freund及Schapire（1998）使用核方法改進感知機學習演算法之後，愈來愈多的人對感知機學習演算法產生興趣。後來的研究表明除了二元分類，感知機也能應用在較複雜、被稱為構造化預測（structured learning）類型的任務上，又或使用在分布式計算環境中的大規模機器學習問題上。

## 定義

感知器使用特徵向量來表示的前饋神經網絡，它是一種二元分類器，把矩陣上的輸入$x$（實數值向量）映射到輸出值$f(x)$上（一個二元的值）。

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

$w$是實數的表示權重的向量，$w \cdot x$是點積。$b$是偏置，一個不依賴於任何輸入值的常數。偏置可以認為是激勵函數的偏移量，或者給神經元一個基礎活躍等級。

$f(x)$（0或1）用於對$x$進行分類，看它是肯定的還是否定的，這屬於二元分類問題。如果$b$是負的，那麼加權後的輸入必須產生一個肯定的值並且大於$-b$，這樣才能令分類神經元大於閾值0。從空間上看，偏置改變了決策邊界的位置（雖然不是定向的）。

由於輸入直接經過權重關係轉換為輸出，所以感知器可以被視為最簡單形式的前饋式人工神經網絡。

## 結構

設有$n$維輸入的單個感知機（如右圖示），${a}_1$至${a}_n$為$n$維輸入向量的各個分量，${w}_1$至${w}_n$為各個輸入分量連接到感知機的權量（或稱權值），${b}$為偏置，$f(.)$為激活函數（又曰激勵函數或傳遞函數），$t$為標量輸出。輸出$t$的數學描述為：

$$t = f(\sum_{i=1}^{n}{{w}_i {x}_i + b}) <pre> = f(\mathbf{w}^T \mathbf{x}) </pre>$$ 其中$\mathbf{w} = [w_1 \; w_2 \; ... \; w_n \; b]^T$，$\mathbf{x} = [x_1 \; x_2 \; ... \; x_n \; 1]^T$及$f(x)$為反對稱的符號函數，其定義為：

$$f(n) = \begin{cases}+1 & \text{if }n \geq 0\\-1 & \text{otherwise}\end{cases}$$ 從式(1)可知，偏置被引申為權量，而對應的輸入值為$1$。故，一感知機的輸出行為是求得輸入向量與權向量的內積後，經一個激活函數所得一個標量結果。

設輸入向量與權向量的內積為零，可得出$(n+1)$維的超平面。平面的法向量為$\mathbf{w}$，並經過$(n+1)$維輸入空間的原點。法向量指向的輸入空間，其輸出值為$+1$，而與法向量反向的輸入空間，其輸出值則為$-1$。故可知這個超平面定義了決策邊界，並把輸入空間劃分為二。

## 準則函數

設一訓練集為$D = \{(\mathbf{p}_1, \; t_1), \;\dots\;, (\mathbf{p}_m, \; t_m)\}$，其中$\mathbf{p}_i$表示輸入，而${t}_i$是對應的目標輸出。由於符號函數的不連續性，如果採用標準的均方誤差，所得誤差函數必然是不連續的，因而基於梯度的學習演算法也就不能被使用。為此，Rosenblatt提出了感知機準則函數：

$$E(\mathbf{w}) = -\sum_{\mathbf{p}_i \in M}^{}{(\mathbf{w}^T\mathbf{p}_i) \; {t}_i}$$

其中$M$是被當前$\mathbf{w}$錯誤分類的的輸入向量集合。當$\mathbf{w}^T\mathbf{p}_i \geq 0$時，${t}_i$為$-1$，而當$\mathbf{w}^T\mathbf{p}_i < 0$時，${t}_i$為$+1$。故，誤差函數$E(\mathbf{w})$是一組正數的和，又或當訓練集裡所有輸入都被正確分類時，等於零。

## 學習演算法

學習演算法對於所有的神經元都是一樣的，因此下面所有東西都要獨立的應用於每個神經元。我們首先定義一些變量：

- $x(j)$表示n維輸入向量中的第j項
- $w(j)$表示權重向量的第j項
- $f(x)$表示神經元接受輸入$x$產生的輸出
- $\alpha$是一個常數，符合$0 < \alpha \leq 1$（接受率）

更進一步，為了簡便我們假定偏置量$b$等於0。因為一個額外的維$n+1$維，可以用$x(n+1)=1$的形式加到輸入向量，這樣我們就可以用$w(n+1)$代替偏置量。

感知器的學習通過對所有訓練實例進行多次的迭代進行更新的方式來建模。令$D_m = \{(x_1,y_1),\dots,(x_m,y_m)\}$表示一個有$m$個訓練實例的訓練集。

每次迭代權重向量以如下方式更新：

對於每個$D_m = \{(x_1,y_1),\dots,(x_m,y_m)\}$中的每個$(x,y)$對。

$$w(j):= w(j) + {\alpha(y-f(x))}{x(j)} \quad(j=1,\ldots,n)$$

注意這意味著，僅當針對給定訓練實例$(x,y)$產生的輸出值$f(x)$與預期的輸出值$y$不同時，權重向量才會發生改變。

如果存在一個正的常數$\gamma$和權重向量$w$，對所有的$i$滿足$y_i \cdot\left( \langle w, x_i \rangle +b \right) > \gamma$，訓練集$D_m$就被叫被做線性分隔的。Novikoff（1962）證明如果訓練集是線性分隔的，那麼感知器演算法可以在有限次迭代後收斂，錯誤的數量由$\left(\frac{2R}{\gamma}\right)^2$限定，其中$R$為輸入向量的最大平均值。

然而，如果訓練集不是線性分隔的，那麼這個演算法則不能確保會收斂。

## 參考文獻

- Freund, Y. and Schapire, R. E. 1998. Large margin classification using the perceptron algorithm. In Proceedings of the 11th Annual Conference on Computational Learning Theory (COLT' 98). ACM Press.
- Gallant, S. I. (1990). Perceptron-based learning algorithms. IEEE Transactions on Neural Networks, vol. 1, no. 2, pp. 179–191.
- 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.
- Minsky M L and Papert S A 1969 Perceptrons (Cambridge, MA: MIT Press)
- 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)。
- 神經網路設計（Neural Network Design），美哈根等著，戴葵等譯。機械工業出版社。ISBN 9787111075851

## 外部連結

- Chapter 3 Weighted networks - the perceptron and chapter 4 Perceptron learning of Neural Networks - A Systematic Introduction by Raúl Rojas（ISBN 978-3540605058）
- History of perceptrons
- Mathematics of perceptrons
- Perceptron demo applet and an introduction by examples