1?感知機(jī)模型
??定義 2.1 (感知機(jī))?假設(shè)輸入空間是 ,輸出空間是 部宿。輸入 表示實(shí)例的特征向量抄腔,對(duì)應(yīng)輸出空間的的點(diǎn);輸出 表示實(shí)例的類別理张。由輸入控件到輸出空間的如下函數(shù):稱為感知機(jī)赫蛇。其中, 和 為感知機(jī)模型的參數(shù)涯穷,叫做權(quán)值 (weight) 或權(quán)值向量 (weight vector)棍掐, 叫做偏置 (bias), 表示 和 的內(nèi)積拷况, 是符號(hào)函數(shù)作煌。
??感知機(jī)是一種線性分類模型掘殴,屬于判別模型。感知機(jī)模型的假設(shè)空間是定義在特征空間中的所有線性分類模型粟誓,即函數(shù)集合 奏寨。
2?感知機(jī)學(xué)習(xí)策略
2.1?數(shù)據(jù)集的線性可分性
??定義 2.2 (數(shù)據(jù)集的線性可分性)?給定一個(gè)數(shù)據(jù)集其中,鹰服,病瞳,,若存在某個(gè)超平面 能夠?qū)?shù)據(jù)集的正實(shí)例點(diǎn)與負(fù)實(shí)例點(diǎn)完全正確地劃分到超平面的兩側(cè)悲酷,則稱數(shù)據(jù)集 為線性可分?jǐn)?shù)據(jù)集 (linearly swparaable data set)套菜;否則,稱數(shù)據(jù)集 線性不可分设易。
??數(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ù) 與 的損失函數(shù)并將其極小化顿肺。
??通常地戏溺,我們選擇誤分類點(diǎn)到超平面 的總距離作為損失函數(shù),這樣得到的函數(shù)往往具有連續(xù)可導(dǎo)等良好性質(zhì)屠尊,便于優(yōu)化計(jì)算旷祸。
??假設(shè)超平面 的誤分類點(diǎn)集合為 ,給定數(shù)據(jù)集 同定義 2.2讼昆,那么所有誤分類點(diǎn)到超平面 的總距離為其中托享, 表示 的 范數(shù)。
??不難注意到 恒為正數(shù)浸赫,將其舍去一方面不影響超平面對(duì)實(shí)例點(diǎn)的劃分嫌吠,另一方面可以避免大數(shù)除以小數(shù)以避免舍入誤差顾彰。實(shí)際上 稱為樣本點(diǎn)的函數(shù)間隔宪潮,是衡量點(diǎn)與平面間隔大小的重要指標(biāo)之一驹尼。
??這樣就得到了感知機(jī)學(xué)習(xí)的損失函數(shù):
3?感知機(jī)學(xué)習(xí)算法
3.1?感知機(jī)學(xué)習(xí)算法的原始形式
??假設(shè)超平面 的誤分類點(diǎn)集合為 筝家,給定數(shù)據(jù)集 同定義 2.2罪郊,根據(jù) 2.2 小節(jié)的分析反璃,我們已經(jīng)得到感知機(jī)學(xué)習(xí)策略等價(jià)于求解含參數(shù) 與 的如下最優(yōu)化問(wèn)題:??感知機(jī)學(xué)習(xí)算法采用的是隨機(jī)梯度下降法 (stochastic gradient descent)取董。
??梯度下降法是沿著函數(shù)下降最快的方向即梯度方向進(jìn)行迭代搜索盐茎,對(duì)于參數(shù) 與 的更新者冤,所有的樣本都有貢獻(xiàn):其中 為步長(zhǎng)肤视,在統(tǒng)計(jì)學(xué)習(xí)中又稱為學(xué)習(xí)率(learning rate)。
??而隨機(jī)梯度法是用樣本中的一個(gè)例子來(lái)近似所有的樣本:其中涉枫,為步長(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ù)集 ,其中芬失,楣黍,;學(xué)習(xí)率棱烂;
??輸出:租漂;感知機(jī)模型;
??(1) 選取初值;
??(2) 在訓(xùn)練集中選取數(shù)據(jù)颊糜;
??(3) 若哩治,則 ??(4) 轉(zhuǎn)至 (2),直至訓(xùn)練集中沒有誤分類點(diǎn)衬鱼。
注:不難發(fā)現(xiàn)业筏,若數(shù)據(jù)集不可分則該算法將會(huì)一直迭代下去。
3.2?感知機(jī)學(xué)習(xí)算法的對(duì)偶形式
??對(duì)偶形式的基本想法是鸟赫,將 和 表示為實(shí)例 和標(biāo)記 的組合形式蒜胖,通過(guò)求解其系數(shù)來(lái)求解 和 。不失一般性抛蚤,假設(shè)算法 2.1 中 和 初始值都為 0台谢。逐步對(duì)參數(shù) 與 進(jìn)行迭代,迭代 次后岁经,參數(shù) 與 可表示為: 其中 朋沮,, 表示第 個(gè)實(shí)例點(diǎn)由于誤分而進(jìn)入迭代的次數(shù)缀壤。 越大樊拓,表明該實(shí)例點(diǎn)被選用的次數(shù)越多纠亚,也就是越接近超平面,從而越容易被分錯(cuò)骑脱。
??通過(guò)上述分析菜枷,得到如下算法:
??算法2.2(感知機(jī)學(xué)習(xí)算法的對(duì)偶形式)
??輸入:訓(xùn)練數(shù)據(jù)集 ,其中叁丧,啤誊,;學(xué)習(xí)率拥娄;
??輸出:蚊锹;感知機(jī)模型;
??(1) 選取初值;
??(2) 在訓(xùn)練集中選取數(shù)據(jù)稚瘾;
??(3) 若牡昆,則 ??(4) 轉(zhuǎn)至 (2),直至訓(xùn)練集中沒有誤分類點(diǎn)摊欠。
??對(duì)偶形式只用計(jì)算 與 的內(nèi)積丢烘,而避免了在迭代過(guò)程中 與 的內(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è)集合 由 個(gè)點(diǎn)組成:石窑。那么根據(jù)定義 的凸殼 為??設(shè)正實(shí)例點(diǎn)集為 牌芋,其構(gòu)成的凸殼為 ;設(shè)負(fù)實(shí)例點(diǎn)集為 松逊,其構(gòu)成的凸殼 為躺屁。
??不失一般性,設(shè) 楼咳。
(1)必要性
??必要性的直接證明比較復(fù)雜,我的想法是由于凸殼是一個(gè)凸集烛恤,再參考最優(yōu)化理論里的 凸集分離定理 即可得證母怜。證明凸殼是凸集是簡(jiǎn)單的,這里以證明 是凸集為例:
??, 滿足. 且??于是有
??令缚柏,由于 苹熏,故有 ,,并且
??因此 有 轨域。即集合內(nèi)任意兩點(diǎn)之間的連線都仍然在集合內(nèi)袱耽,故是凸集。根據(jù)凸集分離定理即可得證干发。凸集分離定理的證明這里就不再重復(fù)了朱巨,可參考開頭給出的參考資料。
??直接的證明方法可參考 統(tǒng)計(jì)學(xué)習(xí)方法習(xí)題解答 第2章 感知機(jī)枉长。
(2)充分性
??根據(jù)線性可分的定義冀续,必然存在 與 ,使得 以及對(duì)應(yīng)的 滿足 ??反證法必峰。假設(shè)正實(shí)例點(diǎn)集所構(gòu)成的凸殼與負(fù)實(shí)例點(diǎn)集所構(gòu)成的凸殼相交洪唐。則 滿足 ,且吼蚁。
??①一方面由于 凭需,可得 滿足,從而由于 有 肝匆。結(jié)合線性可分 粒蜈,從而 。再結(jié)合旗国,于是故位于超平面 的上方枯怖。
??②另一方面由于 ,可得 滿足粗仓,從而由于 有 。結(jié)合線性可分设捐,于是借浊。再結(jié)合,從而故位于超平面 的下方萝招。
??顯然 不能同時(shí)位于一個(gè)超平面的上方與下方蚂斤,故假設(shè)不成立。因此正實(shí)例點(diǎn)集所構(gòu)成的凸殼與負(fù)實(shí)例點(diǎn)集所構(gòu)成的凸殼互不相交槐沼。充分性得證曙蒸。