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