前言

關(guān)于寫作：

博主（暫且如此自稱）是北京某高校的計(jì)算機(jī)系研究生在讀，入行AI領(lǐng)域時(shí)間不久湃交，正在努力進(jìn)修熟空。最近利用工作之余的時(shí)間正在學(xué)習(xí)李航博士的《統(tǒng)計(jì)學(xué)習(xí)方法》，一方面希望能夠通過寫作整理思路搞莺，另一方面息罗，分享學(xué)習(xí)心得也希望可以和志同道合的小伙伴們共同探討進(jìn)步啦~

github傳送門：

GitHub - wyynevergiveup/Statistical-Learning-Method: 《統(tǒng)計(jì)學(xué)習(xí)方法》--李航實(shí)現(xiàn)學(xué)習(xí)過程中的算法以加深理解

系列文章：

1.《統(tǒng)計(jì)學(xué)習(xí)方法》筆記（一）統(tǒng)計(jì)學(xué)習(xí)及監(jiān)督學(xué)習(xí)概論 - 簡書

2.《統(tǒng)計(jì)學(xué)習(xí)方法》筆記（二）感知機(jī)模型 - 簡書

3.《統(tǒng)計(jì)學(xué)習(xí)方法》筆記（三）K近鄰法 - 簡書

4.《統(tǒng)計(jì)學(xué)習(xí)方法》筆記（四）樸素貝葉斯法 - 簡書

正文

2.1 綜述

模型：感知機(jī)是二分類的線性分類模型，輸入時(shí)實(shí)例的特征向量才沧，輸出是實(shí)例的類別{1迈喉，-1}。感知機(jī)對應(yīng)于特征空間中將實(shí)例劃分為正負(fù)兩類的分離超平面温圆，屬于判別模型挨摸。

策略：感知機(jī)學(xué)習(xí)旨在求出將訓(xùn)練數(shù)據(jù)進(jìn)行線性劃分的分離超平面，為此導(dǎo)入基于誤分類的損失函數(shù)岁歉，利用梯度下降法對損失函數(shù)進(jìn)行極小化油坝，求得感知機(jī)模型。

算法：感知機(jī)算法具有簡單而易實(shí)現(xiàn)的特點(diǎn)刨裆，分為原始形式和對偶形式。

感知機(jī)是1957年由Rosenblatt提出彬檀，是神經(jīng)網(wǎng)絡(luò)與支持向量機(jī)的基礎(chǔ)帆啃。

下面我們將從模型三要素：模型、策略窍帝、算法三個(gè)方面介紹感知機(jī)模型努潘。

2.2 感知機(jī)模型

????本節(jié)我們將介紹什么是感知機(jī)模型，以及如何理解感知機(jī)模型卫袒。

????首先有序，我們在考慮任何問題時(shí)總是希望先將問題形式化僧凤，因此，給出感知機(jī)模型的形式化定義：

感知機(jī)的形式化定義

? ? 感知機(jī)模型的假設(shè)空間是定義在特征空間上的所有線性分類模型压怠，即函數(shù)集合 $\left\{ f | f(x) = w \cdot x + b \right\}$ 。

? ? 那么飞苇，如何理解感知機(jī)模型呢菌瘫？

感知機(jī)模型的幾何解釋

? ? 以上解釋個(gè)人感覺已經(jīng)非常直觀蜗顽，下面我們以二維的情況進(jìn)行具體分析。

????上圖是一個(gè)二維坐標(biāo)系雨让，我們要找到一條直線將兩類樣本分開雇盖，因此可以假設(shè)直線方程為 $y = ax+b$ 。將直線方程變形栖忠，改寫為 $ax-y+b=0$ 崔挖。將直線方程進(jìn)一步改寫成向量相乘的形式：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ????????????????? ?? $(a,-1)\cdot (x,y)^T +b = 0$

????令 $\vec{w} = (a,-1)$ ， $\vec{x} = (x,y)$ 庵寞，方程就改寫為：

? ?????????????????????????????????????????????????? $\vec{w} \cdot \vec{x} +b = 0$

? ? 即狸相，我們的目的就是要找到合適的 $\vec{w}$ 和 $b$ ，使得代入任意正樣本時(shí)皇帮， $\vec{w} \cdot \vec{x} +b >0$ （即位于直線的上方）卷哩，反之，代入任意負(fù)樣本時(shí)属拾， $\vec{w} \cdot \vec{x} +b < 0$ 将谊。其中 $\vec{w}$ 是直線的法向量， $b$ 是直線的截距渐白。當(dāng)輸入的特征空間為3維時(shí)尊浓，要求的是三維空間中的一個(gè)平面，當(dāng)特征空間維度更高時(shí)纯衍，已經(jīng)無法找到一個(gè)幾何名詞去形容分離正負(fù)樣本的”面“了栋齿，因而把它統(tǒng)稱為”超平面“。

那我們要如何求得的 $\vec{w}$ 和 $b$ 呢襟诸？

2.3 感知機(jī)策略

? ? 首先需要明確的是瓦堵，感知機(jī)模型只適用于可以線性可分的數(shù)據(jù)集。數(shù)據(jù)集線性可分性定義如下：

數(shù)據(jù)集線性可分性

? ? 對于線性不可分的數(shù)據(jù)歌亲，單層perceptron將失效菇用，比如，異或關(guān)系（XOR）陷揪。

單層perceptron為什么不能表示XOR

????為了確定模型的參數(shù) $\vec{w}$ 和 $b$ 惋鸥，需要確定一個(gè)學(xué)習(xí)策略，即定義損失函數(shù)并將損失函數(shù)極小化悍缠。

? ? 感知機(jī)模型常采用的損失函數(shù)為所有誤分類點(diǎn)到超平面S的總距離卦绣。首先，特征空間內(nèi)任意一點(diǎn) $x_{0}$ 到超平面S的距離為：

? ?????????????????????????????????????????????????????????????? $\frac{1}{\vert \vert \vec{w} \vert \vert } \vert \vec{w} \cdot \vec{x_0} +b \vert$

? ? 這里 $\vert \vert \vec{w} \vert \vert$ 是 $\vec{w}$ 的 $L_2$ 范數(shù)飞蚓。對于誤分類樣本滤港， $\vec{w} \cdot \vec{x_0} +b$ 與 $y_i$ 異號，且 $|y_i| = 1$ 趴拧，因此蜗搔，誤分類點(diǎn) $x_i$ 到超平面S的距離為：

? ?????????????????????????????????????????????????????????????? $-\frac{1}{\vert \vert \vec{w} \vert \vert } y_i\vert \vec{w} \cdot \vec{x_0} +b \vert$

? ? 這樣劲藐，假設(shè)超平面S的誤分類點(diǎn)集合為M，那么所有誤分類點(diǎn)到超平面S的總距離為：

? ?????????????????????????????????????????????????????????????? $-\frac{1}{\vert \vert \vec{w} \vert \vert } \sum_{x_i \in M} y_i\vert \vec{w} \cdot \vec{x_0} +b \vert$

? ? 而不考慮 $\frac{1}{\vert \vert \vec{w} \vert \vert}$ 樟凄，就得到了感知機(jī)學(xué)習(xí)的損失函數(shù)聘芜。

* 為什么可以不考慮 $\frac{1}{\vert \vert \vec{w} \vert \vert}$ ？

答：1.正系數(shù)不影響優(yōu)化方向缝龄，對于線性可分?jǐn)?shù)據(jù)集最后這個(gè)損失都是0汰现；分母用來歸一化法向量，不歸一化也一樣用叔壤，感知機(jī)的解本身不唯一瞎饲。總結(jié)來說炼绘，這個(gè)系數(shù)只會影響過程而不影響結(jié)果嗅战，去掉這個(gè)系數(shù)可以減少計(jì)算量。

感知機(jī)學(xué)習(xí)的損失函數(shù)

2.4 感知機(jī)算法

? ? 感知機(jī)學(xué)習(xí)算法求解的其實(shí)是最優(yōu)化問題俺亮，問題的形式化表述如下驮捍。

最優(yōu)化問題形式化表述

2.4.1 感知機(jī)學(xué)習(xí)算法的原始形式

????這里提到一個(gè)”隨機(jī)梯度下降“（SGD）的概念，實(shí)際在求解最優(yōu)解的過程中使用的是隨機(jī)梯度下降的方式脚曾，具體使用過程描述如下东且。

隨機(jī)梯度下降

感知機(jī)學(xué)習(xí)算法的原始形式

2.4.2 感知機(jī)學(xué)習(xí)算法的對偶形式

感知機(jī)學(xué)習(xí)算法對偶形式的解釋

具體的算法描述如下。

感知學(xué)習(xí)算法的對偶形式

Gram矩陣：由于對偶形式中訓(xùn)練實(shí)例僅以內(nèi)積形式出現(xiàn)本讥。為了方便珊泳，可以預(yù)先將訓(xùn)練集中實(shí)例間的內(nèi)積計(jì)算出來并以矩陣的形式存儲，這個(gè)矩陣就是Gram矩陣拷沸。

對偶形式有什么用色查？

在訓(xùn)練過程中，不再需要每次迭代都更新權(quán)重向量撞芍，而只需更新一個(gè)數(shù)字 $\alpha_i$ 综慎，同時(shí)在判斷是否為誤分類樣本時(shí)，可以通過查表的方式得到簡化計(jì)算勤庐，運(yùn)算量為O(N) （原始形式為O(n)）。但是好港，在實(shí)際實(shí)現(xiàn)過程中發(fā)現(xiàn)愉镰，計(jì)算Gram矩陣本身的開銷也很大O(N*N*n)。

對偶感知機(jī)有用的場景必須滿足以下下兩個(gè)條件：

????當(dāng) N 較小钧汹，O(N) < O(n); （有過擬合的風(fēng)險(xiǎn)）

? ? 實(shí)際所需迭代次數(shù)較多（難分類）丈探，計(jì)算Gram矩陣的開銷可以忽略。

所以拔莱，個(gè)人認(rèn)為對偶形式可用性其實(shí)并不好碗降。