統(tǒng)計(jì)機(jī)器學(xué)習(xí)-感知機(jī)

感知機(jī)是二分類的線性分類模型挤庇，即通過(guò)一個(gè)超平面將數(shù)據(jù)集分割在兩側(cè)顷啼，同在一個(gè)側(cè)的為同一個(gè)分類，一般上側(cè)的為正例七兜，下側(cè)的為負(fù)例壤靶。

感知機(jī)的定義

假設(shè)輸入空間（特征空間）是 $\mathcal X\subseteq\textbf R^n$ ，輸出空間是 $\mathcal Y= \{+1,-1\}$ 惊搏。輸入 $x\in\mathcal X$ 表示實(shí)例的特征向量贮乳，對(duì)應(yīng)于輸入空間（特征空間）的點(diǎn)；輸出 $y\in\mathcal Y$ 表示實(shí)例的類別恬惯。由輸入空間到輸出空間的如下函數(shù)
$f(x)=\mathrm{sign}(w\cdot x+b)$
稱為感知機(jī)向拆。其中， $w$ 和 $b$ 為感知機(jī)模型參數(shù)酪耳， $w\in\textbf R^n$ 叫做權(quán)值或權(quán)值向量浓恳， $b\in\textbf R$ 叫做偏置刹缝， $w\cdot x$ 表示 $w$ 和 $x$ 的內(nèi)積。 $\mathrm{sign}$ 是符號(hào)函數(shù)颈将，即
$\mathrm{sign}= \begin{cases} +1,&x\geq0\\ -1,&x\lt0 \end{cases}$
并且假設(shè)數(shù)據(jù)是完全線性可分的梢夯，即可以通過(guò)一個(gè)超平面，將數(shù)據(jù)完全正確的分割在其兩側(cè)晴圾。當(dāng)數(shù)據(jù)線性不可分時(shí)颂砸，感知機(jī)算法不收斂。

感知機(jī)的損失函數(shù)

假設(shè) $M$ 為誤分類點(diǎn)的集合死姚，則感知機(jī)的損失可以表示為
$L(w,b)=-\frac1{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)\tag1$
$||w||$ 是 $w$ 的 $L_2$ 范數(shù)人乓。最小化該損失的目的是，最小化誤分類點(diǎn)到超平面的距離之和都毒。因?yàn)辄c(diǎn)到平面的距離公式
$\frac{|w\cdot x_i+b|}{||w||}$
當(dāng)誤分類時(shí)色罚，如果 $y_i=+1$ ，模型給出的預(yù)測(cè)應(yīng)該是 $w\cdot x+b\lt0$ 账劲，此時(shí) $|w\cdot x_i+b|=-y_i(w\cdot x_i+b)$ 戳护，反之同理，所以 $-\frac{y_i(w\cdot x_i+b)}{||w||}$ 是誤分類點(diǎn)到超平面的距離瀑焦。由于對(duì)于某個(gè)超平面腌且， $\frac1{||w||}$ 固定，所以不考慮這一項(xiàng)蝠猬，公式(1)中的損失可以簡(jiǎn)化為
$L(w,b)=-\sum_{x_i\in M}y_i(w\cdot x_i+b)\tag2$

感知機(jī)的學(xué)習(xí)算法

感知機(jī)學(xué)習(xí)通常使用梯度下降算法切蟋，分為原始形式和對(duì)偶形式统捶，對(duì)偶形式相比原始形式榆芦，提高了計(jì)算效率。

使用梯度下降喘鸟，首先計(jì)算參數(shù)的梯度匆绣，然后向負(fù)梯度的方向更新參數(shù)：
$\nabla_wL(w,b)=-\sum_{x_i\in M}y_ix_i$

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

隨機(jī)選取一個(gè)誤分類點(diǎn) $(x_i,y_i)$ ，對(duì) $w,b$ 進(jìn)行更新：
$w\leftarrow w+\eta y_ix_i\tag3$

$b\leftarrow b+\eta y_i\tag4$

其中 $0\lt\eta\leq1$ 是步長(zhǎng)什黑，又叫學(xué)習(xí)率崎淳。

感知機(jī)學(xué)習(xí)算法的原始形式

輸入：訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ ，其中 $x_i\in\mathcal X=\textbf R^n$ 愕把， $y_i\in\mathcal Y= \{+1,-1\}$ 拣凹， $i=1,2,\cdots,N$ ；學(xué)習(xí)率 $\eta(0\lt\eta\leq1)$ 恨豁；

輸出： $w,b$ 嚣镜；感知機(jī)模型 $f(x)=\mathrm{sign}(w\cdot x+b)$ 。

（1）選取初值 $w_0,b_0$

（2）在訓(xùn)練數(shù)據(jù)中選取數(shù)據(jù) $(x_i,y_i)$

（3）如果 $y_i(w\cdot x_i+b)\leq0$ 橘蜜，即誤分類菊匿，此時(shí)更新參數(shù)
$w\leftarrow w+\eta y_ix_i$

$b\leftarrow b+\eta y_i\tag4$

（4）轉(zhuǎn)至(2)，直到訓(xùn)練集中沒(méi)有誤分類點(diǎn)。

感知機(jī)學(xué)習(xí)算法的對(duì)偶形式

由原始形式可以看出跌捆，當(dāng)模型收斂時(shí)徽职，假設(shè)參數(shù) $w,b$ 通過(guò)第 $i$ 個(gè)樣本 $(x_i,y_i)$ 更新了 $n_i$ 次，對(duì)于 $N$ 個(gè)樣本佩厚，參數(shù)的更新可以表示為：
$w\leftarrow w_0+\sum_{i=1}^Nn_i\eta y_ix_i$

$b\leftarrow b_0+\sum_{i=1}^Nn_i\eta y_i$

假設(shè)參數(shù)的初值都選取為0姆钉，并且令 $\alpha_i=n_i\eta$ ，則參數(shù)可以表示為
$w=\sum_{i=1}^N\alpha_iy_ix_i\tag5$

$b=\sum_{i=1}^N\alpha_iy_i\tag6$

$\alpha_i$ 越大說(shuō)明根據(jù)第 $i$ 個(gè)樣本更新的越多可款，這個(gè)樣本就越難區(qū)分育韩，對(duì)決定超平面影響也最大。此時(shí)感知機(jī)模型可以表示為：
$f(x)=\mathrm{sign}\bigg(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b\bigg)$
下面給出感知及學(xué)習(xí)算法的對(duì)偶形式：

感知機(jī)學(xué)習(xí)算法的對(duì)偶形式

輸入：訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$ 闺鲸，其中 $x_i\in\mathcal X=\textbf R^n$ 筋讨， $y_i\in\mathcal Y= \{+1,-1\}$ ， $i=1,2,\cdots,N$ 摸恍；學(xué)習(xí)率 $\eta(0\lt\eta\leq1)$ 悉罕；

輸出： $\alpha,b$ ；感知機(jī)模型 $f(x)=\mathrm{sign}\bigg(\sum_{j=1}^N\alpha_jy_jx_j\cdot x+b\bigg)$ 立镶，其中 $\alpha=(\alpha_1,\alpha_2,\cdots,\alpha_N)^T$ 壁袄。

（1） $\alpha\leftarrow0$ ， $b\leftarrow0$

（2）在訓(xùn)練集中選取數(shù)據(jù) $(x_i,y_i)$

（3）如果 $y_i\bigg(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i+b\bigg)\leq0$ 媚媒，即誤分類嗜逻，此時(shí)更新參數(shù)
$\alpha_i\leftarrow \alpha_i+\eta$

$b\leftarrow b+\eta y_i$

（4）轉(zhuǎn)至(2)直到?jīng)]有誤分類數(shù)據(jù)。

這種方式相比原始形式判斷誤分類 $y_i(w\cdot x_i+b)\leq0$ 的方式缭召， $y_i\bigg(\sum_{j=1}^N\alpha_jy_jx_j\cdot x_i+b\bigg)\leq0$ 的方式可以把 $x_i\cdot x_j$ 的結(jié)果預(yù)存在矩陣中栈顷，加快判斷的速度。滿足下面形式的矩陣叫做 $\mathrm{Gram}$ 矩陣：
$G=[x_i\cdot x_j]_{N\times N}$

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

人面猴
序言：七十年代末嵌巷，一起剝皮案震驚了整個(gè)濱河市萄凤，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌搪哪，老刑警劉巖靡努，帶你破解...
沈念sama閱讀 211,376評(píng)論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異晓折，居然都是意外死亡惑朦，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,126評(píng)論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門漓概，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)漾月，“玉大人，你說(shuō)我怎么就攤上這事垛耳≌て粒” “怎么了飘千？”我有些...
開(kāi)封第一講書人閱讀 156,966評(píng)論 0贊 347
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)栈雳。經(jīng)常有香客問(wèn)我护奈，道長(zhǎng)，這世上最難降的妖魔是什么哥纫？我笑而不...
開(kāi)封第一講書人閱讀 56,432評(píng)論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任霉旗，我火速辦了婚禮，結(jié)果婚禮上蛀骇，老公的妹妹穿的比我還像新娘厌秒。我一直安慰自己，他們只是感情好擅憔，可當(dāng)我...
茶點(diǎn)故事閱讀 65,519評(píng)論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布鸵闪。她就那樣靜靜地躺著，像睡著了一般暑诸。火紅的嫁衣襯著肌膚如雪蚌讼。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書人閱讀 49,792評(píng)論 1贊 290
城市分裂傳說(shuō)
那天个榕，我揣著相機(jī)與錄音篡石，去河邊找鬼。笑死西采，一個(gè)胖子當(dāng)著我的面吹牛凰萨，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播械馆，決...
沈念sama閱讀 38,933評(píng)論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼胖眷，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了狱杰？” 一聲冷哼從身側(cè)響起瘦材，我...
開(kāi)封第一講書人閱讀 37,701評(píng)論 0贊 266
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤厅须，失蹤者是張志新（化名）和其女友劉穎仿畸，沒(méi)想到半個(gè)月后，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體朗和，經(jīng)...
沈念sama閱讀 44,143評(píng)論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡错沽，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,488評(píng)論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了眶拉。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片千埃。...
茶點(diǎn)故事閱讀 38,626評(píng)論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡，死狀恐怖忆植，靈堂內(nèi)的尸體忽然破棺而出放可，到底是詐尸還是另有隱情谒臼，我是刑警寧澤，帶...
沈念sama閱讀 34,292評(píng)論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布耀里，位于F島的核電站蜈缤，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏冯挎。R本人自食惡果不足惜底哥，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,896評(píng)論 3贊 313
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望房官。院中可真熱鬧趾徽，春花似錦、人聲如沸翰守。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,742評(píng)論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)蜡峰。三九已至拒课，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間事示，已是汗流浹背早像。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,977評(píng)論 1贊 265
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留肖爵，地道東北人卢鹦。一個(gè)月前我還...
沈念sama閱讀 46,324評(píng)論 2贊 360
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像劝堪，于是被迫代替她去往敵國(guó)和親冀自。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,494評(píng)論 2贊 348