各位讀者好,，上期的文章已經(jīng)講解了《從超平面到SVM（一）》的內(nèi)容，主要講解了超平面和函數(shù)間隔最大化,，本期將繼續(xù)講解《從超平面到SVM》的數(shù)學推理和核函數(shù)部分,，這部分涉及到的數(shù)學知識較多，對于較難理解的部分會盡力講清,，但是仍需部分數(shù)學基礎,，涉及到的知識點讀者可以翻閱之前的數(shù)學課本，后期若有時間我也會對機器學習中的數(shù)學知識進行盤點和總結,，往繼續(xù)關注本公眾號的后期文章,。

上期在講函數(shù)間隔最大化那一部分時經(jīng)過推理后已經(jīng)得到了如下一個優(yōu)化函數(shù)：

上面這個優(yōu)化函數(shù)是一個優(yōu)化問題,，這部分涉及的知識非常的多,，其中凸優(yōu)化是所有優(yōu)化問題里面較為簡單的一種，只要一個問題經(jīng)過轉(zhuǎn)化后可以轉(zhuǎn)化為凸優(yōu)化問題,，則可以認為該問題就可解了,。

如上圖,，在線性可分的情況下，訓練數(shù)據(jù)集的樣本點中與分離超平面最近的樣本點的實例稱為支持向量,，支持向量是使約束條件等號成立的帶點,，即：

對于y_i=+1的正例點，支持向量在超平面H₁上的對應方程為：

對于y_i=-1的負例點,，支持向量在超平面H₂上的對應方程為：

如上圖,，藍色的直線y=x-0.5，是劃分藍色的圓點和紅色的紅叉的超平面,，其中紅色的直線y=x和綠色的直線y=x-1是支持向量（1,，1）,，（2，2）和（2,，1）,，（3，2）所在的直線,，可以看到紅色的直線和綠色的直線之間沒有其他樣本點落在其中,，且分離超平面位于兩條直線的中央。長帶的寬度,，即H1與H2之間的距離稱之為間隔（margin）,。上期的優(yōu)化函數(shù)化簡后如下：

從上述函數(shù)可以看出，最大化H₁和H₂間隔就等同于最大化1/||w0||,，為了后期求導的方便,，可以寫成2/||w0||，H₁和H₂可以稱為間隔邊界,。在決定分離超平面時只有支持向量起到了作用,，如果支持向量變化會影響到解，而移動支持向量以外的點并不會影響最終解,。

為了求解上述優(yōu)化函數(shù),，還需要進一步轉(zhuǎn)化為數(shù)學計算問題，上面是一個比較典型的有限制條件的求多元函數(shù)極值的問題,，以前在高等數(shù)學中最常見的多元函數(shù)條件極值中條件極值都是等式,，此處變成了不等式，如何求解呢,？下面先開始復習下條件等式下的求極值是如何求得：

上面這個函數(shù)存在極值的話,，可以假設此極值點為(x₀,y₀)，當然,，極值點未必只有一個,，因為此處的限制條件為f(x,y)=0的形式，為了方便求導和帶入原方程,，可以將限制條件轉(zhuǎn)化為y=f(x)的形式,，此處就涉及到隱函數(shù)存在定理，定理如下：

看懂上述定理后,，則下面簡單證明下等式條件下拉格朗日乘子法的來歷：

所以上述問題就轉(zhuǎn)化為了一個一元函數(shù)求極值的問題,，可依據(jù)求極值的條件如下：

拉格朗日乘子法：函數(shù)Z=f(x,y)在附加條件?(x,y)=0下可能的極值點，可以先做拉格朗日函數(shù)：

好了,，上面已經(jīng)講清了拉格朗日乘子法的原理,，但是此時仍舊解決不了上面的約束問題，因為該問題約束條件是不等式,，下面將逐步解決此問題,。

對于約束條件是不等式約束的情況,，此時不光需要引入拉格朗日乘子，還需要引入一個KKT條件,，所有的不等式約束問題可以如下的表示：

其中,，不同的m和n代表的是約束條件的個數(shù)，此處默認只有一個即可,，然后依然構造拉格朗日函數(shù),，然后解決辦法如下：

上面的求解優(yōu)化方法中前兩個KKT條件和之前的拉格朗日乘子法是一致的，但是后面一個就比較難懂了,，可以如下去理解：

搞懂了上面的不等式優(yōu)化問題后，就可以依據(jù)之前的優(yōu)化問題構建對應的拉格朗日函數(shù),，其中,，對每一個不等式約束引進拉格朗日乘子αi≥0,i=1,2,3,...,N，定義如下的拉格朗日函數(shù)：

為了更好的求解上述問題,，此時又要引入一個新的概念,，即對偶問題，可以認為是原問題的等價問題,，對偶問題變換后更易求解且后期方便引入核函數(shù),，原問題的對偶問題就是極大極小問題：

于是為了得到問題的解，就變成了先求L對w,、b的極小,，再求對α的極大。

所以,，可以總結下線性可分支持向量機的算法：

輸入：給定線性可分訓練集T={(x₁,y₁),(x₂,y₂),...,(x_N,y_N)},其中xi∈X=Rn,，yi∈Y={+1,-1}，i=1,2,3,...,N

輸出：分離超平面和分類決策函數(shù)

(1)構造并求解約束最優(yōu)化問題

2)計算解w和b

(3)求得分離超平面

(4)分類決策函數(shù)

從上面公式中可以看出w*,b*僅僅依賴于訓練數(shù)據(jù)中對應α^*_j>0的樣本點,，與其他樣本點無關,，其實這部分就是前面所講的離超平面最近的向量，可以稱之為支持向量,，即α^*_j>0>0對應的那部分向量即是支持向量,。

對于線性分類問題可以使用上面的線性分類支持向量機來解決，即在N維坐標空間中可以用N維的變量組合來構建一個超平面劃分正例點和負例點,，如果正例點和負例點的分布無法用一個超平面去劃分就需要用到支持向量機非線性分類器了,，當然，一般解決這種問題不可能再從頭到尾重新研究一種算法,，而是想辦法來將非線性分類問題轉(zhuǎn)化為線性分類問題,，此時就需要引入一種新的辦法，核技巧,。

如上圖,，在二維空間中,，x和o無法找到一條直線將其分開，但是將這些點映射到三維空間中就可以用一個平面去劃分了,，就實現(xiàn)了線性可分,，所以，可以考慮通過對低維空間的樣本點進行映射到高維空間,，然后再在高維空間里面找到一個超平面進行劃分就實現(xiàn)了將線性不可分轉(zhuǎn)化為線性可分的問題了,。

上面這種方法就是通過將樣本點映射到高維特征空間然后在高維特征空間進行分類的方法，公式描述如下：

這樣的方法主要分兩步：

(1)      首先使用一個非線性映射將樣本變換到高緯特征空間

(2)      然后在特征空間里面用線性分類器進行分類

根據(jù)分類平面的解可知,，原始分類函數(shù)可以如下表示：

如果要映射為高維空間函數(shù)則需要做一次映射,，表示如下：

但是如果每次都需要對每個樣本做這類映射計算，然后再在高維空間做線性分類則顯得很麻煩,，為了解決這個問題,，可以考慮進行合二為一，引入一個核變換的函數(shù),，直接將計算部分計算出來,，然后直接用線性分類其分類就好了，所以,，下面介紹下核函數(shù),。

核函數(shù)：設X是輸入空間，H為特征空間,，如果存在一個從X到H的映射：

使得對于所有的x,z∈X,，函數(shù)K(x,z)滿足條件：

則稱K(x,z)為核函數(shù)，Φ(x)為映射函數(shù),，Φ(x)·Φ(z)為二者的內(nèi)積,。

于是，引入核函數(shù)以后,，可以進行如下的變換：

這樣,，就可以把計算的問題交給核函數(shù)了，每次只需在低維空間里面進行計算,，就直接完成了映射過程,，然后用線性分類器就可以分類了，不過有個問題就是,，如果核函數(shù)不能保證映射后的數(shù)據(jù)線性可分怎么辦,，這個問題也是現(xiàn)實中存在的，不過,，經(jīng)過推理和證明,，總結了一些常用的核函數(shù)，這些函數(shù)多數(shù)在映射后都是可分得,，對于及其特殊的情況,，可以通過選擇不同的核函數(shù)進行調(diào)試,。

對于上面的理論基本都是抽象的推理，為了更直觀去理解這部分,，可以舉一個很簡單的例子,，比如最常見的二維空間不可分的異或問題：

這樣，上面兩個圓圈的坐標別為(0,0),、(1,1),三角坐標為(0,1),、(1,0)，很明顯,，無法在二維直角坐標系找到一條直線將圓圈和三角劃分開,，于是可以做如下變換：

這樣，上面兩個圓圈的坐標別為(0,0),、(1,1),三角坐標為(0,1),、(1,0)，很明顯,，無法在二維直角坐標系找到一條直線將圓圈和三角劃分開，于是可以做如下變換：

所以坐標就變成了(0,0,0),、(1,1,1),、(0,0,1)、(1,0,0),，此時該映射到三維空間中的四個點就可分了,，其中黃色的三角確定的屏幕即是超平面：

到現(xiàn)在為止，已經(jīng)從間隔邊界和對偶算法一直講到了核技巧,，《從超平面到SVM》的理論部分就暫時講完了,，不過SVM遠比我們想的要復雜些，雖然理論上已經(jīng)梳理了一遍,，但是它在程序中的實現(xiàn)也是很大的一個問題,，因為SVM涉及到很多樣本空間的計算，這個過程及其耗費時間,，如果按照上面理論講的來實現(xiàn)會發(fā)現(xiàn),，隨著數(shù)據(jù)量的增長SVM算法會越來越慢，為了解決這一問題,，后面還有一部分關于SVM實現(xiàn)的算法稱為SMO算法,，下期本文將繼續(xù)講解SVM的第三部分SMO算法。