線性可分支持向量機
特點
- 二分類問題
- 輸入空間：歐式空間或離散集合
- 特征空間：歐式空間或希爾伯特空間
- 線性可分支持向量機、線性支持向量機：假設(shè)這兩個空間的元素一一對應(yīng)，并將輸入空間中的輸入映射為特征空間中的特征向量
理論模型
-
假設(shè)特征空間上的訓(xùn)練數(shù)據(jù)集：
假設(shè) -
線性可分支持向量機：給定線性可分訓(xùn)練數(shù)據(jù)集，通過間隔最大化或等價地求解相應(yīng)的凸二次規(guī)劃問題學習得到的分離超平面為
超平面 -
決策函數(shù)
決策函數(shù)
函數(shù)間隔和幾何間隔
-
點到分離超平面的遠近表示分類預(yù)測的確信程度，確信程度的符號與類標記y的符號是否一致表示分類是否正確，所以符號
表示分類的正確性正確性 -
函數(shù)間隔
樣本點的函數(shù)間隔
函數(shù)間隔
訓(xùn)練數(shù)據(jù)集的函數(shù)間隔
函數(shù)間隔 -
幾何間隔
樣本點的幾何間隔
幾何間隔
訓(xùn)練數(shù)據(jù)集的幾何間隔
幾何間隔
間隔最大化
-
最大間隔分類超平面
最大間隔 -
根據(jù)幾何間隔和函數(shù)間隔的關(guān)系,問題轉(zhuǎn)化為
間隔 -
因為函數(shù)間隔并不影響問題的最優(yōu)解，所以我們令函數(shù)間隔為1.線性可分支持向量機學習可以轉(zhuǎn)化為以下最優(yōu)化問題
最優(yōu)化問題
拉格朗日對偶
給每一個約束條件加上一個拉格朗日乘子，定義拉格朗日函數(shù)
這里我們把X看做常量，對
在滿足約束的條件下，目標函數(shù)變?yōu)榱?/p>
轉(zhuǎn)化為對偶問題
*** 通過拉格朗日對偶重新定義一個無約束問題，這個無約束問題等價于原來的約束優(yōu)化問題，從而將約束問題無約束化！ ***
求解對偶問題的步驟
- 首先固定，要讓 L 關(guān)于 w 和 b 最小化，我們分別對w，b求偏導(dǎo)數(shù)，即令 ?L/?w 和 ?L/?b 等于零
最后，得到：
-
計算
-
求得分離超平面
-
分類決策函數(shù)
*** 分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入的內(nèi)積，上式稱為線性可分支持向量機的對偶形式 ***
線性支持向量機與軟間隔最大化
引入松弛變量和懲罰參數(shù)
-
構(gòu)造并求解約束最優(yōu)化問題
-
計算
并選擇α*，適合條件
計算：
非線性支持向量機與核函數(shù)
核技巧應(yīng)用到支持向量機，其基本想法：
通過一個非線性變換將輸入空間(歐氏空間R”或離散集合)對應(yīng)于一個特征空間(希爾伯特空間)，使得在輸入空間中的超曲面模型對應(yīng)于特征空間中的超平面模型(支持向量機)。分類問題的學習任務(wù)通過在特征空間中求解線性支持向量機就可以完成.
多項式核函數(shù)
高斯核
如果σ選得很大的話，高次特征上的權(quán)重實際上衰減得非?？?，所以實際上（數(shù)值上近似一下）相當于一個低維的子空間；反過來，如果選得很小，則可以將任意的數(shù)據(jù)映射為線性可分——當然，這并不一定是好事，因為隨之而來的可能是非常嚴重的過擬合問題。不過，總的來說，通過調(diào)控參數(shù)σ，高斯核實際上具有相當高的靈活性，也是使用最廣泛的核函數(shù)之一
序列最小最優(yōu)化算法SMO
-
解如下凸二次規(guī)劃的對偶問題
-
啟發(fā)式算法，基本思路
如果所有變量的解都滿足此最優(yōu)化問題的KKT條件，那么得到解
否則，選擇兩個變量，固定其它變量，針對這兩個變量構(gòu)建一個二次規(guī)劃問題，稱為子問題，可通過解析方法求解，提高了計算速度
子問題的兩個變量：一個是違反KKT條件最嚴重的那個，另一個由約束條件自動確定
-
兩個變量二次規(guī)劃的求解過程
選擇兩個變量，其它固定
假設(shè)問題的初始可行解為
最優(yōu)解
設(shè)α2未經(jīng)剪輯時的最優(yōu)解為
則有
最優(yōu)化問題沿約束方向未經(jīng)剪輯的解
剪輯后的解
得到α1的解
