支援向量機

在機器學習中，支援向量機; zh-hk:支援向量機是在分類與迴歸分析中分析資料的監督式學習模型與相關的學習演算法。給定一組訓練例項，每個訓練例項被標記為屬於兩個類別中的一個或另一個，SVM訓練演算法建立一個將新的例項分配給兩個類別之一的模型，使其成為非機率線性分類器。SVM模型是將例項表示為空間中的點，這樣對映就使得單獨類別的例項被儘可能寬的明顯的間隔分開。然後，將新的例項對映到同一空間，並基於它們落在間隔的哪一側來預測所屬類別。除了進行線性分類之外，SVM還可以使用所謂的有效地進行非線性分類，將其輸入隱式對映到高維特徵空間中。當資料未被標記時，不能進行監督式學習，需要用非監督式學習，它會嘗試找出資料到簇的自然聚類，並將新資料對映到這些已形成的簇。將支援向量機改進的聚類演算法被稱為支援向量聚類，當資料未被標記或者僅一些資料被標記時，支援向量聚類經常在工業應用中用作分類步驟的預處理。動機.將資料進行分類是機器學習中的一項常見任務。假設某些給定的資料點各自屬於兩個類之一，而目標是確定新資料點將在哪個類中。對於支援向量機來說，資料點被視為 formula_1 維向量，而我們想知道是否可以用 formula_2 維超平面來分開這些點。這就是所謂的線性分類器。可能有許多超平面可以把資料分類。最佳超平面的一個合理選擇是以最大間隔把兩個類分開的超平面。因此，我們要選擇能夠讓到每邊最近的資料點的距離最大化的超平面。如果存在這樣的超平面，則稱為最大間隔超平面，而其定義的線性分類器被稱為最大，或者叫做最佳穩定性感知器。"定義.更正式地來說，支援向量機在高維或無限維空間中構造超平面或超平面集合，其可以用於分類、迴歸或其他任務。直觀來說，分類邊界距離最近的訓練資料點越遠越好，因為這樣可以縮小分類器的泛化誤差。儘管原始問題可能是在有限維空間中陳述的，但用於區分的集合在該空間中往往。為此，有人提出將原有限維空間對映到維數高得多的空間中，在該空間中進行分離可能會更容易。為了保持計算負荷合理，人們選擇適合該問題的 formula_3 來定義SVM方案使用的對映，以確保用原始空間中的變數可以很容易計算點積。 高維空間中的超平面定義為與該空間中的某向量的點積是常數的點的集合。定義超平面的向量可以選擇在資料集中出現的特徵向量 formula_4 的影象的引數 formula_5 的線性組合。透過選擇超平面，被對映到超平面上的特徵空間中的點集 formula_6 由以下關係定義：formula_7 注意，如果隨著 formula_8 逐漸遠離 formula_6，formula_3 變小，則求和中的每一項都是在衡量測試點 formula_6 與對應的資料基點 formula_4 的接近程度。這樣，上述核心的總和可以用於衡量每個測試點相對於待分離的集合中的資料點的相對接近度。歷史.原始SVM演算法是由蘇聯數學家弗拉基米爾·瓦普尼克和亞歷克塞·澤範蘭傑斯於1963年發明的。1992年，伯恩哈德·E·博瑟由科琳娜·科特斯和瓦普尼克於1993年提出，並於1995年發表。線性SVM.我們考慮以下形式的 formula_13 點測試集：formula_14其中 formula_15 是 1 或者 −1，表明點 formula_16 所屬的類。formula_17 中每個都是一個 formula_1 維實向量。我們要求將 formula_19 的點集 formula_20 與 formula_21 的點集分開的 “最大間隔超平面”，使得超平面與最近的點 formula_20 之間的距離最大化。任何超平面都可以寫作滿足下面方程的點集 formula_23formula_24其中 formula_25是該法向量。引數 formula_26 決定從原點沿法向量 formula_25 到超平面的偏移量。硬間隔.如果這些訓練資料是線性可分的，可以選擇分離兩類資料的兩個平行超平面，使得它們之間的距離儘可能大。在這兩個超平面範圍內的區域稱為“間隔”，最大間隔超平面是位於它們正中間的超平面。這些超平面可以由方程：formula_28或是formula_29來表示。通過幾何不難得到這兩個超平面之間的距離是 formula_30，因此要使兩平面間的距離最大，我們需要最小化 formula_31。同時為了使得樣本資料點都在超平面的間隔區以外，我們需要保證對於所有的 formula_32 滿足其中的一個條件：formula_33 若 formula_34或是formula_35 若 formula_36這些約束表明每個資料點都必須位於間隔的正確一側。這兩個式子可以寫作：formula_37可以用這個式子一起來得到最佳化問題：“在 formula_38 條件下，最小化 formula_31，對於 formula_40"這個問題的解 formula_41 與 formula_42 決定了我們的分類器 formula_43。此幾何描述的一個顯而易見卻重要的結果是，最大間隔超平面完全是由最靠近它的那些 formula_44 確定的。這些 formula_44 叫做支援向量。軟間隔.為了將SVM擴充套件到資料線性不可分的情況，我們引入鉸鏈損失函式，formula_46當約束條件 (1) 滿足時此函式為零。對於間隔的錯誤一側的資料，該函式的值與距間隔的距離成正比。然後我們希望最小化formula_48其中引數 formula_49 用來權衡增加間隔大小與確保 formula_20 位於間隔的正確一側之間的關係。因此，對於足夠小的 formula_49 值，如果輸入資料是可以線性分類的，則軟間隔SVM與硬間隔SVM將表現相同，但即使不可線性分類，仍能學習出可行的分類規則。非線性分類.弗拉基米爾·瓦普尼克在1963年提出的原始最大間隔超平面演算法構造了一個線性分類器。而1992年，伯恩哈德·E·博瑟應用於最大邊界超平面來建立非線性分類器的方法。 所得到的演算法形式上類似，除了把點積換成了非線性核函式。這就允許演算法在變換後的特徵空間中擬合最大間隔超平面。該變換可以是非線性的，而變換空間是高維的；雖然分類器是變換後的特徵空間中的超平面，但它在原始輸入空間中可以是非線性的。值得注意的是，更高維的特徵空間增加了支援向量機的泛化誤差，但給定足夠多的樣本，演算法仍能表現良好。常見的核函式包括：由等式 formula_60，核函式與變換 formula_61 有關。變換空間中也有 w 值，formula_62。與 w 的點積也要用核技巧來計算，即 formula_63。計算SVM分類器.計算SVM分類器等同於使下面表示式最小化formula_64如上所述，由於我們關注的是軟間隔分類器，formula_49 選擇足夠小的值就能得到線性可分類輸入資料的硬間隔分類器。下面會詳細介紹將(2)簡化為二次規劃問題的經典方法。之後會討論一些最近才出現的方法，如次梯度下降法和座標下降法。原型.最小化(2)可以用下面的方式改寫為目標函式可微的約束最佳化問題。對所有 formula_66 我們引入變數 formula_67。注意到 formula_68 是滿足 formula_69 的最小非負數。因此，我們可以將最佳化問題敘述如下formula_70formula_71 這就叫做"原型"問題。對偶型.透過求解上述問題的，得到簡化的問題formula_72formula_73這就叫做"對偶"問題。由於對偶最小化問題是受線性約束的 formula_74 的二次函式，所以它可以透過二次規劃演算法高效地解出。這裡，變數 formula_74 定義為滿足formula_76. 此外，當 formula_77 恰好在間隔的正確一側時 formula_78，且當 formula_77 位於間隔的邊界時 formula_80。因此，formula_81 可以寫為支援向量的線性組合。可以透過在間隔的邊界上找到一個 formula_77 並求解formula_83得到偏移量 formula_84。核技巧.假設我們要學習與變換後資料點 formula_87 的線性分類規則對應的非線性分類規則。此外，我們有一個滿足 formula_88 的核函式 formula_89。我們知道變換空間中的分類向量 formula_90 滿足formula_91其中 formula_92 可以透過求解最佳化問題formula_93formula_73得到。與前面一樣，可以使用二次規劃來求解係數 formula_74。同樣，我們可以找到讓 formula_80 的索引 formula_97，使得 formula_87 位於變換空間中間隔的邊界上，然後求解formula_99最後，可以透過計算下式來分類新點 formula_100現代方法.用於找到SVM分類器的最近的演算法包括次梯度下降和座標下降。當處理大的稀疏資料集時，這兩種技術已經被證明有著顯著的優點——當存在許多訓練例項時次梯度法是特別有效的，並且當特徵空間的維度高時，座標下降特別有效。次梯度下降.SVM的次梯度下降演算法直接用表示式formula_101注意 formula_102 是 formula_41 與 formula_42 的凸函式。因此，可以採用傳統的梯度下降方法，其中不是在函式梯度的方向上前進，而是在從函式的次梯度中選出的向量的方向上前進。該方法的優點在於，對於某些實現，迭代次數不隨著資料點的數量 formula_13 而增加或減少。座標下降.SVM的座標下降演算法基於對偶問題formula_72formula_73對所有 formula_108 進行迭代，使係數 formula_74 的方向與 formula_110 一致。然後，將所得的係數向量 formula_111 投影到滿足給定約束的最接近的係數向量。然後重複該過程，直到獲得接近最佳的係數向量。所得的演算法在實踐中執行非常快，儘管已經證明的效能保證很少。性質.SVM屬於廣義線性分類器的一族，並且可以解釋為感知器的延伸。它們也可以被認為是吉洪諾夫正則化的特例。它們有一個特別的性質，就是可以同時最小化經驗誤差和最大化幾何邊緣區; 因此它們也被稱為最大間隔分類器。Meyer、Leisch和Hornik對SVM與其他分類器進行了比較。引數選擇.SVM的有效性取決於核函式、核引數和軟間隔引數 "C" 的選擇。通常會選只有一個引數 "formula_112" 的高斯核。"C" 和 formula_112 的最佳組合通常透過在 "C" 和 "formula_112" 為指數增長序列下來選取，例如 formula_115; formula_116。通常情況下，使用交叉驗證來檢查引數選擇的每一個組合，並選擇具有最佳交叉驗證精度的引數。或者，最近在貝葉斯最佳化中的工作可以用於選擇C和γ，通常需要評估比網格搜尋少得多的引數組合。或者，的最近進展可以用於選擇 "C" 和 "formula_112"，通常需要計算的引數組合比網格搜尋少得多。然後，使用所選擇的引數在整個訓練集上訓練用於測試和分類新資料的最終模型。問題.SVM的潛在缺點包括以下方面：實現.最大間隔超平面的引數是透過求解最佳化得到的。有幾種專門的演算法可用於快速解決由SVM產生的QP問題，它們主要依靠啟發式演算法將問題分解成更小、更易於處理的子問題。另一種方法是使用，其使用類似牛頓法的迭代找到卡羅需－庫恩－塔克條件下原型和對偶型的解。這種方法不是去解決一系列分解問題，而是直接完全解決該問題。為了避免求解核矩陣很大的線性系統，在核技巧中經常使用矩陣的低秩近似。另一個常見的方法是普萊特的序列最小最佳化演算法，它把問題分成了若干個可以解析求解的二維子問題，這樣就可以避免使用數值最佳化演算法和矩陣儲存。線性支援向量機的特殊情況可以透過用於最佳化其類似問題邏輯斯諦迴歸的同類演算法更高效求解；這類演算法包括次梯度下降法。LIBLINEAR有一些引人注目的訓練時間上的特性。每次收斂迭代花費在讀取訓練資料上的時間是線性的，而且這些迭代還具有特性，使得演算法非常快。一般的核SVM也可以用次梯度下降法更快求解，在允許並行化時求解速度尤其快。許多機器學習工具包都可以使用核SVM，有、MATLAB、SAS、SVMlight、kernlab、scikit-learn、、Weka、Shark、JKernelMachines、OpenCV等。