學習筆記 感知機

2022-11-24 18:02:55 字數 1959 閱讀 5736

感知機(perceptron)是二類分類的線性分類模型,輸入為例項的特徵向量,輸出為例項的類別,+1和-1。對應於輸入空間中將將例項劃分為正負兩類的分離超平面,屬於判別模型。是神經網路和支援向量機的基礎。

感知機:由輸入空間到輸出空間的如下函式:

\[f(x) = sign(w \cdot x + b)

\]其中,\(w,x,b\)都是向量,\(w\)是權值,\(x\)是輸入,\(b\)叫做偏置。

感知機模型的假設空間是定義在特徵空間中的所有線性分類模型(linear classification model)或線性分類器(linear classifier)。這個\(w \cdot x + b\)就對應特徵空間中的一個超平面,\(w\)是超平面的法向量,\(b\)是超平面的截距。超平面的一邊是+1,另一邊是-1,所以這個超平面稱為分離超平面(separating hyperplance)。

要定義一個損失函式並將損失函式極小化,從而求得一個分離超平面,將線性可分的資料集分開。誤分類的個數不太好,感知機採用的是誤分類點到超平面的總距離,是\(w\)和\(b\)的連續可導函式:

\[\frac |w \cdot x_0 + b|

\]簡化一下,由於\(y_i\)是+1或-1,另外$\frac $可以不考慮,感知機的損失函式就可以定義為:

\[l(w,b) = -\sum_ y_i(w \cdot x_i + b)

\]其中\(m\)是誤分類點的集合。

求解上面那個損失函式最優化問題,最優化的方法是隨機梯度下降法。

選取初值\(w_0\), \(b_0\)

在訓練資料中選取資料\((x_i,y_i)\)

如果\(y_i(w \cdot x_i + b) \leq 0\)

$$w \leftarrow w + \eta y_i x_i$$$$b \leftarrow b + \eta y_i$$
轉至2,直到訓練集中沒有誤分類點

第三步就是一個基本的梯度下降,最低點梯度為0,如果現在的梯度大於0,那麼就得減掉一點,\(\eta\) 用來控制一下每一步減去的多少。

採取不同的初值或選取不同的誤分類點,最後都會找到正確的分離超平面,但是解可以不同。

可以證明,上面的方法經過有限次迭代可以得到一個將訓練資料集完全正確劃分的分離超平面及感知機模型。

具體的過程就不寫了,大概就是,每次迭代都在引數上改變一點點,然後就證明了第\(k\)次得到的超平面的法向量與肯定存在的一個分離超平面法向量的內積,與\(k\)的關係,之後就證明了:

\[k \leq \left ( \frac \right )^2

\]其中,\(\gamma = \min_ \ \cdot x_i + b_) \}\),\(r\)等於最大的\(x\)的模......。

演算法過程是一樣的,但在這個過程中可以以另外一種形式來看待引數所發生的改變。感知機的原始形式和對偶形式可以和之後的支援向量機對應起來。

\(\alpha \leftarrow 0, b \leftarrow 0\)

在訓練集中選取資料\((x_i, y_i)\)

如果\(y_i\left( \sum_^n \alpha_j y_j x_j \cdot x + b \right) \leq 0\)

$$\alpha \leftarrow \alpha_i + \eta$$$$b \leftarrow b + \eta y_i$$
轉至2直到沒有誤分類資料

對偶形式中的訓練例項僅以內積形式出現,為了方便,可以預先將內積儲存,這個矩陣就是gram矩陣:

\[g = [x_i \cdot x_j]_

\](注:本文為讀書筆記與總結,側重演算法原理,**為[《統計學習方法》](一書第二章)

出處:[