0
雷鋒網按：本文原作者射命丸咲，原載于其知乎專欄Python與機器學習。
（這里是本章會用到的 Jupyter Notebook 地址）
感知機是個相當簡單的模型，但它既可以發展成支持向量機（通過簡單地修改一下損失函數）、又可以發展成神經網絡（通過簡單地堆疊），所以它也擁有一定的地位
為方便，我們統一討論二分類問題，并將兩個類別的樣本分別稱為正、負樣本
感知機能做什么？
感知機能（且一定能）將線性可分的數據集分開。什么叫線性可分？在二維平面上、線性可分意味著能用一條線將正負樣本分開，在三維空間中、線性可分意味著能用一個平面將正負樣本分開。可以用兩張圖來直觀感受一下線性可分（上圖）和線性不可分（下圖）的概念：
那么一個感知機將會如何分開線性可分的數據集呢？下面這兩張動圖或許能夠給觀眾老爺們一些直觀感受：
看上去挺捉急的，不過我們可以放心的是：只要數據集線性可分，那么感知機就一定能 “蕩” 到一個能分開數據集的地方（文末會附上證明）
那么反過來，如果數據集線性不可分，那么感知機將如何表現？相信聰明的觀眾老爺們已經猜到了：它將會一直 “蕩來蕩去”（最后停了是因為到了迭代上限）（然后貌似動圖太大導致有殘影…… 不過效果也不差所以就將就著看一下吧 ( σ'ω')σ）：
如何搭建感知機模型？
為了搭建感知機模型，我們需要知道高維數據的線性可分是指什么。為此我們需要定義 “超平面” 的概念：
其中 w、x 都是 n 維向量，Π 則是 Rn 中的超平面。對于二維平面來說 n=2，上式就可以化為：
此即直線方程。有了 Rn 中超平面的定義后，線性可分的概念也就清晰了：對于一個數據集
（xi為輸入，yi為標簽），如果存在一個超平面Π，能夠將D中正負樣本（對于某個樣本（xi，yi），若 yi =1 則稱其為正樣本，若 yi =-1 則稱其為負樣本，且標簽 yi 只能取正負 1 這兩個值）分開，那么就稱 D 是線性可分的。否則，就稱是線性不可分的。
對于感知機模型來說，以上的這些信息就足夠了。事實上，感知機模型只有 w 和 b 這兩個參數，我們要做的就是根據樣本的信息來逐步更新 w 和 b、從而使得對應的超平面 Π 能夠分開 D。
如何訓練感知機模型？
上一節已經說過，感知機模型只有 w 和 b 這兩個參數，其中 w 是一個 n 維向量（
）、則是一個標量（
）。為了保證收斂性，我們需要將 w 初始化為零向量、將 b 初始化為 0：
class Perceptron: def __init__(self): self._w = self._b = None def fit(self, x, y, lr=0.01, epoch=1000): # 將輸入的 x、y 轉為 numpy 數組 x, y = np.asarray(x, np.float32), np.asarray(y, np.float32) self._w = np.zeros(x.shape[1]) self._b = 0
上面這個 fit 函數中有個 lr 和 epoch，它們分別代表了梯度下降法中的學習速率和迭代上限
（p.s. 由后文的推導我們可以證明，對感知機模型來說、其實學習速率設為多少都無關緊要）
梯度下降法我們都比較熟悉了。簡單來說，梯度下降法包含如下兩步：
求損失函數的梯度（求導）
梯度是函數值增長最快的方向我們想要最小化損失函數我們想讓函數值減少得最快將參數沿著梯度的反方向走一步
（這也是為何梯度下降法有時被稱為最速下降法的原因。梯度下降法被普遍應用于神經網絡、卷積神經網絡等各種網絡中，如有興趣、可以參見這篇文章）
那么對于感知機模型來說，損失函數是什么呢？注意到我們感知機對應的超平面為
而我們的樣本為正負樣本，一個自然的想法就是：
（x，y）是正樣本
（x，y）是負樣本
（從幾何直觀來說，上述定義等價為 “（x，1）在的Π上方”、“（x，-1）在Π的下方”）
注意我們前文提到過
（x，y）是正樣本
（x，y）是負樣本
那么一個樸素的損失函數L（x，y）就比較容易寫出來了：
若
，則
若
，則
綜上所述、就有：
損失函數可寫為
（x，y）被正確分類
從而易知只有錯分類的點才會給 L（x，y）貢獻梯度（因為正確分類的點及其 “周圍” 的 L（x，y）的值為常數 0，從而梯度為 0）。所以訓練感知機時，我們只需挑選使得損失函數 L（x，y）最大的一個樣本（xi，yi）、用它來計算梯度、然后梯度下降即可（注意如果（xi，yi）是被正確分類的話，說明所有樣本都已被正確分類，所以此時應該停止模型的訓練【事實上也訓練不動了……】）
由于 L（x，y）的形式簡潔，所以其求導是平凡的（注意對錯分類（xi，yi）樣本而言，
）：
體現在代碼上即為：
for _ in range(epoch): # 計算 w·x+b y_pred = x.dot(self._w) + self._b # 選出使得損失函數最大的樣本 idx = np.argmax(np.maximum(0, -y_pred * y)) # 若該樣本被正確分類，則結束訓練 if y[idx] * y_pred[idx] > 0: break # 否則，讓參數沿著負梯度方向走一步 delta = lr * y[idx] self._w += delta * x[idx] self._b += delta
至此，感知機模型就大致介紹完了，剩下的則是一些純數學的東西，大體上不看也是沒問題的（趴。
相關數學理論
從數學的角度來說，線性可分性還有一個比較直觀的等價定義：正負樣本點集的凸包彼此不交。所謂凸包的定義如下：若集合
由N個點組成：
那么 S 的凸包 conv(S) 即為：
比如，上文給出過的兩個二維數據集的凸包將如下圖所示：
左圖正負樣本點集的凸包不交、所以數據集線性可分，右圖的橙色區域即為正負樣本點集凸包的相交處、所以數據集線性不可分。
該等價性的證明可以用反證法得出：
1）線性可分 → 凸包不交：線性可分意味著存在 w* 和 b*，使得
對任意
成立。如果凸包相交的話，就意味著存在某個樣本（x*，y*）、使得x*既是正樣本輸入數據的線性組合、又是負樣本輸入數據的線性組合：
從而
（式 1）
注意到：
yi=1 時
，
yi=-1 時，
所以（注意由凸包的定義我們有
且
）
這與式 1 矛盾。
2）凸包不交 → 線性可分：嚴謹證明需要用到一些奇怪的東西，這里就只提供一個（非常）不嚴謹的直觀說明（歡迎觀眾老爺們提供更好的證明，現在這個說明我看上去覺得很像是錯的）（喂）：在正樣本點集凸包的邊界上取一個離負樣本點集凸包 “最近” 的點x*(1)并假設負樣本點集凸包邊界上離x*(1)“最近” 的點為x*(2)。過x*(1)畫一個超平面
、使得Π與x*(1)、x*(2)的連線垂直。由凸包的幾何性質可知此時（除了x*(1)外）正樣本點集都被分到了Π的同一側、且x*(2)是離Π“最近” 的點，這樣只需把Π稍微往負樣本點集那邊挪一點（什么鬼！）就行了。
然后是前文遺留下來的、感知機模型收斂性的證明。我們知道感知機對應的超平面為：
將其展開的話、就是
所以我們可以將其改寫為
其中
如果數據集線性可分的話，就意味著存在
、使得對任意
、都有
；注意到
的 scale 不影響超平面、所以我們不妨假設
。同時由于數據集D中的樣本是有限的，所以這又意味著
、使得總有
。
現在我們初始化
為 0 向量（
），并開始感知機模型的訓練（假設現在是第k步）：
1）假設
已經將所有樣本正確分類，則已證畢。
2）否則，取被
誤分類的樣本
，進行參數的更新：
。由此易知（注意
）：
且
（式 2）
注意
是被誤分類的、且yi只能取正負 1，所以
、
，從而由式 2 可以推出：
從而
亦即訓練步數k是有上界的，這意味著收斂性。而且
中不含學習速率η，這說明對感知機模型來說、學習速率設為多少都無關緊要。
最后簡單介紹一個非常重要的概念：拉格朗日對偶性（Lagrange Duality）。我們在前三小節介紹的感知機算法，其實可以稱為 “感知機的原始算法”；而利用拉格朗日對偶性，我們可以得到感知機算法的對偶形式。鑒于拉格朗日對偶性的原始形式太過純數學，所以我打算結合具體的算法來介紹、而不打算敘述其原始形式，感興趣的觀眾老爺可以參見這里。
在有約束的最優化問題中，為了便于求解、我們常常會利用它來將比較原始問題轉化為更好解決的對偶問題。對于特定的問題，原始算法的對偶形式也常常會有一些共性存在。比如對于感知機和后文會介紹的支持向量機來說，它們的對偶算法都會將模型的參數表示為樣本點的某種線性組合、并把問題轉化為求解線性組合中的各個系數。
雖說感知機算法的原始形式已經非常簡單，但是通過將它轉化為對偶形式、我們可以比較清晰地感受到轉化的過程，這有助于理解和記憶后文介紹的、較為復雜的支持向量機的對偶形式。
考慮到原始算法的核心步驟為：
其中
、E是當前被誤分類的樣本點的集合；可以看見、參數的更新是完全基于樣本點的。考慮到我們要將參數w和b表示為樣本點的線性組合，一個自然的想法就是記錄下在核心步驟中、各個樣本點分別被利用了多少次、然后利用這個次數來將w和b表示出來。比如說，若設樣本點
一共在上述核心步驟中被利用了ni次、那么就有（假設初始化參數時
）：
如果進一步設
，則有：
此即感知機模型的對偶形式。需要指出的是，在對偶形式中、樣本點里面的x僅以內積的形式（
）出現；這是一個非常重要且深刻的性質，利用它和后文將進行介紹核技巧、能夠將許多算法從線性算法 “升級” 成為非線性算法。
注意到對偶形式的訓練過程常常會重復用到大量的、樣本點之間的內積，我們通常會提前將樣本點兩兩之間的內積計算出來并存儲在一個矩陣中；這個矩陣就是著名的 Gram 矩陣、其數學定義即為：
從而在訓練過程中如果要用到相應的內積、只需從 Gram 矩陣中提取即可，這樣在大多數情況下都能大大提高效率。
雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。
