給定一個(gè)數(shù)據(jù)集D={(x1,y1),(x2,y2),……,(xm,ym)}高诺，yi∈{-1,+1}妙黍。對(duì)于分類學(xué)習(xí)來說，最基本的想法就是找出一個(gè)超平面箱叁，能夠把不同類別的樣本分開。
對(duì)于上圖的分類惕医，我們會(huì)想用一個(gè)超平面劃分兩類耕漱。
可以看出，劃分兩類的超平面有多種抬伺，那我們應(yīng)該選擇哪一種呢螟够？
直覺上，我們會(huì)選擇超平面1(紅色線)峡钓。因?yàn)樵摮矫鎸?duì)訓(xùn)練樣本局部擾動(dòng)的"容忍性"好齐鲤。如果選擇超平面3，當(dāng)有一個(gè)正例在超平面3的上方之外的話椒楣，那么就會(huì)分類錯(cuò)誤给郊，超平面3就不容忍這個(gè)正例，所以說超平面1的容忍性好捧灰。換句話說淆九，就是超平面1所產(chǎn)生的分類結(jié)果是最魯棒的，就是對(duì)新樣例的泛化能力強(qiáng)毛俏。
在樣本空間中炭庙，超平面的線性方程如下：
其中w = (w1,w2,……,wd)為法向量，決定了超平面的方向煌寇；b為位移項(xiàng)(截距)焕蹄，決定了超平面與原點(diǎn)之間的距離。劃分超平面最終由w和b確定阀溶，記為(w,b)腻脏。
樣本空間中樣本點(diǎn)到超平面的距離如下：
假設(shè)超平面(w,b)能將訓(xùn)練樣本正確分類鸦泳，則對(duì)于(xi,yi)∈D，
若yi=1永品，則wTxi+b>0做鹰；若yi= -1，則有wTxi+b < 0鼎姐，令
由于上面這個(gè)轉(zhuǎn)換詳解過于復(fù)雜钾麸，可以看視頻詳解，這里不作說明炕桨。對(duì)于距離超平面最近的樣本點(diǎn)饭尝，我們稱為"支持向量"。兩個(gè)異類支持向量到超平面的距離之和稱為間隔献宫，如下
為了盡可能劃分類別正確芋肠，我們可以轉(zhuǎn)化為找到具有"最大間隔"的超平面，即找到w和b遵蚜，使得γ最大帖池，即：
而最大化間隔，就需要最大化||w||-1吭净，相當(dāng)于最小化||w||2睡汹，則目標(biāo)可以重寫為：
這就是支持向量機(jī)(SVM)的基本模型。
6.2 對(duì)偶問題
原始問題與對(duì)偶問題以及KKT條件的關(guān)系解釋https://blog.csdn.net/fkyyly/article/details/86488582
原始問題與對(duì)偶問題的視頻講解:https://www.bilibili.com/video/av77638697?p=11
原始問題轉(zhuǎn)化為對(duì)偶問題:https://www.bilibili.com/video/av77638697?p=12
上面這三個(gè)鏈接對(duì)于對(duì)偶問題有較好的解釋寂殉。
對(duì)于上式囚巴，是一個(gè)凸函數(shù)二次規(guī)劃的問題。我們可以對(duì)上式使用拉格朗日乘子法得到原始問題的對(duì)偶問題友扰。
對(duì)每個(gè)約束條件添加拉格朗日乘子αi彤叉，且αi≥0，則該問題的優(yōu)化函數(shù)為：
先求優(yōu)化函數(shù)對(duì)于w和b的極小值即村怪，對(duì)w和b求偏導(dǎo)秽浇，令偏導(dǎo)為0，有：
接著將w代入優(yōu)化函數(shù)得到：
可以看出甚负，對(duì)w和b求偏導(dǎo)之后代入柬焕，再考慮對(duì)b求偏導(dǎo)得到的約束，就得到了對(duì)偶問題：
得到優(yōu)化函數(shù)只剩下α作為參數(shù)梭域，只要求優(yōu)化函數(shù)的極大值斑举，就可以求出α，進(jìn)而求出w和b病涨，再代入我們的模型富玷，就可以了，假設(shè)我們的模型是f(x) = wTx + b，則：
上述過程要滿足KKT條件：
對(duì)于對(duì)偶問題赎懦，我們?cè)撊绾吻蠼猞聊厝妇椋课覀冇玫木褪?b>SMO算法
SMO基本思路：先固定αi之外的所有參數(shù)，然后求αi上的極值铲敛。
SMO步驟：每次選擇兩個(gè)變量αi和αj褐澎，并固定其他參數(shù)会钝，分別對(duì)αi和αj求偏導(dǎo)為0伐蒋，得到αi和αj，若符合約束條件就不用算迁酸，若不符合約束條件先鱼，再更新αi和αj，代入對(duì)偶問題的目標(biāo)函數(shù)奸鬓，直到符合條件焙畔。
可以看出，SMO固定了其他的參數(shù)串远，僅僅考慮αi和αj宏多，因此對(duì)偶問題中的約束條件可以重寫為：
其中的c：
通過重寫之后的約束條件，我們可以將對(duì)偶問題中的目標(biāo)函數(shù)的αj消去澡罚，只剩下αi一個(gè)變量伸但，這時(shí)我們的約束只有KKT里面的αi≥0，對(duì)αi求導(dǎo)為0留搔，得到αi更胖，再求出aj，通過這樣子我們可以更高效的求出ai和aj隔显。求出α之后却妨，代入：
就可以計(jì)算出w了。
那么b該如何計(jì)算呢括眠？
使用所有支持向量求解的平均值
設(shè)支持向量表示為(xs,ys)
設(shè)S= { i | αi>0,i = 1,2,3……,m}為所有支持向量的下標(biāo)集彪标。
支持向量機(jī)的代碼實(shí)現(xiàn)：
https://blog.csdn.net/qq_43608884/article/details/88658216
6.3 核函數(shù)
在前面的討論中，我們假設(shè)訓(xùn)練樣本都是線性可分的掷豺，上述SVM也只是在處理線性可分的數(shù)據(jù)捐下。事實(shí)上，我們很多數(shù)據(jù)都是非線性可分的萌业。
對(duì)于非線性的情況坷襟，SVM 的處理方法是選擇一個(gè)核函數(shù) κ(?,?)，通過將數(shù)據(jù)映射φ到高維空間生年，來解決在原始空間中線性不可分的問題婴程。
具體來說，在線性不可分的情況下抱婉，支持向量機(jī)首先在低維空間中完成計(jì)算档叔，然后通過核函數(shù)將輸入空間映射到高維特征空間桌粉，最終在高維特征空間中構(gòu)造出最優(yōu)分離超平面，從而把平面上本身不好分的非線性數(shù)據(jù)分開衙四。
如圖所示铃肯，一堆數(shù)據(jù)在二維空間無法劃分，從而映射到三維空間里劃分：
類似传蹈，原始問題為：
對(duì)偶問題為：
其中押逼，紅色方框里面的式子，表示的是樣本xi和xj映射到特征空間之后的內(nèi)積惦界，當(dāng)屬性空間的維數(shù)很大時(shí)挑格，直接計(jì)算內(nèi)積是很困難的，因此沾歪，有：
即xi和xj在屬性空間中的內(nèi)積等于在原始樣本空間中通過函數(shù)K(·,·)計(jì)算的結(jié)果漂彤。
這里的函數(shù)K(·,·)，就是核函數(shù)灾搏。
于是挫望，對(duì)偶問題可以重寫為：
最終可以得到：
常用的核函數(shù)K(·,·)有以下幾種：
常用核函數(shù)
關(guān)于核函數(shù)，有下面三個(gè)關(guān)系：
若k1和k2為核函數(shù)狂窑，則對(duì)于任意正數(shù)γ1和γ2媳板，其線性組合γ1k1+γ2k2也為核函數(shù)
若k1和k2為核函數(shù)，則核函數(shù)的直積也為核函數(shù)：
若k1和k2為核函數(shù)蕾域，則對(duì)于任意函數(shù)g(x)：
對(duì)文本數(shù)據(jù)通常采用線性核拷肌，情況不明時(shí)可先嘗試高斯核。
支持向量機(jī)的非線性代碼實(shí)現(xiàn)
https://blog.csdn.net/kt513226724/article/details/80413018
6.4 軟間隔與正則化
在上述中的支持向量機(jī)中旨巷，我們要求所有樣本都要滿足約束巨缘，即都被劃分正確，這叫做"硬間隔"采呐∝舶可實(shí)際上挟秤，很難確定合適的核函數(shù)使得樣本在特種空間中線性可分，不允許分類錯(cuò)誤的樣本。
緩解這一個(gè)問題的辦法就是允許支持向量機(jī)在一些樣本上出錯(cuò)旁振，
為此囱淋，引入"軟間隔"嗜闻。
軟間隔允許某些樣本不滿足約束條件斩芭，也要讓這些樣本很少。則優(yōu)化目標(biāo)可以寫為：
其中C是一個(gè)常數(shù)蝶糯，可以理解為問題正則化時(shí)加入的參數(shù)洋只。當(dāng)C趨于無窮大時(shí)，所有樣本均滿足原來硬間隔的約束條件；當(dāng)C取有限值時(shí)识虚，允許一些樣本不滿足約束肢扯。
而式子中的
然而"0/1損失函數(shù)"的不可微、不連續(xù)担锤，數(shù)學(xué)性質(zhì)較差蔚晨，于是我們可以用其他函數(shù)替代損失函數(shù)，稱為"替代損失函數(shù)"肛循，通常數(shù)學(xué)性質(zhì)較好铭腕，通常有以下三種替代損失函數(shù)：
下面我們使用hinge損失函數(shù)來優(yōu)化目標(biāo)。
首先對(duì)訓(xùn)練集的每個(gè)樣本(xi,yi)引入一個(gè)松弛變量ξi≥0育拨，使函數(shù)間隔加上松弛變量大于等于1谨履，也就是說欢摄，約束條件變?yōu)椋?/p>
對(duì)比硬間隔最大化熬丧，可以看到我們對(duì)樣本到超平面的函數(shù)距離的要求放松了，之前是一定要大于等于1怀挠，現(xiàn)在只需要加上一個(gè)大于等于0的松弛變量能大于等于1就可以了析蝴。當(dāng)引入了ξ之后，也是需要成本的绿淋，所以硬間隔到軟間隔的優(yōu)化目標(biāo)變?yōu)椋?/p>
接著我們對(duì)軟間隔支持向量機(jī)進(jìn)行目標(biāo)函數(shù)的優(yōu)化闷畸。通過拉格朗日乘子法得到：
對(duì)w、b和ξ求偏導(dǎo)為0吞滞，得到：
將他們代入拉格朗日函數(shù)：
此時(shí)我們就得到了佑菩，原始問題的對(duì)偶問題：
接著用SMO算法算出α，就可以得到w裁赠，然后再計(jì)算b殿漠，與硬間隔類似。
對(duì)于上述過程佩捞，也需要滿足KKT條件：
對(duì)于訓(xùn)練樣本(xi,yi)绞幌，有
1）若α=0，那么yi(wTxi+b)-1≥0一忱，即樣本在間隔邊界之外莲蜘，即被正確分類。
2）若0<α
3）若α=C帘营，則μi=0票渠，該樣本點(diǎn)是有可能正確分類、也有可能分類錯(cuò)誤芬迄，此時(shí)考試ξi问顷。
① 如果0≤ξi≤1，那么樣本點(diǎn)在超平面和間隔邊界之間，但是被正確分類择诈。
② 如果ξi=1械蹋，那么樣本點(diǎn)在超平面上，無法被正確分類羞芍。
③ 如果ξi＞1哗戈，樣本點(diǎn)被分類錯(cuò)誤。
對(duì)于荷科，允許誤差的優(yōu)化目標(biāo)函數(shù)唯咬，我們可以寫為更加一般的形式：
Ω(f)稱為"結(jié)構(gòu)風(fēng)險(xiǎn)"，用于描述模型f的某些性質(zhì)畏浆；
第二項(xiàng)的Σml(f(xi),yi)稱為"經(jīng)驗(yàn)風(fēng)險(xiǎn)"胆胰，用于描述模型與訓(xùn)練數(shù)據(jù)的契合度。
C稱為正則化常數(shù)刻获，用于對(duì)結(jié)構(gòu)風(fēng)險(xiǎn)和經(jīng)驗(yàn)風(fēng)險(xiǎn)進(jìn)行折中蜀涨。
上式被稱為"正則化問題"，Ω(f)稱為正則化項(xiàng)蝎毡，C為正則化常數(shù)厚柳。
6.5 支持向量回歸(SVR)
上面講到的SVM是用于分類任務(wù)的，而對(duì)于回歸任務(wù)沐兵，我們使用SVR别垮。
SVM分類，就是找到一個(gè)平面扎谎，讓兩個(gè)分類集合的支持向量或者所有的數(shù)據(jù)離分類平面最遠(yuǎn)碳想；
SVR回歸，就是找到一個(gè)回歸平面毁靶，讓一個(gè)集合的所有數(shù)據(jù)到該平面的距離最近胧奔。
SVR假設(shè)f(x)與y之間最多有ε的偏差，即以f(x)為中心老充，允許f(x)+ε和f(x)-ε的誤差葡盗，構(gòu)建一個(gè)2ε的間隔。
SVR的形式如下
由于間隔帶的兩側(cè)松弛程度有所不同啡浊，所有引入松弛變量ξi和ξ^i觅够，則原始問題重寫為：
接著我們要求對(duì)偶問題。首先引入拉格朗日乘子巷嚣，可以得到拉格朗日函數(shù)：
令L對(duì)w喘先、b、ξi廷粒、ξ^i的偏導(dǎo)為0窘拯，可得到：
將它們代入L红且，可以得到對(duì)偶問題：
上述過程中，要滿足KKT條件：
將上面求得的w代入我們?cè)瓉淼哪Ｐ蚮(x) = wTx + b涤姊，得到SVR的解：
由KKT可以看出暇番，對(duì)每個(gè)樣本(xi,yi)有:
1）(C - αi)ξi=0 ，2）αi(f(xi) - yi- ε - ξi)=0思喊。
于是通過SMO算法得到αi之后壁酬，若0<αi
實(shí)際上，我們更常用的是：選取所有滿足0 < ai< C的樣本求解b之后取平均值恨课。
若考慮映射到高維空間則有：
最終通過上述類似的求解過程舆乔，我們得到SVR可以表示為：
6.6 核方法
對(duì)于SVM和SVR，它們的優(yōu)化問題都是類似下面的式子：
而SVR和SVM學(xué)得的模型總能表示為核函數(shù)K(x,xi)的線性組合剂公，所以上式的模型也可以寫成為核函數(shù)的線性組合：
上式模型的解
對(duì)于上面這個(gè)結(jié)論希俩，就是"表示定理"
人們基于核函數(shù)的學(xué)習(xí)方法，稱為"核方法"纲辽。最常見的颜武，是通過引入核函數(shù)來將線性學(xué)習(xí)擴(kuò)展為非線性。
下面以"核線性判別分析"(KLDA)為例文兑，演示如何引入核函數(shù)進(jìn)行非線性擴(kuò)展盒刚。
我們難以直到映射φ的具體形式腺劣，因此使用核函數(shù)K(x,xi) = φ(xi)Tφ(x)來表達(dá)映射和特征空間F绿贞。
把J(w)作為式子6.57中的損失函數(shù)，令Ω=0橘原，有
由表示定理得籍铁，
再由式6.59得
