硬間隔最大化SVM
- SVM
-
- 介紹
- SVM轉化為最優解問題
- KKT
-
- KKT圖解
- KKT定理
- KKT例子
- 求解SVM最優化問題
- 拉格朗日對偶
-
- 拉格朗日對偶例子
- 用拉格朗日對偶解決問題
- KKT在SVM中的意義
- 測試
SVM
介紹
SVM是一種分類手段，就是找出一個超平面，将給定的資料集{(x1，y1),(x1，y2),…,(xn，yn)}分類(xi為特征向量，yi為類别，這邊分為兩類y=0或1)。這種超平面很多，但SVM分類是找到那個最優的超平面，即下圖中的藍色平面-------要求是margin（分隔間距）最大。
margin（分隔間距）最大：通俗了解就是這個平面向垂直于它的方向上下平移，所碰到的第一個點（上下都有）離它的距離和最大。
是以說SVM的目标就是如何去找到這個能使得margin最大的分類藍色超平面。
SVM轉化為最優解問題
我們先設超平面的方程為：wTx+b =0，兩側margin/2距離的平面方程設為：wTx+b =±c，為了友善起見c選為1：wTx+b =±1。
(為了了解友善，可設x為二維特征，式子就變成：w1 * x1+w2 * x2+b=0，可以看出w就是這個平面的法向量，b為截距）
是以呢，我們隻要求出w向量和 b值 ，就可解得超平面方程。
從上圖中可以看到，凡是在虛平面wTx+b =-1下方的樣本xi，wTx+b <=-1 都屬于y = -1類，在虛平面wTx+b =1上方的樣本xi，wTx+b >=1 都屬于y = 1類。
即if：wTx+b <=-1 則 y = -1
if：wTx+b >= 1 則 y = 1 ==》 y(wTx+b) >= 1 限制條件
現在算margin ：margin是 wTx+b =0和wTx+b =1 距離的兩倍。
（假設x二維，可參考兩直線的距離公式： w1x1+w2x2=0-b，w1x1+w2x2+b=1-b
d = |0-b-1+b| / (根号(w1的平方+w2的平方)) ）提升到高維距離距離就是1/||w||。
是以 margin = 2/||w||
我們期望的是距離最大即margin最大 ，也就是||w|| = wTw 最小。為了友善起見前面加個1/2.。
于是就成了個最優化問題 （注：限制條件是N組不等式 x是N維的）
KKT
對于求解不等式限制條件的優化問題，必須滿足KKT條件
KKT圖解
上圖所示圖中
f是目标函數 ，求其最小值。
g1(x)<=0,g2(x)<=0,g3(x)<=0為限制函數 。
▽則表示為梯度，梯度方向為函數增加最快的方向。
通過 反梯度方向及g(x) = 0 ,我們可以判斷出陰影部分三個函數都<=0，是x的取值範圍。
進一步的通過分析，不難确定x的取值應該是g1=0， g2=0的交點處。
似乎有沒有g3(x)<=0 這個限制條件x取值都一樣，此時我們稱 g1，g2條件是活躍的，g3是不活躍的。
且 ▽f 可以被活躍的兩個限制函數的梯度▽g1，▽g2表示出來。
▽f =α1 (-▽g1)+α2 (-▽g2) 且從圖中梯度方向不難看出 α1，α2都應該大于0。
為了整齊起見，不活躍的g3我們也加上去，隻是系數α3設為0
于是式子就變成▽f =α1 (-▽g1)+α2 (-▽g2)+α3 (-▽g3)
整理可得 ===》▽f +α1 (▽g1)+α2 (▽g2)+α3 (▽g3) = 0
(其中活躍限制條件系數>0,不活躍限制條件系數=0,總的來說α>=0）
KKT定理
以上就是KKT引導，下面給出KKT定理：
概括如下： 目标函數： f(x)
限制條件 (分兩類，一類是等式限制條件，一類是不等式)：
h(x) = 0, g(x)<=0(不等式都寫成<=形式)
KKT條件：
1.：▽f +α(▽g)+λ(▽h)=0
其中等式h(x)前的λ沒有限制就像正常的拉格朗日乘子法一樣。
2.不等式g(x)前的系數α則要大于等于0。(這個就是上面的α推導)
3.最後解讀 αTg(x) = 0 :
寫開就是: α1 (g1)+α2 (g2)+α3 (g3)+…+αn (gn)=0
因為α>=0 g<=0，他們兩都不等于0，相乘結果一定是負。要滿足αTg(x) = 0，如果α不等于0，g就必須等于0，反之也是。
這個結論和剛剛那張圖推導結果是一緻的，即g(x) = 0,說明他是活躍的，α>0，g(x) < 0,說明不活躍，α=0。
KKT例子
怎麼是橫的
如果實在不懂，可以看這篇文。
https://www.cnblogs.com/xinchen1111/p/8804858.html
求解SVM最優化問題
剛剛我們已經将SVM轉化為一個最優化問題。
為了滿足KKT條件，這邊的g(x)取: 1-y(wTx+b) <=0 ,α>=0
列出拉格朗日方程
是以對w，b求偏導等于0。
很多時候在現空間中是找不到一個線性超平面來區分樣本的是以引入核技巧，映射到高維空間中進行分類。
将樣本用核技巧進行處理後：
考慮到次元可能太高，是以用拉格拉日對偶解決問題
拉格朗日對偶
也沒研究過拉格朗日對偶，書上怎麼說，咱就怎麼做：
拉格朗日對偶例子
用拉格朗日對偶解決問題
求min 1/2wTw ,就是求max W(α)=L(w(α),b,α)(推導我不會)
我們需要把wTw，wTφxi，b化成關于α的式子
現在的問題就變成了這個：
下面證明W(α)有最大值，是一個半負定二次型，開口向下有最大值。
是以可求出W(α)的最大值時 的α值（這個計算有一種簡單的SMO算法）
知道α即可通過
求出w。
在通過：
求出b。
KKT在SVM中的意義
KKT條件在實體意義上對應的SVM含義
KKT的條件之一為αTg(x) = 0 ，α >=0, 其中 g(x) = 1-y(wTx+b) 。
可以在圖中看到凡是在wT+b=-1下方 或者 wT+b=1上方的樣本都有y(wTx+b) > 1
通過上述條件可得：此時α必定為0。
隻有在虛線上的的點 1-y(wTx+b)=0 此時α>0
而w是關于α的函數，α為0時，對應的樣本毫無意義，隻有在虛線上的點 α>0才真正起了作用。
是以真正參加運算的隻有邊緣那些點，這些點就叫支援向量
測試
代碼：https://blog.csdn.net/jirong5206/article/details/106032636
将測試樣本核化後代入超平面方程，大于0 ，小于0 分類。