決策邊界
機器學習中監督學習的任務就是如何找出決策邊界。
在訓練集中，有正負樣本，任何監督學習算法就是為了找出區分正負樣本的決策邊界。如下圖，決策邊界是平行於坐標軸y，是決策樹學出來的決策邊界。通過新的點在決策邊界的不同區域，將它預測為正或負類。
不同的算法，就是為了確定不同的決策邊界長什麼樣。
再比如神經網絡（非線性模型）的決策邊界：
所有監督學習算法都是為了確定一個邊界。
SVM 核心思想
Key Idea1
第一個key idea跟確定決策邊界相關，如下圖
有1、2、3，三條決策邊界，哪一條決策邊界會好點呢？
我們先看1，由於1決策邊界過於靠近負樣本，一旦出現一點擾動（噪音）就很容易導致模型將負樣本預測為正樣本，即泛化性能不強。
再看2，對比3，2的抗擾動能力有所不足。
所以，綜上，3作為決策邊界更為恰當。
SVM的目標就是找到區別正負樣本的邊界，使得正負樣本到達這條邊界的範圍最大（模型泛化能力最好）。
那麼我們如何以數學形式，計算這齣這條最寬的路呢？
上圖中橙色的線line是我們想要的那條線，假設這條線的一個法向量為：
已知，直線上任意點x都垂直於法線，有：
假設新來一樣本u，將樣本u的向量投影到法向量w所在的方向，看看u在線的左邊還是右邊，則決策公式：
也可以理解為：
w*u即向量u在w方向上的投影距離。
c可以視為原點到決策邊界的距離，如果小於c，則為負樣本，大於c則為正樣本。
上面的w和b其實就是機器學習算法要學習得出的參數。根據輸入的數據坐標，學出來w和b時，只需要用新點與向量w做點乘（投影距離，定義），再判斷距離與c的大小，就可確定數據是正樣本還是負樣本。
至此，就確定了我們優化的目標——最大邊界範圍。
Key Idea2
看到下圖，根據key idea1，我們知道了我們優化的目標就是找到最寬的那條「路」，「站」在路邊的樣本，我們稱其為支持向量。
對於這些站在街邊的向量，我們對其提出要求，在訓練集中，處於街邊位置的樣本，有：
要注意，上面的向量x都屬於訓練集。
對於那些不處於街邊的向量，如果是正樣本，則有：
數值是大於1，越大越好。
對於負樣本：
數值是小於-1，越小越好。
這就是我們對「街寬」的要求，通過對街寬進行normalize，歸一化後，每一半的街道寬是1。
在訓練集中，不允許有點在街道的範圍內，通過這條路把訓練集中的數據分開。
我們也可以將key idea2的兩個式子給簡化成一個式子，通過加入輔助變量：
通過以上變化，就可以將key idea2的式子簡化為一個表達式。
相對應的，對於支持向量的判斷的表達式也可以被簡化為：
最後，要注意，我們的key idea2 是針對訓練集的要求，key idea1是對任何的樣本點。
Key Idea3
接著，再回顧一下我們key idea2的目標——找到最寬的那條路。
那麼我們如何求「路」的寬呢？
從上圖可知，正負樣本的支持向量之差得出的向量在法向量w方向上的投影就是我們所要求的「路」的寬度。
即：
這裡做個簡單推導：
結合上式1-4與1-3可得：
可推得：
同理可得：
接著結合result1和result2有：
根據式子1-5，可以發現，這條街道得寬度和訓練集本身沒有任何關係，只要知道了這條街的法向量，那麼這個街道的寬度就是以這條「街道」法向量的模為分母，2為分子的分式的值。
我們可以發現，要使得這條街越寬，則法向量的模要儘可能小。
即：
綜上，我們要找到一個法向量w，使得其同時 滿足式子1-3和1-6。
Key Idea4
拉格朗日求解求導
拉格朗日能夠把帶限制條件的函數極值算法給變成一個不帶條件的函數極值算法。
可知上面式子1-6求極值，需要滿足：
通過拉格朗日方法，將帶條件的求函數極值轉化為不帶條件的函數極值求解問題，減少了計算的限制條件。
由此可得拉格朗日函數：
根據拉格朗日乘數法，式1-7中，未知數為w、b，對其求偏導使其等於0，有：
由上式可以發現，向量w其實是訓練集中xi的線性組合，因為yi要麼+1，要麼-1，alpha_i大部分是0。
可以看作支持向量的線性組合。
帶入計算可得：(ij符號意義相同，不必太過在意)
現在的目的就是，找到一些 alpha_i 的值，使得L最大。
即式子裡的alpha不為0，即取決於xi和xj的點乘。
即訓練集中，不需要告訴x是什麼，只需要告訴所有訓練集中兩兩x點乘的結果。（通向核方法的關鍵發現）
Key Idea5
由 key idea1有：
結合key idea4中：
可得：
在上式中，大部分的alphai都為0，只有少部分的alphai不為0，這些不為0的alpha_i對應的xi就是支持向量。
核方法推導
上面的決策邊界都是線性的，但是大部分的分類問題都是非線性的，如下圖：
我們很難找到一條直線，將正負樣本分開。這個時候，如果有一個變換(phi)，將二維坐標系變換成另一個坐標系，如下圖：
將每一個數做非線性變化，在變換後的空間中做一個線性的分類，就能夠順利的將其分開。
也就是說，我們要找到一個非線性變換，使得xi，在變換後的空間裡線性可分。
但這並不是核方法。如果我們要用非線性變化的方式，我們不需要對每一個點做非線性變化。在 Key Idea4中，我們發現要求函數極值，我們只需要對訓練的樣本向量兩兩求點乘，我們只需要將兩兩之間的變換之後的點乘，不需要告訴這個變換是什麼。
變換之後的點乘，仍然是xi,xj的函數，即：
即只需要定義出，它在某一個空間中，進行了某種變換後，在這個空間裡的兩兩之間點乘的結果，這個函數就叫kernel（核函數）。
舉個例子，假設非線性變化後的點乘結果：
有了核函數後，在所有的預測過程中，我們只需要將兩兩點乘換為k（核函數）的值即可。
為什麼使用kernel方法會比找變換的函數方法更高效呢?
假設我們用的是RBF核函數，非線性變換會映射到無窮維高的，這個是無法描述的，但是我們可以求在這個無窮維空間裡兩個向量點的點乘，所以核方法更為優秀。
關鍵就是讓優化目標跟決策函數具備一種非線性變換的能力。
如何求alpha
coordinate ascent
這裡只簡單的講個大概，大家能理解就理解，不理解也沒關係，因為前面已經講完了重點——SVM的核心思想了。
coordinate ascent是smo算法的一種基礎思想。
在上式中，只有alpha是變量，我們將式子抽象為求n個變量aplha的最大點：
多個變量的函數求極值比較難做，但是單個變量求極值就比較簡單。那麼，我們如何用單個變量求極值的方法來做多個變量求極值呢？
用上面的方法，依次拿一個alpha當變量，求式子1-8的alpha值仍然無法求出alpha的值，還需要對上述方法進行一定的改進，需要一次拿兩個變量來求。
之前key idea4中有涉及到，單單一個alpha是可以被其他alpha線性表達的，所以需要有兩個alpha變量。
好了，今天分享的內容就到這裡，希望對大家有所關注！
如果大家覺得文有所值，幫忙轉發收藏+關注哦~