序

SVM的面試題目相對(duì)有章可循玛臂，本次記錄一下常見(jiàn)的幾個(gè)面試題

一句話(huà)介紹SVM

SVM是一種二分類(lèi)模型，他的基本模型是定義在特征空間上的間隔最大的線(xiàn)性分類(lèi)器辕近，間隔大使它有別于普通的感知機(jī)韵吨，通過(guò)核技巧隱式的在輸入空間直接求解映射空間中特征向量的內(nèi)積，使其成為一個(gè)非線(xiàn)性分類(lèi)器移宅。SVM的學(xué)習(xí)策略是間隔最大化归粉，可形式化為一個(gè)求解凸二次規(guī)劃問(wèn)題。

SVM中的幾個(gè)核心概念

1 確定超平面及函數(shù)間隔

由空間上的平面公式確定超平面 wx+b = 0漏峰，且 |wx+b| 表示點(diǎn) x 到平面上的距離糠悼。正類(lèi)負(fù)例位于分割平面兩側(cè)，因此y(wx+b) 可同時(shí)表示分類(lèi)正確性以及距離確信度浅乔。這也就是函數(shù)間隔倔喂，其被定義為訓(xùn)練集中所有點(diǎn)到超平面距離的最小值。

2 幾何間隔

由于成比例地縮放w和b會(huì)使得 |wx+b| 跟著成比例縮放靖苇，因此席噩，需要對(duì)法向量w加上約束，使得間隔是確定的贤壁，也就是函數(shù)間隔整體除以 ||w||悼枢，也就得到了幾何間隔

3 間隔最大化（硬間隔）

分為硬間隔最大和軟間隔最大
SVM的基本思想就是求解可以正確劃分?jǐn)?shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面，其原因是線(xiàn)性可分超平面有無(wú)數(shù)個(gè)芯砸，但是間隔最大超平面是唯一的萧芙。

間隔最大化的意思就是以充分大的確信度對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類(lèi)，也就是說(shuō)假丧，不僅將正負(fù)實(shí)例分開(kāi)双揪，同時(shí)對(duì)最難分的實(shí)例點(diǎn)（距離超平面最近的點(diǎn)）也有足夠大的確信度將其分離。
此處推出約束優(yōu)化問(wèn)題的原始形式（見(jiàn)上一篇博客）

4 支持向量

與超平面最近的點(diǎn)被稱(chēng)為支持向量包帚，也就是使得原始問(wèn)題約束項(xiàng)成立的點(diǎn)渔期。
實(shí)際上離超平面很遠(yuǎn)的點(diǎn)已經(jīng)被正確分類(lèi)，我們讓它離超平面更遠(yuǎn)并沒(méi)有意義渴邦。反而我們最關(guān)心是那些離超平面很近的點(diǎn)疯趟，這些點(diǎn)很容易被誤分類(lèi)。如果我們可以讓離超平面比較近的點(diǎn)盡可能的遠(yuǎn)離超平面谋梭，那么我們的分類(lèi)效果會(huì)好有一些

5 核函數(shù)

注意信峻，核函數(shù)本質(zhì)不是將特征映射到高維空間，而是找到一種直接在低位空間對(duì)高維空間中向量做點(diǎn)積運(yùn)算的簡(jiǎn)便方法瓮床。
其證明以及案例可參考李航-統(tǒng)計(jì)學(xué)習(xí)方法 P117

6 為何將原始問(wèn)題轉(zhuǎn)為對(duì)偶問(wèn)題

總是說(shuō)對(duì)偶問(wèn)題更容易求解盹舞，道理在哪呢产镐？

之所以說(shuō)換為對(duì)偶問(wèn)題更容易求解，其原因在于降低了算法的計(jì)算復(fù)雜度踢步。在原問(wèn)題下癣亚，算法的復(fù)雜度與樣本維度相關(guān)，即等于權(quán)重w的維度获印，而在對(duì)偶問(wèn)題下述雾，算法復(fù)雜度與樣本數(shù)量有關(guān)，即為拉格朗日算子的個(gè)數(shù)兼丰。
因此玻孟，如果你是做線(xiàn)性分類(lèi)，且樣本維度低于樣本數(shù)量的話(huà)地粪，在原問(wèn)題下求解就好了取募，Liblinear之類(lèi)的線(xiàn)性SVM默認(rèn)都是這樣做的琐谤；但如果你是做非線(xiàn)性分類(lèi)蟆技，那就會(huì)涉及到升維（比如使用高斯核做核函數(shù)，其實(shí)是將樣本升到無(wú)窮維）斗忌，升維后的樣本維度往往會(huì)遠(yuǎn)大于樣本數(shù)量质礼，此時(shí)顯然在對(duì)偶問(wèn)題下求解會(huì)更好。

另一方面织阳，我們有分析過(guò)眶蕉，只有在支持向量上的樣本對(duì)應(yīng)的拉格朗日算子λ才大于0，其余的λ都是=0唧躲，而轉(zhuǎn)為對(duì)偶問(wèn)題的計(jì)算對(duì)象僅有λ造挽，所以大大降低了計(jì)算復(fù)雜度。

為什么SVM對(duì)缺失值敏感

SVM與LR的聯(lián)系

1）損失函數(shù)
    SVM是hinge損失
    LR是log損失
2）輸出
    LR給出了后驗(yàn)概率
    SVM只給出0或1弄痹，也就是屬于哪一個(gè)類(lèi)別
3）異常值
    LR對(duì)異常值敏感饭入；SVM相對(duì)不敏感，泛化能力好
4）訓(xùn)練集大小
    較小的訓(xùn)練集更適合SVM肛真。
    SVM的參數(shù)優(yōu)化方法是先轉(zhuǎn)為對(duì)偶問(wèn)題再使用SMO算法谐丢，最壞情況下的時(shí)間復(fù)雜度是O(n^2)，并不適合在大規(guī)模數(shù)據(jù)集上做分類(lèi)蚓让。
    另外乾忱，在使用核技巧，例如RBF時(shí)历极，特征會(huì)升高至無(wú)限維窄瘟，因此其計(jì)算量也變得很大。
5）LR用到所有的樣本點(diǎn)來(lái)尋找分割面趟卸；SVM只用到少數(shù)靠近支持面的幾個(gè)點(diǎn)蹄葱。
6）非線(xiàn)性處理方式
    LR靠特征組合高次項(xiàng)纲酗；SVM也可以組合，但更多使用核函數(shù)
7）LR較為簡(jiǎn)單，可以適用于大規(guī)模線(xiàn)性分類(lèi)；SVM較復(fù)雜灶挟，但是理論支撐完備家妆，
8）SVM只考慮支持向量

SVM優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：
    1、可以有效解決高維特征的分類(lèi)和回歸問(wèn)題
    2洗鸵、無(wú)需依賴(lài)全體樣本，只依賴(lài)支持向量
    3、有大量的核技巧可以使用鸠补，從而可以應(yīng)對(duì)線(xiàn)性不可分
    4、樣本量中等偏小照樣有較好的效果
缺點(diǎn)：
    1嘀掸、如果特征維度遠(yuǎn)大于樣本個(gè)數(shù)紫岩，SVM表現(xiàn)一般
    2、SVM在樣本巨大且使用核函數(shù)時(shí)計(jì)算量很大
    3睬塌、非線(xiàn)性數(shù)據(jù)的核函數(shù)選擇依舊沒(méi)有標(biāo)準(zhǔn)
    4泉蝌、SVM對(duì)缺失數(shù)據(jù)敏感
    5、特征的多樣性導(dǎo)致很少使用svm揩晴，因?yàn)?svm 本質(zhì)上是屬于一個(gè)幾何模型勋陪，這個(gè)模型需要去定義 instance 之間的 kernel 或者 similarity（線(xiàn)性svm中的內(nèi)積），而我們無(wú)法預(yù)先設(shè)定一個(gè)很好的similarity硫兰。這樣的數(shù)學(xué)模型使得 svm 更適合去處理 “同性質(zhì)”的特征

為什么SVM的分割超平面方程為 wx + b = 0诅愚？

1）這個(gè)超平面的公式是假設(shè)。
2）其中w和x均為向量劫映，b是一個(gè)實(shí)數(shù)违孝。
3）在三維空間中一個(gè)法向量w，一個(gè)位移b能夠唯一確定一個(gè)平面泳赋，因此作出如上公式假設(shè)雌桑。
而x向量可以看作是原點(diǎn)到平面上任一點(diǎn)的連線(xiàn)向量，而w就是原點(diǎn)垂直于平面的那個(gè)向量摹蘑，因此筹燕，w的大小就是原點(diǎn)到超平面的最短距離。
4）為什么要設(shè)其=0衅鹿？
為了方便撒踪，假設(shè)兩類(lèi)樣本點(diǎn)的邊界到超平面的距離是相等的，因此就設(shè)為0大渤，這樣的話(huà)制妄，wx + b > 0就表示樣本點(diǎn)在分割平面上方，wx + b < 0的話(huà)就代表在其下方泵三。

超平面方程與 ax+b=y的直線(xiàn)方程有何聯(lián)系耕捞？

幾何角度解釋如何尋找最優(yōu)超平面

1）給出一個(gè)中間超平面H0衔掸，并且其滿(mǎn)足wx - b = 0，給出另外兩個(gè)超平面H1：wx - b = m俺抽；H1：wx - b = -m敞映，設(shè)定為正負(fù)m的目的是為了讓H1到H0的距離 = H2到H0的距離磷斧。
2）w和b都是可以進(jìn)行同步縮放的振愿，因此我們?yōu)榱撕?jiǎn)化問(wèn)題，將m縮放為1冕末，那么兩個(gè)超平面的方程為：

3）上述兩個(gè)超平面的中間是沒(méi)有數(shù)據(jù)的仅炊，這句話(huà)是對(duì)超平面的一個(gè)約束桐经，轉(zhuǎn)化為數(shù)學(xué)描述就是：

上圖中其實(shí)可以看出宿百，如果X0距離另外一個(gè)超平面距離為m的話(huà)，那么豈不是X0+m可以求得另一個(gè)超平面上的點(diǎn)逛漫。
但是X0是可以看作一個(gè)向量，而m只是一個(gè)標(biāo)量掏熬，因此需要將m轉(zhuǎn)化為標(biāo)量，換句話(huà)說(shuō)秒梅，也就是想得到一個(gè)垂直于H1的且長(zhǎng)度為m的一個(gè)向量旗芬。
其實(shí)對(duì)于H1來(lái)說(shuō)，w就是其上的法向量那么：

經(jīng)過(guò)上面式子的推導(dǎo)就將m的求法得到了。

SVM參數(shù)C的選擇

SVM核函數(shù)的選擇

轉(zhuǎn)載注明：http://www.reibang.com/p/fa02098bc220