支持向量機(support vector machine麻裁,SVM)是一種出色的分類技術(shù),也可以用于回歸分析(SVR)嗤锉。這種技術(shù)可以很好的應(yīng)用于高維數(shù)據(jù)渔欢,避免維度災(zāi)難等問題。
SVM有一個特點就是使用訓練集中的一個子集來表示決策邊界档冬,該子集稱作支持向量膘茎。
最大邊緣超平面
SVM的核心目標是找到分類中的最大邊緣超平面,讓其作為決策邊界酷誓,那么什么是最大邊緣超平面呢披坏?
可以看到,中間的這些直線把“+”和“-”分隔開來盐数,形成了兩類棒拂,這些直線就叫做超平面,它使得所有的“+”號在超平面的一側(cè),所有的“-”號在另外一側(cè)帚屉,由于這些超平面都能完美的分隔+和-號的類別谜诫,所以誤差是0.
但是可以發(fā)現(xiàn),這種超平面有無數(shù)多個(圖中就能看到有好多個)攻旦,如果有一些未知的點需要預(yù)測分類喻旷,那么他們可能未必會被這些超平面完美的分隔:
以最下側(cè)的超平面為例,如果我們有未知的點按照藍色排布牢屋,那么可以看到且预,最下側(cè)的這個超平面完全不能分類所有藍色點的“-”號,那么如果它作為決策邊界烙无,泛化能力就不是很好锋谐。
我們肯定要從這些超平面中選一個最合理的作為決策邊界,使得未知的點盡量的能被正確預(yù)測分類截酷,那么肯定是上圖中間的這個超平面最好了涮拗,我們目測就可以得到結(jié)果,因為它離兩邊這些點的距離圍成的面積應(yīng)該是最大的迂苛,而且兩邊的面積基本是差不多的三热。(個人理解)所以應(yīng)該能裝得下更多的未知點,也就能得到最好的泛化效果灾部。
為了不用肉眼觀測康铭,能量化的得到這個結(jié)果,我們可以定義最大邊緣超平面赌髓。
下圖中有兩個決策邊界从藤,和
,其中每個決策邊界都對應(yīng)著兩個超平面(記作
)荣倾。其中
是由
進行兩側(cè)平移,直到接觸到最近的一個訓練集的點停止舌仍,生成的妒貌,同理
也是铸豁。
我們把兩個超平面(同一個決策邊界生成的)之間的距離叫做分類器的邊緣灌曙,那么下圖中,顯然生成的兩個超平面距離應(yīng)該是最大的节芥,
就叫做最大邊緣超平面(
雖然是決策邊界在刺,但是決策邊界都是超平面)逆害。
通常來說,較大邊緣的超平面具有更好的泛化誤差蚣驼,如果邊緣比較小魄幕,那么決策邊界的輕微擾動都可能對分類產(chǎn)生顯著影響。
SVM算法的核心就是設(shè)計最大化決策邊界邊緣的分類器颖杏,以保證最壞情況下泛化誤差最小纯陨。
線性支持向量機
公式
假設(shè)有一個包含個訓練樣本的二元分類問題,每個樣本表示為一個二元組
, 其中
队丝,對應(yīng)于第i個樣本的屬性集(一個樣本有多個屬性/特征),設(shè)y有-1和1兩個類別,則一個線性分類器的決策邊界可以寫成如下形式:
其中的為參數(shù),
是法向量(垂直于決策邊界)的向量臭墨,代表著超平面的方向赔嚎,而
代表超平面與原點之間的距離(可以用一次函數(shù)的公式來理解)。
為什么一定會垂直于決策邊界呢胧弛?我們設(shè)有兩個點
是決策邊界上的兩點尤误,那么有:
二者相減有:
因為肯定是平行于決策邊界的,那么為了保證內(nèi)積為0结缚,
肯定要垂直于決策邊界损晤。
根據(jù)以上的決策邊界,則肯定有:
在決策邊界上方的點肯定存在
使得
(上圖中的方塊點)
在決策邊界下方的點肯定存在使得
(上圖中的圓形點)
如果上方的點是1類红竭,下方是-1類尤勋,則有:
如果我們能得到,那么就可以用這個公式對未知點進行預(yù)測分類茵宪。代入公式最冰,如果
就是1類,反之則為-1類稀火。
接下來我們的任務(wù)就是如何求這兩個參數(shù)暖哨,首先,既然是求最大邊緣超平面凰狞,我們要把決策邊界的邊緣算出來篇裁。
決策邊界的邊緣
根據(jù)上圖,考慮那些離決策邊界最近的方形和圓形赡若,我們可以得到兩個平行的超平面表示如下:
決策邊界的邊緣就是這兩個超平面的距離达布。
參考上圖的斩熊,不難得出邊緣
為:
其中是w的2范數(shù)往枣。
很顯然,我們想要讓這個最大辱姨,那么就要讓
最小无畔。
于是,接下來我們的求參數(shù)目標就明確了诸衔。
參數(shù)的確定
由于肯定是非負的雕沉,我們可以改寫一下
這個式子集乔,讓它變成求
的最小值。
既然要求最小值坡椒,就需要有另外一個約束條件扰路,否則是沒辦法求的,我們來看之前總結(jié)的線性SVM分類器的公式:
由于和
是決策邊界的兩個超平面倔叼,我們從上圖中可以看出汗唱,所有的點(除了這兩個超平面經(jīng)過的點以外,經(jīng)過的點是離決策邊界最近的點)丈攒,都肯定有
和
哩罪。
我們把y引入進來,那么這兩個式子就能合到一起寫為:
注意不要和之前總結(jié)的公式中的弄混际插,那個條件是最終預(yù)測分類的公式,也就是表明只要在決策邊界的上方就可以進行分類显设,而現(xiàn)在的>=1是在已知訓練集的情況下求模型的參數(shù)框弛。
綜合以上的式子,我們可以得到求參數(shù)的基本式:
目標函數(shù)是二次的瑟枫,而約束在參數(shù)和
上是線性的,因此這是一個凸優(yōu)化問題绞蹦,不存在局部優(yōu)化的問題力奋。
求這一套公式的最小值,需要用到拉格朗日乘數(shù)法幽七,這個我也不是很明白景殷,就按照百度百科的定義往里套:
設(shè)給定二元函數(shù)z=?(x,y)和附加條件φ(x,y)=0,為尋找z=?(x,y)在附加條件下的極值點澡屡,先做拉格朗日函數(shù)
猿挚,其中λ為參數(shù)。
令F(x,y,λ)對x和y和λ的一階偏導數(shù)等于零驶鹉,即
F'x=?'x(x,y)+λφ'x(x,y)=0 [1]
F'y=?'y(x,y)+λφ'y(x,y)=0
F'λ=φ(x,y)=0
由上述方程組解出x,y及λ绩蜻,如此求得的(x,y),就是函數(shù)z=?(x,y)在附加條件φ(x,y)=0下的可能極值點室埋。
雖然我們這里的附加條件是大于等于1的办绝,不過不妨改寫一下試試伊约,則有:
其中的就是拉格朗日乘子,理論上來說孕蝉,拉格朗日乘子可以為任何值屡律。
如果約束條件是=0的話,我們就可以直接對和
求偏導數(shù)降淮,讓他們等于0超埋,就能求得參數(shù)。
但是目前條件并不是等于0的佳鳖,而是大于等于0的霍殴。
處理不等式約束一種方法就是變換成一組等式約束,根據(jù)KKT條件系吩,可以限制拉格朗日乘子飛赴来庭,把之前的約束變換為:
該約束表明,除非訓練樣本滿足方程淑玫,否則拉格朗日乘子必須為0巾腕。
結(jié)合上面展示決策邊界和超平面的圖,我們可以想到絮蒿,滿足這個方程的樣本,肯定都在決策邊界生成的兩個超平面上叁鉴。這些樣本處的拉格朗日乘子肯定夠大于0土涝,而其他樣本的拉格朗日乘子,肯定等于0幌墓,因此問題得到簡化但壮。因為參數(shù)的確定僅依賴于這些在超平面上的樣本。
這些在超平面上的樣本常侣,被稱作支持向量蜡饵,這也就是支持向量機的命名緣由。
有了以上的修改后的約束胳施,我們可以在 對
和
求偏導溯祸,并讓他們等于0.
我們已知舞肆,這個時候的和
是有滿足條件的最優(yōu)解的焦辅,把這兩個式子代入原公式,就能得到
的最小值(當然此時因為不知道拉格朗日乘子椿胯,我們是求不出來的)筷登,代入公式可得:
該函數(shù)叫做對偶拉格朗日函數(shù)。
用這個函數(shù)哩盲,就是把之前求w和b的公式變換成了求拉格朗日乘子的公式前方,同時需要注意狈醉,這個式子中是求拉格朗日對偶函數(shù)的最大化問題。
我們可以用二次規(guī)劃法或者SMO方法來求拉格朗日乘子惠险。
二次規(guī)劃算法比較通用苗傅,但是計算量比較大,SMO算法的核心就是把復(fù)雜的式子變換成比較簡易的之后莺匠,用二次規(guī)劃來計算金吗。
SMO的基本思路是:先固定之外的所有參數(shù),然后求
上的極值趣竣,由于存在約束
摇庙,如果固定了
之外的其他變量,則能求出
遥缕。
那么對偶函數(shù)里有兩個λ卫袒,我們就可以固定這兩個λ之外的參數(shù),之后求解单匣。
其中有一個λ不滿足KKT條件夕凝,則目標函數(shù)就會在迭代后減小,違背程度越大户秤,變量更新后導致的目標函數(shù)值就越大码秉。所以SMO先選取違背KKT條件最大的變量,第二個變量選擇使目標函數(shù)值見效最快的變量鸡号,使選取的兩個變量對應(yīng)樣本之間的間隔最大转砖。
然后可以變換為簡單的二次規(guī)劃問題:
找到一組λ后鲸伴,就可以用原公式求得的解府蔗,決策邊界可以表示為:
之后b可以通過求解。
因為λ通過數(shù)值計算得到汞窗,因此可能存在誤差姓赤,則b可能不唯一。通常我們可以用b的平均值作為決策邊界的參數(shù)仲吏。
例子
如圖所示不铆,這組數(shù)據(jù)集有兩個特征和一個
標簽,我們要對其進行建模分類蜘矢,可以得到有兩個拉格朗日乘子(支持向量上的)狂男,其他的均為0.
我們可以得到有:
第一個是針對
的參數(shù),以此類推品腹。
有了岖食,可以求得
有:
可以根據(jù)兩個b求平均值,得到b=7.93舞吭,因此就能得到分類的模型泡垃。
如果需要做預(yù)測析珊,把對應(yīng)點的x向量代入到模型中,求得結(jié)果為1的話蔑穴,就是方形類忠寻,其他為圓形類。
非線性支持向量機
上面討論的模型最終都會生成一條直線存和,也就是線性的模型奕剃,那么往往需要判斷非線性的如何處理呢,這里需要引入核函數(shù)的技術(shù)捐腿。
核函數(shù)
要把SVM應(yīng)用到非線性決策邊界的數(shù)據(jù)集上纵朋,就要把數(shù)據(jù)集從原來的坐標空間x變換到新的坐標空間中。
我們假定存在一個合適的函數(shù)來變化給定的數(shù)據(jù)集茄袖,那么變換之后操软,我們就可以根據(jù)
來構(gòu)建線性決策邊界(類似于換元法,回憶一下)宪祥。變換之后聂薪,線性決策邊界具有以下的形式:
根據(jù)線性SVM的參數(shù)計算公式,我們把公式里面的換成
蝗羊,即可求解藏澳。
不過這種方式往往會涉及到向量對的點積,計算比較麻煩耀找,當特征數(shù)較多時笆载,可能會造成維度災(zāi)難的問題,因此我們要引入核函數(shù)涯呻。
核函數(shù)是一種使用原屬性集計算變換后的空間中的相似度的方法,簡而言之就是腻要,我們?nèi)绻凑丈弦欢握f的算法复罐,則我們需要先計算,然后再計算參數(shù)雄家,而我們運用核函數(shù)效诅,可以直接計算\boldsymbol{x}就可以達到變換屬性集的目的。
我們令趟济,這樣就可以把映射的函數(shù)變成了原屬性集的計算乱投。
就是核函數(shù)。
但是這個一般我們是不知道的顷编,因此我們要找尋幾種通用的函數(shù)戚炫,讓他們可以實現(xiàn)
的功能,以便模擬非線性的決策邊界媳纬。
這里我們引入一個Mercer定理双肤,所有的核函數(shù)都必須滿足Mercer定理施掏。
Merver定理
任何半正定的函數(shù)都可以作為核函數(shù)。所謂半正定的函數(shù)f(xi,xj)茅糜,是指擁有訓練數(shù)據(jù)集合(x1,x2,...xn)七芭,我們定義一個矩陣的元素aij = f(xi,xj),這個矩陣式n*n的蔑赘,如果這個矩陣是半正定的狸驳,那么f(xi,xj)就稱為半正定的函數(shù)。這個mercer定理是核函數(shù)必要條件.
通常有如下幾種核函數(shù):
應(yīng)用的時候缩赛,我們直接把核函數(shù)作為就可以了耙箍,也就是用代替。
另外需要注意峦筒,類似于高斯核函數(shù)這種帶參數(shù)的函數(shù)究西,需要調(diào)整參數(shù)來滿足不同的決策邊界形狀。
我們也可以通過核函數(shù)的組合來形成新的核函數(shù):
- 如果
為核函數(shù)物喷,那么對于任意正數(shù) *
卤材,有線性組合
也是核函數(shù)。
- 如果
為核函數(shù)峦失,那么他們的直積也是核函數(shù)扇丛。
- 如果
為核函數(shù),則有任意函數(shù)
也為核函數(shù)尉辑。
軟邊緣
我們直到一般算法都要防止過擬合帆精,防止噪聲帶來的模型泛化能力下降,那么SVM的防止過擬合方法就是軟邊緣隧魄。
如圖卓练,可以看到,圖中有一些+類跑到了決策邊界的下方购啄,而有一些-類跑到了決策邊界的上方襟企,很明顯這些類是不滿足之前我們確定的約束的,在軟邊緣中狮含,我們允許這種情況發(fā)生顽悼。同時引入一個松弛變量來表明軟邊緣的幅度,則有:
其中就是松弛變量几迄。
很顯然蔚龙,這個變量的意義就是把下側(cè)的超平面向上移動,上側(cè)的向下移動映胁,也就是說代入了誤差估計木羹。
當然,不可能無限制的增加屿愚,那樣的話可能會包括太多錯誤樣本汇跨,我們可以把最開始的目標函數(shù)改寫务荆,不求的最小值,而是改寫成如下的式子:穷遂,其中C和k是指定的參數(shù)函匕,表示對誤分訓練實例的懲罰,一般來說蚪黑,k=1盅惜。
當C為無窮大時,公式迫使所有樣本滿足約束忌穿,而當C取有限值時抒寂,則允許部分樣本不滿足約束。
根據(jù)該公式掠剑,則我們可以改寫拉格朗日函數(shù)為:
其中屈芜,前面兩項是需要最小化的目標函數(shù),第三項表示與松弛變量相關(guān)的不等式約束朴译,最后一項是要求的值非負的結(jié)果井佑。
其中均大于等于0,是拉格朗日乘子眠寿。
此外躬翁,根據(jù)KKT條件,可以變換約束如下:
注意盯拱,上述三個式子中的是非零的盒发,當且僅當訓練樣本位于直線
上或者
。另外對于誤分類的訓練樣本狡逢,
都為0.
我們按照正常優(yōu)化的算法宁舰,對,
,
求偏導數(shù),可以得到參數(shù):
代入原公式奢浑,可以得到只包括拉格朗日乘子的對偶拉格朗日函數(shù)明吩。
這個式子看上去跟不加軟邊緣的對偶函數(shù)是一樣的,但是約束是不同的殷费。
軟邊緣的對偶函數(shù)約束為
之后就可以用二次規(guī)劃或者SOM求參數(shù)值了,從而得到模型低葫。
這就是帶軟邊緣的SVM详羡。
多分類
以上提到的都是二元分類的辦法,那么多分類可以參考常用的多分類處理嘿悬,用一對一方法实柠,如果有多分類問題,我們可以分解為K(K-1)/2個二類分類器善涨,每一個分類器用來區(qū)分一對類窒盐。(注意這里的y都是單獨的類草则,不是一堆類別的集合)
當為構(gòu)建分類器時,其他不屬于這兩類的點都被忽略掉蟹漓。
之后針對需要預(yù)測分類的樣本炕横,我們用不同的分類器進行分類,最后進行投票葡粒,得到結(jié)果份殿。
以上就是SVM(用于分類的支持向量機)的內(nèi)容,最后看看該算法的特點:
特征
- SVM是凸優(yōu)化問題嗽交,不存在局部最優(yōu)卿嘲,所以性能比較好。
- SVM算法中夫壁,需要制定核函數(shù)類型拾枣,防止過擬合的話我們還需要一個C作為代價函數(shù)。
- 如果數(shù)據(jù)中存在分類的屬性值(離散化)盒让,可以考慮引入啞變量梅肤,將每個屬性值二元化。