16.gitchat訓練營-SVR——一種“寬容”的回歸模型

1.寬容的支持向量回歸（SVR）

一種“寬容的”回歸模型：支持向量回歸（Support Vector Regression，SVR）。

支持向量回歸模型的模型函數(shù)也是一個線性函數(shù)： $y=wx+b$ 针余≌埽看起來和線性回歸的模型函數(shù)一樣分苇！但 SVR 和線性回歸彤蔽，卻是兩個不同的回歸模型让禀。

這兩個模型不同點學習過程挑社，就是：計算損失的原則不同，目標函數(shù)和最優(yōu)化算法也不同巡揍。

1.1.原理

SVR 在線性函數(shù)兩側(cè)制造了一個“間隔帶”痛阻，對于所有落入到間隔帶內(nèi)的樣本，都不計算損失腮敌；只有間隔帶之外的录平，才計入損失函數(shù)麻车。之后再通過最小化間隔帶的寬度與總損失來最優(yōu)化模型。如下圖這樣斗这，只有那些圈了紅圈的樣本（或在隔離帶邊緣之外动猬，或落在隔離帶邊緣上），才被計入最后的損失：

image

1.2.SVR 的兩個松弛變量

這樣看起來表箭，是不是 SVR 很像 SVM赁咙？不過請注意，有一點 SVR 和 SVM 正相反免钻，那就是：SVR 巴不得所有的樣本點都落在“隔離帶”里面彼水，而 SVM 則恰恰希望所有的樣本點都在“隔離帶”之外！正是這一點區(qū)別极舔，導致 SVR 要同時引入兩個而不是一個松弛變量凤覆。

SVR 引入兩個松弛變量： $\xi$ 和 $\xi^*$

SVR的基本情況

$f(x) = wx +b$ 是我們最終要求得的模型函數(shù)； $wx + b + \epsilon$ 和 $wx +b – \epsilon$ （也就是 $f(x) + \epsilon$ 和 $f(x) - \epsilon$ ）是隔離帶的上下邊緣拆魏； $\xi$ 是隔離帶上邊緣之上樣本點的 $y$ 值盯桦，與對應 $x$ 坐標在“上邊緣超平面”上投影的差；而 $\xi^*$ 則是隔離帶下邊緣之下樣本點渤刃，到隔離帶下邊緣上的投影拥峦，與該樣本點 $y$ 值的差。用公式來反應：

image

對于任意樣本 $x_i$ 卖子，如果它在隔離帶里面或者隔離帶邊緣上略号，則 $\xi$ 和 $\xi^*$ 都為 $0$ ；如果它在隔離帶上邊緣上方洋闽，則 $\xi_i > 0玄柠，\xi_i^*=0$ ；如果它在下邊緣下方诫舅，則 $\xi_i = 0随闪，\xi_i^* > 0$ 。

2.SVR 的主問題和對偶問題

2.1.SVR 的主問題

SVR 主問題的數(shù)學描述如下：
$min_{w,b,\xi,\xi^*}\frac{1}{2}||w||^2 + C\sum_{i=1}^{m}(\xi_i +\xi_i^*)$
$s.t. \,\, f(x_i) - y_i \leqslant \epsilon + \xi_i;\;\; y_i - f(x_i) \leqslant \epsilon + \xi_i^* ;\;\; \xi_i \geqslant 0; \;\; \xi_i^* \geqslant 0,\;\; i = 1,2, ..., m.$

2.2.SVR 的拉格朗日函數(shù)和對偶問題

我們引入拉格朗日乘子 $\mu_i \geqslant 0骚勘，\mu_i^* \geqslant 0铐伴， \alpha_i \geqslant 0$ 和 $\alpha_i^* \geqslant 0$ ，來針對上述主問題構(gòu)建拉格朗日函數(shù)俏讹，得到拉格朗日函數(shù)如下：
$L(w,b,\xi,\xi^*, \alpha,\alpha^*, \mu,\mu^*) = \frac{1}{2}||w||^2 + C\sum_{i=1}^{m}(\xi_i +\xi_i^*) + \sum_{i=1}^{m}\alpha_i(f(x_i) - y_i -\epsilon - \xi_i) +$
$\sum_{i=1}^{m}\alpha_i^*(y_i - f(x_i) -\epsilon - \xi_i^*) + \sum_{i=1}^{m}\mu_i(0 - \xi_i) + \sum_{i=1}^{m}\mu_i^*(0 - \xi_i^*)$

它對應的對偶問題是：
$max_{\alpha, \alpha^*, \mu, \mu^*}min_{w,b,\xi,\xi^*}L(w,b,\xi,\xi^*, \alpha,\alpha^*, \mu,\mu^*)$

2.3.求解 SVR 對偶問題

首先要求最小化部分：
$min_{w,b,\xi,\xi^*}L(w,b,\xi,\xi^*, \alpha,\alpha^*, \mu,\mu^*)$
分別對 $w$ 当宴， $b$ ， $\xi$ 和 $\xi^*$ 求偏導泽疆，并令偏導為 $0$ 户矢，可得：
$w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i,$
$0 = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i),$
$C = \alpha_i + \mu_i ,$
$C = \alpha_i^* + \mu_i .$
將上述4個等式帶回到對偶問題中，在通過求負將極大化問題轉(zhuǎn)化為極小化問題殉疼，得到如下結(jié)果：
$\\ min_{\alpha,\alpha^*}[\sum_{i=1}^{m}y_i(\alpha_i - \alpha_i^*) + \epsilon\sum_{i=1}^{m}(\alpha_i + \alpha_i^*) + \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\alpha_i -\alpha_i^*)(\alpha_j -\alpha_j^*)x_i^Tx_j ]$
$\\ s.t. \sum_{i=1}^{m}(\alpha_i^* - \alpha_i) = 0; \;\; 0 \leqslant \alpha_i, \alpha_i^* \leqslant C.$

2.4.用 SMO 算法求解 SVR

SMO 算法針對的是任意樣本 $x_i$ 只對應一個參數(shù) $\alpha_i$ 的情況梯浪，而此處捌年，這個樣本卻對應兩個參數(shù) $\alpha_i$ 和 $\alpha_i^*$ 。有沒有辦法把 $\alpha_i$ 和 $\alpha_i^*$ 轉(zhuǎn)化為一個參數(shù)呢挂洛？辦法還是有的！

我們整個求解過程采用的是拉格朗日對偶法托酸，對偶問題有解的充要條件是滿足** KKT 條件**。那么對于 SVR 的對偶問題，它的 KKT 條件是什么呢？它的 KKT 條件如下：
$\alpha_i(f(x_i) - y_i - \epsilon - \xi_i) = 0,$
$\alpha_i^*(y_i - f(x_i) - \epsilon - \xi_i^* ) = 0,$
$\alpha_i\alpha_i^*=0,$
$\xi_i\xi_i^* = 0,$
$(C - \alpha_i)\xi_i = 0,$
$(C - \alpha_i^*)\xi_i^* = 0.$

由 KKT 條件可見贱案，當且僅當 $f(x_i) - y_i - \epsilon - \xi_i = 0$ 時， $\alpha_i$ 才可以取非 $0$ 值；當且僅當 $y_i - f(x_i) - \epsilon - \xi_i^* = 0$ 時， $\alpha_i^*$ 才可以取非 $0$ 值百新。

$f(x_i) - y_i - \epsilon - \xi_i = 0 => y_i = f(x_i) - \epsilon - \xi_i$ 對應的是在隔離帶下邊緣以下的樣本形庭。而 $y_i - f(x_i) - \epsilon - \xi_i^* = 0 => y_i = f(x_i) + \epsilon + \xi_i^*$ 對應的是在隔離帶上邊緣之上的樣本桩卵。一個樣本不可能同時既在上邊緣之上，又在上邊緣之下辞州，所以這兩個等式最多只有一個成立，相應的 $\alpha_i$ 和 $\alpha_i^*$ 中至少有一個為 $0$ 。

我們設(shè)： $\lambda_i = \alpha_i – \alpha_i^*$ 。既然 $\alpha_i$ 和 $\alpha_i^*$ 中至少有一個為 $0$ ，且 $0 \leqslant \alpha_i，\alpha_i^*，\leqslant C$ 霹期，于是有 : $|\lambda_i| = \alpha_i + \alpha_i^*$ 帕膜。

將 $\lambda_i$ 和 $|\lambda_i|$ 帶入對偶問題荒典，則有：
$\\ min_{\lambda}[\sum_{i=1}^{m}y_i(\lambda_i) + \epsilon( |\lambda_i|) + \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\lambda_i \lambda_j x_i^Tx_j ]$
$\\ s.t. \sum_{i=1}^{m}(\lambda_i) = 0; \;\;-C \leqslant \lambda_i \leqslant C.$
如此一來，不就可以應用 SMO 求解了嘛寺董！當然覆糟，這樣一個推導過程僅僅用于說明 SMO 也可以應用于 SVR，具體的求解過程和 SVM 的 SMO 算法還是有所差異的遮咖。

3.支持向量與求解線性模型參數(shù)

因為 $f(x) = wx + b$ 滩字，又因為前面已經(jīng)求出 $w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i$ ，因此：
$f(x) = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i^Tx + b$
由此可見御吞，只有滿足 $\alpha_i^* - \alpha_i \ne 0$ 的樣本才對 $w$ 取值有意義麦箍，才是 SVR 的支持向量。也就是說陶珠，只有當樣本滿足下列兩個條件之一時挟裂，它才是支持向量：
$f(x_i) - y_i - \epsilon - \xi_i = 0$
或
$y_i - f(x_i) - \epsilon - \xi_i^* = 0$

換言之，這個樣本要么在隔離帶上邊緣以上揍诽，要么在隔離帶下邊緣以下（含兩個邊緣本身）诀蓉。也就是說，落在 $\epsilon$ 隔離帶之外的樣本寝姿，才是 SVR 的支持向量交排！可見划滋，無論是 SVM 還是 SVR饵筑，它們的解都僅限于支持向量，即只是全部訓練樣本的一部分处坪。因此 SVM 和 SVR 的解都具有稀疏性根资。

通過最優(yōu)化方法求解出了 $w$ 之后，我們還需要求 $b$ 同窘。
$f(x_i) = wx_i + b => b = f(x_i) – wx_i$
而且玄帕，對于那些落在隔離帶上邊緣上的支持向量，有 $f(x_i)= y_i+\epsilon$ 想邦，落在隔離帶下邊緣上的支持變量有 $f(x_i) = y_i -\epsilon$ 裤纹。

因此， $b = \frac{1}{|S_u| + |S_d|}[\sum_{s\in S_u}(y_s + \epsilon - w x_s) + \sum_{s\in S_d}(y_s - \epsilon - w x_s)]$ 其中 $S_u$ 是位于隔離帶上邊緣的支持向量集合，而 $S_d$ 則是位于隔離帶下邊緣的支持向量集合鹰椒。

4.SVR 的核技巧

SVR 核技巧的實施辦法和 SVM 一樣锡移，也是將輸入空間的 $x$ 通過映射函數(shù) $\phi(x)$ 映射到更高維度的特征空間。然后再在特征空間內(nèi)做本文前面所述的一系列操作漆际。因此淆珊，在特征空間中的線性模型為：
$f(x) = w\phi(x) + b$
其中：
$w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)\phi(x_i)$

對照 SVM 核函數(shù)的做法，我們也令：
$k(x_i,x_j) = \phi(x_i)^T \phi(x_j)$
則：
$f(x) = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)k(x,x_i) + b$
具體核技巧的實施過程奸汇，也對照 SVM 即可施符。

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市擂找，隨后出現(xiàn)的幾起案子戳吝，更是在濱河造成了極大的恐慌，老刑警劉巖贯涎，帶你破解...
沈念sama閱讀 206,214評論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件骨坑，死亡現(xiàn)場離奇詭異，居然都是意外死亡柬采，警方通過查閱死者的電腦和手機欢唾，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,307評論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來粉捻，“玉大人礁遣，你說我怎么就攤上這事〖缛校” “怎么了祟霍？”我有些...
開封第一講書人閱讀 152,543評論 0贊 341
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長盈包。經(jīng)常有香客問我沸呐，道長，這世上最難降的妖魔是什么呢燥？我笑而不...
開封第一講書人閱讀 55,221評論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任崭添，我火速辦了婚禮，結(jié)果婚禮上叛氨，老公的妹妹穿的比我還像新娘呼渣。我一直安慰自己，他們只是感情好寞埠，可當我...
茶點故事閱讀 64,224評論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布屁置。她就那樣靜靜地躺著，像睡著了一般仁连。火紅的嫁衣襯著肌膚如雪蓝角。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 49,007評論 1贊 284
城市分裂傳說
那天，我揣著相機與錄音使鹅，去河邊找鬼颇象。笑死，一個胖子當著我的面吹牛并徘，可吹牛的內(nèi)容都是我干的遣钳。我是一名探鬼主播，決...
沈念sama閱讀 38,313評論 3贊 399
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼麦乞，長吁一口氣：“原來是場噩夢啊……” “哼蕴茴！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起姐直，我...
開封第一講書人閱讀 36,956評論 0贊 259
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤倦淀，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后声畏，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體撞叽，經(jīng)...
沈念sama閱讀 43,441評論 1贊 300
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 35,925評論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年插龄，在試婚紗的時候發(fā)現(xiàn)自己被綠了愿棋。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 38,018評論 1贊 333
活死人
序言：一個原本活蹦亂跳的男人離奇死亡均牢，死狀恐怖糠雨，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情徘跪，我是刑警寧澤甘邀，帶...
沈念sama閱讀 33,685評論 4贊 322
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站垮庐，受9級特大地震影響松邪，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜哨查，卻給世界環(huán)境...
茶點故事閱讀 39,234評論 3贊 307
男人毒藥：我在死后第九天來索命
文/蒙蒙一逗抑、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧解恰，春花似錦锋八、人聲如沸浙于。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,240評論 0贊 19
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽羞酗。三九已至腐宋，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背胸竞。一陣腳步聲響...
開封第一講書人閱讀 31,464評論 1贊 261
情欲美人皮
我被黑心中介騙來泰國打工欺嗤，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人卫枝。一個月前我還...
沈念sama閱讀 45,467評論 2贊 352
代替公主和親
正文我出身青樓煎饼，卻偏偏與公主長得像，于是被迫代替她去往敵國和親校赤。傳聞我的和親對象是個殘疾皇子吆玖，可洞房花燭夜當晚...
茶點故事閱讀 42,762評論 2贊 345