感知機(jī)算法及收斂性證明

1、感知機(jī)算法簡(jiǎn)述

感知機(jī)算法其實(shí)已經(jīng)很熟悉了，這次看《統(tǒng)計(jì)學(xué)習(xí)方法》權(quán)當(dāng)復(fù)習(xí)一遍，然后有一個(gè)point對(duì)我來(lái)說(shuō)是新的——感知機(jī)算法實(shí)際上采用了隨機(jī)梯度下降。這其實(shí)是一個(gè)很顯然的點(diǎn)，但我之前看到的資料都是直接說(shuō)明了超平面參數(shù)的更新方式，并從幾何直觀上解釋了這樣做是為了讓超平面向誤分樣本點(diǎn)的方向旋轉(zhuǎn)，而未從梯度的角度來(lái)解釋?zhuān)@里補(bǔ)充一下這個(gè)角度。

感知機(jī)（perceptron）是二分類(lèi)線性分類(lèi)模型，其輸入空間（特征空間）是X\subseteq R^n，輸出空間是Y=\{+1,-1\}，由輸入空間到輸出空間的如下函數(shù)：

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

稱(chēng)為感知機(jī)。w\in R^n和b\in R分別是感知機(jī)的權(quán)值和偏置。

感知機(jī)的損失函數(shù)定義為所有誤分類(lèi)點(diǎn)到超平面的距離之和，即：

L(w,b)=-\sum_{x_i\in M}y_i (w\cdot x_i+b)

其中M表示誤分類(lèi)點(diǎn)的集合，若M固定，則損失函數(shù)梯度為：

\bigtriangledown_w L(w,b)=-\sum_{x_i\in M}y_i x_i

\bigtriangledown_b L(w,b)=-\sum_{x_i\in M}y_i

采用隨機(jī)梯度下降法，每次隨機(jī)選取一個(gè)誤分類(lèi)點(diǎn)(x_i,y_i)，對(duì)w,b進(jìn)行更新：

w\leftarrow w+\eta y_i x_i

b\leftarrow b+\eta y_i

其中\eta(0<\eta\leq 1)稱(chēng)為學(xué)習(xí)率。

感知機(jī)算法流程如下：

（1）選取初值w_0,b_0。
（2）在訓(xùn)練集中選取數(shù)據(jù)(x_i,y_i)。
（3）如果y_i(w\cdot x_i+b)\leq 0,則更新參數(shù)：

w\leftarrow w+\eta y_i x_i

b\leftarrow b+\eta y_i

（4）轉(zhuǎn)至（2）直至訓(xùn)練集中無(wú)誤分點(diǎn)。

2、感知機(jī)算法收斂性證明

所謂感知機(jī)算法的收斂性，就是說(shuō)只要給定而分類(lèi)問(wèn)題是線性可分的，那么按上述感知機(jī)算法進(jìn)行操作，在有限次迭代后一定可以找到一個(gè)可將樣本完全分類(lèi)正確的超平面。

首先，為了方便推導(dǎo)，我們將偏置b并入權(quán)重向量w,記作\hat{w}=(w^T,b)^T，同樣將輸入向量加以擴(kuò)充，記作\hat{x}=(x^T,1)^T，顯然，\hat{w}\cdot\hat{x}=w\cdot x+b。

既然樣本是線性可分的，我們可以假設(shè)有一個(gè)滿足條件||\hat{w}_{opt}||=1的超平面\hat{w}_{opt}將樣本點(diǎn)完全正確分開(kāi)，且存在\gamma>0，對(duì)所有i=1,2,\dots,N，有：

y_i(\hat{w}_{opt}\cdot \hat{x}_i)\geq \gamma

令R=\max_{1\leq i\leq N}||\hat{x}_i||，則感知機(jī)算法在訓(xùn)練集上誤分類(lèi)次數(shù)k滿足：

k\leq ( \frac{R}{\gamma})^2

證明：

\begin{aligned} \hat{w}_k\cdot \hat{w}_{opt} & = \hat{w}_{k-1}\cdot \hat{w}_{opt}+\eta y_i \hat{w}_{opt}\cdot x_i\\ & \geq \hat{w}_{k-1}\cdot \hat{w}_{opt}+\eta \gamma\\ & \geq \dots \\ & \geq k\eta \gamma \end{aligned}

\begin{aligned} ||\hat{w}_k||^2&=||\hat{w}_{k-1}+\eta y_i x_i||^2\\ &=||\hat{w}_{k-1}||^2+\eta^2||x_i||^2+2\eta\hat{w}_{k-1}y_i x_i\\ &\leq ||\hat{w}_{k-1}||^2+\eta^2 R^2\\ &\leq \dots\\ &\leq k\eta^2 R^2\\ \end{aligned}

結(jié)合上述兩個(gè)結(jié)論，可以得到：

k\eta \gamma\leq\hat{w}_k\cdot \hat{w}_{opt}\leq||\hat{w}_k|| ||\hat{w}_{opt}||\leq \sqrt{k}\eta R

\Rightarrow k\leq(\frac{R}{\gamma})^2

從而感知機(jī)算法的收斂性得證。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容