轉(zhuǎn)自微信公眾號：機(jī)器學(xué)習(xí)算法與Python學(xué)習(xí)
統(tǒng)計學(xué)習(xí)方法 & 小象學(xué)院
SVM算法優(yōu)點：
可用于線性/非線性分類，也可以用于回歸
低泛化誤差
容易解釋
計算復(fù)雜度低
缺點：
對參數(shù)和核函數(shù)的選擇比較敏感
原始SVM只比較擅長處理二分類問題
它的基本模型是定義在特征空間上的間隔最大的分類器，間隔最大使它有別于感知機(jī)。
SVM還包括核技巧，這使它成為實質(zhì)上的非線性分類器。
支持向量機(jī)的學(xué)習(xí)策略就是間隔最大化，可以形式化為一個求解凸二次規(guī)劃的問題，也等價于正則化的合頁損失函數(shù)的最小化問題。
支持向量機(jī)的學(xué)習(xí)算法是求解凸二次規(guī)劃的最優(yōu)化算法
方法包括：
1. 線性可分支持向量機(jī)
2. 線性支持向量機(jī)
3. 非線性支持向量機(jī)
線性可分時，通過硬間隔最大化，當(dāng)數(shù)據(jù)近似線性可分時，通過軟間隔最大化，當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時，通過使用核技巧及軟間隔最大化
通過核函數(shù)可以學(xué)習(xí)非線性支持向量機(jī)，等價于隱式地在高維特征空間中學(xué)習(xí)線性支持向量機(jī)。這樣的方法稱為核技巧
關(guān)鍵點：支持向量機(jī)、核函數(shù)、序列最小優(yōu)化算法SMO
一、線性可分與硬間隔最大化
假設(shè)輸入空間與特征空間為兩個不同的空間。輸入空間為歐式空間或離散集合，特征空間為歐式空間或希爾伯特空間。假設(shè)這兩個空間元素一一對應(yīng)并將輸入空間中的輸入映射為特征空間中的特征向量。
非線性支持向量機(jī)利用一個從輸入空間到特征空間的非線性映射將輸入映射為特征向量。所以輸入都是由輸入空間轉(zhuǎn)換到特征空間，支持向量機(jī)的學(xué)習(xí)是在特征空間進(jìn)行的。
? ? ?假設(shè)給定一個特征空間上的訓(xùn)練數(shù)據(jù)集
其中xi為第i個特征向量，yi為xi類的標(biāo)記。學(xué)習(xí)目標(biāo)是在特征空間中找到一個分離超平面，wx+b=0
一般地，當(dāng)訓(xùn)練數(shù)據(jù)線性可分時，存在無窮個分離超平面可將兩類數(shù)據(jù)正確分開，感知機(jī)利用誤分類最小策略，求得分離超平面，這時的解也是無窮多個的，因為解和初始解的選擇和步驟有密切關(guān)系。
而線性可分支持向量機(jī)利用間隔最大化求最優(yōu)分離超平面，這時解是唯一的。
--函數(shù)間隔與幾何間隔
一般來說，一個點距離分離超平面的遠(yuǎn)近可以表示為分類預(yù)測的準(zhǔn)信度，在超平面wx+b=0確定的情況下，|wx+b|能夠相對地表示點x距離超平面的遠(yuǎn)近。所以可以用y（wx+b）來表示分類的正確性以及確信度，這就是函數(shù)間隔
函數(shù)間隔可以表示分類預(yù)測的正確性以及確信度，但是選擇分離超平面時只有函數(shù)間隔是不夠的，因為只要成比例地改變w和b，超平面并沒有改變，但是函數(shù)間隔卻變?yōu)樵瓉淼膎倍。所以，我們需要對超平面的法向量w加上某些約束，如規(guī)范化，||w||=1，這樣使得間隔是確定的，這時函數(shù)為幾何間隔。
--間隔最大化
支持向量機(jī)學(xué)習(xí)的基本想法是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面。與感知機(jī)相比不僅將正負(fù)實例點分來，而且對于最難分的實例點（離超平面最近的點）也有足夠的確信度將它們分開
原始問題
對偶問題
在決定分離超平面時只有支持向量起作用，而其他實例不起作用
支持向量的個數(shù)一般很少，所以支持向量機(jī)由很少的重要的訓(xùn)練樣本決定
學(xué)習(xí)的對偶算法
通過求解對偶問題得到原始問題的最優(yōu)解，優(yōu)點是：1.對偶問題往往更容易求解；2. 引入核函數(shù)，推廣到非線性分類問題
引入拉格朗日函數(shù)
其中alpha=（alpha1,...,alphan）T的拉格朗日乘子向量
為了得到對偶問題的解，首先對L（w,b,alpha）對w，b的極小，再對alpha求極大
將目標(biāo)函數(shù)由極大轉(zhuǎn)換為極小得到如下等價對偶最優(yōu)化問題
補(bǔ)充KKT條件
對于含有不等式約束的優(yōu)化問題，如何求取最優(yōu)值呢？常用的方法是KKT條件，同樣地，把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫為一個式子L(a, b, x)= f(x) + a*g(x)+b*h(x)，KKT條件是說最優(yōu)值必須滿足以下條件：
1. L(a, b, x)對x求導(dǎo)為零；
2. h(x) =0;
3. a*g(x) = 0;
也就是說，分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入內(nèi)積。7.30稱為線性可分支持向量機(jī)的對偶形式。
在此模型中w和b只依賴于訓(xùn)練數(shù)據(jù)中對應(yīng)于alphai>0的樣本點
線性支持向量機(jī)與軟間隔最大化
通常，訓(xùn)練數(shù)據(jù)中有一些奇異點（outlier）,將這些奇異點去除后剩下的大部分樣本點是線性可分的。
線性不可分意味著某些樣本點不滿足函數(shù)間隔大于等于1的約束條件，因此我們可以引進(jìn)一個松弛變量eta>=0
約束條件變?yōu)?/p>
目標(biāo)函數(shù)變?yōu)?/p>
C>0稱為懲罰參數(shù)，C值大對誤分類的懲罰增大，C值小時對于誤分類的懲罰減小。
目標(biāo)函數(shù)包含兩層含義：使1/2||w||^2盡量小即間隔盡量大，同時使得誤分類點的個數(shù)盡量小，C是協(xié)調(diào)二者的關(guān)系。
變?yōu)槿缦峦苟我?guī)劃問題原始問題
解為(w,b,eta)
學(xué)習(xí)的對偶算法
由于原始問題對于b的解并不唯一，所以實際計算可以取在所有復(fù)合條件的樣本點上的平均值
