感知機(jī)（perceptron）是二類(lèi)分類(lèi)的線(xiàn)性分類(lèi)模型，其輸入為實(shí)例的特征向量，輸出為實(shí)例的類(lèi)別，取+1和-1二值。感知機(jī)對(duì)應(yīng)于輸入空間中將實(shí)例劃分為正負(fù)兩類(lèi)的分離超平面，屬于判別模型。感知機(jī)學(xué)習(xí)旨在求出將訓(xùn)練數(shù)據(jù)進(jìn)行線(xiàn)性劃分的分離超平面，為此導(dǎo)入了基于誤分類(lèi)的損失函數(shù)，利用梯度下降法對(duì)損失函數(shù)進(jìn)行極小化，求得感知機(jī)模型。感知機(jī)學(xué)習(xí)算法具有簡(jiǎn)單而易于實(shí)現(xiàn)的優(yōu)點(diǎn)，分為原始形式和對(duì)偶形式。感知機(jī)是神經(jīng)網(wǎng)絡(luò)與支持向量機(jī)的基礎(chǔ)。
劃重點(diǎn)：簡(jiǎn)單說(shuō)就是個(gè)二分類(lèi)的線(xiàn)性分類(lèi)模型,感知機(jī)學(xué)習(xí)，就是通過(guò)訓(xùn)練數(shù)據(jù)集，求得感知機(jī)模型，即求的模型參數(shù)。
感知機(jī)模型
- 由輸入空間到輸出空間的如下函數(shù)稱(chēng)為感知機(jī)：
=sign(w.x+b))w叫做權(quán)值（weight）或權(quán)值向量，b叫做偏置(bias)。
感知機(jī)模型的原理：給每一個(gè)屬性一個(gè)權(quán)重w,對(duì)屬性值和權(quán)重的乘積求和，將這個(gè)值和一個(gè)閥值(0/1)進(jìn)行比較，可以判定比如是否錄用這個(gè)應(yīng)聘者。
感知機(jī)的幾何解釋?zhuān)壕€(xiàn)性方程.
線(xiàn)性分類(lèi)器的幾何表示：直線(xiàn)、平面、超平面。
- 對(duì)應(yīng)于特征空間Rn中的一個(gè)超平面S，其中w是超平面的法向量[注]，b是超平面的截距。這個(gè)超平面將特征空間劃分為兩個(gè)部分，位于兩部分的點(diǎn)分別被分為正、負(fù)兩類(lèi)。因此，超平面S稱(chēng)為分離超平面（separating hyperplanes）。
注：比如在二維平面里，分界是一條直線(xiàn)的情形下，y=wTx，那么分界線(xiàn)對(duì)應(yīng)的y取值都是0，此時(shí)對(duì)于這條線(xiàn)來(lái)說(shuō)，w就是分界線(xiàn)的法向量。
感知機(jī)是咋學(xué)習(xí)的，為啥說(shuō)它是知錯(cuò)能改？
1>假設(shè)數(shù)據(jù)集線(xiàn)性可分，感知機(jī)的學(xué)習(xí)目標(biāo)是求得一個(gè)能夠?qū)⒂?xùn)練集正實(shí)例點(diǎn)和負(fù)實(shí)例點(diǎn)完全正確分開(kāi)的超平面。為了找到這個(gè)超平面，即確定感知機(jī)模型參數(shù)w，b，需要確定一個(gè)學(xué)習(xí)策略，即定義（經(jīng)驗(yàn)）損失函數(shù)并將損失函數(shù)極小化。
損失函數(shù)的一個(gè)自然選擇是誤分類(lèi)點(diǎn)的總數(shù)，但是損失函數(shù)不是w，b的連續(xù)可導(dǎo)函數(shù)，不易優(yōu)化。損失函數(shù)的另一個(gè)選擇是計(jì)算誤分類(lèi)點(diǎn)到超平面的總距離。 輸入空間中任一點(diǎn)x0x0到超平面S的距離為：
感知機(jī)sign(w.x+b)學(xué)習(xí)的損失函數(shù)定義為(重點(diǎn))：
一個(gè)特定樣本的損失函數(shù)，在誤分類(lèi)的時(shí)候該函數(shù)是w和b的線(xiàn)性函數(shù)，而正確分類(lèi)的時(shí)候是0，因此損失函數(shù)時(shí)w和b的連續(xù)可導(dǎo)函數(shù)。
劃重點(diǎn)：感知機(jī)學(xué)習(xí)策略就是在假設(shè)空間中選取使感知機(jī)的損失函數(shù)最小的模型參數(shù)w和b，即感知機(jī)模型。
2>感知機(jī)學(xué)習(xí)算法轉(zhuǎn)化為求解感知機(jī)損失函數(shù)的最優(yōu)化問(wèn)題，最優(yōu)化的方法是隨機(jī)梯度下降法。
學(xué)習(xí)算法：
輸入：訓(xùn)練數(shù)據(jù)集T、學(xué)習(xí)率α
輸出：w,b；感知機(jī)模型f(x)=sign(w.x + b)
(1)選取初值w0,b0
(2)在訓(xùn)練集中選取數(shù)據(jù)(xi,yi)
(3)如果yi(w.xi + b) <= 0，使用隨機(jī)梯度下降法更新w和b
(4)轉(zhuǎn)至(2)，直至訓(xùn)練集中沒(méi)有誤分類(lèi)點(diǎn)（重復(fù)的將誤分類(lèi)的點(diǎn)一直更新）
任意選取一個(gè)超平面w0,b0w0,b0，然后用梯度下降法不斷地極小化目標(biāo)函數(shù)
隨機(jī)選取一個(gè)誤分類(lèi)點(diǎn)(xi,yi)(xi,yi)，對(duì)w,b進(jìn)行更新：
其中η是步長(zhǎng)，又稱(chēng)為學(xué)習(xí)速率。這樣通過(guò)迭代可以期待損失函數(shù)L(w,b)不斷減小，直到0.
這種學(xué)習(xí)算法直觀(guān)上解釋?zhuān)寒?dāng)一個(gè)實(shí)例類(lèi)被誤分類(lèi)，即位于分離超平面的錯(cuò)誤一側(cè)時(shí)，則調(diào)整w,b的值，使分離超平面向該分類(lèi)點(diǎn)的一側(cè)移動(dòng)，以減少該誤分類(lèi)點(diǎn)與超平面的距離，直至超平面越過(guò)該誤分類(lèi)點(diǎn)使其被正確分類(lèi)。
-
剛開(kāi)始，隨便一點(diǎn)，開(kāi)始兩個(gè)相同類(lèi)型連線(xiàn)即法向量，作垂線(xiàn)得到初始的分類(lèi)平面(線(xiàn))
初始(來(lái)源：臺(tái)灣國(guó)立大學(xué)林老師課程) -
當(dāng)檢測(cè)到錯(cuò)誤后，通過(guò)旋轉(zhuǎn)開(kāi)始修正，得到優(yōu)化的分類(lèi)
-
不斷檢測(cè)，直到?jīng)]有錯(cuò)誤
最后
但是這個(gè)PLA算法真的會(huì)停嗎？
分兩種情況討論：數(shù)據(jù)線(xiàn)性可分；數(shù)據(jù)線(xiàn)性不可分
注意PLA 停止的條件是，對(duì)任何數(shù)據(jù)分類(lèi)都正確，顯然數(shù)據(jù)線(xiàn)性不可分時(shí)PLA 無(wú)法停止，那么我們可以用Pocket算法，運(yùn)用貪心思想找到一個(gè)比較好的。
數(shù)據(jù)線(xiàn)性可分:
一定存在完美的w(記為wf)， 使得所有的(xi, yi), yi = sign(wf*xi).可知：
下面證明在數(shù)據(jù)線(xiàn)性可分時(shí)，簡(jiǎn)單的感知機(jī)算法會(huì)收斂。（這個(gè)是根據(jù)林老師的定義給的，我感覺(jué)比較清晰，詳細(xì)的可以看《統(tǒng)計(jì)學(xué)習(xí)方法》第二章）
而且量向量夾角余弦值不會(huì)大于1，可知T 的值有限。T=1，即向量?jī)?nèi)積為1，兩向量重合，由此，我們證明了簡(jiǎn)單的PLA 算法可以收斂。
數(shù)據(jù)線(xiàn)性不可分：
Pocket Algorithm當(dāng)數(shù)據(jù)線(xiàn)性不可分時(shí)（存在噪音），簡(jiǎn)單的PLA 算法顯然無(wú)法收斂。我們要討論的是如何得到近似的結(jié)果。我們希望盡可能將所有結(jié)果做對(duì)，即：
尋找wg 是一個(gè)NP-hard 問(wèn)題！只能找到近似解。算法如下：
與簡(jiǎn)單PLA 的區(qū)別：迭代有限次數(shù)（提前設(shè)定）；隨機(jī)地尋找分錯(cuò)的數(shù)據(jù)（而不是循環(huán)遍歷）；只有當(dāng)新得到的w 比之前得到的最好的wg 還要好時(shí)，才更新wg（這里的好指的是分出來(lái)的錯(cuò)誤更少）。由于計(jì)算w 后要和之前的wg 比較錯(cuò)誤率來(lái)決定是否更新wg， 所以pocket algorithm 比簡(jiǎn)單的PLA 方法要低效。
關(guān)于對(duì)偶形式以及兩種算法代碼實(shí)現(xiàn)可以參見(jiàn)：
感知機(jī)-碼農(nóng)場(chǎng)
Reference：
《統(tǒng)計(jì)學(xué)習(xí)方法》第二章
《機(jī)器學(xué)習(xí)基石》臺(tái)灣國(guó)立大學(xué)第8，9
