上一篇講了線性可分的SVM推導(dǎo)，現(xiàn)在講一講基本線性可分的情形，后面還會(huì)介紹多分類的使用以及核函數(shù)的使用。

outlier 的處理

給定數(shù)據(jù)集? ，當(dāng)樣本數(shù)據(jù)大部分為線性可分的，存在少量異常值使得數(shù)據(jù)線性不可分，或者導(dǎo)致分離超平面被擠壓，可以通過一些方法仍然按照線性可分的方式處理，異常值的情況如下圖所示：

以上情況意味著某些樣本點(diǎn)的函數(shù)間隔并不滿足大于 1 的要求。為了解決這個(gè)問題，為每個(gè)樣本引入一個(gè)松弛變量, 使得函數(shù)間隔可以小于 1 ，即滿足??,這里顯然??不能任意大，因?yàn)槟菚?huì)導(dǎo)致任意樣本點(diǎn)都滿足要求，所以要把優(yōu)化目標(biāo)改成如下的形式：

上面將不等式約束都已經(jīng)化成了的形式了，為方便使用拉格朗日乘子法與KKT條件。

這里??叫做懲罰參數(shù)，上述的不等式約束記做??的形式，同樣通過對(duì)偶的形式求解，首先構(gòu)造拉格朗日函數(shù)：

拉格朗日函數(shù)中的乘子?， 且???，很明顯的有：

因此原始問題轉(zhuǎn)化為：

對(duì)于上述問題應(yīng)用對(duì)偶可得：

接下來求解對(duì)偶問題，對(duì)于極小部分的參數(shù)??求導(dǎo)：

將以上結(jié)果帶入對(duì)偶問題，極小部分便得到一個(gè)關(guān)于??的函數(shù)：

注意這里根據(jù)??與??消去了?。

使原始問題滿足KKT條件，則原問題與對(duì)偶問題具備強(qiáng)對(duì)偶性。（其實(shí)在這里可以通過Slater條件成立推出強(qiáng)對(duì)偶性，再?gòu)膹?qiáng)對(duì)偶性推出原問題滿足KKT條件，Slater條件為兩個(gè)，1是原問題為凸優(yōu)化問題，這個(gè)顯而易見。2是原問題存在嚴(yán)格滿足不等式約束的解，這個(gè)也是顯而易見的，對(duì)于所有不是支持向量的點(diǎn)，都是嚴(yán)格滿足這個(gè)條件的。故Slater條件是成立的。）

聯(lián)立KKT條件與對(duì)偶問題約束最后可求解得出

首先由? KKT 條件 (1) 可得：

根據(jù) KKT 條件(3) (4) (6) (9)可知若?，則??,且存在??，使得：

因此便可求得??：

至此，可以總結(jié)出帶有異常值的線性可分 SVM 的算法1.3：

Algorithm 1.3

下圖中實(shí)線為分離超平面，虛線為間隔邊界，且有間隔邊界與分離超平面的函數(shù)距離為1，幾何距離為?。在線性不可分的情況下，求解得到??的分量??對(duì)應(yīng)的樣本實(shí)例??中的??稱為支持向量，這時(shí)的支持向量要比線性可分復(fù)雜一些，如下圖的點(diǎn)，以下支持向量點(diǎn)到間隔邊界的幾何距離均已標(biāo)注出為?。這個(gè)幾何距離是這樣計(jì)算的，點(diǎn)? 到分離超平面的函數(shù)距離為?, 而分離超平面與間隔邊界的函數(shù)距離為 1 ，所以點(diǎn)? 到間隔邊界的距離為??,幾何距離只需除以??即可得到結(jié)果。

可見這時(shí)候的支持向量或者分布在間隔邊界上，或者在間隔邊界與超平面之間，或者在分離超平面誤分的一側(cè)。 根據(jù) KKT 條件可以得出一些很有意思的結(jié)論，當(dāng)??時(shí)，根據(jù) KKT 條件 (3) 可得?，即? ，又由于??可得??，根據(jù) KKT 條件 (4) 可得??，所以當(dāng)??時(shí)，可得 ，這時(shí)樣本便為支持向量，且落在間隔邊界上；當(dāng)??時(shí)且??，這時(shí)便為分類正確的且落在間隔邊界之后的點(diǎn)，至于? 的情況，根據(jù)??的不同取值，可分為不同的情況，總結(jié)起來便有：

至此，帶有異常值的非線性可分的情況也解決了，但是還需要注意的是數(shù)據(jù)集是完全非線性可分的。這時(shí)便需要引入核方法了。核方法并不是 SVM 的專利，其可以解決一系列機(jī)器學(xué)習(xí)問題。

---

多分類

至于 K 分類問題 (K>2) ,最簡(jiǎn)單的方式便是?one-vs-all?的方法，如下圖所示，該方法共訓(xùn)練 K 個(gè)分類器，對(duì)于待分類樣本點(diǎn)，分別使用這 K 個(gè)分類器進(jìn)行分類，對(duì)于樣本??分類的計(jì)算如下：?，若只有一個(gè) +1 出現(xiàn)，則其為樣本對(duì)應(yīng)類別 k ；但實(shí)際情況下構(gòu)造的決策函數(shù)總是有誤差的，此時(shí)輸出不只一個(gè) +1 (不只一類聲稱它屬于自己)，或者沒有一個(gè)輸出為 +1 (即沒有一個(gè)類聲稱它屬于自己)，這時(shí)比較則比較??輸出值，最大者對(duì)應(yīng)類別為樣本 ?的類別 k 。

或者采用 LIBSVM 中?one-vs-one?的方法，其做法是在任意兩類樣本之間設(shè)計(jì)一個(gè)SVM，因此 k 個(gè)類別的樣本就需要設(shè)計(jì)??個(gè)SVM。當(dāng)對(duì)一個(gè)未知樣本進(jìn)行分類時(shí)，最后得票最多的類別即為該未知樣本的類別。比如說 A,B,C 三類。在訓(xùn)練的時(shí)候針對(duì) (A,B) (A,C) (B,C) 所對(duì)應(yīng)的樣本作為訓(xùn)練集，然后得到三個(gè)模型，在測(cè)試的時(shí)候，對(duì)應(yīng)的分別對(duì)三個(gè)模型進(jìn)行測(cè)試，然后采取投票形式得到最后的結(jié)果，如下圖所示：

再就是直接使用 Hinge Loss 進(jìn)行多分類了，這個(gè)接下來也會(huì)詳細(xì)介紹。

參考文章：

致謝ooon大神，從他的博文中學(xué)到了很多東西！

支持向量機(jī)SVM

?

?

總結(jié)

以上是生活随笔為你收集整理的【机器学习】SVM基本线性可分与多分类的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。