演算法收斂證明

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

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

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

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

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

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

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

其中 稱為學習率。

感知機演算法流程如下：

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

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

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

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

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

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

證明：

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

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

② 感知機的收斂性

感知機是最基礎的機器學習模型之一，它的類別為：

該模型本質上是雹叢嫌在輸入空間定義了一個分離超平面： ， 為該超平面的法向量， 為該超平面的截距。該超平面將輸入空間劃分為兩部分，位於兩側的點（輸入數據）分別屬於正負兩類。
給定一個線性可分的訓練樣本集，通過尋找合適的 和 使得訓練樣本集的數據被正確劃分到超平面的兩側，該過程即感知機模型的訓練過程。
這里有一個前提「訓練樣本集線性可分」，即對於訓練樣本集： ，其中， ，若存在某超平面 ，使得 ，則稱 為線性可分數據集。

為了尋找能正確劃分訓練樣本集的超平面，需要定義損失函數，並將損失函數極小化。如何度量損失呢？如下圖所示，有A、B、C三點，表示三個樣本，都在分離超平面的正側，距離分離超平面的距離依次減小。距離越遠，預測為正類的確信度越大，反之則不那麼確信。

在超平面 確定的情況下， 能夠相對地表示點 距離超平面的遠近，而 的符號與類標記 的符號是否一致能夠表示分類是否正確。所以可以用 來表示分類的正確性與確信度，這就是函數間隔（functional margin）的概念。
設 為 上被超平面 誤分類的所有點的集合，則
按照機器學習約定俗成的慣例，損失函數為正，對損失函數求極小值。因此，我們將感知機的損失函數定義為 上所有被誤分類的點到超平面 的函數間隔的絕對值，即：
感知機的學習策略是在假設空間中選取使上式最小的分離超平面系數 和 。

感知機的學習問題可轉化為求解使損失函數最小的最優化問題，即求參數 ，使其為以下極小化問題的解。
其中，M為誤分類點的集合。求解該問題可使用梯度下降演算法。
損失函數 的梯度為：

如果樣本集非常大，梯度下降演算法每輪迭代都要計算全局梯度，這需要耗費非常大的計算資源，實際應用中通常使用隨機梯度下降演算法代替，即每次隨機選取一個誤分類點 ，對 沿梯度負方向更新。

其中 為步長，又叫做學習率。隨機梯度的期望為全局梯度，因此其收斂性與梯度下降演算法一致。通過不斷迭代以上步驟，可以期待損失函數 不斷減小，直到為0.
該演算法的直觀理解為：當一個實例點被誤分類，調整 的值，使分離超鄭肆平面向該誤分類點移動，減小該誤分類點與超平面的距離，直至超平面越過該點，使其被正確分類。
該演算法在訓練開始時需要選取一個初始分類超平面 ，經過 輪迭代後：

其中， 為第 輪迭代時隨機選取的誤分類點。當 時，第 輪迭代時的超平面方程為：

可以看出，學習速率 可以被約去，說明當 時，演算法收斂速度與 無關。下面證明感知機訓練演算法收斂性，證明過程可進一步驗證該結論。

證明感知機訓練演算法是收斂的，即證明訓練過程可在有限輪迭代內完成，即迭代次數 存在一個上界。
為了便於敘述，將偏置 並入權重向量 ，記作 ，同時對輸入向量 進行擴充，記作 ，顯然 。

證明：
訓練數據集線性可分，則存在能將數據集完全正確分開的分離超平面，對任一滿足源手要求的分離超平面 ，存在 ，對所有 ：

初始時， ，隨機選取某樣本，若被誤分類，則更新權重。令 是第 次迭代時的擴充權重向量，此次迭代隨機選擇的第 個誤分類樣本滿足條件：

迭代時進行如下更新：

聯合(2)(4)式，有：

聯合(3)(4)式，有：

聯合(5)(6)式，有：

定理得證。
從(7)式可知，迭代次數 存在上界，這說明當訓練數據集線性可分時，感知機學習演算法是收斂的。
進一步地，通過調整 可以改變 的取值。演算法經過 次迭代結束後得到分離超平面 ，由(1)式可知， ，令 ，則可使得 ，從而得到感知機迭代次數收斂上界的精簡形式：