第六章支持向量機

間隔與支持向量

給定訓練樣本集，分類學習最基本的想法就是基于訓練集在樣本空間中找到一個劃分超平面守呜，將不同類別的樣本分開型酥。

但是能將不同類別樣本分開的劃分超平面可能有很多，直觀上查乒，我們應該去找“正中間”的劃分超平面弥喉，也就是對訓練樣本局部擾動容忍性最好的超平面蒋譬。

在樣本空間中捂蕴，劃分超平面的方程為 $w^Tx+b=0$ 负敏，其中 $w$ 是法向量饺律，決定了超平面的方向鸵膏； $b$ 是位移伶丐，決定了超平面與原點之間的距離木柬。

樣本空間中任意點 $x$ 到超平面的距離可寫為：
$r=\frac{|w^Tx + b|}{||w||}$
假設超平面能將訓練樣本正確分類间学，即對于樣本 $(x_i, y_i)\in D$ 拒担，有：
$w^Tx_i + b \geq +1, y_i=+1$
$w^Tx_i + b \leq -1, y_i=-1$
使得不等式等號成立的幾個訓練樣本點被稱為支持向量嘹屯，兩個異類支持向量到超平面的距離之和為：
$\gamma = \frac{|+1|}{||w||} + \frac{|-1|}{||w||} = \frac{2}{||w||}$
也被稱為間隔(margin)。

支持向量機的目的就是找到具有最大間隔的劃分超平面从撼，即公式(1)：
$\max_{w,b} \frac{2}{||w||} \iff \min_{w,b} \frac{1}{2}||w||^2$
$s.t. \ y_i(w^Tx_i + b) \geq 1, i=1,2,...,m$
轉化為凸二次規(guī)劃問題州弟。

進而得到對應的分類模型 $f(x) = w^Tx + b$

支持向量機的重要性質：訓練完成后钧栖，大部分訓練樣本都不需要保留，最終模型只與支持向量有關婆翔。

對偶問題

對公式(1)運用拉格朗日乘子法可得到其對偶問題:
$\max_{\alpha} \sum_{i=1}^m \alpha_i - \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m\alpha_i \alpha_j y_i y_j x_i^T x_j$
$s.t. \sum_{i=1}^m\alpha_i y_i = 0,$
$\quad \quad \alpha_i\geq 0, i=1,2,...,m$
其中 $\alpha_i$ 為拉格朗日乘子拯杠，解出 $\alpha$ 后，求出 $w$ 與 $b$ 即可得到模型：
$f(x) = w^T x + b = \sum_{i=1}^m \alpha_i y_i x_i^T x + b$
注意上述過程需要滿足KKT條件啃奴。

核函數(shù)

前面假設訓練樣本是線性可分的潭陪，即存在一個劃分超平面能將訓練樣本正確分類。然而現(xiàn)實任務中最蕾，原始樣本空間也許不存在一個能正確分類兩類樣本的超平面依溯，比如異或問題。

因此瘟则，我們考慮將樣本從原始空間映射到一個更高維的特征空間黎炉，使得樣本在這個特征空間內線性可分。
令 $\phi(x)$ 表示將 $x$ 映射后的特征向量醋拧，于是慷嗜，在特征空間中對應的模型表示為：
$f(x) = w^T \phi(x) + b$
其中 $w$ 和 $b$ 是模型參數(shù)。
則其對偶問題中需要計算 $\phi(x_i)^T \phi(x_j)$ 趁仙，為樣本 $x_i$ 和 $x_j$ 映射到特征空間中的內積洪添，由于特征空間維數(shù)可能很高，甚至為無窮維雀费，因此直接計算該內積通常很困難。為了避開這個障礙痊焊，考慮如下函數(shù)：
$\kappa(x_i, x_j) = \phi(x_i)^T \phi(x_j)$
即 $x_i$ 與 $x_j$ 在特征空間中內積等于它們在原始空間中函數(shù) $\kappa(.,.)$ 的計算結果盏袄。

最終可得模型為：
$f(x) = w^T\phi(x) + b = \sum_{i=1}^m\alpha_i y_i \kappa(x, x_i) + b$
這里的函數(shù) $\kappa(.,.)$ 就是核函數(shù)(kernel function)。

定理(核函數(shù)): 令 $X$ 為輸入空間薄啥， $\kappa(.,.)$ 是定義在 $X\times X$ 上的對稱函數(shù)，則 $\kappa$ 是核函數(shù)當且僅當對于任意數(shù)據(jù) $D=\left\{ x_1, x_2, ..., x_m \right\}$ 垄惧，核矩陣(kernel matrix)K總是半正定的刁愿。

核函數(shù)選擇成為支持向量機的最大變數(shù)，若核函數(shù)選擇不合適到逊，則意味著將樣本映射到了一個不合適的特征空間铣口，很可能導致性能不佳。
常用的核函數(shù)有線性核觉壶、多項式核脑题、高斯核、拉普拉斯核等铜靶。

軟間隔與正則化

前面我們一直假定訓練樣本在原始空間或特征空間是線性可分的叔遂，然而，現(xiàn)實任務中往往很難確定合適的核函數(shù)使得訓練樣本在特征空間線性可分；此外已艰，就算恰好找到了某個核函數(shù)使得訓練集在特征空間中線性可分痊末，也很難斷定這個結果不是由于過擬合造成的。

緩解這個問題的一個辦法就是允許支持向量機在一些樣本上出錯哩掺。
硬間隔要求所有樣本都必須劃分正確凿叠，而軟間隔則允許某些樣本不滿足約束：
$y_i(w^Tx_i + b)\geq 1$
此時要求在最大化間隔的同時，不滿足約束的樣本應盡可能少疮丛。

優(yōu)化目標改寫為：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m l_{0/1}(y_i(w^Tx_i + b) - 1)$
其中 $C>0$ 是一個常數(shù)幔嫂， $l_{0/1}$ 是0/1損失函數(shù)：
$l_{0/1}(z)=1 \ \text{if} \ z<0 \ \text{else} \ 0$
但是0/1損失函數(shù)非凸，非連續(xù)誊薄，數(shù)學性質不太好履恩，使得優(yōu)化目標不易直接求解。人們通常使用其他一些函數(shù)來代替呢蔫，比如hinge損失：
$l_{hinge}(z) = \max(0, 1-z)$

則優(yōu)化目標變?yōu)椋?br> $\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m \max(0, 1-y_i(w^Tx_i + b))$
可看成是正則化的合頁(hinge)損失最小化問題切心。

引入松弛變量 $\xi_i\geq 0$ ，優(yōu)化目標可進一步重寫為：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m \xi_i$
這就是軟間隔支持向量機片吊。每個樣本都有一個對應的松弛變量绽昏，表示該樣本不滿足約束的程度。與原始目標函數(shù)相似俏脊，這仍是一個二次規(guī)劃問題全谤，可通過拉格朗日乘子法求解。

$L_p$ 范數(shù)是常用的正則化項爷贫，其中 $L_2$ 范數(shù) $||w||_2$ 傾向于 $w$ 的分量取值盡量均衡认然，即非零分量個數(shù)盡量稠密，而 $L_0$ 范數(shù)和 $L_1$ 范數(shù)則傾向于 $w$ 的分量盡量稀疏漫萄，即非零分量個數(shù)盡量少卷员。

支持向量機是針對二分類任務設計的，對多分類任務要進行專門的推廣[Hsu and Lin, 2002]

支持向量回歸

考慮回歸問題腾务，即給定訓練集 $D=\left \{ (x_1, y_1), (x_2, y_2), ..., (x_m, y_m)) \right \}, y_i\in R$ 毕骡，希望學得模型 $f(x)=w^T x + b$ ，使得 $f(x)$ 與 $y$ 盡可能接近岩瘦。

傳統(tǒng)回歸模型當且僅當 $f(x)$ 與 $y$ 完全相同時未巫，損失才為0。而支持向量回歸(Support Vector Regression, SVR)假設我們能容忍 $\epsilon$ 的偏差担钮，即僅當 $f(x)$ 與 $y$ 之間的差別絕對值大于 $\epsilon$ 時才計算損失橱赠。
這相當于以 $f(x)$ 為中心，構建了一個寬度為 $2\epsilon$ 的間隔帶箫津，若訓練樣本落入該間隔帶狭姨，則被認為是預測正確的宰啦。

所以，SVR問題可形式化為：
$\min_{w,b}\frac{1}{2}||w||^2 + C\sum_{i=1}^m l_{\epsilon}(f(x_i) - y_i)$
其中 $C$ 為正則化常數(shù)饼拍， $l_{\epsilon}$ 是 $\epsilon$ -不敏感損失函數(shù)：
$l_{\epsilon}(z) = 0 \ \text{if}\ ||z||\leq \epsilon \ \text{else}\ |z|-\epsilon$

Hsu, C.-W. and C.-J. Lin. (2002). "A comparison of methods for multi-class support vector machines."
《西瓜書》
《南瓜書》

最后編輯于：2022.01.27 21:19:51

?著作權歸作者所有,轉載或內容合作請聯(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
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長朵锣。經常有香客問我，道長甸私，這世上最難降的妖魔是什么诚些？我笑而不...
開封第一講書人閱讀 56,432評論 1贊 283
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮皇型，結果婚禮上诬烹，老公的妹妹穿的比我還像新娘。我一直安慰自己弃鸦，他們只是感情好绞吁，可當我...
茶點故事閱讀 65,519評論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布。她就那樣靜靜地躺著唬格，像睡著了一般家破。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上门粪，一...
開封第一講書人閱讀 49,792評論 1贊 290
城市分裂傳說
那天髓梅，我揣著相機與錄音酝锅，去河邊找鬼。笑死阁谆，一個胖子當著我的面吹牛，可吹牛的內容都是我干的。我是一名探鬼主播熬拒，決...
沈念sama閱讀 38,933評論 3贊 406
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼欢瞪，長吁一口氣：“原來是場噩夢啊……” “哼啸盏！你這毒婦竟也來了回懦？” 一聲冷哼從身側響起健民，我...
開封第一講書人閱讀 37,701評論 0贊 266
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎崇堵，沒想到半個月后鸳劳，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經...
沈念sama閱讀 44,143評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 36,488評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了患雇。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片苛吱。...
茶點故事閱讀 38,626評論 1贊 340
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖，靈堂內的尸體忽然破棺而出衰齐，到底是詐尸還是另有隱情废酷，我是刑警寧澤澈蟆，帶...
沈念sama閱讀 34,292評論 4贊 329
?日本核電站爆炸內幕
正文年R本政府宣布奏赘，位于F島的核電站疲憋，受9級特大地震影響缚柳，放射性物質發(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

第六章 支持向量機