《淺析感知機（三）--收斂性證明與對偶形式以及python代碼講解》

01-29

繼上篇《淺析感知機（二）--學習演算法及python代碼剖析》 - 知乎專欄感知機學習演算法以及python實現講完之後，其實感知機的知識大部分已經講完，這篇文章可以收尾一下，講解一下感知機的對偶形式，以及證明一下為什麼在迭代有限次的時候可以收斂等知識。

下文目錄如下：

1.感知機學習演算法的收斂性證明

2.感知機學習演算法的對偶形式

3.為什麼引出引出對偶形式

4.對偶形式python代碼講解

5.感知機內容的總結

推薦閱讀方式：結合前面講過的淺析感知機（一）--模型與學習策略 - 知乎專欄

《淺析感知機（二）--學習演算法及python代碼剖析》 - 知乎專欄

以及李航博士的《統計學習方法》一起閱讀，效果較好！

一：感知機學習演算法的收斂性

我們需要證明經過有限次迭代可以得到一個將訓練數據集完全正確劃分的分離超平面及感知機模型。（證明了，我們心裡才有底，否則都不知道是否能夠保證收斂）

開始：

我們會有以下定理：

設訓練數據集T={(x1,y1),(x2,y2),...,(xn,yn)}是線性可分的，則下面倆個定理成立：

由上面定理可以得到，直白來說，如果是一個線性可分的數據集，我是可以在有限次k更新，得到一個將數據集完美分割好的超平面（感知機模型）。下面給出證明：（前方數學證明預警，這裡默認收斂性成立也是可以的，不影響應用）

定理一證明如下：

定理二證明如下：

友情提示，可能不是太清楚，但是只要仔細跟著去看，一定能夠看懂。把收斂性的證明該注意的地方全部寫到了。（完全按李航博士書籍順序講解）

那麼我們可以得到結論，誤分類的次數k是有上界的，當訓練數據集線性可分的時候，感知機學習演算法原始迭代是收斂的！（證明了演算法是對的，可行的）

二：感知機學習演算法的對偶形式

對偶形式就是將參數w，b表示為實例xi和標記yi的線性組合的形式，通過求解其係數而求得w和b,對誤分類點進行更新，我們假設初始值w0,b0均為0，對誤分類點(xi,yi)通過：

這裡， $alpha _{i}$ 當 $eta$ =1的時候，它就表示第i個實例點由於誤分而進行的更新的次數，實例點更新次數越多，意味著它距離分離超平面越近，也就越難正確分類（越容易分錯，超平面一動不多就容易將這些點分錯），換句話說，這樣的實例對學習結果影響最大（在支持向量機中，這些點代表著支持向量）

那麼我們怎麼得到它的對偶形式呢？將xi,yi表達的w帶入原來感知機模型中，得到下面對偶感知機模型：

根據上面模型方程，我們可以看出與原始感知機模型不同的就是w的形式有所改變，那麼到底為什麼有對偶形式出現了，後面會講原因！

得到下面的對偶形式演算法學習步驟：

這裡的更新說明如下：

$alpha _{i}=n_{i}eta$

則

$alpha _{i+1}=alpha _{i}+eta$ 推出： $n _{i+1}eta = n _{i}eta+eta$ 則 $n_{i+1}=n_{i}+1$

代表的意思為該點如果分錯，那麼更新次數加一，b的更新方式與原感知機模型更新方式一樣。

三：為什麼要引出對偶形式

根據查閱資料，普遍的觀點是以下倆點：

1.從對偶形式學習演算法過程可以看出，樣本點的特徵向量以內積的形式存在於感知機對偶形式的訓練演算法中，凡是涉及到矩陣，向量內積的運算量就非常大（現實中特徵維度很高），這裡我們如果事先計算好所有的內積，存儲於Gram矩陣中，以後碰到更新的點，直接從Gram矩陣中查找即可，相當於我就初始化運算一遍Gram矩陣，以後都是查詢，大大加快了計算速度。

2.跟SVM的對偶形式其實有類似之處（後面講到SVM的時候再說明）

四：對偶形式python代碼講解

首先給出書上一個例子，然後針對這個例子進行編程：

例題2.2：

根據演算法過程，有以下步驟：

最終我們可以將迭代過程中的參數變化寫出如下表所示：

有了演算法邏輯流程，代碼很簡單，下面我們根據這個例子寫出python代碼如下：

分開講解：

首先我們初始化和處理數據，代碼如下：

獲得Gram矩陣，代碼如下：

檢查所有分類點是否分類正確：

按照公式更新參數：

主函數控制邏輯以及控制迭代次數：

代碼結果如下：

與我們例子中是完全對應的！

完整代碼如下：

import numpy as npnn# An example in that book, the training set and parameters sizes are fixedntraining_set = np.array([[[3, 3], 1], [[4, 3], 1], [[1, 1], -1]])nna = np.zeros(len(training_set), np.float)nb = 0.0nGram = Noneny = np.array(training_set[:, 1])nx = np.empty((len(training_set), 2), np.float)nfor i in range(len(training_set)):n x[i] = training_set[i][0]nndef cal_gram():n """n calculate the Gram matrixn :return:n """n g = np.empty((len(training_set), len(training_set)), np.int)n for i in range(len(training_set)):n for j in range(len(training_set)):n g[i][j] = np.dot(training_set[i][0], training_set[j][0])n return gnnndef update(i):n """n update parameters using stochastic gradient descentn :param i:n :return:n """n global a, bn a[i] += 1n b = b + y[i]n print a,bnnn# calculate the judge conditionndef cal(i):n global a, b, x, ynn res = np.dot(a * y, Gram[i])n res = (res + b) * y[i]n return resnn# check if the hyperplane can classify the examples correctlyndef check():n global a, b, x, yn flag = Falsen for i in range(len(training_set)):n if cal(i) <= 0:n flag = Truen update(i)n if not flag:n w = np.dot(a * y, x)n print "RESULT: w: " + str(w) + " b: " + str(b)n return Falsen return Truennnif __name__ == "__main__":n Gram = cal_gram() # initialize the Gram matrixn for i in range(1000):n if not check(): breakn

五：感知機內容的總結

1.感知機是一個二分類學習演算法，是後面神經網路與支持向量機的基礎。它著重考慮是否將所有訓練數據分類正確，而不考慮分的有多好，這是與支持向量機所不同的地方。如圖所示：

在感知機看來，紅色與綠色的模型是一樣好的，但是支持向量機看來，綠色的模型要比紅色的模型要好。

2.感知機模型中，只要給出的數據是線性可分的，那麼我們就能證明在有限次迭代過程中，能夠收斂（有了它，我們心裡才有底，保證了演算法正確性）

3.感知機有它的對偶形式，其實與原始形式很多地方是一樣的，對偶形式的出現為後面支持向量機的對偶形式打了基礎，Gram矩陣的出現也大大減少了我們的計算量！

好，到這裡為止，講完了第一章感知機的相關知識！希望對大家有幫助，歡迎大家指錯交流！

參考：

李航《統計學習方法》

致謝：郭江師兄，曉明師兄，德川，皓宇，繼豪，海濤師兄