支持向量機(jī)

一、什么是支持向量機(jī)

支持向量機(jī)(Suport Vector Machine,常簡(jiǎn)稱為SVM)倡勇,是一個(gè)監(jiān)督式學(xué)習(xí)的方式殖告。支持向量機(jī)屬于一般化線性分類器,這類分類器的特點(diǎn)是能夠同時(shí)最小化經(jīng)驗(yàn)誤差與最大化幾何邊緣區(qū)晴圾,因此支持向量機(jī)機(jī)也被稱為最大邊緣區(qū)分類器。

藍(lán)色和紅色的線圈出來的點(diǎn)就是所謂的支持向量噪奄,離分界線最近的點(diǎn)死姚,如果去掉這些點(diǎn),直線多半要改變位置勤篮。Classifier Boundary就是決策函數(shù)f(x)都毒,在兩個(gè)類的中間。紅色和藍(lán)色之間的間隙就是我們要的最大化分類的間隙碰缔。

二温鸽、關(guān)于拉格朗日乘子法和KKT條件

1.關(guān)于拉格朗日乘子法

有拉格朗日乘子法的地方,必然是一個(gè)組合優(yōu)化問題手负。比如
\begin{align} min \space f = 2x_1^2+3x_2^2+7x_3^2 \\ s.t. 2x_1 + x_2 = 1 \\ 2x_2+3x_3 = 2 \end{align}

這是一個(gè)帶等式約束的優(yōu)化問題,有目標(biāo)值姑尺,有約束條件竟终,不能直接求導(dǎo)∏畜可以使用拉格朗日方法统捶,把這個(gè)約束乘以一個(gè)系數(shù)加到目標(biāo)函數(shù)中去,這樣相當(dāng)與既考慮了原目標(biāo)函數(shù)柄粹,也考慮了約束條件喘鸟。然后分別對(duì)x求導(dǎo)等于0,
\begin{align} \frac{\partial{f}}{\partial{x_2}} = 4x_1+2\alpha_1 = 0 \implies x_1 = -0.5\alpha_1 \\ \frac{\partial f} {\partial x_2} = 6x_2+\alpha_1+2\alpha_2 = 0 \implies x_2 = -\frac{\alpha_1+2\alpha_2}{6} \\ \frac{\partial f}{\partial x_3} = 14x_3+3\alpha_2 = 0 \implies x_3 = -\frac{3\alpha_2}{14} \end{align}
把它帶點(diǎn)菜約束條件中去驻右,可以看到什黑,2個(gè)變量兩個(gè)等式,最終可再帶回去求x就可以了堪夭。更高一層愕把,帶有不等式的約束問題怎么辦拣凹?需要用更一般化的拉格朗日乘子法,即KKT條件恨豁,來求解這個(gè)問題嚣镜。

2.關(guān)于KKT條件

任何原始問題約束條件無非最多三種,等式約束橘蜜,大于號(hào)約束菊匿,小于號(hào)約束,而這三種最終通過將約束方程簡(jiǎn)化成兩類:約束方程等于0和約束方程小于0计福。

假設(shè)原始問題約束條件為下例所示:
\begin{align} min \space f = x_1^2-2x_1+1+x_2^2+4x_2+4 \\ s.t. \space x_1 + 10x_2 > 10 \\ 10x_1 - 10 x_2 < 10 \end{align}
那么把約束條件變個(gè)樣子
\begin{align} s.t. \space 10 -x_1 - 10x_2 < 0 \\ 10x_1 - 10 x_2 < 10 \end{align}
現(xiàn)在拿到目標(biāo)函數(shù)中去變成
\begin{align} L(x,\alpha) = f(x)+\alpha_1 g_1(x)+\alpha_2 g_2(x) \\ = x_1^2 - 2x_1+1+x_2^2+4x_2+4+\alpha_1(10-x_1+10x_2)+\alpha_2(10x_2-x_2-10) \end{align}

那么KKT條件的定理是什么呢跌捆?就是如果一個(gè)優(yōu)化問題在轉(zhuǎn)變成
L(x,\alpha,\beta) = f(x) +\sum \alpha_ig_i(x) + \sum \beta_ih_i(x)
其中g(shù)是不等式約束,h是等式約束棒搜。那么KKT條件就是函數(shù)的最優(yōu)值疹蛉,它必定滿足下面條件:

  1. L對(duì)各個(gè)x求導(dǎo)為0
  2. h(x) = 0
  3. \sum \alpha_ig_i(x) = 0 ,\alpha_i \le 0

這三個(gè)等式很好理解,重點(diǎn)是第三個(gè)句子不好理解力麸,因?yàn)槲覀冎涝诩s束條件變完或可款,所有的g(x) \le 0,且求和還要為0克蚂。那么為什么KKT的條件是這樣的呢闺鲸?

某次的g(x)在為最優(yōu)解起作用,那么它的系數(shù)值(可以)不為0埃叭,如果某次g(x)沒有為下一次的最優(yōu)解起作用摸恍,那么它的系數(shù)就必須為0。

三赤屋、函數(shù)間隔和幾何間隔

函數(shù)間隔
對(duì)于給定的訓(xùn)練數(shù)據(jù)集T合超平面(w,b)立镶,定義超平面(w,b)關(guān)于樣本點(diǎn)(x_i,y_i)的函數(shù)間隔為\hat{\gamma_i} = y_i(\omega*x_i+b)

函數(shù)間隔可以表示分類預(yù)測(cè)的正確性及確信度。但是選擇超平面時(shí)类早,只有函數(shù)間隔是不夠的媚媒,因子只要成比較改變\omega和b,超平面并沒有改變涩僻,但函數(shù)間隔卻擴(kuò)大了缭召。

幾何間隔
對(duì)于給定的訓(xùn)練數(shù)據(jù)集T和超平面(\omega,b),定義超平面(\oemga,b)關(guān)于樣本點(diǎn)(x_i,y_i)的幾何間隔為\hat \gamma = y_i(\frac{\omega}{\|\omega\|}*x_i+\frac逆日{\|\omega\|},其中\|\omega\|\omegaL_2范數(shù)嵌巷。

如果\|\omega\|=1,那么函數(shù)間隔和幾何間隔相等室抽。如果超平面參數(shù)\omega,b成比例地改變(超平面沒有改變)搪哪,函數(shù)間隔也成比例改變,而幾何間隔不變狠半。

四噩死、間隔最大化

支持向量機(jī)的基本想法是求解能夠正確分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面颤难。對(duì)線性可分的訓(xùn)練數(shù)據(jù)集而言,線性可分分離超平面有無窮多個(gè)(等價(jià)于感知機(jī))已维,但是幾何間隔最大的分離超平面時(shí)唯一的行嗤。這里的間隔最大化被稱為硬間隔最大化。

間隔最大化的直觀解釋是:對(duì)訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超平面意味著以充分大的確信度對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分類垛耳。也就是說栅屏,不僅將正負(fù)實(shí)例點(diǎn)分開,而且對(duì)最難分的實(shí)例點(diǎn)(離超平面最近的點(diǎn))也有足夠大的確信度將他們分開堂鲜。這樣的超平面應(yīng)該對(duì)未知的新實(shí)例有很好的分類預(yù)測(cè)能力栈雳。

1.最大間隔分離超平面

下面考慮如何求一個(gè)幾何間隔最大的分離超平面,即最大間隔分離超平面缔莲。具體地哥纫,這個(gè)問題可以表示為下面的約束最優(yōu)化問題:
\begin{align} \mathop{\max}_{\omega,b} \space \gamma \\ s.t. \space y_i(\frac{\omega}{\|\omega\|}*x_i+\frac{\|\omega\|}) \ge \gamma (i=1,2,\dots,N)\\ \end{align}
即我們希望最大化超平面(\omega,b)關(guān)于訓(xùn)練數(shù)據(jù)集的集合間隔\gamma痴奏,約束條件表示的是超平面(\omega,b)關(guān)于每個(gè)訓(xùn)練樣本點(diǎn)的集合間隔至少是\gamma

考慮幾何間隔和函數(shù)間隔的關(guān)系式蛀骇,可將這個(gè)問題改成為
\begin{align} \mathop{\max}_{\omega,b} \space \hat{\gamma} \\ s.t. \space y_i(\omega*x_i+b) \ge \hat{\gamma}) (i = 1,2,\dots,N)\\ \end{align}
函數(shù)間隔\hat\gamma并不影響最優(yōu)化問題的解。事實(shí)上读拆,假設(shè)將\omega和b成比例改變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=%5Clambda%5Comega%E5%92%8C%5Clambda%20b" alt="\lambda\omega和\lambda b" mathimg="1">,這時(shí)函數(shù)間隔變成\lambda\hat\gamma擅憔。函數(shù)間隔的改變對(duì)最優(yōu)化問題的不等式約束沒有影響,對(duì)目標(biāo)函數(shù)的優(yōu)化也沒有影響檐晕,也就事實(shí)說暑诸,它產(chǎn)生一個(gè)等價(jià)的最優(yōu)化問題。這樣辟灰,就可以取\hat\gamma=1个榕。將\hat\gamm=1代入上面的最優(yōu)化問題。注意最大化\frac{1}{\|\omega\|}和最小化\frac{1}{2}\|\omega\|是一樣的芥喇。

于是就得到下面的線性可分支持向量機(jī)學(xué)習(xí)的最優(yōu)化問題
\begin{align} \mathop{\min}_{\omega,b} \space \frac{1}{2}\|\omega\|^2 \\ s.t. \space y_i(\omega*x_i+b)-1 \ge 0 (i = 1,2,\dots,N)\\ \end{align}
這是一個(gè)凸二次規(guī)劃問題(contex quadratic programming)問題笛洛。
凸優(yōu)問題是指約束最優(yōu)化問題
\begin{align} \mathop{\min}_{\omega} \space f(\omega) \\ s.t. \space g_i(\omega) \ge 0 (i = 1,2,\dots,N) \\ h_i(\omega) = 0(i=1,2,\dots,l) \end{align}
其中,目標(biāo)函數(shù)f(\omega)和約束函數(shù)g_i(\omega)都是R^n上的可連續(xù)可微的凸函數(shù)乃坤,約束函數(shù)h_i(\omega)R^n的仿射函數(shù)。當(dāng)木匾函數(shù)是f(\omega)是二次函數(shù)且約束函數(shù)g_i(\omega)是仿射函數(shù)時(shí)沟蔑,上述的凸優(yōu)化問題成為凸二次規(guī)劃問題湿诊。
如果求出約束最優(yōu)化問題的解\omega^*,b^*,那么就可以得出最大間隔分離超平面\omega^**x+b^*=0及決策函數(shù)f(x)=sign(\omega^*x+b^*)瘦材,即線性可分支持向量機(jī)模型厅须。

五、學(xué)習(xí)的對(duì)偶算法

為了求解線性可分支持向量機(jī)的最優(yōu)化問題食棕,將它作為原始最優(yōu)化問題朗和,應(yīng)用到拉格朗日對(duì)偶性错沽,通過求解對(duì)偶問題得到原始問題的最優(yōu)解,這就是線性可支持向量機(jī)的對(duì)偶算法(dual algorithm)眶拉。這樣做的優(yōu)點(diǎn)千埃,一是對(duì)偶問題往往根據(jù)容易求解;二是自然引入核函數(shù)忆植,進(jìn)而推廣到非線性可分類問題放可。

首先構(gòu)建拉格朗日函數(shù)(Lagrange function)。為此朝刊,對(duì)每一個(gè)不等式約束引入拉格朗日乘子(Lagrange multiplier)\alpha_i \ge 0 ,i=1,2,\dots,N定義拉格朗日函數(shù):
L(\omega,b,\alpha)=\frac{1}{2}\|\omega\|^2-sum_{i=1}^N\alpha_iyi(\omega*x_i+b)+\sum_{i=1}^N \alpha_i
其中\alpha=(\alpha_1,\alpha_2,\dots,\alpha_N)^T為拉格朗日乘子向量耀里。

根據(jù)拉格朗日對(duì)偶性,原始問題的對(duì)偶問題是極大極小問題\mathop{max}_{\alpha}\mathop{\min}_{\omega,b}L(\omega,b,\alpha)

為了得到對(duì)偶函數(shù)問題的解拾氓,需要先求L(\omega,b,\alpha)對(duì)\omega,b的極小冯挎,再求\alpha的極大
(1)求\mathop{\min}_{\omega,b}L(\omega,b,\alpha)
將拉格朗日函數(shù)L(\omega,b,\alpha)分別對(duì)\omega,b求偏導(dǎo)數(shù)并令其等于0
\begin{align} \bigtriangledown_{\omega}L(\omega,b,\alpha)=\omega-\sum_{i=1}^N\alpha_iy_ix_i=0 \\ \bigtriangledown_bL(\omega,b,\alpha) = -sum_{i=1}^N\alpha_iy_i=0 \\ \omega = \sum_{i=1}^N\alpha_iy_ix_i=0 \space(1)\\ \sum_{i=1}^N\alpha_iy_i=0 \space(2) \end{align}

將(1)代入拉格朗日函數(shù),并利用(2)咙鞍,即可得
\begin{equation}\label{eq1} \begin{split} L(\omega,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j)*x_i+b)+ \sum_{i=1}^N\alpha_i \\ =-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \end{split} \end{equation}

\mathop{\min}_{\omega,b}=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i
(2)求\mathop{\min}_{\omega,b}對(duì)\alpha的極房官,即對(duì)偶問題
\mathop{max}_{\omega} \space -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \space(3)
s.t. \space \sum_{i=1}^N\alpha_iy_i = 0(\alpha_i \ge 0 ,i=1,2,\dots,N)
將公式(3)的目標(biāo)函數(shù)由極大值轉(zhuǎn)換成求極小,就得到下面與之等價(jià)的對(duì)偶最優(yōu)化問題
\mathop{min}_{\omega} \space \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \space(3)
s.t. \space \sum_{i=1}^N\alpha_iy_i = 0(\alpha_i \ge 0 ,i=1,2,\dots,N) \space(4)

(3)解\omega^*,b^*
假設(shè)\alpha^*=(\alpha_1^*,\alpha_2^*,\dots,\alpha_l^*)^T是對(duì)偶最優(yōu)化問題的解奶陈,則存在下標(biāo)使得\alpha_j^* > 0易阳,并求按下式求得原始最優(yōu)化的解\omega^*,b

根據(jù)KKT條件成立,即得
\begin{equation}\label{eq1} \begin{split} \bigtriangledown_{\omega}L(\omega^*,b^*,\alpha^*) = \omega^*-\sum_{i=1}^N\alpha_i^*y_ix_i = 0\\ \bigtriangledown_b L(\omega^*,b^*,\alpha^*)=-\sum_{i=1}^N \alpha_i^*y_i =0 \\ \alpha_i^*(y_i(\omega^**x_i+b^*)-1) \ge 0,i=1,2,\dots,N \\ y_i(\omega^**x_i+b^*)-1 \ge 0,i =1,2,\dots,N \\ \alpha_i^* \ge 0 ,i =1,2,\dots,N \end{split} \end{equation}
因此
\omega^*=\sum_{i=1}^N \alpha_i^*y_ix_i\space(5)
y_j^2=1,且至少存在一個(gè)\alpha_j > 0吃粒,假設(shè)\alpha^* = 0,那么\omega= 0不是原始問題的解,所以
b^{*}=y_j-\sum_{i=1}^N \alpha_i^*y_i(x_i*x_j) \space(6)

那么分離的超平面可以寫成
\sum_{i=1}^N\alpha_i^*y_i(x*x_i)+b^*=0\space(7)
決策函數(shù)可以寫成
f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x*x_i)+b^*) \space (8)

由此可以看出潦俺,分類決策函數(shù)只依賴于輸入x和訓(xùn)練樣本輸入的內(nèi)積,式(8)稱為線性可分支持向量機(jī)的對(duì)偶形式徐勃。

案例
訓(xùn)練數(shù)據(jù)正例點(diǎn)是x_1 = (3,3)^T,x_2=(4,3)^T事示,負(fù)例點(diǎn)是x_3=(1,1)^T,試用線性可分支持向量機(jī)
解:根據(jù)所給數(shù)據(jù)僻肖,對(duì)偶問題是
\begin{equation}\label{eq1} \begin{split} \mathop{\min}_{\alpha} \space \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum_{i=1}^N\alpha_i \\ = \frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2-12\alpha_1\alpha_3-14\alpha_2\alpha_3)-\alpha_1-\alpha_2-\alpha_3 \\ s.t. \space \alpha_1+\alpha_2-\alpha_3 = 0 \\ \alpha_i \ge 0,i =1,2,3 \end{split} \end{equation}

兩個(gè)向量\overrightarrow{a}=[a_1,a_2,\dots,a_n]\overrightarrow肖爵=[b_1,b_2,\dots,b_n]的點(diǎn)積定義為:
\overrightarrow{a} \ast \overrightarrow = \sum_{i=1}^Na_ib_i=a_1b_1+a_2b_2+\dots+a_nb_n

解這一優(yōu)化問題臀脏,將a_3=a_1+a_2代入目標(biāo)函數(shù)并記為
s(a_1,a_2)=4a_1^2+\frac{13}{2}a_2^2+10a_1a_2-2a_1-2a_2

對(duì)a_1,a_2求偏導(dǎo)令其為0劝堪,易知s(a_1,a_2)在點(diǎn)(\frac{3}{2},-1)^T處取極值,該點(diǎn)不滿足約束條件a_2\ge 0揉稚,所以最小值應(yīng)在邊界上達(dá)到秒啦。

當(dāng)a_1 = 0時(shí),最小值s(0,\frac{2}{13})=-\frac{2}{13}搀玖,當(dāng)a_2=0時(shí)余境,最小值s(\frac{1}{4},0)=-\frac{1}{4},于是s(a_1,a_2)在a_1=\frac{1}{4},a_2=0處最小芳来,此時(shí)a_3=a_1+a_2=\frac{1}{4}

這樣,a_1^*=a_2^*=\frac{1}{4}對(duì)應(yīng)的實(shí)例點(diǎn)x_1,x_3是支持向量含末,計(jì)算可得w_1^*=w_2^*=\frac{1}{2},b^*=-2

分離超平面為\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=0
分離決策函數(shù)為f(x)=sign(\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2)

六、軟間隔最大化

線性可分問題的支持向量機(jī)學(xué)習(xí)方法即舌,對(duì)線性不可分訓(xùn)練數(shù)據(jù)是不適用的院崇,因?yàn)檫@時(shí)上述方法中的不等式約束不能都成立没讲。線性不可分意味著不能滿足函數(shù)間隔大于等于1的約束條件。為了解決這個(gè)問題,對(duì)每個(gè)樣本點(diǎn)(x_i,y_i)都引入一個(gè)松弛變量\xi_i \ge 0政己,使得函數(shù)間隔加上變量大于等于1懈凹,這樣約束條件變?yōu)?br> y_i(w*x_i+b) >= 1 -\xi_i
同時(shí)對(duì)于每個(gè)松弛變量\xi_i泪蔫,支付一個(gè)代價(jià)\xi_i,目標(biāo)函數(shù)由原來的\frac{1}{2}\|w\|^2變成
\frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i \space(6.1)
C>0為懲罰參數(shù)蹦狂,一般由應(yīng)用問題解決,C值大時(shí)對(duì)誤分類的懲罰增大嗦明,C值小時(shí)對(duì)誤分類的懲罰減小笼沥。最小化木匾函數(shù)有2層意思:使得\frac{1}{2}\|2\|^2盡量小,即間隔盡量大娶牌,同時(shí)使誤分類點(diǎn)的個(gè)數(shù)盡量小奔浅,C是調(diào)和兩者的系數(shù)

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

1.背景知識(shí)

(1)核技巧

非線性分類問題是指通過非線性模型才能很好地進(jìn)行分類的問題诗良。非線性問題往往不好求解汹桦,希望通過線性分類問題的方法解決這個(gè)問題,所采取的方法是進(jìn)行一個(gè)非線性變換鉴裹,將非線性問題變成線性問題舞骆,通過解變換后的線性問題的方法求解原來的非線性問題。

用線性分類方法求解非線性分類問題分兩步:首先使用一個(gè)變換將原來空間的數(shù)據(jù)映射到新空間径荔;然后在新空間里用線性分類學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類模型督禽。核技巧就屬于這樣的方法。

(2)核函數(shù)定義

設(shè)X是輸入空間(歐氏空間R^n的子集或離散集合)总处,又設(shè)H為特征向量(希伯而空間H)狈惫,如果存在一個(gè)從X到H的映射
\phi(x):X \to H
使得對(duì)所有x,z \in X,函數(shù)K(x,z)滿足條件
K(x,z)=\phi(x)*\phi(z)
則稱K(x,z)為核函數(shù)鹦马,phi(x)為映射函數(shù)胧谈,\phi(x)*\phi(z)為\phi(x)和\phi(z)的內(nèi)積。通常計(jì)算K(x,z)比較容易荸频,而通話\phi(x)和\phi(z)計(jì)算K(x,z)并不容易第岖。

\phi是輸入空間到特征空間的迎神,特征空間一般是高維的试溯,甚至是無窮維,可以看到郊酒,對(duì)于給定的核K(x,z)遇绞,特征空間H和映射函數(shù)\phi的取法并不唯一键袱,可以取不同的特征空間,即便是在同一特征空間也可以取不同的映射摹闽。

(3)核技巧在支持向量機(jī)中的應(yīng)用

在對(duì)偶目標(biāo)函數(shù)中的內(nèi)積x_i*x_j可以用核函數(shù)K(x,z)=\phi(x)*\phi(z)來代替蹄咖,此時(shí)對(duì)偶問題的目標(biāo)函數(shù)成為
W(\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i
這等價(jià)于經(jīng)過映射函數(shù)\phi將原來的輸入空間變換到一個(gè)新的特征空間,將輸入空間中的內(nèi)積x_i*x_j變換成特征空間中的內(nèi)積\phi(x_i)*\phi*(x_j)付鹿,在新的特征空間里從訓(xùn)練樣本中學(xué)習(xí)線性支持向量機(jī)澜汤。學(xué)習(xí)是隱式地在特征空間進(jìn)行的,不需要顯式地定義特征空間和營業(yè)日函數(shù)舵匾。在實(shí)際應(yīng)用中俊抵,往往依賴領(lǐng)域知識(shí)直接選擇核函數(shù)。

2.常用核函數(shù)

(1)多項(xiàng)式核函數(shù)(polynomial kernal function)

K(x,z)=(x*z+1)^p
對(duì)應(yīng)的支持向量機(jī)是一個(gè)p次多項(xiàng)式分類器坐梯,在此情形下徽诲,分類決策函數(shù)成為
f(x)=sign(\sum_{i=1}^{N_s}a_i^*y_i(x_i*x+1)^p+b^*)

(2)高斯核函數(shù)(Guassian kernel function)

K(x,z)=exp(-\frac{\|x-z\|^2}{2\sigma^2})
對(duì)應(yīng)的支持向量機(jī)是高斯徑向基函數(shù)(radial basis function)分類器。在此情形下吵血,分類決策函數(shù)成為
f(x)=sign(\sum_{i=1}^{N_s}a_i^*y_i(exp(-\frac{\|x-z\|^2}{2\sigma^2})+b^*)

(3)字符串核函數(shù)

核函數(shù)不僅可以定義在歐式空間谎替,還可以定義在離散數(shù)據(jù)的集合上。比如蹋辅,字符串核函數(shù)是定義在字符串集合上的核函數(shù)钱贯。字符串核函數(shù)在文本分類、信息檢索侦另、生物信息學(xué)等方面都有應(yīng)用秩命。

兩個(gè)字符串s和t上的字符串核函數(shù)是基于映射\phi_n的特征空間中的內(nèi)積:
k_n(s,t)=\sum_{\mu \in \Sigma^n}[\phi_n(s)]_{\mu}[\phi_n(t)]_{\mu}
=\sum_{\mu \in \Sigma^n}\sum_{(i,j):s(i)=t(j)=\mu}\lambda^{l(i)}\lambda^{l(j)}
字符串核函數(shù)k_n(s,t)給出了字符串s和t中長度等于n的所有子串組成的特征向量的余弦相似度。直觀上看淋肾,兩個(gè)字符串相同的字串越多硫麻,它們就越相似,字符串核函數(shù)的值就越大樊卓。字符串核函數(shù)可以由動(dòng)態(tài)規(guī)劃快速地計(jì)算拿愧。

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

支持向量機(jī)的學(xué)習(xí)問題可以形式化為求解凸二次規(guī)劃問題碌尔,這樣的凸二次規(guī)劃問題具有全局最優(yōu)解浇辜,并且有許多最優(yōu)化算法可以用于這一問題的求解。但是當(dāng)訓(xùn)練樣本容量很大時(shí)唾戚,這些算法往往變得非常低效柳洋,以至無法使用。

序列最小最優(yōu)化(sequential minimal optimization,SMO)算法叹坦,是一種啟發(fā)式算法熊镣,其基本思路是:如果所有變量的解都滿足此最優(yōu)化問題的KKT條件,那么這個(gè)最優(yōu)化問題的解就得到了。因?yàn)镵KT條件是該最優(yōu)化問題的充分必要條件绪囱。否則测蹲,選擇兩個(gè)變量,固定其他變量鬼吵,針對(duì)這兩個(gè)變量構(gòu)建一個(gè)二次規(guī)劃問題扣甲。這個(gè)二次規(guī)劃問題的目標(biāo)是使函數(shù)值變得更小。重要的是齿椅,這時(shí)子問題可以通過解析方法求解琉挖,這樣就可以大大提高整個(gè)算法的計(jì)算速度。子問題有兩個(gè)變量涣脚,一個(gè)是違反KKT條件最嚴(yán)重的那一個(gè)示辈,另一個(gè)由約束條件自動(dòng)確定。如此涩澡,SMO算法將原問題不斷分解為子問題并對(duì)子問題求解顽耳,進(jìn)而達(dá)到求解原問題的目的。

1.兩個(gè)變量二次規(guī)劃的求解辦法

假設(shè)兩個(gè)變量是\alpha_1,\alpha_2妙同,其他變量\alpha_i(i=3,4,\dots,N)是固定的射富,于是SNO的最優(yōu)化問題的子問題可以寫成。

\begin{align} \mathop{min}_{\alpha_1,\alpha_2} \space W(\alpha_1,\alpha_2)=\frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2 \\ -(\alpha_1+\alpha_2)+y_1\alpha_1\sum{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_iK_{i2} \space(7.1) \\ s.t. \alpha_1y_1+\alpha_2y_2 = - \sum_{i=3}^N y_i \alpha_i = \zeta \space(7.2)\\ 0 \leq \alpha_i \leq C \space(7.3) (i =1,2) \end{align}
其中粥帚,K_{ij}=K(x_i,x_j),i,j=1,2,\dots,N,\zeta是常數(shù)胰耗,目標(biāo)函數(shù)中省略不含\alpha_1,\alpha_2的常數(shù)項(xiàng)。

為了求解兩個(gè)變量的二次規(guī)劃問題芒涡,約束可以用二維空間中的圖形表示


二變量優(yōu)化問題.png

不等式約束(7.3)使得(\alpha_1,\alpha_2)在盒子[0,C][0,C]內(nèi)柴灯,等式約束(7.2)使(\alpha_1,\alpha_2)在平行于盒子[0,C][0,C]的對(duì)角線的直線上。因此要求的是目標(biāo)函數(shù)在一條平行于對(duì)角線的線段上最優(yōu)值费尽。這使得兩個(gè)變量的最優(yōu)化問題成為實(shí)質(zhì)上的單變量最優(yōu)化文圖赠群,不訪考慮為變量\alpha_2的最優(yōu)化問題。

假設(shè)初始化可行解為\alpha_1^{old},\alpha_2^{old}旱幼,最優(yōu)化解為\alpha_1^{new},\alpha_2^{new}查描,并且假設(shè)沿著約束方向未經(jīng)剪輯時(shí)\alpha_2的最優(yōu)解為\alpha_2^{new,func}

由于\alpha_2^{new}需滿足不等式約束(7.3),所以最優(yōu)值\alpha_2^{new}的取值范圍必須滿足條件
L \leq \alpha_2^{new} \leq H
其中柏卤,L與H是\alpha_2^{new}所在對(duì)角線段端點(diǎn)的界冬三,如果y_1 \ne y_2
L = max(0,\alpha_2^{old}-\alpha_1^{old}),H=min(C,C+\alpha_2^{old}-\alpha_1^{old})
如果y_1 = y_2,則
L=max(0,\alpha_2^{old}+\alpha_1^{old}-C),H=min(C,a_2^{old},a_1^{old})

下面首先要求沿著約束方向未經(jīng)剪輯即未考慮不等式約束(7.3)時(shí)a_2的最優(yōu)解a_2^{new,func}缘缚,然后在解決剪輯后a_2的解a_2^{new}勾笆,我們用定理來描述這個(gè)結(jié)果
g(x)=\sum_{i=1}^Na_iy_uK(x_i,x)+b \space (7.4)

E_i=g(x_i)-y_i=(\sum_{j=1}^Na_jy_jK(x_j,x_i)+b)-y_i(i=1,2) \space(7.5)

當(dāng)i=1,2時(shí),E_i為函數(shù)g(x)對(duì)輸入x_i的預(yù)測(cè)值與真實(shí)輸出y_i之差

定理 最優(yōu)化問題(7.1)~(7.3)沿著約束方向未經(jīng)剪輯時(shí)的解是
a_2^{new,unc}=a_2^{old}+\frac{y_2(E_1-E_2)}{\eta
其中\eta=K_{11}+K_{22}-2K_{12}=\|Phi(x_1)-\Phi(x_2)\|^2
\Phi(x)是輸入空間到特征空間的映射

經(jīng)剪輯后的a_2的解是
a_2^{new} = \begin{cases} H & \quad a^{new,func} > H \\ a^{new,func}& \quad L \leq a_2^{new,func} \leq H \\ L & \quad a_2^{new,func} < L \end{cases}
a_2^{new}求得a_1^{new}
a_1^{new} = a_1^{old}+y_1y_2(a_2^{old}-a_2^{new})

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末桥滨,一起剝皮案震驚了整個(gè)濱河市窝爪,隨后出現(xiàn)的幾起案子弛车,更是在濱河造成了極大的恐慌,老刑警劉巖蒲每,帶你破解...
    沈念sama閱讀 222,946評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件帅韧,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡啃勉,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門双妨,熙熙樓的掌柜王于貴愁眉苦臉地迎上來淮阐,“玉大人,你說我怎么就攤上這事刁品∑兀” “怎么了?”我有些...
    開封第一講書人閱讀 169,716評(píng)論 0 364
  • 文/不壞的土叔 我叫張陵挑随,是天一觀的道長状您。 經(jīng)常有香客問我,道長兜挨,這世上最難降的妖魔是什么膏孟? 我笑而不...
    開封第一講書人閱讀 60,222評(píng)論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮拌汇,結(jié)果婚禮上柒桑,老公的妹妹穿的比我還像新娘。我一直安慰自己噪舀,他們只是感情好魁淳,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,223評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著与倡,像睡著了一般界逛。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上纺座,一...
    開封第一講書人閱讀 52,807評(píng)論 1 314
  • 那天息拜,我揣著相機(jī)與錄音,去河邊找鬼比驻。 笑死该溯,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的别惦。 我是一名探鬼主播狈茉,決...
    沈念sama閱讀 41,235評(píng)論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼掸掸!你這毒婦竟也來了氯庆?” 一聲冷哼從身側(cè)響起蹭秋,我...
    開封第一講書人閱讀 40,189評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎堤撵,沒想到半個(gè)月后仁讨,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,712評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡实昨,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,775評(píng)論 3 343
  • 正文 我和宋清朗相戀三年洞豁,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片荒给。...
    茶點(diǎn)故事閱讀 40,926評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡丈挟,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出志电,到底是詐尸還是另有隱情曙咽,我是刑警寧澤,帶...
    沈念sama閱讀 36,580評(píng)論 5 351
  • 正文 年R本政府宣布挑辆,位于F島的核電站例朱,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏鱼蝉。R本人自食惡果不足惜洒嗤,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,259評(píng)論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望蚀乔。 院中可真熱鬧烁竭,春花似錦、人聲如沸吉挣。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽睬魂。三九已至终吼,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間氯哮,已是汗流浹背际跪。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留喉钢,地道東北人姆打。 一個(gè)月前我還...
    沈念sama閱讀 49,368評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像肠虽,于是被迫代替她去往敵國和親幔戏。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,930評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容