MachineLearing—SVM

  • 2019 年 10 月 6 日
  • 筆記

yix今天我們來看看機器學習中的SVM,SVM是什麼呢,它的中文名叫支持向量機(Support Vector Machine),是機器學習中的一種分類算法。

SVM,在機器學習里他就是個分類器,當它用於回歸分類的時候又叫SVR(Support Vector Regression)。

一般的我們會在什麼時候使用SVM呢?

我們來看看這一張圖:

對於A這張圖我們可以從圖中很顯然的看出來有兩類數據集,而且他們是很均勻的分別在左右兩側。我們可以使用一條直接直接將這兩個分類劃分開,如下圖:

或者是這樣:

又或者是這樣:

從上面三個圖中我們可以很明顯看出上面的三種不同的直線都能將圖中的方點和圓點分成兩類,這就是我們使用SVM的一個場景了,使用一條直線(你可以理解成一個一次函數)將數據集有效的劃分成兩類。

那麼我們的問題來了,就從上面這個例子來說,我們有無數根直線都能將他們劃分開,難道這無數根直線都是我們的解嗎?

當然不是的,我們需要做的是從這無數個直線中找出最優解,這才是我們SVM乾的事情。

那下面我們來解釋解釋它的工作原理:

圖像中的蘋果和香蕉正好是我們要劃分的兩類,我們要做的事情是什麼,要保證距離香蕉最近的蘋果是最遠的。

這句話好像有點繞口,那我們解釋一下:意思就是從蘋果類中找出一個蘋果,它的距離是距離所以香蕉是最近的,同時我們要保證這個距離要盡量的遠。

所以,現在我們明確了我們現在要做什麼了:

A、尋找最大分類間距

B、轉而通過拉格朗日函數求優化的問題

下面我們要解釋兩個概念:

線性可分數據和分隔超平面

數據可以通過畫一條直線就可以將它們完全分開,這組數據叫線性可分(linearly separable)數據,而這條分隔直線稱為分隔超平面(separating hyperplane)。

我們是不是發現了,一條線分隔了一個平面,也就是說一維的東西分隔了而為的數據,同樣的道理,二維的平面可以分隔三維的空間(你家的房子被你家的牆劃分成兩個空間),所以我們可以知道,對於N維的數據,我們需要N-1維的對象來進行分隔,這就是分類的決策邊界。

要點:尋找最大間隔

為什麼要找最大間隔?

1、感官上它是安全的(確實是,毋庸置疑)

2、假如在邊界的位置發生一個很小的錯誤,邊界的點在垂直方向上被顛倒了,這個小小的錯誤就會導致我們的分類錯誤。

3、交叉驗證很容易。

4、我們數學上求一根直線到一個圓最安全的距離,不就是找那個圓上那個最近的那個點,要求這個點距離直線儘可能的遠。實在不行你就看第五點。

5、前人的經驗,加上本人的經驗告訴你,就該這麼干!

OK,我們如何去尋找最大間隔?

還記得我們在高中的時候學過的點到直線的距離公式嗎?

在這裡我們也同樣使用,首先我們先要表示分隔超平面,他們的函數間距為:

(y(x)=w^Tx+b)

分類的結果表示為:

(f(x)=sign(w^Tx+b)) (sign表示>0為1,<0為-1,=0為0)

點到超平面的幾何間距:

(d(x)=(w^Tx+b)/||w||)

||w||表示w矩陣的二範數=> (sqrt{w^T*w}), 點到超平面的距離也是類似的。

OK,下面我們來使用拉格朗日乘子法來優化我們的求解:

  • 類別標籤用-1、1,是為了後期方便 (label*(w^Tx+b)) 的標識和距離計算;如果 (label*(w^Tx+b)>0) 表示預測正確,否則預測錯誤。
  • 現在目標很明確,就是要找到wb,因此我們必須要找到最小間隔的數據點,也就是前面所說的支持向量
    • 也就說,讓最小的距離取最大.(最小的距離:就是最小間隔的數據點;最大:就是最大間距,為了找出最優超平面–最終就是支持向量)
    • 目標函數:(arg: max_{關於w, b} left( min[label*(w^Tx+b)]*frac{1}{||w||} right) )
    1. 如果 (label*(w^Tx+b)>0) 表示預測正確,也稱函數間隔,(||w||) 可以理解為歸一化,也稱幾何間隔
    2. 令 (label*(w^Tx+b)>=1), 因為0~1之間,得到的點是存在誤判的可能性,所以要保障 (min[label*(w^Tx+b)]=1),才能更好降低噪音數據影響。
    3. 所以本質上是求 (arg: max_{關於w, b} frac{1}{||w||} );也就說,我們約束(前提)條件是: (label*(w^Tx+b)=1)
  • 新的目標函數求解: (arg: max_{關於w, b} frac{1}{||w||} )
    • => 就是求: (arg: min_{關於w, b} ||w|| ) (求矩陣會比較麻煩,如果x只是 (frac{1}{2}*x^2) 的偏導數,那麼。。同樣是求最小值)
    • => 就是求: (arg: min_{關於w, b} (frac{1}{2}*||w||^2)) (二次函數求導,求極值,平方也方便計算)
    • 本質上就是求線性不等式的二次優化問題(求分隔超平面,等價於求解相應的凸二次規劃問題)
  • 通過拉格朗日乘子法,求二次優化問題
    • 假設需要求極值的目標函數 (objective function) 為 f(x,y),限制條件為 φ(x,y)=M # M=1
    • 設g(x,y)=M-φ(x,y) # 臨時φ(x,y)表示下文中 (label*(w^Tx+b))
    • 定義一個新函數: F(x,y,λ)=f(x,y)+λg(x,y)
    • a為λ(a>=0),代表要引入的拉格朗日乘子(Lagrange multiplier)
    • 那麼: (L(w,b,alpha)=frac{1}{2} * ||w||^2 + sum_{i=1}^{n} alpha_i * [1 – label * (w^Tx+b)])
    • 因為:(label*(w^Tx+b)>=1, alpha>=0) , 所以 (alpha*[1-label*(w^Tx+b)]<=0) , (sum_{i=1}^{n} alpha_i * [1-label*(w^Tx+b)]<=0)
    • 當 (label*(w^Tx+b)>1) 則 (alpha=0) ,表示該點為非支持向量
    • 相當於求解: (max_{關於alpha} L(w,b,alpha) = frac{1}{2} *||w||^2)
    • 如果求: (min_{關於w, b} frac{1}{2} *||w||^2) , 也就是要求: (min_{關於w, b} left( max_{關於alpha} L(w,b,alpha)right))
  • 現在轉化到對偶問題的求解
    • (min_{關於w, b} left(max_{關於alpha} L(w,b,alpha) right) ) >= (max_{關於alpha} left(min_{關於w, b} L(w,b,alpha) right) )
    • 現在分2步
    • 先求: (min_{關於w, b} L(w,b,alpha)=frac{1}{2} * ||w||^2 + sum_{i=1}^{n} alpha_i * [1 – label * (w^Tx+b)])
    • 就是求L(w,b,a)關於[w, b]的偏導數, 得到w和b的值,並化簡為:L和a的方程
    • 參考: 如果公式推導還是不懂,也可以參考《統計學習方法》李航-P103<學習的對偶算法>
    • 終於得到課本上的公式: (max_{關於alpha} left( sum_{i=1}^{m} alpha_i – frac{1}{2} sum_{i, j=1}^{m} label_i·label_j·alpha_i·alpha_j·<x_i, x_j> right) )
    • 約束條件: (a>=0) 並且 (sum_{i=1}^{m} a_i·label_i=0)

這裡我們解釋一下SVM的鬆弛變量,可以參考:https://blog.csdn.net/wusecaiyun/article/details/49659183

之前討論的情況都是建立在樣例線性可分的假設上,當樣例線性不可分時,我們可以嘗試使用核函數來將特徵映射到高維,這樣很可能就可分了。然而,映射後我們也不能100%保證可分。那怎麼辦呢,我們需要將模型進行調整,以保證在不可分的情況下,也能夠儘可能地找出分隔超平面。

看下面兩張圖:

可以看到一個離群點(可能是噪聲)可以造成超平面的移動,間隔縮小,可見以前的模型對噪聲非常敏感。再有甚者,如果離群點在另外一個類中,那麼這時候就是線性不可分了。

這時候我們應該允許一些點遊離並在在模型中違背限制條件(函數間隔大於1)。我們設計得到新的模型如下(也稱軟間隔):

  • 我們知道幾乎所有的數據都不那麼乾淨, 通過引入鬆弛變量來 允許數據點可以處於分隔面錯誤的一側
  • 約束條件: (C>=a>=0) 並且 (sum_{i=1}^{m} a_i·label_i=0)
  • 總的來說:
    • (label*(w^Tx+b) > 1) and alpha = 0 (在邊界外,就是非支持向量)
    • (label*(w^Tx+b) = 1) and 0< alpha < C (在分割超平面上,就支持向量)
    • (label*(w^Tx+b) < 1) and alpha = C (在分割超平面內,是誤差點 -> C表示它該受到的懲罰因子程度)
    • 參考地址:https://www.zhihu.com/question/48351234/answer/110486455
    • &i是鬆弛變量,常量C是懲罰因子, 表示離群點的權重(用於控制「最大化間隔」和「保證大部分點的函數間隔小於1.0」 )
    • C值越大,表示離群點影響越大,就越容易過度擬合;反之有可能欠擬合。
    • 我們看到,目標函數控制了離群點的數目和程度,使大部分樣本點仍然遵守限制條件。
    • 例如:正類有10000個樣本,而負類只給了100個(C越大表示100個負樣本的影響越大,就會出現過度擬合,所以C決定了負樣本對模型擬合程度的影響!,C就是一個非常關鍵的優化點!)
  • 這一結論十分直接,SVM中的主要工作就是要求解 alpha.

SMO 高效優化算法(用於訓練SVM)

創建一個 alpha 向量並將其初始化為0向量  當迭代次數小於最大迭代次數時(外循環)     對數據集中的每個數據向量(內循環):         如果該數據向量可以被優化             隨機選擇另外一個數據向量             同時優化這兩個向量             如果兩個向量都不能被優化,退出內循環     如果所有向量都沒被優化,增加迭代數目,繼續下一次循環
  • SMO目標:求出一系列 alpha 和 b,一旦求出 alpha,就很容易計算出權重向量 w 並得到分隔超平面。
  • SMO思想:是將大優化問題分解為多個小優化問題來求解的。
  • SMO原理:每次循環選擇兩個 alpha 進行優化處理,一旦找出一對合適的 alpha,那麼就增大一個同時減少一個。

開始SVM開發:

Step1收集數據:可以使用任意方法。

Step2準備數據:需要數值型數據。

Step3分析數據:有助於可視化分隔超平面。

Step4訓練算法:SVM的大部分時間都源自訓練,該過程主要實現兩個參數的調優。

Step5測試算法:十分簡單的計算過程就可以實現。

Step6使用算法:幾乎所有分類問題都可以使用SVM,值得一提的是,SVM本身是一個二類分類器,對多類問題應用SVM需要對代碼做一些修改。

準備數據:

對文件進行逐行解析,從而得到第行的類標籤和整個特徵矩陣

訓練算法:

參數:

dataMatIn 特徵集合

classLabels 類別標籤

C 鬆弛變量(常量值),允許有些數據點可以處於分隔面的錯誤一側。(

控制最大化間隔和保證大部分的函數間隔小於1.0這兩個目標的權重。可以通過調節該參數達到不同的結果。)

toler 容錯率(是指在某個體系中能減小一些因素或選擇對某個系統產生不穩定的概率。)

maxIter 退出前最大的循環次數

返回值:

b 模型的常量值

alphas 拉格朗日乘子

詳細代碼見:

https://www.bytelang.com/o/s/c/YPmOea33zyQ=