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

1翩活、感知機(jī)算法簡述

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

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

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

稱為感知機(jī)咽扇。 $w\in R^n$ 和 $b\in R$ 分別是感知機(jī)的權(quán)值和偏置邪财。

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

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

其中 $M$ 表示誤分類點(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è)誤分類點(diǎn) $(x_i,y_i)$ 嘶伟，對 $w,b$ 進(jìn)行更新：

$w\leftarrow w+\eta y_i x_i$

$b\leftarrow b+\eta y_i$

其中 $\eta(0<\eta\leq 1)$ 稱為學(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)練集中無誤分點(diǎn)绊袋。

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

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

首先展姐，為了方便推導(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)完全正確分開涣狗，且存在 $\gamma>0$ 谍婉，對所有 $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)練集上誤分類次數(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ī)算法的收斂性得證。

最后編輯于：2020.02.28 20:12:22

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末丁溅，一起剝皮案震驚了整個(gè)濱河市唤蔗，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌窟赏，老刑警劉巖妓柜，帶你破解...
沈念sama閱讀 206,723評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異涯穷，居然都是意外死亡棍掐，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,485評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門拷况，熙熙樓的掌柜王于貴愁眉苦臉地迎上來作煌，“玉大人掘殴，你說我怎么就攤上這事∷谑模” “怎么了奏寨？”我有些...
開封第一講書人閱讀 152,998評論 0贊 344
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長鹰服。經(jīng)常有香客問我病瞳，道長，這世上最難降的妖魔是什么获诈？我笑而不...
開封第一講書人閱讀 55,323評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任仍源，我火速辦了婚禮，結(jié)果婚禮上舔涎，老公的妹妹穿的比我還像新娘。我一直安慰自己逗爹，他們只是感情好亡嫌，可當(dāng)我...
茶點(diǎn)故事閱讀 64,355評論 5贊 374
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著掘而，像睡著了一般挟冠。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上袍睡，一...
開封第一講書人閱讀 49,079評論 1贊 285
城市分裂傳說
那天知染，我揣著相機(jī)與錄音，去河邊找鬼斑胜。笑死控淡，一個(gè)胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的止潘。我是一名探鬼主播掺炭，決...
沈念sama閱讀 38,389評論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼凭戴！你這毒婦竟也來了涧狮？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 37,019評論 0贊 259
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤么夫，失蹤者是張志新（化名）和其女友劉穎者冤，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體档痪，經(jīng)...
沈念sama閱讀 43,519評論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡涉枫，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,971評論 2贊 325
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了钞它。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片拜银。...
茶點(diǎn)故事閱讀 38,100評論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡殊鞭，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出尼桶，到底是詐尸還是另有隱情操灿，我是刑警寧澤，帶...
沈念sama閱讀 33,738評論 4贊 324
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布泵督，位于F島的核電站趾盐，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏小腊。R本人自食惡果不足惜救鲤，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,293評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望秩冈。院中可真熱鬧本缠，春花似錦、人聲如沸入问。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,289評論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽芬失。三九已至楣黍，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間棱烂，已是汗流浹背租漂。一陣腳步聲響...
開封第一講書人閱讀 31,517評論 1贊 262
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留颊糜，地道東北人哩治。一個(gè)月前我還...
沈念sama閱讀 45,547評論 2贊 354
代替公主和親
正文我出身青樓，卻偏偏與公主長得像芭析，于是被迫代替她去往敵國和親锚扎。傳聞我的和親對象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,834評論 2贊 345

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

1翩活、感知機(jī)算法簡述

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

推薦閱讀更多精彩內(nèi)容