Ng第十二课：支持向量机(Support Vector Machines)（一）
1 目錄
支持向量機(jī)基本上是最好的有監(jiān)督學(xué)習(xí)算法了，從logistic回歸出發(fā)，引出了SVM，揭示模型間的聯(lián)系，過渡自然。
?
2 重新審視logistic回歸
Logistic回歸目的是從特征學(xué)習(xí)出一個(gè)0/1分類模型，而這個(gè)模型是將特征的線性組合作為自變量，由于自變量的取值范圍是負(fù)無窮到正無窮。因此，使用logistic函數(shù)（或稱作sigmoid函數(shù)）將自變量映射到(0,1)上，映射后的值被認(rèn)為是屬于y=1的概率。
假設(shè)函數(shù)其中x是n維特征向量，函數(shù)g就是logistic函數(shù)。的圖像是
可以看到，將無窮映射到了(0,1)。
假設(shè)函數(shù)就是特征屬于y=1的概率。
?
當(dāng)要判別一個(gè)新來的特征屬于哪個(gè)類時(shí)，只需求，若大于0.5就是y=1的類，反之屬于y=0類。
再審視一下，發(fā)現(xiàn)只和有關(guān)，>0，那么，g(z)只不過是用來映射，真實(shí)的類別決定權(quán)還在。還有當(dāng)時(shí)，=1，反之=0。如果只從出發(fā)，希望模型達(dá)到的目標(biāo)無非就是讓訓(xùn)練數(shù)據(jù)中y=1的特征，y=0的特征。Logistic回歸就是要學(xué)習(xí)得到，使得正例的特征遠(yuǎn)大于0，負(fù)例的特征遠(yuǎn)小于0，強(qiáng)調(diào)在全部訓(xùn)練實(shí)例上達(dá)到這個(gè)目標(biāo)。
圖形化表示如下：
中間那條線是，logistic回顧強(qiáng)調(diào)所有點(diǎn)盡可能地遠(yuǎn)離中間那條線。學(xué)習(xí)出的結(jié)果也就中間那條線。考慮上面3個(gè)點(diǎn)A、B和C。從圖中可以確定A是×類別的，然而C我們是不太確定的，B還算能夠確定。這樣可以得出結(jié)論，我們更應(yīng)該關(guān)心靠近中間分割線的點(diǎn)，讓他們盡可能地遠(yuǎn)離中間線，而不是在所有點(diǎn)上達(dá)到最優(yōu)。這大概就是支持向量機(jī)的思路和logistic回歸的不同點(diǎn)。
?
3 形式化表示
? ? 這次使用的結(jié)果標(biāo)簽是y=-1,y=1替換在logistic回歸中使用的y=0和y=1。同時(shí)將替換成w和b（0）。以前的，其中認(rèn)為，替換為b，后面替換為（即）。這樣，我們讓，進(jìn)一步?= hw,b（x）。
再明確下假設(shè)函數(shù)?
上一節(jié)提到過只需考慮的正負(fù)問題，而不用關(guān)心g(z)，因此這里將g(z)做一個(gè)簡化，將其簡單映射到y(tǒng)=-1和y=1上。映射關(guān)系如下：
?
4 函數(shù)間隔和幾何間隔
給定一個(gè)訓(xùn)練樣本，x是特征，y是結(jié)果標(biāo)簽。i表示第i個(gè)樣本。定義函數(shù)間隔如下：
?? （每個(gè)點(diǎn)相距距離）
? ? 當(dāng)時(shí)，又（直線圖的例子全在第一象限），的值實(shí)際上就是（該情況下永為正值）。反之亦然（-1）。為了使函數(shù)間隔最大（更大的信心確定該例是正例還是反例），當(dāng)時(shí)，應(yīng)該是個(gè)大正數(shù)，反之是個(gè)大負(fù)數(shù)。因此函數(shù)間隔代表了我們認(rèn)為特征是正例還是反例的確信度。
? ?繼續(xù)考慮w和b，如果同時(shí)加大w和b，比如在前面乘個(gè)系數(shù)比如2，那么所有點(diǎn)的函數(shù)間隔都會(huì)增大二倍，這個(gè)對求解問題來說不應(yīng)該有影響，因?yàn)槲覀円蠼獾氖?#xff08;那根直線），同時(shí)擴(kuò)大w和b對結(jié)果是無影響的。這樣，但也要限制w和b，可能需要加入歸一化條件，畢竟求解的目標(biāo)是確定唯一一個(gè)w和b，而不是多組線性相關(guān)的向量。這個(gè)歸一化一會(huì)再考慮。
剛剛我們定義的函數(shù)間隔是針對某一個(gè)樣本的，現(xiàn)在我們定義全局樣本上的函數(shù)間隔
? ，說白了就是在訓(xùn)練樣本上分類正例和負(fù)例確信度最小那個(gè)函數(shù)間隔。
?
接下來定義幾何間隔，先看圖
? ? 假設(shè)我們有了B點(diǎn)所在的分割面。任何其他一點(diǎn)，比如A到該面的距離以表示，假設(shè)B就是A在分割面上的投影。我們知道向量BA的方向是（分割面的梯度），單位向量是。A點(diǎn)是，所以B點(diǎn)是x=（利用初中的幾何知識），帶入得，
進(jìn)一步得到
實(shí)際上就是點(diǎn)到平面距離。
再換種更加優(yōu)雅的寫法：
?就是點(diǎn)到平面的距離
當(dāng)時(shí)，不就是函數(shù)間隔嗎？是的，前面提到的函數(shù)間隔歸一化結(jié)果就是幾何間隔。他們?yōu)槭裁磿?huì)一樣呢？因?yàn)楹瘮?shù)間隔是我們定義的，在定義的時(shí)候就有幾何間隔的色彩。同樣，同時(shí)擴(kuò)大w和b，w擴(kuò)大幾倍，就擴(kuò)大幾倍，結(jié)果無影響。同樣定義全局的幾何間隔
?
?
5 最優(yōu)間隔分類器（optimal margin classifier）
? ? 前面提到的目標(biāo)是尋找一個(gè)超平面，使得離超平面比較近的點(diǎn)能有更大的間距。也就是我們不考慮所有的點(diǎn)都必須遠(yuǎn)離超平面，我們關(guān)心求得的超平面能夠讓所有點(diǎn)中離它最近的點(diǎn)具有最大間距。形式化表示為：
? ? 用=1表示w，使得表示的是幾何間隔
? ? 到此，已經(jīng)將模型定義出來了。如果求得了w和b，那么來一個(gè)特征x，就能夠分類了，稱為最優(yōu)間隔分類器。
? ? 接下的問題就是如何求解w和b的問題了。由于不是凸函數(shù)，我們想先處理轉(zhuǎn)化一下，考慮幾何間隔和函數(shù)間隔的關(guān)系，，我們改寫一下上面的式子：
這個(gè)時(shí)候目標(biāo)函數(shù)仍然不是凸函數(shù)，沒法直接代入優(yōu)化軟件里計(jì)算。我們還要改寫。前面說到同時(shí)擴(kuò)大w和b對結(jié)果沒有影響，但我們最后要求的仍然是w和b的確定值，因此就需要對做一些限制，以保證解是唯一的。這里為了簡便取，這樣的意義是將全局的函數(shù)間隔定義為1，也即是將離超平面最近的點(diǎn)的距離定義為。由于求的最大值相當(dāng)于求的最小值，因此改寫后結(jié)果為：
?
這下好了，只有線性約束了，而且是個(gè)典型的二次規(guī)劃問題（目標(biāo)函數(shù)是自變量的二次函數(shù)）。代入優(yōu)化軟件可解。
（雖然沒有圖解那么直觀，但每一步推導(dǎo)有理有據(jù)，依靠思路的流暢性來推導(dǎo)出目標(biāo)函數(shù)和約束。）
接下來介紹的是手工求解的方法了，一種更優(yōu)的求解方法。
?
6 拉格朗日對偶（Lagrange duality）
???? 先拋開上面的二次規(guī)劃問題，先來看看存在等式約束的極值問題求法，比如下面的最優(yōu)化問題：
????????
??? 目標(biāo)函數(shù)是f(w)，下面是等式約束。通常解法是引入拉格朗日算子，這里使用來表示算子，得到拉格朗日公式為
????????
??? L是等式約束的個(gè)數(shù)。
??? 然后分別對w和求偏導(dǎo)，使得偏導(dǎo)數(shù)等于0，然后解出w和。
? ? 至于為什么引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的約束，dw的變化方向與f(w)的梯度垂直時(shí)才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，因此他們之間存在線性關(guān)系。
然后探討有不等式約束的極值問題求法，問題如下：
????????
? ? 定義一般化的拉格朗日公式
?
??? 這里的和都是拉格朗日算子。如果按這個(gè)公式求解，會(huì)出現(xiàn)問題，因?yàn)橐蠼獾氖亲钚≈?#xff0c;而這里的已經(jīng)不是0了，可以將調(diào)整成很大的正值，來使最后的函數(shù)結(jié)果是負(fù)無窮。因此需要排除這種情況，定義下面的函數(shù)：
?????
??? 這里的P代表primal。假設(shè)或者，那么總是可以調(diào)整和來使得有最大值為正無窮。而只有g(shù)和h滿足約束時(shí)，為f(w)。這個(gè)函數(shù)的精妙之處在于，而且求極大值。
??? 因此可以寫作
????
??? 這樣原來要求的min f(w)可以轉(zhuǎn)換成求了。 ???
????
? ? 使用來表示。如果直接求解，首先面對的是兩個(gè)參數(shù)，而也是不等式約束，然后再在w上求最小值。這個(gè)過程不容易做，那么怎么辦呢？
? ? 先考慮另外一個(gè)問題
??? D的意思是對偶，將問題轉(zhuǎn)化為先求拉格朗日關(guān)于w的最小值，將和看作是固定值。之后在求最大值的話：
?
??? 這個(gè)問題是原問題的對偶問題，相對于原問題只是更換了min和max的順序，而一般更換順序的結(jié)果是Max Min(X) <= MinMax(X)。然而在這里兩者相等。用來表示對偶問題如下：
??????
??? 下面解釋在什么條件下兩者會(huì)等價(jià)。假設(shè)f和g都是凸函數(shù)，h是仿射的（affine，）。并且存在w使得對于所有的i，。在這種假設(shè)下，一定存在使得是原問題的解，是對偶問題的解。還有另外，滿足庫恩-塔克條件（Karush-Kuhn-Tucker, KKT condition），該條件如下：
????
??? 所以如果滿足了庫恩-塔克條件，那么他們就是原問題和對偶問題的解。讓我們再次審視公式（5），這個(gè)條件稱作是KKT dual complementarity條件。這個(gè)條件隱含了如果，那么。也就是說，時(shí)，w處于可行域的邊界上，這時(shí)才是起作用的約束。而其他位于可行域內(nèi)部（的）點(diǎn)都是不起作用的約束，其。這個(gè)KKT雙重補(bǔ)足條件會(huì)用來解釋支持向量和SMO的收斂測試。
??? 這部分內(nèi)容思路比較凌亂，還需要先研究下《非線性規(guī)劃》中的約束極值問題，再回頭看看。KKT的總體思想是將極值會(huì)在可行域邊界上取得，也就是不等式為0或等式約束里取得，而最優(yōu)下降方向一般是這些等式的線性組合，其中每個(gè)元素要么是不等式為0的約束，要么是等式約束。對于在可行域邊界內(nèi)的點(diǎn)，對最優(yōu)解不起作用，因此前面的系數(shù)為0。
7 最優(yōu)間隔分類器（optimal margin classifier）
??? 重新回到SVM的優(yōu)化問題：
????
??? 我們將約束條件改寫為：
????
??? 從KKT條件得知只有函數(shù)間隔是1（離超平面最近的點(diǎn)）的線性約束式前面的系數(shù)，也就是說這些約束式，對于其他的不在線上的點(diǎn)()，極值不會(huì)在他們所在的范圍內(nèi)取得，因此前面的系數(shù).注意每一個(gè)約束式實(shí)際就是一個(gè)訓(xùn)練樣本。
??? 看下面的圖：
????
??? 實(shí)線是最大間隔超平面，假設(shè)×號的是正例，圓圈的是負(fù)例。在虛線上的點(diǎn)就是函數(shù)間隔是1的點(diǎn)，那么他們前面的系數(shù)，其他點(diǎn)都是。這三個(gè)點(diǎn)稱作支持向量。構(gòu)造拉格朗日函數(shù)如下： ???
????
??? 注意到這里只有沒有是因?yàn)樵瓎栴}中沒有等式約束，只有不等式約束。
??? 下面按照對偶問題的求解步驟來一步步進(jìn)行，
????
??? 首先求解的最小值，對于固定的，的最小值只與w和b有關(guān)。對w和b分別求偏導(dǎo)數(shù)。
????
????
??? 并得到
????
??? 將上式帶回到拉格朗日函數(shù)中得到，此時(shí)得到的是該函數(shù)的最小值（目標(biāo)函數(shù)是凸函數(shù)）
??? 代入后，化簡過程如下：
?????
最后得到
???? 由于最后一項(xiàng)是0，因此簡化為
????
??? 這里我們將向量內(nèi)積表示為
??? 此時(shí)的拉格朗日函數(shù)只包含了變量。然而我們求出了才能得到w和b。
??? 接著是極大化的過程，
??? 前面提到過對偶問題和原問題滿足的幾個(gè)條件，首先由于目標(biāo)函數(shù)和線性約束都是凸函數(shù)，而且這里不存在等式約束h。存在w使得對于所有的i，。因此，一定存在使得是原問題的解，是對偶問題的解。在這里，求就是求了。
??? 如果求出了，根據(jù)即可求出w（也是，原問題的解）。然后
????
??? 即可求出b。即離超平面最近的正的函數(shù)間隔要等于離超平面最近的負(fù)的函數(shù)間隔。
??? 關(guān)于上面的對偶問題如何求解，將留給下一篇中的SMO算法來闡明。
??? 這里考慮另外一個(gè)問題，由于前面求解中得到
????
??? 我們通篇考慮問題的出發(fā)點(diǎn)是，根據(jù)求解得到的，我們代入前式得到
????
??? 也就是說，以前新來的要分類的樣本首先根據(jù)w和b做一次線性運(yùn)算，然后看求的結(jié)果是大于0還是小于0,來判斷正例還是負(fù)例。現(xiàn)在有了，我們不需要求出w，只需將新來的樣本和訓(xùn)練數(shù)據(jù)中的所有樣本做內(nèi)積和即可。那有人會(huì)說，與前面所有的樣本都做運(yùn)算是不是太耗時(shí)了？其實(shí)不然，我們從KKT條件中得到，只有支持向量的，其他情況。因此，我們只需求新來的樣本和支持向量的內(nèi)積，然后運(yùn)算即可。這種寫法為下面要提到的核函數(shù)（kernel）做了很好的鋪墊。
轉(zhuǎn)載于:https://www.cnblogs.com/Real-Ying/p/6841277.html
總結(jié)
以上是生活随笔為你收集整理的Ng第十二课：支持向量机(Support Vector Machines)（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 自学it18大数据笔记-第三阶段Scal
- 下一篇： 双向队列(STL做法)