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