感知機演算法原理(PLA原理)及 Python 實現

感知機演算法原理(PLA原理)及 Python 實現
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

參考書籍:李航老師的《統計學習方法》、林軒田老師的《機器學習基石》

如無特殊說明,圖片均來自網路(google圖片、百度圖片),如有侵權請聯絡我,我會立即刪除或更改


PLAPerceptron Learning Algorithm 的縮寫,也叫感知機演算法。感知機演算法與線性迴歸有很多相似的地方。例如線性迴歸採用梯度下降法求最優引數的時候對每個資料點都進行了遍歷,求誤差的平均值。而 PLA 只選取一個點進行處理,所以 PLA 的學習過程也可以叫做 隨機梯度下降

如果不瞭解什麼是線性迴歸,可以參考我的另一篇文章:《機器學習筆記01:線性迴歸(Linear Regression)和梯度下降(Gradient Decent)》


1 感知機模型

1.1 形象的感知機

什麼是感知機模型呢,簡而言之就是可以將有兩個特徵的資料集中的正例和反例完全分開的關於一條直線的函式,或者可以是關於三維空間中的一個平面的函式,更可以是關於高維的一個超平面的函式。

什麼?關於一條直線的函式?關於一個平面的函式?關於一個超平面的函式?其實感知機就是一個分段函式,不過變數是一條直線、平面或超平面而已。

可能聽起來有點繞口,看了1.2節就明白了。當然如果資料集只有一個特徵,那麼也可以是一個點。比如下面的這條直線就將資料集中的正負例項完全分成了兩部分:

這裡寫圖片描述
或者下面的這個三維空間中的平面將有三個特徵的資料集分成了兩部分:
這裡寫圖片描述


1.2 感知機的數學表示

上面的圖片應該已經給了大家一個形象的理解:感知器就是一個東西能夠把訓練集中的正例和反例劃分為兩個部分,並且能夠對未來輸入的資料進行分類。舉個例子:一個小孩子的媽媽在教他什麼是蘋果什麼不是蘋果,首先會拿個蘋果過來說“記住,這個是蘋果”,然後拿了一個杯子過來說“這個不是蘋果”,又拿來一個稍微不一樣的蘋果說“這個也是蘋果”……,最後,小孩子就學習到了一個模型(判斷蘋果的標準)來判斷什麼是蘋果什麼不是蘋果。

首先,感知機的輸入空間(特徵空間)為 X⊆Rn\mathcal{X} \subseteq R^n,即 nn 維向量空間,輸出空間為 Y={ 1,−1}\mathcal{Y}=\{ 1, -1\},即 −1-1 代表反例, 1 1 代表正例。例如:輸入 x∈Xx\in\mathcal{X} 對應於輸入空間 RnR^n 中的某個點,而輸出 y∈Yy\in\mathcal{Y} 表示該點所在的分類。需要注意的是,輸入 xx 是一個 nn 維的向量,即 x=(x(1),x(2),…,x(n))x = (x^{(1)},x^{(2)},…,x^{(n)})。現在已經有了輸入和輸出的定義,我們就可以給出感知機 f(x)f(x) 的模型了:

f(x)=sign(ω⋅x b)

f(x) = sign(\omega\cdot x b)
其中,向量 ω=(ω(1),ω(2),…,ω(n))\omega=(\omega^{(1)},\omega^{(2)},…,\omega^{(n)}) 中的每個分量代表輸入向量空間 RnR^n 中向量xx的每個分量 xix_i 的權重,或者說引數。b∈Rb\in R 稱為偏置單元,ω⋅x\omega\cdot x 表示 ω\omega 和 xx的內積,signsign 是一個符號函式,即:

sign(x)=⎧⎩⎨ 1,−1,x⩾0x<0

sign(x) =\begin{cases}
1, & x \geqslant 0 \\[2ex]
-1, & x \lt 0
\end{cases}
我們把上面這個函式 f(x)f(x) 稱為感知機。


1.3 感知機的假設空間

上面說了,感知機是一個模型,它具有輸入和輸出。但是我們事先並不知道這個模型到底是什麼。同時我們也需要知道到哪裡去尋找我們想要的感知機模型,所以這裡有個概念叫做 假設空間,我們把假設空間用 H\mathcal{H} 表示,它是一個包含了在特徵空間(輸入空間) RnR^n 中定義的所有線性分類模型的一個集合,即有:

H={f|f(x)=sign(ω⋅x b)}

\mathcal{H}=\{f|f(x)=sign(\omega\cdot x b)\}
李航老師《統計學習方法》中的假設空間沒有 signsign 函式,個人覺得既然是感知機模型的假設空間,而不是超平面(包括點、直線和平面)的集合,就應該將sign加上

而我們要希望得到就是一個最佳的(能夠完美劃分訓練集的)感知機 hopt∈Hh_{opt}\in\mathcal{H}。例如下圖中的各種直線就是二維假設空間 H\mathcal{H} 中的一部分模型去掉符號函式 signsign 後的直線(不可能畫出所有的直線),而直線 aa 就是一個完美的劃分直線(要注意模型和超平面的區別,即有無 signsign 函式的區別):

這裡寫圖片描述
而其他直線(黑色)都不能把正例和反例完全分開。


1.4 感知機的幾何意義

且先去掉感知機模型中用於輸出分類結果的 signsign 函式,如果我們有如下方程:

ω⋅x b=0

\omega\cdot x b=0
那麼這個方程的幾何意義是什麼呢?其意義很簡單:

  1. 方程 ω⋅x b=0\omega\cdot x b=0 是一個超平面的方程
  2. ω\omega 是這個超平面的法向量
  3. bb 是這個超平面的截距

例如在三維空間座標系內,平面的方程均可用三元一次方程 Ax By Cz D=0Ax By Cz D=0來表示,其中 ω=(A,B,C)\omega=(A,B,C),x=(x,y,z)x=(x,y,z),d=Dd=D。很明顯,如下圖所示,這個三維空間中的平面把整個三維空間分成了兩個部分。對於更高維度的平面我們可能想象不出來,但是它們的性質卻是相同的。

這裡寫圖片描述


1.5 感知機的輸入和輸出

總結一下目前用到的符號,我們需要知道以下數學符號的含義:

符號含義
H\mathcal{H}假設空間
f(x)∈Hf(x)\in \mathcal{H}感知機模型
X⊆Rn\mathcal{X}\subseteq R^n特徵空間
Y={ 1,−1}\mathcal{Y}=\{ 1,-1\}輸出空間
RnR^nnn 維向量空間
ω=(ω(1),ω(2),…,ω(n))\omega=(\omega^{(1)},\omega^{(2)},…,\omega^{(n)})超平面的法向量,或者說特徵的引數向量
ω(i),(i=1,2,…,n)\omega^{(i)},(i=1,2,…,n)超平面的法向量的分量,或者說某個引數
x=(x(1),x(2),…,x(n))x=(x^{(1)},x^{(2)},…,x^{(n)})輸入向量,特徵向量
x(i),(i=1,2,…,n)x^{(i)},(i=1,2,…,n)特徵向量中的某個特徵
bb超平面的截距
sign(x)sign(x)符號函式,x⩾0x\geqslant 0 時為 1 1,否則為 −1-1
D=(x1,y1),(x2,y2),…,(xm,ym)\mathcal{D}={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}資料集,mm 為樣本數, nn 為特徵數,yy 為分類標籤(1或者-1)

注意

D=x1,x2,…,xm=⎛⎝⎜⎜⎜⎜⎜⎜x(1)1x(1)2⋮x(1)mx(2)1x(2)2⋮x(2)m⋯⋯⋱⋯x(n)1x(n)2⋮x(n)my1y2⋮ym⎞⎠⎟⎟⎟⎟⎟⎟

\mathcal{D}={x_1,x_2,…,x_m}=
\begin{pmatrix}
x_1^{(1)} & x_1^{(2)} & \cdots & x_1^{(n)} & y_1\\
x_2^{(1)} & x_2^{(2)} & \cdots & x_2^{(n)} & y_2\\
\vdots & \vdots & \ddots & \vdots & \vdots \\
x_m^{(1)} & x_m^{(2)} & \cdots & x_m^{(n)} & y_m\\
\end{pmatrix}

以上某些符號在後面會用到。


2. 感知機的學習過程

2.1 資料集的線性可分和線性不可分

感知機要求訓練資料是線性可分的,否則無法構建一個線性的分類器。什麼是線性可分和線性不可分呢,直觀的表示如下:

這裡寫圖片描述
除了第一個資料集是線性可分的,其他兩個都不是線性可分的。上圖是二維空間中的情況,高維空間的情況也一樣。

下面是資料集線性可分的定義(李航《統計學習方法》P26):

給定一個資料集

D=(x1,y1),(x2,y2),…,(xn,yn)

\mathcal{D} = {(x_1,y_1),(x_2,y_2),…,(x_n,y_n)}其中,xi∈X⊆Rnx_i\in \mathcal{X} \subseteq R^n,yi∈Y={ 1,−1}y_i\in \mathcal{Y} = \{ 1,-1\},i=1,2,..,ni=1,2,..,n。如果存在某個超平面 S\mathcal{S}

ω⋅x b=0

\omega \cdot x b = 0能夠將資料集的正例項點和負例項點完全正確地劃分到超平面的兩側,即對所有 yi= 1y_i= 1 的例項 ii,有 ω⋅xI b>0\omega \cdot x_I b > 0,對所有 yi=−1y_i=-1 的例項 ii,有 ω⋅xI b<0\omega \cdot x_I b < 0,則資料集 D\mathcal{D} 為線性可分資料集(linearly separable data set);否則,稱資料 D\mathcal{D} 集線性不可分


2.2 PLA 原理及過程

PLA 的原理很簡單,開始時,我們令 ω=b=0\omega=b=0,然後在訓練資料 D\mathcal{D} 中任意選擇一點,如果該點被錯誤分類了,那麼我們就調整分類的直線或者超平面使該點能夠被正確分類。

在說明 PLA 原理之前,我們先來回顧一下向量的內積(inner product)。例如有向量 a=(a(1),a(2),…,a(n)),b=(b(1),b(2),…,b(n))a=(a^{(1)},a^{(2)},…,a^{(n)}),b=(b^{(1)},b^{(2)},…,b^{(n)}),則它們的內積為:

a⋅b=∑i=1na(i)b(i)=∥a∥⋅∥b∥⋅cosθ

a\cdot b = \sum_{i=1}^n{a^{(i)}b^{(i)}}=\Vert a\Vert\cdot \Vert b\Vert\cdot cos\theta
在紙上畫畫就明白,當內積為負數時,兩個向量的夾角 θ\theta 大於 90°90°;當內積為正數時,兩個向量的夾角 θ\theta 小於 90°90°;當內積為 00 時,兩個向量垂直。

在 1.4 節我們給出了感知機的幾何意義,方程 ω⋅x b=0\omega\cdot x b=0 代表了一個平面。我們不妨將其改寫為 ω^⋅x^=0\hat \omega\cdot \hat x = 0,其中:
ω^=(b,ω)=(ω0,ω)=(ω(0),ω(1),ω(2),…,ω(n))\hat \omega = (b,\omega) = (\omega^{0},\omega)=(\omega^{(0)},\omega^{(1)},\omega^{(2)},…,\omega^{(n)})
x^=(1,x)=(1,x(1),x(2),…,x(n))\hat x = (1,x)=(1,x^{(1)},x^{(2)},…,x^{(n)})
我們的目的就是求得超平面的法向量 ω^\hat \omega, 使超平面能夠完美地劃分資料集。

具體怎麼求呢,我們採用隨機梯度下降法,即隨意找一個點,如果分類錯誤,我們就更新 ω^\hat \omega:

  1. 輸入資料 D=(x1,y1),(x2,y2),…,(xm,ym)\mathcal{D}={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)},其中 xi∈X⊂Rnx_i\in \mathcal{X} \subset R^n,y∈Y={ 1,−1}y\in \mathcal{Y} = \{ 1,-1\},i=1,2,…,ni=1,2,…,n。
  2. 選取初值 ω^0=0\hat \omega_0 = 0,即設為零向量。
  3. 遍歷 D\mathcal{D} 中的資料,如果遇到某個樣本 (xi,yi)(x_i,y_i) 使得 yi(ω^⋅x)⩽0y_i(\hat \omega \cdot x) \leqslant 0,即目前分類輸出和真實分類不同,則
    ω^←ω^0 yix^i

    \hat \omega \leftarrow \hat \omega_0 y_i\hat x_i

  4. ω^\hat \omega 更新後,回到第三步,重新開始遍歷,如果遍歷完整個資料集 D\mathcal{D} 都未有更新操作(沒有錯誤分類點),則轉第五步。
  5. 輸出當前超平面的法向量 ω^\hat \omega。

最後程式輸出的 ω^\hat \omega 即為我們要找的能夠完美劃分資料集的超平面的法向量。

下面來看一個例子(出自林軒田老師的《機器學習基石》),紅色代表當前超平面的法向量,紫色代表本次更新後的法向量,黑色代表隨機選擇的一個錯誤的分類點,注意是如何調整超平面的:

這裡寫圖片描述
最後看起來好像還有一個藍色的點在超平面上,其實放大後發現,這個點的圓心是在正例一方的。所以感知機訓練完成。


2.3 PLA 的收斂性證明

可能很多朋友會懷疑上面的演算法最終會不會停止,因為每更新一次 ω^\hat \omega,可能就會有新的錯誤分類點出現。先說結論吧,對於線性可分的資料集,PLA 最終是會停止的,即滿足演算法的有窮性,並且誤分類的次數也是有上界的。

李航老師《統計學習方法》P33頁中的證明可能會讓很多人摸不著頭腦,為啥 ∥ω^opt∥=1\Vert\hat\omega_{opt}\Vert=1 呢,為什麼不可以是其他的值呢?答案是:∥ω^opt∥\Vert\hat\omega_{opt}\Vert 可以取任何正實數。

下面就來證明一下 PLA 的收斂性(參考李航《統計學習方法》、林軒田《機器學習基石》、MIT機器學習PPT):

設存在理想超平面 S\mathcal{S} 能夠完全正確劃分資料集 D\mathcal{D},其法向量(模型引數向量)為 ω^opt\hat\omega_{opt}。

令 γ=min0⩽i⩽myi(ω^⋅x^i)\gamma = \min\limits_{0\leqslant i \leqslant m}{y_i(\hat\omega\cdot\hat x_i)},即 γ\gamma 為離超平面最近的資料點與超平面的距離(mm 為樣本數量,後文中的含義相同)。那麼,對於任意的點 x^i\hat x_i 均有

yi(ω^⋅x^i)⩾γ

y_i(\hat\omega\cdot\hat x_i)\geqslant\gamma

令感知機演算法從 ω^0\hat\omega_0=0 開始,每遇到錯誤分類就更新引數向量,令 ω^k−1\hat\omega_{k-1} 為遇到第 kk 個錯誤分類之前的引數向量,則遇到第 kk 個誤分類情況時需要滿足

yi(ω^k−1⋅x^i)⩽0

y_i(\hat\omega_{k-1}\cdot\hat x_i)\leqslant 0

若 (x^i,yi)(\hat x_i,y_i) 是被 ω^k−1\hat\omega_{k-1} 錯誤分類的資料,則更新引數向量:

ω^k=ω^k−1 yix^i

\hat\omega_{k}=\hat\omega_{k-1} y_i\hat x_i

下面證明兩個不等式用於後面的證明:
(1)ω^k⋅ω^opt⩾kγ\hat\omega_k\cdot\hat\omega_{opt}\geqslant k\gamma:

ω^k⋅ω^opt=ω^k−1⋅^ωopt yix^iω^opt⩾ω^k−1⋅ωopt γ

\begin{align}
\hat\omega_k\cdot\hat\omega_{opt}
&= \hat\omega_{k-1}\hat\cdot\omega_{opt} y_i\hat x_i \hat\omega_{opt} \\
&\geqslant \hat\omega_{k-1}\cdot\omega_{opt} \gamma
\end{align}
又:

ω^k−1⋅ω^opt=ω^k−2⋅^ωopt yix^iω^opt⩾ω^k−2⋅ωopt γ

\begin{align}
\hat\omega_{k-1}\cdot\hat\omega_{opt}
&= \hat\omega_{k-2}\hat\cdot\omega_{opt} y_i\hat x_i \hat\omega_{opt} \\
&\geqslant \hat\omega_{k-2}\cdot\omega_{opt} \gamma
\end{align}
所以可以得到如下遞推公式:

ω^k⋅ω^opt⩾ω^k−1⋅ωopt γ⩾ω^k−2⋅ωopt 2γ⩾…⩾ω^1⋅ωopt (k−1)γ⩾ω^0⋅ωopt kγ=kγ

\hat\omega_k\cdot\hat\omega_{opt}
\geqslant \hat\omega_{k-1}\cdot\omega_{opt} \gamma
\geqslant \hat\omega_{k-2}\cdot\omega_{opt} 2\gamma
\geqslant …
\geqslant \hat\omega_{1}\cdot\omega_{opt} (k-1)\gamma
\geqslant \hat\omega_{0}\cdot\omega_{opt} k\gamma=k\gamma


(2)∥ω^k∥2⩽kR2{\Vert\hat\omega_{k}\Vert}^2\leqslant kR^2:

∥ω^k∥2=∥ω^k−1∥2 2yiω^k−1⋅x^i y2i∥x^i∥2,(yi∈{ 1,−1},可略去y2i)

{\Vert\hat\omega_{k}\Vert}^2 = {\Vert\hat\omega_{k-1}\Vert}^2 2y_i\hat\omega_{k-1}\cdot\hat x_i y_i^2{\Vert\hat x_i\Vert}^2, (y_i\in\{ 1,-1\},可略去 y_i^2)
因為處理都是錯誤分類,所以yiω^k−1⋅x^i⩽0y_i\hat\omega_{k-1}\cdot\hat x_i\leqslant 0
所以:

∥ω^k∥2⩽∥ω^k−1∥2 ∥x^i∥2

{\Vert\hat\omega_{k}\Vert}^2
\leqslant {\Vert\hat\omega_{k-1}\Vert}^2 {\Vert\hat x_i\Vert}^2
令 R=max0⩽i⩽m∥x^i∥R=\max\limits_{0\leqslant i \leqslant m}{\Vert\hat x_i\Vert},即離原點最遠的點與原點的距離。則:

∥ω^k∥2⩽∥ω^k−1∥2 R2

{\Vert\hat\omega_{k}\Vert}^2
\leqslant {\Vert\hat\omega_{k-1}\Vert}^2 R^2
又:

∥ω^k−1∥2⩽∥ω^k−2∥2 R2

{\Vert\hat\omega_{k-1}\Vert}^2
\leqslant {\Vert\hat\omega_{k-2}\Vert}^2 R^2
所以有遞推公式:

∥ω^k∥2⩽∥ω^k−1∥2 R2⩽∥ω^k−2∥2 2R2⩽…⩽∥ω^1∥2 (k−1)R2⩽∥ω^0∥2 kR2⩽kR2

{\Vert\hat\omega_{k}\Vert}^2
\leqslant {\Vert\hat\omega_{k-1}\Vert}^2 R^2
\leqslant {\Vert\hat\omega_{k-2}\Vert}^2 2R^2
\leqslant …
\leqslant {\Vert\hat\omega_{1}\Vert}^2 (k-1)R^2
\leqslant {\Vert\hat\omega_{0}\Vert}^2 kR^2
\leqslant kR^2

所以,由(1)、(2)可知:

1⩾cosθ=ω^k⋅ω^opt∥ω^k∥∥ω^opt∥⩾kγ∥ω^k∥∥ω^opt∥⩾kγkR2−−−√∥ω^opt∥

1\geqslant cos\theta
= \frac{\hat\omega_{k}\cdot\hat\omega_{opt}}{\Vert\hat\omega_{k}\Vert\Vert\hat\omega_{opt}\Vert}
\geqslant \frac{k\gamma}{\Vert\hat\omega_{k}\Vert\Vert\hat\omega_{opt}\Vert}
\geqslant \frac{k\gamma}{\sqrt {kR^2}\Vert\hat\omega_{opt}\Vert}

其中 θ\theta 為 ω^k\hat\omega_{k} 和 ω^opt\hat\omega_{opt} 的夾角。
所以由上面的不等式可知:

k⩽R2∥ω^opt∥2γ2

k \leqslant \frac{R^2{\Vert\hat\omega_{opt}\Vert}^2}{\gamma^2}
所以,感知機的錯誤修正次數是有上限的,由於 ∥ω^opt∥\Vert\hat\omega_{opt}\Vert 是必然存在的,所以 k 一定存在。即感知機演算法是收斂的。


3. 用 Python 實現感知機

由於篇幅太大,實現另開一篇:感知機的 python 實現

如有錯誤,請批評指正


最近遇到很多轉載不註明出處,還打著原創旗號的小編和博主,所以:
知識共享許可協議
本文采用 知識共享署名-非商業性使用-禁止演繹 2.5 中國大陸許可協議 進行許可。


相關文章

程式語言 最新文章