SVM支持向量機

從 集智百科
跳到: 導覽搜尋


該詞條由 烏丟丟 翻譯編輯,由 HengFlynn 審校,張江總審校,翻譯自Wikipedia詞條Support_vector_machine


機器學習中,支持向量機(support vector machine,常簡稱為SVM,又名支持向量網絡[1])指的是一種有監督式學習模型及其相關的學習算法,廣泛用於分類回歸分析。當給定一組訓練實例,並標記這些訓練實例屬於兩個類別的其中之一,SVM訓練算法基於這些實例創建一個模型將新的實例歸類為兩個類別中的一個,使其成為非概率二元線性分類器(儘管SVM中有些方法如概率輸出會在概率分類集合中使用)。SVM模型將實例表示為空間中的點,使得不同類別的實例被儘可能明顯的間隔所分開。然後,新的實例將被映射到同一空間中,並基於它們落在間隔的哪一側來預測其所屬類別。


除了進行線性分類之外,SVM還可以使用所謂的核技巧實現有效地非線性分類,將其輸入實例映射到高維特徵空間中。對於未標記數據,無法進行有監督式學習,但是可以使用非監督式學習進行訓練。非監督式學習會嘗試找出數據到簇的自然聚類,並將新數據映射到這些已形成的簇中。Hava Siegelmann 和 Vladimir Vapnik創造了支持向量聚類[2]算法,該算法利用支持向量機算法生成的支持向量統計數據對未標記的數據分類。這一算法也成為了工業應用最廣泛的聚類算法之一。

目錄

動機

數據分類是機器學習中的一項常見任務。 假設給定的一些數據點各自屬於兩個類其中之一,而數據分類的目標是利用這些數據確定新給定的數據點將在哪個類中。對於支持向量機來說,數據點被視為p維向量,而我們想知道是否可以用p-1超平面來分開這些點。這就是所謂的線性分類器。可能存在許多超平面可以把數據分類,而最佳超平面的一個合理選擇標準是找出把兩個類以最大間隔分開的超平面

H_1 不能把類別分開。H_{2} 可以,但只有很小的間隔。H_3 以最大間隔將它們分開。

所以,我們要選擇的超平面是實現距離超平面最近點之間距離間隔最大的。如果存在這樣的超平面,則可將其稱為最大間隔超平面,而基於其定義的線性分類器被稱為最大間隔分類器,或叫做最佳穩定性感知器

定義

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

核機器

儘管原始問題可能是在有限維空間中陳述的,但用於區分的集合在該空間中往往不是線性可分的。為此,有人提出將原始的限維空間映射到維數高得多的空間中,在這種空間中進行分離可能會更容易。為了保證計算負荷合理,人們選擇適合該問題的核函數 k(x,y) 來定義SVM方案使用的映射[5],以確保用原始空間中的變量可以很容易計算點積。高維空間中的超平面指的是與該空間中的某向量的點積是常數的點的集合。定義超平面的向量可以被選擇成為在數據集合中出現的特徵向量x_i的圖像的參數 \alpha _i的線性組合。通過選擇超平面,被映射到超平面上的特徵空間中的點集 x 由以下關係定義:\sum_i\alpha _ik(x_i,x)=constant. 需要注意的是,如果隨着y 逐漸遠離 x{k}(x,y) 變小,則求和中的每一項都是在衡量測試點 x與對應的數據集中點 x_i的接近程度。在這種情況下,上述內核的總和可以用于衡量每個測試點相對於待分離的集合中的數據點的相對接近度。也要注意到,點x的集合映射到任何超平面的結果可以特別複雜,同時也允許複雜得多的在原始空間里為非凸集合間的分離。

應用

SVM可以用於解決多種真實世界的問題:

  • 用於文本和超文本的分類,在歸納和轉導方法中都可以顯著減少所需要的有類標的樣本數。
  • 用於圖像分類。實驗結果顯示:相比於傳統的查詢優化方案,在經過三到四輪相關反饋之後,支持向量機能夠獲取明顯更高的搜索準確度。這同樣也適用於圖像分區系統,比如使用Vapnik所建議用特權方法的修改版本SVM的那些圖像分區系統。[6][7]
  • 用於手寫字體識別[8]
  • SVM算法已被廣泛應用於生物和其他科學。SVM用於分類蛋白質,可達到90%以上分類準確度。基於支持向量機權重的置換測試可作為一種機制,用於解釋的支持向量機模型。[9][10] 在早些時候,支持向量機權重也被用來解釋SVM模型。[11]在生命科學領域,利用支持向量機的Posthoc Posthoc interpretation進行特徵識別,並用於預測是一個相對較新的研究方向,而且有着特殊的意義。

歷史

最初的SVM算法是Vladimir N. VapnikAlexey Ya. Chervonenkis 於1963年發明。1992年,Bernhard E. Boser、Isabelle M. Guyon和Vladimir N. Vapnik提出了一種通過將核技巧應用於最大間隔超平面來創建非線性分類器的方法。[12]現行標準的前身(軟間隔)由Corinna Cortes和Vapnik於1993年提出,並於1995年發表。

線性SVM

按照以下形式給出  n 點測試集:

  (\overrightarrow{x_{1}},y_{1}),...,(\overrightarrow{x_{n}},y_{n})

其中 y_1 是 1 或者 −1,表明點 \overrightarrow{x_i} 所屬的類。 \overrightarrow{x_i}中每個都是一個 p 維實向量。我們希望找出可將 y_i=1的點集\overrightarrow{x_i}y_i=-1的點集分開的 「最大間隔超平面」,使得超平面與最近的點\overrightarrow{x_i} 之間的距離最大化。

任何超平面都可以表示為滿足下面方程的點集 \overrightarrow{x_i}

設樣本屬於兩個類,用該樣本訓練SVM得到的最大間隔超平面。在超平面上的樣本點也稱為支持向量。

\overrightarrow{\omega }\cdot \overrightarrow{x}-b=0

其中 \overrightarrow{\omega }(不必是歸一化的)是該超平面的法向量,其更像是海賽正規形式,但 \overrightarrow{\omega }不必是單位向量。參數 \frac{b}{\left \| \overrightarrow{\omega } \right \|}決定了從原點沿法向量\overrightarrow{\omega }到超平面的偏移量。

硬間隔

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

\overrightarrow{\omega }\cdot \overrightarrow{x}-b=1 (所有位於或者高於這條分界線的屬於一類,標籤為1)

或是

\overrightarrow{\omega }\cdot \overrightarrow{x}-b=-1(所有位於或者低於這條分界線的屬於一類,標籤為-1)

利用幾何方法不難得到這兩個超平面之間的距離是 \frac{2}{\left \| \overrightarrow{\omega } \right \|}[13],因此要使兩平面間的距離最大,我們需要實現\left \| \overrightarrow{\omega } \right \|最小化。同時,為了使得樣本數據點都在超平面的間隔區以外,我們需要保證對於所有的 i 滿足如下條件之一:

\overrightarrow{\omega }\cdot \overrightarrow{x}-b>or= 1 , 若y_i=1

或是:

\overrightarrow{\omega }\cdot \overrightarrow{x}-b\leq 1, 若y_i=-1

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

這兩個式子也可以寫成如下形式:

y_i(\overrightarrow{\omega }\cdot \overrightarrow{x}-b)\geq 1, 對所有1\leq i\leq n.\qquad\qquad(1)
我們可以結合這個方程式進行問題優化:
「在 y_i(\vec{w}\cdot\vec{x_i} - b) \ge 1 條件下,最小化 \|\vec{w}\|,對於 i = 1,...,n
這個問題的解 \vec wb 決定了我們的分類器 \overrightarrow{x} \mapsto sgn(\overrightarrow{\omega }\cdot \overrightarrow{x}-b).

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

軟間隔

為了將SVM擴展到數據線性不可分的情況,我們引入鉸鏈損失函數,

max(0,1-y_{i}(\overrightarrow{\omega }\cdot \overrightarrow{x_{i}}-b)).

注意y_i是第i個目標(例如,在本例中,1或者-1),\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b是當前輸出。

當約束條件 (1) 滿足時(也就是如果 \overrightarrow{x}_i 位於邊距的正確一側)此函數為零。對於位於間隔的錯誤一側的數據,該函數的值與該數據與間隔的距離成正比。

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

非線性分類

核機器

Vapnik在1963年提出的最原始的最大間隔超平面算法構造了一個線性分類器。而1992年,Bernhard E. Boser、Isabelle M. Guyon和Vladimir N. Vapnik提出了一種通過將核技巧(由Aizerman et al.[14]最先提出)應用於最大邊界超平面來創建非線性分類器的方法。[12] 除了把點積換成了非線性函數,所得到的算法形式上與前者類似。這種變化允許算法在變換後的特徵空間中擬合最大間隔超平面。這類變換可以是非線性的,但變換空間是高維的;儘管分類器是變換後的特徵空間中的超平面,但它在原始輸入空間中可以是非線性的。

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

常見的核函數包括:

核函數與經過方程式 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 \left \{ 1,...,n \right \} 我們引入變量  \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(\omega \cdot x_i-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(\overrightarrow{\omega }\cdot \overrightarrow{x_i}-b)=1\Leftrightarrow b=\overrightarrow{\omega }\cdot \overrightarrow{x_i}-y_i

得到偏移量  b。(注意由於 y_i=\pm 1 因而 y_{i}^{-1}=y_{i})。

核技巧

SVM訓練實例,核為:\Phi \left ( \left ( a,b \right ) \right )=(a,b,a^{2}+b^{2}).

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

我們知道變換空間中的分類向量  \vec w 滿足:
 \overrightarrow{\omega }=\sum_{i=1}^{n}c_iy_i\varphi (\overrightarrow{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 \\
                                      &=  \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 \\
\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 \\
  &= \left[\sum_{k=1}^n c_ky_kk(\vec x_k, \vec x_i)\right] - y_i.
\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 wb凸函數。因此,可以採用傳統的梯度下降(或SGD)方法,其不是在函數梯度的方向上前進,而是在從函數的次梯度中選出的向量的方向上前進。該方法的優點在於,對於某些實現,迭代次數不隨着數據點的數量 n 而增加或減少。[16]

坐標下降

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 \left \{ 1,...,n \right \} 進行迭代,使係數  c_i 的方向與  \partial f/ \partial c_i 一致。然後,將所得的係數向量  (c_1',\,\ldots,\,c_n') 投影到滿足給定約束的最接近的係數向量(通常使用歐氏距離)。然後重複該過程,直到獲得接近最佳的係數向量。儘管已證明的性能保證很少,其所得的算法在實踐中運行的非常快。[17]

經驗風險最小化

上文所描述的軟間隔支持向量機是經驗風險最小化(ERM)算法用於鉸鏈損失(hinge loss)的一個例子。從這方面看,支持向量機屬於推斷統計學算法的一個自然類,而它許多獨特的特點都緣於合頁損失的行為。這一觀點可以提供對於SVMs如何工作以及為何有效這一問題更深入的了解,並讓我們更好的分析他們的統計性質。

風險最小化

在監督學習中,給定一個訓練實例集合X_{1}...X_{n} 及對應標籤y_{1}...y_{n},我們希望利用給定的X_{n+1}預測y(n+1)。為實現這一預測我們給出假設f,例如f(X_{n+1})y(n+1)的一個「好」近似值。「好」近似值通常由損失函數\ell(y,z)定義,損失函數描述作為y的預測值z的不準確度。我們希望選擇一個最小化期望風險的假設:

\varepsilon (f)=\mathbb{E}\left [ \ell(y_{n+1},f(X_{n+1})) \right ].

在大多數情況下,我們不知道X_{n+1}y(n+1)的聯合分佈,因此,通常的策略是選擇一個最小化經驗風險的假設:

\hat{\varepsilon }(f)=\frac{1}{n}\sum_{k=1}^{n}\ell(y_{k},f(X_{k})).

在某些關於隨機變量X_{k}y_{k}序列(例如由有限馬爾可夫過程產生)的假設下,如果該假設集合足夠小,那麼隨着n的增大,經驗風險的最小化將近似接近期望風險的最小化。這一過程被叫做經驗風險最小化,簡稱ERM。

正則化和穩定性

為了最小化問題有一個良好定義的解決方法,我們必須對所考慮的假設集合\mathcal{H}給出約束條件。如果\mathcal{H}是一個賦范向量空間(例如SVM),一個有效的特殊辦法是僅考慮滿足\left \| f \right \|_{\mathcal H}<k這一條件的假設 f。這等同於添加一項「正則化懲罰」\mathcal R(f)=\lambda \left \| f \right \|_{\mathcal H},並解決這一新的優化問題。

\hat f = \mathrm{arg}\min_{f \in \mathcal{H}} \hat \varepsilon(f) + \mathcal{R}(f).

該方法被稱作吉洪諾夫正則化

一般來說,R(f)可以衡量假設f的複雜度,因此更傾向於更簡單的假設。

SVM與鉸鏈損失

利用(軟間隔)SVM分類器\overrightarrow{\omega} ,b:x\mapsto sgn(\overrightarrow{\omega }\cdot \overrightarrow{x}-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.

從上述討論我們可以看到,SVM技術等同於經驗風險最小化加上吉洪諾夫正則化,此時的損失函數是鉸鏈損失

\ell(y,z) = \max\left(0, 1 - yz \right).

在這一觀點下, SVM與其他基礎的分類算法聯繫緊密,如 正則化最小二乘法 and 邏輯回歸。這三者的不同在於損失函數的選擇:正則化最小二乘法統計經驗風險最小化使用平方損失函數\ell_{sq}(y,z) = (y-z)^2;邏輯回歸使用對數損失函數

\ell_{\log}(y,z) = \ln(1 + e^{-yz}).

目標函數

合頁損失與其他損失函數區別主要在於「目標函數」,而目標函數使一對給定的隨機變量X,y期望風險最小化。 特別的,在 X = x事件的條件下,讓y_x 表示 y。在這個分類集合里,我們有:

y_x = \begin{cases} 1 & \text{with probability } p_x \\ -1 & \text{with probability } 1-p_x  \end{cases}

那麼最理想分類器為:

f^*(x) = \begin{cases}1 & \text{if }p_x \geq 1/2 \\ -1 & \text{otherwise}\end{cases}

對於平方損失,目標函數就是條件期望函數,f_{sq}(x) =\mathbb{E}[y_{x}];而對於對數損失,目標函數是邏輯函數,f_{\log}(x) = \ln\left(p_x / ({1-p_x})\right)。當這兩個目標函數都是正確分類器,即 \sgn(f_{sq}) = \sgn(f_\log) = f^*,它們能給我們信息要比我們需要的更多。實際上,他們能給我們充足的信息來充分描繪 y_x的分佈。

在另一方面,合頁損失的目標函數正是f^*。因此,在充分假設空間,或適當選擇的核,SVM分類器會趨於可實現正確數據分類的最簡單函數( \mathcal{R})。這一方面拓展了SVM的幾何解釋:對於線性分類,間隔在支持向量和最簡單的最大間隔分類器之間的函數使得經驗風險最小化。[18]


性質

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

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

參數選擇

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和γ,通常只需要評估比網格搜索少得多的參數組合。然後,使用所選擇的參數在整個訓練集上訓練用於測試和分類新數據的最終模型。[20]

問題

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

  • 需要對輸入數據進行完全標記
  • 未校準類成員概率——起源於Vapnik理論的SVM避免了在有限數據中估計概率。
  • SVM僅直接適用於兩類任務。因此,必須應用將多類任務減少到幾個二元問題的算法;請參閱多類SVM一節。
  • 解出的模型的參數很難理解。

延伸

支持向量聚類

支持向量聚類是一種建立在核函數上的類似方法,同樣適用於無監督學習和數據挖掘。它被認為是數據科學中的一種基本方法。

多元分類SVM

多元分類SVM旨在應用支持向量機對實例賦上標籤,標籤是從一個含幾種元素的有限集合擬定的。

主要的方法是將單獨的多元分類問題降到多個二元分類問題。[21]通常有以下幾種方法:[21][22]

  • 構造二元分類器區分(i)其中一個標籤及剩餘標籤(一對多)或(ii)每一個對類(一對一)。一對多情況下對新實例進行分類由勝者全得策略完成,由最高輸出函數的分類器分類(輸出函數的分數必須標準化)。一對一情況下採用投票策略,每一分類器將實例賦給兩類中的一類,最終擁有最多票數的類決定實例分類。
  • 有向無環圖SVM (DAGSVM)[23]
  • 糾錯輸出編碼[24]

Crammer和Singer提議多元分類SVM將多類分類問題變成單個優化問題而不是分解為多個二元分類問題。[25]也可以參考Lee,Lin和Wahba的論文。[26] [27]

轉導支持向量機

轉導支持向量機拓展了SVMs,通過轉導法則,它們也可以在半監督學習中處理部分標註數據。除了訓練集 D,學習器也被賦予一個待分類的測試實例集合。

\mathcal{D}^\star = \{ \vec{x}^\star_i \mid \vec{x}^\star_i \in \mathbb{R}^p\}_{i=1}^k \,

轉導支持向量機由以下主要的優化問題定義:[28]

最小化 (在 {\vec{w}, b, \vec{y^\star}}中)

\frac{1}{2}\|\vec{w}\|^2

受約束於 (對任意 i = 1, \dots, n 和任意 j = 1, \dots, k)

y_i(\vec{w}\cdot\vec{x_i} - b) \ge 1,\,
y^\star_j(\vec{w}\cdot\vec{x^\star_j} - b) \ge 1,

以及

y^\star_{j} \in \{-1, 1\}.\,

轉導支持向量機由Vladimir N. Vapnik於1998年提出。

結構化支持向量機

支持向量機可以被拓展為結構化的支持向量機,推廣後標籤空間是結構化的並且可能具有無限的大小。

回歸

不同ε的支持向量回歸(預測)。隨着ε增大,預測對誤差的敏感度降低。

回歸 形式的支持向量機於1996年由Vladimir N. Vapnik, Harris Drucker, Christopher J. C. Burges, Linda Kaufman and Alexander J. Smola提出。[29]該方法稱為支持向量回歸(SVR)。支持向量分類的模型僅依靠訓練數據的子集,因為模型的損失函數不關心邊緣以外的訓練點。類似的,SVR模型僅依靠因為模型的損失函數不關心邊緣以外的訓練點,因為模型的損失函數忽視了接近模型預測的訓練數據。另一形式的SVM,即最小二乘支持向量機 已經由Suykens和Vandewalle提出。[30]

訓練原始SVR意味着求解[31]

minimize \frac{1}{2} \|w\|^2
subject to \begin{cases}
                    y_i - \langle w, x_i \rangle  - b \le \varepsilon  \\
                    \langle w, x_i \rangle + b - y_i \le \varepsilon
                  \end{cases}

其中x_i是目標值為y_i的訓練樣本。內積加上截距\langle w, x_i \rangle + b是樣本的預測值,\varepsilon是一個作為限制的自由參量:所有的預測值都應與真實預測值在\varepsilon的範圍內。通常加入鬆弛變量來使不可行情況下產生誤差和近似值。

貝葉斯SVM

2011年,Polson和Scott運用數據增強在SVM中加入貝葉斯解釋。[32]在這一方法中,SVM被視為 概率圖模型(參數由概率分佈聯繫)。這一延伸視角使得貝葉斯方法應用於SVMs,例如靈活特徵模型,自動超參數調優,以及預測不確定性量化。近期,一種可標度的貝葉斯SVM模型由Wenzel等提出來實現貝葉斯SVM在大數據上的應用。[33]

實現

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

另一種方法是使用內點法,其使用類似牛頓法的迭代找到卡羅需-庫恩-塔克條件下原型和對偶型的解。[34] 這種方法不是去解決一系列分解問題,而是直接完全解決該問題。為了避免求解核矩陣很大的線性系統,在核技巧中經常使用矩陣的低秩近似。

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

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

一般的核SVM也可以用次梯度下降法(P-packSVM[38])更快求解,在允許並行化時求解速度尤其快。

許多機器學習工具包都可以使用核SVM,有LIBSVMMATLABSAS、SVMlight、kernlabscikit-learnShogunWekaSharkJKernelMachinesOpenCV等。

簡單實現與演示

from sklearn.datasets.samples_generator import make_blobs
 
# revised from https://github.com/Madhu009/Deep-math-machine-learning.ai/blob/master/SVM-FromScratch.ipynb
# data preparation
 
(X,y) =  make_blobs(n_samples=50,n_features=2,centers=2,cluster_std=1.05,random_state=40)
#we need to add 1 to X values (we can say its bias)
X1 = np.c_[np.ones((X.shape[0])),X]
 
plt.scatter(X1[:,1],X1[:,2],marker='o',c=y)
plt.axis([-5,10,-12,-1])
plt.show()

未分類.png

postiveX=[]
negativeX=[]
for i,v in enumerate(y):
    if v==0:
        negativeX.append(X[i])
    else:
        postiveX.append(X[i])
 
#our data dictionary
data_dict = {-1:np.array(negativeX), 1:np.array(postiveX)}
 
#all the required variables 
w=[] #weights 2 dimensional vector
b=[] #bias
 
max_feature_value=float('-inf')
min_feature_value=float('+inf')
 
for yi in data_dict:
    if np.amax(data_dict[yi])>max_feature_value:
        max_feature_value=np.amax(data_dict[yi])
 
    if np.amin(data_dict[yi])<min_feature_value:
        min_feature_value=np.amin(data_dict[yi])
 
learning_rate = [max_feature_value * 0.1, max_feature_value * 0.01, max_feature_value * 0.001,]
 
def SVM_Training(data_dict):
    i=1
    global w
    global b
    # { ||w||: [w,b] }
    length_Wvector = {}
    transforms = [[1,1],[-1,1],[-1,-1],[1,-1]]
 
    b_step_size = 2
    b_multiple = 5
    w_optimum = max_feature_value*0.5
 
    for lrate in learning_rate:
 
 
        w = np.array([w_optimum,w_optimum])     
        optimized = False
        while not optimized:
            #b=[-maxvalue to maxvalue] we wanna maximize the b values so check for every b value
            for b in np.arange(-1*(max_feature_value*b_step_size), max_feature_value*b_step_size, lrate*b_multiple):
                for transformation in transforms:  # transforms = [[1,1],[-1,1],[-1,-1],[1,-1]]
                    w_t = w*transformation
 
                    correctly_classified = True
 
                    # every data point should be correct
                    for yi in data_dict:
                        for xi in data_dict[yi]:
                            if yi*(np.dot(w_t,xi)+b) < 1:  # we want  yi*(np.dot(w_t,xi)+b) >= 1 for correct classification
                                correctly_classified = False
 
                    if correctly_classified:
                        length_Wvector[np.linalg.norm(w_t)] = [w_t,b] #store w, b for minimum magnitude
 
            if w[0] < 0:
                optimized = True
            else:
                w = w - lrate
 
        norms = sorted([n for n in length_Wvector])
 
        minimum_wlength = length_Wvector[norms[0]]
        w = minimum_wlength[0]
        b = minimum_wlength[1]
 
        w_optimum = w[0]+lrate*2
 
SVM_Training(data_dict)
 
def visualize(data_dict):
 
 
        #[[ax.scatter(x[0],x[1],s=100,color=colors[i]) for x in data_dict[i]] for i in data_dict]
 
        plt.scatter(X1[:,1],X1[:,2],marker='o',c=y)
 
        # hyperplane = x.w+b
        # v = x.w+b
        # psv = 1
        # nsv = -1
        # dec = 0
        def hyperplane_value(x,w,b,v):
            return (-w[0]*x-b+v) / w[1]
 
        datarange = (min_feature_value*0.9,max_feature_value*1.)
        hyp_x_min = datarange[0]
        hyp_x_max = datarange[1]
 
        # (w.x+b) = 1
        # positive support vector hyperplane
        psv1 = hyperplane_value(hyp_x_min, w, b, 1)
        psv2 = hyperplane_value(hyp_x_max, w, b, 1)
        ax.plot([hyp_x_min,hyp_x_max],[psv1,psv2], 'k')
 
        # (w.x+b) = -1
        # negative support vector hyperplane
        nsv1 = hyperplane_value(hyp_x_min, w, b, -1)
        nsv2 = hyperplane_value(hyp_x_max, w, b, -1)
        ax.plot([hyp_x_min,hyp_x_max],[nsv1,nsv2], 'k')
 
        # (w.x+b) = 0
        # positive support vector hyperplane
        db1 = hyperplane_value(hyp_x_min, w, b, 0)
        db2 = hyperplane_value(hyp_x_max, w, b, 0)
        ax.plot([hyp_x_min,hyp_x_max],[db1,db2], 'y--')
 
        plt.axis([-5,10,-12,-1])
        plt.show()
 
visualize(data_dict)

分類.png

參見

  • 相關向量機,是一個函數形式與支持向量機相同的概率稀疏核模型。

參考

  1. Cortes, Corinna; Vapnik, Vladimir N. (1995). "Support-vector networks". Machine Learning. 20 (3): 273–297. doi:10.1007/BF00994018
  2. Ben-Hur, Asa; Horn, David; Siegelmann, Hava; and Vapnik, Vladimir N.; "Support vector clustering"; (2001); Journal of Machine Learning Research, 2: 125–137
  3. "Archived copy". Archived from the original on 2017-11-08. Retrieved 2017-11-08
  4. Trevor_Hastie,_Robert_Tibshirani,_Jerome_Friedman - The elements of Statistical Learning Pg. 134
  5. *Press, William H.; Teukolsky, Saul A.; Vetterling, William T.; Flannery, Brian P. (2007). "Section 16.5. Support Vector Machines". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8. Archived from the original on 2011-08-11.
  6. Vapnik, Vladimir N.: Invited Speaker. IPMU Information Processing and Management 2014)
  7. Barghout, Lauren. "Spatial-Taxon Information Granules as Used in Iterative Fuzzy-Decision-Making for Image Segmentation." Granular Computing and Decision-Making. Springer International Publishing, 2015. 285-318.
  8. DeCoste, Dennis (2002). "Training Invariant Support Vector Machines" (PDF). Machine Learning. 46: 161–190.
  9. Gaonkar, Bilwaj; Davatzikos, Christos; "Analytic estimation of statistical significance maps for support vector machine based multi-variate image analysis and classification"
  10. Cuingnet, Rémi; Rosso, Charlotte; Chupin, Marie; Lehéricy, Stéphane; Dormont, Didier; Benali, Habib; Samson, Yves; and Colliot, Olivier; "Spatial regularization of SVM for the detection of diffusion alterations associated with stroke outcome", Medical Image Analysis, 2011, 15 (5): 729–737
  11. Statnikov, Alexander; Hardin, Douglas; & Aliferis, Constantin; (2006); "Using SVM weight-based methods to identify causally relevant and non-causally relevant variables", Sign, 1, 4
  12. 12.0 12.1 Boser, Bernhard E.; Guyon, Isabelle M.; Vapnik, Vladimir N. (1992). "A training algorithm for optimal margin classifiers". Proceedings of the fifth annual workshop on Computational learning theory – COLT '92. p. 144. doi:10.1145/130385.130401. ISBN 089791497X.
  13. "Why does the SVM margin is $\frac{2}{\-\mathbf{w}\-}$".Mathematics Stack Exchange.
  14. Aizerman, Mark A.; Braverman, Emmanuel M.; Rozonoer, Lev I. (1964). "Theoretical foundations of the potential function method in pattern recognition learning". Automation and Remote Control 25: 821–837.
  15. Jin, Chi; Wang, Liwei (2012). Dimensionality dependent PAC-Bayes margin bound. Advances in Neural Information Processing Systems. Archived from the original on 2015-04-02.
  16. Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan; Cotter, Andrew (2010-10-16). "Pegasos: primal estimated sub-gradient solver for SVM". Mathematical Programming. 127 (1): 3–30. doi:10.1007/s10107-010-0420-4. ISSN 0025-5610.
  17. Hsieh, Cho-Jui; Chang, Kai-Wei; Lin, Chih-Jen; Keerthi, S. Sathiya; Sundararajan, S. (2008-01-01). "A Dual Coordinate Descent Method for Large-scale Linear SVM". Proceedings of the 25th International Conference on Machine Learning. ICML '08. New York, NY, USA: ACM: 408–415. doi:10.1145/1390156.1390208 .ISBN 978-1-60558-205-4.
  18. Rosasco, Lorenzo; De Vito, Ernesto; Caponnetto, Andrea; Piana, Michele; Verri, Alessandro (2004-05-01). "Are Loss Functions All the Same?". Neural Computation. 16 (5): 1063–1076. CiteSeerX 10.1.1.109.6786 Freely accessible. doi:10.1162/089976604773135104. ISSN 0899-7667. PMID 15070510.
  19. Meyer, David; Leisch, Friedrich; Hornik, Kurt (2003). "The support vector machine under test". Neurocomputing. 55: 169. doi:10.1016/S0925-2312(03)00431-4.
  20. Hsu, Chih-Wei; Chang, Chih-Chung & Lin, Chih-Jen (2003). A Practical Guide to Support Vector Classification (PDF) (Technical report). Department of Computer Science and Information Engineering, National Taiwan University. Archived (PDF) from the original on 2013-06-25.
  21. 21.0 21.1 Duan, Kai-Bo; Keerthi, S. Sathiya (2005). "Which Is the Best Multiclass SVM Method? An Empirical Study". Multiple Classifier Systems. LNCS. 3541. pp. 278–285. doi:10.1007/11494683_28. ISBN 978-3-540-26306-7.
  22. Hsu, Chih-Wei & Lin, Chih-Jen (2002). "A Comparison of Methods for Multiclass Support Vector Machines" (PDF). IEEE Transactions on Neural Networks.
  23. Platt, John; Cristianini, Nello; Shawe-Taylor, John (2000). "Large margin DAGs for multiclass classification". In Solla, Sara A.; Leen, Todd K.; and Müller, Klaus-Robert; eds. Advances in Neural Information Processing Systems (PDF). MIT Press. pp. 547–553. Archived (PDF) from the original on 2012-06-16.
  24. Dietterich, Thomas G.; Bakiri, Ghulum (1995). "Solving Multiclass Learning Problems via Error-Correcting Output Codes" (PDF). Journal of Artificial Intelligence Research. 2: 263–286. arXiv:cs/9501101 Bibcode:1995cs........1101D. Archived (PDF) from the original on 2013-05-09..
  25. Crammer, Koby & Singer, Yoram (2001). "On the Algorithmic Implementation of Multiclass Kernel-based Vector Machines" (PDF). Journal of Machine Learning Research. 2: 265–292. Archived (PDF) from the original on 2015-08-29.
  26. Lee, Yoonkyung; Lin, Yi & Wahba, Grace (2001). "Multicategory Support Vector Machines" (PDF). Computing Science and Statistics. 33. Archived (PDF) from the original on 2013-06-17.
  27. Lee, Yoonkyung; Lin, Yi; Wahba, Grace (2004). "Multicategory Support Vector Machines". Journal of the American Statistical Association. 99 (465): 67. doi:10.1198/016214504000000098.
  28. Joachims, Thorsten; "Transductive Inference for Text Classification using Support Vector Machines", Proceedings of the 1999 International Conference on Machine Learning (ICML 1999), pp. 200–209
  29. Drucker, Harris; Burges, Christopher J. C.; Kaufman, Linda; Smola, Alexander J.; and Vapnik, Vladimir N. (1997); "Support Vector Regression Machines", in Advances in Neural Information Processing Systems 9, NIPS 1996, 155–161, MIT Press.
  30. Suykens, Johan A. K.; Vandewalle, Joos P. L.; "Least squares support vector machine classifiers", Neural Processing Letters, vol. 9, no. 3, Jun. 1999, pp. 293–300
  31. Smola, Alex J.; Schölkopf, Bernhard (2004). "A tutorial on support vector regression". Statistics and Computing 14 (3): 199–222. Archived from the original on 2012-01-31. http://eprints.pascal-network.org/archive/00000856/01/fulltext.pdf.
  32. Polson, Nicholas G.; Scott, Steven L. (2011). "Data Augmentation for Support Vector Machines". Bayesian Analysis. 6 (1): 1–23. doi:10.1214/11-BA601.
  33. Wenzel, Florian; Galy-Fajou, Theo; Deutsch, Matthäus; Kloft, Marius (2017). "Bayesian Nonlinear Support Vector Machines for Big Data". Machine Learning and Knowledge Discovery in Databases (ECML PKDD). arXiv:1707.05532. Bibcode:2017arXiv170705532W.
  34. Ferris, Michael C.; Munson, Todd S. (2002). "Interior-Point Methods for Massive Support Vector Machines" (PDF). SIAM Journal on Optimization. 13 (3): 783. doi:10.1137/S1052623400374379. Archived (PDF) from the original on 2008-12-04.
  35. Platt, John C. (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines (PDF). NIPS. Archived (PDF) from the original on 2015-07-02.
  36. Shalev-Shwartz, Shai; Singer, Yoram; Srebro, Nathan (2007). Pegasos: Primal Estimated sub-GrAdient SOlver for SVM (PDF). ICML. Archived (PDF) from the original on 2013-12-15.
  37. Fan, Rong-En; Chang, Kai-Wei; Hsieh, Cho-Jui; Wang, Xiang-Rui; Lin, Chih-Jen (2008). "LIBLINEAR: A library for large linear classification" (PDF). Journal of Machine Learning Research. 9: 1871–1874.
  38. Allen Zhu, Zeyuan; Chen, Weizhu; Wang, Gang; Zhu, Chenguang; Chen, Zheng (2009). P-packSVM: Parallel Primal grAdient desCent Kernel SVM (PDF). ICDM. Archived (PDF) from the original on 2014-04-07.

文獻

外部鏈接

  • libsvm, LIBSVM is a popular library of SVM learners
  • liblinear is a library for large linear classification including some 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

本詞條內容翻譯自 wikipedia.org,遵守 CC3.0協議。

個人工具
名字空間
動作
導覽
工具箱