初版 2015.06.18
二版 2016.10.07
一、類神經網絡簡介 (Neural Network, NN)
類神經網絡是一種受生物學啟發而產生的一種模擬人腦的學習系統。
對於神經(neuron)我們有一個簡單的抽象：每個神經元是與其他神經元連結在一起的，一個神經元會受到多個其他神經元狀態的衝擊，並由此決定自身是否激發。
神經細胞透過輸入神經樹由其它神經細胞輸入脈波訊號後，經過神經細胞核的處理，其處理大約是：
- 將收集到的訊號作加總
- 非線性轉換
- 產生一個新的脈波信號
神經網絡裡的結點相互連結決定了輸入的數據在裡面經過怎樣的計算。我們可以通過大量的輸入，讓神經網絡調整它自身的連接情況從而總是能夠得到我們預期的輸出。
二、感知器 Perceptron
設有 $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}) = f(\mathbf{w}^T \mathbf{x})$
其中 $\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}$
權值(w)：如果當前神經元的某個輸入值權值為零，則當前神經元激發與否與這個輸入值無關；如果某個輸入值的權重為正，它對於當前神經元的激發值產生正影響。反之，如果權重為負，則它對激發值產生負影響。
偏移量(b)：它定義了神經元的激發臨界值在空間上，它對決策邊界(decision boundary) 有平移作用，就像常數作用在一次或二次函數上的效果。感知器表示為輸入向量與權向量內積時，偏置被引申為權量，而對應的輸入值為 1。
決策邊界(decision boundary)：設輸入向量與權向量的內積為零，可得出 $n+1$ 維的超平面。平面的法向量為 $\mathbf{w}$，並經過 $n+1$ 維輸入空間的原點。法向量指向的輸入空間，其輸出值為$+1$，而與法向量反向的輸入空間，其輸出值則為$-1$。故可知這個超平面定義了決策邊界，並把輸入空間劃分為二。
激勵函數(activation function)：激勵函數代表神經元在什麼輸入情況下，才觸發動作。
2.1 感知器可以「學習」的函數
Consider a 2-input perceptron : It outputs 1 iff $w_0 + w_1x_1 + w_2x_2 > 0$
- Boolean $AND(x_1, x_2)$ : $w_0 = -1.5, w_1 = w_2 = 1$
- Boolean $OR(x_1, x_2)$ : $w_0 = -0.5, w_1 = w_2 = 1$
- Boolean $XOR(x_1, x_2)$ : Not possible.
With real-valued inputs, can implement only linearly separable functions.
2.2 感知器演算法 Perceptron Learning Algorithm (PLA)
感知器演算法基本上是一種「知錯就改」演算法，感知器算法實際上是在不斷「猜測」正確的權重w和偏移量b，使h(x)越來越接近目標函式。
PLA錯誤糾正主要是下面兩步，for t = 0,1,...
- 找到$w_t$產生的一個錯誤點：
$sign(w_t^Tx_{n(t)}) \neq y_{n(t)}$
(注意這裡x_n的下標不是值維度，而是數據點的編號。y_{n(t)}指第t次更新後的一個分類錯誤點) - 用下面的方法更正這個錯誤：
$w_{t+1} \leftarrow w_t + y_{n(t)}x_{n(t)}$
感知器演算法的特性
- 錯誤驅動(error-driven)：當我們訓練這個算法時，只要輸出值是正確的，這個算法就不會進行任何數據的調整。反之，當輸出值與實際值異號，這個算法就會自動調整參數的比重。
- 實時(online)：逐一處理每一條數據，而不是進行批處理(batch)。
[補充] Batch-Incremental vs. Instance-Incremental Learning
- Instance-Incremental: Update the model with new training examples as soon as they are available.
- Naive Bayes
- Hoeffding Decision Trees
- Neural Networks
- k-Nearest Neighbour (model based on a moving window)
- Batch-Incremental: Collect w training examples, then build a batch model with these examples (and drop an old model when memory is full), and repeat.
- Logistic Regression Decision Trees
- Support Vector Machines etc.

三、反傳遞演算法 (Back-Propagation) 與 梯度下降法 (Gradient descent)
一個「多層感知器」模型中包含「輸入層、隱藏層與輸出層」，這種多層感知器與「單層感知器」的一個不同點在於擁有一個隱藏層，因此其能力增強了很多。而反傳遞演算法是一種梯度下降法，只要能計算出梯度的方向，就能讓「多層感知器」的權重朝著能量下降最快的方向前進。
3.1 梯度下降法 Gradient Descent
我們需要在向量空間中搜索最合適的權值向量，我們需要有一定的規則指導我們的搜索，採用沿著梯度方向往下走的方法，就稱為「梯度下降法」(Gradient Descent)。，這種方法可以說是一種「貪婪演算法」(Greedy Algorithm)，因為它每次都朝著最斜的方向走去，企圖得到最大的下降幅度。
為了要計算梯度，我們不能採用不可微分的 sign() 步階函數」，因為這樣就不能用微積分的方式計算出梯度了，而必須改用可以微分的連續函數 sigmoid()，這樣才能夠透過微分計算出梯度。
首先我們來定義輸出誤差，即對於任意一組權值向量，那它得到的輸出和我們預想的輸出之間的誤差值。定義誤差的方法很多，不同的誤差計算方法可以得到不同的權值更新法則，這裡我們先用這樣的定義：
$E(\vec{w})=\frac{1}{2}\sum_{d \in D}(t_d-o_d)^2$
上面公式中$D$代表了所有的輸入實例，或者說是樣本，$d$代表了一個樣本實例，$o_d$表示感知器的輸出，$t_d$代表我們預想的輸出。
這樣，我們的目標就明確了，就是想找到一組權值讓這個誤差的值最小，顯然我們用誤差對權值求導將是一個很好的選擇，導數的意義是提供了一個方向，沿著這個方向改變權值，將會讓總的誤差變大，更形象的叫它為梯度。在直覺概念上，曲面上某一點的梯度，其實是曲面在該點切平面的法向量。
$\nabla E(w_i)=\frac{\partial E}{\partial w}=\frac{1}{2}\frac{\partial \sum_{d \in D}(t_d-o_d)^2}{\partial w_i}=\frac{1}{2}\sum_{d \in D}\frac{\partial (t_d-o_d)^2}{\partial w_i}$
既然梯度確定了E最陡峭的上升的方向，那麼梯度下降的訓練法則是：
$\vec{w_i} \gets \vec{w_i}+\Delta \vec{w_i}，其中\Delta \vec{w_i}=-\eta \frac{\partial E}{\partial w_i}$
3.2 隨機梯度下降
梯度下降是一種重要最優化算法，但在應用它的時候通常會有兩個問題：
1）有時收斂過程可能非常慢；
2）如果誤差曲面上有多個局極小值，那麼不能保證這個過程會找到全局最小值。
為了解決上面的問題，實際中我們應用的是梯度下降的一種變體被稱為隨機梯度下降。上面公式中的誤差是針對於所有訓練樣本而得到的，而隨機梯度下降的思想是根據每個單獨的訓練樣本來更新權值，這樣我們上面的梯度公式就變成了：
$\frac{\partial E}{\partial w_i}=\frac{1}{2}\frac{\partial (t-o)^2}{\partial w_i}=-(t-o)\frac{\partial o}{\partial w_i}$
經過推導後，我們就可以得到最終的權值更新的公式：
$w_i=w_i+\Delta w_i \\ \delta=(t-o)o(1-o) \\ \Delta w_i=\eta \delta x_i$
有了上面權重的更新公式後，我們就可以通過輸入大量的實例樣本，來根據我們預期的結果不斷地調整權值，從而最終得到一組權值使得我們的SIGMOID能夠對一個新的樣本輸入得到正確的或無限接近的結果。
[注意] 梯度下降法的缺點
- 靠近極小值時速度減慢
- 直線搜索可能會產生問題
- 可能會「之」字型下降。
下面這個例子也鮮明的示例了"之字"的上升（非下降），這個例子用梯度上升（非梯度下降）法求 $F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)$ 的極大值（非極小值，實際是局部極大值）。
3.3 The backpropagation algorithm
The backpropagation equations provide us with a way of computing the gradient of the cost function. Let's explicitly write this out in the form of an algorithm :
in details :
How the backpropagation algorithm works
Backpropagation Hung-yi Lee
3.3 Expressiveness of ANNs
- Any Boolean function can be represented by a network with a single hidden layer
- Any bounded continuous function can be approximated with arbitrarily small error by a net with one hidden layer.
- Any function can be approximated to arbitrary accuracy by a net with two hidden layers.
References
Wiki - 感知器
Allan's Workspace - 機器學習入門 - 感知器 (Perceptron)
機器學習算法 原理、實現與實踐 —— 感知機與梯度下降
http://www.cnblogs.com/ronny/p/ann_01.html
陳鍾誠 / 教科書 / 人工智慧 實作：多層感知器與反傳遞演算法
http://ccc.nqu.edu.tw/db/ai/backprop.html
類神經網路、語意相似度(一個不嫌少、兩個恰恰好)
http://www.slideshare.net/chickenrun/ss-33780038
藍林鳥的博客 - 感知器與PLA算法
http://www.ramlinbird.com/%E6%84%9F%E7%9F%A5%E5%99%A8%E4%B8%8Epla%E7%AE%97%E6%B3%95/
發表文章
