寫在前面的話：距離上篇部落格竟過去快一個月了，寫完神經網絡部落格正式進入考試模式，幾次考試+幾篇報告下來弄得心頗不甯靜了，今日定下來看到一句雞血：Tomorrow is another due！也許生活就需要一些deadline~~
上篇主要介紹了神經網絡。首先從生物學神經元出發，引出了它的數學抽象模型–MP神經元以及由兩層神經元組成的感覺機模型，并基于梯度下降的方法描述了感覺機模型的權值調整規則。由于簡單的感覺機不能處理線性不可分的情形，是以接着引入了含隐層的前饋型神經網絡，BP神經網絡則是其中最為成功的一種學習方法，它使用誤差逆傳播的方法來逐層調節連接配接權。最後簡單介紹了局部/全局最小以及目前十分火熱的深度學習的概念。本篇圍繞的核心則是曾經一度取代過神經網絡的另一種監督學習算法–支援向量機（Support Vector Machine），簡稱SVM。
#6、支援向量機
支援向量機是一種經典的二分類模型，基本模型定義為特征空間中最大間隔的線性分類器，其學習的優化目标便是間隔最大化，是以支援向量機本身可以轉化為一個凸二次規劃求解的問題。
##6.1 函數間隔與幾何間隔
對于二分類學習，假設現在的資料是線性可分的，這時分類學習最基本的想法就是找到一個合适的超平面，該超平面能夠将不同類别的樣本分開，類似二維平面使用ax+by+c=0來表示，超平面實際上表示的就是高維的平面，如下圖所示：
對資料點進行劃分時，易知：當超平面距離與它最近的資料點的間隔越大，分類的魯棒性越好，即當新的資料點加入時，超平面對這些點的适應性最強，出錯的可能性最小。是以需要讓所選擇的超平面能夠最大化這個間隔Gap（如下圖所示）， 常用的間隔定義有兩種，一種稱之為函數間隔，一種為幾何間隔，下面将分别介紹這兩種間隔，并對SVM為什麼會選用幾何間隔做了一些闡述。
###6.1.1 函數間隔
在超平面w’x+b=0确定的情況下，|w’x*+b|能夠代表點x距離超平面的遠近，易知：當w’x+b>0時，表示x在超平面的一側（正類，類标為1），而當w’x+b<0時，則表示x在超平面的另外一側（負類，類别為-1），是以（w’x+b）y* 的正負性恰能表示資料點x*是否被分類正确。于是便引出了函數間隔的定義（functional margin）:
而超平面（w,b）關于所有樣本點（Xi，Yi）的函數間隔最小值則為超平面在訓練資料集T上的函數間隔：
可以看出：這樣定義的函數間隔在處理SVM上會有問題，當超平面的兩個參數w和b同比例改變時，函數間隔也會跟着改變，但是實際上超平面還是原來的超平面，并沒有變化。例如：w1x1+w2x2+w3x3+b=0其實等價于2w1x1+2w2x2+2w3x3+2b=0，但計算的函數間隔卻翻了一倍。進而引出了能真正度量點到超平面距離的概念–幾何間隔（geometrical margin）。
###6.1.2 幾何間隔
幾何間隔代表的則是資料點到超平面的真實距離，對于超平面w’x+b=0，w代表的是該超平面的法向量，設x為超平面外一點x在法向量w方向上的投影點，x與超平面的距離為r，則有x=x-r(w/||w||)，又x在超平面上，即w’x+b=0，代入即可得：
為了得到r的絕對值，令r呈上其對應的類别y，即可得到幾何間隔的定義：
從上述函數間隔與幾何間隔的定義可以看出：實質上函數間隔就是|w’x+b|，而幾何間隔就是點到超平面的距離。
##6.2 最大間隔與支援向量
通過前面的分析可知：函數間隔不适合用來最大化間隔，是以這裡我們要找的最大間隔指的是幾何間隔，于是最大間隔分類器的目标函數定義為：
一般地，我們令r^為1（這樣做的目的是為了友善推導和目标函數的優化），進而上述目标函數轉化為：
對于y(w’x+b)=1的資料點，即下圖中位于w’x+b=1或w’x+b=-1上的資料點，我們稱之為支援向量（support vector），易知：對于所有的支援向量，它們恰好滿足y*(w’x*+b)=1，而所有不是支援向量的點，有y*(w’x*+b)>1。
##6.3 從原始優化問題到對偶問題
對于上述得到的目标函數，求1/||w||的最大值相當于求||w||^2的最小值，是以很容易将原來的目标函數轉化為：
即變為了一個帶限制的凸二次規劃問題，按書上所說可以使用現成的優化計算包（QP優化包）求解，但由于SVM的特殊性，一般我們将原問題變換為它的對偶問題，接着再對其對偶問題進行求解。為什麼通過對偶問題進行求解，有下面兩個原因：
* 一是因為使用對偶問題更容易求解；
* 二是因為通過對偶問題求解出現了向量内積的形式，進而能更加自然地引出核函數。
對偶問題，顧名思義，可以了解成優化等價的問題，更一般地，是将一個原始目标函數的最小化轉化為它的對偶函數最大化的問題。對于目前的優化問題，首先我們寫出它的朗格朗日函數：
上式很容易驗證：當其中有一個限制條件不滿足時，L的最大值為 ∞（隻需令其對應的α為 ∞即可）；當所有限制條件都滿足時，L的最大值為1/2||w||^2（此時令所有的α為0），是以實際上原問題等價于：
由于這個的求解問題不好做，是以一般我們将最小和最大的位置交換一下（需滿足KKT條件） ，變成原問題的對偶問題：
這樣就将原問題的求最小變成了對偶問題求最大（用對偶這個詞還是很形象），接下來便可以先求L對w和b的極小，再求L對α的極大。
（1）首先求L對w和b的極小，分别求L關于w和b的偏導，可以得出：
将上述結果代入L得到：
（2）接着L關于α極大求解α（通過SMO算法求解，此處不做深入）。
（3）最後便可以根據求解出的α，計算出w和b，進而得到分類超平面函數。
在對新的點進行預測時，實際上就是将資料點x*代入分類函數f(x)=w’x+b中，若f(x)>0，則為正類，f(x)<0，則為負類，根據前面推導得出的w與b，分類函數如下所示，此時便出現了上面所提到的内積形式。
這裡實際上隻需計算新樣本與支援向量的内積，因為對于非支援向量的資料點，其對應的拉格朗日乘子一定為0，根據最優化理論（K-T條件），對于不等式限制y(w’x+b)-1≥0，滿足：
##6.4 核函數
由于上述的超平面隻能解決線性可分的問題，對于線性不可分的問題，例如：異或問題，我們需要使用核函數将其進行推廣。一般地，解決線性不可分問題時，常常采用映射的方式，将低維原始空間映射到高維特征空間，使得資料集在高維空間中變得線性可分，進而再使用線性學習器分類。如果原始空間為有限維，即屬性數有限，那麼總是存在一個高維特征空間使得樣本線性可分。若∅代表一個映射，則在特征空間中的劃分函數變為：
按照同樣的方法，先寫出新目标函數的拉格朗日函數，接着寫出其對偶問題，求L關于w和b的極大，最後運用SOM求解α。可以得出：
（1）原對偶問題變為：
（2）原分類函數變為：
求解的過程中，隻涉及到了高維特征空間中的内積運算，由于特征空間的維數可能會非常大，例如：若原始空間為二維，映射後的特征空間為5維，若原始空間為三維，映射後的特征空間将是19維，之後甚至可能出現無窮維，根本無法進行内積運算了，此時便引出了核函數（Kernel）的概念。
是以，核函數可以直接計算隐式映射到高維特征空間後的向量内積，而不需要顯式地寫出映射後的結果，它雖然完成了将特征從低維到高維的轉換，但最終卻是在低維空間中完成向量内積計算，與高維特征空間中的計算等效**（低維計算，高維表現）**，進而避免了直接在高維空間無法計算的問題。引入核函數後，原來的對偶問題與分類函數則變為：
（1）對偶問題：
（2）分類函數：
是以，線上性不可分問題中，核函數的選擇成了支援向量機的最大變數，若選擇了不合适的核函數，則意味着将樣本映射到了一個不合适的特征空間，則極可能導緻性能不佳。同時，核函數需要滿足以下這個必要條件：
由于核函數的構造十分困難，通常我們都是從一些常用的核函數中選擇，下面列出了幾種常用的核函數：
##6.5 軟間隔支援向量機
前面的讨論中，我們主要解決了兩個問題：當資料線性可分時，直接使用最大間隔的超平面劃分；當資料線性不可分時，則通過核函數将資料映射到高維特征空間，使之線性可分。然而在現實問題中，對于某些情形還是很難處理，例如資料中有噪聲的情形，噪聲資料（outlier）本身就偏離了正常位置，但是在前面的SVM模型中，我們要求所有的樣本資料都必須滿足限制，如果不要這些噪聲資料還好，當加入這些outlier後導緻劃分超平面被擠歪了，如下圖所示，對支援向量機的泛化性能造成很大的影響。
為了解決這一問題，我們需要允許某一些資料點不滿足限制，即可以在一定程度上偏移超平面，同時使得不滿足限制的資料點盡可能少，這便引出了**“軟間隔”支援向量機**的概念
* 允許某些資料點不滿足限制y(w'x+b)≥1；
* 同時又使得不滿足限制的樣本盡可能少。
這樣優化目标變為：
如同階躍函數，0/1損失函數雖然表示效果最好，但是數學性質不佳。是以常用其它函數作為“替代損失函數”。
支援向量機中的損失函數為hinge損失，引入**“松弛變量”**，目标函數與限制條件可以寫為：
其中C為一個參數，控制着目标函數與新引入正則項之間的權重，這樣顯然每個樣本資料都有一個對應的松弛變量，用以表示該樣本不滿足限制的程度，将新的目标函數轉化為拉格朗日函數得到：
按照與之前相同的方法，先讓L求關于w，b以及松弛變量的極小，再使用SMO求出α，有：
将w代入L化簡，便得到其對偶問題：
将“軟間隔”下産生的對偶問題與原對偶問題對比可以發現：新的對偶問題隻是限制條件中的α多出了一個上限C，其它的完全相同，是以在引入核函數處理線性不可分問題時，便能使用與“硬間隔”支援向量機完全相同的方法。
----在此SVM就介紹完畢。