歡迎大家關(guān)注公眾號(hào)【哈希大數(shù)據(jù)】
感知機(jī)可以說是最古老的分類方法之一了，在1957年就已經(jīng)提出乓梨。今天看來它的分類模型在大多數(shù)時(shí)候泛化能力不強(qiáng)鳖轰，但是它的原理卻值得好好研究。因?yàn)檠芯客噶烁兄獧C(jī)模型扶镀，學(xué)習(xí)支持向量機(jī)的話會(huì)降低不少難度蕴侣。同時(shí)如果研究透了感知機(jī)模型，再學(xué)習(xí)神經(jīng)網(wǎng)絡(luò)臭觉，深度學(xué)習(xí)昆雀，也是一個(gè)很好的起點(diǎn)。這里對(duì)感知機(jī)的原理做一個(gè)小結(jié)蝠筑。
1. 感知機(jī)模型
　感知機(jī)的思想很簡(jiǎn)單忆肾，比如我們?cè)谝粋€(gè)平臺(tái)上有很多的男孩女孩，感知機(jī)的模型就是嘗試找到一條直線菱肖，能夠把所有的男孩和女孩隔離開客冈。放到三維空間或者更高維的空間，感知機(jī)的模型就是嘗試找到一個(gè)超平面稳强，能夠把所有的二元類別隔離開场仲。當(dāng)然你會(huì)問和悦，如果我們找不到這么一條直線的話怎么辦？找不到的話那就意味著類別線性不可分渠缕，也就意味著感知機(jī)模型不適合你的數(shù)據(jù)的分類鸽素。使用感知機(jī)一個(gè)最大的前提，就是數(shù)據(jù)是線性可分的亦鳞。這嚴(yán)重限制了感知機(jī)的使用場(chǎng)景馍忽。它的分類競(jìng)爭(zhēng)對(duì)手在面對(duì)不可分的情況時(shí)，比如支持向量機(jī)可以通過核技巧來讓數(shù)據(jù)在高維可分燕差，神經(jīng)網(wǎng)絡(luò)可以通過激活函數(shù)和增加隱藏層來讓數(shù)據(jù)可分遭笋。
用數(shù)學(xué)的語言來說，如果我們有m個(gè)樣本徒探，每個(gè)樣本對(duì)應(yīng)于n維特征和一個(gè)二元類別輸出瓦呼，如下：
　(x₁⁽⁰⁾,x₂⁽⁰⁾,...x_n⁽⁰⁾,y₀), (x₁⁽¹⁾,x₂⁽¹⁾,...x_n⁽¹⁾,y₁),...
(x₁^(m),x₂^(m),...x_n^(m),y_m)
我們的目標(biāo)是找到這樣一個(gè)超平面：
θ₀+θ₁x₁+...+θ_nx_n=0
讓其中一種類別的樣本都滿足θ₀+θ₁x₁+...+θ_nx_n >0,讓另一種類別的樣本都滿足θ₀+θ₁x₁+...+θ_nx_n<0 .
從而得到線性可分。如果數(shù)據(jù)線性可分测暗，這樣的超平面一般都不是唯一的央串，也就是說感知機(jī)模型可以有多個(gè)解。
為了簡(jiǎn)化這個(gè)超平面的寫法碗啄，我們?cè)黾右粋€(gè)特征
x₀=1 质和，這樣超平面為

image

image

image

image

image

其中M是所有誤分類的點(diǎn)的集合。這是一個(gè)凸函數(shù)矾麻，可以用梯度下降法或者擬牛頓法來解決纱耻，常用的是梯度下降法。
但是用普通的基于所有樣本的梯度和的均值的批量梯度下降法（BGD）是行不通的险耀，原因在于我們的損失函數(shù)里面有限定弄喘，只有誤分類的M集合里面的樣本才能參與損失函數(shù)的優(yōu)化。所以我們不能用最普通的批量梯度下降,只能采用隨機(jī)梯度下降（SGD）或者小批量梯度下降（MBGD）甩牺。如果對(duì)這幾種梯度下降法的區(qū)別不了解蘑志，可以參考我的另一篇文章梯度下降（Gradient Descent）小結(jié)。
感知機(jī)模型選擇的是采用隨機(jī)梯度下降贬派，這意味著我們每次僅僅需要使用一個(gè)誤分類的點(diǎn)來更新梯度急但。

image

1. 定義所有x0為1裆熙。選擇θ向量的初值和 步長(zhǎng)α的初值。可以將θ向量置為0向量入录，步長(zhǎng)設(shè)置為1齐媒。要注意的是，由于感知機(jī)的解不唯一纷跛，使用的這兩個(gè)初值會(huì)影響θ向量的最終迭代結(jié)果喻括。
   (x1(i),x2(i),...xn(i),yi) , 用向量表示即(x(i),y(i))，這個(gè)點(diǎn)應(yīng)該滿足：y(i)θ?x(i)<0
2. 對(duì)θ向量進(jìn)行一次隨機(jī)梯度下降的迭代：
   θ=θ+αy(i)x(i)
   4）檢查訓(xùn)練集里是否還有誤分類的點(diǎn)贫奠，如果沒有唬血，算法結(jié)束，此時(shí)的θ向量即為最終結(jié)果唤崭。如果有拷恨，繼續(xù)第2步。
   5. 感知機(jī)模型的算法對(duì)偶形式
   上一節(jié)的感知機(jī)模型的算法形式我們一般稱為感知機(jī)模型的算法原始形式谢肾。對(duì)偶形式是對(duì)算法執(zhí)行速度的優(yōu)化腕侄。具體是怎么優(yōu)化的呢？
   通過上一節(jié)感知機(jī)模型的算法原始形式
   θ=θ+αy⁽ⁱ⁾x⁽ⁱ⁾
   可以看出芦疏，我們每次梯度的迭代都是選擇的一個(gè)樣本來更新θ向量冕杠。最終經(jīng)過若干次的迭代得到最終的結(jié)果。對(duì)于從來都沒有誤分類過的樣本酸茴，他被選擇參與θ迭代的次數(shù)是0分预，對(duì)于被多次誤分類而更新的樣本j，它參與θ迭代的次數(shù)我們?cè)O(shè)置為mj薪捍。如果令θ向量初始值為0向量笼痹， 這樣我們的θ向量的表達(dá)式可以寫為：
   
   image
   
   其中mj為樣本(x^(j),y^(j))在隨機(jī)梯度下降到當(dāng)前的這一步之前因誤分類而更新的次數(shù)。
   每一個(gè)樣本(x^(j),y^(j))的mj的初始值為0酪穿，每當(dāng)此樣本在某一次梯度下降迭代中因誤分類而更新時(shí)凳干，mj 的值加1。
   由于步長(zhǎng)α為常量被济，我們令β_j=αm_j,這樣θ向量的表達(dá)式為:
   
   image
   
   在每一步判斷誤分類條件的地方救赐，我們用 y⁽ⁱ⁾θ?x⁽ⁱ⁾<0 的變種:
   來判斷誤分類。
   注意到這個(gè)判斷誤分類的形式里面是計(jì)算兩個(gè)樣本x(i)和x(j)的內(nèi)積溉潭，而且這個(gè)內(nèi)積計(jì)算的結(jié)果在下面的迭代次數(shù)中可以重用净响。如果我們事先用矩陣運(yùn)算計(jì)算出所有的樣本之間的內(nèi)積少欺，那么在算法運(yùn)行時(shí)喳瓣， 僅僅一次的矩陣內(nèi)積運(yùn)算比多次的循環(huán)計(jì)算省時(shí)。 計(jì)算量最大的判斷誤分類這兒就省下了很多的時(shí)間赞别，畏陕，這也是對(duì)偶形式的感知機(jī)模型比原始形式優(yōu)的原因。
   樣本的內(nèi)積矩陣稱為Gram矩陣仿滔，它是一個(gè)對(duì)稱矩陣惠毁，記為 G=[x⁽ⁱ⁾?x^(j)]
   這里給出感知機(jī)模型的算法對(duì)偶形式的內(nèi)容犹芹。
   算法的輸入為m個(gè)樣本，每個(gè)樣本對(duì)應(yīng)于n維特征和一個(gè)二元類別輸出1或者-1鞠绰，如下：
   (x₁⁽⁰⁾,x₂⁽⁰⁾,...x_n⁽⁰⁾,y₀), (x₁⁽¹⁾,x₂⁽¹⁾,...x_n⁽¹⁾,y₁),...
   (x₁^(m),x₂^(m),...x_n^(m),y_m)
   輸出為分離超平面的模型系數(shù)θ向量
   算法的執(zhí)行步驟如下：
3. 定義所有x₀為1腰埂，步長(zhǎng)α初值，設(shè)置β的初值0蜈膨∮炝可以將α設(shè)置為1。要注意的是翁巍，由于感知機(jī)的解不唯一驴一，使用的步長(zhǎng)初值會(huì)影響θ向量的最終迭代結(jié)果。
4. 計(jì)算所有樣本內(nèi)積形成的Gram矩陣G灶壶。
   3） 在訓(xùn)練集里面選擇一個(gè)誤分類的點(diǎn)(x⁽ⁱ⁾,y⁽ⁱ⁾)肝断，這個(gè)點(diǎn)應(yīng)該滿足：
   
   image
   
   在檢查是否滿足時(shí)可以通過查詢Gram矩陣的gij 的值來快速計(jì)算是否小于0。
5. 對(duì)β向量的第i個(gè)分量進(jìn)行一次更新：β_i=β_i+α
   5）檢查訓(xùn)練集里是否還有誤分類的點(diǎn)驰凛，如果沒有胸懈，算法結(jié)束，此時(shí)的θ向量最終結(jié)果為下式恰响。如果有箫荡，繼續(xù)第2步。
   其中β_j 為β向量的第j個(gè)分量渔隶。
   5. 小結(jié)
   感知機(jī)算法是一個(gè)簡(jiǎn)單易懂的算法羔挡，自己編程實(shí)現(xiàn)也不太難。前面提到它是很多算法的鼻祖间唉，比如支持向量機(jī)算法绞灼，神經(jīng)網(wǎng)絡(luò)與深度學(xué)習(xí)。因此雖然它現(xiàn)在已經(jīng)不是一個(gè)在實(shí)踐中廣泛運(yùn)用的算法呈野，還是值得好好的去研究一下低矮。感知機(jī)算法對(duì)偶形式為什么在實(shí)際運(yùn)用中比原始形式快，也值得好好去體會(huì)被冒。