目錄

1.導出目標

2拉格朗日轉換

3對偶問題：

因為是希望得出L最小時的一些參數w,b,a，但是目前很難一起求得最佳參數，所以換個思路。因為：

所以能夠容易的計算出拉格朗日乘子a約束時的最壞情況是：

但是m個a的值還是無法求出，而后面會得知，根據L對w,b的求導關系，w,b可以被a表示出來，所以關鍵變為求a。

根據對偶關系，極大值關系可以轉為極小值關系，且轉換后的問題會不大于原問題，在取得極值的時候才取等號，也就是：

這樣問題變為，先把w,b求導關系代入求L極小值關系，最后再尋找a的問題，最后a的求解會通過SMO等思路求解，具體SMO放到最后講解，因為太難了。

4求對偶問題

1)求L的極小值時的w,b，求導：

得出極小值需滿足如上這些關系

2)代入L求導關系式，求關于a的極大值：

所以關鍵是對這個函數求極大值時的a，假設通過后面的SMO找到了，記為a*，那么顯然得到了w的解析式：

5 求b

因為對于所有支持向量點(正例上支持向量點位于WTx+b = 1超平面上，反例WTx+b= -1)記作(xs,ys)，均有:

根據KKT條件：ai>0時，yi(WTxi+b)-1=0：(必定：WTxi+b = 1 或WTxi+b= -1)即xi必須是支持向量點，而ai=0時:

也就是說對w無影響，因此上式中w還可以簡化成只考慮支持向量點計算(實際上這就是SVM稱為支持向量機的原因，因為模型真正起作用的，就只是這些支持向量點)：

假設我們有S個支持向量(位于WTx+b = 1，WTx+b= -1超平面上的點集)，則對應我們求出S個b?,理論上這些b?都可以作為最終的結果， 但是我們一般采用一種更健壯的辦法，即求出所有支持向量所對應的b?，然后將其平均值作為最后的結果：

6 得出模型

ai參數求出之后，如上所示，就相當于求出了w,b了。就可以得到模型，進行預測了：

def _f(self, i):

r = self.b

for j in range(self.m):

r += self.alpha[j] * self.Y[j] * self.kernel(self.X[i], self.X[j])

return r

6.1 f(x)的約束條件：

7 核函數

現實中可能有些不存在線性的可分超平面，但是可能映射到更高維度可能就可分了，有證明顯示，如果原始空間維度有限，那么一定存在高維特征空間使樣本可分。

這樣對x的映射關系，可以直接用到上面推導的所有公式里：

原問題映射：

對偶形式映射：

這種映射我們并不知道具體是如何的，因此也不知如何去計算了，所以這里就設想出來核函數的概念了：

def kernel(self, x1, x2):

if self._kernel == 'linear':

return sum([x1[k] * x2[k] for k in range(self.n)])

elif self._kernel == 'poly':

return (sum([x1[k] * x2[k] for k in range(self.n)]) + 1) ** 2

return 0

假設出原來的這種內積映射，是等價于某個函數k(.,.)計算的結果。問題就變成了：

求解后模型為：

核函數性質

k是核函數，當且僅當’核矩陣’K總是半正定：

常見核函數列表：

另外核函數線性組合起來還是核函數(系數為正)，k1,k1,r1>0,r2>0：k3=r1k1+r2k2 也是核函數

7.1 軟間隔

討論軟間隔是因為像這種情況，嚴格分出來(線性不可分了已經，用核函數可以分)是個彎曲的，但實際上應該就是這下面這樣一條斜線才是最好的模型表示：

因此辦法是，允許在一些情況下出現錯誤，引入軟間隔的概念，在這個軟間隔內允許出錯。也就是允許不滿足約束：

對于不滿足的點，我們會累記一個損失函數，再引入懲罰力度因子C，則可以重新定義優化目標：

7.2 松弛變量：

顯然，這些損失是常數且>=0，因此引入松弛變量的概念替換原來的損害函數計算結果，重寫簡化：

上式進行拉格朗日變換：為什么這樣：https://blog.csdn.net/jiang425776024/article/details/87607526

同樣的求導，對偶和上面4一致，省略。最終得到如下對偶問題：

7.3?KKT約束

可見，與非軟間隔的問題相比，僅僅是對約束ai多了一個上界約束，且約束就是

這個約束是有道理的：

a) 如果α=0,那么yi(wTxi+b)?1≥0,即樣本在間隔邊界上或者已經被正確分類。

b)?如果0

c) 如果α=C，說明這是一個可能比較異常的點，需要檢查此時ξi

1)如果0≤ξi≤1,那么點被正確分類，但是卻在超平面和自己類別的間隔邊界之間

2)如果ξi=1,那么點在分離超平面上，無法被正確分類。

3)如果ξi>1,那么點在超平面的另一側，也就是說，這個點不能被正常分類

實現代碼，判斷是否否后KKT條件，True符合，False不符合：

def _KKT(self, i):

y_g = self._g(i) * self.Y[i]

if self.alpha[i] == 0:#a=0:需要yif(xi)-1>=0

return y_g >= 1

elif 0 < self.alpha[i] < self.C: #0

return y_g == 1

else:

return y_g <= 1 #a>=C:異常點,需要0≤ξi≤1滿足在區間內yif(xi)<=1

8 SMO求a

8.1對偶問題上，上面已知對偶形式:

8.2.SMO算法思想

在SMO算法中的思想是，每次選擇一對變量(αi,αj)進行優化，其余m-2個固定看作是常量, 因為在SVM中，α并不是完全獨立的，而是具有約束的:

因此一個只選一個ai，那么ai可以被其它表示。

假設我們選取的兩個需要優化的參數為α1,α2, 剩下的α3,α4,…,αm則固定作為常數處理。將SVM優化問題進行展開就可以得到(把與α1,α2無關的項合并成常數項C):(省略了a3+a4+...+am=C，因為其對max函數無意義)

8.2.1更新方法

因為y1,y2只能是1/-1，因此a1,a2的關系被限制在盒子里的一條線段上(只能是a1-a2/a1+a2兩種情況)，所以兩變量的優化問題實際上僅僅是一個變量的優化問題(一個能由另一個得出)。我們假設是對a2的優化問題,所以只存在2幅圖的情況：

1)y1!=y2,則約束a1y1+a2y2=k：a1-a2=k，L，H為約束下a2的最小最大值,為下圖

2)y1=y2:

if self.Y[i1] == self.Y[i2]:

L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)

H = min(self.C, self.alpha[i1] + self.alpha[i2])

else:

L = max(0, self.alpha[i2] - self.alpha[i1])

H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])

def _E(self, i):

return self._f(i) - self.Y[i]

則最優化問題轉為更新：

最終更新方式：

剪輯判斷：

def _compare(self, _alpha, L, H):

# 剪輯操作

if _alpha > H:

return H

elif _alpha < L:

return L

else:

return _alpha

a1,a2更新：

# 邊界

if self.Y[i1] == self.Y[i2]:

L = max(0, self.alpha[i1] + self.alpha[i2] - self.C)

H = min(self.C, self.alpha[i1] + self.alpha[i2])

else:

L = max(0, self.alpha[i2] - self.alpha[i1])

H = min(self.C, self.C + self.alpha[i2] - self.alpha[i1])

E1 = self.E[i1]

E2 = self.E[i2]

eta = self.kernel(self.X[i1], self.X[i1]) + self.kernel(self.X[i2], self.X[i2]) - 2 * self.kernel(

self.X[i1], self.X[i2])

if eta <= 0:

# print('eta <= 0')

continue

alpha2_new_unc = self.alpha[i2] + self.Y[i2] * (E1 - E2) / eta

alpha2_new = self._compare(alpha2_new_unc, L, H)

alpha1_new = self.alpha[i1] + self.Y[i1] * self.Y[i2] * (self.alpha[i2] - alpha2_new)

self.alpha[i1] = alpha1_new

self.alpha[i2] = alpha2_new

8.2.2 推導過程

則：

求導：

代入關系式，添加新舊標記方便迭代更新：

得：

得出上面的更新方式。

8.2.3選兩點a1,a2的方法

SMO每個子問題選擇兩個變量優化，其中至少一個變量是違法KKT條件的。

第1個變量a1的選擇

SMO稱選擇第一個變量的過程為外層循環，外層循環選取違反KKT條件最嚴重的樣本點(xi,yi)對應的ai值作為第一個變量a1；檢測是否滿足KKT條件(7.3有具體介紹)：

一般，外層循環先遍歷所有滿足0

第2個變量a2的選擇

SMO算法稱選擇第二一個變量為內層循環，假設我們在外層循環已經找到了α1, 第二個變量α2的選擇標準是讓|E1?E2|有足夠大的變化。8.2.1定義了E(預測值與真實值之差)。由于α1定了的時候,E1也確定了，所以要想|E1?E2|最大，只需要在E1為正時，選擇最小的Ei作為E2，在E1為負時，選擇最大的Ei作為E2，可以將所有的Ei保存為列表，加快迭代。

如果內存循環找到的點不能讓目標函數有足夠的下降，可以采用遍歷支持向量點來做α2,直到目標函數有足夠的下降， 如果所有的支持向量做α2都不能讓目標函數有足夠的下降，可以跳出循環，重新選擇α1。

def _init_alpha(self):

# 外層循環首先遍歷所有滿足0

總結

以上是生活随笔為你收集整理的svr公式推导_ML-支持向量：SVM、SVC、SVR、SMO原理推导及实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。