圖解機器學習讀書筆記-CH8:SVM分類

間隔最大化分類

考慮二分類:
f_{\omega,\gamma}(x) = \omega^Tx + \gamma
\omega為分割樣本的超平面的法線, \gamma為截距.

2018-08-29 at 上午9.27.png

對各樣本間隔m_i=f_{\omega, \gamma}(x_i)y_i為正時的\omega和\gamma學習.

閉集約束條件: (\omega^Tx_i+\gamma)y_i \ge 1, \forall i = 1, \cdots, n

以上\omega和\gamma存在時,稱訓練樣本線性可分.

硬間隔SVM

分割最充分的超平面為最優(yōu)解, 對應正則化后的間隔的最小值:

2018-08-29 at 上午9.38.png
  • 正則化間隔m_i:
    m_i = \frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}
  • m_i最大化:
    \max\left\{\frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}\right\}_{I=1}^n = \frac{1}{\|\omega\|}

從幾何學來講, 間隔為兩端的兩個超平面\omega^Tx+\gamma=+1和\omega^Tx+\gamma=-1的間距的一半, 使這個間隔最大的超平面對應的分類器稱為硬間隔支持向量機分類器:

軟間隔SVM

硬間隔SVM假定訓練樣本線性可分, 軟件個SVM允許間隔計算出現(xiàn)少量誤差:
min_{\omega,\gamma,\varepsilon}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\varepsilon_i\right]\; 約束條件\;(\omega^Tx_i + \gamma)y_i \ge 1- \varepsilon_i, \varepsilon_i =\ge 0,\forall i=1,\cdots, n

C>0是調(diào)整誤差范圍參數(shù), C越大, \sum_{i=1}^n\varepsilon_i越接近0, 軟間隔SVM越接近硬間隔SVM.

通常的SVM指軟間隔SVM.

2018-08-29 at 上午9.44.png

SVM分類器求解

SVM最優(yōu)化問題是目標函數(shù)為二次函數(shù), 約束條件為線性的典型二次規(guī)劃問題:

二次規(guī)劃求解

導入拉格朗日變量:
L( \omega, \gamma, \xi, \alpha, \beta) = \frac{1}{2}\|\delta\|^2 + C \sum_{i=1}^n\xi{i} - \sum_{i=1}^n\alpha_i \left( ( \omega^T x_i+\gamma)y_i - 1 + \xi_i \right) - \sum_{i=1}^n\beta_i\xi_i

考慮最優(yōu)化問題等價表現(xiàn)形式--拉格朗日對偶問題:
\underset{ \alpha, \beta}{max} \; \underset{ \omega, \gamma, \xi}{inf}\; L( \omega, \gamma, \xi, \alpha, \beta)\; s.t.\; \alpha \ge 0, \beta \ge 0

根據(jù)最優(yōu)解條件可得:
\frac{\partial }{\partial \omega}L = 0 => \omega = \sum_{i=1}^n\alpha_iy_ix_i \\ \frac{\partial }{\partial \gamma}L = 0 => \sum_{i=1}^n\alpha_iy_i = 0 \\ \frac{\partial }{\partial \xi}L = 0 => \alpha_i + \beta_i = C, \forall i=1,\cdots,n

消去松弛變量\varepsilon可得拉格朗日對偶問題如下公式:

\hat \alpha = \underset{\alpha}{argmax}\left[\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_jx_i^T \right]\; 約束條件\;\sum_{i=1}^n\alpha_iy_i = 0, 0 \le \alpha_i \le C\;, \forall i = 1,\cdots,n
上述最優(yōu)化問題, 利用只有n個最優(yōu)變量的二次規(guī)劃問題, 求解比原始最優(yōu)化問題跟高效. 原始的最優(yōu)化問題:
min_{\omega,\gamma,\varepsilon}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\varepsilon_i\right]\; 約束條件\;(\omega^Tx_i + \gamma)y_i \ge 1- \varepsilon_i, \varepsilon_i =\ge 0,\forall i=1,\cdots, n

拉格朗日對偶問題的解用\hat \alpha表示, 則SVM的解\hat \omega為:
\hat\omega = \sum_{i=1}^n\hat \alpha_iy_i\mathbf x_i
截距的解\hat \gamma:
\hat \gamma = y_i - \sum_{j:\hat \alpha_i>0} \hat \alpha_jy_jx_i^Tx_j

稀疏性

KKT條件

對偶解的最優(yōu)條件即KKT條件. 對偶變量和約束條件滿足互補關系:
\alpha_i(m_i-1+\xi_i) = 0,\beta_i\xi_i = 0,\forall i = 1, \cdots, n
KKT條件:

KKT條件

核映射非線性模型

核映射使得SVM可以應用于非線性模型. 使用非線性函數(shù)\psi對輸入樣本\{x_i\}_{=1}^n使用線性SVM分類器.這種特征空間內(nèi)的線性分類器, 在輸入空間是非線性分類器.

如果特征空間維數(shù)比輸入空間維數(shù)d更高,則樣本線性可分的可能性更大, 然而特征空間維數(shù)過大, 計算量也會響應增加.

核映射可顯著降低計算量: 學習時, 線性SVM分類器樣本空間輸入只存在內(nèi)積形式x_i^Tx_j=\langle x_i,x_j \rangle; 非線性SVM分類器特征空間輸入只存在內(nèi)積形式\langle \psi(x_i), \psi(x_j) \rangle

核映射優(yōu)勢:

  • 通過核函數(shù)K( x,x')定義內(nèi)積\langle \psi(x_i), \psi(x_j)\rangle, 不需要知道特征變換\psi具體是什么.
  • 輸入x不是向量, 也可以正確分類.

常見的核函數(shù):
多項式核函數(shù)
K( x, x') = ( x^Tx' + c)^p
高斯核函數(shù)
K( x, x') = exp\left(- \frac{\| x -x'\|^2}{2h^2}\right)

核映射方法適用于只關注內(nèi)積的任何算法, 如聚類分析, 降維,將現(xiàn)行算法輕松轉(zhuǎn)化為非線性.

Hinge損失最小化

考慮將SVM分類作為最小二乘分類的擴展.
SVM分類器將0/1損失作為間隔m = f_\theta( x)y的函數(shù)單調(diào)非增, 但是二乘L_2損失不是單調(diào)非增, 直接應用有些不自然, 故考慮將如下Hinge損失作為代理損失:
max\{0, 1-m\}
Hinge損失在m<1時有線性遞增趨勢, 即分類錯誤時, 損失無窮遞增

Hinge損失和0/1損失函數(shù)圖像:


Hinge損失和0/1損失

Hinge損失最小化學習:
min_{\theta} = \sum_{i=1}^nmax\{0, 1-f_{\theta}( x_i)y_i\}

回顧線性分類問題和和模型分類問題
線性分類:
f_{\omega, \gamma}(x) = \omega^Tx+\gamma = \sum_{i=1}^n\omega_ix_i + \gamma

核模型分類問題:
f_{\theta, \gamma} = \sum_{j=1}^n\theta_jK(x,x_j)+\gamma

對核模型分類問題進行Hinge損失最小化學習, 引入核矩陣K_{i,j} = K(x_i, x_j)的L_2正則化項:
\underset{\theta, \gamma}{min}[ C\sum_{i=1}^nmax\{0, 1- f_{\theta, \gamma}(x_i)y \} + \frac{1}{2}\sum_{i,j=1}^n\theta_i\theta_jK(x_i, x_j) ]

Ramp損失的魯棒學習

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 人面猴
    序言：七十年代末拗馒，一起剝皮案震驚了整個濱河市屯伞，隨后出現(xiàn)的幾起案子挽懦，更是在濱河造成了極大的恐慌峻贮，老刑警劉巖，帶你破解...
    沈念sama閱讀 211,376評論 6贊 491
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異，居然都是意外死亡，警方通過查閱死者的電腦和手機欢峰，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,126評論 2贊 385
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進店門粘室，熙熙樓的掌柜王于貴愁眉苦臉地迎上來划咐，“玉大人，你說我怎么就攤上這事柜蜈【俜矗” “怎么了懊直？”我有些...
    開封第一講書人閱讀 156,966評論 0贊 347
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長火鼻。 經(jīng)常有香客問我室囊，道長，這世上最難降的妖魔是什么魁索？ 我笑而不...
    開封第一講書人閱讀 56,432評論 1贊 283
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任融撞，我火速辦了婚禮，結(jié)果婚禮上粗蔚，老公的妹妹穿的比我還像新娘尝偎。我一直安慰自己，他們只是感情好，可當我...
    茶點故事閱讀 65,519評論 6贊 385
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布致扯。 她就那樣靜靜地躺著肤寝，像睡著了一般。 火紅的嫁衣襯著肌膚如雪抖僵。 梳的紋絲不亂的頭發(fā)上鲤看，一...
    開封第一講書人閱讀 49,792評論 1贊 290
  • 城市分裂傳說
    那天，我揣著相機與錄音耍群，去河邊找鬼义桂。 笑死，一個胖子當著我的面吹牛蹈垢，可吹牛的內(nèi)容都是我干的澡刹。 我是一名探鬼主播，決...
    沈念sama閱讀 38,933評論 3贊 406
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼耘婚，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了陆赋？” 一聲冷哼從身側(cè)響起沐祷，我...
    開封第一講書人閱讀 37,701評論 0贊 266
  • 萬榮殺人案實錄
    序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎攒岛，沒想到半個月后赖临，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 44,143評論 1贊 303
  • ?護林員之死
    正文 獨居荒郊野嶺守林人離奇死亡灾锯，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 36,488評論 2贊 327
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年兢榨，在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片顺饮。...
    茶點故事閱讀 38,626評論 1贊 340
  • 活死人
    序言：一個原本活蹦亂跳的男人離奇死亡吵聪，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出兼雄，到底是詐尸還是另有隱情吟逝，我是刑警寧澤，帶...
    沈念sama閱讀 34,292評論 4贊 329
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布赦肋，位于F島的核電站块攒，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏佃乘。R本人自食惡果不足惜囱井，卻給世界環(huán)境...
    茶點故事閱讀 39,896評論 3贊 313
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望趣避。 院中可真熱鬧庞呕，春花似錦、人聲如沸程帕。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,742評論 0贊 21
  • 一樁弒父案料祠，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至澎羞，卻和暖如春髓绽，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背妆绞。 一陣腳步聲響...
    開封第一講書人閱讀 31,977評論 1贊 265
  • 情欲美人皮
    我被黑心中介騙來泰國打工顺呕， 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人括饶。 一個月前我還...
    沈念sama閱讀 46,324評論 2贊 360
  • 代替公主和親
    正文 我出身青樓株茶，卻偏偏與公主長得像，于是被迫代替她去往敵國和親图焰。 傳聞我的和親對象是個殘疾皇子启盛，可洞房花燭夜當晚...
    茶點故事閱讀 43,494評論 2贊 348

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