Day5~6 第二章 感知機(jī)


1?感知機(jī)模型

??定義 2.1 (感知機(jī))?假設(shè)輸入空間是 \mathcal{X}\subseteq\mathbb{R}^n,輸出空間是 \mathcal{Y}=\{+1,-1\}部宿。輸入 x\in\mathcal{X} 表示實(shí)例的特征向量抄腔,對(duì)應(yīng)輸出空間的的點(diǎn);輸出 y\in\mathcal{Y} 表示實(shí)例的類別理张。由輸入控件到輸出空間的如下函數(shù):f(x)=\text{sgn}(\omega \cdot x+b)稱為感知機(jī)赫蛇。其中,\omegab 為感知機(jī)模型的參數(shù)涯穷,\omega \in \mathbb{R}^n叫做權(quán)值 (weight) 或權(quán)值向量 (weight vector)棍掐,b\in\mathbb{R}^n 叫做偏置 (bias)\omega\cdot x 表示 \omegax 的內(nèi)積拷况,\text{sgn} 是符號(hào)函數(shù)作煌。
??感知機(jī)是一種線性分類模型掘殴,屬于判別模型。感知機(jī)模型的假設(shè)空間是定義在特征空間中的所有線性分類模型粟誓,即函數(shù)集合 \{f|f(x)=\omega\cdot x+b\}奏寨。


2?感知機(jī)學(xué)習(xí)策略

2.1?數(shù)據(jù)集的線性可分性

??定義 2.2 (數(shù)據(jù)集的線性可分性)?給定一個(gè)數(shù)據(jù)集T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\}其中,x_i\in\mathcal{X}=\mathbb{R}^n鹰服,y_i\in\mathcal{Y}=\{+1,-1\}病瞳,i=1,2,\dots ,N,若存在某個(gè)超平面 S 能夠?qū)?shù)據(jù)集的正實(shí)例點(diǎn)與負(fù)實(shí)例點(diǎn)完全正確地劃分到超平面的兩側(cè)悲酷,則稱數(shù)據(jù)集 T線性可分?jǐn)?shù)據(jù)集 (linearly swparaable data set)套菜;否則,稱數(shù)據(jù)集 T 線性不可分设易。
??數(shù)據(jù)集是線性可分的是感知機(jī)學(xué)習(xí)最基本的假設(shè)之一逗柴。

2.2?感知機(jī)學(xué)習(xí)策略

??感知機(jī)的學(xué)習(xí)目標(biāo)是求得一個(gè)能夠?qū)⒂?xùn)練集正實(shí)例點(diǎn)和負(fù)實(shí)例點(diǎn)完全正確分開的超平面。為此我們需要定義一個(gè)包含模型參數(shù) \omegab 的損失函數(shù)并將其極小化顿肺。
??通常地戏溺,我們選擇誤分類點(diǎn)到超平面 S 的總距離作為損失函數(shù),這樣得到的函數(shù)往往具有連續(xù)可導(dǎo)等良好性質(zhì)屠尊,便于優(yōu)化計(jì)算旷祸。
??假設(shè)超平面 S 的誤分類點(diǎn)集合為 M,給定數(shù)據(jù)集 T 同定義 2.2讼昆,那么所有誤分類點(diǎn)到超平面 S 的總距離為-\frac{1}{||\omega||}\sum\limits_{x_i\in M} y_i(\omega \cdot x_i+b)其中托享,||\omega|| 表示 \omegaL_2 范數(shù)。

??不難注意到 1/||\omega|| 恒為正數(shù)浸赫,將其舍去一方面不影響超平面對(duì)實(shí)例點(diǎn)的劃分嫌吠,另一方面可以避免大數(shù)除以小數(shù)以避免舍入誤差顾彰。實(shí)際上 y(\omega\cdot x+b) 稱為樣本點(diǎn)的函數(shù)間隔宪潮,是衡量點(diǎn)與平面間隔大小的重要指標(biāo)之一驹尼。

??這樣就得到了感知機(jī)學(xué)習(xí)的損失函數(shù):L(\omega,b)=-\sum\limits_{x_i\in M} y_i(\omega \cdot x_i+b)


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

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

??假設(shè)超平面 S 的誤分類點(diǎn)集合為 M筝家,給定數(shù)據(jù)集 T 同定義 2.2罪郊,根據(jù) 2.2 小節(jié)的分析反璃,我們已經(jīng)得到感知機(jī)學(xué)習(xí)策略等價(jià)于求解含參數(shù) \omegab 的如下最優(yōu)化問(wèn)題\min\limits_{\omega,b} L(\omega,b) = \min\limits_{\omega,b}\left\{- \sum\limits_{x_i\in M} y_i(\omega \cdot x_i+b)\right\}??感知機(jī)學(xué)習(xí)算法采用的是隨機(jī)梯度下降法 (stochastic gradient descent)取董。

??梯度下降法是沿著函數(shù)下降最快的方向即梯度方向進(jìn)行迭代搜索盐茎,對(duì)于參數(shù) \omegab的更新者冤,所有的樣本都有貢獻(xiàn)\left( \begin{array}{l} \omega^T \\ b \end{array} \right) \leftarrow \left( \begin{array}{l} \omega^T \\ b \end{array} \right)- \eta\ \big(\text{grad}\ L(\omega ,b)\big)^T = \left( \begin{array}{l} \omega^T+\eta\sum\limits_{x_i\in M} y_ix_i^T \\ b+\eta\sum\limits_{x_i\in M} y_i\end{array} \right)其中 \eta(0<\eta\leqslant 1)為步長(zhǎng)肤视,在統(tǒng)計(jì)學(xué)習(xí)中又稱為學(xué)習(xí)率(learning rate)。
??而隨機(jī)梯度法是用樣本中的一個(gè)例子來(lái)近似所有的樣本\left( \begin{array}{l} \omega^T \\ b \end{array} \right) \leftarrow \left( \begin{array}{l} \omega^T \\ b \end{array} \right) +\eta\left( \begin{array}{l} y_ix_i^T \\ \ \ \ y_i \end{array} \right)其中涉枫,\eta(0<\eta\leqslant 1)為步長(zhǎng)邢滑。
??隨機(jī)梯度法相較于梯度下降法的優(yōu)點(diǎn)是當(dāng)樣本量很大時(shí),訓(xùn)練速度是非吃柑快的(因?yàn)樘荻认陆邓惴看蔚家玫饺繕颖?困后,并且可以進(jìn)行在線更新乐纸。但是隨機(jī)梯度下降最大的缺點(diǎn)在于每次學(xué)習(xí)可能并不會(huì)按照正確的方向進(jìn)行,因此可能帶來(lái)優(yōu)化波動(dòng)(擾動(dòng))摇予,并且容易陷入局部最優(yōu)點(diǎn)汽绢。
??另外,有一種折中的辦法稱為小批量梯度下降法 (mini-batch gradient descent)侧戴,算法使用了一些小樣本來(lái)近似全部的樣本宁昭。相對(duì)于隨機(jī)梯度下降,其降低了收斂波動(dòng)性酗宋,即降低了參數(shù)更新的方差积仗,使得更新更加穩(wěn)定。相對(duì)于全量梯度下降蜕猫,其提高了每次學(xué)習(xí)的速度斥扛。這個(gè)方法在神經(jīng)網(wǎng)絡(luò)訓(xùn)練中是非常常用的。

??通過(guò)上述分析丹锹,得到如下算法:
??算法2.1(感知機(jī)學(xué)習(xí)算法的原始形式)
??輸入:訓(xùn)練數(shù)據(jù)集 T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\},其中x_i\in\mathcal{X}=\mathbb{R}^n芬失,y_i\in\mathcal{Y}=\{+1,-1\}楣黍,i=1,2,\dots,N;學(xué)習(xí)率\eta(0<\eta\leqslant 1)棱烂;
??輸出:\omega ,b租漂;感知機(jī)模型f(x)=\text{sgn}(\omega\cdot x+b)
??(1) 選取初值\omega_0,b_0;
??(2) 在訓(xùn)練集中選取數(shù)據(jù)x_i,y_i颊糜;
??(3) 若y_i(\omega\cdot x_i +b)\leqslant 0哩治,則\omega\leftarrow\omega+\eta\ y_ix_i b\leftarrow b+\eta\ y_i??(4) 轉(zhuǎn)至 (2),直至訓(xùn)練集中沒有誤分類點(diǎn)衬鱼。

注:不難發(fā)現(xiàn)业筏,若數(shù)據(jù)集不可分則該算法將會(huì)一直迭代下去。

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

??對(duì)偶形式的基本想法是鸟赫,wb 表示為實(shí)例 x_i 和標(biāo)記 y_i 的組合形式蒜胖,通過(guò)求解其系數(shù)來(lái)求解 wb。不失一般性抛蚤,假設(shè)算法 2.1 中 wb 初始值都為 0台谢。逐步對(duì)參數(shù) \omegab 進(jìn)行迭代,迭代 n 次后岁经,參數(shù) \omegab 可表示為:\omega=\sum_{i=1}^N\alpha_i y_ix_i,\quad b=\sum_{i=1}^N\alpha_i y_i 其中 \alpha_i=n_i \eta朋沮,\sum\limits_{i=1}^N n_i = nn_i 表示第 i 個(gè)實(shí)例點(diǎn)由于誤分而進(jìn)入迭代的次數(shù)缀壤。n_i 越大樊拓,表明該實(shí)例點(diǎn)被選用的次數(shù)越多纠亚,也就是越接近超平面,從而越容易被分錯(cuò)骑脱。
??通過(guò)上述分析菜枷,得到如下算法:
??算法2.2(感知機(jī)學(xué)習(xí)算法的對(duì)偶形式)
??輸入:訓(xùn)練數(shù)據(jù)集 T=\{(x_1,y_1),(x_2,y_2),\dots ,(x_N,y_N)\},其中x_i\in\mathcal{X}=\mathbb{R}^n叁丧,y_i\in\mathcal{Y}=\{+1,-1\}啤誊,i=1,2,\dots,N;學(xué)習(xí)率\eta(0<\eta\leqslant 1)拥娄;
??輸出:\omega ,b蚊锹;感知機(jī)模型f(x)=\text{sgn}(\sum\limits_{j=1}^N \alpha_j y_j x_j \cdot x+b)
??(1) 選取初值\alpha_0=,b_0=0;
??(2) 在訓(xùn)練集中選取數(shù)據(jù)x_i,y_i稚瘾;
??(3) 若y_i\left(\sum\limits_{j=1}^N \alpha_j y_j x_j \cdot x_i +b\right)\leqslant 0牡昆,則\alpha\leftarrow\alpha+\eta b\leftarrow b+\eta\ y_i??(4) 轉(zhuǎn)至 (2),直至訓(xùn)練集中沒有誤分類點(diǎn)摊欠。

??對(duì)偶形式只用計(jì)算 x_ix_j 的內(nèi)積丢烘,而避免了在迭代過(guò)程中 \omegax_i 的內(nèi)積計(jì)算⌒┙罚可以預(yù)先將訓(xùn)練集中的實(shí)例間的內(nèi)積計(jì)算出來(lái)并以矩陣的形式儲(chǔ)存播瞳,即 Gram 矩陣,這樣能夠減少在迭代學(xué)習(xí)過(guò)程中的計(jì)算免糕,加快學(xué)習(xí)速率赢乓。


4?習(xí)題

習(xí)題 2.3?證明以下定理:樣本集線性可分的充要條件是正實(shí)例點(diǎn)集所構(gòu)成的凸殼與負(fù)實(shí)例點(diǎn)集所構(gòu)成的凸殼互不相交。

證明:
??設(shè)集合 S\subset \mathbb{R}^nk 個(gè)點(diǎn)組成:S = \{x_1,\dots,x_k\}石窑。那么根據(jù)定義 S 的凸殼 \text{conv(S)}\text{conv}(S)=\left\{x=\sum\limits_{i=1}^k \lambda_i x_i \bigg|\sum\limits_{i=1}^k \lambda_i=1, \lambda_i\geqslant 0, i=1,2,\dots ,k \right\}??設(shè)正實(shí)例點(diǎn)集為 S^+牌芋,其構(gòu)成的凸殼為 \text{conv}(S^+);設(shè)負(fù)實(shí)例點(diǎn)集為 S^-松逊,其構(gòu)成的凸殼 為\text{conv}(S^-)躺屁。
??不失一般性,設(shè) x_1,\dots,x_{m} \in S^+经宏,x_{m+1},\dots,x_{k} \in S^-楼咳。
(1)必要性
??必要性的直接證明比較復(fù)雜,我的想法是由于凸殼是一個(gè)凸集烛恤,再參考最優(yōu)化理論里的 凸集分離定理 即可得證母怜。證明凸殼是凸集是簡(jiǎn)單的,這里以證明 \text{conv}(S^+) 是凸集為例:
??\forall v_1 ,v_2 \in \text{conv}(S^+), \exists \lambda_1,\dots,\lambda_m,\eta_1,\dots,\eta_m\geqslant 0, 滿足\Sigma\lambda_i=\Sigma\eta_i=1. 且v_1=\sum\limits_{i=1}^m\lambda_ix_i, \quad v_2=\sum\limits_{i=1}^m\eta_ix_i??于是\forall \xi\in[0,1]
\begin{align} \xi v_1+(1-\xi )v_2 = & \,\, \xi\sum\limits_{i=1}^m\lambda_ix_i+(1-\xi)\sum\limits_{i=1}^m\eta_ix_i\\ = & \,\sum\limits_{i=1}^m \big(\xi\lambda_i+(1-\xi)\eta_i\big)x_i\\ \end{align}??令\tau_i=\xi\lambda_i+(1-\xi)\eta_i缚柏,由于 \xi\in[0,1]苹熏,故有 \tau_i\geqslant 0i=1,2,\dots m,并且
\begin{align} \sum\limits_{i=1}^m\tau_i = & \,\sum\limits_{i=1}^m \big(\xi\lambda_i+(1-\xi)\eta_i\big)\\ = & \,\, \xi\sum\limits_{i=1}^m\lambda_i+(1-\xi)\sum\limits_{i=1}^m\eta_i\\ = & \,\, \xi+(1-\xi)=1\\ \end{align}??因此 \forall \xi\in[0,1]\xi v_1+(1-\xi)v_2\in \text{conv}(S^+)轨域。即集合內(nèi)任意兩點(diǎn)之間的連線都仍然在集合內(nèi)袱耽,故\text{conv}(S^+)是凸集。根據(jù)凸集分離定理即可得證干发。凸集分離定理的證明這里就不再重復(fù)了朱巨,可參考開頭給出的參考資料。
??直接的證明方法可參考 統(tǒng)計(jì)學(xué)習(xí)方法習(xí)題解答 第2章 感知機(jī)枉长。

(2)充分性
??根據(jù)線性可分的定義冀续,必然存在 \omegab ,使得 \forall x_i\in S 以及對(duì)應(yīng)的 y_i 滿足 y_i(\omega\cdot x_i+b)>0,\ i=1,2,\dots k??反證法必峰。假設(shè)正實(shí)例點(diǎn)集所構(gòu)成的凸殼與負(fù)實(shí)例點(diǎn)集所構(gòu)成的凸殼相交洪唐。則 \exists x^*\in S 滿足 x^*\in \text{conv}(S^+),且x^*\in \text{conv}(S^-)吼蚁。
??①一方面由于 x^*\in \text{conv}(S^+)凭需,可得 x^*=\sum\limits_{i=1}^m\eta_ix_i滿足\sum\limits_{i=1}^m \eta_i=1, \eta_i\geqslant 0, i=1,\dots ,m,從而\begin{align} \omega \cdot x^*+b= & \,\, \omega \cdot \sum\limits_{i=1}^m\eta_ix_i+b\\ = & \,\,\omega \cdot \sum\limits_{i=1}^m\eta_ix_i+\sum\limits_{i=1}^m\eta_i b\\ = & \,\, \sum\limits_{i=1}^m\eta_i(\omega \cdot x_i+ b)\\ \end{align}由于 \forall x_i\in S^+y_i=1肝匆。結(jié)合線性可分 y_i(\omega\cdot x_i+b)>0粒蜈,從而 \omega\cdot x_i+b>0。再結(jié)合\eta_i\geqslant 0旗国,于是\omega \cdot x^*+b=\sum\limits_{x_i\in S^+}\eta_i(\omega \cdot x_i+ b)>0x^*位于超平面 \omega\cdot x + b 的上方枯怖。
??②另一方面由于 x^*\in \text{conv}(S^-),可得 x^*=\sum\limits_{i=m+1}^k\eta_ix_i滿足\sum\limits_{i=m+1}^k \eta_i=1, \eta_i\geqslant 0, i=1,\dots ,m粗仓,從而\begin{align} \omega \cdot x^*+b= & \,\, \omega \cdot \sum\limits_{i=m+1}^k\eta_ix_i+b\\ = & \,\, \omega \cdot \sum\limits_{i=m+1}^k\eta_ix_i+\sum\limits_{i=m+1}^k\eta_i b\\ = & \sum\limits_{i=m+1}^k\eta_i(\omega \cdot x_i+ b)\\ \end{align}由于 \forall x_i\in S^-y_i=-1。結(jié)合線性可分y_i(\omega\cdot x_i+b)>0设捐,于是\omega\cdot x_i+b<0借浊。再結(jié)合\eta_i\geqslant 0,從而\omega \cdot x^*+b=\sum\limits_{x_i\in S^-}\eta_i(\omega \cdot x_i+ b)<0x^*位于超平面 \omega\cdot x + b 的下方萝招。
??顯然 x^* 不能同時(shí)位于一個(gè)超平面的上方與下方蚂斤,故假設(shè)不成立。因此正實(shí)例點(diǎn)集所構(gòu)成的凸殼與負(fù)實(shí)例點(diǎn)集所構(gòu)成的凸殼互不相交槐沼。充分性得證曙蒸。

最后編輯于
?著作權(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)離奇詭異,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)审孽,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,393評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門县袱,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人佑力,你說(shuō)我怎么就攤上這事式散。” “怎么了打颤?”我有些...
    開封第一講書人閱讀 162,577評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵暴拄,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我瘸洛,道長(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
  • 文/蒼蘭香墨 我猛地睜開眼员寇,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼弄慰!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起蝶锋,我...
    開封第一講書人閱讀 38,903評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤陆爽,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后扳缕,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體墓陈,經(jīng)...
    沈念sama閱讀 45,319評(píng)論 1 310
  • 正文 獨(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
  • 正文 年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
  • 我被黑心中介騙來(lái)泰國(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

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