感知機是怎麼實現「知錯能改」的？

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

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

感知機模型

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

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

感知機模型的原理：給每一個屬性一個權重w,對屬性值和權重的乘積求和，將這個值和一個閥值(0/1)進行比較，可以判定比如是否錄用這個應聘者。

感知機的幾何解釋：線性方程.

線性分類器的幾何表示：直線、平面、超平面。

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

註：比如在二維平面里，分界是一條直線的情形下，y=wTx，那麼分界線對應的y取值都是0，此時對於這條線來說，w就是分界線的法向量。

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

1. 假設數據集線性可分，感知機的學習目標是求得一個能夠將訓練集正實例點和負實例點完全正確分開的超平面。為了找到這個超平面，即確定感知機模型參數w，b，需要確定一個學習策略，即定義（經驗）損失函數並將損失函數極小化。

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

任一點到超平面距離

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

損失函數

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

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

2. 感知機學習演算法轉化為求解感知機損失函數的最優化問題，最優化的方法是隨機梯度下降法。

學習演算法：

輸入：訓練數據集T、學習率α

輸出：w,b；感知機模型f(x)=sign(w.x + b)

(1) 選取初值w0,b0

(2) 在訓練集中選取數據(xi,yi)

(3) 如果yi(w.xi + b)

(4) 轉至(2)，直至訓練集中沒有誤分類點（重複的將誤分類的點一直更新）

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

梯度

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

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

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

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

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

當檢測到錯誤後，通過旋轉開始修正，得到優化的分類

不斷檢測，直到沒有錯誤

最後

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

分兩種情況討論：數據線性可分；數據線性不可分

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

數據線性可分:

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

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

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

數據線性不可分：

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

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

Pocket Algorithm

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

Reference：

《統計學習方法》第二章

《機器學習基石》台灣國立大學第8，9

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！