1 單刀直入，先回答有必要嗎？
最近和許多朋友交流，發(fā)現(xiàn)當(dāng)前機(jī)器學(xué)習(xí)應(yīng)聘時(shí)，手推SVM這道題已經(jīng)越來越像快速排序一樣，成為必點(diǎn)菜了。
那么，手推SVM是不是必要的呢？正反雙方各執(zhí)一詞，正方說，手推SVM才能看出應(yīng)聘者的理論基礎(chǔ)，反方說，現(xiàn)實(shí)中，SVM限于性能，應(yīng)用面很小，尤其是現(xiàn)在xgboost, lightGBM等高性能的boosting框架的盛行，更讓SVM成為了好看不好用的東西。能說清楚基礎(chǔ)原理就可以了，沒必要手推。
我的觀點(diǎn)是：如果你是應(yīng)聘者，不要思考這個(gè)問題，趕緊多推幾遍SVM，爭(zhēng)取達(dá)到閉眼也能推出來的地步，因?yàn)槟銢]有選擇，假如你跟面試官說，這個(gè)沒必要推，實(shí)際中用的不多，估計(jì)你的面試也玄了，因?yàn)槊嬖嚬俨恢滥闶钦f真的還是在為自己不會(huì)找理由。
如果你是面試官，我的建議是不要問了，至少不要推導(dǎo)SVM了，大家都是被資本剝削，你不過是找一個(gè)同事，有大把的問題可以問出應(yīng)聘者能否勝任公司的崗位，只要技術(shù)水平夠，性情相投就可以了。如果你也問，等你跳槽時(shí)，自己還是要付出精力去臨時(shí)背背那些推導(dǎo)，這叫作繭自縛。
在這里插個(gè)小曲。我第一次面試時(shí)和當(dāng)時(shí)公司的技術(shù)總監(jiān)聊了小一個(gè)小時(shí)的曾國藩，一見如故，后來我提出薪資要求，總監(jiān)說你剛從體制里面出來，不了解現(xiàn)在互聯(lián)網(wǎng)薪資行情，要的太低了，我會(huì)跟HR說在你的要求上乘以1.5的。
我覺得這才是一個(gè)技術(shù)人應(yīng)有的行為準(zhǔn)則！無產(chǎn)階級(jí)何必為難無產(chǎn)階級(jí)，只要你覺得這個(gè)人技術(shù)水平能勝任崗位，就可以了。雖然我后來沒有去那家公司，但我至今仍然從內(nèi)心感謝那位總監(jiān)。
不過客觀講，機(jī)器學(xué)習(xí)暴漲的需求面前，大家實(shí)戰(zhàn)經(jīng)驗(yàn)都有限，可用來測(cè)試面試者實(shí)際經(jīng)驗(yàn)的問題不好找，為降低招聘風(fēng)險(xiǎn)，問一下理論推導(dǎo)，也是權(quán)宜之計(jì)。
2 步步為營，怎么搞定SVM的推導(dǎo)？
那么，怎么能夠快速地，長久地記住SVM的推導(dǎo)呢？
看到身邊不少朋友采用的辦法就是一遍又一遍的抄，抄熟之后就開始自己一遍又一遍的默寫。個(gè)人覺得這樣做是必要的，但不是最重要的，最重要的是獲得intuition，即對(duì)每一步推導(dǎo)背后的意圖建立起自己的感覺，這樣就可以逐漸從背記的狀態(tài)轉(zhuǎn)移到自覺推導(dǎo)的境界。
下面，我們就嘗試盡可能簡(jiǎn)單地快速地推導(dǎo)一遍SVM，但是重點(diǎn)不是推導(dǎo)，而是試圖根據(jù)我的理解，說明每一步推導(dǎo)背后的動(dòng)機(jī)。理解清楚后，相信推導(dǎo)就是順理成章了。
3 SVM的基本思想
SVM的基本思想非常直觀。設(shè)想一個(gè)多維平面上散落著正樣本和負(fù)樣本，如果能找到一個(gè)超平面，恰好能將正負(fù)樣本分開，那么這個(gè)超平面就可以用來對(duì)樣本進(jìn)行分類。如下圖所示：
我們的目標(biāo)是找到圖中的H3。那么，很自然地，我們就會(huì)產(chǎn)生兩個(gè)問題:
1 如果這樣的超平面確實(shí)存在，那么如何找到它？
2 如果這樣的超平面不存在，那么如何找一個(gè)盡可能將正負(fù)樣本分開的超平面？
以上兩個(gè)問題就是SVM要解決的核心問題！所有關(guān)于SVM的知識(shí)都可以歸為為了解決兩個(gè)問題中的一個(gè)。
有了問題，就好比有了靶子，后面的推導(dǎo)都是沖著靶子去的，這樣就更能理解推導(dǎo)的原理了。圍繞問題去學(xué)習(xí)，是我推崇的學(xué)習(xí)方法，它的好處有二，一是更能調(diào)動(dòng)主觀能動(dòng)性，因?yàn)槟憧梢跃蛦栴}進(jìn)行很多自己的思考，二是能讓知識(shí)更加模塊化，便于完善知識(shí)結(jié)構(gòu)。
4?由易到難，先解決第一個(gè)問題
對(duì)第一個(gè)問題的解決，實(shí)際上就會(huì)得到SVM的基本型，即線性可分的SVM。這里請(qǐng)注意，第一個(gè)問題的假設(shè)是這樣的超平面是存在的，或者說，樣本是線性可分的，這一點(diǎn)需要牢記在心。要解決這個(gè)問題，我們可以進(jìn)一步細(xì)化出2個(gè)問題：
1、如何衡量一個(gè)超平面是否能將正負(fù)樣本分開
2、如何去尋找這樣的超平面
下面的推導(dǎo)基本上是按照以上三個(gè)問題的順序進(jìn)行的。
（一）從數(shù)學(xué)上表示超平面將正負(fù)樣本分開
一個(gè)超平面可以用如下的式子表示:
ω,b是超平面的參數(shù)。
一個(gè)樣本點(diǎn) 到P(xi,yi) 超平面的幾何距離(注意:這里是距離而非間隔)為:
理解這個(gè)公式需要回憶一下線性代數(shù)知識(shí)，當(dāng)然，你也可以直接承認(rèn)這個(gè)公式，接受它就可以了。
如果你還是無法接受，歡迎到我的語雀上看本文的詳細(xì)版本，那里有簡(jiǎn)單的推導(dǎo)。地址是：
https://www.yuque.com/liwenju/kadtqt/hmmeha
若該超平面能將正負(fù)樣本分開，也就是正負(fù)樣本完全被超平面隔離開，該情況從數(shù)學(xué)的角度看，就等同于:
對(duì)任一個(gè)樣本P(xi,yi)，都有
這里的distance相比上面的幾何距離，最大區(qū)別是它是有正負(fù)號(hào)的，稱為幾何間隔。幾何間隔就是帶符號(hào)的幾何距離，就是這么簡(jiǎn)單。為什么這樣就表示超平面正確區(qū)分了樣本集呢？我們來具體分析下。
對(duì)于所有的正樣本，yi=1，distance(xi,yi)大于0意味著
這意味著xi在超平面正的一側(cè)，也就是在法向量ω指向的一側(cè)
同理，對(duì)所有的負(fù)樣本，yi=-1，也有
這意味著負(fù)樣本都在超平面與法向量ω反向的一側(cè)。
實(shí)際上若超平面對(duì)任一樣本滿足distance(xi,yi)<0，也同樣可以證明超平面將正負(fù)樣本分開了。不過，上面的表示并沒有失去一般性，因?yàn)樗^的正負(fù)樣本不過是我們的標(biāo)記而已。我們此時(shí)完全可以將正的標(biāo)記為負(fù)的，將負(fù)的標(biāo)記為正的，這樣，能將正負(fù)樣本分開的超平面，對(duì)任意一個(gè)樣本，就重新滿足了distance(xi,yi)>0這一條件。
問題解決。
（二）將數(shù)學(xué)表示轉(zhuǎn)化為最優(yōu)化問題
上面，我們已經(jīng)得到結(jié)論:將正負(fù)樣本分開的超平面等價(jià)于:
對(duì)任一樣本(xi,yi)，均有distance(xi,yi)>0
顯然，這樣的超平面如果存在，那一定會(huì)有無數(shù)多個(gè)，也就是說，如果一個(gè)超平面將正負(fù)樣本分開了，我們只要將這個(gè)超平面進(jìn)行極微小的旋轉(zhuǎn)，那么，旋轉(zhuǎn)得到的超平面仍然可以將正負(fù)樣本分開。所以，我們不能滿足于找到一個(gè)將正負(fù)樣本分開的超平面，而是要尋找其中最好的那個(gè)。我們希望找到的超平面，不僅能將樣本集分開，而且分得越開越好！
那么問題來了，如何度量超平面將樣本集分開的程度？很簡(jiǎn)單，對(duì)于一個(gè)特定的超平面，對(duì)所有的樣本，最小的distance越大，表示它將該樣本集分得越開。據(jù)此，我們可以將問題轉(zhuǎn)化成一個(gè)最優(yōu)化的問題，即尋找能將樣本集分得最開的超平面。
用數(shù)學(xué)表示就是：
（三）求解上面的最優(yōu)化問題
我們解決一個(gè)問題，有一類思路就是對(duì)問題進(jìn)行轉(zhuǎn)換，不停地轉(zhuǎn)換，直到轉(zhuǎn)換成一個(gè)熟悉的，已有解決方案的問題。為了求解上面的最優(yōu)化問題，我們需要對(duì)上面的問題進(jìn)一步進(jìn)行轉(zhuǎn)換。所以，讓我們繼續(xù)轉(zhuǎn)換上面的問題吧。
這里我們先要區(qū)分開超平面本身和超平面的表示ω,b。對(duì)一個(gè)超平面，我們肯定能找到一對(duì)ω,b來從數(shù)學(xué)上表示它，但是，當(dāng)我們等倍數(shù)縮放ω,b時(shí)，縮放后的新的ωn,bn仍然表示原來的超平面。
假設(shè)對(duì)某一個(gè)特定的超平面ω,b，我們已經(jīng)找到了使得里面的min取得最小值的的(xj，yj)，其最小值為
按道理，我們現(xiàn)在應(yīng)該進(jìn)行外層的求最大化過程了。但是，對(duì)不同的超平面，里面的min所對(duì)應(yīng)的xj, yj是各不相同的，這給我們帶來麻煩。這個(gè)怎么破？方法是這樣的。我們看最小值的分子部分
顯然它的值是大于0的，因?yàn)槲覀兊某霭l(fā)點(diǎn)就是從將正負(fù)樣本分開的超平面中選取分得最開的那個(gè)超平面，這是我們問題的前提假設(shè)。
既然它是大于0的，那么，對(duì)這個(gè)特定的超平面，我們一定能通過等倍數(shù)縮放ω,b使得
這樣一來，里面的min就變成了
這就是說，對(duì)所有的超平面ω,b，只要我們都用它們某個(gè)特定的表示，即某個(gè)特定的ω,b值，里面的min就總是
這個(gè)特定的表示就是使得對(duì)取得最小值的yj有
那么對(duì)于其他的樣本點(diǎn)xi,yi，顯然就有
因?yàn)閤j,yj作為取得最小值的點(diǎn)，其值為1，其他的樣本點(diǎn)自然是大于等于1了。
被稱作樣本點(diǎn)對(duì)超平面的函數(shù)間隔。這才是函數(shù)間隔上場(chǎng)的時(shí)間，特別不喜歡那些一上來就定義函數(shù)間隔和幾何間隔，然后就一陣推導(dǎo)，總讓人覺得隔靴搔癢似的。
至此，我們找到一個(gè)將里面的min消去的辦法，即將所有超平面的表示加以限制，使得這個(gè)表示滿足
對(duì)所有的樣本
并且這個(gè)等號(hào)是可以取到的。
此時(shí)，內(nèi)層的min就是
我們的問題就轉(zhuǎn)化成了這樣：
s.t.?
Note：
1，我們之所以選擇使得對(duì)所有樣本函數(shù)間隔大于等于1的超平面表示，完全是為了形式上的簡(jiǎn)潔。
也可以選大于等于0.5的超平面表示，這時(shí)里面的min就成了
形式上顯然沒那么簡(jiǎn)潔了，因?yàn)榉帜钢械?對(duì)解決問題一點(diǎn)用也沒有。
2，表面看，我們要最大化的目標(biāo)中已經(jīng)沒有了b。但實(shí)際上，我們知道，b已經(jīng)成為了約束條件的一部分，如果b的取值破壞了約定條件，那是不可以的！
好了，到此為止，我們已經(jīng)成功地從尋找最大間隔超平面這一思想出發(fā)，經(jīng)過層層轉(zhuǎn)化，得到了一個(gè)純粹形式的數(shù)學(xué)問題。剩下的路程就進(jìn)入了數(shù)學(xué)的領(lǐng)地了。
具體的推導(dǎo)需要很多的數(shù)學(xué)公式，但是地鐵上用手機(jī)很難搞，暫時(shí)按下，回頭補(bǔ)上。
至于對(duì)那些線性不可分的樣本集，即對(duì)本文開頭提出的第二個(gè)問題，后續(xù)會(huì)繼續(xù)。
