支持向量機：SVM

來自專欄 機器學習與圖像處理

文章首發於公眾號：輪子工廠。想要學習機器學習得同學在公眾號後台回復關鍵字：機器學習，可獲取李宏毅教授整套機器學習視頻與課件。

介紹

• 支持向量機主要由兩部分組成：折頁損失函數(Hinge Loss)和核方法(Kernel Method)

損失函數

• 假設我們輸入的數據格式如下：

• 其中x表示數據向量，y表示數據標籤，標籤分為兩類，即+1和-1.在這裡去模型函數為：

• 所以分類用的損失函數為：

• 其中定義當計算出的函數值於標籤不相等的時候取1，相等的時候取0，但是這樣得到的函數有一點不好，它無法進行微分，即無法進行梯度下降。所以我們採用了另外一種函數作為損失函數，即：

對各種損失函數的討論

• 在下面我們將討論各種損失函數的特性，如下圖所示：

• 在上圖中，橫坐標是 ,如果預測的符號於原始標籤的符號是相同的，那麼它們的損失值為0，如果符號相反則損失值為1，其中黑色的線是理想損失函數曲線，但是可以明顯的看到這是一個不可微分的函數，所以我們使用了近似損失函數進行代替，這個近似損失函數可以由多種選擇，下面將對每一種可能的選擇進行討論：
• 其中紅色曲線是二次函數曲線，其損失函數的表達式為:

• 我們可以看到當數據的標籤值是 +1 的時候，預測值為 +1 可以達到最小的損失；當標籤值為 -1 的時候，預測值為 -1 可以達到最小的損失。所以當 的時候取到最小的損失函數值，但是在後面這個函數就是不合理的，因為隨著預測值逐漸變大，損失函數的取值居然越來越大，這明顯是不合理的。
• 接下來我們考慮使用sigmoid+square loss作為損失函數，其函數曲線是藍色的那一條，具體的損失函數如下：

• 從表達式可以看出，如果 ，那麼整體的函數值將趨近於 ln1=0，如果 ，那麼整體的函數值將趨近於 ∞，所以函數曲線如上圖。這個函數曲線是合理的，因為隨著 y^nf(xn) 的增加函數值會逐漸下降。對比 sigmoid + square loos 作為損失函數的方法，我們可以看到，當自變數（橫坐標對應的值）取到負無窮的時候， sigmoid + cross entropy 會有很大的梯度值，而 sigmoid + square loos 的梯度值幾乎為0，也就是說，前者在梯度下降的過程中，主要努力就會得到回報，而後者沒有回報，所以也很有可能不想努力。另一點，在這裡我們將交叉熵的函數值除以了 ln2，主要目的是希望可以得到理想損失函數的一個上界。
• 最後我們來考慮折頁損失函數(Hinge Loss)，具體表達式以及函數曲線如下圖所示：

如上的損失函數，我們可以看到，對於一個正例，如果 f(x)>1，那麼便得到了一個完美的分類結果，如果是反例的話，如果 f(x)<?1，那麼便得到了一個完美的分類結果。所以x 不用太大，因為大了函數值也是相同的。觀察函數曲線可以知道，當 的時候，就已經夠好了，但是它們同向卻在 penalty 認為實際上還不夠好，雖然可以正確分類了，但是損失函數仍然或讓自變數向右移動變得更好，這個區間也就是所謂的邊界(margin)。其中損失函數中取 1 的原始，它可以得到理想損失函數的一個緊緻的上界。

• 如果我們對比交叉熵函數和折頁損失函數的話，它們最大的區別在於對待已經正確分類的例子的態度。如果將圖中的黑點從1 的位置移動到 2 的位置，我們可以看到交叉熵損失函數的函數值會繼續下降，也就是說它在已經得到好的結果之後還希望得到更好的結果；但是折頁函數是一種及格就好的函數，當大於margin的時候就好了。在實際的使用中，折頁函數略優於交叉熵損失函數，就是說沒有領先的很多。但是折頁函數更能夠顧全全局，當進行多分類的時候得到的效果會更好。

線性SVM分類器

• 線性的SVM的步驟主要如下圖所示分為三部：

• 第一部分是目標函數，這裡使用如上圖所示的目標函數，它可以表示為兩個向量之間的點積運算，進而可以表示為權重的轉置與輸入 x 的相乘。
• 第二步，構建損失函數，這裡使用的是折頁損失函數和 L2 的正則項，因為前面的損失函數明顯是一個凸函數，後面的正則化項也明顯是一個凸函數，所以這些的組合也是一個凸函數；
• 這樣在第三步就可以使用梯度下降的方法更新參數。有的人可能會想，這個函數是分段線性的可以使用梯度下降嘛，可以的。想想之前的RElu，也是這樣的啊，同樣可以使用梯度下降的方法進行訓練。
• 在這裡我們可以看到，實際上邏輯回歸和線性的 SVM 之間的區別就在於 損失函數的不同。另一方面，通過第一步我們可以看出，實際上SVM與神經網路之間是相通的，所以在2013年的ICML中有一篇文章是「Deep Learning Using Linear Support Vector Machines」。

使用梯度下降訓練SVM

• 首先我們將損失函數中折頁損失函數取出，並判斷下面兩個等式是否相等：

實際上僅僅考慮這兩個等式，他們之間是不相等的，但是同時考慮最小化如下的損失函數的話，兩者就是相同的了：

這個時候我們用 ? 代替原來的折頁損失函數，這裡 ? 滿足之前紅色框框內的兩個不等式，所以在這裡我們認為他是鬆弛變數，而這樣的問題可以使用二次規劃的方法進行求解。

核方法

對偶表示

• 最後分類函數的權重實際上是輸入數據的線性組合，如下圖所示

• 造成這種結果的原始，實際上可以通過之前所講的利用梯度下降的方法更新參數的角度進行考慮。如上圖所示，我們將所有的權重更新的過程合併成一個向量，其中的折頁損失函數的導數記為 ，他的具體表達式也如上圖所示。如果我們將權重的初始值設為0 的話，那麼參數 w 實際上就是輸入數據的線性組合，另外因為對於折頁損失函數來講，它裡面有很多零的值，所以係數 α 中有很多的0，這樣權重實際上是輸入數據的稀疏組合，其中稀疏不為零所對應的數據點稱為支持向量。這樣的結果導致模型的魯棒性更強，即使有離群值的點或者不合理的點，只要不選取它們作為支持向量，那麼對於分類結果的影響並不大。
• 由於在上面的部分已經證明了，SVM的權重實際上是通過輸入點的線性組合得到，因此它可以表示為如下的形式：

• 這裡是將原來的求和轉變為了向量相乘的形式，這個表達方式在機器學習中是常常使用的。在得到了的權重的對偶表達方式之後，第一步是進行變數替代，如下圖所示

• 將 w 帶入之後可以看到 f(x) 主要這三部分組成，第一部分是係數 α ，他是一個行向量，一共有 N 列，後面的兩項可以使用矩陣乘法的結合律，得到一個列向量，一共有 N 行。所以 f(x) 可以表示為上圖那種形式，將其中的 可以表示為 ，我們將K稱為核方法。
• 如下圖所示，經目標函數表達為係數與 的線性組合之後，接下來的任務就是最小化損失函數：

• 其中需要注意的是，雖然後一項中有 n 還有 n′ ，但是這兩個的求和範圍是相同的，只不過先對 n′ 進行求和運算再對 n 進行求和運算。在這裡我們不是真的需要知道向量 xn，只需要知道向量 xn 與 xn′ 的內部關係即可。這種方法就叫做核技巧(Kernel Trick)。

核技巧（Kernel Trick）

• 當我們將原來的數據點映射到高維空間的時候，這個時候使用核技巧往往是十分有用的，如下圖所示:

• 如上圖中我們將 x 映射到 Φ(x)，這個時候我們計算轉化到高維再做點積，通過化簡可以知道這個過程等價於先對原始數據進行點積，之後再平方。這種方式主要在輸入數據是高維數據的時候可以減少大量的計算量，如下圖所示:

• 如果首先做高維映射的話，需要進行 乘法得到高維數據的點，之後再讓高維的點之間進行點積，一共需要 次乘法。但是如果首先進行內積運算在進行平方運算的話，需要計算 k+1 次乘法。這個計算量明顯要小很多。所以核技巧的主要作用是減少計算量。
• 下面再以徑向基核(Radial Basis Function Kernel)為例進行介紹

• 我們可以看到如果將徑向基函數用泰勒公式展開的話,我們可以看到是無窮多項的求和，所以是沒有辦法通過先向高維映射，之後在進行點積的方法求解的。另外通過上面的過程我們也可以了解到，實際上RBF(Radial Basis Function)核實際上是一種在無窮維上的分類器，雖然效果比較好，但是也十分容易過擬合。
• 接著我們以 Sigmoid 核為例進行介紹

• 我們實際上可以看到 f(x) 的計算過程可以通過如下的神經網路進行計算，對於輸入的數據 x ，它首先與 x1 做點積，這個過程實際上即使在計算第一個神經元的加權輸入，一共有 n 個這樣的神經元，它們與對應的係數相乘再相加就可以可到目標函數 f(x)。因此使用 Sigmoid 核的SVM實際上是一個只包含一個隱層，激活函數為 Sigmoid 函數的神經網路。
• 並不是所有的先對向量做點積再做其他操作都有對應的核函數，只有滿足Mercer』s theory can check的才可以。

深度學習與支持向量機的關係

• 深度學習與支持向量機在原理上有很大的相關性，具體如下圖所示:

• 深度學習前面的隱層實際上是在做特徵的高維映射，最後使用一個線性的分類器進行分類；
• 而SVM使用核方法對數據進行非線性映射，之後在使用線性分類器進行分類。
• 兩者都是先特徵映射再做分類的方法，這裡實際上SVM的核方法也是可學習的，但是它們沒有辦法學習到深度學習那種程度。
• 當你使用多個核函數的時候，對於兩個核之間的連接的權重是可以學習的，就好像之前的SVM只有一個隱層，當使用多核方法的時候就相當於有多個隱層，那麼它們之間權重就是可學習的了。

為你推薦一下文章：