经典算法解读：一文看懂支持向量机以及推导
本文是吳恩達(dá)老師的機(jī)器學(xué)習(xí)課程[1]和《統(tǒng)計(jì)學(xué)習(xí)方法》[2]的筆記和代碼復(fù)現(xiàn)部分（支持向量機(jī)）。
作者：黃海廣[3]
備注：筆記和作業(yè)（含數(shù)據(jù)、原始作業(yè)文件）、視頻都在 github 中下載。
我將陸續(xù)將課程筆記和課程代碼發(fā)布在公眾號(hào)“機(jī)器學(xué)習(xí)初學(xué)者”，敬請(qǐng)關(guān)注。這個(gè)是第三部分：支持向量機(jī)，是原教程的第七周，包含了筆記和作業(yè)代碼（原課程作業(yè)是 OCTAVE 的，這里是復(fù)現(xiàn)的 python 代碼）
已完成
第一部分：回歸代碼
第二部分：邏輯回歸
本文資源都在 github：
https://github.com/fengdu78/Coursera-ML-AndrewNg-Notes
https://github.com/fengdu78/lihang-code
筆記部分：
十二、支持向量機(jī)(Support Vector Machines)
12.1 優(yōu)化目標(biāo)
參考視頻: 12 - 1 - Optimization Objective (15 min).mkv
到目前為止,你已經(jīng)見過一系列不同的學(xué)習(xí)算法。在監(jiān)督學(xué)習(xí)中，許多學(xué)習(xí)算法的性能都非常類似，因此，重要的不是你該選擇使用學(xué)習(xí)算法A還是學(xué)習(xí)算法B，而更重要的是，應(yīng)用這些算法時(shí)，所創(chuàng)建的大量數(shù)據(jù)在應(yīng)用這些算法時(shí)，表現(xiàn)情況通常依賴于你的水平。比如：你為學(xué)習(xí)算法所設(shè)計(jì)的特征量的選擇，以及如何選擇正則化參數(shù)，諸如此類的事。還有一個(gè)更加強(qiáng)大的算法廣泛的應(yīng)用于工業(yè)界和學(xué)術(shù)界，它被稱為支持向量機(jī)(Support Vector Machine)。與邏輯回歸和神經(jīng)網(wǎng)絡(luò)相比，支持向量機(jī)，或者簡(jiǎn)稱SVM，在學(xué)習(xí)復(fù)雜的非線性方程時(shí)提供了一種更為清晰，更加強(qiáng)大的方式。因此，在接下來的視頻中，我會(huì)探討這一算法。在稍后的課程中，我也會(huì)對(duì)監(jiān)督學(xué)習(xí)算法進(jìn)行簡(jiǎn)要的總結(jié)。當(dāng)然，僅僅是作簡(jiǎn)要描述。但對(duì)于支持向量機(jī)，鑒于該算法的強(qiáng)大和受歡迎度，在本課中，我會(huì)花許多時(shí)間來講解它。它也是我們所介紹的最后一個(gè)監(jiān)督學(xué)習(xí)算法。
正如我們之前開發(fā)的學(xué)習(xí)算法，我們從優(yōu)化目標(biāo)開始。那么，我們開始學(xué)習(xí)這個(gè)算法。為了描述支持向量機(jī)，事實(shí)上，我將會(huì)從邏輯回歸開始展示我們?nèi)绾我稽c(diǎn)一點(diǎn)修改來得到本質(zhì)上的支持向量機(jī)。
那么，在邏輯回歸中我們已經(jīng)熟悉了這里的假設(shè)函數(shù)形式，和右邊的 S 型激勵(lì)函數(shù)。然而，為了解釋一些數(shù)學(xué)知識(shí).我將用?表示。
現(xiàn)在考慮下我們想要邏輯回歸做什么：如果有一個(gè)?的樣本，我的意思是不管是在訓(xùn)練集中或是在測(cè)試集中，又或者在交叉驗(yàn)證集中，總之是?，現(xiàn)在我們希望?趨近 1。因?yàn)槲覀兿胍_地將此樣本分類，這就意味著當(dāng)?趨近于 1 時(shí)，?應(yīng)當(dāng)遠(yuǎn)大于 0，這里的意思是遠(yuǎn)遠(yuǎn)大于 0。這是因?yàn)橛捎??表示?，當(dāng)?遠(yuǎn)大于 0 時(shí)，即到了該圖的右邊，你不難發(fā)現(xiàn)此時(shí)邏輯回歸的輸出將趨近于 1。相反地，如果我們有另一個(gè)樣本，即。我們希望假設(shè)函數(shù)的輸出值將趨近于 0，這對(duì)應(yīng)于，或者就是??會(huì)遠(yuǎn)小于 0，因?yàn)閷?duì)應(yīng)的假設(shè)函數(shù)的輸出值趨近 0。
如果你進(jìn)一步觀察邏輯回歸的代價(jià)函數(shù)，你會(huì)發(fā)現(xiàn)每個(gè)樣本?都會(huì)為總代價(jià)函數(shù)，增加這里的一項(xiàng)，因此，對(duì)于總代價(jià)函數(shù)通常會(huì)有對(duì)所有的訓(xùn)練樣本求和，并且這里還有一個(gè)項(xiàng)，但是，在邏輯回歸中，這里的這一項(xiàng)就是表示一個(gè)訓(xùn)練樣本所對(duì)應(yīng)的表達(dá)式。現(xiàn)在，如果我將完整定義的假設(shè)函數(shù)代入這里。那么，我們就會(huì)得到每一個(gè)訓(xùn)練樣本都影響這一項(xiàng)。
現(xiàn)在，先忽略??這一項(xiàng)，但是這一項(xiàng)是影響整個(gè)總代價(jià)函數(shù)中的這一項(xiàng)的。
現(xiàn)在，一起來考慮兩種情況：
一種是等于 1 的情況；另一種是??等于 0 的情況。
在第一種情況中，假設(shè)??，此時(shí)在目標(biāo)函數(shù)中只需有第一項(xiàng)起作用，因?yàn)闀r(shí)，項(xiàng)將等于 0。因此，當(dāng)在??的樣本中時(shí)，即在?中 ，我們得到??這樣一項(xiàng)，這里同上一張幻燈片一致。
我用??表示，即：?。當(dāng)然，在代價(jià)函數(shù)中，?前面有負(fù)號(hào)。我們只是這樣表示，如果??代價(jià)函數(shù)中，這一項(xiàng)也等于 1。這樣做是為了簡(jiǎn)化此處的表達(dá)式。如果畫出關(guān)于?的函數(shù)，你會(huì)看到左下角的這條曲線，我們同樣可以看到，當(dāng)?增大時(shí)，也就是相當(dāng)于增大時(shí)，?對(duì)應(yīng)的值會(huì)變的非常小。對(duì)整個(gè)代價(jià)函數(shù)而言，影響也非常小。這也就解釋了，為什么邏輯回歸在觀察到正樣本時(shí)，試圖將設(shè)置得非常大。因?yàn)?#xff0c;在代價(jià)函數(shù)中的這一項(xiàng)會(huì)變的非常小。
現(xiàn)在開始建立支持向量機(jī)，我們從這里開始：
我們會(huì)從這個(gè)代價(jià)函數(shù)開始，也就是一點(diǎn)一點(diǎn)修改，讓我取這里的?點(diǎn)，我先畫出將要用的代價(jià)函數(shù)。
新的代價(jià)函數(shù)將會(huì)水平的從這里到右邊(圖外)，然后我再畫一條同邏輯回歸非常相似的直線，但是，在這里是一條直線，也就是我用紫紅色畫的曲線，就是這條紫紅色的曲線。那么，到了這里已經(jīng)非常接近邏輯回歸中使用的代價(jià)函數(shù)了。只是這里是由兩條線段組成，即位于右邊的水平部分和位于左邊的直線部分，先別過多的考慮左邊直線部分的斜率，這并不是很重要。但是，這里我們將使用的新的代價(jià)函數(shù)，是在的前提下的。你也許能想到，這應(yīng)該能做同邏輯回歸中類似的事情，但事實(shí)上，在之后的優(yōu)化問題中，這會(huì)變得更堅(jiān)定，并且為支持向量機(jī)，帶來計(jì)算上的優(yōu)勢(shì)。例如，更容易計(jì)算股票交易的問題等等。
目前，我們只是討論了的情況，另外一種情況是當(dāng)時(shí)，此時(shí)如果你仔細(xì)觀察代價(jià)函數(shù)只留下了第二項(xiàng)，因?yàn)榈谝豁?xiàng)被消除了。如果當(dāng)時(shí)，那么這一項(xiàng)也就是 0 了。所以上述表達(dá)式只留下了第二項(xiàng)。因此，這個(gè)樣本的代價(jià)或是代價(jià)函數(shù)的貢獻(xiàn)。將會(huì)由這一項(xiàng)表示。并且，如果你將這一項(xiàng)作為的函數(shù)，那么，這里就會(huì)得到橫軸。現(xiàn)在，你完成了支持向量機(jī)中的部分內(nèi)容，同樣地，我們要替代這一條藍(lán)色的線，用相似的方法。
如果我們用一個(gè)新的代價(jià)函數(shù)來代替，即這條從 0 點(diǎn)開始的水平直線，然后是一條斜線，像上圖。那么，現(xiàn)在讓我給這兩個(gè)方程命名，左邊的函數(shù)，我稱之為，同時(shí)，右邊函數(shù)我稱它為。這里的下標(biāo)是指在代價(jià)函數(shù)中，對(duì)應(yīng)的??和??的情況，擁有了這些定義后，現(xiàn)在，我們就開始構(gòu)建支持向量機(jī)。
這是我們?cè)谶壿嫽貧w中使用代價(jià)函數(shù)。也許這個(gè)方程看起來不是非常熟悉。這是因?yàn)橹坝袀€(gè)負(fù)號(hào)在方程外面，但是，這里我所做的是，將負(fù)號(hào)移到了表達(dá)式的里面，這樣做使得方程看起來有些不同。對(duì)于支持向量機(jī)而言，實(shí)質(zhì)上我們要將這替換為，也就是，同樣地，我也將這一項(xiàng)替換為，也就是代價(jià)。這里的代價(jià)函數(shù)，就是之前所提到的那條線。此外，代價(jià)函數(shù)，也是上面所介紹過的那條線。因此，對(duì)于支持向量機(jī)，我們得到了這里的最小化問題，即:
然后，再加上正則化參數(shù)。現(xiàn)在，按照支持向量機(jī)的慣例，事實(shí)上，我們的書寫會(huì)稍微有些不同，代價(jià)函數(shù)的參數(shù)表示也會(huì)稍微有些不同。
首先，我們要除去這一項(xiàng)，當(dāng)然，這僅僅是由于人們使用支持向量機(jī)時(shí)，對(duì)比于邏輯回歸而言，不同的習(xí)慣所致，但這里我所說的意思是：你知道，我將要做的是僅僅除去這一項(xiàng)，但是，這也會(huì)得出同樣的??最優(yōu)值，好的，因?yàn)?僅是個(gè)常量，因此，你知道在這個(gè)最小化問題中，無論前面是否有?這一項(xiàng)，最終我所得到的最優(yōu)值都是一樣的。這里我的意思是，先給你舉一個(gè)樣本，假定有一最小化問題：即要求當(dāng)取得最小值時(shí)的值，這時(shí)最小值為：當(dāng)時(shí)取得最小值。
現(xiàn)在，如果我們想要將這個(gè)目標(biāo)函數(shù)乘上常數(shù) 10，這里我的最小化問題就變成了：求使得最小的值，然而，使得這里最小的值仍為 5。因此將一些常數(shù)乘以你的最小化項(xiàng)，這并不會(huì)改變最小化該方程時(shí)得到值。因此，這里我所做的是刪去常量。也相同的，我將目標(biāo)函數(shù)乘上一個(gè)常量，并不會(huì)改變?nèi)〉米钚≈禃r(shí)的值。
第二點(diǎn)概念上的變化，我們只是指在使用支持向量機(jī)時(shí)，一些如下的標(biāo)準(zhǔn)慣例，而不是邏輯回歸。因此，對(duì)于邏輯回歸，在目標(biāo)函數(shù)中，我們有兩項(xiàng)：第一個(gè)是訓(xùn)練樣本的代價(jià)，第二個(gè)是我們的正則化項(xiàng)，我們不得不去用這一項(xiàng)來平衡。這就相當(dāng)于我們想要最小化加上正則化參數(shù)，然后乘以其他項(xiàng)對(duì)吧？這里的表示這里的第一項(xiàng)，同時(shí)我用B表示第二項(xiàng)，但不包括，我們不是優(yōu)化這里的。我們所做的是通過設(shè)置不同正則參數(shù)達(dá)到優(yōu)化目的。這樣，我們就能夠權(quán)衡對(duì)應(yīng)的項(xiàng)，是使得訓(xùn)練樣本擬合的更好。即最小化。還是保證正則參數(shù)足夠小，也即是對(duì)于B項(xiàng)而言，但對(duì)于支持向量機(jī)，按照慣例，我們將使用一個(gè)不同的參數(shù)替換這里使用的來權(quán)衡這兩項(xiàng)。你知道，就是第一項(xiàng)和第二項(xiàng)我們依照慣例使用一個(gè)不同的參數(shù)稱為，同時(shí)改為優(yōu)化目標(biāo)，。因此，在邏輯回歸中，如果給定，一個(gè)非常大的值，意味著給予更大的權(quán)重。而這里，就對(duì)應(yīng)于將?設(shè)定為非常小的值，那么，相應(yīng)的將會(huì)給比給更大的權(quán)重。因此，這只是一種不同的方式來控制這種權(quán)衡或者一種不同的方法，即用參數(shù)來決定是更關(guān)心第一項(xiàng)的優(yōu)化，還是更關(guān)心第二項(xiàng)的優(yōu)化。當(dāng)然你也可以把這里的參數(shù)?考慮成，同?所扮演的角色相同，并且這兩個(gè)方程或這兩個(gè)表達(dá)式并不相同，因?yàn)?#xff0c;但是也并不全是這樣，如果當(dāng)時(shí)，這兩個(gè)優(yōu)化目標(biāo)應(yīng)當(dāng)?shù)玫较嗤闹?#xff0c;相同的最優(yōu)值?。因此，就用它們來代替。那么，我現(xiàn)在刪掉這里的，并且用常數(shù)來代替。因此，這就得到了在支持向量機(jī)中我們的整個(gè)優(yōu)化目標(biāo)函數(shù)。然后最小化這個(gè)目標(biāo)函數(shù)，得到SVM 學(xué)習(xí)到的參數(shù)。
最后有別于邏輯回歸輸出的概率。在這里，我們的代價(jià)函數(shù)，當(dāng)最小化代價(jià)函數(shù)，獲得參數(shù)時(shí)，支持向量機(jī)所做的是它來直接預(yù)測(cè)的值等于 1，還是等于 0。因此，這個(gè)假設(shè)函數(shù)會(huì)預(yù)測(cè) 1。當(dāng)大于或者等于 0 時(shí)，或者等于 0 時(shí)，所以學(xué)習(xí)參數(shù)就是支持向量機(jī)假設(shè)函數(shù)的形式。那么，這就是支持向量機(jī)數(shù)學(xué)上的定義。
在接下來的視頻中，讓我們?cè)倩厝闹庇^的角度看看優(yōu)化目標(biāo)，實(shí)際上是在做什么，以及 SVM 的假設(shè)函數(shù)將會(huì)學(xué)習(xí)什么，同時(shí)也會(huì)談?wù)勅绾巫鲂┰S修改，學(xué)習(xí)更加復(fù)雜、非線性的函數(shù)。
12.2 大邊界的直觀理解
參考視頻: 12 - 2 - Large Margin Intuition (11 min).mkv
人們有時(shí)將支持向量機(jī)看作是大間距分類器。在這一部分，我將介紹其中的含義，這有助于我們直觀理解SVM模型的假設(shè)是什么樣的。
這是我的支持向量機(jī)模型的代價(jià)函數(shù)，在左邊這里我畫出了關(guān)于的代價(jià)函數(shù)，此函數(shù)用于正樣本，而在右邊這里我畫出了關(guān)于的代價(jià)函數(shù)，橫軸表示，現(xiàn)在讓我們考慮一下，最小化這些代價(jià)函數(shù)的必要條件是什么。如果你有一個(gè)正樣本，，則只有在時(shí)，代價(jià)函數(shù)才等于 0。
換句話說，如果你有一個(gè)正樣本，我們會(huì)希望，反之，如果，我們觀察一下，函數(shù)，它只有在的區(qū)間里函數(shù)值為 0。這是支持向量機(jī)的一個(gè)有趣性質(zhì)。事實(shí)上，如果你有一個(gè)正樣本，則其實(shí)我們僅僅要求大于等于 0，就能將該樣本恰當(dāng)分出，這是因?yàn)槿绻?gt;0 大的話，我們的模型代價(jià)函數(shù)值為 0，類似地，如果你有一個(gè)負(fù)樣本，則僅需要<=0 就會(huì)將負(fù)例正確分離，但是，支持向量機(jī)的要求更高，不僅僅要能正確分開輸入的樣本，即不僅僅要求>0，我們需要的是比 0 值大很多，比如大于等于 1，我也想這個(gè)比 0 小很多，比如我希望它小于等于-1，這就相當(dāng)于在支持向量機(jī)中嵌入了一個(gè)額外的安全因子，或者說安全的間距因子。
當(dāng)然，邏輯回歸做了類似的事情。但是讓我們看一下，在支持向量機(jī)中，這個(gè)因子會(huì)導(dǎo)致什么結(jié)果。具體而言，我接下來會(huì)考慮一個(gè)特例。我們將這個(gè)常數(shù)設(shè)置成一個(gè)非常大的值。比如我們假設(shè)的值為 100000 或者其它非常大的數(shù)，然后來觀察支持向量機(jī)會(huì)給出什么結(jié)果？
如果?非常大，則最小化代價(jià)函數(shù)的時(shí)候，我們將會(huì)很希望找到一個(gè)使第一項(xiàng)為 0 的最優(yōu)解。因此，讓我們嘗試在代價(jià)項(xiàng)的第一項(xiàng)為 0 的情形下理解該優(yōu)化問題。比如我們可以把設(shè)置成了非常大的常數(shù)，這將給我們一些關(guān)于支持向量機(jī)模型的直觀感受。
我們已經(jīng)看到輸入一個(gè)訓(xùn)練樣本標(biāo)簽為，你想令第一項(xiàng)為 0，你需要做的是找到一個(gè)，使得，類似地，對(duì)于一個(gè)訓(xùn)練樣本，標(biāo)簽為，為了使?函數(shù)的值為 0，我們需要。因此，現(xiàn)在考慮我們的優(yōu)化問題。選擇參數(shù)，使得第一項(xiàng)等于 0，就會(huì)導(dǎo)致下面的優(yōu)化問題，因?yàn)槲覀儗⑦x擇參數(shù)使第一項(xiàng)為 0，因此這個(gè)函數(shù)的第一項(xiàng)為 0，因此是乘以 0 加上二分之一乘以第二項(xiàng)。這里第一項(xiàng)是乘以 0，因此可以將其刪去，因?yàn)槲抑浪?0。
這將遵從以下的約束：，如果?是等于 1 的，，如果樣本是一個(gè)負(fù)樣本，這樣當(dāng)你求解這個(gè)優(yōu)化問題的時(shí)候，當(dāng)你最小化這個(gè)關(guān)于變量的函數(shù)的時(shí)候，你會(huì)得到一個(gè)非常有趣的決策邊界。
具體而言，如果你考察這樣一個(gè)數(shù)據(jù)集，其中有正樣本，也有負(fù)樣本，可以看到這個(gè)數(shù)據(jù)集是線性可分的。我的意思是，存在一條直線把正負(fù)樣本分開。當(dāng)然有多條不同的直線，可以把正樣本和負(fù)樣本完全分開。
比如，這就是一個(gè)決策邊界可以把正樣本和負(fù)樣本分開。但是多多少少這個(gè)看起來并不是非常自然是么?
或者我們可以畫一條更差的決策界，這是另一條決策邊界，可以將正樣本和負(fù)樣本分開，但僅僅是勉強(qiáng)分開，這些決策邊界看起來都不是特別好的選擇，支持向量機(jī)將會(huì)選擇這個(gè)黑色的決策邊界，相較于之前我用粉色或者綠色畫的決策界。這條黑色的看起來好得多，黑線看起來是更穩(wěn)健的決策界。在分離正樣本和負(fù)樣本上它顯得的更好。數(shù)學(xué)上來講，這是什么意思呢？這條黑線有更大的距離，這個(gè)距離叫做間距(margin)。
當(dāng)畫出這兩條額外的藍(lán)線，我們看到黑色的決策界和訓(xùn)練樣本之間有更大的最短距離。然而粉線和藍(lán)線離訓(xùn)練樣本就非常近，在分離樣本的時(shí)候就會(huì)比黑線表現(xiàn)差。因此，這個(gè)距離叫做支持向量機(jī)的間距，而這是支持向量機(jī)具有魯棒性的原因，因?yàn)樗τ靡粋€(gè)最大間距來分離樣本。因此支持向量機(jī)有時(shí)被稱為大間距分類器，而這其實(shí)是求解上一頁幻燈片上優(yōu)化問題的結(jié)果。
我知道你也許想知道求解上一頁幻燈片中的優(yōu)化問題為什么會(huì)產(chǎn)生這個(gè)結(jié)果？它是如何產(chǎn)生這個(gè)大間距分類器的呢？我知道我還沒有解釋這一點(diǎn)。
我將會(huì)從直觀上略述為什么這個(gè)優(yōu)化問題會(huì)產(chǎn)生大間距分類器。總之這個(gè)圖示有助于你理解支持向量機(jī)模型的做法，即努力將正樣本和負(fù)樣本用最大的間距分開。
在本節(jié)課中關(guān)于大間距分類器，我想講最后一點(diǎn)：我們將這個(gè)大間距分類器中的正則化因子常數(shù)設(shè)置的非常大，我記得我將其設(shè)置為了 100000，因此對(duì)這樣的一個(gè)數(shù)據(jù)集，也許我們將選擇這樣的決策界，從而最大間距地分離開正樣本和負(fù)樣本。那么在讓代價(jià)函數(shù)最小化的過程中，我們希望找出在和兩種情況下都使得代價(jià)函數(shù)中左邊的這一項(xiàng)盡量為零的參數(shù)。如果我們找到了這樣的參數(shù)，則我們的最小化問題便轉(zhuǎn)變成：
事實(shí)上，支持向量機(jī)現(xiàn)在要比這個(gè)大間距分類器所體現(xiàn)得更成熟，尤其是當(dāng)你使用大間距分類器的時(shí)候，你的學(xué)習(xí)算法會(huì)受異常點(diǎn)(outlier) 的影響。比如我們加入一個(gè)額外的正樣本。
在這里，如果你加了這個(gè)樣本，為了將樣本用最大間距分開，也許我最終會(huì)得到一條類似這樣的決策界，對(duì)么？就是這條粉色的線，僅僅基于一個(gè)異常值，僅僅基于一個(gè)樣本，就將我的決策界從這條黑線變到這條粉線，這實(shí)在是不明智的。而如果正則化參數(shù)，設(shè)置的非常大，這事實(shí)上正是支持向量機(jī)將會(huì)做的。它將決策界，從黑線變到了粉線，但是如果?設(shè)置的小一點(diǎn)，**如果你將 C 設(shè)置的不要太大，則你最終會(huì)得到這條黑線，**當(dāng)然數(shù)據(jù)如果不是線性可分的，如果你在這里有一些正樣本或者你在這里有一些負(fù)樣本，則支持向量機(jī)也會(huì)將它們恰當(dāng)分開。因此，大間距分類器的描述，僅僅是從直觀上給出了正則化參數(shù)非常大的情形，同時(shí)，要提醒你的作用類似于，是我們之前使用過的正則化參數(shù)。這只是非常大的情形，或者等價(jià)地??非常小的情形。你最終會(huì)得到類似粉線這樣的決策界，但是實(shí)際上應(yīng)用支持向量機(jī)的時(shí)候，**當(dāng)不是非常非常大的時(shí)候，它可以忽略掉一些異常點(diǎn)的影響，得到更好的決策界。**甚至當(dāng)你的數(shù)據(jù)不是線性可分的時(shí)候，支持向量機(jī)也可以給出好的結(jié)果。
回顧?，因此：
?較大時(shí)，相當(dāng)于??較小，可能會(huì)導(dǎo)致過擬合，高方差。
?較小時(shí)，相當(dāng)于較大，可能會(huì)導(dǎo)致低擬合，高偏差。
我們稍后會(huì)介紹支持向量機(jī)的偏差和方差，希望在那時(shí)候關(guān)于如何處理參數(shù)的這種平衡會(huì)變得更加清晰。我希望，這節(jié)課給出了一些關(guān)于為什么支持向量機(jī)被看做大間距分類器的直觀理解。它用最大間距將樣本區(qū)分開，盡管從技術(shù)上講，這只有當(dāng)參數(shù)是非常大的時(shí)候是真的，但是它對(duì)于理解支持向量機(jī)是有益的。
本節(jié)課中我們略去了一步，那就是我們?cè)诨脽羝薪o出的優(yōu)化問題。為什么會(huì)是這樣的？它是如何得出大間距分類器的？我在本節(jié)中沒有講解，在下一節(jié)課中，我將略述這些問題背后的數(shù)學(xué)原理，來解釋這個(gè)優(yōu)化問題是如何得到一個(gè)大間距分類器的。
12.3 大邊界分類背后的數(shù)學(xué)（選修）
參考視頻: 12 - 3 - Mathematics Behind Large Margin Classification (Optional) (20 min).mkv
在本節(jié)課中，我將介紹一些大間隔分類背后的數(shù)學(xué)原理。本節(jié)為選修部分，你完全可以跳過它，但是聽聽這節(jié)課可能讓你對(duì)支持向量機(jī)中的優(yōu)化問題，以及如何得到大間距分類器，產(chǎn)生更好的直觀理解。
首先，讓我來給大家復(fù)習(xí)一下關(guān)于向量?jī)?nèi)積的知識(shí)。假設(shè)我有兩個(gè)向量，和，我將它們寫在這里。兩個(gè)都是二維向量，我們看一下，的結(jié)果。也叫做向量和之間的內(nèi)積。由于是二維向量，我可以將它們畫在這個(gè)圖上。我們說，這就是向量即在橫軸上，取值為某個(gè)，而在縱軸上，高度是某個(gè)作為的第二個(gè)分量。現(xiàn)在，很容易計(jì)算的一個(gè)量就是向量的范數(shù)。表示的范數(shù)，即的長(zhǎng)度，即向量的歐幾里得長(zhǎng)度。根據(jù)畢達(dá)哥拉斯定理，，這是向量的長(zhǎng)度，它是一個(gè)實(shí)數(shù)。現(xiàn)在你知道了這個(gè)的長(zhǎng)度是多少了。我剛剛畫的這個(gè)向量的長(zhǎng)度就知道了。
現(xiàn)在讓我們回頭來看向量?，因?yàn)槲覀兿胗?jì)算內(nèi)積。是另一個(gè)向量，它的兩個(gè)分量和是已知的。向量可以畫在這里，現(xiàn)在讓我們來看看如何計(jì)算和之間的內(nèi)積。這就是具體做法，我們將向量投影到向量上，我們做一個(gè)直角投影，或者說一個(gè) 90 度投影將其投影到上，接下來我度量這條紅線的長(zhǎng)度。我稱這條紅線的長(zhǎng)度為，因此就是長(zhǎng)度，或者說是向量投影到向量上的量，我將它寫下來，是投影到向量上的長(zhǎng)度，因此可以將，或者說的長(zhǎng)度。這是計(jì)算內(nèi)積的一種方法。如果你從幾何上畫出的值，同時(shí)畫出的范數(shù)，你也會(huì)同樣地計(jì)算出內(nèi)積，答案是一樣的。另一個(gè)計(jì)算公式是：就是?這個(gè)一行兩列的矩陣乘以。因此可以得到。根據(jù)線性代數(shù)的知識(shí)，這兩個(gè)公式會(huì)給出同樣的結(jié)果。順便說一句，。因此如果你將和交換位置，將投影到上，而不是將投影到上，然后做同樣地計(jì)算，只是把和的位置交換一下，你事實(shí)上可以得到同樣的結(jié)果。申明一點(diǎn)，在這個(gè)等式中的范數(shù)是一個(gè)實(shí)數(shù)，也是一個(gè)實(shí)數(shù)，因此就是兩個(gè)實(shí)數(shù)正常相乘。
最后一點(diǎn)，需要注意的就是值，事實(shí)上是有符號(hào)的，即它可能是正值，也可能是負(fù)值。我的意思是說，如果是一個(gè)類似這樣的向量，是一個(gè)類似這樣的向量，和之間的夾角大于 90 度，則如果將投影到上，會(huì)得到這樣的一個(gè)投影，這是的長(zhǎng)度，在這個(gè)情形下我們?nèi)匀挥惺堑扔诔艘缘姆稊?shù)。唯一一點(diǎn)不同的是在這里是負(fù)的。在內(nèi)積計(jì)算中，如果和之間的夾角小于 90 度，那么那條紅線的長(zhǎng)度是正值。然而如果這個(gè)夾角大于 90 度，則將會(huì)是負(fù)的。就是這個(gè)小線段的長(zhǎng)度是負(fù)的。如果它們之間的夾角大于 90 度，兩個(gè)向量之間的內(nèi)積也是負(fù)的。這就是關(guān)于向量?jī)?nèi)積的知識(shí)。我們接下來將會(huì)使用這些關(guān)于向量?jī)?nèi)積的性質(zhì)試圖來理解支持向量機(jī)中的目標(biāo)函數(shù)。
這就是我們先前給出的支持向量機(jī)模型中的目標(biāo)函數(shù)。為了講解方便，我做一點(diǎn)簡(jiǎn)化，僅僅是為了讓目標(biāo)函數(shù)更容易被分析。
我接下來忽略掉截距，令，這樣更容易畫示意圖。我將特征數(shù)置為 2，因此我們僅有兩個(gè)特征，現(xiàn)在我們來看一下目標(biāo)函數(shù)，支持向量機(jī)的優(yōu)化目標(biāo)函數(shù)。當(dāng)我們僅有兩個(gè)特征，即時(shí)，這個(gè)式子可以寫作：，我們只有兩個(gè)參數(shù)。你可能注意到括號(hào)里面的這一項(xiàng)是向量的范數(shù)，或者說是向量的長(zhǎng)度。我的意思是如果我們將向量寫出來，那么我剛剛畫紅線的這一項(xiàng)就是向量的長(zhǎng)度或范數(shù)。這里我們用的是之前學(xué)過的向量范數(shù)的定義，事實(shí)上這就等于向量的長(zhǎng)度。
當(dāng)然你可以將其寫作，如果，那就是的長(zhǎng)度。在這里我將忽略，這樣來寫的范數(shù)，它僅僅和有關(guān)。但是，數(shù)學(xué)上不管你是否包含，其實(shí)并沒有差別，因此在我們接下來的推導(dǎo)中去掉不會(huì)有影響這意味著我們的目標(biāo)函數(shù)是等于。因此支持向量機(jī)做的全部事情，就是極小化參數(shù)向量范數(shù)的平方，或者說長(zhǎng)度的平方。
現(xiàn)在我將要看看這些項(xiàng)：更深入地理解它們的含義。給定參數(shù)向量給定一個(gè)樣本，這等于什么呢?在前一頁幻燈片上，我們畫出了在不同情形下，的示意圖，我們將會(huì)使用這些概念，和就類似于和?。
讓我們看一下示意圖：我們考察一個(gè)單一的訓(xùn)練樣本，我有一個(gè)正樣本在這里，用一個(gè)叉來表示這個(gè)樣本，意思是在水平軸上取值為，在豎直軸上取值為。這就是我畫出的訓(xùn)練樣本。盡管我沒有將其真的看做向量。它事實(shí)上就是一個(gè)始于原點(diǎn)，終點(diǎn)位置在這個(gè)訓(xùn)練樣本點(diǎn)的向量。現(xiàn)在，我們有一個(gè)參數(shù)向量我會(huì)將它也畫成向量。我將畫在橫軸這里，將?畫在縱軸這里，那么內(nèi)積?將會(huì)是什么呢？
使用我們之前的方法，我們計(jì)算的方式就是我將訓(xùn)練樣本投影到參數(shù)向量，然后我來看一看這個(gè)線段的長(zhǎng)度，我將它畫成紅色。我將它稱為用來表示這是第?個(gè)訓(xùn)練樣本在參數(shù)向量上的投影。根據(jù)我們之前幻燈片的內(nèi)容，我們知道的是將會(huì)等于?乘以向量??的長(zhǎng)度或范數(shù)。這就等于。這兩種方式是等價(jià)的，都可以用來計(jì)算和之間的內(nèi)積。
這告訴了我們什么呢？這里表達(dá)的意思是：這個(gè)?或者的,約束是可以被這個(gè)約束所代替的。因?yàn)?，將其寫入我們的優(yōu)化目標(biāo)。我們將會(huì)得到?jīng)]有了約束，而變成了。
需要提醒一點(diǎn)，我們之前曾講過這個(gè)優(yōu)化目標(biāo)函數(shù)可以被寫成等于。
現(xiàn)在讓我們考慮下面這里的訓(xùn)練樣本。現(xiàn)在，繼續(xù)使用之前的簡(jiǎn)化，即，我們來看一下支持向量機(jī)會(huì)選擇什么樣的決策界。這是一種選擇，我們假設(shè)支持向量機(jī)會(huì)選擇這個(gè)決策邊界。這不是一個(gè)非常好的選擇，因?yàn)樗拈g距很小。這個(gè)決策界離訓(xùn)練樣本的距離很近。我們來看一下為什么支持向量機(jī)不會(huì)選擇它。
對(duì)于這樣選擇的參數(shù)，可以看到參數(shù)向量事實(shí)上是和決策界是 90 度正交的，因此這個(gè)綠色的決策界對(duì)應(yīng)著一個(gè)參數(shù)向量這個(gè)方向,順便提一句的簡(jiǎn)化僅僅意味著決策界必須通過原點(diǎn)。現(xiàn)在讓我們看一下這對(duì)于優(yōu)化目標(biāo)函數(shù)意味著什么。
比如這個(gè)樣本，我們假設(shè)它是我的第一個(gè)樣本，如果我考察這個(gè)樣本到參數(shù)的投影，投影是這個(gè)短的紅線段，就等于，它非常短。類似地，這個(gè)樣本如果它恰好是，我的第二個(gè)訓(xùn)練樣本，則它到的投影在這里。我將它畫成粉色，這個(gè)短的粉色線段是，即第二個(gè)樣本到我的參數(shù)向量的投影。因此，這個(gè)投影非常短。事實(shí)上是一個(gè)負(fù)值，是在相反的方向，這個(gè)向量和參數(shù)向量的夾角大于 90 度，的值小于 0。
我們會(huì)發(fā)現(xiàn)這些將會(huì)是非常小的數(shù)，因此當(dāng)我們考察優(yōu)化目標(biāo)函數(shù)的時(shí)候，對(duì)于正樣本而言，我們需要,但是如果?在這里非常小,那就意味著我們需要的范數(shù)非常大.因?yàn)槿绻??很小,而我們希望,令其實(shí)現(xiàn)的唯一的辦法就是這兩個(gè)數(shù)較大。如果??小，我們就希望的范數(shù)大。類似地，對(duì)于負(fù)樣本而言我們需要。我們已經(jīng)在這個(gè)樣本中看到會(huì)是一個(gè)非常小的數(shù)，因此唯一的辦法就是的范數(shù)變大。但是我們的目標(biāo)函數(shù)是希望找到一個(gè)參數(shù)，它的范數(shù)是小的。因此，這看起來不像是一個(gè)好的參數(shù)向量的選擇。
相反的，來看一個(gè)不同的決策邊界。比如說，支持向量機(jī)選擇了這個(gè)決策界，現(xiàn)在狀況會(huì)有很大不同。如果這是決策界，這就是相對(duì)應(yīng)的參數(shù)的方向，因此，在這個(gè)決策界之下，垂直線是決策界。使用線性代數(shù)的知識(shí)，可以說明，這個(gè)綠色的決策界有一個(gè)垂直于它的向量。現(xiàn)在如果你考察你的數(shù)據(jù)在橫軸上的投影，比如這個(gè)我之前提到的樣本，我的樣本，當(dāng)我將它投影到橫軸上，或說投影到上，就會(huì)得到這樣。它的長(zhǎng)度是，另一個(gè)樣本，那個(gè)樣本是。我做同樣的投影，我會(huì)發(fā)現(xiàn)，的長(zhǎng)度是負(fù)值。你會(huì)注意到現(xiàn)在?和這些投影長(zhǎng)度是長(zhǎng)多了。如果我們?nèi)匀灰獫M足這些約束，>1，則因?yàn)樽兇罅?#xff0c;的范數(shù)就可以變小了。因此這意味著通過選擇右邊的決策界，而不是左邊的那個(gè)，支持向量機(jī)可以使參數(shù)的范數(shù)變小很多。因此，如果我們想令的范數(shù)變小，從而令范數(shù)的平方變小，就能讓支持向量機(jī)選擇右邊的決策界。這就是支持向量機(jī)如何能有效地產(chǎn)生大間距分類的原因。
看這條綠線，這個(gè)綠色的決策界。我們希望正樣本和負(fù)樣本投影到的值大。要做到這一點(diǎn)的唯一方式就是選擇這條綠線做決策界。這是大間距決策界來區(qū)分開正樣本和負(fù)樣本這個(gè)間距的值。這個(gè)間距的值就是等等的值。通過讓間距變大，即通過這些等等的值，支持向量機(jī)最終可以找到一個(gè)較小的范數(shù)。這正是支持向量機(jī)中最小化目標(biāo)函數(shù)的目的。
以上就是為什么支持向量機(jī)最終會(huì)找到大間距分類器的原因。因?yàn)樗噲D極大化這些的范數(shù)，它們是訓(xùn)練樣本到?jīng)Q策邊界的距離。最后一點(diǎn)，我們的推導(dǎo)自始至終使用了這個(gè)簡(jiǎn)化假設(shè)，就是參數(shù)。
就像我之前提到的。這個(gè)的作用是：的意思是我們讓決策界通過原點(diǎn)。如果你令不是 0 的話，含義就是你希望決策界不通過原點(diǎn)。我將不會(huì)做全部的推導(dǎo)。實(shí)際上，支持向量機(jī)產(chǎn)生大間距分類器的結(jié)論，會(huì)被證明同樣成立，證明方式是非常類似的，是我們剛剛做的證明的推廣。
之前視頻中說過，即便不等于 0，支持向量機(jī)要做的事情都是優(yōu)化這個(gè)目標(biāo)函數(shù)對(duì)應(yīng)著值非常大的情況，但是可以說明的是，即便不等于 0，支持向量機(jī)仍然會(huì)找到正樣本和負(fù)樣本之間的大間距分隔。
總之，我們解釋了為什么支持向量機(jī)是一個(gè)大間距分類器。在下一節(jié)我們，將開始討論如何利用支持向量機(jī)的原理，應(yīng)用它們建立一個(gè)復(fù)雜的非線性分類器。
12.4 核函數(shù) 1
參考視頻: 12 - 4 - Kernels I (16 min).mkv
回顧我們之前討論過可以使用高級(jí)數(shù)的多項(xiàng)式模型來解決無法用直線進(jìn)行分隔的分類問題：
為了獲得上圖所示的判定邊界，我們的模型可能是的形式。
我們可以用一系列的新的特征來替換模型中的每一項(xiàng)。例如令：?
...得到。然而，除了對(duì)原有的特征進(jìn)行組合以外，有沒有更好的方法來構(gòu)造？我們可以利用核函數(shù)來計(jì)算出新的特征。
給定一個(gè)訓(xùn)練樣本，我們利用的各個(gè)特征與我們預(yù)先選定的地標(biāo)(landmarks)的近似程度來選取新的特征。
例如：
其中：，為實(shí)例中所有特征與地標(biāo)之間的距離的和。上例中的就是核函數(shù)，具體而言，這里是一個(gè)高斯核函數(shù)(Gaussian Kernel)。注：這個(gè)函數(shù)與正態(tài)分布沒什么實(shí)際上的關(guān)系，只是看上去像而已。
這些地標(biāo)的作用是什么？如果一個(gè)訓(xùn)練樣本與地標(biāo)之間的距離近似于 0，則新特征?近似于，如果訓(xùn)練樣本與地標(biāo)之間距離較遠(yuǎn)，則近似于一個(gè)較大的數(shù)。
假設(shè)我們的訓(xùn)練樣本含有兩個(gè)特征[?]，給定地標(biāo)與不同的值，見下圖：
圖中水平面的坐標(biāo)為?，而垂直坐標(biāo)軸代表。可以看出，只有當(dāng)與重合時(shí)才具有最大值。隨著的改變值改變的速率受到的控制。
在下圖中，當(dāng)樣本處于洋紅色的點(diǎn)位置處，因?yàn)槠潆x更近，但是離和較遠(yuǎn)，因此接近 1，而,接近 0。因此，因此預(yù)測(cè)。同理可以求出，對(duì)于離較近的綠色點(diǎn)，也預(yù)測(cè)，但是對(duì)于藍(lán)綠色的點(diǎn)，因?yàn)槠潆x三個(gè)地標(biāo)都較遠(yuǎn)，預(yù)測(cè)。
這樣，圖中紅色的封閉曲線所表示的范圍，便是我們依據(jù)一個(gè)單一的訓(xùn)練樣本和我們選取的地標(biāo)所得出的判定邊界，在預(yù)測(cè)時(shí)，我們采用的特征不是訓(xùn)練樣本本身的特征，而是通過核函數(shù)計(jì)算出的新特征。
12.5 核函數(shù) 2
參考視頻: 12 - 5 - Kernels II (16 min).mkv
在上一節(jié)視頻里，我們討論了核函數(shù)這個(gè)想法，以及怎樣利用它去實(shí)現(xiàn)支持向量機(jī)的一些新特性。在這一節(jié)視頻中，我將補(bǔ)充一些缺失的細(xì)節(jié)，并簡(jiǎn)單的介紹一下怎么在實(shí)際中使用應(yīng)用這些想法。
如何選擇地標(biāo)？
我們通常是根據(jù)訓(xùn)練集的數(shù)量選擇地標(biāo)的數(shù)量，即如果訓(xùn)練集中有個(gè)樣本，則我們選取個(gè)地標(biāo)，并且令:。這樣做的好處在于：現(xiàn)在我們得到的新特征是建立在原有特征與訓(xùn)練集中所有其他特征之間距離的基礎(chǔ)之上的，即：
下面我們將核函數(shù)運(yùn)用到支持向量機(jī)中，修改我們的支持向量機(jī)假設(shè)為：
? 給定，計(jì)算新特征，當(dāng)?時(shí)，預(yù)測(cè)?，否則反之。
相應(yīng)地修改代價(jià)函數(shù)為：，
?在具體實(shí)施過程中，我們還需要對(duì)最后的正則化項(xiàng)進(jìn)行些微調(diào)整，在計(jì)算時(shí)，我們用代替，其中是根據(jù)我們選擇的核函數(shù)而不同的一個(gè)矩陣。這樣做的原因是為了簡(jiǎn)化計(jì)算。
理論上講，我們也可以在邏輯回歸中使用核函數(shù)，但是上面使用?來簡(jiǎn)化計(jì)算的方法不適用與邏輯回歸，因此計(jì)算將非常耗費(fèi)時(shí)間。
在此，我們不介紹最小化支持向量機(jī)的代價(jià)函數(shù)的方法，你可以使用現(xiàn)有的軟件包（如liblinear,libsvm等）。在使用這些軟件包最小化我們的代價(jià)函數(shù)之前，我們通常需要編寫核函數(shù)，并且如果我們使用高斯核函數(shù)，那么在使用之前進(jìn)行特征縮放是非常必要的。
另外，支持向量機(jī)也可以不使用核函數(shù)，不使用核函數(shù)又稱為線性核函數(shù)(linear kernel)，當(dāng)我們不采用非常復(fù)雜的函數(shù)，或者我們的訓(xùn)練集特征非常多而樣本非常少的時(shí)候，可以采用這種不帶核函數(shù)的支持向量機(jī)。
下面是支持向量機(jī)的兩個(gè)參數(shù)和的影響：
?較大時(shí)，相當(dāng)于較小，可能會(huì)導(dǎo)致過擬合，高方差；
?較小時(shí)，相當(dāng)于較大，可能會(huì)導(dǎo)致低擬合，高偏差；
較大時(shí)，可能會(huì)導(dǎo)致低方差，高偏差；
較小時(shí)，可能會(huì)導(dǎo)致低偏差，高方差。
如果你看了本周的編程作業(yè)，你就能親自實(shí)現(xiàn)這些想法，并親眼看到這些效果。這就是利用核函數(shù)的支持向量機(jī)算法，希望這些關(guān)于偏差和方差的討論，能給你一些對(duì)于算法結(jié)果預(yù)期的直觀印象。
12.6 使用支持向量機(jī)
參考視頻: 12 - 6 - Using An SVM (21 min).mkv
目前為止，我們已經(jīng)討論了SVM比較抽象的層面，在這個(gè)視頻中我將要討論到為了運(yùn)行或者運(yùn)用SVM。你實(shí)際上所需要的一些東西：支持向量機(jī)算法，提出了一個(gè)特別優(yōu)化的問題。但是就如在之前的視頻中我簡(jiǎn)單提到的，我真的不建議你自己寫軟件來求解參數(shù)，因此由于今天我們中的很少人，或者其實(shí)沒有人考慮過自己寫代碼來轉(zhuǎn)換矩陣，或求一個(gè)數(shù)的平方根等我們只是知道如何去調(diào)用庫函數(shù)來實(shí)現(xiàn)這些功能。同樣的，用以解決SVM最優(yōu)化問題的軟件很復(fù)雜，且已經(jīng)有研究者做了很多年數(shù)值優(yōu)化了。因此你提出好的軟件庫和好的軟件包來做這樣一些事兒。然后強(qiáng)烈建議使用高優(yōu)化軟件庫中的一個(gè)，而不是嘗試自己落實(shí)一些數(shù)據(jù)。有許多好的軟件庫，我正好用得最多的兩個(gè)是liblinear和libsvm，但是真的有很多軟件庫可以用來做這件事兒。你可以連接許多你可能會(huì)用來編寫學(xué)習(xí)算法的主要編程語言。
在高斯核函數(shù)之外我們還有其他一些選擇，如：
多項(xiàng)式核函數(shù)（Polynomial Kernel）
字符串核函數(shù)（String kernel）
卡方核函數(shù)（ chi-square kernel）
直方圖交集核函數(shù)（histogram interp kernel）
等等...
這些核函數(shù)的目標(biāo)也都是根據(jù)訓(xùn)練集和地標(biāo)之間的距離來構(gòu)建新特征，這些核函數(shù)需要滿足 Mercer's 定理，才能被支持向量機(jī)的優(yōu)化軟件正確處理。
多類分類問題
假設(shè)我們利用之前介紹的一對(duì)多方法來解決一個(gè)多類分類問題。如果一共有個(gè)類，則我們需要個(gè)模型，以及個(gè)參數(shù)向量。我們同樣也可以訓(xùn)練個(gè)支持向量機(jī)來解決多類分類問題。但是大多數(shù)支持向量機(jī)軟件包都有內(nèi)置的多類分類功能，我們只要直接使用即可。
盡管你不去寫你自己的SVM的優(yōu)化軟件，但是你也需要做幾件事：
1、是提出參數(shù)的選擇。我們?cè)谥暗囊曨l中討論過誤差/方差在這方面的性質(zhì)。
2、你也需要選擇內(nèi)核參數(shù)或你想要使用的相似函數(shù)，其中一個(gè)選擇是：我們選擇不需要任何內(nèi)核參數(shù)，沒有內(nèi)核參數(shù)的理念，也叫線性核函數(shù)。因此，如果有人說他使用了線性核的SVM（支持向量機(jī)），這就意味這他使用了不帶有核函數(shù)的SVM（支持向量機(jī)）。
從邏輯回歸模型，我們得到了支持向量機(jī)模型，在兩者之間，我們應(yīng)該如何選擇呢？
下面是一些普遍使用的準(zhǔn)則：
為特征數(shù)，為訓(xùn)練樣本數(shù)。
(1)如果相較于而言，要大許多，即訓(xùn)練集數(shù)據(jù)量不夠支持我們訓(xùn)練一個(gè)復(fù)雜的非線性模型，我們選用邏輯回歸模型或者不帶核函數(shù)的支持向量機(jī)。
(2)如果較小，而且大小中等，例如在 1-1000 之間，而在 10-10000 之間，使用高斯核函數(shù)的支持向量機(jī)。
(3)如果較小，而較大，例如在 1-1000 之間，而大于 50000，則使用支持向量機(jī)會(huì)非常慢，解決方案是創(chuàng)造、增加更多的特征，然后使用邏輯回歸或不帶核函數(shù)的支持向量機(jī)。
值得一提的是，神經(jīng)網(wǎng)絡(luò)在以上三種情況下都可能會(huì)有較好的表現(xiàn)，但是訓(xùn)練神經(jīng)網(wǎng)絡(luò)可能非常慢，選擇支持向量機(jī)的原因主要在于它的代價(jià)函數(shù)是凸函數(shù)，不存在局部最小值。
今天的SVM包會(huì)工作得很好，但是它們?nèi)匀粫?huì)有一些慢。當(dāng)你有非常非常大的訓(xùn)練集，且用高斯核函數(shù)是在這種情況下，我經(jīng)常會(huì)做的是嘗試手動(dòng)地創(chuàng)建，擁有更多的特征變量，然后用邏輯回歸或者不帶核函數(shù)的支持向量機(jī)。如果你看到這個(gè)幻燈片，看到了邏輯回歸，或者不帶核函數(shù)的支持向量機(jī)。在這個(gè)兩個(gè)地方，我把它們放在一起是有原因的。原因是：邏輯回歸和不帶核函數(shù)的支持向量機(jī)它們都是非常相似的算法，不管是邏輯回歸還是不帶核函數(shù)的SVM，通常都會(huì)做相似的事情，并給出相似的結(jié)果。但是根據(jù)你實(shí)現(xiàn)的情況，其中一個(gè)可能會(huì)比另一個(gè)更加有效。但是在其中一個(gè)算法應(yīng)用的地方，邏輯回歸或不帶核函數(shù)的SVM另一個(gè)也很有可能很有效。但是隨著SVM的復(fù)雜度增加，當(dāng)你使用不同的內(nèi)核函數(shù)來學(xué)習(xí)復(fù)雜的非線性函數(shù)時(shí)，這個(gè)體系，你知道的，當(dāng)你有多達(dá) 1 萬（10,000）的樣本時(shí)，也可能是 5 萬（50,000），你的特征變量的數(shù)量這是相當(dāng)大的。那是一個(gè)非常常見的體系，也許在這個(gè)體系里，不帶核函數(shù)的支持向量機(jī)就會(huì)表現(xiàn)得相當(dāng)突出。你可以做比這困難得多需要邏輯回歸的事情。
最后，神經(jīng)網(wǎng)絡(luò)使用于什么時(shí)候呢？對(duì)于所有的這些問題，對(duì)于所有的這些不同體系一個(gè)設(shè)計(jì)得很好的神經(jīng)網(wǎng)絡(luò)也很有可能會(huì)非常有效。有一個(gè)缺點(diǎn)是，或者說是有時(shí)可能不會(huì)使用神經(jīng)網(wǎng)絡(luò)的原因是：對(duì)于許多這樣的問題，神經(jīng)網(wǎng)絡(luò)訓(xùn)練起來可能會(huì)特別慢，但是如果你有一個(gè)非常好的SVM實(shí)現(xiàn)包，它可能會(huì)運(yùn)行得比較快比神經(jīng)網(wǎng)絡(luò)快很多，盡管我們?cè)诖酥皼]有展示，但是事實(shí)證明，SVM具有的優(yōu)化問題，是一種凸優(yōu)化問題。因此，好的SVM優(yōu)化軟件包總是會(huì)找到全局最小值，或者接近它的值。對(duì)于SVM你不需要擔(dān)心局部最優(yōu)。在實(shí)際應(yīng)用中，局部最優(yōu)不是神經(jīng)網(wǎng)絡(luò)所需要解決的一個(gè)重大問題，所以這是你在使用SVM的時(shí)候不需要太去擔(dān)心的一個(gè)問題。根據(jù)你的問題，神經(jīng)網(wǎng)絡(luò)可能會(huì)比SVM慢，尤其是在這樣一個(gè)體系中，至于這里給出的參考，看上去有些模糊，如果你在考慮一些問題，這些參考會(huì)有一些模糊，但是我仍然不能完全確定，我是該用這個(gè)算法還是改用那個(gè)算法，這個(gè)沒有太大關(guān)系，當(dāng)我遇到機(jī)器學(xué)習(xí)問題的時(shí)候，有時(shí)它確實(shí)不清楚這是否是最好的算法，但是就如在之前的視頻中看到的算法確實(shí)很重要。但是通常更加重要的是：你有多少數(shù)據(jù)，你有多熟練是否擅長(zhǎng)做誤差分析和排除學(xué)習(xí)算法，指出如何設(shè)定新的特征變量和找出其他能決定你學(xué)習(xí)算法的變量等方面，通常這些方面會(huì)比你使用邏輯回歸還是SVM這方面更加重要。但是，已經(jīng)說過了，SVM仍然被廣泛認(rèn)為是一種最強(qiáng)大的學(xué)習(xí)算法，這是一個(gè)體系，包含了什么時(shí)候一個(gè)有效的方法去學(xué)習(xí)復(fù)雜的非線性函數(shù)。因此，實(shí)際上與邏輯回歸、神經(jīng)網(wǎng)絡(luò)、SVM一起使用這些方法來提高學(xué)習(xí)算法，我認(rèn)為你會(huì)很好地建立很有技術(shù)的狀態(tài)。（編者注：當(dāng)時(shí)GPU計(jì)算比較慢，神經(jīng)網(wǎng)絡(luò)還不流行。）
機(jī)器學(xué)習(xí)系統(tǒng)對(duì)于一個(gè)寬泛的應(yīng)用領(lǐng)域來說，這是另一個(gè)在你軍械庫里非常強(qiáng)大的工具，你可以把它應(yīng)用到很多地方，如硅谷、在工業(yè)、學(xué)術(shù)等領(lǐng)域建立許多高性能的機(jī)器學(xué)習(xí)系統(tǒng)。
代碼部分
機(jī)器學(xué)習(xí)練習(xí) 3 - 支持向量機(jī)
代碼修改并注釋：黃海廣，haiguang2000@qq.com
在本練習(xí)中，我們將使用支持向量機(jī)（SVM）來構(gòu)建垃圾郵件分類器。我們將從一些簡(jiǎn)單的 2D 數(shù)據(jù)集開始使用 SVM 來查看它們的工作原理。然后，我們將對(duì)一組原始電子郵件進(jìn)行一些預(yù)處理工作，并使用 SVM 在處理的電子郵件上構(gòu)建分類器，以確定它們是否為垃圾郵件。
我們要做的第一件事是看一個(gè)簡(jiǎn)單的二維數(shù)據(jù)集，看看線性 SVM 如何對(duì)數(shù)據(jù)集進(jìn)行不同的 C 值（類似于線性/邏輯回歸中的正則化項(xiàng)）。
import numpy as np import pandas as pd import matplotlib.pyplot as plt import seaborn as sb from scipy.io import loadmatraw_data = loadmat('data/ex6data1.mat')我們將其用散點(diǎn)圖表示，其中類標(biāo)簽由符號(hào)表示（+表示正類，o 表示負(fù)類）。
data = pd.DataFrame(raw_data['X'], columns=['X1', 'X2']) data['y'] = raw_data['y']positive = data[data['y'].isin([1])] negative = data[data['y'].isin([0])]fig, ax = plt.subplots(figsize=(12, 8)) ax.scatter(positive['X1'], positive['X2'], s=50, marker='x', label='Positive') ax.scatter(negative['X1'], negative['X2'], s=50, marker='o', label='Negative') ax.legend() plt.show()請(qǐng)注意，還有一個(gè)異常的正例在其他樣本之外。這些類仍然是線性分離的，但它非常緊湊。我們要訓(xùn)練線性支持向量機(jī)來學(xué)習(xí)類邊界。在這個(gè)練習(xí)中，我們沒有從頭開始執(zhí)行 SVM 的任務(wù)，所以我要用 scikit-learn。
from sklearn import svm svc = svm.LinearSVC(C=1, loss='hinge', max_iter=1000) svc LinearSVC(C=1, class_weight=None, dual=True, fit_intercept=True,intercept_scaling=1, loss='hinge', max_iter=1000, multi_class='ovr',penalty='l2', random_state=None, tol=0.0001, verbose=0)首先，我們使用 C=1 看下結(jié)果如何。
svc.fit(data[['X1', 'X2']], data['y']) svc.score(data[['X1', 'X2']], data['y']) 0.9803921568627451其次，讓我們看看如果 C 的值越大，會(huì)發(fā)生什么
svc2 = svm.LinearSVC(C=100, loss='hinge', max_iter=1000) svc2.fit(data[['X1', 'X2']], data['y']) svc2.score(data[['X1', 'X2']], data['y']) 1.0這次我們得到了訓(xùn)練數(shù)據(jù)的完美分類，但是通過增加 C 的值，我們創(chuàng)建了一個(gè)不再適合數(shù)據(jù)的決策邊界。我們可以通過查看每個(gè)類別預(yù)測(cè)的置信水平來看出這一點(diǎn)，這是該點(diǎn)與超平面距離的函數(shù)。
data['SVM 1 Confidence'] = svc.decision_function(data[['X1', 'X2']])fig, ax = plt.subplots(figsize=(12,8)) ax.scatter(data['X1'], data['X2'], s=50, c=data['SVM 1 Confidence'], cmap='seismic') ax.set_title('SVM (C=1) Decision Confidence') plt.show() data['SVM 2 Confidence'] = svc2.decision_function(data[['X1', 'X2']])fig, ax = plt.subplots(figsize=(12,8)) ax.scatter(data['X1'], data['X2'], s=50, c=data['SVM 2 Confidence'], cmap='seismic') ax.set_title('SVM (C=100) Decision Confidence') plt.show()可以看看靠近邊界的點(diǎn)的顏色，區(qū)別是有點(diǎn)微妙。如果您在練習(xí)文本中，則會(huì)出現(xiàn)繪圖，其中決策邊界在圖上顯示為一條線，有助于使差異更清晰。
現(xiàn)在我們將從線性 SVM 轉(zhuǎn)移到能夠使用內(nèi)核進(jìn)行非線性分類的 SVM。我們首先負(fù)責(zé)實(shí)現(xiàn)一個(gè)高斯核函數(shù)。雖然 scikit-learn 具有內(nèi)置的高斯內(nèi)核，但為了實(shí)現(xiàn)更清楚，我們將從頭開始實(shí)現(xiàn)。
def gaussian_kernel(x1, x2, sigma):return np.exp(-(np.sum((x1 - x2)**2) / (2 * (sigma**2)))) x1 = np.array([1.0, 2.0, 1.0]) x2 = np.array([0.0, 4.0, -1.0]) sigma = 2 gaussian_kernel(x1, x2, sigma) 0.32465246735834974該結(jié)果與練習(xí)中的預(yù)期值相符。接下來，我們將檢查另一個(gè)數(shù)據(jù)集，這次用非線性決策邊界。
raw_data = loadmat('data/ex6data2.mat')data = pd.DataFrame(raw_data['X'], columns=['X1', 'X2']) data['y'] = raw_data['y']positive = data[data['y'].isin([1])] negative = data[data['y'].isin([0])]fig, ax = plt.subplots(figsize=(12, 8)) ax.scatter(positive['X1'], positive['X2'], s=30, marker='x', label='Positive') ax.scatter(negative['X1'], negative['X2'], s=30, marker='o', label='Negative') ax.legend() plt.show()對(duì)于該數(shù)據(jù)集，我們將使用內(nèi)置的 RBF 內(nèi)核構(gòu)建支持向量機(jī)分類器，并檢查其對(duì)訓(xùn)練數(shù)據(jù)的準(zhǔn)確性。為了可視化決策邊界，這一次我們將根據(jù)實(shí)例具有負(fù)類標(biāo)簽的預(yù)測(cè)概率來對(duì)點(diǎn)做陰影。從結(jié)果可以看出，它們大部分是正確的。
svc = svm.SVC(C=100, gamma=10, probability=True) svc SVC(C=100, cache_size=200, class_weight=None, coef0=0.0,decision_function_shape='ovr', degree=3, gamma=10, kernel='rbf',max_iter=-1, probability=True, random_state=None, shrinking=True,tol=0.001, verbose=False) svc.fit(data[['X1', 'X2']], data['y']) svc.score(data[['X1', 'X2']], data['y']) 0.9698725376593279 data['Probability'] = svc.predict_proba(data[['X1', 'X2']])[:,0] fig,?ax?=?plt.subplots(figsize=(12,8)) ax.scatter(data['X1'], data['X2'], s=30, c=data['Probability'], cmap='Reds') plt.show()對(duì)于第三個(gè)數(shù)據(jù)集，我們給出了訓(xùn)練和驗(yàn)證集，并且基于驗(yàn)證集性能為 SVM 模型找到最優(yōu)超參數(shù)。雖然我們可以使用 scikit-learn 的內(nèi)置網(wǎng)格搜索來做到這一點(diǎn)，但是本著遵循練習(xí)的目的，我們將從頭開始實(shí)現(xiàn)一個(gè)簡(jiǎn)單的網(wǎng)格搜索。
raw_data = loadmat('data/ex6data3.mat') X?=?raw_data['X'] Xval = raw_data['Xval'] y = raw_data['y'].ravel() yval = raw_data['yval'].ravel()C_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100] gamma_values = [0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30, 100]best_score = 0 best_params = {'C': None, 'gamma': None}for C in C_values:for gamma in gamma_values:svc = svm.SVC(C=C, gamma=gamma)svc.fit(X, y)score = svc.score(Xval, yval)if score > best_score:best_score = scorebest_params['C'] = Cbest_params['gamma'] = gammabest_score, best_params (0.965, {'C': 0.3, 'gamma': 100})大間隔分類器
from sklearn.svm import SVC from sklearn import datasets import matplotlib as mpl import matplotlib.pyplot as plt mpl.rc('axes', labelsize=14) mpl.rc('xtick', labelsize=12) mpl.rc('ytick', labelsize=12) iris = datasets.load_iris() X = iris["data"][:, (2, 3)] # petal length, petal width y = iris["target"]setosa_or_versicolor = (y == 0) | (y == 1) X = X[setosa_or_versicolor] y = y[setosa_or_versicolor]# SVM Classifier model svm_clf = SVC(kernel="linear", C=float("inf")) svm_clf.fit(X, y) SVC(C=inf, cache_size=200, class_weight=None, coef0=0.0,decision_function_shape='ovr', degree=3, gamma='auto_deprecated',kernel='linear', max_iter=-1, probability=False, random_state=None,shrinking=True, tol=0.001, verbose=False) # Bad models x0 = np.linspace(0, 5.5, 200) pred_1 = 5*x0 - 20 pred_2 = x0 - 1.8 pred_3 = 0.1 * x0 + 0.5 def plot_svc_decision_boundary(svm_clf, xmin, xmax):w = svm_clf.coef_[0]b = svm_clf.intercept_[0]# At the decision boundary, w0*x0 + w1*x1 + b = 0# => x1 = -w0/w1 * x0 - b/w1x0 = np.linspace(xmin, xmax, 200)decision_boundary = -w[0]/w[1] * x0 - b/w[1]margin = 1/w[1]gutter_up = decision_boundary + margingutter_down = decision_boundary - marginsvs = svm_clf.support_vectors_plt.scatter(svs[:, 0], svs[:, 1], s=180, facecolors='#FFAAAA')plt.plot(x0, decision_boundary, "k-", linewidth=2)plt.plot(x0, gutter_up, "k--", linewidth=2)plt.plot(x0, gutter_down, "k--", linewidth=2)plt.figure(figsize=(12,2.7))plt.subplot(121) plt.plot(x0, pred_1, "g--", linewidth=2) plt.plot(x0, pred_2, "m-", linewidth=2) plt.plot(x0, pred_3, "r-", linewidth=2) plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs", label="Iris-Versicolor") plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo", label="Iris-Setosa") plt.xlabel("Petal length", fontsize=14) plt.ylabel("Petal width", fontsize=14) plt.legend(loc="upper left", fontsize=14) plt.axis([0, 5.5, 0, 2])plt.subplot(122) plot_svc_decision_boundary(svm_clf, 0, 5.5) plt.plot(X[:, 0][y==1], X[:, 1][y==1], "bs") plt.plot(X[:, 0][y==0], X[:, 1][y==0], "yo") plt.xlabel("Petal length", fontsize=14) plt.axis([0, 5.5, 0, 2])plt.show()特征縮放的敏感性
Xs = np.array([[1, 50], [5, 20], [3, 80], [5, 60]]).astype(np.float64) ys = np.array([0, 0, 1, 1]) svm_clf = SVC(kernel="linear", C=100) svm_clf.fit(Xs, ys)plt.figure(figsize=(12,3.2)) plt.subplot(121) plt.plot(Xs[:, 0][ys==1], Xs[:, 1][ys==1], "bo") plt.plot(Xs[:, 0][ys==0], Xs[:, 1][ys==0], "ms") plot_svc_decision_boundary(svm_clf, 0, 6) plt.xlabel("$x_0$", fontsize=20) plt.ylabel("$x_1$ ", fontsize=20, rotation=0) plt.title("Unscaled", fontsize=16) plt.axis([0, 6, 0, 90])from sklearn.preprocessing import StandardScaler scaler = StandardScaler() X_scaled = scaler.fit_transform(Xs) svm_clf.fit(X_scaled, ys)plt.subplot(122) plt.plot(X_scaled[:, 0][ys==1], X_scaled[:, 1][ys==1], "bo") plt.plot(X_scaled[:, 0][ys==0], X_scaled[:, 1][ys==0], "ms") plot_svc_decision_boundary(svm_clf, -2, 2) plt.xlabel("$x_0$", fontsize=20) plt.title("Scaled", fontsize=16) plt.axis([-2, 2, -2, 2]) plt.show()硬間隔和軟間隔分類
X_outliers = np.array([[3.4, 1.3], [3.2, 0.8]]) y_outliers = np.array([0, 0]) Xo1 = np.concatenate([X, X_outliers[:1]], axis=0) yo1 = np.concatenate([y, y_outliers[:1]], axis=0) Xo2 = np.concatenate([X, X_outliers[1:]], axis=0) yo2 = np.concatenate([y, y_outliers[1:]], axis=0)svm_clf2 = SVC(kernel="linear", C=10**9) svm_clf2.fit(Xo2, yo2)plt.figure(figsize=(12, 2.7))plt.subplot(121) plt.plot(Xo1[:, 0][yo1 == 1], Xo1[:, 1][yo1 == 1], "bs") plt.plot(Xo1[:, 0][yo1 == 0], Xo1[:, 1][yo1 == 0], "yo") plt.text(0.3, 1.0, "Impossible!", fontsize=24, color="red") plt.xlabel("Petal length", fontsize=14) plt.ylabel("Petal width", fontsize=14) plt.annotate("Outlier",xy=(X_outliers[0][0], X_outliers[0][1]),xytext=(2.5, 1.7),ha="center",arrowprops=dict(facecolor='black', shrink=0.1),fontsize=16, ) plt.axis([0, 5.5, 0, 2])plt.subplot(122) plt.plot(Xo2[:, 0][yo2 == 1], Xo2[:, 1][yo2 == 1], "bs") plt.plot(Xo2[:, 0][yo2 == 0], Xo2[:, 1][yo2 == 0], "yo") plot_svc_decision_boundary(svm_clf2, 0, 5.5) plt.xlabel("Petal length", fontsize=14) plt.annotate("Outlier",xy=(X_outliers[1][0], X_outliers[1][1]),xytext=(3.2, 0.08),ha="center",arrowprops=dict(facecolor='black', shrink=0.1),fontsize=16, ) plt.axis([0, 5.5, 0, 2])plt.show() from sklearn.pipeline import Pipeline from sklearn.datasets import make_moons X, y = make_moons(n_samples=100, noise=0.15, random_state=42) def plot_predictions(clf, axes):x0s = np.linspace(axes[0], axes[1], 100)x1s = np.linspace(axes[2], axes[3], 100)x0, x1 = np.meshgrid(x0s, x1s)X = np.c_[x0.ravel(), x1.ravel()]y_pred = clf.predict(X).reshape(x0.shape)y_decision = clf.decision_function(X).reshape(x0.shape)plt.contourf(x0, x1, y_pred, cmap=plt.cm.brg, alpha=0.2)plt.contourf(x0, x1, y_decision, cmap=plt.cm.brg, alpha=0.1) def plot_dataset(X, y, axes):plt.plot(X[:, 0][y == 0], X[:, 1][y == 0], "bs")plt.plot(X[:, 0][y == 1], X[:, 1][y == 1], "g^")plt.axis(axes)plt.grid(True, which='both')plt.xlabel(r"$x_1$", fontsize=20)plt.ylabel(r"$x_2$", fontsize=20, rotation=0) from sklearn.svm import SVC gamma1, gamma2 = 0.1, 5 C1, C2 = 0.001, 1000 hyperparams = (gamma1, C1), (gamma1, C2), (gamma2, C1), (gamma2, C2)svm_clfs = [] for gamma, C in hyperparams:rbf_kernel_svm_clf = Pipeline([("scaler", StandardScaler()),("svm_clf",SVC(kernel="rbf", gamma=gamma, C=C))])rbf_kernel_svm_clf.fit(X, y)svm_clfs.append(rbf_kernel_svm_clf)plt.figure(figsize=(12, 7))for i, svm_clf in enumerate(svm_clfs):plt.subplot(221 + i)plot_predictions(svm_clf, [-1.5, 2.5, -1, 1.5])plot_dataset(X, y, [-1.5, 2.5, -1, 1.5])gamma, C = hyperparams[i]plt.title(r"$\gamma = {}, C = {}$".format(gamma, C), fontsize=12)plt.show()svm 推導(dǎo)（統(tǒng)計(jì)學(xué)習(xí)方法）
1．支持向量機(jī)最簡(jiǎn)單的情況是線性可分支持向量機(jī)，或硬間隔支持向量機(jī)。構(gòu)建它的條件是訓(xùn)練數(shù)據(jù)線性可分。其學(xué)習(xí)策略是最大間隔法。可以表示為凸二次規(guī)劃問題，其原始最優(yōu)化問題為
求得最優(yōu)化問題的解為，，得到線性可分支持向量機(jī)，分離超平面是
分類決策函數(shù)是
最大間隔法中，函數(shù)間隔與幾何間隔是重要的概念。
線性可分支持向量機(jī)的最優(yōu)解存在且唯一。位于間隔邊界上的實(shí)例點(diǎn)為支持向量。最優(yōu)分離超平面由支持向量完全決定。 二次規(guī)劃問題的對(duì)偶問題是
通常，通過求解對(duì)偶問題學(xué)習(xí)線性可分支持向量機(jī)，即首先求解對(duì)偶問題的最優(yōu)值
，然后求最優(yōu)值和，得出分離超平面和分類決策函數(shù)。
2．現(xiàn)實(shí)中訓(xùn)練數(shù)據(jù)是線性可分的情形較少，訓(xùn)練數(shù)據(jù)往往是近似線性可分的，這時(shí)使用線性支持向量機(jī)，或軟間隔支持向量機(jī)。線性支持向量機(jī)是最基本的支持向量機(jī)。
對(duì)于噪聲或例外，通過引入松弛變量，使其“可分”，得到線性支持向量機(jī)學(xué)習(xí)的凸二次規(guī)劃問題，其原始最優(yōu)化問題是
求解原始最優(yōu)化問題的解和，得到線性支持向量機(jī)，其分離超平面為
分類決策函數(shù)為
線性可分支持向量機(jī)的解唯一但不唯一。對(duì)偶問題是
線性支持向量機(jī)的對(duì)偶學(xué)習(xí)算法，首先求解對(duì)偶問題得到最優(yōu)解，然后求原始問題最優(yōu)解和，得出分離超平面和分類決策函數(shù)。
對(duì)偶問題的解中滿的實(shí)例點(diǎn)稱為支持向量。支持向量可在間隔邊界上，也可在間隔邊界與分離超平面之間，或者在分離超平面誤分一側(cè)。最優(yōu)分離超平面由支持向量完全決定。
線性支持向量機(jī)學(xué)習(xí)等價(jià)于最小化二階范數(shù)正則化的合頁函數(shù)
3．非線性支持向量機(jī)
對(duì)于輸入空間中的非線性分類問題，可以通過非線性變換將它轉(zhuǎn)化為某個(gè)高維特征空間中的線性分類問題，在高維特征空間中學(xué)習(xí)線性支持向量機(jī)。由于在線性支持向量機(jī)學(xué)習(xí)的對(duì)偶問題里，目標(biāo)函數(shù)和分類決策函數(shù)都只涉及實(shí)例與實(shí)例之間的內(nèi)積，所以不需要顯式地指定非線性變換，而是用核函數(shù)來替換當(dāng)中的內(nèi)積。核函數(shù)表示，通過一個(gè)非線性轉(zhuǎn)換后的兩個(gè)實(shí)例間的內(nèi)積。具體地，是一個(gè)核函數(shù)，或正定核，意味著存在一個(gè)從輸入空間 x 到特征空間的映射，對(duì)任意，有
對(duì)稱函數(shù)
，任意正整數(shù)，對(duì)稱函數(shù)對(duì)應(yīng)的 Gram 矩陣是半正定的。所以，在線性支持向量機(jī)學(xué)習(xí)的對(duì)偶問題中，用核函數(shù)替代內(nèi)積，求解得到的就是非線性支持向量機(jī)
4．SMO 算法
SMO 算法是支持向量機(jī)學(xué)習(xí)的一種快速算法，其特點(diǎn)是不斷地將原二次規(guī)劃問題分解為只有兩個(gè)變量的二次規(guī)劃子問題，并對(duì)子問題進(jìn)行解析求解，直到所有變量滿足 KKT 條件為止。這樣通過啟發(fā)式的方法得到原二次規(guī)劃問題的最優(yōu)解。因?yàn)樽訂栴}有解析解，所以每次計(jì)算子問題都很快，雖然計(jì)算子問題次數(shù)很多，但在總體上還是高效的。
分離超平面：
點(diǎn)到直線距離：
為 2-范數(shù)：
直線為超平面，樣本可表示為：
margin：
函數(shù)間隔：
幾何間隔：，當(dāng)數(shù)據(jù)被正確分類時(shí)，幾何間隔就是點(diǎn)到超平面的距離
為了求幾何間隔最大，SVM 基本問題可以轉(zhuǎn)化為求解:(為幾何間隔，(為函數(shù)間隔)
分類點(diǎn)幾何間隔最大，同時(shí)被正確分類。但這個(gè)方程并非凸函數(shù)求解，所以要先 ① 將方程轉(zhuǎn)化為凸函數(shù)，② 用拉格朗日乘子法和 KKT 條件求解對(duì)偶問題。
① 轉(zhuǎn)化為凸函數(shù)：
先令，方便計(jì)算（參照衡量，不影響評(píng)價(jià)結(jié)果）
再將轉(zhuǎn)化成求解凸函數(shù)，1/2 是為了求導(dǎo)之后方便計(jì)算。
② 用拉格朗日乘子法和 KKT 條件求解最優(yōu)值：
整合成：
推導(dǎo)：
根據(jù) KKT 條件：
代入
再把 max 問題轉(zhuǎn)成 min 問題：
以上為 SVM 對(duì)偶問題的對(duì)偶形式
kernel
在低維空間計(jì)算獲得高維空間的計(jì)算結(jié)果，也就是說計(jì)算結(jié)果滿足高維（滿足高維，才能說明高維下線性可分）。
soft margin & slack variable
引入松弛變量，對(duì)應(yīng)數(shù)據(jù)點(diǎn)允許偏離的 functional margin 的量。
目標(biāo)函數(shù)：
對(duì)偶問題：
Sequential Minimal Optimization
首先定義特征到結(jié)果的輸出函數(shù)：.
因?yàn)?/p>
有
import?numpy?as?np import pandas as pd from sklearn.datasets import load_iris from sklearn.model_selection import train_test_split import matplotlib.pyplot as plt %matplotlib inline # data def create_data():iris = load_iris()df = pd.DataFrame(iris.data, columns=iris.feature_names)df['label'] = iris.targetdf.columns = ['sepal length', 'sepal width', 'petal length', 'petal width', 'label']data = np.array(df.iloc[:100, [0, 1, -1]])for i in range(len(data)):if data[i,-1] == 0:data[i,-1] = -1# print(data)return data[:,:2], data[:,-1] X, y = create_data() X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.25) plt.scatter(X[:50,0],X[:50,1], label='0') plt.scatter(X[50:,0],X[50:,1], label='1') plt.legend() class SVM:def __init__(self, max_iter=100, kernel='linear'):self.max_iter = max_iterself._kernel = kerneldef init_args(self, features, labels):self.m, self.n = features.shapeself.X = featuresself.Y = labelsself.b = 0.0# 將Ei保存在一個(gè)列表里self.alpha = np.ones(self.m)self.E = [self._E(i) for i in range(self.m)]# 松弛變量self.C = 1.0def _KKT(self, i):y_g = self._g(i) * self.Y[i]if self.alpha[i] == 0:return y_g >= 1elif 0 < self.alpha[i] < self.C:return y_g == 1else:return y_g <= 1# g(x)預(yù)測(cè)值，輸入xi（X[i]）def _g(self, i):r = self.bfor j in range(self.m):r += self.alpha[j] * self.Y[j] * self.kernel(self.X[i], self.X[j])return r# 核函數(shù)def kernel(self, x1, x2):if self._kernel == 'linear':return sum([x1[k] * x2[k] for k in range(self.n)])elif self._kernel == 'poly':return (sum([x1[k] * x2[k] for k in range(self.n)]) + 1)**2return 0# E（x）為g(x)對(duì)輸入x的預(yù)測(cè)值和y的差def _E(self, i):return self._g(i) - self.Y[i]def _init_alpha(self):# 外層循環(huán)首先遍歷所有滿足0<a<C的樣本點(diǎn)，檢驗(yàn)是否滿足KKTindex_list = [i for i in range(self.m) if 0 < self.alpha[i] < self.C]# 否則遍歷整個(gè)訓(xùn)練集non_satisfy_list = [i for i in range(self.m) if i not in index_list]index_list.extend(non_satisfy_list)for i in index_list:if self._KKT(i):continueE1 = self.E[i]# 如果E2是+，選擇最小的；如果E2是負(fù)的，選擇最大的if E1 >= 0:j = min(range(self.m), key=lambda x: self.E[x])else:j = max(range(self.m), key=lambda x: self.E[x])return i, jdef _compare(self, _alpha, L, H):if _alpha > H:return Helif _alpha < L:return Lelse:return _alphadef fit(self, features, labels):self.init_args(features, labels)for t in range(self.max_iter):# traini1, i2 = self._init_alpha()# 邊界if self.Y[i1] == self.Y[i2]:L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)H = min(self.C, self.alpha[i1] + self.alpha[i2])else:L = max(0, self.alpha[i2] - self.alpha[i1])H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])E1 = self.E[i1]E2 = self.E[i2]# eta=K11+K22-2K12eta = self.kernel(self.X[i1], self.X[i1]) + self.kernel(self.X[i2],self.X[i2]) - 2 * self.kernel(self.X[i1], self.X[i2])if eta <= 0:# print('eta <= 0')continuealpha2_new_unc = self.alpha[i2] + self.Y[i2] * (E1 - E2) / eta #此處有修改，根據(jù)書上應(yīng)該是E1 - E2，書上130-131頁alpha2_new = self._compare(alpha2_new_unc, L, H)alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (self.alpha[i2] - alpha2_new)b1_new = -E1 - self.Y[i1] * self.kernel(self.X[i1], self.X[i1]) * (alpha1_new - self.alpha[i1]) - self.Y[i2] * self.kernel(self.X[i2],self.X[i1]) * (alpha2_new - self.alpha[i2]) + self.bb2_new = -E2 - self.Y[i1] * self.kernel(self.X[i1], self.X[i2]) * (alpha1_new - self.alpha[i1]) - self.Y[i2] * self.kernel(self.X[i2],self.X[i2]) * (alpha2_new - self.alpha[i2]) + self.bif 0 < alpha1_new < self.C:b_new = b1_newelif 0 < alpha2_new < self.C:b_new = b2_newelse:# 選擇中點(diǎn)b_new = (b1_new + b2_new) / 2# 更新參數(shù)self.alpha[i1] = alpha1_newself.alpha[i2] = alpha2_newself.b = b_newself.E[i1] = self._E(i1)self.E[i2] = self._E(i2)return 'train done!'def predict(self, data):r = self.bfor i in range(self.m):r += self.alpha[i] * self.Y[i] * self.kernel(data, self.X[i])return 1 if r > 0 else -1def score(self, X_test, y_test):right_count = 0for i in range(len(X_test)):result = self.predict(X_test[i])if result == y_test[i]:right_count += 1return right_count / len(X_test)def _weight(self):# linear modelyx = self.Y.reshape(-1, 1) * self.Xself.w = np.dot(yx.T, self.alpha)return self.w svm = SVM(max_iter=100) svm.fit(X_train, y_train) 'train done!' svm.score(X_test, y_test) 0.48參考資料
[1]機(jī)器學(xué)習(xí)課程:?https://www.coursera.org/course/ml
[2]《統(tǒng)計(jì)學(xué)習(xí)方法》:?https://www.coursera.org/course/ml
[3]黃海廣:?https://github.com/fengdu78
[4]:[Lagrange Multiplier and KKT: http://blog.csdn.net/xianlingmao/article/details/7919597
[5]:[推導(dǎo)SVM: https://my.oschina.net/dfsj66011/blog/517766
[6]:[機(jī)器學(xué)習(xí)算法實(shí)踐-支持向量機(jī)(SVM)算法原理: http://pytlab.org/2017/08/15/%E6%9C%BA%E5%99%A8%E5%AD%A6%E4%B9%A0%E7%AE%97%E6%B3%95%E5%AE%9E%E8%B7%B5-%E6%94%AF%E6%8C%81%E5%90%91%E9%87%8F%E6%9C%BA-SVM-%E7%AE%97%E6%B3%95%E5%8E%9F%E7%90%86/
[7]?:[Python實(shí)現(xiàn)SVM: http://blog.csdn.net/wds2006sdo/article/details/53156589
關(guān)于本站
“機(jī)器學(xué)習(xí)初學(xué)者”公眾號(hào)由是黃海廣博士創(chuàng)建，黃博個(gè)人知乎粉絲23000+，github排名全球前100名（32000+）。本公眾號(hào)致力于人工智能方向的科普性文章，為初學(xué)者提供學(xué)習(xí)路線和基礎(chǔ)資料。原創(chuàng)作品有：吳恩達(dá)機(jī)器學(xué)習(xí)個(gè)人筆記、吳恩達(dá)深度學(xué)習(xí)筆記等。
往期精彩回顧
那些年做的學(xué)術(shù)公益-你不是一個(gè)人在戰(zhàn)斗
適合初學(xué)者入門人工智能的路線及資料下載
吳恩達(dá)機(jī)器學(xué)習(xí)課程筆記及資源（github標(biāo)星12000+，提供百度云鏡像）
吳恩達(dá)深度學(xué)習(xí)筆記及視頻等資源（github標(biāo)星8500+，提供百度云鏡像）
《統(tǒng)計(jì)學(xué)習(xí)方法》的python代碼實(shí)現(xiàn)（github標(biāo)星7200+）
備注：加入本站微信群或者qq群，請(qǐng)回復(fù)“加群”
加入知識(shí)星球（4300+用戶，ID：92416895），請(qǐng)回復(fù)“知識(shí)星球”
總結(jié)
以上是生活随笔為你收集整理的经典算法解读：一文看懂支持向量机以及推导的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 收藏！！如何 Get 机器学习必备的算法
- 下一篇： 【CTR预估】CTR模型如何加入稠密连续