演算法的收斂性證明

1. 感知機演算法及收斂性證明

感知機演算法其實已經很熟悉了，這次看《統計學習方法》權當復習一遍，然後有一橘念個point對我來說是新的—— 感知機演算法實際上採用了隨機梯度下降 。這其實是一個很顯然的點，但我之前看到的資料都是直接說明了超平面參數的更新方式，並從幾何直觀上解釋了這樣做是為了讓超平面向誤分樣本點的方向旋轉，而未從梯度的角度來解釋，這里補充一下這個角度。

感知機（perceptron）是二分類線性分類模型，其輸入空間（特徵空間）是 ，輸出空間是 ，前伍簡由輸入空間到輸出空間的如下函數：

稱為感知機。 和 分別是感知機的權值和偏置。

感知機的損失函數定義為 所有誤分類點到超平面的距離慧褲之和 ，即：

其中 表示誤分類點的集合，若 固定，則損失函數梯度為：

採用隨機梯度下降法，每次隨機選取一個誤分類點 ，對 進行更新：

其中 稱為學習率。

感知機演算法流程如下：

（1）選取初值 。
（2）在訓練集中選取數據 。
（3）如果 ,則更新參數：

（4）轉至（2）直至訓練集中無誤分點。

所謂感知機演算法的收斂性，就是說只要給定而分類問題是線性可分的，那麼按上述感知機演算法進行操作，在有限次迭代後一定可以找到一個可將樣本完全分類正確的超平面。

首先，為了方便推導，我們將偏置 並入權重向量 ,記作 ，同樣將輸入向量加以擴充，記作 ，顯然， 。

既然樣本是線性可分的，我們可以假設有一個滿足條件 的超平面 將樣本點完全正確分開，且存在 ，對所有 ，有：

令 ，則感知機演算法在訓練集上誤分類次數 滿足：

證明：

結合上述兩個結論，可以得到：

從而感知機演算法的收斂性得證。