線性可分支持向量機(jī)

特點(diǎn)

1. 二分類問題
2. 輸入空間：歐式空間或離散集合
3. 特征空間：歐式空間或希爾伯特空間
4. 線性可分支持向量機(jī)创南、線性支持向量機(jī)：假設(shè)這兩個空間的元素一一對應(yīng)卿泽，并將輸入空間中的輸入映射為特征空間中的特征向量

理論模型

1. 假設(shè)特征空間上的訓(xùn)練數(shù)據(jù)集：

   
   
   假設(shè)

2. 線性可分支持向量機(jī)：給定線性可分訓(xùn)練數(shù)據(jù)集岭参，通過間隔最大化或等價地求解相應(yīng)的凸二次規(guī)劃問題學(xué)習(xí)得到的分離超平面為

   
   
   超平面

3. 決策函數(shù)

   
   
   決策函數(shù)

函數(shù)間隔和幾何間隔

1. 點(diǎn)到分離超平面的遠(yuǎn)近
   確信程度
   表示分類預(yù)測的確信程度尝艘，
   符號
   的符號與類標(biāo)記y的符號是否一致表示分類是否正確演侯，所以
   
   正確性
   表示分類的正確性

2. 函數(shù)間隔
   樣本點(diǎn)的函數(shù)間隔

   
   
   函數(shù)間隔
   
   

   訓(xùn)練數(shù)據(jù)集的函數(shù)間隔

   
   
   函數(shù)間隔

3. 幾何間隔
   樣本點(diǎn)的幾何間隔

   
   
   幾何間隔
   
   

   訓(xùn)練數(shù)據(jù)集的幾何間隔

   
   
   幾何間隔

間隔最大化

1. 最大間隔分類超平面

   
   
   最大間隔

2. 根據(jù)幾何間隔和函數(shù)間隔的關(guān)系,問題轉(zhuǎn)化為

   
   
   間隔

3. 因?yàn)楹瘮?shù)間隔并不影響問題的最優(yōu)解拷获，所以我們令函數(shù)間隔為1.線性可分支持向量機(jī)學(xué)習(xí)可以轉(zhuǎn)化為以下最優(yōu)化問題

   
   
   最優(yōu)化問題

拉格朗日對偶

舷嗡，定義拉格朗日函數(shù)

在滿足約束的條件下，目標(biāo)函數(shù)變?yōu)榱?/p>

*** 通過拉格朗日對偶重新定義一個無約束問題，這個無約束問題等價于原來的約束優(yōu)化問題援雇，從而將約束問題無約束化惫搏！ ***

求解對偶問題的步驟

1. 首先固定
   ，要讓 L 關(guān)于 w 和 b 最小化铣猩，我們分別對w茴丰，b求偏導(dǎo)數(shù)，即令 ?L/?w 和 ?L/?b 等于零
   
   
   
   
   最后失仁，得到：
   

2. 計(jì)算

   
   
   
   

3. 求得分離超平面

   
   

4. 分類決策函數(shù)

   
   

*** 分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入的內(nèi)積萄焦，上式稱為線性可分支持向量機(jī)的對偶形式 ***

線性支持向量機(jī)與軟間隔最大化

引入松弛變量和懲罰參數(shù)

1. 構(gòu)造并求解約束最優(yōu)化問題

   
   

2. 計(jì)算

   
   
   
   

   并選擇α*拂封，適合條件

   
   
   
   計(jì)算：
   

非線性支持向量機(jī)與核函數(shù)

核技巧應(yīng)用到支持向量機(jī)冒签，其基本想法：
通過一個非線性變換將輸入空間(歐氏空間R”或離散集合)對應(yīng)于一個特征空間(希爾伯特空間)钟病，使得在輸入空間中的超曲面模型對應(yīng)于特征空間中的超平面模型(支持向量機(jī))萧恕。分類問題的學(xué)習(xí)任務(wù)通過在特征空間中求解線性支持向量機(jī)就可以完成.

多項(xiàng)式核函數(shù)

高斯核

如果σ選得很大的話票唆，高次特征上的權(quán)重實(shí)際上衰減得非骋倥牵快噪伊，所以實(shí)際上（數(shù)值上近似一下）相當(dāng)于一個低維的子空間；反過來鉴吹，如果選得很小豆励，則可以將任意的數(shù)據(jù)映射為線性可分——當(dāng)然，這并不一定是好事般堆，因?yàn)殡S之而來的可能是非常嚴(yán)重的過擬合問題诚啃。不過，總的來說和橙，通過調(diào)控參數(shù)σ，高斯核實(shí)際上具有相當(dāng)高的靈活性晰搀，也是使用最廣泛的核函數(shù)之一

序列最小最優(yōu)化算法SMO

1. 解如下凸二次規(guī)劃的對偶問題

   
   

2. 啟發(fā)式算法外恕，基本思路
   如果所有變量的解都滿足此最優(yōu)化問題的KKT條件乡翅，那么得到解
   否則，選擇兩個變量尚洽，固定其它變量靶累，針對這兩個變量構(gòu)建一個二次規(guī)劃問題挣柬，稱為子問題，可通過解析方法求解澈灼，提高了計(jì)算速度
   子問題的兩個變量：一個是違反KKT條件最嚴(yán)重的那個店溢，另一個由約束條件自動確定

   
   

3. 兩個變量二次規(guī)劃的求解過程
   選擇兩個變量床牧，其它固定

   
   
   
   

   假設(shè)問題的初始可行解為

   
   
   
   最優(yōu)解
   
   
   設(shè)α2未經(jīng)剪輯時的最優(yōu)解為
   
   
   

   則有

   
   
   
   最優(yōu)化問題沿約束方向未經(jīng)剪輯的解
   
   
   剪輯后的解
   
   
   得到α1的解