知錯能改的感知機(jī)(Perceptron)

本文作者： UqRai

2017-05-25 10:34

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

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

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

感知機(jī)模型

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

知錯能改的感知機(jī)(Perceptron)

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

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

知錯能改的感知機(jī)(Perceptron)

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

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

感知機(jī)是咋學(xué)習(xí)的，為啥說它是知錯能改？

1. 假設(shè)數(shù)據(jù)集線性可分，感知機(jī)的學(xué)習(xí)目標(biāo)是求得一個能夠?qū)⒂?xùn)練集正實(shí)例點(diǎn)和負(fù)實(shí)例點(diǎn)完全正確分開的超平面。為了找到這個超平面，即確定感知機(jī)模型參數(shù)w，b，需要確定一個學(xué)習(xí)策略，即定義（經(jīng)驗(yàn)）損失函數(shù)并將損失函數(shù)極小化。

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

知錯能改的感知機(jī)(Perceptron)

任一點(diǎn)到超平面距離

感知機(jī)sign(w.x+b)學(xué)習(xí)的損失函數(shù)定義為(重點(diǎn))：

知錯能改的感知機(jī)(Perceptron)

損失函數(shù)

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

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

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

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

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

知錯能改的感知機(jī)(Perceptron)

梯度

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

知錯能改的感知機(jī)(Perceptron)

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

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

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

知錯能改的感知機(jī)(Perceptron)

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

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

知錯能改的感知機(jī)(Perceptron)

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

知錯能改的感知機(jī)(Perceptron)

最后

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

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

知錯能改的感知機(jī)(Perceptron)

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

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

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

知錯能改的感知機(jī)(Perceptron)

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

知錯能改的感知機(jī)(Perceptron)

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

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

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

知錯能改的感知機(jī)(Perceptron)

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

知錯能改的感知機(jī)(Perceptron)

Pocket Algorithm

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