2018-11-15 神奇的SVM

1、神奇的SVM從點(diǎn)到直線距離開(kāi)始：

r=\frac{\vert w^Tx+b\vert }{\vert \vert w\vert \vert }

一個(gè)二位坐標(biāo)系，怎么才能把兩類分開(kāi)，我翻墻找到個(gè)MIT機(jī)器學(xué)習(xí)的視頻，賊棒！把軟件隔、核函數(shù)解釋的清清楚楚。有個(gè)油管是視頻，貼不過(guò)來(lái)，只能給路徑了！簡(jiǎn)單清晰佩服佩服！吐槽下國(guó)內(nèi)的講述聽(tīng)不下去，上來(lái)就推公式，真的受不鳥(niǎo)。

https://www.youtube.com/watch?v=6nDqY8MPLDM

2、如何選這條“線”——優(yōu)化問(wèn)題

1、解決目標(biāo)：最大化間隔r，也就是最小化間隔\vert\vert w \vert\vert

\begin{array} \\min_{w,b} \quad\frac{1}{2} \vert \vert w \vert \vert ^2\\ \text{s.t} \quad \quad y_i(w^Tx_i+b)\geq 1 , \quad i=1,2,...,m \end{array}

2、對(duì)偶問(wèn)題轉(zhuǎn)換：原優(yōu)化問(wèn)題是凸二次規(guī)劃問(wèn)題，不等式太多，需要求解的空間太大，所以求其對(duì)偶問(wèn)的解。

對(duì)偶理論有許多重要應(yīng)用：在原始的和對(duì)偶的兩個(gè)線性規(guī)劃中求解任何一個(gè)規(guī)劃時(shí)，會(huì)自動(dòng)地給出另一個(gè)規(guī)劃的最優(yōu)解；當(dāng)對(duì)偶問(wèn)題比原始問(wèn)題有較少約束時(shí)，求解對(duì)偶規(guī)劃比求解原始規(guī)劃要方便得多。

（1）拉格朗日乘子法和KKT條件

https://www.zhihu.com/question/58584814/answer/159863739

重點(diǎn)：

1、KKT條件是凸優(yōu)化問(wèn)題有解的必要條件，主要是對(duì)不等式限制，把超多不等式轉(zhuǎn)化為等式，只留下松弛變量一個(gè)不等式約束，這樣就是減少了解空間，提升效率。

2、拉格朗日約束就是進(jìn)一步求導(dǎo)的方式，縮減不等式數(shù)量。

思想：將不等式約束條件變成等式約束條件

通過(guò)拉格朗日乘子我們將原問(wèn)題化為先求\alpha 為何值時(shí)，拉格朗日方程有最大值，然后求出\alpha 后求解w=\sum_{i=1}^m {\alpha} _i y_i x_i（拉格朗日方程對(duì)w和b求偏導(dǎo)為0）和b的問(wèn)題。

故所求的對(duì)偶問(wèn)題是：

\begin{array} \\\max_{\alpha} \quad \sum_{i=1}^m {\alpha} _i-\frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m{\alpha} _i{\alpha} _jy_iy_j \textbf{x}_i^T \textbf{x}_j \\ s.t \qquad \sum_{i=1}^m{\alpha} _iy_i=0;\\ \quad \quad\quad \alpha _i\geq 0,i=1,2... ,m \end{array}

KKT條件（注意是必要條件）

\begin{cases} \alpha _i\geq0; \\ y_if(x_i)-1 \geq 0;\\ \alpha _i( y_if(x_i)-1 ) = 0 \end{cases}

可見(jiàn)，通過(guò)對(duì)偶問(wèn)題后，本問(wèn)題就轉(zhuǎn)換為求解\alpha 獲取最大值的問(wèn)題。通過(guò)KKT條件 \alpha _i( y_if(x_i)-1 ) = 0，我們進(jìn)一步確認(rèn)兩種情況的出現(xiàn)，一種是： \alpha _i= 0，另一種情況是 y_if(x_i)=1

于是上面這個(gè)二次規(guī)劃問(wèn)題（\textbf{x}_i^T \textbf{x}_j ）進(jìn)一步用SMO方法解。
3、序列最小優(yōu)化算SMO:

https://zhuanlan.zhihu.com/p/29212107

為什么用這個(gè)算法呢？百度發(fā)現(xiàn)怎么解二次規(guī)劃問(wèn)題，很多人會(huì)說(shuō)常用方法是：橢球法、內(nèi)點(diǎn)法、增廣拉格朗日法、梯度投影法 等。

其實(shí)問(wèn)題再回歸以下，什么是支持向量？？支持向量就是那些在不同樣本中離我們的“線”最近的樣本點(diǎn)。

SVM其實(shí)訓(xùn)練只需要支持向量參與就行，其他都是忽略項(xiàng)。那么上述這些算法其實(shí)對(duì)于大量樣本來(lái)講，大部分的樣本都是無(wú)用的，也就是無(wú)法引起我們對(duì)目標(biāo)函數(shù)更大的變化，所以專門設(shè)計(jì)了SOM算法，用啟發(fā)式算法，每次選擇取違背KKT條件程度最大的變量，這個(gè)怎么找？SOM用啟發(fā)式算法，當(dāng)確定了第一個(gè)變量后，選擇使兩個(gè)變量對(duì)應(yīng)樣本之間最大的變量作為第二個(gè)變量。直觀來(lái)說(shuō)，更新兩個(gè)差別很大的變量，比起相似的變量，會(huì)帶給目標(biāo)函數(shù)更大的變化。思路通了以后再看以上公式推導(dǎo)和編程。

3、如何選這條“線”——不是“直”線？？

核函數(shù)：

類似學(xué)習(xí)線性變換的方法，我們一般講低緯度不可分的話我們會(huì)給這些數(shù)據(jù)進(jìn)行映射，將其映射到高緯平面中，使其線性可分。但進(jìn)一步，如果凡是遇到線性不可分的樣例，一律映射到高維空間，那么這個(gè)維度大小是會(huì)高到可怕的(如上文中19維乃至無(wú)窮維的例子)。那咋辦呢？此時(shí)，核函數(shù)就隆重登場(chǎng)了，核函數(shù)的價(jià)值在于它雖然也是講特征進(jìn)行從低維到高維的轉(zhuǎn)換，但核函數(shù)絕就絕在它事先在低維上進(jìn)行計(jì)算，而將實(shí)質(zhì)上的分類效果表現(xiàn)在了高維上，也就如上文所說(shuō)的避免了直接在高維空間中的復(fù)雜計(jì)算。

4、如何選這條“線”——隔板不是“1”？？

最大化隔板、不滿足條件的樣本盡量少？？？

怎么辦？繼續(xù)對(duì)第一個(gè)拉格朗日方法優(yōu)化問(wèn)題加約束??！方法和1一樣，只是在出力樣本時(shí)候加個(gè)損失函數(shù)，其中有hinge損失、指數(shù)損失和對(duì)數(shù)損失。這樣我們就完成了整個(gè)問(wèn)題的主要思路的梳理。

5、個(gè)人提煉

其實(shí)，SVM可以說(shuō)是3條直線走天下，簡(jiǎn)單易懂，最后目標(biāo)極其清晰！這里的支持向量、對(duì)偶問(wèn)題、核函數(shù)、軟隔板，其實(shí)也就是研究人員分析問(wèn)題時(shí)的幾個(gè)步驟：1、找關(guān)鍵點(diǎn)，2、復(fù)雜問(wèn)題反面思考，3、高緯解決問(wèn)題，4、沒(méi)有一次能全部解決的問(wèn)題，凡事留個(gè)裕度。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容