學習筆記 支援向量機

2022-11-24 18:02:54 字數 3167 閱讀 9397

支援向量機(svm),基本模型是定義在特徵空間上的間隔最大的線性分類器,使用核技巧可以使它成為實質上的非線性分類器。“使間隔最大”形成一個凸二次規劃問題。由簡至繁可分為:線性可分(硬間隔)支援向量機,(軟間隔)線性支援向量機,非線性支援向量機。

資料線性可分的時候,感知機可以求得分離超平面,但有無數多個解,而支援向量機通過間隔最大化求得的最優分離超平面,解是唯一的。

超平面\((w, b)\)關於樣本點\((x_i, y_i)\)的幾何間隔:$$\gamma = y_i (\frac \cdot x_i + \frac ),$$求最大間隔分離超平面可以表示成下面的約束最優化問題:

\[\max_ \: \gamma$$$$s.t. \: y_i (\frac \cdot x_i + \frac ) \geq \gamma

\]進行簡單的推導,得到下面的線性可分支援向量機學習演算法——最大間隔法,

線性可分支援向量機學習演算法——最大間隔法

構造並求解約束最優化問題:$$\min_ : \frac||w||^2$$$$s.t. : y_i (w \cdot x_i + b) - 1 \geq 0, i = 1, 2, ..., n$$

由此得到分離超平面:$$w^* \cdot x + b^* = 0$$分類決策函式$$f(x) = sign(w^* \cdot x + b^*)$$

距離分離超平面最近的例項稱為支援向量,在決定分離超平面時只有支援向量起作用,其他例項點不起作用。

可以應用拉格朗日對偶性,通過求解對偶問題得到原始問題的解,簡單來說,就是把最優化問題中的約束條件作為目標函式的一部分,形成新的最優化問題,這個新的最優化問題如果想要和原問題一致的話,需要滿足kkt條件。經過推導,可以得到線性可分支援向量機原始問題的對偶問題,相應的對偶學習演算法為,

構造並求解約束最優化問題$$\min_ :: \frac \sum_\sum_ \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_^\alpha_i$$$$s,t.:: \sum_^ \alpha_i y_i = 0$$ $$\alpha_i \geq 0, i = 1, 2, ..., n $$求得最優解$$ \alpha^* = ( \alpha_1^, \alpha_2^,..., \alpha_n*)t$$

計算 $$w^* = \sum_^ \alpha_i^* y_i x_i$$並選擇\(\alpha\)的一個正分量,計算$$b^* = y_j - \sum_^n \alpha_i^*y_i(x_i \cdot x_j)$$

求得分離超平面:$$w^* \cdot x + b^* = 0$$分類決策函式$$f(x) = sign(w^* \cdot x + b^*)$$

資料集中對應於\(\alpha_i > 0\)的例項為支援向量,在間隔邊界上。

對於線性不可分的資料,可以引入一個鬆弛變數\(\xi_i \geq 0\),對約束條件放寬一點,同時在目標函式中給予相應的懲罰,這樣,就得到了線性不可分的線性支援向量機的原始問題:

\[\min_ \: \: \frac ||w||^2 + c\sum_^n \xi_i$$$$s.t. \: \: y_i(w \cdot + b) \geq 1 - \xi_i, i=1,2, ..., n$$$$\xi_i \geq 0, i = 1,2,...,n

\]

與線性可分支援向量機一樣,可以得到線性支援向量機相應的對偶問題,

選擇懲罰引數\(c > 0\),構造並求解凸二次規劃問題$$\min_ :: \frac \sum_\sum_ \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_^\alpha_i$$$$s,t.:: \sum_^ \alpha_i y_i = 0$$ $$0 \leq \alpha_i \leq c, i = 1, 2, ..., n $$求得最優解$$ \alpha^* = ( \alpha_1^, \alpha_2^,..., \alpha_n*)t$$

計算 $$w^* = \sum_^ \alpha_i^* y_i x_i$$並選擇\(\alpha\)的一個大於0小於\(c\)的分量,計算$$b^* = y_j - \sum_^n \alpha_i^*y_i(x_i \cdot x_j)$$

求得分離超平面:$$w^* \cdot x + b^* = 0$$分類決策函式$$f(x) = sign(w^* \cdot x + b^*)$$

這時的線性支援向量機原始最優化問題等價於合頁損失函式最小化問題$$\min_ :: \sum_^n [1 - y_i(w \cdot x_i + b)]_+ + \lambda ||w||^2$$,合頁損失函式長得像合頁,是0-1損失函式的上界。

在處理非線性問題的時候,可以把原空間對映到新的空間,這是的資料可能就線性可分了,這是就能在新空間中學習分類模型。

核技巧的想法是,在學習與**中只定義核函式\(k(x,z)\),而不顯式地定義對映函式\(\phi\),用一些合適的\(k(x,z)\),計算起來容易。在支援向量機的對偶問題中,目標函式與決策函式都只涉及例項與例項之間的內積,可以用核函式\(k(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)\)來代替。

選擇適當的核函式\(k(x, z)\)和適當的引數\(c\),構造並求解最優化問題$$\min_ :: \frac \sum_\sum_ \alpha_i \alpha_j y_i y_j k(x_i, x_j) - \sum_^\alpha_i$$$$s,t.:: \sum_^ \alpha_i y_i = 0$$ $$0 \leq \alpha_i \leq c, i = 1, 2, ..., n $$求得最優解$$ \alpha^* = ( \alpha_1^, \alpha_2^,..., \alpha_n*)t$$

選擇\(\alpha\)的一個大於0小於\(c\)的分量,計算$$b^* = y_j - \sum_^n \alpha_i^*y_ik(x_i \cdot x_j)$$

構造決策函式:$$f(x) = sign(\sum_^n \alpha_i^* y_i k(x \cdot x_i) + b^*)$$

(注:本文為讀書筆記與總結,側重演算法原理,**為[《統計學習方法》](一書第七章)

出處:[