文章目錄

• 優化目標：
• 優化步驟：
• 對偶問題本質：
• 選擇第一個樣本點標準：
• • 選擇第一個樣本點標準為：最不滿足KKT條件的樣本
  • 如何判斷樣本點是否滿足KKT條件？
  • • 滿足和不滿足KKT的情況:
    • 量化不滿足KKT條件的程度：
• 選擇第二個樣本點標準：
• SMO算法描述：

優化目標：

針對上述問題，使用比較成熟的二次凸優化的問題，類似于坐標下降方式，每次只優化一個方向，其他方向固定，在這個特定的問題里因為約束條件限制變量存在依賴關系，每次選擇兩個變量，這兩個變量存在依賴關系，可以轉化成一個變量，類似于坐標下降方法求解：

優化步驟：

1、考察所有變量（α1,…,αN）及對應的樣本點（(x1,y1),…,(xN,yN)）滿足 KKT 條件的情況。
2、若所有變量及對應樣本在容許誤差內都滿足 KKT 條件，則退出循環體、完成訓練
3、否則、通過如下步驟選出兩個變量來構造新的規劃問題：
a、選出違反 KKT 條件最嚴重的樣本點、以其對應的變量作為第一個變量。
b、第二個變量的選取有一種比較繁復且高效的方法，但對于一個樸素的實現而言、第二個變量可以隨機選取。
4、將上述步驟選出的變量以外的變量固定、僅針對這兩個變量進行最優化。易知此時問題轉化為了求二次函數的極大值、從而能簡單地得到解析解。

對偶問題本質：

實際上是對每一個樣本的權重做規劃，支持向量對應的樣本點權重為正，非支持向量的權重為0，從這個角度：我們優化時是在優化每一個樣本點的權重。

選擇第一個樣本點標準：

選擇第一個樣本點標準為：最不滿足KKT條件的樣本

選擇那些不滿足KKT條件的樣本點，當所有的樣本點都滿足KKT條件了，我們就找到了對應的解了。
為什么呢？因為最終的最優解肯定是都是滿足KKT條件的，這個是KKT條件里定義了的。

我們的解要滿足的KKT條件的對偶互補條件為：$${\alpha }_i^{?}(y_i(w^T{x}_i+b)?1+{\xi }_i^{?})=0$$
根據這個KKT條件的對偶互補條件，我們有：$${\alpha }_i^{?}=0?y_i(w^{?}??(x_i)+b)\ge 1$$ $$0<={\alpha }_i^{?}<=C?y_i(w^{?}??(x_i)+b)=1$$ $${\alpha }_i^{?}=C?y_i(w^{?}??(x_i)+b)\le 1$$
由于$w^{?}=\sum _{j=1}^m{\alpha }_j^{?}{y}_j?(x_j)$,我們令$g(x)=w^{?}??(x)+b=\sum _{j=1}^m{\alpha }_j^{?}{y}_{j}K(x,x_j)+b^{?}$，則有： $${\alpha }_i^{?}=0?y_{i}g(x_i)\ge 1$$ $$0<{\alpha }_i^{?}<C?y_{i}g(x_i)=1$$ $${\alpha }_i^{?}=C?y_{i}g(x_i)\le 1$$

假如所有的${\alpha }_i^{?}$都滿足對偶互補條件，也就是所有的樣本都滿足KKT條件，那么我們就找到了我們的優化目標。

如何判斷樣本點是否滿足KKT條件？

滿足和不滿足KKT的情況:

首先我們知道滿足KKT條件的三種情況：
1.y[i]*g(i)>=1 且 alpha=0,樣本點落在最大間隔外(分類完全正確的那些樣本)
2.y[i]*g(i)=1 且 alpha<C,樣本點剛好落在最大間隔邊界上
3.y[i]*g(i)<=1 且 alpha=C,樣本點落在最大間隔內部
那么不滿足的情況：
1.若y[i]*g(i)<1,如果alpha<C，那么就違背KKT(alpha=C 才正確)
2.若y[i]*g(i)>1,如果alpha>0,那么就違背KKT(alpha==0才正確)
3.若y[i]*g(i)==1,仍滿足KKT條件，無需進行優化

量化不滿足KKT條件的程度：

我們使用函數間隔來衡量誤差，具體就是函數間隔與1的距離：

每一個樣本點都有三種可能情況是否滿足KKT的條件，上面介紹過：
1.y[i]*g(i)>=1 且 alpha=0,樣本點落在最大間隔外(分類完全正確的那些樣本)
2.y[i]*g(i)=1 且 alpha<C,樣本點剛好落在最大間隔邊界上
3.y[i]*g(i)<=1 且 alpha=C,樣本點落在最大間隔內部
我們考慮這3種情況，計算每種情況下的誤差，3種情況下的誤差平方和最大的樣本點就是偏離KKT條件最嚴重的樣本點。

正確的操作步驟應該是如下：
1、計算每一樣本的誤差$c_i$；
2、判斷每一個樣本是否滿足KKT條件，不滿足的化，記錄下來并記錄誤差
3、在不滿足KKT的樣本里面找|$c_i$|最大的樣本點。

上圖的那個操作步驟也可以：
1、把$c_i$復制三份，分別對應：alpha=0，alpha<C，alpha=C三種情況
2、alpha=0時，找出所有alpha=0的樣本點（不是這種情況的，其他兩種情況會考慮，損失置為0），滿足y[i]*g(i)>=1，誤差損失置為0
3、0<alpha<C時，找出所有0<alpha<C的樣本點（不是這種情況的，其他兩種情況會考慮，損失置為0），滿足y[i]*g(i)=1，誤差損失置為0
4、alpha=C時，找出所有alpha=C的樣本點（不是這種情況的，其他兩種情況會考慮，損失置為0），滿足y[i]*g(i)<=1，誤差損失置為0

選擇第二個樣本點標準：

選擇第二樣本點時，需要選擇和第一個樣本點偏離最大的樣本點。

假設在外層循環中已經找到第1個變量${\alpha }_1$，現在要在內層循環中找第2個變量${\alpha }_2$。第2個變量選擇的標準是希望能使${\alpha }_2$有足夠大的變化。

第二個變量${\alpha }_2^{new}$的選擇標準是讓|$E_1$?$E_2$|有足夠大的變化。由于${\alpha }_1$定了的時候,$E_1$也確定了，所以要想|$E_1$?$E_2$|最大，只需要在$E_1$為正時，選擇最小的$E_i$作為$E_2$， 在$E_1$為負時，選擇最大的$E_i$作為$E_2$，可以將所有的$E_i$保存下來加快迭代。

SMO算法描述：

總結

以上是生活随笔為你收集整理的机器学习：SVM训练，SMO算法描述，启发式选择样本或变量的全部內容，希望文章能夠幫你解決所遇到的問題。

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