知錯能改的感知機(Perceptron)

本文作者： UqRai

2017-05-25 10:34

導語：一篇關(guān)于感知機的深度科普。

感知機（perceptron）是二類分類的線性分類模型，其輸入為實例的特征向量，輸出為實例的類別，取+1和-1二值。感知機對應于輸入空間中將實例劃分為正負兩類的分離超平面，屬于判別模型。感知機學習旨在求出將訓練數(shù)據(jù)進行線性劃分的分離超平面，為此導入了基于誤分類的損失函數(shù)，利用梯度下降法對損失函數(shù)進行極小化，求得感知機模型。感知機學習算法具有簡單而易于實現(xiàn)的優(yōu)點，分為原始形式和對偶形式。感知機是神經(jīng)網(wǎng)絡與支持向量機的基礎(chǔ)。

劃重點：簡單說就是個二分類的線性分類模型,感知機學習，就是通過訓練數(shù)據(jù)集，求得感知機模型，即求的模型參數(shù)。

感知機模型

由輸入空間到輸出空間的如下函數(shù)稱為感知機：

知錯能改的感知機(Perceptron)

w叫做權(quán)值（weight）或權(quán)值向量，b叫做偏置(bias)。

感知機模型的原理：給每一個屬性一個權(quán)重w,對屬性值和權(quán)重的乘積求和，將這個值和一個閥值(0/1)進行比較，可以判定比如是否錄用這個應聘者。
感知機的幾何解釋：線性方程.
線性分類器的幾何表示：直線、平面、超平面。

知錯能改的感知機(Perceptron)

對應于特征空間Rn中的一個超平面S，其中w是超平面的法向量[注]，b是超平面的截距。這個超平面將特征空間劃分為兩個部分，位于兩部分的點分別被分為正、負兩類。因此，超平面S稱為分離超平面（separating hyperplanes）。

雷鋒網(wǎng)注：比如在二維平面里，分界是一條直線的情形下，y=wTx，那么分界線對應的y取值都是0，此時對于這條線來說，w就是分界線的法向量。

感知機是咋學習的，為啥說它是知錯能改？

1. 假設數(shù)據(jù)集線性可分，感知機的學習目標是求得一個能夠?qū)⒂柧毤龑嵗c和負實例點完全正確分開的超平面。為了找到這個超平面，即確定感知機模型參數(shù)w，b，需要確定一個學習策略，即定義（經(jīng)驗）損失函數(shù)并將損失函數(shù)極小化。

損失函數(shù)的一個自然選擇是誤分類點的總數(shù)，但是損失函數(shù)不是w，b的連續(xù)可導函數(shù)，不易優(yōu)化。損失函數(shù)的另一個選擇是計算誤分類點到超平面的總距離。輸入空間中任一點x0x0到超平面S的距離為：

知錯能改的感知機(Perceptron)

任一點到超平面距離

感知機sign(w.x+b)學習的損失函數(shù)定義為(重點)：

知錯能改的感知機(Perceptron)

損失函數(shù)

一個特定樣本的損失函數(shù)，在誤分類的時候該函數(shù)是w和b的線性函數(shù)，而正確分類的時候是0，因此損失函數(shù)時w和b的連續(xù)可導函數(shù)。

劃重點：感知機學習策略就是在假設空間中選取使感知機的損失函數(shù)最小的模型參數(shù)w和b，即感知機模型。

2. 感知機學習算法轉(zhuǎn)化為求解感知機損失函數(shù)的最優(yōu)化問題，最優(yōu)化的方法是隨機梯度下降法。

學習算法：
輸入：訓練數(shù)據(jù)集T、學習率α
輸出：w,b；感知機模型f(x)=sign(w.x + b)
(1) 選取初值w0,b0
(2) 在訓練集中選取數(shù)據(jù)(xi,yi)
(3) 如果yi(w.xi + b) <= 0，使用隨機梯度下降法更新w和b
(4) 轉(zhuǎn)至(2)，直至訓練集中沒有誤分類點（重復的將誤分類的點一直更新）

任意選取一個超平面w0,b0w0,b0，然后用梯度下降法不斷地極小化目標函數(shù)

知錯能改的感知機(Perceptron)

梯度

隨機選取一個誤分類點 (xi,yi)(xi,yi)，對 w,b 進行更新：

知錯能改的感知機(Perceptron)

其中 η 是步長，又稱為學習速率。這樣通過迭代可以期待損失函數(shù) L(w,b) 不斷減小，直到 0.

這種學習算法直觀上解釋：當一個實例類被誤分類，即位于分離超平面的錯誤一側(cè)時，則調(diào)整w,b的值，使分離超平面向該分類點的一側(cè)移動，以減少該誤分類點與超平面的距離，直至超平面越過該誤分類點使其被正確分類。

剛開始，隨便一點，開始兩個相同類型連線即法向量，作垂線得到初始的分類平面(線)

知錯能改的感知機(Perceptron)

初始(來源：臺灣國立大學林老師課程)

當檢測到錯誤后，通過旋轉(zhuǎn)開始修正，得到優(yōu)化的分類

知錯能改的感知機(Perceptron)

不斷檢測，直到?jīng)]有錯誤

知錯能改的感知機(Perceptron)

最后

但是這個PLA算法真的會停嗎？

分兩種情況討論：數(shù)據(jù)線性可分；數(shù)據(jù)線性不可分

知錯能改的感知機(Perceptron)

注意PLA 停止的條件是，對任何數(shù)據(jù)分類都正確，顯然數(shù)據(jù)線性不可分時PLA 無法停止，那么我們可以用Pocket算法，運用貪心思想找到一個比較好的。

數(shù)據(jù)線性可分:

一定存在完美的w(記為wf)，使得所有的(xi, yi), yi = sign(wf*xi).可知：

知錯能改的感知機(Perceptron)

下面證明在數(shù)據(jù)線性可分時，簡單的感知機算法會收斂。（這個是根據(jù)林老師的定義給的，我感覺比較清晰，詳細的可以看《統(tǒng)計學習方法》第二章）

知錯能改的感知機(Perceptron)

而且量向量夾角余弦值不會大于1，可知T 的值有限。T=1，即向量內(nèi)積為1，兩向量重合，由此，我們證明了簡單的PLA 算法可以收斂。

數(shù)據(jù)線性不可分：

Pocket Algorithm當數(shù)據(jù)線性不可分時（存在噪音），簡單的PLA 算法顯然無法收斂。我們要討論的是如何得到近似的結(jié)果。我們希望盡可能將所有結(jié)果做對，即：

知錯能改的感知機(Perceptron)

尋找 wg 是一個NP-hard 問題！只能找到近似解。算法如下：

知錯能改的感知機(Perceptron)

Pocket Algorithm

與簡單PLA 的區(qū)別：迭代有限次數(shù)（提前設定）；隨機地尋找分錯的數(shù)據(jù)（而不是循環(huán)遍歷）；只有當新得到的w 比之前得到的最好的wg 還要好時，才更新wg（這里的好指的是分出來的錯誤更少）。由于計算w 后要和之前的wg 比較錯誤率來決定是否更新wg，所以pocket algorithm 比簡單的PLA 方法要低效。