感知機(jī)模型(Perceptron)的收斂性解讀 | 統(tǒng)計(jì)學(xué)習(xí)方法

Python復(fù)現(xiàn)，使用了隨機(jī)梯度下降法蓄拣，梯度下降法扬虚，adagrad和對(duì)偶形式四種算法：

舟曉南：感知機(jī)模型python復(fù)現(xiàn) - 隨機(jī)梯度下降法；梯度下降法球恤；adagrad辜昵；對(duì)偶形式

在《統(tǒng)計(jì)學(xué)習(xí)方法》的感知機(jī)算法章節(jié)中，作者提出了一個(gè)問題咽斧，即如何證明一個(gè)線性可分的數(shù)據(jù)集堪置，可以在有限次的迭代后得到這個(gè)分離超平面。我們稱在有限次迭代后獲得分離超平面的性質(zhì)為感知機(jī)算法的收斂性张惹。對(duì)于一個(gè)線性不可分的數(shù)據(jù)集晋柱，感知機(jī)模型將進(jìn)入無法收斂的狀態(tài)，即無法獲得一個(gè)可以將所有實(shí)例正確分類的分離超平面诵叁，而是在迭代過程中進(jìn)入震蕩。

算法的收斂性：

感知機(jī)模型： $\\f(x)=\operatorname{sign}(w \cdot x+b)$ ?

首先為了計(jì)算方便钦椭，將b并入權(quán)重向量w拧额，記作 $\hat{w}=(\mathrm{w}碑诉， \mathrm)$ 侥锦，同樣輸入向量也需要相應(yīng)地?cái)U(kuò)充进栽，記作 $\hat{x}=(x， 1)$ 恭垦。

$\\\hat{w} \cdot \hat{x}=(\mathrm{w}快毛， \mathrm) \cdot(x番挺， 1)=\mathrm{w} \cdot \mathrm{x}+\mathrm唠帝$

證明1：

設(shè)訓(xùn)練集線性可分，那么存在超平面可將訓(xùn)練集完全正確分開玄柏，此超平面設(shè)為：

$\\\hat{w}_{\mathrm{opt}} \cdot \hat{x}=w_{\mathrm{opt}} \cdot x+b_{\mathrm{opt}}=0$

在我的另一篇關(guān)于感知機(jī)的文章：

舟曉南：統(tǒng)計(jì)學(xué)習(xí)方法 - 感知機(jī)模型解讀 | 數(shù)據(jù)分析襟衰，機(jī)器學(xué)習(xí)，學(xué)習(xí)歷程全記錄

中提到作為函數(shù)間隔可以等比例放大縮小粪摘，因此這里為了方便可以將 $\hat{w}_{\mathrm{opt}}$ 放大縮小至 $\left\|\hat{w}_{\mathrm{opt}}\right\|=1$ 瀑晒。

因?yàn)楸徽_分類的實(shí)例有：

$\\y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)>0$

且i有限（實(shí)例的數(shù)量有限），因此在 $y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)$ 中存在一個(gè)最小值徘意，設(shè)此最小值為γ：

$\\\gamma=\min _{i}\left\{y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right)\right\}$

那么對(duì)于所有實(shí)例來說苔悦，都有不等式（1）：

$\\y_{i}\left(\hat{w}_{\mathrm{opt}} \cdot \hat{x}_{i}\right) \geqslant \gamma$

證明2：

因?yàn)楦兄獧C(jī)算法從初始權(quán)重向量 $\hat{w}_{0}=0$ 開始，可令 ${\hat{w}}_{k-1}$ 是第k個(gè)誤分類實(shí)例之前的擴(kuò)充權(quán)重向量椎咧，且(xi,yi)是被其誤分類的樣本點(diǎn)玖详。

對(duì)于誤分類的實(shí)例，滿足：

$\\y_{i}\left(\hat{w}_{k-1} \cdot \hat{x}_{i}\right) \leqslant 0$

經(jīng)過損失函數(shù)求導(dǎo)得到梯度后邑退，w可進(jìn)行更新：

$\\\hat{w}_{k}=\hat{w}_{k-1}+\eta y_{i} \hat{x_{i}}$

那么利用不等式（1）可得：

$\\\begin{aligned} \hat{w}_{k} \cdot \hat{w}_{\text {opt }}=\left(\hat{w}_{k-1}+\eta y_{i} \hat{x}_{i}\right) \cdot & \hat{w}_{\text {opt }}=\hat{w}_{k-1} \cdot \hat{w}_{\text {opt }}+\eta y_{i} \hat{w}_{\text {opt }} \cdot \hat{x}_{i} \\ & \geqslant w_{k-1} \cdot \hat{w}_{\text {opt }}+\eta \gamma \end{aligned}$

由此可推得不等式（2）：

$\\\hat{w}_{k} \cdot \hat{w}_{\mathrm{opt}} \geqslant \hat{w}_{k-1} \cdot \hat{w}_{\mathrm{opt}}+\eta \gamma \geqslant \hat{w}_{k-2} \cdot \hat{w}_{\mathrm{opt}}+2 \eta \gamma \geqslant \cdots \geqslant k \eta \gamma$

接著竹宋，因?yàn)閷?shí)例有限，即i有限地技，我們可以定義 $R= \max \left\|\hat{x}_{i}\right\|$ 蜈七，在此基礎(chǔ)上計(jì)算 $\left\|\hat{w}_{k}\right\|^{2}$ ：

$\\\left\|\hat{w}_{k}\right\|^{2}=\hat{w}_{k} \cdot \hat{w}_{k}=\left(\hat{w}_{k-1}+\eta y_{i} \hat{x}_{i}\right)^{2}=\left\|\hat{w}_{k-1}\right\|^{2}+2 \eta y_{i} \hat{w}_{k-1} \cdot \hat{x}_{i}+\eta^{2}\left\|\hat{x}_{i}\right\|^{2}$

因?yàn)?xi, yi)是誤分類項(xiàng)，所以 $y_{i} \hat{w}_{k-1} \cdot \hat{x}_{i}$ 為負(fù)莫矗，且 $\eta \in(0飒硅，1]$ ，所以可推得不等式（3）：

$\\\left\|\hat{w}_{k}\right\|^{2} \leqslant\left\|\hat{w}_{k-1}\right\|^{2}+\eta^{2}\left\|\hat{x}_{i}\right\|^{2} \leqslant\left\|\hat{w}_{k-1}\right\|^{2}+\eta^{2} R^{2} \leqslant\left\|\hat{w}_{k-2}\right\|^{2}+2 \eta^{2} R^{2} \leqslant \cdots \leqslant k \eta^{2} R^{2}$

結(jié)合不等式（2）和不等式（3）作谚，及 $\left\|\hat{w}_{opt}\right\|=1$ 的前提條件三娩，可得：

$\\ k \eta \gamma \leqslant \hat{w}_{k} \cdot \hat{w}_{\mathrm{opt}} \leqslant\left\|\hat{w}_{k}\right\|\left\|\hat{w}_{\mathrm{opt}}\right\| =\left\|\hat{w}_{k}\right\|= \sqrt{k} \eta R$

關(guān)于上式 $\hat{w}_{k} \cdot \hat{w}_{\mathrm{opt}} \leqslant\left\|\hat{w}_{k}\right\|\left\|\hat{w}_{\mathrm{opt}}\right\|$ 這個(gè)部分為柯西-施瓦茲不等式，可自行查看證明過程妹懒。

通過上式可得：

$\\k \leqslant\left(\frac{R}{\gamma}\right)^{2}$

定理表明雀监，誤分類的次數(shù)k是有上界的，經(jīng)過有限次搜索可以找到將訓(xùn)練數(shù)據(jù)完全正確分開的分離超平面涨享。也就是說控淡，當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時(shí)，感知機(jī)學(xué)習(xí)算法原始形式迭代是收斂的绰沥。

我是舟曉南瓦宜，關(guān)注我的同名公眾號(hào) 和知乎蔚万，發(fā)掘更多內(nèi)容哦

對(duì)機(jī)器學(xué)習(xí)，深度學(xué)習(xí)临庇，python感興趣反璃，歡迎關(guān)注專欄，學(xué)習(xí)筆記已原創(chuàng)70+篇假夺，持續(xù)更新中~ ^_^

學(xué)習(xí)筆記：數(shù)據(jù)分析淮蜈，機(jī)器學(xué)習(xí)，深度學(xué)習(xí)

關(guān)于 python 二三事

專欄文章舉例：

【機(jī)器學(xué)習(xí)】關(guān)于邏輯斯蒂回歸侄泽，看這一篇就夠了礁芦！解答絕大部分關(guān)于邏輯斯蒂回歸的常見問題，以及代碼實(shí)現(xiàn) - 知乎 (zhihu.com)

記錄一下工作中用到的少有人知的pandas騷操作悼尾，提升工作效率 - 知乎 (zhihu.com)

關(guān)于切片時(shí)不考慮最后一個(gè)元素以及為什么從0開始計(jì)數(shù)的問題 - 知乎 (zhihu.com)

關(guān)于轉(zhuǎn)行：

舟曉南：如何轉(zhuǎn)行和學(xué)習(xí)數(shù)據(jù)分析 | 工科生三個(gè)月成功轉(zhuǎn)行數(shù)據(jù)分析心得淺談

舟曉南：求職數(shù)據(jù)分析師崗位柿扣，簡(jiǎn)歷應(yīng)該如何寫？｜工科生三個(gè)月成功轉(zhuǎn)行數(shù)據(jù)分析心得淺談

我建了個(gè)數(shù)據(jù)分析闺魏，機(jī)器學(xué)習(xí)未状，深度學(xué)習(xí)的群~ 需要學(xué)習(xí)資料，想要加入社群均可私信~

在群里我會(huì)不定期分享各種數(shù)據(jù)分析相關(guān)資源析桥，技能學(xué)習(xí)技巧和經(jīng)驗(yàn)等等~

詳情私信司草，一起進(jìn)步吧！

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

人面猴
序言：七十年代末泡仗，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子娩怎，更是在濱河造成了極大的恐慌，老刑警劉巖截亦，帶你破解...
沈念sama閱讀 216,470評(píng)論 6贊 501
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異崩瓤，居然都是意外死亡袍啡，警方通過查閱死者的電腦和手機(jī)却桶，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,393評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人嗅剖，你說我怎么就攤上這事蛋逾。” “怎么了窗悯？”我有些...
開封第一講書人閱讀 162,577評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵偷拔，是天一觀的道長(zhǎng)蒋院。經(jīng)常有香客問我莲绰，道長(zhǎng)，這世上最難降的妖魔是什么蛤签？我笑而不...
開封第一講書人閱讀 58,176評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任震肮，我火速辦了婚禮称龙，結(jié)果婚禮上戳晌，老公的妹妹穿的比我還像新娘。我一直安慰自己沦偎，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,189評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布搔驼。她就那樣靜靜地躺著侈询，像睡著了一般舌涨。火紅的嫁衣襯著肌膚如雪妄荔。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 51,155評(píng)論 1贊 299
城市分裂傳說
那天哗伯，我揣著相機(jī)與錄音篷角，去河邊找鬼焊刹。笑死，一個(gè)胖子當(dāng)著我的面吹牛虐块，可吹牛的內(nèi)容都是我干的俩滥。我是一名探鬼主播，決...
沈念sama閱讀 40,041評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼贺奠，長(zhǎng)吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼霜旧！你這毒婦竟也來了儡率？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 38,903評(píng)論 0贊 274
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤崎逃，失蹤者是張志新（化名）和其女友劉穎眉孩，沒想到半個(gè)月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體浪汪，經(jīng)...
沈念sama閱讀 45,319評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡吟宦，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,539評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了殃姓。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,703評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡篷牌，死狀恐怖踏幻，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情该面，我是刑警寧澤，帶...
沈念sama閱讀 35,417評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布题造，位于F島的核電站猾瘸，受9級(jí)特大地震影響丢习，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜咐低，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,013評(píng)論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一袜腥、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧羹令，春花似錦、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,664評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)显拜。三九已至爹袁，卻和暖如春远荠，著一層夾襖步出監(jiān)牢的瞬間譬淳，已是汗流浹背盹兢。一陣腳步聲響...
開封第一講書人閱讀 32,818評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國(guó)打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留浦妄，地道東北人见芹。一個(gè)月前我還...
沈念sama閱讀 47,711評(píng)論 2贊 368
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像玄呛，于是被迫代替她去往敵國(guó)和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子故黑，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,601評(píng)論 2贊 353

感知機(jī)模型(Perceptron)的收斂性解讀 | 統(tǒng)計(jì)學(xué)習(xí)方法

算法的收斂性：

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