支持向量機(jī)基本模型
支持向量機(jī)的基本思想是，在如下的樣本集中：
基于訓(xùn)練集D在樣本空間中找到一個(gè)劃分超平面，將不同類別的樣本分開
劃分超平面可以表示成如下的線性方程：
其中w為法向量，b為位移項(xiàng)瞭郑，空間內(nèi)任意一點(diǎn)到以上超平面的距離為：
則有
距離超平面最近的幾個(gè)訓(xùn)練樣本點(diǎn)使得上式的等號(hào)成立勿锅，它們被稱為支持向量（support vector），兩個(gè)異類支持向量到超平面的距離之和為：
稱之為間隔（margin）
支持向量機(jī)的目的即找到最大間隔（maximum margin）的劃分超平面切厘，即解如下的不等式約束的凸優(yōu)化問題：
等價(jià)于：
上述模型即支持向量機(jī)（Support Vector Machine，SVM）的基本模型
SMO算法
對(duì)偶問題求解
支持向量機(jī)的基本模型是一個(gè)凸二次規(guī)劃（convex quadratic programming）問題懊缺，可以使用拉格朗日乘子得到其對(duì)偶問題（dual problem）從而求解
對(duì)于式子：
對(duì)每一條約束增加拉格朗日乘子疫稿，得到該問題的拉格朗日函數(shù)：
從而得到對(duì)偶問題為：
上述過程的KKT（Karush-Kuhn-Tucker）方程為：
可以求解支持向量機(jī)的模型
支持向量機(jī)有一個(gè)重要性質(zhì)：訓(xùn)練完成后，大部分的訓(xùn)練樣本都不需保留鹃两，最終模型僅與支持向量有關(guān)
SMO算法
為了求解該對(duì)偶問題遗座，SMO（Sequential Minimal Optimization）算法是一個(gè)很高效的算法，其基本思路是俊扳，先固定 ai 之外的所有參數(shù)途蒋，然后求 ai 上的極值。由于存在約束 Σaiyi=0 馋记，若固定 ai 之外的其他變量号坡，則 ai 可由其他變量導(dǎo)出。于是梯醒，SMO每次選擇兩個(gè)變量 ai 和 aj 宽堆，并固定其他參數(shù)。在參數(shù)初始化后冤馏，SMO不斷執(zhí)行如下兩個(gè)步驟直至收斂：
- 選取一對(duì)需更新的變量 ai 和 aj
- 固定 ai 和 aj 以外的參數(shù)日麸，求解對(duì)偶問題獲得更新后的 ai 和 aj
支持向量機(jī)的超平面中的偏移量 b 的求算方式為：
軟間隔與正則化
軟間隔支持向量機(jī)
并不是每一組訓(xùn)練集在特種空間內(nèi)都是線性可分的，為了緩解該問題逮光，在有些時(shí)候可以允許支持向量機(jī)在一些樣本上出錯(cuò)代箭，使用軟間隔（soft margin）的方式：
軟間隔指允許某些樣本不滿足如下的約束條件：
但在最大化間隔的同時(shí)也使得不滿足約束的樣本應(yīng)該盡可能的少，于是優(yōu)化目標(biāo)可以寫為：
其中涕刚，C>0嗡综，為常數(shù)，C為無窮大時(shí)杜漠，上式要求所有樣本均滿足約束條件极景，C取有限值時(shí)察净，上式允許一些樣本不滿足約束條件。
l0/1是“0/1損失函數(shù)”：
一些替代損失（surrogate loss）如下：
圖像如下：
引入松弛變量（slack variables）可以改寫式子成為：
解以上的二次規(guī)劃問題盼樟，依然使用對(duì)偶函數(shù)法氢卡，得到其拉格朗日函數(shù)為：
對(duì)偶問題為：
KKT方程為：
優(yōu)化目標(biāo)的一般形式
優(yōu)化目標(biāo)的一般形式為：第一項(xiàng)用來描述劃分超平面的間隔大小，另一項(xiàng)用來表述訓(xùn)練集上的誤差：
- 第一項(xiàng)稱為結(jié)構(gòu)風(fēng)險(xiǎn)（structural risk）晨缴，用于描述模型的某些性質(zhì)
- 第二項(xiàng)稱為經(jīng)驗(yàn)風(fēng)險(xiǎn)（empirical risk）译秦，用于描述模型與訓(xùn)練數(shù)據(jù)的契合程度
- C用于對(duì)二者進(jìn)行折中
支持向量回歸
考慮回歸問題，給定樣本
希望得到一個(gè)回歸模型：
使得y和f(x)盡可能接近击碗，w和b是待定參數(shù)
支持向量回歸（Support Vector Rrgression筑悴，SVR）假設(shè)能容忍f(x)和y之間有一個(gè)偏差，當(dāng)f(x)和y之間的差別大于該偏差的時(shí)候才計(jì)算損失稍途，相當(dāng)于以f(x)為中心構(gòu)建了一個(gè)寬度為兩倍偏差的間隔帶阁吝，若訓(xùn)練樣本落入此間隔帶則認(rèn)為模型預(yù)測(cè)正確
SVR問題可以表示為：
其中的l為不敏感損失函數(shù)（insensitive loss function）
引入松弛變量后可以重寫為：
依然可以使用對(duì)偶問題求解
全文參考：周志華 著 《機(jī)器學(xué)習(xí)》
轉(zhuǎn)載請(qǐng)注明出處，本文永久更新鏈接：小天才的雜貨鋪-個(gè)人博客
