間隔與支持向量
支持向量機(jī)(Support Vector Machine)是最常用的機(jī)器學(xué)習(xí)算法之一.
首先我們從最簡單的SVM開始回顧. 假設(shè)一個特征空間中有若干二分類樣本, 且它們是線性可分的,那么在能夠?qū)⑵湔_分類的無數(shù)個超平面中,我們應(yīng)該挑選怎樣的超平面呢?
SVM給出的答案是: 找到在兩類樣本正中間的超平面. 很容易想出,此時該劃分的泛化能力比較強(qiáng).
我們用下式來表示劃分的超平面:
wTx+b=0
其中w為法向量,b為位移, 那么樣本空間中任一點(diǎn)x到該超平面的距離即為:
r=|wTx+b|||w||
假設(shè)超平面能夠分類正確,則可以(通過適當(dāng)放縮)使下式成立:
{wTxi+b≥+1yi=+1wTxi+b≤?1yi=?1
此時, 距離超平面最近的這幾個訓(xùn)練樣本剛好使上式的等號成立,它們就被稱作支持向量,兩個異類的支持向量到超平面的距離和為:
γ=2||w||
該項(xiàng)則被稱作間隔.
那么SVM的目標(biāo)即為找到擁有最大間隔的那個超平面, 最大化間隔即為最小化下式:
minw,b12||w||2s.t.yi(wTxi+b)≥1,i=1,2,...,m
那么SVM問題就轉(zhuǎn)為解決一個不等式限制下的優(yōu)化問題.
對偶問題
為了解決這個問題, 可以使用拉格朗日乘子法來構(gòu)造其對偶問題.
對于拉格朗日對偶性,可以參考李航老師<統(tǒng)計(jì)機(jī)器學(xué)習(xí)>附錄C部分. 需要注意的是,對偶函數(shù)的解給出了的是主問題的下界, 即對偶問題的最優(yōu)解并不等于主問題(原問題)的最優(yōu)解. 只有當(dāng) 主問題是凸優(yōu)化問題且可行域中至少有一點(diǎn)滿足約束時,兩個問題的最優(yōu)解一樣, 稱作 強(qiáng)對偶性.
幸運(yùn)的是SVM要解決的問題恰好滿足強(qiáng)對偶性,因此我們可以通過構(gòu)造并解決對偶問題來解SVM的主問題,且通過對偶問題,可以自然地引入后面的核技巧.
KKT條件
回顧上面的過程,這里該問題滿足KKT(Karush-Kuhn-Tucker)條件. 該條件是優(yōu)化問題中一個重要的限制條件, 其泛化的過程是這樣的:
對于無限制優(yōu)化問題, 只要求其駐點(diǎn)就行了.
對于等號限制優(yōu)化問題, 則需要加上拉格朗日乘子.
對于不等限制優(yōu)化問題, 則需要保證KKT條件了.
具體而言, 該條件是這樣的:
{αi≥0dual feasibility;yif(xi)?1≥0primal feasibility;αi(yif(xi)?1)=0complementary slackness.
第一個條件dual feasibility(對偶可行性), 正如其名, 是對偶問題的限制條件,也就是對拉格朗日乘子的限制.
第二個條件primal feasibility(主可行性), 則是我們最初主問題的限制條件.
第三個條件complementary slackness, 直接翻譯成中文可以叫互補(bǔ)松弛量. 對于這個條件的理解,首先明確對偶問題(max-min)的解是主問題(min-max)的下界. 那么這個變量大概就衡量了該界的準(zhǔn)確的, 當(dāng)slackness為零時,表示主問題和對偶問題的最優(yōu)解一致. 因此臺灣那邊也把這個slackness叫做”差余”, 大概是衡量兩個問題最優(yōu)解之間的差. 當(dāng)該條件得到滿足時,我們通常也叫保證了 強(qiáng)對偶.
