機(jī)器學(xué)習(xí)算法深度總結(jié)(4)-SVM

1. 間隔最大化分類

考慮二分類:
$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$ 為正時(shí)的 $\omega$ 和 $\gamma$ 學(xué)習(xí).

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

以上 $\omega$ 和 $\gamma$ 存在時(shí),稱訓(xùn)練樣本線性可分.

2. 硬間隔SVM

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

2018-08-29 at 上午9.38.png

正則化間隔 $m_i$ :
$m_i = \frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}$
$m_i$ 最小化:
$min\left\{\frac{(\omega^Tx_i + \gamma)y_i}{\|\omega\|}\right\}_{I=1}^n = \frac{1}{\|\omega\|}$

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

3. 軟間隔SVM

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

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

通常的SVM指軟間隔SVM.

2018-08-29 at 上午9.44.png

4. SVM求解

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

二次規(guī)劃求解

導(dǎo)入拉格朗日變量:
$L( \omega, \gamma, \xi, \alpha, \beta) = \frac{1}{2}\|\omega\|^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)化問題等價(jià)表現(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_i}L = 0 => \alpha_i + \beta_i = C, \forall i=1,\cdots,n$
消去松弛變量 $\xi_i$ 可得拉格朗日對偶問題如下公式:
$\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^Tx_j \right]\; 約束條件\;\sum_{i=1}^n\alpha_iy_i = 0, 0 \le \alpha_i \le C\;, \forall i = 1,\cdots,n$
上述最優(yōu)化問題, 利用只有n個(gè)最優(yōu)變量的二次規(guī)劃問題, 求解比原始最優(yōu)化問題跟高效. 原始的最優(yōu)化問題:
$min_{\omega,\gamma,\xi}\left[\frac{1}{2}\|\omega\|^2+C\sum_{i=1}^n\xi_i\right]\; 約束條件\;(\omega^Tx_i + \gamma)y_i \ge 1- \xi_i, \xi_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$

5. 稀疏性

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

KKT條件

6. 核映射

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

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

核映射可顯著降低計(jì)算量: 學(xué)習(xí)時(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ù):
多項(xiàng)式核函數(shù)
$K( x, x') = ( x^Tx' + c)^p$
高斯核函數(shù)
$K( x, x') = \exp\left(- \frac{\| x -x'\|^2}{2h^2}\right)$

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

7. hinge損失的二乘求解

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

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

Hinge損失和0/1損失

Hinge損失最小化學(xué)習(xí):
$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$

對核模型分類問題進(jìn)行Hinge損失最小化學(xué)習(xí), 引入核矩陣 $K_{i,j} = K(x_i, x_j)$ 的 $L_2$ 正則化項(xiàng):
$\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) ]$

最后編輯于：2018.10.13 17:35:23

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

人面猴
序言：七十年代末缚忧，一起剝皮案震驚了整個(gè)濱河市忌警，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌利赋，老刑警劉巖，帶你破解...
沈念sama閱讀 211,423評論 6贊 491
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件涩笤，死亡現(xiàn)場離奇詭異匾浪，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)粹淋，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,147評論 2贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來瑟慈，“玉大人桃移，你說我怎么就攤上這事「鸨蹋” “怎么了借杰？”我有些...
開封第一講書人閱讀 157,019評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長进泼。經(jīng)常有香客問我第步，道長，這世上最難降的妖魔是什么缘琅？我笑而不...
開封第一講書人閱讀 56,443評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮廓推，結(jié)果婚禮上刷袍，老公的妹妹穿的比我還像新娘。我一直安慰自己樊展，他們只是感情好呻纹，可當(dāng)我...
茶點(diǎn)故事閱讀 65,535評論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著专缠，像睡著了一般雷酪。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上涝婉，一...
開封第一講書人閱讀 49,798評論 1贊 290
城市分裂傳說
那天哥力，我揣著相機(jī)與錄音，去河邊找鬼。笑死吩跋，一個(gè)胖子當(dāng)著我的面吹牛寞射，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播锌钮，決...
沈念sama閱讀 38,941評論 3贊 407
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼桥温，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了梁丘？” 一聲冷哼從身側(cè)響起侵浸，我...
開封第一講書人閱讀 37,704評論 0贊 266
萬榮殺人案實(shí)錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎氛谜，沒想到半個(gè)月后掏觉，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,152評論 1贊 303
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡混蔼，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 36,494評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年履腋，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片惭嚣。...
茶點(diǎn)故事閱讀 38,629評論 1贊 340
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡遵湖，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出晚吞，到底是詐尸還是另有隱情延旧，我是刑警寧澤，帶...
沈念sama閱讀 34,295評論 4贊 329
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布槽地，位于F島的核電站迁沫，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏捌蚊。R本人自食惡果不足惜集畅，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,901評論 3贊 313
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望缅糟。院中可真熱鬧挺智，春花似錦、人聲如沸窗宦。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,742評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽赴涵。三九已至媒怯，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間髓窜，已是汗流浹背扇苞。一陣腳步聲響...
開封第一講書人閱讀 31,978評論 1贊 266
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人杨拐。一個(gè)月前我還...
沈念sama閱讀 46,333評論 2贊 360
代替公主和親
正文我出身青樓祈餐，卻偏偏與公主長得像，于是被迫代替她去往敵國和親哄陶。傳聞我的和親對象是個(gè)殘疾皇子帆阳，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 43,499評論 2贊 348