【ML-QA-1】支持向量機SVM中常見的面試問題QA

image

以下只是將知識點QA化音念，不要為了面試硬背答案，還是先得好好看書

Q-List：

簡要介紹一下SVM
支持向量機包含幾種模型
什么是支持向量
SVM為什么采用間隔最大化
SVM的參數(shù)（C朱浴，ξ烈菌， $\gamma$ ）
Linear SVM和LR的異同
SVM和感知機的區(qū)別
感知機的損失函數(shù)
SVM的損失函數(shù)
SVM怎么處理多分類
SVM可以處理回歸問題嗎
為什么把原問題轉(zhuǎn)換為對偶問題
為什么求解對偶問題更加高效
alpha系數(shù)有多少個
核函數(shù)，種類、如何選擇
高斯核為什么會把原始維度映射到無窮多維
核函數(shù)的意義是什么
什么樣的函數(shù)可以作為一個有效的核函數(shù)
大規(guī)模數(shù)據(jù)能用SVM嗎

QA：

簡要介紹一下SVM

支持向量機SVM是一種二類分類模型口芍。它的基本模型是定義在特征空間中的間隔最大的線性分類器。學(xué)習(xí)的目標(biāo)就是在特征空間內(nèi)找到一個分離超平面雇卷，能夠?qū)嵗值讲煌念悺?/p>

(從分類平面阶界，到求兩類間的最大間隔虹钮，到轉(zhuǎn)化為求間隔分之一，等優(yōu)化問題膘融，然后就是優(yōu)化問題的解決辦法芙粱，首先是用拉格拉日乘子把約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化，對各個變量求導(dǎo)令其為零氧映，得到的式子帶入拉格朗日式子從而轉(zhuǎn)化為對偶問題春畔，最后再利用SMO（序列最小優(yōu)化）來解決這個對偶問題。)

支持向量機包含幾種模型

當(dāng)訓(xùn)練樣本線性可分時岛都，通過硬間隔最大化律姨，學(xué)習(xí)一個線性分類器，即線性可分支持向量機臼疫。
當(dāng)訓(xùn)練數(shù)據(jù)近似線性可分時择份，引入松弛變量，通過軟間隔最大化烫堤，學(xué)習(xí)一個線性分類器荣赶，即線性支持向量機。
當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時鸽斟，通過使用核技巧及軟間隔最大化拔创，學(xué)習(xí)非線性支持向量機。

什么是支持向量

在線性可分的情況下富蓄，訓(xùn)練數(shù)據(jù)集的樣本點中與分離超平面距離最近的樣本點的實例稱為支持向量（support vector）剩燥。

SVM為什么采用間隔最大化

當(dāng)訓(xùn)練數(shù)據(jù)線性可分時，存在無窮個分離超平面可以將兩類數(shù)據(jù)正確分開立倍。感知機或神經(jīng)網(wǎng)絡(luò)等利用誤分類最小策略灭红，求得分離超平面，不過此時的解有無窮多個口注。線性可分支持向量機利用間隔最大化求得最優(yōu)分離超平面变擒，這時，解是唯一的疆导。另一方面，此時的分隔超平面所產(chǎn)生的分類結(jié)果是最魯棒的葛躏，對未知實例的泛化能力最強澈段。

SVM中的參數(shù) （C，ξ舰攒，γ)

線性不可分意味著某些樣本點不能滿足函數(shù)間隔大于等于1的約束條件败富，為了解決這個問題，對每個樣本點引入一個松弛變量 $\xi_i\ge0$

C是懲罰系數(shù)摩窃，即對誤差的寬容度兽叮。C越大芬骄，說明越不能容忍出現(xiàn)誤差，容易過擬合鹦聪。C越小账阻，容易欠擬合。C過大或過小泽本，泛化能力變差淘太。

C理解為調(diào)節(jié)優(yōu)化方向中兩個指標(biāo)（間隔大小，分類準(zhǔn)確度）偏好的權(quán)重规丽。當(dāng)C趨于無窮大時蒲牧，這個問題也就是不允許出現(xiàn)分類誤差的樣本存在，那這就是一個hard-margin SVM問題（過擬合）赌莺。當(dāng)C趨于0時冰抢，我們不再關(guān)注分類是否正確，只要求間隔越大越好艘狭，那么我們將無法得到有意義的解且算法不會收斂（欠擬合）挎扰。

$\gamma$ 是選擇RBF函數(shù)作為kernel后，該函數(shù)自帶的一個參數(shù)缓升。隱含地決定了數(shù)據(jù)映射到新的特征空間后的分布鼓鲁， $\gamma$ 越大，支持向量越少港谊， $\gamma$ 值越小骇吭，支持向量越多。支持向量的個數(shù)影響訓(xùn)練與預(yù)測的速度歧寺。

這里面需要引入一下老師們的討論燥狰，需要考慮到RBF核的特點，特征空間分布等方面斜筐。討論

Linear SVM和LR的異同

相同點：
LR和SVM都是分類算法龙致。
如果不考慮核函數(shù)，LR和SVM都是線性分類算法顷链，即分類決策面都是線性的目代。
LR和SVM都是監(jiān)督學(xué)習(xí)算法。
不同點
損失函數(shù)不同嗤练，LR是對數(shù)損失logloss，SVM是合頁損失hinge loss霜大。
LR受所有數(shù)據(jù)影響曙强，而SVM只考慮局部的邊界線附近的點（支持向量）。

SVM和感知機的區(qū)別

相同點
都是屬于監(jiān)督學(xué)習(xí)的一種分類器（決策函數(shù)）臀防。
不同點
感知機追求最大程度正確劃分袱衷，最小化錯誤致燥，很容易造成過擬合嫌蚤。支持向量機追求大致正確分類的同時，一定程度上避免過擬合箱蝠。
感知機使用的學(xué)習(xí)策略是梯度下降法；而SVM采用的是由不等式約束條件構(gòu)造拉格朗日函數(shù)间校，然后求偏導(dǎo)令其為0，根據(jù)一大堆的ai參數(shù)（一直迭代到滿足kkt條件為止滓彰，kkt條件是用來滿足不等式約束下的拉格朗日乘子法的泛化）饼暑，來最終求得w和b彰居。
SVM分類超平面的解是唯一的畦徘，要滿足間隔最大化井辆。感知機的解不唯一杯缺，沒有間隔最大化的約束條件萍肆，滿足分開數(shù)據(jù)點的分界面都是可以的。
感知機屬于線性分類模型亲铡，SVM包括核技巧，實質(zhì)是非線性分類器锭硼。

感知機的損失函數(shù)

感知機的損失函數(shù)是所有誤分類點到超平面的總距離: $L(w,b)=-\sum\limits_{x_i\in{M}}y_i(w*x_i+b)$

SVM的損失函數(shù)

SVM除了原始最優(yōu)化問題，還有另外一種解釋就是最優(yōu)化以下目標(biāo)函數(shù)：
$\sum\limits_{i=1}^{N}[1-y_i(w*x_i+b)]_++\lambda\left\|w\right\|^2$
其中第一項是經(jīng)驗損失Hinge Loss暑始，合頁損失函數(shù)。
$L(y(w*x+b))={[1-y(w*x+b)]}_+$
下標(biāo)“+”表示取正值的函數(shù)嗤朴，類似ReLu函數(shù)股缸。那么當(dāng)樣本點被正確分類且函數(shù)間隔（確信度） $y_i(w*x_i+b)>1$ 時歧杏，損失為0陨献，否則損失是 $1-y_i(w*x_i+b)$
目標(biāo)函數(shù)第二項是系數(shù)為 $\lambda$ 的w的L2范數(shù)，正則化項沮协， $\lambda$ 是可調(diào)節(jié)的超參數(shù)龄捡。

SVM怎么處理多分類

直接法
直接修改目標(biāo)函數(shù)，將多個分類面的參數(shù)求解合并到一個最優(yōu)化問題中慷暂。計算復(fù)雜度高聘殖，實現(xiàn)起來比較麻煩，適合于小型問題行瑞。
間接法
- 一對多法（one-vs-rest, OVR SVMs）奸腺，一次把某類樣本歸為一類，其他的為另一類
- 一對一法血久，任意兩類樣本設(shè)計一個SVM

SVM可以處理回歸問題嗎

對于回歸問題突照，優(yōu)化目標(biāo)函數(shù)和分類問題一致，還是 $min\frac{1}{2}\left\|w\right\|^2$ 氧吐，但是約束條件不同讹蘑，看下圖

image

藍色線是分類超平面，藍色區(qū)域邊界就是間隔邊界筑舅，上面的點就是支持向量座慰，因此藍色區(qū)域內(nèi)的點是沒有損失的，但是外面的點是由損失的翠拣，損失大小為紅色線的長度版仔，這個地方就很像線性回歸的誤差了。
因此，SVM回歸模型的損失函數(shù)度量為：

image

為什么把原問題轉(zhuǎn)換為對偶問題

對偶問題是凸優(yōu)化問題
對偶問題將原始問題中的約束轉(zhuǎn)為了對偶問題中的等式約束
方便核函數(shù)的引入
求解更高效蛮粮，改變了問題的復(fù)雜度背桐，由求特征向量w轉(zhuǎn)化為求比例系數(shù)a，在原始問題下蝉揍，求解的復(fù)雜度與樣本的維度有關(guān)，即w的維度畦娄。在對偶問題下又沾，只與樣本數(shù)量有關(guān)

為什么求解對偶問題更加高效

因為只用求解alpha系數(shù)，而alpha系數(shù)只有支持向量才非0熙卡，其他全部為0

alpha系數(shù)有多少個

樣本點的個數(shù)

核函數(shù)杖刷，種類、如何選擇

線性核
多項式核
高斯核（RBF核函數(shù)）

如果特征的數(shù)量大到和樣本數(shù)量差不多驳癌，選用線性核SVM或LR
如果特征的數(shù)量少滑燃，樣本數(shù)量正常，選用RBF核函數(shù)
如果特征很少颓鲜，樣本很多表窘，最好是手動加一些特征，轉(zhuǎn)為第一個情況

高斯核為什么會把原始維度映射到無窮多維

從泰勒展開式的角度來解釋
參考

核函數(shù)的意義是什么

核函數(shù)的真正意義是做到了沒有真正映射到高維空間卻達到了映射的作用甜滨，即減少了大量的映射計算乐严。

什么樣的函數(shù)可以作為一個有效的核函數(shù)

只要滿足Mercer定理。

大規(guī)模數(shù)據(jù)能用SVM嗎

SVM的空間消耗主要是在存儲訓(xùn)練樣本和核矩陣衣摩，由于SVM是借助二次規(guī)劃來求解支持向量昂验，而求解二次規(guī)劃將涉及m階矩陣的計算（m為樣本的個數(shù)），當(dāng)m數(shù)目很大時該矩陣的存儲和計算將耗費大量的及其內(nèi)存和運算時間艾扮。如果數(shù)據(jù)量很大既琴，SVM的訓(xùn)練時間就會比較長，所以SVM在大數(shù)據(jù)的使用中比較受限泡嘴。

參考

《統(tǒng)計學(xué)習(xí)方法》李航
《機器學(xué)習(xí)》周志華
https://blog.csdn.net/qq_32742009/article/details/81838152
https://blog.csdn.net/guo1988kui/article/details/80207551
http://blog.sina.com.cn/s/blog_62970c250102xfzj.html
http://blog.sina.com.cn/s/blog_6ae183910101cxbv.html