精品一区二区三区三区,久操国产在线资源,国产在线视频网

? ? SVM是一種傳統(tǒng)的學習算法，多用于二分類問題。根據(jù)SVM處理的問題樣本是否線性可分可以將SVM分為三種類型。如果存在一個劃分超平面可以完美的分隔開所有樣本，那么這種SVM叫“線性可分SVM”，通過“硬間隔最大化”學習得到模型；如果存在一個劃分超平面可以分隔開絕大部分樣本，只有少量樣本不能正確劃分，則可以通過“軟間隔最大化”學習得到模型，這種SVM叫“線性SVM”；還有一種情況，上面兩種情況均無法滿足，比如“異或問題”，這樣的SVM稱為“非線性SVM”，需要引入核函數(shù)，再按照“軟間隔最大化”的方法訓練模型。

? ? 總之，SVM學習策略的核心是“間隔最大化”。本文用于推導的公式是基于線性可分SVM的，也就是討論“硬間隔最大化”的數(shù)學原理。那么什么是“間隔”，什么又是“支持向量”，先來看一張圖片。

SVM對分割訓練集樣本有多種劃分超平面

? ? 假設樣本數(shù)據(jù)集 $D=\left\{ (x_{1} ,y_{1} ),(x_{2} ,y_{2} ),...,(x_{m} ,y_{m} ) \right\}$ ，其中 $y_{i} \epsilon \left\{ -1,+1 \right\}$ ，上圖中的“+”“-”表示正樣本和負樣本，可以看出，五條線表示五種超平面的劃分方法，那么哪個才是最合適的呢？直觀地理解，加粗的線是一種最佳的劃分超平面，因為它不僅可以正確分開所有樣本點，還處于最“中間”的位置。這會使得超平面劃分的泛化能力更強（如果給樣本加入噪聲或擾動，更不易分類錯）。換言之，此分類器的魯棒性更強，對未知的數(shù)據(jù)的分類錯誤率更低。

? ? 下面，我們逐步引出“間隔”的概念。在樣本空間中，劃分超平面的方程為 $\omega ^Tx+b=0$ （可從二維平面的角度理解），樣本中任意點到劃分平面的距離 $r$ 就是 $r=\frac{\vert\omega ^Tx+b\vert}{\vert\vert\omega \vert\vert}$ 。還是看上面的圖，樣本被完全正確的分類，也就是說如果樣本為正，則 $\omega ^Tx+b＞0$ ，如果樣本為負，則 $\omega ^Tx+b<0$ 。

? ? 我們觀察到，即使是離平面最近的樣本，也是與平面有一定距離的，離劃分超平面最近的那幾個向量，就是“支持向量”。由此可以看出SVM的一個特性，超平面的選擇只與支持向量的值有關(guān)，如果更改甚至刪掉其他的部分樣本，模型不會受到影響。這就是“支持向量機”。支持向量機的個數(shù)一般很少，所以支持向量機是由少數(shù)“重要的”樣本決定的。

????我們這樣描述所有樣本，令

$\omega ^Tx_{i} +b\geq +1, y_{i} =+1;\\\omega ^Tx_{i} +b\leq -1, y_{i} =-1;$

? ? 其中， $i$ 表示樣本編號。這里解釋一下，為什么可以令表達式 $\geq +1$ 而不是嚴格 $>0$ 。前面提到，離劃分平面最近的樣本點與平面是有一定的距離的，我們看劃分超平面的方程 $\omega ^Tx+b=0$ ， $\omega$ 和 $b$ 是可以同時擴大、縮小相同倍數(shù)而不改變原方程的，那么在正樣本的原方程可以寫為 $\omega ^Tx+b\geq r_{最近}$ ，除了自變量之外的三個參數(shù)可以同時擴大或縮小就成了上面的方程。那什么時候等號成立呢？自然就是當樣本為“支持向量”的時候。這時兩個異類的支持向量到平面的距離之和為：

$\gamma =\frac{2}{\vert \vert \omega \vert \vert} \\$ ;

? ? 這就是“間隔”的定義。不難看出，我們的目標應該是找到間隔最大的超平面，也就是

$max_{\omega ,b} \frac{2}{\vert \vert \omega \vert \vert } ;\\s.t. y_{i} (\omega ^T x_{i} +b)\geq 1,i=1...m;$

? ? 我們將其改寫為最小值函數(shù)：

$min_{\omega ,b} \frac{1}{2} \vert \vert \omega \vert \vert ^2 ;\\s.t. y_{i} (\omega ^T x_{i} +b)\geq 1,i=1...m;$

? ? 上式被稱為SVM的基本型（后文統(tǒng)一稱作“原問題方程”）。那如何求解這個問題呢？我們對其對偶問題進行求解，這樣做有兩個原因，一是對偶問題只涉及到一個參數(shù)，更易求解，二是自然引出核函數(shù)，核函數(shù)也是SVM的核心之一。對上式使用拉格朗日乘子法即可得到對偶問題：

$L(\omega ,b,\alpha )=\frac{1}{2} \vert \vert \omega \vert \vert ^2+\sum_{i=1}^m \alpha _{i} (1-y_{i} (\omega ^T x_{i} +b))\\$

? ? 我們最終要求解的問題時極大極小問題，即 $max_{\alpha _{i} } min_{\omega ,b} L(\omega ,b,\alpha )$ ，首先計算極小的部分，根據(jù)大學數(shù)學的基本知識，令 $L(\omega ,b,\alpha )$ 對 $\omega$ 和 $b$ 求偏導：

$\omega =\sum_{i=1}^m \alpha _{i} x_{i} y_{i} ;\\0=\sum_{i=1}^m \alpha _{i} y_{i} ;$

? ? 代入原式，得：

$\\L(\omega ,b,\alpha )=\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha _{i} \alpha _{j} x_{i} x_{j} y_{i} y_{j} +\sum_{i=1}^m \alpha _{i} -\sum_{i=1}^m \alpha _{i} x _{i} y_{i} \sum_{j=1}^m \alpha _{j} x _{j} y_{j} \\=\sum_{i=1}^m \alpha _{i}-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha _{i} \alpha _{j} x_{i} x_{j} y_{i} y_{j}$

????所以對偶問題要解的方程是：

$\\max_{\alpha _{i} } L(\omega ,b,\alpha )=max_{\alpha _{i} }(\sum_{i=1}^m \alpha _{i}-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha _{i} \alpha _{j} x_{i} x_{j} y_{i} y_{j} )$

$s.t.\sum_{i=1}^m \alpha _{i} y_{i} =0; \\\alpha _{i} \geq 0,i=1...m;$

? ? 只需要解出來一個向量 $\alpha$ 即可。這里現(xiàn)成的、高效的算法是SMO算法。

SMO的基本思路是先固定 $\alpha _{i}$ 之外的所有參數(shù)，求 $\alpha _{i}$ 上的極值。每次SMO會選擇兩個變量 $\alpha _{i}, \alpha _{j}$ ，并固定其他參數(shù)。

? ? 在每次迭代時，選擇一對需要更新的變量 $\alpha _{i} ,\alpha _{j}$ ，固定其他變量，也就是：

$\alpha _{i} y_{i} +\alpha _{j} y_{j}=c;\\c=-\sum_{k\neq i,j}\alpha _{k} y_{k};$

? ? 這樣， $\alpha _{j}$ 可以表示為 $\alpha _{i}$ 的函數(shù)，對偶問題要解的極大值方程為單變量二次規(guī)劃問題，易于求解。求解出 $\alpha$ 之后，再求解 $\omega ,b$ ，有如下定理：

若 $\alpha =(\alpha _{1} ,\alpha _{2} ,...,\alpha _{n} )^T$ 是對偶問題的解，那么存在 $\alpha _{j} >0$ ，且原問題方程的解為：

$\omega =\sum_{i=1}^m\alpha _{i} y _{i} x _{i} ;\\b=y _{i} -\sum_{i=1}^m\alpha _{i} y _{i}( x _{i}\bullet x _{j});$