支持向量機的數學原理第一頁，共六十二頁，2022年，8月28日什么是支持向量機在右圖中A圖表示有兩類的數據集，圖B,C,D都提供了一個線性分類器來對數據進行分類？但是哪個效果好一些？第二頁，共六十二頁，2022年，8月28日什么是支持向量機

支持向量機（SVM）是90年代中期發展起來的基于統計學習理論的一種機器學習方法，通過尋求結構化風險最小來提高學習機泛化能力，實現經驗風險和置信范圍的最小化，從而達到在統計樣本量較少的情況下，亦能獲得良好統計規律的目的。在深度學習出現之前，SVM一直霸占著機器學習老大哥的位子。他的理論很優美，各種變種改進版本也很多，比如latent-SVM,structural-SVM等。通俗來講，它是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，即支持向量機的學習策略便是間隔最大化，最終可轉化為一個凸二次規劃問題的求解。支持向量機的學習算法是求解凸二次規劃的最優化算法。第三頁，共六十二頁，2022年，8月28日什么是支持向量機支持向量機學習方法包含構建由簡至繁的模型：線性可分支持向量機、線性支持向量機及非線性支持向量機。當訓練數據線性可分時，通過硬間隔最大化，學習一個線性的分類器，即線性可分支持向量機；當訓練數據近似可分時，通過軟間隔最大化，也學習一個線性的分類器，即線性支持向量機；當訓練數據線性不可分時，通過使用核技巧及軟間隔最大化，學習非線性支持向量機。第四頁，共六十二頁，2022年，8月28日第一部分線性可分支持向量機

與硬間隔最大化第五頁，共六十二頁，2022年，8月28日線性可分支持向量機下面舉個簡單的例子，一個二維平面(一個超平面，在二維空間中的例子就是一條直線)，如下圖所示，平面上有兩種不同的點，分別用兩種不同的顏色表示，一種為紅顏色的點，另一種則為藍顏色的點，紅顏色的線表示一個可行的超平面。從右圖中我們可以看出，這條紅顏色的線把紅顏色的點和藍顏色的點分開來了。而這條紅顏色的線就是我們上面所說的超平面，也就是說，這個所謂的超平面的的確確便把這兩種不同顏色的數據點分隔開來，在超平面一邊的數據點所對應的

y

全是-1，而在另一邊全是1。第六頁，共六十二頁，2022年，8月28日線性可分支持向量機接著，我們可以令分類函數：顯然，如果

f(x)=0

，那么

x

是位于超平面上的點。我們不妨要求對于所有滿足

f(x)<0

的點，其對應的

y

等于-1，而

f(x)>0

則對應

y=1

的數據點。

當然，有些時候，或者說大部分時候數據并不是線性可分的，這個時候滿足這樣條件的超平面就根本不存在(不過關于如何處理這樣的問題我們后面會講)，這里先從最簡單的情形開始推導，就假設數據都是線性可分的，亦即這樣的超平面是存在的。第七頁，共六十二頁，2022年，8月28日線性可分支持向量機如何確定分類函數中的兩個參數w和b？尋找兩條邊界端或極端劃分直線中間的最大間隔（之所以要尋最大間隔是為了能更好的劃分不同類的點），從而確定最終的最大間隔分類超平面和分類函數；進而把尋求分類函數

的問題轉化為對w，b的最優化問題。第八頁，共六十二頁，2022年，8月28日函數間隔

一般而言，一個點距離超平面的遠近可以表示為分類預測的確信或準確程度。在超平面w*x+b=0確定的情況下，|w*x+b|能夠相對的表示點x到距離超平面的遠近，而w*x+b的符號與類標記y的符號是否一致表示分類是否正確，所以，可以用量y*(w*x+b)的正負性來判定或表示分類的正確性和確信度。于此，我們便引出了定義樣本到分類間隔距離的函數間隔functionalmargin的概念。我們定義函數間隔functionalmargin

為：

定義超平面(w，b)關于訓練數據集T的函數間隔為超平面(w，b)關于T中所有樣本點(xi，yi)的函數間隔最小值，其中，x是特征，y是結果標簽，i表示第i個樣本，有：第九頁，共六十二頁，2022年，8月28日幾何間隔函數間隔雖然可以表示分類預測的正確性和確信度，但在選擇分類超平面時，只有函數間隔還遠遠不夠，因為如果成比例的改變w和b，如將他們改變為2w和2b，雖然此時超平面沒有改變，但函數間隔的值f(x)卻變成了原來的2倍。其實，我們可以對法向量w加些約束條件，使其表面上看起來規范化，如此，我們很快又將引出真正定義點到超平面的距離--幾何間隔的概念。對于給定的訓練數據集T和超平面（w,b），定義超平面關于樣本點(x,y)的幾何間隔為：定義超平面(w，b)關于訓練數據集T的幾何間隔為超平面(w,b)關于T中所有樣本點(xi，yi)的幾何間隔最小值，

r=minri(i=1,2,…n)

第十頁，共六十二頁，2022年，8月28日支持向量和間隔邊界在線性可分情況下，訓練數據集的樣本點與分離超平面距離最近的樣本點的實力稱為支持向量，支持向量是使約束條件式y(i)(wTx(i)+b)≥1,i=1,2,3……m中等號成立的的點。在決定分離超平面時只有支持向量起作用，而其他實例點并不起作用

第十一頁，共六十二頁，2022年，8月28日間隔最大化支持向量機學習的基本想法是求解能夠正確劃分訓練數據集并且幾何間隔最大的分離超平面，對線性可分的數據集而言，線性可分分離超平面有無窮多個（等價于感知機），但是幾何間隔最大的分離超平面是唯一的。間隔最大化的直觀解釋是：對訓練數據集找到幾何間隔最大的超平面意味著以充分大的確信度對訓練數據進行分類，也就是說，不僅將正負實例分開，而且對最難分的實例點（離超平面最近的點）也有足夠大的確信度將它們分開，這樣的超平面應該對未知的新實例有很好的分類預測能力。第十二頁，共六十二頁，2022年，8月28日間隔最大化按照前面的分析，對一個數據點進行分類，當它的間隔越大的時候，分類的可信度越大。對于一個包含

n

個點的數據集，我們可以很自然地定義它的間隔為所有這

n

個點的間隔值中最小的那個。于是，為了使得分類的可信度高，我們希望所選擇的超平面能夠最大化這個間隔值。第十三頁，共六十二頁，2022年，8月28日間隔最大化下面考慮如何求得一個幾何間隔最大的分離超平面，即最大間隔分離超平面，具體地，這個問題可以表示為下面的約束最優化問題：

*此處公式有問題，約束條件左邊應除以一個||w||即我們希望最大化超平面(w,b)關于訓練數據集的幾何間隔，約束條件表示的是超平面(w,b)關于每個訓練樣本點的幾何間隔至少是γ。考慮到幾何間隔和函數間隔的關系式，可將這個問題改寫為：第十四頁，共六十二頁，2022年，8月28日間隔最大化函數間隔的取值并不影響最優化問題的解。事實上，假設將w和b按比例改變為λw和λb,這時函數間隔成為λγ’。函數間隔的這一改變對上面最優化問題的不等式約束，對目標函數的優化也沒有影響，也就是說，它產生一個等價的最優化問題。這樣，就可以取γ’=1,將γ’=1代入前面的最優化問題，也即是將離超平面最近的點的距離定義為1/||w||，由于最大化1/||w||和最小化1/2||w||2等價，于是得到下面的線性可分支持向量機學習的最優化問題：

這是一個凸二次規劃問題。如果求出了該問題的解w*、b*,那么就可以得到最大間隔分離平面w*x+b*=0及分類決策函數f(w)=sign(w*x+b*),即線性可分支持向量機模型。第十五頁，共六十二頁，2022年，8月28日關于凸優化的一些簡單概念凸集的定義為：其幾何意義表示為：如果集合C中任意2個元素連線上的點也在集合C中，則C為凸集。其示意圖如下所示：第十六頁，共六十二頁，2022年，8月28日關于凸優化的一些簡單概念凸函數的定義為：其幾何意義表示為函數任意兩點連線上的值大于對應自變量處的函數值，示意圖如下：常見的凸函數有：指數函數族；非負對數函數；仿射函數；二次函數；常見的范數函數；第十七頁，共六十二頁，2022年，8月28日關于凸優化的一些簡單概念凸優化問題（OPT）的定義為：即要求目標函數是凸函數，變量所屬集合是凸集合的優化問題。或者目標函數是凸函數，變量的約束函數是凸函數（不等式約束時），或者是仿射函數（等式約束時）。*f(x)稱為仿射函數，如果它滿足f(x)=ax+b,a∈Rn,b∈Rn,x∈Rn第十八頁，共六十二頁，2022年，8月28日凸二次規劃問題求解原始問題轉換為形式后，原問題成了一個凸二次規劃問題。解此問題除了用解決QP問題的常規方法之外，還可以通過求解對偶問題得到最優解，這就是線性可分條件下支持向量機的對偶算法，這樣做的優點在于：一者對偶問題往往更容易求解；二者可以自然的引入核函數，進而推廣到非線性分類問題。

首先構建拉格朗日函數，通過給每一個約束條件加上一拉格朗日乘值，即引入拉格朗日乘子，如此我們便可以通過拉格朗日函數將約束條件融和到目標函數里去。

第十九頁，共六十二頁，2022年，8月28日條件極值與拉格朗日乘數法例：要設計一個容量為V

的長方體開口水箱，試問水箱的長、寬、高各為多少時，其表面積最小？為此，設水箱的長、寬、高分別為x,y,z,則表面積為依題意，上述的長、寬、高不僅要符合定義域的要求：x>0,y>0,z>0,而且還須滿足條件這類附有約束條件的極值問題稱為條件極值條件極值問題的一般形式是等式約束：即在條件組：的限制下，求目標函數

的極值。第二十頁，共六十二頁，2022年，8月28日條件極值與拉格朗日乘數法條件極值的一種求解方法是代入法.，將條件極值化為無條件極值。例如，在上述例子中，由條件

解出代入目標函數中，

得到

然后求這個函數的無條件極值。然而在一般情形下，這種方法往往是行不通的，因為要從條件組

解出m

個變元常常是不可能的.下面介紹的拉格朗日乘數法是求條件極值的一種有效方法.第二十一頁，共六十二頁，2022年，8月28日條件極值與拉格朗日乘數法

可確定函數

則問題等價于一元函數

的極值問題,由極值的必要條件，知極值點x0

必滿足因

故有即

記極值點必滿足想法：把上面的條件極值點轉化為一般極值點問題第二十二頁，共六十二頁，2022年，8月28日條件極值與拉格朗日乘數法構造一個函數使得其極值點就是上面函數的條件極值點引入輔助函數則極值點滿足:輔助函數L稱為拉格朗日(Lagrange)函數.利用拉格朗日函數求極值的方法稱為拉格朗日乘數法.第二十三頁，共六十二頁，2022年，8月28日條件極值與拉格朗日乘數法利用拉格朗日乘數法求函數

在條件

下的極值步驟如下：1.作拉格朗日函數求拉格朗日函數的極值

先求解拉格朗日函數的偏導數構成的方程組再考察駐點是否是極值點第二十四頁，共六十二頁，2022年，8月28日拉格朗日對偶性第二十五頁，共六十二頁，2022年，8月28日拉格朗日對偶性第二十六頁，共六十二頁，2022年，8月28日拉格朗日對偶性第二十七頁，共六十二頁，2022年，8月28日拉格朗日對偶性第二十八頁，共六十二頁，2022年，8月28日拉格朗日對偶性第二十九頁，共六十二頁，2022年，8月28日拉格朗日對偶性第三十頁，共六十二頁，2022年，8月28日拉格朗日對偶性第三十一頁，共六十二頁，2022年，8月28日對偶算法求解第三十二頁，共六十二頁，2022年，8月28日對偶算法求解第三十三頁，共六十二頁，2022年，8月28日對偶算法求解第三十四頁，共六十二頁，2022年，8月28日對偶算法求解第三十五頁，共六十二頁，2022年，8月28日對偶算法求解第三十六頁，共六十二頁，2022年，8月28日對偶算法求解第三十七頁，共六十二頁，2022年，8月28日對偶算法求解第三十八頁，共六十二頁，2022年，8月28日對偶算法求解第三十九頁，共六十二頁，2022年，8月28日對偶算法求解第四十頁，共六十二頁，2022年，8月28日對偶算法求解第四十一頁，共六十二頁，2022年，8月28日對偶算法求解第四十二頁，共六十二頁，2022年，8月28日對偶算法求解第四十三頁，共六十二頁，2022年，8月28日對偶算法求解第四十四頁，共六十二頁，2022年，8月28日對偶算法求解第四十五頁，共六十二頁，2022年，8月28日最大間隔分離超平面的存在唯一性第四十六頁，共六十二頁，2022年，8月28日最大間隔分離超平面的存在唯一性第四十七頁，共六十二頁，2022年，8月28日第二部分線性支持向量機

與軟間隔最大化第四十八頁，共六十二頁，2022年，8月28日線性支持向量機在第一部分最開始討論支持向量機的時候，我們就假定，數據是線性可分的，亦即我們可以找到一個可行的超平面將數據完全分開。然而，這只是一種理想狀態，通常情況下數據往往不是線性可分的，因為數據中一般存在噪聲。對于這種偏離正常位置很遠的噪聲點，我們稱之為outlier，在我們原來的SVM模型里，outlier的存在有可能造成很大的影響，因為超平面本身就是只有少數幾個supportvector組成的，如果這些supportvector里又存在outlier的話，其影響就很大了。第四十九頁，共六十二頁，2022年，8月28日線性支持向量機用黑圈圈起來的那個藍點是一個outlier，它偏離了自己原本所應該在的那個半空間，如果直接忽略掉它的話，