支持向量機(jī)

“SVM有三寶，間隔對(duì)偶核技巧”

首先，支持向量機(jī)是一個(gè)二分類的模型。

他與感知機(jī)算法有很多相似的地方，都是使用超平面分割空間，但是與感知不同的是：

支持向量機(jī)并不是感知機(jī)的錯(cuò)誤驅(qū)動(dòng)，而是對(duì)于幾何間隔的最大化。
支持向量機(jī)可以解決的問題很多樣，線性可分，近似線性，非線性可分。

線性可分問題：

對(duì)于線性可分的問題：

支持向量機(jī)采用硬間隔最大的方法訓(xùn)練模型。

首先，我們先解釋一下，什么是間隔？

間隔，就如我們所想的就是距離，而這里我們要提及的有兩種間隔：

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

幾何間隔

幾何間隔，對(duì)于兩個(gè)點(diǎn)來說，就是兩個(gè)點(diǎn)之間的距離，至于怎么算，我想也不用說了。

但是，在分類訓(xùn)練問題中，往往不是兩個(gè)點(diǎn)，而是兩堆點(diǎn)，那么對(duì)于兩堆點(diǎn)，什么是幾何間隔呢？

就是兩堆中離得最近的點(diǎn)到超平面的距離，而在SVM中，我們知道：

我們是通過超平面分割來實(shí)現(xiàn)分類的，所以這個(gè)幾何距離在實(shí)際中表示的就是：

將所有點(diǎn)分開的確信度大小

公式就是：
$gap = \frac{y_i(\omega x_i+b)}{||\omega||}$

函數(shù)間隔

可能學(xué)習(xí)過感知機(jī)的同學(xué)，知道函數(shù)間隔，當(dāng)時(shí)統(tǒng)計(jì)學(xué)習(xí)方法中李杭老師對(duì)函數(shù)間隔一筆帶過，留到SVM這里。這里，我們就對(duì)當(dāng)時(shí)的一些問題一目了然了。
$Gap = y_i(\omega x_i+b)$
在感知機(jī)中，與其說這是函數(shù)間隔，我更愿意將他理解為分類錯(cuò)誤的判別函數(shù)，其實(shí)感知機(jī)中并沒有涉及到距離，所以這也就是，支持向量機(jī)與他不同的地方。

為什么支持向量機(jī)不采用函數(shù)間隔呢？

如果我們相同比例的擴(kuò)大 $\omega$ 和 $b$ ，超平面并沒有變，但是函數(shù)間隔卻變成了原來的n倍。所以，對(duì)于支持向量機(jī)不能使用函數(shù)間隔。

硬間隔最大化

什么是硬間隔呢？

要理解硬間隔，你需要知道什么叫軟間隔，而什么是軟間隔呢？這個(gè)在近似線性可分再說吧。

這里，我們只要知道，硬間隔在這里就是間隔。

所以，我們的整個(gè)訓(xùn)練過程，現(xiàn)在就變成了一個(gè)約束條件下的最優(yōu)化問題：
$max \gamma\\ s.t. y_i(\frac{\omega}{||\omega||}x_i+\frac{||\omega||}) \geq \gamma$
為什么要有約束條件呢？

其實(shí)很簡(jiǎn)單，首先我們要先滿足線性可分，才能使用硬間隔最大化。所以，我們得保證所有的訓(xùn)練數(shù)據(jù)都要有一個(gè)間隔，然后在從間隔中取出最大的一個(gè)。

其實(shí)，我們可以從前面知道：

函數(shù)間隔只是用來指示分類是否正確的函數(shù)，但是對(duì)于距離并沒有影響，簡(jiǎn)單的說，函數(shù)間隔只是掌握了方向，真正影響分類確信度的是 $||\omega||$ ，也就是 $\omega$ 的L2范數(shù)。

或者說這樣解釋：

首先因?yàn)閿?shù)據(jù)是線性可分的，所以，所以一定會(huì)有兩條直線穿過正例和負(fù)例的支持向量，如圖：

img

\omega x+b = 1\\ \omega x+b = -1

所以兩條直線之間的間隔就是我們要比較的間隔 $\frac{2}{||\omega||}$ ，然后我們的約束條件就是：

數(shù)據(jù)線性可分

如何實(shí)現(xiàn)呢？

只要有一條直線能把他們完全分開
$if\quad y_i == 1:\quad \omega x_i+b \geq 1\\ if\quad y_i == -1:\quad \omega x_i+b \leq 1\\$
合并在一起就是：
$y_i(\omega x_i+b) \geq 1$

所以，我們可以變換為：
$max\frac{1}{||\omega||}\\ s.t.y_i(\omega x_i+b)\geq 1$
然后，要求 $\frac{1}{||\omega||}$ 的最大值，也就是求 $||\omega||$ 的最小值。為了方便求導(dǎo)：
$min\frac{1}{2}||\omega||^2\\ s.t.y_i(\omega x_i+b)\geq 1$
現(xiàn)在有了公式，我們?cè)趺磧?yōu)化他呢？

對(duì)于有約束條件的優(yōu)化問題，我們使用拉格朗日乘子法

但是這里的拉格朗日乘子法和我們高數(shù)中學(xué)到的不太一樣，我們學(xué)習(xí)到的是最基本的拉格朗日乘子法是等式約束，很明顯，我們這里是不等式約束。所以，我們采用的是一種不一樣的東西：

上面的優(yōu)化問題等價(jià)于：
$min_\mu max_{\alpha,\beta}L(\mu,\alpha,\beta)\\ s.t.\quad \alpha_i \geq0 \quad i=1,2,3,4...,m.$
證明：

現(xiàn)在，我們來推導(dǎo)一下整個(gè)過程：

首先，我們要做的是間隔最大化：
$min \frac{1}{2}||\omega||^2\\ s.t.\quad y_i(\omega x_i+b) \geq 1$
然后，我們使用拉格朗日乘子法（向量化）：
$L(\omega, b,\lambda) = \frac{1}{2}\omega^T\omega+\sum_{i=1}^N\lambda_i(1-y_i(\omega^Tx_i+b))\\ min\quad maxL(\omega, b, \lambda)\\ s.t.\quad \lambda_i\geq 0$
為了減小計(jì)算難度，我們這里使用了拉格朗日的強(qiáng)對(duì)偶性：
$max\quad min L(\omega, b,\lambda)\\ s.t.\quad \lambda_i \geq 0$
然后，我們開始計(jì)算：

分別對(duì) $\omega,b$ 求偏導(dǎo)，等于零，再帶入到拉格朗日函數(shù)中，最終我們就得到了 $min\quad L(\omega, b, \lambda)$ 的值。

最終，我們就得到了：
$max (-\frac{1}{2}\sum_{i=1}^N\sum_{j=0}^N\lambda_i\lambda_jy_iy_jx_i^Tx_j+\sum_{i=1}^N\lambda_i)\\ s.t.\quad \lambda_i \geq 0 \\ \sum_{i=1}^N\lambda_iy_i=0$
這樣，我們就可以看到，我們把一個(gè)不等式約束的問題通過拉格朗日轉(zhuǎn)換成了等式約束問題，從而，我們可以算出這個(gè) $\lambda?$ ,然后，我們使用KKT條件算出最后的 $\omega,b?$ 。

KKT條件：(強(qiáng)對(duì)偶性一定滿足KKT)

主問題可行： $1-y_i(\omega_Tx_i+b) \leq 0;?$
對(duì)偶問題可行： $\lambda_i \geq0;?$
互補(bǔ)松弛： $\lambda_i(1-y_i(\omega_Tx_i+b)) =0;?$

根據(jù)KKT條件，我們可以求出：
$\omega = \sum_{i=0}{N}\lambda_iy_ix_i\\ b = y_i - \sum_{i=1}^N\lambda_iy_ix_i^Tx_k$
最終，我們就得到了分類決策函數(shù)。

對(duì)于最后一步最大化，我們將所有數(shù)據(jù)帶入，然后通過偏導(dǎo)等于零，求得最大值

所以，我們解決一個(gè)Hard-margin分類問題時(shí)，我們需要:

構(gòu)造并解出等式約束最優(yōu)化問題
計(jì)算 $\omega, b$
求出分離超平面。

線性不可分問題

顯然很多時(shí)候，我們的訓(xùn)練數(shù)據(jù)并不是那么的完美，總是有著各種各樣的噪聲，所以，我們需要將我們的SVM擴(kuò)展到線性不可分的情況上去。

這時(shí)候，我們就需要引入軟間隔最大化

什么是軟間隔呢？

我們從頭說起：

往往真實(shí)情況是我們并不能完美的將所有的數(shù)據(jù)分開，總有一些特異點(diǎn)在硬間隔最大化的策略下無法分類。那么這時(shí)候，我們?yōu)樗袛?shù)據(jù)的判斷上加入了一個(gè)常數(shù)松弛變量，使特異點(diǎn)在松弛變量的影響下可以被分開。所以這時(shí)候，我們的約束條件就變成了：
$y_i(\omega x_i+b)\geq1-\epsilon_i$
同時(shí)，對(duì)于每個(gè)松弛變量，我們需要支付一個(gè)代價(jià) $\epsilon_i?$ ,目標(biāo)函數(shù)就由原來的 $\frac{1}{2}||\omega||?$ 變?yōu)榱耍?br> $\frac{1}{2}||\omega||^2+C\sum_{i=1}^N\epsilon_i$
這里的C是懲罰參數(shù)，表示了對(duì)誤分類的懲罰力度。

現(xiàn)在，最小化目標(biāo)函數(shù)就有了兩層意思：

使 $\frac{1}{2}||\omega||^2$ 盡量小也就是間隔盡量大
使誤分類點(diǎn)盡可能少

C是調(diào)和兩者的參數(shù)。

現(xiàn)在，線性不可分的線性支持向量機(jī)的學(xué)習(xí)問題就變成了凸二次規(guī)劃問題：
$min_{\omega,b,\epsilon} \frac{1}{2}||\omega||^2+C\sum_{i=1}^N\epsilon_i\\ s.t.\quad y_i(\omega x_i+b)\geq1-\epsilon_i\\ \quad \epsilon\geq0$
其他的就和上面的一樣了。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

機(jī)器學(xué)習(xí)之支持向量機(jī)

機(jī)器學(xué)習(xí)之支持向量機(jī)

支持向量機(jī)

線性可分問題：