統(tǒng)計(jì)機(jī)器學(xué)習(xí)-線性可分支持向量機(jī)與硬間隔最大化

考慮一個(gè)二分類問(wèn)題湘今。假設(shè)輸入空間與特征空間為兩個(gè)不同的空間已球。輸入空間為歐氏空間或離散集合宽菜，特征空間為歐式空間或希爾伯特空間。線性可分支持向量機(jī)净神、線性支持向量機(jī)假設(shè)這兩個(gè)空間的元素一一對(duì)應(yīng)，并將輸入空間中的輸入映射為特征空間中的特征向量溉委。非線性支持向量機(jī)利用一個(gè)從輸入空間到特征空間的非線性映射將輸入映射為特征向量（核技巧）鹃唯。支持向量機(jī)的學(xué)習(xí)是在特征空間進(jìn)行的。

輸入空間：輸入空間是輸入的所有可能取值的集合瓣喊。

特征空間：特征空間是所有特征向量存在的空間坡慌，特征向量的每一維代表一個(gè)特征，通常與輸入空間一一對(duì)應(yīng)藻三，但也可以通過(guò)映射函數(shù)從輸入空間映射得到特征空間洪橘。

歐氏空間：內(nèi)積空間+完備性+有限維跪者。

希爾伯特空間：內(nèi)積空間+完備性，可以看做歐式空間在無(wú)限維的情形熄求。

線性可分支持向量機(jī)渣玲、線性支持向量機(jī)處理的樣本在輸入空間上就通過(guò)線性劃分，所以輸入空間和特征空間一一對(duì)應(yīng)弟晚。非線性支持向量機(jī)處理的樣本在輸入空間上不可以線性劃分忘衍，所以需要通過(guò)映射函數(shù)從輸入空間映射到特征空間使其在特征空間上可以線性劃分，最終轉(zhuǎn)化成線性可分支持向量機(jī)卿城、線性支持向量機(jī)的形式枚钓。

問(wèn)題

假設(shè)給定一個(gè)特征空間上的訓(xùn)練數(shù)據(jù)集
$T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$
其中， $x_i\in\mathcal X=\textbf R^n$ 瑟押， $y_i\in\mathcal Y=\{+1,-1 \}$ 搀捷， $i=1,2,\cdots,N$ ， $x_i$ 為第 $i$ 個(gè)特征向量多望，也稱為實(shí)例嫩舟， $y_i$ 為 $x_i$ 的類標(biāo)記，當(dāng) $y_i=+1$ 時(shí)便斥，稱 $x_i$ 為正例至壤；當(dāng) $y_i=-1$ 時(shí)，稱 $x_i$ 為負(fù)例枢纠， $(x_i,y_i)$ 稱為樣本點(diǎn)像街。再假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的。

線性可分：用一個(gè)超平面可以將正負(fù)例完全正確的劃分在超平面兩側(cè)晋渺。

學(xué)習(xí)的目的是找到一個(gè)超平面：
$w^*\cdot x+b^*=0$
對(duì)于一個(gè)新的輸入 $x$ 的分類決策函數(shù)為：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
滿足條件的這樣的超平面可能有很多個(gè)镰绎，但是支持向量機(jī)通過(guò)幾何間隔在超平面的選擇上加上了約束，即最大化幾何間隔木西，使最后得到的超平面是唯一的畴栖。

函數(shù)間隔和幾何間隔

函數(shù)間隔

一般來(lái)說(shuō)，一個(gè)樣本點(diǎn)到超平面的距離代表了支持向量機(jī)對(duì)這個(gè)樣本分類的確信程度八千。由于當(dāng)超平面確定吗讶，點(diǎn)到平面的距離公式
$\frac {|w\cdot x+b|}{||w||}$
的分母為一個(gè)常量，所以確信程度的大小由分子 $|w\cdot x+b|$ 決定恋捆。于是定義樣本點(diǎn) $(x_i,y_i)$ 的函數(shù)間隔：
$\hat \gamma_i=y_i(w\cdot x_i+b)\tag1$
對(duì)于 $T$ 中所有樣本的函數(shù)間隔：
$\hat \gamma=\min_{i=1,\cdots N}\hat\gamma_i\tag2$
當(dāng)超平面能夠完全分類正確時(shí) $y_i(w\cdot x_i+b)\geq0$ 照皆，所以函數(shù)間隔代表確信程度最小樣本的確信程度，最大化函數(shù)間隔就等于最大化支持向量機(jī)對(duì)樣本分類的確信程度沸停。在線性可分支持向量機(jī)中膜毁，這也稱為硬間隔最大化。

幾何間隔

由于對(duì)參數(shù) $w$ 和 $b$ 成比例縮放，就可以改變函數(shù)間隔 $\hat\gamma$ 的大小瘟滨，但這仍然表示同一個(gè)超平面候醒。所以提出幾何間隔 $\gamma$ 對(duì) $w$ 規(guī)范化：
$\gamma_i=\frac{\hat \gamma_i}{||w||}\tag3$

$\gamma=\frac{\hat \gamma}{||w||}\tag4$

$||w||$ 代表 $w$ 的 $L2$ 范數(shù)。

重新定義問(wèn)題

學(xué)習(xí)一個(gè)超平面：
$w\cdot x+b=0$
超平面的參數(shù) $w$ 和 $b$ 需要滿足條件
$\max_{w,b}\gamma\tag5$

$\mathrm{s.t.}\ \ y_i(\frac{w}{||w||}\cdot x_i+\frac杂瘸{||w||})\geq\gamma,\ \ i=1,2,\cdots,N\tag6$

根據(jù)公式(4)將(5)-(6)轉(zhuǎn)化為關(guān)于函數(shù)間隔 $\hat\gamma$ 的表述方式：

$\max_{w,b}\frac{\hat\gamma}{||w||}\tag7$

$\mathrm{s.t.}\ \ y_i(w\cdot x_i+b)\geq\hat\gamma,\ \ i=1,2,\cdots,N\tag8$

由于函數(shù)間隔 $\hat\gamma$ 的取值不會(huì)影響最優(yōu)化問(wèn)題的解（參數(shù) $w$ 和 $b$ 成比例縮放）倒淫，所以取 $\hat\gamma=1$ 。而最大化 $\frac{1}{||w||}$ 等價(jià)于最小化 $\frac12||w||^2$ 胧沫，所以支持向量機(jī)最終可以表示成最優(yōu)化問(wèn)題：
$\min_{w,b}\ \ \frac12||w||^2\tag9$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N\tag{10}$

這是一個(gè)凸二次規(guī)劃問(wèn)題昌简，即目標(biāo)函數(shù) $f(w)=\frac12||w||^2$ 是二次函數(shù)，且約束函數(shù) $g_i(w)=1-y_i(w\cdot x_i+b)$ 是仿射函數(shù)绒怨。

線性可分支持向量機(jī)學(xué)習(xí)算法--最大間隔法

輸入：線性可分訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$ 纯赎，其中 $x_i\in\mathcal X=\textbf R^n$ ， $y_i\in\mathcal Y=\{+1,-1 \}$ 南蹂， $i=1,2,\cdots,N$ 犬金；

輸出：最大間隔分離超平面和分類決策函數(shù)。

（1）構(gòu)造并求解約束最優(yōu)化問(wèn)題：
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

求得最優(yōu)解 $w^*$ 六剥， $b^*$ 晚顷。

（2）由此得到分離超平面：
$w^*\cdot x+b^*=0$
分類決策函數(shù)：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$
這樣的超平面存在且唯一，證明略疗疟。

支持向量和間隔邊界

支持向量是使約束條件公式(10)等號(hào)成立的點(diǎn)该默，即
$w\cdot x_i+b=y_i$
對(duì)于正例 $y_i=+1$ ，支持向量在超平面
$H_1:w\cdot x+b=1$
對(duì)于負(fù)例 $y_i=-1$ 策彤，支持向量在超平面
$H_2:w\cdot x+b=-1$
如圖所示

間隔邊界

落在 $H_1$ 和 $H_2$ 上的實(shí)例點(diǎn)稱為支持向量栓袖， $H_1$ 和 $H_2$ 之間的距離稱為間隔， $H_1$ 和 $H_2$ 稱為間隔邊界店诗。在決定超平面時(shí)裹刮，只有支持向量起作用，所以這種模型叫做支持向量機(jī)庞瘸。

學(xué)習(xí)的對(duì)偶算法

對(duì)于最優(yōu)化問(wèn)題(9)-(10)：
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

首先構(gòu)建拉格朗日函數(shù)：
$L(w,b,a)=\frac12||w||^2-\sum_{i=1}^N\alpha_iy_i(w\cdot x_i+b)+\sum_{i=1}^N\alpha_i\tag{11}$
其中 $\alpha_i\geq0$ 捧弃，則原始問(wèn)題為極小極大問(wèn)題：
$\min_{w,b}\max_\alpha L(w,b,a)$
由拉格朗日對(duì)偶性改為求解原始問(wèn)題的對(duì)偶問(wèn)題：
$\max_\alpha\min_{w,b}L(w,b,a)$
首先求解對(duì)偶問(wèn)題的內(nèi)部極小問(wèn)題：
$\min_{w,b}L(w,b,a)$
將拉格朗日函數(shù)分別對(duì) $w$ ， $b$ 求偏導(dǎo)并令其等于0：
$\nabla_wL(w,b,\alpha)=w-\sum_{i=1}^N\alpha_iy_ix_i=0$

$\sum_{i=1}^N\alpha_iy_i=0$

得到：
$w=\sum_{i=1}^N\alpha_iy_ix_i\tag{12}$

$\sum_{i=1}^N\alpha_iy_i=0\tag{13}$

將其代入(11)得到：
$\begin{align} L(w,b,\alpha)&=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_iy_i\Bigg(\bigg(\sum_{j=1}^N\alpha_jy_jx_j\bigg)\cdot x_i+b\Bigg)+\sum_{i=1}^N\alpha_i\\ &=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-b\sum_{i=1}^N\alpha_iy_i+\sum_{i=1}^N\alpha_i\\ &=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i \end{align}$
于是對(duì)偶問(wèn)題為：
$\max_\alpha-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\tag{14}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

對(duì)(14)的目標(biāo)函數(shù)取相反數(shù)轉(zhuǎn)化為極小問(wèn)題：
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\tag{15}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

定理

設(shè) $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 是對(duì)偶問(wèn)題最優(yōu)化問(wèn)題
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

的解擦囊，則存在下標(biāo) $j$ 违霞，使得 $\alpha_j^*\gt0$ ，并按下式求得原始最優(yōu)化問(wèn)題
$\min_{w,b}\ \ \frac12||w||^2$

$\mathrm{s.t.}\ \ 1-y_i(w\cdot x_i+b)\leq0,\ \ i=1,2,\cdots,N$

的解 $w^*$ 瞬场， $b^*$
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i\tag{16}$

$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)\tag{17}$

證明

由于目標(biāo)函數(shù) $f(w)=\frac12||w||^2$ 和約束函數(shù) $g_i(w)=1-y_i(w\cdot x_i+b)$ 是凸函數(shù)葛家，且假設(shè)不等式約束 $g_i(w)$ 是嚴(yán)格可行的，則 $w^*$ 泌类， $b^*$ ， $\alpha^*$ 分別原始問(wèn)題和對(duì)偶問(wèn)題的解的充分必要條件是 $w^*$ ， $b^*$ 刃榨， $\alpha^*$ 滿足 $KKT$ 條件：
$\nabla_wL(w^*,b^*,\alpha^*)=w^*-\sum_{i=1}^N\alpha_i^*y_ix_i=0\tag{18}$

$\nabla_bL(w^*,b^*,\alpha^*)=-\sum_{i=1}^N\alpha_i^*y_i=0\tag{19}$

$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0\tag{20}$

$g_i(w^*)=1-y_i(w^*\cdot x_i+b^*)\leq0\tag{21}$

$\alpha_i^*\geq0,\ \ i=1,2,\cdots,N\tag{22}$

由(18)得
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
由反證法弹砚，假設(shè)不存在下標(biāo) $j$ ，使得 $\alpha_j^*\gt0$ 枢希，根據(jù)(22)桌吃，則 $\alpha^*=0$ ，代入(18)得到 $w^*=0$ 苞轿，超平面不存在茅诱，假設(shè)不成立。于是存在下標(biāo) $j$ 搬卒，使得 $\alpha_j^*\gt0$ 瑟俭，根據(jù)(20)得到
$1-y_j(w^*\cdot x_j+b^*)=0$
根據(jù) $y_j^2=1$ 得
$y_j(w^*\cdot x_j+b^*)=y_j^2$
解得
$b^*=y_j-w^*\cdot x_j$
將
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
代入得到
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$
證明完成。

線性可分支持向量機(jī)的對(duì)偶學(xué)習(xí)算法

輸入：線性可分訓(xùn)練數(shù)據(jù)集 $T= \{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N) \}$ 其中 $x_i\in\mathcal X=\textbf R^n$ 契邀， $y_i\in\mathcal Y=\{+1,-1 \}$ 摆寄， $i=1,2,\cdots,N$ ；

輸出：最大間隔分離超平面和分類決策函數(shù)坯门。

（1）構(gòu)造并求解約束最優(yōu)化問(wèn)題
$\min_\alpha\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\tag{15}$

$\mathrm{s.t.}\ \ \sum_{i=1}^N\alpha_iy_i=0$

$\alpha_i\geq0,\ \ i=1,2,\cdots,N$

求得最優(yōu)解 $\alpha^*=(\alpha_1^*,\alpha_2^*,\cdots,\alpha_N^*)$ 微饥。

（2）計(jì)算
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
并選擇 $\alpha^*$ 的一個(gè)正分量 $\alpha_j^*\gt0$ ，計(jì)算
$b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j)$
（3）求得分離超平面
$w^*\cdot x+b^*=0$
分類決策函數(shù)：
$f(x)=\mathrm{sign}(w^*\cdot x+b^*)$

支持向量

根據(jù)公式
$w^*=\sum_{i=1}^N\alpha_i^*y_ix_i$
可以知道對(duì) $w^*$ 的結(jié)果有影響的樣本點(diǎn) $(x_i,y_i)$ 古戴，其 $\alpha_i^*\neq0$ 欠橘，又因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Calpha_i%5E*%5Cgeq0" alt="\alpha_i^*\geq0" mathimg="1">，所以 $\alpha_i^*\gt0$ 现恼，根據(jù) $KKT$ 條件：
$\alpha_i^*g_i(w^*)=\alpha_i^*(1-y_i(w^*\cdot x_i+b^*))=0$
所以
$1-y_i(w^*\cdot x_i+b^*)=0$
這樣的樣本點(diǎn)落在間隔邊界上
$w^*\cdot x_i+b^*=\pm1$
與前面的描述相同肃续。

最后編輯于：2020.07.02 22:39:40

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

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市述暂，隨后出現(xiàn)的幾起案子痹升，更是在濱河造成了極大的恐慌，老刑警劉巖畦韭，帶你破解...
沈念sama閱讀 218,386評(píng)論 6贊 506
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件疼蛾，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡艺配，警方通過(guò)查閱死者的電腦和手機(jī)察郁，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,142評(píng)論 3贊 394
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)转唉，“玉大人皮钠，你說(shuō)我怎么就攤上這事≡ǎ” “怎么了麦轰？”我有些...
開封第一講書人閱讀 164,704評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)。經(jīng)常有香客問(wèn)我款侵，道長(zhǎng)末荐，這世上最難降的妖魔是什么？我笑而不...
開封第一講書人閱讀 58,702評(píng)論 1贊 294
?港島之戀（遺憾婚禮）
正文為了忘掉前任新锈，我火速辦了婚禮甲脏，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘妹笆。我一直安慰自己块请，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,716評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布拳缠。她就那樣靜靜地躺著墩新，像睡著了一般。火紅的嫁衣襯著肌膚如雪脊凰。梳的紋絲不亂的頭發(fā)上抖棘，一...
開封第一講書人閱讀 51,573評(píng)論 1贊 305
城市分裂傳說(shuō)
那天，我揣著相機(jī)與錄音狸涌，去河邊找鬼切省。笑死，一個(gè)胖子當(dāng)著我的面吹牛帕胆，可吹牛的內(nèi)容都是我干的朝捆。我是一名探鬼主播，決...
沈念sama閱讀 40,314評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼懒豹，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼芙盘！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起脸秽，我...
開封第一講書人閱讀 39,230評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤儒老，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后记餐，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體驮樊，經(jīng)...
沈念sama閱讀 45,680評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡厂抽，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,873評(píng)論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年疑务，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片匙赞。...
茶點(diǎn)故事閱讀 39,991評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡雕沿，死狀恐怖练湿，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情审轮，我是刑警寧澤肥哎，帶...
沈念sama閱讀 35,706評(píng)論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布辽俗，位于F島的核電站，受9級(jí)特大地震影響贤姆，放射性物質(zhì)發(fā)生泄漏榆苞。R本人自食惡果不足惜，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,329評(píng)論 3贊 330
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一霞捡、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧薄疚，春花似錦碧信、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,910評(píng)論 0贊 22
一樁弒父案砰碴，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至板丽，卻和暖如春呈枉，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背埃碱。一陣腳步聲響...
開封第一講書人閱讀 33,038評(píng)論 1贊 270
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工猖辫，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人砚殿。一個(gè)月前我還...
沈念sama閱讀 48,158評(píng)論 3贊 370
代替公主和親
正文我出身青樓啃憎，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親似炎。傳聞我的和親對(duì)象是個(gè)殘疾皇子辛萍，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,941評(píng)論 2贊 355