支持向量機

在機器學習中，支援向量機（中國大陸稱支持向量機，support vector machine，常簡稱為SVM，又名支援向量網路）是在分類與迴歸分析中分析數據的監督式學習模型與相關的學習演算法。給定一組訓練實例，每個訓練實例被標記為屬於兩個類別中的一個或另一個，SVM訓練演算法建立一個將新的實例分配給兩個類別之一的模型，使其成為非機率二元分類器線性分類器。SVM模型是將實例表示為空間中的點，這樣映射就使得單獨類別的實例被儘可能寬的明顯的間隔分開。然後，將新的實例映射到同一空間，並基於它們落在間隔的哪一側來預測所屬類別。

除了進行線性分類之外，SVM還可以使用所謂的核技巧有效地進行非線性分類，將其輸入隱式映射到高維特徵空間中。

當數據未被標記時，不能進行監督式學習，需要用非監督式學習，它會嘗試找出數據到簇的自然聚類，並將新數據映射到這些已形成的簇。將支援向量機改進的聚類演算法被稱為支援向量聚類，當數據未被標記或者僅一些數據被標記時，支援向量聚類經常在工業應用中用作分類步驟的預處理。

## 動機

<image>

將數據進行分類是機器學習中的一項常見任務。

假設某些給定的數據點各自屬於兩個類之一，而目標是確定新數據點將在哪個類中。對於支持向量機來說，數據點被視為 $p$ 維向量，希望知道是否可以用 $(p-1)$ 維超平面來分開這些點。這就是所謂的線性分類器。可能有許多超平面可以把數據分類。最佳超平面的一個合理選擇是以最大間隔把兩個類分開的超平面。因此，要選擇能夠讓到每邊最近的數據點的距離最大化的超平面。如果存在這樣的超平面，則稱為最大間隔超平面，而其定義的線性分類器被稱為最大間隔分類器，或者叫做最佳穩定性感知器。

## 定義

更正式地來說，支持向量機在高維或無限維空間中構造超平面或超平面集合，其可以用於分類、回歸或其他任務。直觀來說，分類邊界距離最近的訓練資料點越遠越好，因為這樣可以縮小分類器的泛化誤差。

<image>

儘管原始問題可能是在有限維空間中陳述的，但用於區分的集合在該空間中往往線性可分。為此，有人提出將原有限維空間映射到維數高得多的空間中，在該空間中進行分離可能會更容易。為了保持計算負荷合理，人們選擇適合該問題的正定核 $k(x,y)$ 來定義SVM方案使用的映射，以確保用原始空間中的變量可以很容易計算點積。高維空間中的超平面定義為與該空間中的某向量的點積是常數的點的集合。定義超平面的向量可以選擇在數據集中出現的特徵向量 $x_i$ 的圖像的參數 $\alpha_i$ 的線性組合。通過選擇超平面，被映射到超平面上的特徵空間中的點集 $x$ 由以下關係定義：$\textstyle\sum_i \alpha_i k(x_i,x) = \mathrm{constant}.$ 注意，如果隨著 $y$ 逐漸遠離 $x$，$k(x,y)$ 變小，則求和中的每一項都是在衡量測試點 $x$ 與對應的數據基點 $x_i$ 的接近程度。這樣，上述內核的總和可以用于衡量每個測試點相對於待分離的集合中的數據點的相對接近度。

## 應用

- 用於文本和超文本的分類，在歸納和直推方法中都可以顯著減少所需要的有類標的樣本數。
- 用於圖像分類。實驗結果顯示：在經過三到四輪相關反饋之後，比起傳統的查詢優化方案，支持向量機能夠取得明顯更高的搜索準確度。這同樣也適用於圖像分割系統，比如使用Vapnik所建議的使用特權方法的修改版本SVM的那些圖像分割系統。
- 用於手寫字體識別。
- 用於醫學中分類蛋白質，超過90%的化合物能夠被正確分類。基於支持向量機權重的置換測試已被建議作為一種機制，用於解釋的支持向量機模型。支持向量機權重也被用來解釋過去的SVM模型。為識別模型用於進行預測的特徵而對支持向量機模型做出事後解釋是在生物科學中具有特殊意義的相對較新的研究領域。

## 歷史

原始SVM演算法是由蘇聯數學家弗拉基米爾·瓦普尼克和亞歷克塞·澤范蘭傑斯於1963年發明的。1992年，伯恩哈德·E·博瑟（Bernhard E. Boser）、伊莎貝爾·M·蓋昂（Isabelle M. Guyon）和瓦普尼克提出了一種通過將核技巧應用於最大間隔超平面來創建非線性分類器的方法。當前標準的前身（軟間隔）由科琳娜·科特斯和瓦普尼克於1993年提出，並於1995年發表。

## 線性SVM

我們考慮以下形式的 $n$ 點測試集：

$$(\vec{x}_1, y_1),\, \ldots ,\, (\vec{x}_n, y_n)$$

其中 $y_i$ 是 1 或者 −1，表明點 $\vec{x}_i$ 所屬的類。$\vec{x}_i$ 中每個都是一個 $p$ 維實向量。我們要求將 $y_i=1$ 的點集 $\vec{x}_i$ 與 $y_i=-1$ 的點集分開的 「最大間隔超平面」，使得超平面與最近的點 $\vec{x}_i$ 之間的距離最大化。

任何超平面都可以寫作滿足下面方程的點集 $\vec{x}$

$\vec{w}\cdot\vec{x} - b=0,\,$

<image>

其中 ${\vec{w}}$（不必是歸一化的）是該法向量。參數 $\tfrac{b}{\|\vec{w}\|}$ 決定從原點沿法向量 ${\vec{w}}$ 到超平面的偏移量。

### 硬間隔

如果這些訓練數據是線性可分的，可以選擇分離兩類數據的兩個平行超平面，使得它們之間的距離儘可能大。在這兩個超平面範圍內的區域稱為「間隔」，最大間隔超平面是位於它們正中間的超平面。這些超平面可以由方程：

$$\vec{w}\cdot\vec{x} - b=1\,$$

或是

$$\vec{w}\cdot\vec{x} - b=-1.\,$$

來表示。通過幾何不難得到這兩個超平面之間的距離是 $\tfrac{2}{\|\vec{w}\|}$，因此要使兩平面間的距離最大，我們需要最小化 $\|\vec{w}\|$。同時為了使得樣本數據點都在超平面的間隔區以外，我們需要保證對於所有的 $i$ 滿足其中的一個條件：

$\vec{w}\cdot\vec{x}_i - b \ge 1,$ 若 $y_i = 1$

或是

$\vec{w}\cdot\vec{x}_i - b \le -1,$ 若 $y_i = -1.$

這些約束表明每個數據點都必須位於間隔的正確一側。

這兩個式子可以寫作：

$$y_i(\vec{w}\cdot\vec{x}_i - b) \ge 1, \quad \text{ for all } 1 \le i \le n.\qquad\qquad(1)$$

可以用這個式子一起來得到優化問題：「在 $y_i(\vec{w}\cdot\vec{x_i} - b) \ge 1$ 條件下，最小化 $\|\vec{w}\|$，對於 $i = 1,\,\ldots,\,n$"這個問題的解 $\vec w$ 與 $b$ 決定了我們的分類器 $\vec{x} \mapsto \sgn(\vec{w} \cdot \vec{x} - b)$。

此幾何描述的一個顯而易見卻重要的結果是，最大間隔超平面完全是由最靠近它的那些 $\vec{x}_i$ 確定的。這些 $\vec{x}_i$ 叫做支持向量。

### 軟間隔

為了將SVM擴展到數據線性不可分的情況，我們引入鉸鏈損失函數，$\max\left(0, 1-y_i(\vec{w}\cdot\vec{x_i} - b)\right).$當約束條件 (1) 滿足時（也就是如果 $\vec{x}_i$ 位於邊距的正確一側）此函數為零。對於間隔的錯誤一側的數據，該函數的值與距間隔的距離成正比。

然後我們希望最小化$\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(\vec{w}\cdot \vec{x_i} - b)\right) \right] + \lambda\lVert \vec{w} \rVert^2,$其中參數 $\lambda$ 用來權衡增加間隔大小與確保 $\vec{x}_i$ 位於間隔的正確一側之間的關係。因此，對於足夠小的 $\lambda$ 值，如果輸入數據是可以線性分類的，則軟間隔SVM與硬間隔SVM將表現相同，但即使不可線性分類，仍能學習出可行的分類規則。

## 非線性分類

<image>

弗拉基米爾·瓦普尼克在1963年提出的原始最大間隔超平面演算法構造了一個線性分類器。而1992年，伯恩哈德·E·博瑟（Bernhard E. Boser）、伊莎貝爾·M·蓋昂（Isabelle M. Guyon）和瓦普尼克提出了一種通過將核技巧（最初由Aizerman et al.提出）應用於最大邊界超平面來創建非線性分類器的方法。所得到的演算法形式上類似，除了把點積換成了非線性核函數。這就允許演算法在變換後的特徵空間中擬合最大間隔超平面。該變換可以是非線性的，而變換空間是高維的；雖然分類器是變換後的特徵空間中的超平面，但它在原始輸入空間中可以是非線性的。

值得注意的是，更高維的特徵空間增加了支持向量機的泛化誤差，但給定足夠多的樣本，演算法仍能表現良好。

常見的核函數包括：

- 齊次多項式：$k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j})^d$
- 多項式核函數：$k(\vec{x_i},\vec{x_j})=(\vec{x_i} \cdot \vec{x_j} + 1)^d$
- 高斯徑向基函數：$k(\vec{x_i},\vec{x_j})=\exp(-\gamma \|\vec{x_i} - \vec{x_j}\|^2)$，其中 $\gamma > 0$。有時參數化表示 $\gamma=1/{2 \sigma^2}$
- 雙曲正切：$k(\vec{x_i},\vec{x_j})=\tanh(\kappa \vec{x_i} \cdot \vec{x_j}+c)$，其中一些（而非所有）$\kappa > 0$ 且 $c < 0$

由等式 $k(\vec{x_i}, \vec{x_j}) = \varphi(\vec{x_i})\cdot \varphi(\vec{x_j})$，核函數與變換 $\varphi(\vec{x_i})$ 有關。變換空間中也有 w 值，$\textstyle\vec{w} = \sum_i \alpha_i y_i \varphi(\vec{x}_i)$。與 w 的點積也要用核技巧來計算，即 $\textstyle \vec{w}\cdot\varphi(\vec{x}) = \sum_i \alpha_i y_i k(\vec{x}_i, \vec{x})$。

## 計算SVM分類器

計算（軟間隔）SVM分類器等同於使下面表達式最小化$\left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(w\cdot x_i + b)\right) \right] + \lambda\lVert w \rVert^2. \qquad(2)$如上所述，由於我們關注的是軟間隔分類器，$\lambda$ 選擇足夠小的值就能得到線性可分類輸入數據的硬間隔分類器。下面會詳細介紹將(2)簡化為二次規劃問題的經典方法。之後會討論一些最近才出現的方法，如次梯度下降法和坐標下降法。

### 原型

最小化(2)可以用下面的方式改寫為目標函數可微的約束優化問題。

對所有 $i \in \{1,\,\ldots,\,n\}$ 我們引入變量 $\zeta_i = \max\left(0, 1 - y_i(w\cdot x_i + b)\right)$。注意到 $\zeta_i$ 是滿足 $y_i(w\cdot x_i + b) \geq 1- \zeta_i$ 的最小非負數。

因此，我們可以將優化問題敘述如下$\text{minimize } \frac 1 n \sum_{i=1}^n \zeta_i + \lambda\|w\|^2$ $\text{subject to } y_i(x_i \cdot w + b) \geq 1 - \zeta_i \,\text{ and }\,\zeta_i \geq 0,\,\text{for all }i.$ 這就叫做原型問題。

### 對偶型

通過求解上述問題的對偶 (最優化)，得到簡化的問題$\text{maximize}\,\, f(c_1 \ldots c_n) = \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(x_i \cdot x_j)y_jc_j,$ $\text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.$這就叫做對偶問題。由於對偶最小化問題是受線性約束的 $c_i$ 的二次函數，所以它可以通過二次規劃演算法高效地解出。

這裡，變量 $c_i$ 定義為滿足$\vec w = \sum_{i=1}^n c_iy_i \vec x_i$. 此外，當 $\vec x_i$ 恰好在間隔的正確一側時 $c_i = 0$，且當 $\vec x_i$ 位於間隔的邊界時 $0 < c_i <(2n\lambda)^{-1}$。因此，$\vec w$ 可以寫為支持向量的線性組合。

可以通過在間隔的邊界上找到一個 $\vec x_i$ 並求解$y_i(\vec w \cdot \vec x_i + b) = 1 \iff b = y_i - \vec w \cdot \vec x_i.$ 得到偏移量 $b$。（注意由於 $y_i=\pm 1$ 因而 $y_i^{-1}=y_i$。）

### 核技巧

假設我們要學習與變換後數據點 $\varphi(\vec x_i)$ 的線性分類規則對應的非線性分類規則。此外，我們有一個滿足 $k(\vec x_i, \vec x_j) = \varphi(\vec x_i) \cdot \varphi(\vec x_j)$ 的核函數 $k$。

我們知道變換空間中的分類向量 $\vec w$ 滿足$\vec w = \sum_{i=1}^n c_iy_i\varphi( \vec x_i),$其中 $c_i$ 可以通過求解優化問題$\begin{align} \text{maximize}\,\, f(c_1 \ldots c_n) &= \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(\varphi(\vec x_i) \cdot \varphi(\vec x_j))y_jc_j \\ <pre> &= \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_ik(\vec x_i,\vec x_j)y_jc_j \\ </pre> \end{align}$ $\text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.$得到。與前面一樣，可以使用二次規劃來求解係數 $c_i$。同樣，我們可以找到讓 $0 < c_i <(2n\lambda)^{-1}$ 的索引 $i$，使得 $\varphi(\vec x_i)$ 位於變換空間中間隔的邊界上，然後求解$\begin{align} b = \vec w \cdot \varphi(\vec x_i) - y_i &= \left[\sum_{k=1}^n c_ky_k\varphi(\vec x_k)\cdot\varphi(\vec x_i)\right] - y_i \\ <pre> &= \left[\sum_{k=1}^n c_ky_kk(\vec x_k, \vec x_i)\right] - y_i. </pre> \end{align}$最後，可以通過計算下式來分類新點 $\vec z \mapsto \sgn(\vec w \cdot \varphi(\vec z) + b) = \sgn\left(\left[\sum_{i=1}^n c_iy_ik(\vec x_i, \vec z)\right] + b\right).$

### 現代方法

用於找到SVM分類器的最近的演算法包括次梯度下降和坐標下降。當處理大的稀疏數據集時，這兩種技術已經被證明有著顯著的優點——當存在許多訓練實例時次梯度法是特別有效的，並且當特徵空間的維度高時，坐標下降特別有效。

#### 次梯度下降

SVM的次梯度下降演算法直接用表達式$f(\vec w, b) = \left[\frac 1 n \sum_{i=1}^n \max\left(0, 1 - y_i(w\cdot x_i + b)\right) \right] + \lambda\lVert w \rVert^2.$注意 $f$ 是 $\vec w$ 與 $b$ 的凸函數。因此，可以採用傳統的梯度下降（或）方法，其中不是在函數梯度的方向上前進，而是在從函數的次梯度中選出的向量的方向上前進。該方法的優點在於，對於某些實現，迭代次數不隨著數據點的數量 $n$ 而增加或減少。

#### 坐標下降

SVM的坐標下降演算法基於對偶問題

$\text{maximize}\,\, f(c_1 \ldots c_n) = \sum_{i=1}^n c_i - \frac 1 2 \sum_{i=1}^n\sum_{j=1}^n y_ic_i(x_i \cdot x_j)y_jc_j,$ $\text{subject to } \sum_{i=1}^n c_iy_i = 0,\,\text{and } 0 \leq c_i \leq \frac{1}{2n\lambda}\;\text{for all }i.$對所有 $i \in \{1,\, \ldots,\, n\}$ 進行迭代，使係數 $c_i$ 的方向與 $\partial f/ \partial c_i$ 一致。然後，將所得的係數向量 $(c_1',\,\ldots,\,c_n')$ 投影到滿足給定約束的最接近的係數向量。（通常使用歐氏距離。）然後重複該過程，直到獲得接近最佳的係數向量。所得的演算法在實踐中運行非常快，儘管已經證明的性能保證很少。

## 性質

SVM屬於廣義線性分類器的一族，並且可以解釋為感知器的延伸。它們也可以被認為是吉洪諾夫正則化的特例。它們有一個特別的性質，就是可以同時最小化經驗誤差和最大化幾何邊緣區; 因此它們也被稱為最大間隔分類器。

Meyer、Leisch和Hornik對SVM與其他分類器進行了比較。

### 參數選擇

SVM的有效性取決於核函數、核參數和軟間隔參數 C 的選擇。

通常會選只有一個參數 $\gamma$ 的高斯核。C 和 $\gamma$ 的最佳組合通常通過在 C 和 $\gamma$ 為指數增長序列下網格搜索來選取，例如 $C \in \{ 2^{-5}, 2^{-3}, \dots, 2^{13},2^{15} \}$; $\gamma \in \{ 2^{-15},2^{-13}, \dots, 2^{1},2^{3} \}$。通常情況下，使用交叉驗證來檢查參數選擇的每一個組合，並選擇具有最佳交叉驗證精度的參數。或者，最近在貝葉斯優化中的工作可以用於選擇C和γ，通常需要評估比網格搜索少得多的參數組合。或者，貝葉斯優化的最近進展可以用於選擇 C 和 $\gamma$，通常需要計算的參數組合比網格搜索少得多。然後，使用所選擇的參數在整個訓練集上訓練用於測試和分類新數據的最終模型。

### 問題

SVM的潛在缺點包括以下方面：

- 需要對輸入數據進行完全標記
- 未校準類成員機率
- SVM僅直接適用於兩類任務。因此，必須應用將多類任務減少到幾個二元問題的演算法；請參閱多類SVM一節。
- 解出的模型的參數很難理解。

## 延伸

- 支持向量聚類：支持向量聚類是一種建立在核函數上的類似方法，同適用於非監督學習和數據挖掘。它被認為是數據科學中的一種基本方法。
- 轉導支持向量機
- 多元分類支持向量機：SVM演算法最初是為二值分類問題設計的，實現多分類的主要方法是將一個多分類問題轉化為多個二分類問題。常見方法包括「一對多法」和「一對一法」，一對多法是將某個類別的樣本歸為一類,其他剩餘的樣本歸為另一類，這樣k個類別的樣本就構造出了k個二分類SVM；一對一法則是在任意兩類樣本之間設計一個SVM。
- 支持向量回歸
- 結構化支持向量機：支持向量機可以被推廣為結構化的支持向量機，推廣後標籤空間是結構化的並且可能具有無限的大小。

## 實現

最大間隔超平面的參數是通過求解優化得到的。有幾種專門的演算法可用於快速解決由SVM產生的QP問題，它們主要依靠啟發式算法將問題分解成更小、更易於處理的子問題。

另一種方法是使用內點法，其使用類似牛頓法的迭代找到卡羅需－庫恩－塔克條件下原型和對偶型的解。

這種方法不是去解決一系列分解問題，而是直接完全解決該問題。為了避免求解核矩陣很大的線性系統，在核技巧中經常使用矩陣的低秩近似。

另一個常見的方法是普萊特的序列最小優化演算法（SMO），它把問題分成了若干個可以解析求解的二維子問題，這樣就可以避免使用數值優化演算法和矩陣存儲。

線性支持向量機的特殊情況可以通過用於優化其類似問題邏輯斯諦迴歸的同類演算法更高效求解；這類演算法包括次梯度下降法（如PEGASOS）和坐標下降法（如LIBLINEAR）。LIBLINEAR有一些引人注目的訓練時間上的特性。每次收斂迭代花費在讀取訓練數據上的時間是線性的，而且這些迭代還具有收斂速率特性，使得演算法非常快。

一般的核SVM也可以用次梯度下降法（P-packSVM）更快求解，在允許並行化時求解速度尤其快。

許多機器學習工具包都可以使用核SVM，有、MATLAB、SAS、SVMlight、kernlab、scikit-learn、Weka、Shark、JKernelMachines、OpenCV等。

## 外部連結

- www.support-vector.net The key book about the method, "An Introduction to Support Vector Machines" with online software
- Burges, Christopher J. C.; A Tutorial on Support Vector Machines for Pattern Recognition , Data Mining and Knowledge Discovery 2:121–167, 1998
- www.kernel-machines.org (general information and collection of research papers)
- www.support-vector-machines.org (Literature, Review, Software, Links related to Support Vector Machines — Academic Site)
- svmtutorial.online A simple introduction to SVM, easily accessible to anyone with basic background in mathematics
- videolectures.net (SVM-related video lectures)
- Karatzoglou, Alexandros et al.; Support Vector Machines in R , Journal of Statistical Software April 2006, Volume 15, Issue 9.
- libsvm , LIBSVM is a popular library of SVM learners
- liblinear is a library for large linear classification including some SVMs
- Shark is a C++ machine learning library implementing various types of SVMs
- dlib is a C++ library for working with kernel methods and SVMs
- SVM light is a collection of software tools for learning and classification using SVM
- SVMJS live demo is a GUI demo for JavaScript implementation of SVMs
- Gesture Recognition Toolkit contains an easy to use wrapper for libsvm