SVM理論和算法分析報(bào)告

1、硬間隔線性支撐向量機(jī)假設(shè)給定一個(gè)特征空間上的訓(xùn)練數(shù)據(jù)集:T= (xi,yi)，(X2,y2)，(xn$n)其中，x i Rn, yi + 1,- 1, i = 1,2,N Xi為第i個(gè)特征向量或?qū)嵗?，yi為xi的類(lèi)標(biāo)記，當(dāng)yi = 1時(shí)，稱 Xi為正例，當(dāng)yi = - 1時(shí)，稱xi為負(fù)例；（Xi , yi）為樣本點(diǎn)。假設(shè)訓(xùn)練數(shù)據(jù)集是線性可分的（存在硬間隔），那么學(xué)習(xí)的目標(biāo)是在特征空間找到一個(gè)分離超平面，能將實(shí)例分到不同的類(lèi)。分離超平面方程w?x + b = 0，它由法向量 w和截距b決定，可用（w,b）表示。分離超平面將特征空間分為兩部分，一部分是正類(lèi)，一部分是負(fù)類(lèi)。法向量指向的一側(cè)為正類(lèi)，另

2、一側(cè)是負(fù)類(lèi)。一般地，當(dāng)訓(xùn)練數(shù)據(jù)集線性可分時(shí)，存在無(wú)窮個(gè)分離超平面可將兩類(lèi)數(shù)據(jù)正確分開(kāi)，感知機(jī)利用誤分類(lèi)最小的策略，求得分離超平面，不過(guò)這是的解有無(wú)窮多。線性可分支撐向量機(jī)利用間隔最大化求最優(yōu)分離超平面， 解唯一、模型推導(dǎo)1.函數(shù)間隔：一般來(lái)說(shuō)，一個(gè)點(diǎn)距離分離超平面的遠(yuǎn)近可以表示分類(lèi)預(yù)測(cè)的確信程度。在超平面w?x+ b= 0確定的情況下，|w?x+ b|能夠相對(duì)地表示（注意：真實(shí)距離為 也藝）點(diǎn)x距離超平面的遠(yuǎn)近。而w ?x + b的符/w/號(hào)與類(lèi)標(biāo)記y的符號(hào)是否一致能夠表示分類(lèi)是否正確。所以可用標(biāo)量y（w?x + b）來(lái)表示分類(lèi)的正確性及確信度，值為正表示分類(lèi)正確，值為負(fù)表示分類(lèi)錯(cuò)誤。超平面（

3、?, ?）關(guān)于樣本點(diǎn)（？?, ?）的函數(shù)間隔為：? = ?(? ?+ ?)超平面(?, ?)關(guān)于訓(xùn)練數(shù)據(jù)集T的函數(shù)間隔：? = ? ? = ? ?(? + ?) ? ?、 ? /CC CC CC /2.幾何間隔：函數(shù)間隔可以表示分類(lèi)預(yù)測(cè)的正確性及確信度，但是選擇分離超平面時(shí)，只有函數(shù)間隔還不夠。 因?yàn)橹灰杀壤馗淖?w和b,雖然超平面并沒(méi)有改變，但函數(shù)間隔（它是（w,b）的線性函數(shù)）卻依原比例同等改變。為了將（w,b）表示的超平面的唯一化，即每個(gè)超平面對(duì)應(yīng)Rn+1中的唯一向量（w,b），可以對(duì)法向量 w加以規(guī)范化約束/w / = 1，這時(shí)函數(shù)間隔稱為幾何間隔。超平面（?, ?）關(guān)于樣本點(diǎn)（？

4、?, ?）的幾何間隔為：?超平面（?, ?）關(guān)于訓(xùn)練數(shù)據(jù)集T的幾何間隔為:? ?=?,?, ? ?= ?,?; ? -'/? / /? /? = ? ?= ?( ? +on on on cc on no no'二 cc ' ' II ' ' ' ' '/3間隔最大化支撐向量機(jī)學(xué)習(xí)的基本想法是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集并且?guī)缀伍g隔最大的分離超平面。對(duì)于線性可分 的訓(xùn)練數(shù)據(jù)集而言，線性可分分離超平面有無(wú)窮多個(gè)，每一個(gè)都是一個(gè)感知機(jī)，但是幾何間隔最大的分離超 平面時(shí)唯一的。間隔最大化的直觀解釋是：對(duì)訓(xùn)練數(shù)據(jù)集找到幾何間隔最大的超

5、平面意味著以充分大的卻新都對(duì)訓(xùn)練數(shù)據(jù)進(jìn) 行分類(lèi)。也就是說(shuō)，不僅將正負(fù)實(shí)例點(diǎn)要分開(kāi)，而且對(duì)最難分的實(shí)例點(diǎn)（離超平面最近的點(diǎn)）也有足夠多大 的確信度將它們分開(kāi)。因此所要優(yōu)化的問(wèn)題表示為：?,?> ?, ? = ?, ?,? ?改寫(xiě)為,?,?II? /? ?(?+ ?) >?,? = ?,?,?Y的取值不影響最優(yōu)化問(wèn)題的解（如果w ?,b?是最優(yōu)解，那么入w ?,入b?也是最優(yōu)解，因此丫？是變動(dòng)的可以取到 任意值，如果固定Y? ,w?,b?也就變得唯一了），令丫 ？ = 1,等價(jià)變換為，?,? /? /? ? ?(? ? + ?) > ? ?=?？這是為了運(yùn)算方便)， ? II?

6、/?'?,? ?- ?"(?"+ ?) < ? ?=?？ ?, b?。(目標(biāo)函數(shù)是支撐間隔，約束是樣本點(diǎn)在間隔邊界或外側(cè)，目標(biāo)是尋找支撐向量使得間隔最大化)等價(jià)變換 為(標(biāo)準(zhǔn)無(wú)等式約束的凸二次規(guī)劃，?.?凸二次規(guī)劃問(wèn)題存在全局最優(yōu)解w(4)分離超平面與分類(lèi)決策函數(shù) 分離超平面：? ? + ? = ?分類(lèi)決策函數(shù):?(?) = ?(?+ ?)(5)支撐向量與間隔邊界在線性可分情況下，訓(xùn)練數(shù)據(jù)集的樣本點(diǎn)中與分離超平面距離最近的樣本點(diǎn)的實(shí)例稱為支撐向量，支撐向量是使約束條件等號(hào)成立的點(diǎn)，即？- ?(? ?+ ?) = ?，對(duì)于正例點(diǎn)，支撐向量在超平面? +?= ?上

7、，對(duì)于負(fù)例點(diǎn)，支撐向量在超平面 ？ ？?？+ ?= - ?上，沒(méi)有實(shí)例點(diǎn)落在這兩個(gè)平行的超平面?(間隔邊界)之間，這兩個(gè)超平面之間的距離稱為間隔，它依賴于分離超平面的法向量W等于用幾。在決定分離超平面時(shí)只有支持向量起作用，而其他實(shí)例點(diǎn)并不起作用。如果移動(dòng)支持向量將改變所求的解， 但是如果在間隔邊界以外移動(dòng)其他實(shí)例點(diǎn)，甚至去掉這些點(diǎn)，則解是不會(huì)改變的。顯然支撐向量是訓(xùn)練集中 重要的樣本。二、模型求解 將原始問(wèn)題轉(zhuǎn)化為L(zhǎng)agrange對(duì)偶問(wèn)題，通過(guò)求解對(duì)偶問(wèn)題來(lái)獲得原始問(wèn)題的最優(yōu)解：對(duì)每個(gè)不等式約束引入 Lagrange 乘子 a i ,1. Lagrange對(duì)偶函數(shù)：?刀?= ?(?,?,?)

8、= ? /? /?- 刀 ?(? ?+ ?) ?= ?1,2,，N。其中a = ( a 1, a 2,，a n)T為拉格朗日乘子向量，a i > 0 , i = 2.對(duì)偶問(wèn)題：maxmin L(w b, a )a Wb(1) 求?(?, ?,?)?W_(W,b, a ) = W-?bL(W,b, a )=-N刀i = 1N刀i = 1a iyi Xi = 0a iyi = 0得出NW=刀 a i yii =1NXi刀 a i yi = 0i =1帶入拉格朗日函數(shù)，得出? ?(? ? ?)? ' ? ?= 工 工 ? ?(? ?)?= ? ?= ?刀？?？?？（?=?刀 ？?？?？

9、 ?) ? + ?) + 刀 ?= ? ?= ? ?-?刀刀？?？?？?？?(？?？?？?)+ 刀?= ? ?= ? ?= ?(2) 求? ? ?(?, ?, ?)? ?,? 1 1? ? (-?刀 刀? ?(? ?) + ?= ?=?刀?)?= ?. ?.刀? = ?= ? > ? , ?= ?,?, ,?轉(zhuǎn)換為求極小? ? ( T？?厶?刀?(?)-?= ? ?= ?刀?)?= ?根據(jù)對(duì)偶理論，對(duì)上述對(duì)偶優(yōu)化存在，使w 可以轉(zhuǎn)化為求解對(duì)偶問(wèn)題。3.最優(yōu)解根據(jù)KKT條件?. ?.刀? = ?= ? > ? , ?= ?,?, ,？a ?是對(duì)偶問(wèn)題的解，因此求解原始問(wèn)題,?,b?是

10、原始問(wèn)題的解,)=w?-寸*=1 a ?yi)=-寸=1 a ?yi =a ?(yi (w/? ?xi + b?) - 1) = 0 , i = 1,2,N-yi (w7?Xi + b?) - 1 > 0, i = 1,2,-,Na ? > 0, i =-(e)?ML(W b?,?b?L(w?, b?.12,，N由（a）求得其中至少有一個(gè)a 條件（C），得出? > 0 (如果a將?帶入KKT條件，得出Xj = 0 0(a)(b )(c)(d )?=刀? ?= ?0，那么w?= 0 ,b?無(wú)解，顯然它不是原始最優(yōu)化問(wèn)題的解），結(jié)合 KKTyk(w ?xk + b?) - 1 =

11、 0Nyk (刀 a ?yiXi) ? xk+ b?) = 1i =1兩邊同時(shí)乘以yk，由于（yj2= 1N?ykVk(刀 a iyxj ? Xk+ b?) = yki = 1N刀 a ?yi (Xi ?Xk) + b? = yki =1? ?' = ?- X ?(?)?= ?因此分類(lèi)決策函數(shù)為? ?(?) = ?( X ?(?) + ?)?= ?從?, ?中可以看出它們僅僅依賴于？ ? > 0的特征點(diǎn)，即支撐向量（因?yàn)閥k（腫？Xk+ b?） - 1=0? W Xk + b? = ±1，所有x k在分隔邊界上）；這仍是一個(gè)二次凸優(yōu)化，存在全局最優(yōu)解, 二、模型求解仍使

12、用Lagrange對(duì)偶方法求解1.Lagrange 函數(shù)軟間隔線性支撐向量機(jī)一、模型推導(dǎo)如果樣本集中存在特異點(diǎn)使得樣本集線性不可分，即不能滿足函數(shù)間隔大于等于1不等式約束條件，為了解決這個(gè)問(wèn)題，可以對(duì)每個(gè)樣本點(diǎn) (Xi , yi)引入一個(gè)松弛變量E i > 0，使函數(shù)間隔加上松弛變量大于等于1.這樣約束條件變?yōu)?(?+ ?) > ?- ?同時(shí)對(duì)每個(gè)松弛變量E i，支付一個(gè)代價(jià)E i，目標(biāo)函數(shù)變成? ?II? /'+ ?刀 E i? ? ?' ?= ?這里，C > 0稱為懲罰參數(shù)，一般由應(yīng)用問(wèn)題決定，C值大時(shí)對(duì)誤分類(lèi)的懲罰增大，C值小時(shí)對(duì)誤分類(lèi)的懲罰減小。最小化

13、上述目標(biāo)函數(shù)有兩層含義，要使的1 /W I2盡量小即間隔盡量大，同時(shí)使的誤分類(lèi)的點(diǎn)的個(gè)數(shù)盡量小，C是調(diào)和二者的系數(shù)。這時(shí)的間隔稱為軟間隔，因?yàn)殚g隔內(nèi)含義特異點(diǎn)。原始優(yōu)化問(wèn)題：? II? /?+ ?刀? ? ?, ?=?.?. ?- ?- ?(?+ ?) < ?, ? = ?,?,? > ?=?？: , , , , ?(?,?,?,?,?)= 刁 /?刀?= ?-刀?(?(?+ ?) - ?+ ?)-刀?= ? ?= ?其中，? > ?, ? > ?。2.對(duì)偶問(wèn)題：?第?？?(?,？?,？?,？?,？?) ! - - -?,?(1)求? ?(?, ?, ?, ?, ?)?

14、 ? ? ' ' ' ' ! - - -?wL(w,b, Ew-刀 a i yi xi = 0i = 1N得出?bL(wb,=-刀 a iyji = 1C?1Tw=刀 a i yi xii =1N刀 a i yi = 0i =1C- a i - 口 i =w的解是唯一的，但 b的解不唯一，b的解存在于一個(gè)區(qū)間。帶入拉格朗日函數(shù)，得出? ?(?,?,?,?,?)=- 刀 刀？?？?？?？?(？?？?？?)+ 刀？? ? ? ''?=? ?= ?= ?注意它與口無(wú)關(guān)。(2) 求 ? ?(? ? ? ? ?) ? ? ? ?' ' &#

15、39; ' ! - -? ?(- 刀刀?(? ?) + 刀?) ? -? ?刀?=:?= ?> ? >?=? ? 5 5？5 ?> ?,?=? ? 5 5？5 ?-?=? >?= ?,?,?-？5 ''?= ?=? ?= ?消去口 i ,轉(zhuǎn)換為求極小? ?(刃刀 刀? ?(? ?)- ？=?= ?刀?)?= ?. ?.刀? = ?= ? > ? ?= ? ? < ? < ?(3)最優(yōu)解根據(jù)KKT條件?w?L(w? ,b?,?,a ?,?):=W -寸=1 a ?yi Xi?b?L(w?,b',?,a ?,?):=-XN=

16、1 a ?yi = 0-?L(w7,b',?',a ?,?')To?=C?1T- a ? - ?a ?(yi (w? ?Xi + b?) - 1?+ ?i)=0 , i = 1,2, -, N-=0-0Q Q?i?i =0 , i = 12,(a)(b) -(c)-(d)(e)?i > 0 , i = 12,N-(f)yi (w/?xi + b?) - 1 + ? > 0, i = 1,2，N(g)a ? > 0, i = 12,-",N-(h)? > 0, i = 12,-,N-(i)由(a)求得?=oX ? ? ? ?= ?由(c)

17、、( e)(i )得出? ?(? - ?) ? = ?Q? - ? > ?再結(jié)合(f)得出如果? ? <?，那么？ =?;如果?=? ?5? > ?;-:J (j )由(d) ,( h)得出如果?> 0,那么?(? ? +? ?) - ?+ ?=?;如果? =? ?:?, ?(? ?+ ?)? +?不確定；-(k)由(j) , (k)得出 如果? <?< ?,那么？?？= ?,?(?+ ?)-?+?= ?，因此？?(？?？?+?)= ?；? ?' = ?- X ?(?)?= ?由(j) , (g)得出 如果?= ?，那么?= ?, ?K?+ ?) &

18、gt; ?;這說(shuō)明位于間隔邊界上或以外；由(j)，(k)得出如果?= ?，那么?(? ?+ ?) = ?- ?, ? > ?； 此種情況下，進(jìn)一步討論：?如果？?？= ?，那么？?在間隔邊界上； 如果? < ?< 1那么？勿分類(lèi)正確，？?在間隔邊界與分離超平面之間； 如果? = ?，那么？活在分界面上； 如果? > 1那么？?在分離超平面誤分一側(cè)；因此可以看出，軟間隔的支撐向量(？ ？> 0) ?或者在間隔邊界上，或者在間隔邊界與分離超平面之間， 或者在分離超平面誤分一側(cè)。3.支撐向量的另一種解釋 最小化以下目標(biāo)函數(shù)：NX 1 - yi (w?xi + b)+ +

19、 入 IIw fi =1第一項(xiàng)是經(jīng)驗(yàn)損失或經(jīng)驗(yàn)風(fēng)險(xiǎn)，函數(shù)稱為合頁(yè)損失函數(shù)L(y(w?x + b) = 1 - yj (w?xi + b) +，下標(biāo)“ + "表示以下取正值得函數(shù)。+z z > 0z+ = 0 z < 0也就是說(shuō)，當(dāng)樣本點(diǎn)被正確分類(lèi)且函數(shù)間隔大于1時(shí)，損失函數(shù)為0,否則(x i為支撐向量時(shí))損失函數(shù)是1- yj (w?xj + b)，第二項(xiàng)是系數(shù)為入的 w的L 2范數(shù)，是正則化項(xiàng)；這兩種優(yōu)化是等價(jià)的(通過(guò)變量替換方 法);非線性支撐向量機(jī)對(duì)于分類(lèi)問(wèn)題是非線性的(線性模型無(wú)法將正負(fù)實(shí)例正確分開(kāi))，可以利用核技巧，進(jìn)行一個(gè)非線性變換， 將非線性問(wèn)題變換為線性問(wèn)題

20、，通過(guò)解變換后的線性問(wèn)題的方法求解原來(lái)的非線性問(wèn)題。用線性分類(lèi)方法求解非線性分類(lèi)問(wèn)題問(wèn)題分兩步：首先使用一個(gè)變換將原空間的數(shù)據(jù)映射到新空間；然后再新空間里用線性分類(lèi)學(xué)習(xí)方法從訓(xùn)練數(shù)據(jù)中學(xué)習(xí)分類(lèi)模型；核技巧應(yīng)用到支持向量機(jī)，其基本思想：通過(guò)一個(gè)非線性變換將輸入空間(歐氏空間Rn或離散集合)對(duì)應(yīng)于一個(gè)特征空間(希爾伯特空間H),使得在輸入空間R n中的超曲面模型對(duì)應(yīng)于特征空間H中的超平面模型(支撐向量機(jī))，這樣分類(lèi)問(wèn)題的學(xué)習(xí)任務(wù)通過(guò)在特征空間中求解線性支撐向量機(jī)就可以完成。一、非線性支撐向量機(jī)在線性支撐向量機(jī)的對(duì)偶問(wèn)題中，無(wú)論是目標(biāo)函數(shù)還是決策函數(shù)(分離超平面)都只涉及輸入實(shí)例與實(shí) 例之間的內(nèi)積，

21、如果把這個(gè)內(nèi)積？?？?看作是希爾伯特空間中的兩個(gè)特征的內(nèi)積 ？?)? ?(?)= ?(?,?) = ? ?，其中？?？= ?(?) , ?= ? (?)，那么對(duì)于在低維線性不可分的樣本集 ?，?= 1,2, ,?，如果通過(guò)映射？?變換到高維希爾伯特空間?，?= 1,2,?變得線性可分(假設(shè) 能找到這樣的合適的映射？?)，那么就可以使用核函數(shù)？?,？?)代替計(jì)算?，這里？?， ?未/ / / /知，但？?，?，?(?,?)已知。使用核函數(shù)后的對(duì)偶問(wèn)題的目標(biāo)函數(shù)成為：? ? ?(?) = ?刀 刀? ?(? ?)-刀? ?= ?=?= ?最優(yōu)解成為?'=刀? ?= ? ? ? = ?- 刀

22、 ?( ? ?)?= ?分類(lèi)決策函數(shù)成為?(?) = ?(刀?(? ?) + ?)?=?在實(shí)際應(yīng)用中，往往依賴領(lǐng)域知識(shí)直接選擇核函數(shù)，核函數(shù)選擇的有效性需要通過(guò)實(shí)驗(yàn)驗(yàn)證。二、核函數(shù)方法核函數(shù)：設(shè)X是輸入空間(歐氏空間R n的子集或離散集合)，H為特征空間(希爾伯特空間)，如果存在一 個(gè)從X到H的映射，?(x):X f H使得對(duì)所有x ,z X，函數(shù)K (x,z)滿足條件K(x,z) = ?(x) ?(z)則稱K(x,z)為核函數(shù)，？(x)為映射函數(shù)，？(x)?(z)為?(x)和?(z)內(nèi)積；(希爾伯特空間是完備化的內(nèi)積空間，其中的每個(gè)元素是一個(gè)向量(可以無(wú)窮維)，向量之間定義有內(nèi)積運(yùn) 算，且空

23、間關(guān)于內(nèi)積誘導(dǎo)出的范數(shù)是完備的) 核技巧的想法是：在學(xué)習(xí)與預(yù)測(cè)中只定義核函數(shù)K (x,z)，而不顯示地定義映射函數(shù)？，因?yàn)橥ǔＶ苯佑?jì)算 K(x,z)比較容易，而通過(guò)?(x)和?(z)計(jì)算K(x,z)并不容易。注意，？(x)是輸入空間R n到特征空間H的映射， 特征空間H般是高維的，甚至是無(wú)窮維的。我們需要的是特征空間中兩個(gè)特征的內(nèi)積結(jié)果，而不是特征的 表示。如果我們能通過(guò)簡(jiǎn)單的函數(shù)K(x,z)得到?(x) ?(z)的內(nèi)積，那就簡(jiǎn)化了問(wèn)題，不用考慮？?的形式，這正是核函數(shù)的妙用之處。對(duì)于給定的核函數(shù)K (x,z)，特征空間H (希爾伯特子空間)和映射函數(shù)？?的取法不唯一，因?yàn)楹撕瘮?shù)給出 的是映射

24、后的內(nèi)積結(jié)果，所選取的映射過(guò)程可能是不同的。核函數(shù)判定定理：設(shè)K:X XX- F是對(duì)稱函數(shù)，貝叮(x,z)為正定核函數(shù)的充要條件是對(duì)任意xi X,i =1,2,m K(x,z)對(duì)應(yīng)的 Gram矩陣:K= K(?, ?)mxm是半正定的。對(duì)于一個(gè)具體函數(shù)K (x,z)來(lái)說(shuō)，檢驗(yàn)它是否為正定核函數(shù)并不容易，因?yàn)橐?duì)任意有限輸入集驗(yàn)證K對(duì)應(yīng)的Gram矩陣是否為半正定。在實(shí)際問(wèn)題中往往應(yīng)用已有的核函數(shù)。常用核函數(shù)：(1) 多項(xiàng)式核函數(shù)：K(x,z) = (x?z+ 1)p,對(duì)應(yīng)的支撐向量機(jī)是一個(gè) p次多項(xiàng)式分類(lèi)器；(2) 高斯核函數(shù)：K(x,z) = exp (- 謬)，對(duì)應(yīng)的支撐向量機(jī)是高斯徑向基

25、函數(shù)分類(lèi)器；(3) 字符串核函數(shù)：1) 基本定義： 有限字符表工；字符串s: s(1)s(2)s(|s|),字符串s的長(zhǎng)度|s|，空字符串長(zhǎng)度為0;字符串連接：st , s和t分別是字符串；長(zhǎng)度為n的字符串集合工n;所有字符串的集合：工?= ?n=0工n;s 的子串 u:給定一個(gè)指標(biāo)序列i = (i 1, i 2, ,i |u|), 1 < i 1 < i 2 < ? << |s|, u = s(i)=s(ijs(i2)s(i|u|)，其長(zhǎng)度記作 l (i ) = i|u| - i 1 + 1，如果 i 是連續(xù)的，則1 (i) = |u|；否則1 (i) >

26、 |?|。2) 映射定義：?假設(shè)S是長(zhǎng)度大于或等于n字符串的集合，s是S的元素，建立字符串集合S到特征空間？?？= ?-的映射 ? ?(?), ?表示定義在?-上的實(shí)數(shù)空間，其每一維對(duì)應(yīng)一個(gè)字符串 ？£?，映射？?(？?)將字符串s ?對(duì)應(yīng)于空間中？?？的一個(gè)向量，其在u維上的取值為?(?)?(?) ? = E?:?(?)=?，這里，0 < ? < 1是一個(gè)衰減參數(shù)，？?)表示字符串i的長(zhǎng)度，求和在s中所有與u相同的子串上進(jìn)行。 說(shuō)明：u代表維，如在字符串u維，顯然空間有|藝|n維，每一維是字母表藝上的一個(gè)長(zhǎng)度為n的字符串； ?(?)是表示通過(guò)指標(biāo)序列i，表示的一個(gè)s的子

27、串，這個(gè)子串可以不連續(xù)；？?(？?)= u表示s的子串?(?)等于u;l (i)是子串？?(？?)在s中的指標(biāo)序列i的最后一個(gè)分量減去第一個(gè)分量然后加一；例子：假設(shè)工為英文字符集，n為3，S為長(zhǎng)度大于或等于3的字符串集合，考慮將字符集S映射到特征空間?3?3= ?"，?3的一維對(duì)應(yīng)于字符串 asd，這是，字符串“ Nasdaq”在這一維上的值是?(?asdaq)asd = ?3,只有一個(gè)子串a(chǎn)sd，序號(hào)是234；字符串“ lass das ”在這一維上的值是?(lass das) asd = 2?5，因 為有兩個(gè)asd，序號(hào)分別為236,246;3) 核函數(shù)兩個(gè)字符創(chuàng)s和t的字符串核

28、函數(shù)是基于映射的特征空間中的內(nèi)積：kn(S,t)= 刀?(?) ?(?) ?= 刀?(?)?(?)? (i j )：s(i ) = t(j )= u它給出了字符串s和t中長(zhǎng)度等于n的所有子串組成的特征向量的余弦相似度。直觀上，兩個(gè)字符串相同的 子串越多，它們就越相似，字符串核函數(shù)的值就越大，字符串核函數(shù)可以由動(dòng)態(tài)規(guī)劃快速計(jì)算。序列最小最優(yōu)化算法支撐向量機(jī)的學(xué)習(xí)問(wèn)題可以形式化為求解凸二次規(guī)劃問(wèn)題，具有全局最優(yōu)解，并且有很多最優(yōu)化算法可以用 于求解這一問(wèn)題。但是當(dāng)訓(xùn)練樣本容量很大時(shí)，這些算法往往變得非常低效。序列最小最優(yōu)化算法，由 Platt在1998年提出，它是一種啟發(fā)式算法，相對(duì)比較高效。SM

29、(算法基本思路是：如果所有變量的解都滿足次最優(yōu)化問(wèn)題的KKT條件，那么這個(gè)最優(yōu)化問(wèn)題的解就得到了，因?yàn)镵KT條件是該最優(yōu)化問(wèn)題的充分必要條件，否則，選擇兩個(gè)變量，固定其他變量，針對(duì)這個(gè)兩個(gè)變量構(gòu)建一個(gè)二次規(guī)劃問(wèn)題，這個(gè)二次規(guī)劃問(wèn)題關(guān)于這兩個(gè)變量的解應(yīng)該更接近原始二次規(guī)劃問(wèn)題的解，因?yàn)?這會(huì)使得原始二次規(guī)劃問(wèn)題的目標(biāo)函數(shù)值變得更小。重要的是，這時(shí)子問(wèn)題可以通過(guò)解析方法求解，子問(wèn)題 有兩個(gè)變量，一個(gè)是違反 KKT條件最嚴(yán)重的那一個(gè)，另一個(gè)由約束條件自動(dòng)確定。如此，算法將原問(wèn)題不斷 分解為子問(wèn)題并對(duì)子問(wèn)題求解，進(jìn)而達(dá)到求解原問(wèn)題的目的。原始優(yōu)化問(wèn)題：Nmin /w+ CE E i w,b, E 2i

30、 =1s.t yi (w?Xi + b) > 1 - E i , i = 1,2，,NE i >0,i = 1,2，N對(duì)偶問(wèn)題:N1min 刀a 2刀 a ii =1j =1a jyiyjK(Xi ,Xj)-刀 a ii =1S.t .0 <子問(wèn)題的兩個(gè)變量只有一個(gè)是自由變量，假設(shè)a 的等式約束可知：NE a i yi = 0i =1< C,i = 1,2,N,a 2為兩個(gè)變量，固定a3,a 4,，a N,那么根據(jù)上面N*1 =-刀 a i yii =3由于y i ?yi = 1，所以1 = - y 1 刀 a i yii =2如果a 2確定，那么a 1也隨之確定，所以

31、子問(wèn)題中同時(shí)更新兩個(gè)變量。優(yōu)化子問(wèn)題：SMO?法包含兩個(gè)部分：求解兩個(gè)兩個(gè)變量二次規(guī)劃的解析方法和選擇變量的啟發(fā)式方法。不失一般性，假3 ,1 2K22 a 2+ y1y2K12 a 1 a 2 - ( a 1 + a 2) + y1 a 1 刀 yi a i K1i =3設(shè)選擇的兩個(gè)變量是a 1 ,a 2，其他變量a 3 , a 4,，a n固定，于是SMO勺優(yōu)化問(wèn)題的子問(wèn)題可以寫(xiě)成:N1 2min W a 1, a 2） = 2 K11 a 1 + a 1 , a 22N+ y2 a 2 刀 yi ai = 3i K2S.t .其中，K ij = K(Xi,Xj) , i,j = 1,2,

32、，N,?是常數(shù)，目標(biāo)函數(shù)中省略了不含aa 2的常數(shù)項(xiàng)。a 1y 1 + a 2y2 =-刀 a i yi = ?i =3（1）求解兩變量二次規(guī)劃的解析方法:可行解范圍:假設(shè)子問(wèn)題的初始可行解為a old , 不等式約束（盒子約束）條件的限制:a Old，最優(yōu)解為a new,a 2eW，顯然最優(yōu)解受等式約束（直線約束）和(a)化簡(jiǎn)為new1=y1? - anew2 :old呵、=y1( a 1丄 old 、y1 + a 2y2)-newa 2 y2y1 w Cnew1 = y1?-new2 .、亦1 = a 1ld+ a 2ldy2y1- a2°切1 w c?如果y 2 = y1，那么

33、old1olda 2newa 2 W Ca old +oldnew olda 2- C W a 2 W a 1olda 2(b)由(a) , (b)得出:如果?= ?，那么？=?) = ?(? ?y ) :?)?W ?W ? ( ?+(c)? 如果y 2工，那么oldW a 1old2 +oldold久 2- a 1W a 2ew W C-olda 2(d)由(a) , (d)得出:如果？?？工？?？，那么？=?) = ? I I)?(?,? )?< ?W ?(? - ?+(e)如果最優(yōu)解不在約束內(nèi)，必須被剪輯。假設(shè)在沿著約束方向a?;a 2y2 = ?未經(jīng)剪輯時(shí)a 2的最優(yōu)解為a 2e

34、w unc;然后再求剪輯后a 2的解?F面忽略不等式約束,求取迭代解new, unc2min W( a 1,a 1 , a 21a 2)= 2K11Ny +22a2kk1 一 2+21aa2y2(a 1 + a 2) + y1 a 1 (刀 yi a i K1 )i =3+ y2 a 2 (刀 yi a i K2)i =3由于 a iy1 = ?- a 2y2，得出%1y"1=(?- a 2y2)y1a 1 = (? - a 2y2)y1帶入目標(biāo)函數(shù)1W a 2)= 21(?-1 一 2+2吩2ya22y2K12(? - a 2y2)a 2 - (? - a 2丫2)丫1- a 2

35、N+ (?-a 2丫2)( 刀 yi a i Ki1 ) + y2 a 2 (刀 yi a i Ki2)對(duì)a 2求導(dǎo)?W=-y2Kii( ?- a 2y2) + K22 a 2 + y2Ki2? - 2Ki2 a 2 + yiy2 - i - y2 (刀 yi a i Ki )i = 3+ y2 (刀 yi a i K2 )i =3=-y2Kii? + a 20i + K22 a 2 + y2Ki2? - 202 a 2 + yiy2 - iN-y2(刀 yi a i Ki) + y2 (刀 yi a i %2)i = 3i =3= -2?+ a 2(Kii+ K22 - 2Ki2) + y2

36、Ki2?+ yiy2 - i-y2(刀 yii = 3a i Ki )+ y2(刀 yi a i Ki2 )i =3a 2(Kii + K22 - 2Ki2)- y2 ( y2 - yi + Kii? - K12? +i Ki )-(刀 yi a i K2 )i = 3令其為0,得到new, unc /、a 2(Kii + K22 - 2Ki2)=y2(Ny2- yi + Kii?- Ki2?+ (刀 yii = 3Na i Ki)-(刀 yi a i 2)i = 3將?= a ildyi + a 2ldy2帶入，得到new, unca 2(Kii + K22 - 2Ki2)=y2 ( y2

37、- yi + Kii a old yi + Kii aold2 y2-Ki2 a ildyi- Ki2 a 尸 y?i Ki )-(刀 yi a i K2 )i = 3old、，=y2 ( y2 - yi + Kii a i yi+ Kii a oldy2-Ki2 a old yi - Ki2a0ldy2oldoldiii - yi a 1 Zi-y2 a 2氏21)-a i K2 -old $old / 、yi a i 22 - y2a 2 k22)=y2( y2- yi + Kii aildyi + Kii a oldy2-Ki2 a ild yi -oldKi2 a 2 y2 - yia

38、 ild Kii - y2 a 2ld K?iN+ yi a oldKi2+ y2 a oldK?2 +NNy2( y2 -yi+ (Kii +K?2 -2Ki2)aold2 y2 + (刀 yi =iq a i Ki-刀 yi a i Ki2 )i = iNN(Kii +K22-2K12)aold2 +y2 ( y2' yi + (刀 yia i Ki -刀 yi a i K2 )i = ii =i(刀 yi a i Ki -刀 yi a i Ki2)i =ii = i=(K11 + K22 - 2K12)olda 2+ y2(刀 yi a iKi1 - y1)-(刀 yi a i

39、Ki2 - y2)i = 1i =1令Ei = £=' a j Kji + b- yi , i 的預(yù)測(cè)與真實(shí)輸出y i之差；那么1,2；其中斗=1片a j Ki + b是對(duì)輸入x i的預(yù)測(cè),因此E i表示對(duì)輸入x inew, a 2unc(K11 + K22 - 2K|2)= (K11old+ K22 - 2K12) a 2N+ y2(刀yi a M1 - yj -i = 1N(刀 yi a i 氏2 - y2)i = 1(K11 + K22 - 2K12)olda 2+ y2(E1 - E2)new unca 2old ,y2(E1 - E2)a 2+2(Ku + K22

40、- 22)old ,y2(E1 - E2)a 2 +/ 0(X1)- 0(X2)!f-因此?H,a 2ew =new, unc2a 2L,new unca 2> ?new, uncL W a 2new, unca 2new ,new由y a 1+ y2a 2= y11ld + y2 a 2ld 得出new ,y1(y1a 1 +new、y2a 2 )/ old=y1(y1a 1y2 a old )（2）變量的（啟發(fā)式）選擇方法:? ? = ?+ ? ( ?)SMO算法在每個(gè)子問(wèn)題中選擇兩個(gè)變量?jī)?yōu)化，其中至少一個(gè)變量是違反KKT條件的。1）第一個(gè)變量的選擇SMO爾選擇第1個(gè)變量的過(guò)程為外層

41、循環(huán)。外層循環(huán)在訓(xùn)練樣本中選取違反 其對(duì)應(yīng)的變量作為第1個(gè)變量。具體地，檢驗(yàn)訓(xùn)練樣本點(diǎn) （Xj , yi）是否滿足 隔SVM文章）KKT條件最嚴(yán)重的樣本點(diǎn)，并將KKT條件，即（具體推導(dǎo)見(jiàn)軟間如果? = ?，那么 ？?？=?, ?(? ? + ?) > ?；如果? <?<?,那么？?= ?,?如(？?？?？?？+?)- ?+?= ?，因此？?(？?？?？+?)= ?；如果?= ?，那么？?(？?？+ ?) = ?- ?, ? >?；Na i = 0 ? yi (刀 a j yj K(xj ?xi) + b)j = 1N0 < a i < ? ? yi (刀 a

42、 j yj K(xj ?xi ) +j =1b) = 1a i = C? yi (刀 a j yj K(xj ?xi) + b)j = 1該檢驗(yàn)是在？?范圍內(nèi)進(jìn)行的。在檢驗(yàn)過(guò)程中，外層循環(huán)首先遍歷所有滿足條件0< a i < ?的樣本點(diǎn)，即在間隔邊界上的支撐向量點(diǎn)，檢驗(yàn)它們是否滿足KKT條件；如果這些樣本點(diǎn)都滿足KKT條件，那么遍歷整個(gè)訓(xùn)練集，檢驗(yàn)它們是否滿足 KKT條件；2）第二個(gè)變量的選擇SMO爾選擇第2個(gè)變量的過(guò)程為內(nèi)層循環(huán)。假設(shè)在外層循環(huán)中已經(jīng)找到第1個(gè)變量?，現(xiàn)在要在內(nèi)層循環(huán)中找第2個(gè)變量？?。第2個(gè)變量的選擇的標(biāo)準(zhǔn)是希望能使 ？?有足夠大的變化（這樣新的a i也會(huì)有足夠

43、大的 變化，從而盡快趨向滿足 KKT條件的值）。從上面的推導(dǎo)中可以發(fā)現(xiàn)，a 2eW<賴于|Ei - E2|，為了加快計(jì)算速度，一種簡(jiǎn)單的做法是選擇?,使其對(duì)應(yīng)的|Ei -巨|最大。因?yàn)?已定，Ei也是確定的。如果E i是正，那么選擇最小的E i作為E2；如果如果E i是負(fù)， 那么選擇最大的E i作為E2;（為了節(jié)省時(shí)間，將所有的E i值保存在一個(gè)列表中）；在特殊情況下，如果內(nèi)層循環(huán)通過(guò)以上方法選擇的？?不能使目標(biāo)函數(shù)有足夠的下降，那么采用以下啟發(fā)式規(guī)則繼續(xù)選擇？?；遍歷在間隔邊界上的支撐向量點(diǎn)，依次將其對(duì)應(yīng)的變量作為？ ？?試用，直到目標(biāo)函數(shù)有足夠的下降。若找不到合適的？ ？?，那么遍歷

44、訓(xùn)練數(shù)據(jù)集；若仍找不到合適的 ？ ？?，則放棄第i個(gè)?，再通 過(guò)外層循環(huán)尋求另外的？ ？?。3）計(jì)算閾值b和差值? ?每次完成兩個(gè)變量的優(yōu)化后，都要重新計(jì)算閾值b和?,使用迭代的方法更新b；根據(jù)定義預(yù)測(cè)誤差 Ei = f=iyj aj Ki + b- yi，展開(kāi)得NEi + yi - XjJ=3yj下面討論如何迭代更新 顯然每次更新完a new,?a）.如果? < ?" Ei =刀 yj a j Ki + b°ldj = 3 a j Ki = a °ld yi Kii?yi +oldolda iyi Kii + a 2 y2K2ia old y2K2i + bold(f)?帶入（f），得出b,即獲得?:a new后 b new的選擇應(yīng)該使得KKT條件成立;?時(shí)，由KKT條件可知：Nyi (刀 a i yi K(Xi ?xi) + b) = ii = iNa iyiK(Xi ?xi) + b = yi?=?-刀 ? (? ?)?= ?=