支持向量機的數(shù)學(xué)原理第一頁，共六十二頁，編輯于2023年，星期六什么是支持向量機在右圖中A圖表示有兩類的數(shù)據(jù)集，圖B,C,D都提供了一個線性分類器來對數(shù)據(jù)進行分類？但是哪個效果好一些？第二頁，共六十二頁，編輯于2023年，星期六什么是支持向量機

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

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

y

全是-1，而在另一邊全是1。第六頁，共六十二頁，編輯于2023年，星期六線性可分支持向量機接著，我們可以令分類函數(shù)：顯然，如果

f(x)=0

，那么

x

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

f(x)<0

的點，其對應(yīng)的

y

等于-1，而

f(x)>0

則對應(yīng)

y=1

的數(shù)據(jù)點。

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

的問題轉(zhuǎn)化為對w，b的最優(yōu)化問題。第八頁，共六十二頁，編輯于2023年，星期六函數(shù)間隔

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

為：

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

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

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

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

n

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

n

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

*此處公式有問題，約束條件左邊應(yīng)除以一個||w||即我們希望最大化超平面(w,b)關(guān)于訓(xùn)練數(shù)據(jù)集的幾何間隔，約束條件表示的是超平面(w,b)關(guān)于每個訓(xùn)練樣本點的幾何間隔至少是γ?？紤]到幾何間隔和函數(shù)間隔的關(guān)系式，可將這個問題改寫為：第十四頁，共六十二頁，編輯于2023年，星期六間隔最大化函數(shù)間隔的取值并不影響最優(yōu)化問題的解。事實上，假設(shè)將w和b按比例改變?yōu)棣藈和λb,這時函數(shù)間隔成為λγ’。函數(shù)間隔的這一改變對上面最優(yōu)化問題的不等式約束，對目標(biāo)函數(shù)的優(yōu)化也沒有影響，也就是說，它產(chǎn)生一個等價的最優(yōu)化問題。這樣，就可以取γ’=1,將γ’=1代入前面的最優(yōu)化問題，也即是將離超平面最近的點的距離定義為1/||w||，由于最大化1/||w||和最小化1/2||w||2等價，于是得到下面的線性可分支持向量機學(xué)習(xí)的最優(yōu)化問題：

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

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

第十九頁，共六十二頁，編輯于2023年，星期六條件極值與拉格朗日乘數(shù)法例：要設(shè)計一個容量為V

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

的極值。第二十頁，共六十二頁，編輯于2023年，星期六條件極值與拉格朗日乘數(shù)法條件極值的一種求解方法是代入法.，將條件極值化為無條件極值。例如，在上述例子中，由條件

解出代入目標(biāo)函數(shù)中，

得到

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

解出m

個變元常常是不可能的.下面介紹的拉格朗日乘數(shù)法是求條件極值的一種有效方法.第二十一頁，共六十二頁，編輯于2023年，星期六條件極值與拉格朗日乘數(shù)法

可確定函數(shù)

則問題等價于一元函數(shù)

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

必滿足因

故有即

記極值點必滿足想法：把上面的條件極值點轉(zhuǎn)化為一般極值點問題第二十二頁，共六十二頁，編輯于2023年，星期六條件極值與拉格朗日乘數(shù)法構(gòu)造一個函數(shù)使得其極值點就是上面函數(shù)的條件極值點引入輔助函數(shù)則極值點滿足:輔助函數(shù)L稱為拉格朗日(Lagrange)函數(shù).利用拉格朗日函數(shù)求極值的方法稱為拉格朗日乘數(shù)法.第二十三頁，共六十二頁，編輯于2023年，星期六條件極值與拉格朗日乘數(shù)法利用拉格朗日乘數(shù)法求函數(shù)

在條件

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

先求解拉格朗日函數(shù)的偏導(dǎo)數(shù)構(gòu)成的方程組再考察駐點是否是極值點第二十四頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第二十五頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第二十六頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第二十七頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第二十八頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第二十九頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第三十頁，共六十二頁，編輯于2023年，星期六拉格朗日對偶性第三十一頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十二頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十三頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十四頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十五頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十六頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十七頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十八頁，共六十二頁，編輯于2023年，星期六對偶算法求解第三十九頁，共六十二頁，編輯于2023年，星期六對偶算法求解第四十頁，共六十二頁，編輯于2023年，星期六對偶算法求解第四十一頁，共六十二頁，編輯于2023年，星期六對偶算法求解第四十二頁，共六十二頁，編輯于2023年，星期六對偶算法求解第四十三頁，共六十二頁，編輯于2023年，星期六對偶算法求解第四十四頁，共六十二頁，編輯于2023年，星期六對偶算法求解第四十五頁，共六十二頁，編輯于2023年，星期六最大間隔分離超平面的存在唯一性第四十六頁，共六十二頁，編輯于2023年，星期六最大間隔分離超平面的存在唯一性第四十七頁，共六十二頁，編輯于2023年，星期六第二部分線性支持向量機

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