感知機學習演算法

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

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

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

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

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

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

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

其中 稱為學習率。

感知機演算法流程如下：

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

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

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

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

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

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

證明：

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

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

Ⅱ 感知機的收斂性

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

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

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

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

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

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

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

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

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

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

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

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

迭代時進行如下更新：

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

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

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

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

Ⅲ 神經網路演算法

20 世紀五、六⼗年代，科學家 Frank Rosenblatt其受到 Warren McCulloch 和 Walter Pitts早期的⼯作的影響，發明了感知機（Perceptrons）。

⼀個感知器接受⼏個⼆進制輸⼊， ，並產⽣⼀個⼆進制輸出：

如上圖所示的感知機有三個輸⼊： 。通常可以有更多或更少輸⼊。 我們再引⼊權重： ，衡量輸入對輸出的重要性。感知機的輸出為0 或者 1，則由分配權重後的總和 ⼩於等於或者⼤於閾值決定。和權重⼀樣，閾值（threshold）是⼀個實數，⼀個神經元的參數。⽤更精確的代數形式如下：

給三個因素設置權重來作出決定：

可以把這三個因素對應地⽤⼆進制變數 來表⽰。例如，如果天⽓好，我們把

，如果不好， 。類似地，如果你的朋友陪你去， ，否則 。 也類似。

這三個對於可能對你來說，「電影好不好看」對你來說最重要，而天氣顯得不是那麼的重要。所以你會這樣分配權值： ，然後定義閾值threshold=5。

現在，你可以使⽤感知器來給這種決策建⽴數學模型。

例如：

隨著權重和閾值的變化，你可以得到不同的決策模型。很明顯，感知機不是⼈做出決策使⽤的全部模型。但是這個例⼦說明了⼀個感知機如何能權衡不同的依據來決策。這看上去也可以⼤致解釋⼀個感知機⽹絡有時確實能夠做出一些不錯的決定。

現在我們隊上面的結構做一點變化，令b=-threshold，即把閾值移到不等號左邊，變成偏置， 那麼感知器的規則可以重寫為:

引⼊偏置只是我們描述感知器的⼀個很⼩的變動，但是我們後⾯會看到它引導更進⼀步的符號簡化。因此，我們不再⽤閾值，⽽總是使⽤偏置。

感知機是首個可以學習的人工神經網路，它的出現引起的神經網路的第一層高潮。需要指出的是，感知機只能做簡單的線性分類任務，而且Minsky在1969年出版的《Perceptron》書中，證明了感知機對XOR（異或）這樣的問題都無法解決。但是感知機的提出，對神經網路的發展是具有重要意義的。

通過上面的感知機的觀察我們發現一個問題，每個感知機的輸出只有0和1，這就意味著有時我們只是在單個感知機上稍微修改了一點點權值w或者偏置b，就可能造成最終輸出完全的反轉。也就是說，感知機的輸出是一個階躍函數。如下圖所示，在0附近的時候，輸出的變化是非常明顯的，而在遠離0的地方，我們可能調整好久參數也不會發生輸出的變化。

這樣階躍的跳變並不是我們想要的，我們需要的是當我們隊權值w或者偏置b做出微小的調整後，輸出也相應的發生微小的改變。這同時也意味值我們的輸出不再只是0和1，還可以輸出小數。由此我們引入了S型神經元。

S型神經元使用 S 型函數，也叫Sigmoid function函數，我們用它作為激活函數。其表達式如下：

圖像如下圖所示：

利⽤實際的 σ 函數，我們得到⼀個，就像上⾯說明的，平滑的感知器。 σ 函數的平滑特性，正是關鍵因素，⽽不是其細部形式。 σ 的平滑意味著權重和偏置的微⼩變化，即 ∆w 和 ∆b，會從神經元產⽣⼀個微⼩的輸出變化 ∆output。實際上，微積分告訴我們

∆output 可以很好地近似表⽰為：

上面的式子是⼀個反映權重、偏置變化和輸出變化的線性函數。這⼀線性使得我們可以通過選擇權重和偏置的微⼩變化來達到輸出的微⼩變化。所以當 S 型神經元和感知器本質上是相同的，但S型神經元在計算處理如何變化權重和偏置來使輸出變化的時候會更加容易。

有了對S型神經元的了解，我們就可以介紹神經網路的基本結構了。具體如下：

在⽹絡中最左邊的稱為輸⼊層，其中的神經元稱為輸⼊神經元。最右邊的，即輸出層包含有輸出神經元，在圖中，輸出層只有⼀個神經元。中間層，既然這層中的神經元既不是輸⼊也不是輸出，則被稱為隱藏層。

這就是神經網路的基本結構，隨著後面的發展神經網路的層數也隨之不斷增加和復雜。

我們回顧一下神經網路發展的歷程。神經網路的發展歷史曲折盪漾，既有被人捧上天的時刻，也有摔落在街頭無人問津的時段，中間經歷了數次大起大落。

從單層神經網路（感知機）開始，到包含一個隱藏層的兩層神經網路，再到多層的深度神經網路，一共有三次興起過程。詳見下圖。

我們希望有⼀個演算法，能讓我們找到權重和偏置，以⾄於⽹絡的輸出 y(x) 能夠擬合所有的 訓練輸⼊ x。為了量化我們如何實現這個⽬標，我們定義⼀個代價函數：

這⾥ w 表⽰所有的⽹絡中權重的集合， b 是所有的偏置， n 是訓練輸⼊數據的個數，
a 是表⽰當輸⼊為 x 時輸出的向量，求和則是在總的訓練輸⼊ x 上進⾏的。當然，輸出 a 取決於 x, w和 b，但是為了保持符號的簡潔性，我沒有明確地指出這種依賴關系。符號 ∥v∥ 是指向量 v 的模。我們把 C 稱為⼆次代價函數；有時也稱被稱為均⽅誤差或者 MSE。觀察⼆次代價函數的形式我們可以看到 C(w, b) 是⾮負的，因為求和公式中的每⼀項都是⾮負的。此外，代價函數 C(w,b)的值相當⼩，即 C(w; b) ≈ 0，精確地說，是當對於所有的訓練輸⼊ x， y(x) 接近於輸出 a 時。因

此如果我們的學習演算法能找到合適的權重和偏置，使得 C(w; b) ≈ 0，它就能很好地⼯作。相反，當 C(w; b) 很⼤時就不怎麼好了，那意味著對於⼤量地輸⼊， y(x) 與輸出 a 相差很⼤。因此我們的訓練演算法的⽬的，是最⼩化權重和偏置的代價函數 C(w; b)。換句話說，我們想要找到⼀系列能讓代價盡可能⼩的權重和偏置。我們將采⽤稱為梯度下降的演算法來達到這個⽬的。

下面我們將代價函數簡化為C(v)。它可以是任意的多元實值函數， 。
注意我們⽤ v 代替了 w 和 b 以強調它可能是任意的函數，我們現在先不局限於神經⽹絡的環境。

為了使問題更加簡單我們先考慮兩個變數的情況，想像 C 是⼀個只有兩個變數 和 的函數，我們的目的是找到 和 使得C最小。

如上圖所示，我們的目的就是找到局部最小值。對於這樣的一個問題，一種方法就是通過微積分的方法來解決，我們可以通過計算導數來求解C的極值點。但是對於神經網路來說，我們往往面對的是非常道的權值和偏置，也就是說v的維數不只是兩維，有可能是億萬維的。對於一個高維的函數C(v)求導數幾乎是不可能的。

在這種情況下，有人提出了一個有趣的演算法。想像一下一個小球從山頂滾下山谷的過程， 我們的⽇常經驗告訴我們這個球最終會滾到⾕底。我們先暫時忽略相關的物理定理， 對球體的⾁眼觀察是為了激發我們的想像⽽不是束縛我們的思維。因此與其陷進物理學⾥凌亂的細節，不如我們就這樣問⾃⼰：如果我們扮演⼀天的上帝，能夠構造⾃⼰的物理定律，能夠⽀配球體可以如何滾動，那麼我們將會採取什麼樣的運動學定律來讓球體能夠總是滾落到⾕底呢？

為了更精確地描述這個問題，讓我們思考⼀下，當我們在 和 ⽅向分別將球體移動⼀個很⼩的量，即 ∆ 和 ∆ 時，球體將會發⽣什麼情況。微積分告訴我們 C 將會有如下變化：

也可以用向量表示為

現在我們的問題就轉換為不斷尋找一個小於0的∆C，使得C+∆C不斷變小。

假設我們選取：

這⾥的 η 是個很⼩的正數（稱為學習速率），於是

由於 ∥∇C∥2 ≥ 0，這保證了 ∆C ≤ 0，即，如果我們按照上述⽅程的規則去改變 v，那麼 C
會⼀直減⼩，不會增加。

所以我們可以通過不斷改變v來C的值不斷下降，是小球滾到最低點。

總結⼀下，梯度下降演算法⼯作的⽅式就是重復計算梯度 ∇C，然後沿著相反的⽅向移動，沿著⼭⾕「滾落」。我們可以想像它像這樣：

為了使梯度下降能夠正確地運⾏，我們需要選擇合適的學習速率η，確保C不斷減少，直到找到最小值。

知道了兩個變數的函數 C 的梯度下降方法，我們可以很容易的把它推廣到多維。我們假設 C 是⼀個有 m 個變數 的多元函數。 ∆C 將會變為：

其中， ∇C為

∆v為：

更新規則為：

在回到神經網路中，w和b的更新規則為：

前面提到神經⽹絡如何使⽤梯度下降演算法來學習他們⾃⾝的權重和偏置。但是，這⾥還留下了⼀個問題：我們並沒有討論如何計算代價函數的梯度。這里就需要用到一個非常重要的演算法：反向傳播演算法（backpropagation）。

反向傳播演算法的啟示是數學中的鏈式法則。

四個方程：

輸出層誤差方程：

當前層誤差方程：

誤差方程關於偏置的關系：

誤差方程關於權值的關系

演算法描述：

檢視這個演算法，你可以看到為何它被稱作反向傳播。我們從最後⼀層開始向後計算誤差向量δ。這看起來有點奇怪，為何要從後⾯開始。但是如果你認真思考反向傳播的證明，這種反向移動其實是代價函數是⽹絡輸出的函數的結果。為了理解代價隨前⾯層的權重和偏置變化的規律，我們需要重復作⽤鏈式法則，反向地獲得需要的表達式。

參考鏈接： http://neuralnetworksanddeeplearning.com/

Ⅳ 感知機（Perceptron）

在之前的文章中我們已經講過了邏輯回歸分類器，現在趁熱打鐵總結一下與邏輯回歸非常相似的感知機模型。感知機模型是一個非常古老的分類演算法，現在很少會單獨使用它，但是它的原理簡單有效，很值得學習和理解，從原理上來說，感知機模型是神經網路和支持向量機的基礎，理解了感知機有利於理解支持向量機和神經網路的原理。

在 廣義線性模型（4）邏畝旁輯回歸 中我們說邏輯回歸可以視為包含一個線性回歸和一個值域映射兩個過程，如果拿邏輯回歸與感知機作比較的話，可以說感知機也同樣包括這兩個過程，只不過它的值域映射比邏輯回歸簡單很多，感知機直接將線性模型的輸出映射為+1和-1，即需要預測的兩個類別上，正可謂簡單粗暴。所以說，感知機也是線性模型，用來處理線性可分的二分類問題，同樣屬於判別模型。

感知機假設數據線性可分的，希望通過學習得到一個線性的決策邊界，將訓練數據集正樣本點和負樣本點完全正確分開的分離，在決策邊界一側為正樣本，另一側為負樣本，這個思路跟邏輯回歸是一樣的。

感知機模型可以表示為下式，其中 函數將線性模型的輸出映射為預測類別：

由點到超平面的距離計算方法可知： 代表了樣本點到決策邊界的距離（文章沒有用 的形式，拋棄了常數項的問題，其實是不準確的，若有看官，還請不要介意）；

同時我們可知， 的樣本類別輸出值取為1，滿足 的樣本類別輸出值取為-1，因此正確分類的樣本滿足 ，而錯誤分類的樣本滿足 ， 表示了錯誤分類的樣本到決策超平面的距離，感知機損失函數的優化目標，就是期望使錯誤分類的所有樣本到超平面的距離之和最小（正樣本+1，負樣本-1這樣的定義方式使得定義損失函數變得很方便），損失函數為：

式中，M為樣本中所有錯誤分類樣本點的集合。實際上，我們會把損失函數中參數的L2正則項 扔掉，認為它不會影響優化結果，即得到損失函數：

為什麼可以不考慮 呢？ 搜索解空間的時候， 會一直在變化啊？我覺得這個挺難理解的，根據資料及猜測，我覺得勉強能接受的原因為：

確定了損失函數的形式，接下來就要進行損失函數的優化，還是使用梯度下降，由於損失函數中只有錯誤分類的樣本點才參與計算，所以不需要使用普通的批量梯度下降了，我們選擇使用 隨機梯度下降 ， 每次迭代只使用一個錯誤分類的樣本來對參數進行更新 。

感知機的學習演算法的原始形式即直接使用梯度下降，其學習過程為：

可以發現，在原始形式中，每一輪迭代都需要判斷各個樣本點是不是錯誤分類點，既對於每個樣本點 都需要計算 ，向量內積 的時間復雜度為 ，因此總的時間復雜度為 ，其中N為樣本點數量，k為迭代次數（雖然每次迭代不需要全部遍歷N個樣本，不過表達時間復雜度時可以去掉因子保留變數，表示成 ），這個時間復雜度還是比較高的，有沒有更快捷的計算方法呢？我們來看看感知機的學習演算法的對偶形式。

什麼叫對偶形式？這里的對偶可不是「三尺劍，六鈞弓」的意思，優化理論中的對偶問題是指每一個線性規劃問題（稱為原始問題）有一迅余橡個與它對應的對偶線性規劃問題（稱為對偶問題），原始問題與對偶問題的解是對應的，得出一個問題的解，另一個問題的解也就得到了，可以簡單的理解為從不同角度看待同一個問題，通過改變這個問題的形式使得我們更好求解。

根據感知機學習演算法的原始形式可知，只有錯誤分類的樣本點才會用於梯度下降計算，對於被 次誤分類而更新的樣本 ，它參與 迭代的次數同樣為 。如果令參數 初始值為 ， 這樣我們的 的表達毀汪式可以寫為：

表示對全部樣本 中的每個個樣本點進行 次梯度下降，其中沒被錯誤分類過的樣本點 。引用知乎上一個答案對 的理解：

這樣參數 的學習問題就轉變成了樣本錯誤分類次數 的學習問題，此之謂「對偶」也。這樣做的好處是什麼呢？原始形式的痛點在於 中的內積運算，在對偶問題中轉變為：

由內積 轉變為內積 ，區別是 是已知的，可以提前通過矩陣運算得到Gram矩陣保存下來重用，樣本循環和迭代的時間復雜度不變， 個 維向量的內積計算提前，所以時間復雜度大概可以表示為 ，與 倒不太好比較，不過這里按矩陣運算的時間復雜度完全沒有優化來計算的，實際肯定比這小得多，並且工程上矩陣運算都是高度優化過的，非常快，所以對偶形式在使用效率上是很有優勢的。

對偶形式的學習過程為：

感知機演算法原理很簡單，但其中很多思路很棒，所以由它發展出了神經網路、支持向量機這樣的更復雜、更准確的演算法，搞懂了感知機模型的基本原理，接下來我們就來寫一寫跟它很相似的支持向量機~

主要參考

《統計學習方法》 李航
感知機的損失函數為什麼可以採用函數間隔(忽略1/||w||)?
如何理解感知機學習演算法的對偶形式？