Zi 字媒體

Python機器學習演算法入門之簡單感知器學習演算法

2021/12/25

yidianzixun

復旦大數據

❈

ZZR，Python中文社區專欄作者，OpenStack工程師，曾經的NLP研究者。主要興趣方向：OpenStack、Python爬蟲、Python數據分析。

Blog：

考慮一個問題：現在我們有一些過往核發信用卡的資料，包括用戶個人信息和審核結果。根據這些資料，我們希望預測能不能給下一個用戶發信用卡。用戶基本信息如下：

這些基本信息組成了一個向量。不同的信息有不同的權重，設權重向量。我們希望構造一個函數來給用戶的信用打分，並且，如果信用分超過了某個閾值，我們就認為這個客戶是可靠的，可以給他發信用卡：

能發：

不能：

通過階躍函數，進一步將這個過程函數化：

所以，當，通過；當，拒絕；當，忽略。

其中：

整理該方程如下：

具體到二維空間簡化上面的問題，假設用戶只有兩個屬性，就可以用二維空間的一個點來表示一個用戶。如下所示，藍圈表示通過，紅叉表示拒絕。注意到直線的兩邊，一邊大於0，一邊小於0，也就是一邊都是藍圈，一邊都是紅叉。所以現在的目標就是，找到一條直線，可以將已知的藍圈和紅叉完美區分開。

基礎知識回顧

簡單回顧一下線性代數的知識。一條直線可以由一個點和法向量唯一確定。其點法式方程為：。相應地，其方向向量為：

感知機學習演算法

簡單感知機演算法（Perceptron Learning Algorithm，PLA）的思路很簡單，首先隨便找一條直線，然後遍歷每一個已知點，如果正確，則跳過；如果錯誤，則利用這個點的信息對直線進行修正。修正的思路如上圖所示：是直線的法向量。是錯誤點的方向向量，是真實值。具體情況可分為如下兩種情況：

為了將這個出錯的點包括進紫色區域，應該靠近方向。因此，。

為了將這個出錯的點排除出紫色區域，應該遠離方向。因此，。

綜上，得到修正函數：

那麼為什麼感知機演算法可以逐步接近正確呢？

已知兩邊同時乘上和，得：

因為，所以：注意到恰好就是我們給出的當前用戶的分數。當，也就是我們打分打低了，修正後分數上升；當，也就是我們打分打高了，修正後分數下降。這個結論說明，對於這組錯誤數據，經過修正以後，我們打出的分數更靠近正確結果了。

證明：PLA終止的充分條件

從演算法的規則上可以看出，PLA終止的必要條件是數據集中確定存在一條直線，可以將藍圈和紅叉分開，也就是線性可分：

現在證明，線性可分是PLA終止的充分條件。

（1）設表示第t次更新時的點，一共更新了n次。若線性可分，則必然存在一條完美的直線，使得對，有。也就是：

（為向量內積，也就是）又由的更新規則得：

因此：

綜上，得到：

初始時，所以：

（2）因為每次遇到錯誤的數據才會更新，也就是。其中是第t次更新時的權重值。因此：

（3）綜上，得：

是一個常數，因此，隨著t的增大，也逐步增大，也就是向量和的夾角逐漸減小，逐漸接近。

又因為：，所以。因此，PLA演算法必然收斂。Linear Pocket Algorithm上述PLA演算法的前提是數據集線性可分。但是很明顯，在分類之前我們不可能知道我們手裡的數據是不是線性可分的。更何況，數據集可能有雜訊（noise），這些雜訊是之前的經驗中錯誤的分類結果，這些雜訊將導致PLA無法收斂。因此，我們的目標就從找到一條完美劃分數據集的，變成了找到一條最接近完美，使得錯誤的點最少。這個轉變使得我們可以理非線性可分的數據集：