- 相關(guān)推薦
使用誤差中心基準(zhǔn)最優(yōu)化方式的支持向量機(jī)的快速訓(xùn)練(一)
外文資料譯文
使用誤差中心基準(zhǔn)最優(yōu)化方式的支持向量機(jī)的
快速訓(xùn)練
L. Meng,Q. H. Wu。
電機(jī)工程和電子學(xué)學(xué)院，利物浦大學(xué)，利物浦， L69 3GJ 英國(guó)
摘要: 這篇文章為支持向量機(jī) (SVM) 訓(xùn)練提出一個(gè)新算法，這個(gè)算法是基于由現(xiàn)在的機(jī)器引起的誤差中心束來(lái)訓(xùn)練一部機(jī)器的。從各種不同的訓(xùn)練組合的實(shí)驗(yàn)中展現(xiàn)出新的運(yùn)算法則刻度的計(jì)算時(shí)間與訓(xùn)練組合大小幾乎成線(xiàn)性關(guān)系，因此與二次規(guī)劃標(biāo)準(zhǔn)(QP)技術(shù)相比可被提供于更大的訓(xùn)練組合。
keywords: 支持矢量機(jī)器, 二次規(guī)畫(huà), 模式分類(lèi), 機(jī)器了解。
1 引言
在統(tǒng)計(jì)學(xué)理論中基于最近的進(jìn)展，支持向量機(jī) (SVMs) 組成一個(gè)勇于式樣分類(lèi)的學(xué)習(xí)系統(tǒng)的新團(tuán)體。訓(xùn)練一個(gè)支持向量機(jī)相當(dāng)于解決一個(gè)有著密集矩陣的二次規(guī)劃的問(wèn)題。二次規(guī)劃標(biāo)準(zhǔn)的解決需要這個(gè)矩陣的所有儲(chǔ)存而且他們的效率在于他們的稀疏程度,他向有著大的訓(xùn)練組合設(shè)定的支持向量機(jī)訓(xùn)練提出申請(qǐng)。
被 Vapnik 和他的隊(duì)被提倡的支持向量機(jī), 是一新的模式分類(lèi)和非線(xiàn)性回歸技術(shù).(參看【1】,【2】,和【3】)
由于線(xiàn)性分離的問(wèn)題,一個(gè)支持向量機(jī)是一個(gè)從有最大值的一組反面樣本中分離出一組正面樣本的超平面。雖然簡(jiǎn)單直觀, 但是這個(gè)最大值的觀點(diǎn)實(shí)際上開(kāi)拓了在統(tǒng)計(jì)學(xué)理論中的結(jié)構(gòu)風(fēng)險(xiǎn)最小化（SRM）原則【4】. 因此，所了解的機(jī)器不僅有最小的經(jīng)驗(yàn)風(fēng)險(xiǎn)還有好的推廣的能力。
對(duì)于非線(xiàn)性可分離的問(wèn)題,在分類(lèi)超平面被建立之前輸入一個(gè)非線(xiàn)性映射 ，而這個(gè)分類(lèi)超平面將訓(xùn)練樣本從輸入空間傳送到比較高維的特征空間。分類(lèi)超平面是建立在特征空間的。他在輸入空間產(chǎn)生一個(gè)非線(xiàn)性決定邊界。這個(gè)決定邊界是由在特征空間的處于分類(lèi)超平面的映射點(diǎn)組成的。非線(xiàn)性映射運(yùn)用模式可分離定理通過(guò)【5】被一致運(yùn)用.一個(gè)復(fù)雜的存在于一個(gè)高維非線(xiàn)性空間的模式分類(lèi)問(wèn)題比在一個(gè)低維空間更有可能是線(xiàn)性分離的。
對(duì)于支持向量機(jī), 分類(lèi)決定函數(shù)的新的樣本被定義為:
指一個(gè)分類(lèi)樣本, 指相符合的特征向量，和b分別指常向量和分類(lèi)超平面的截距，向量和常量b是最優(yōu)參數(shù)。
w和b的優(yōu)化相當(dāng)于優(yōu)化一個(gè)服從于一些線(xiàn)性約束的目標(biāo)函數(shù),。目標(biāo)函數(shù)聯(lián)合支持向量機(jī)優(yōu)化是一個(gè)凸二次函數(shù)而且因此最佳化問(wèn)題沒(méi)有最大限度的限制。許多變量的二次函數(shù)的優(yōu)化問(wèn)題在優(yōu)化理論方面被很好理解并且大多數(shù)與之接近的標(biāo)準(zhǔn)能直接應(yīng)用于支持向量機(jī)的訓(xùn)練。然而，大多數(shù)二次規(guī)劃標(biāo)準(zhǔn)技術(shù)需要在目標(biāo)函數(shù)里面二次型的全部?jī)?chǔ)存空間。他們或者僅僅適合一些小問(wèn)題或者僅僅適合二次型非常稀疏的假設(shè)，也就是說(shuō)大多數(shù)的二次型元素是零。不幸地是，對(duì)于一個(gè)支持向量機(jī)佳化問(wèn)題這不事實(shí)，問(wèn)題中二次型方程不僅僅是密集的而且有一個(gè)在訓(xùn)練組合中隨著數(shù)據(jù)點(diǎn)二次增長(zhǎng)的能力。為了有1000個(gè)或者更多樣本的訓(xùn)練任務(wù)，存儲(chǔ)器的需求將會(huì)超過(guò)百兆字節(jié)因此這是不可能碰到的。這禁止了對(duì)于有大的訓(xùn)練組織問(wèn)題的二次規(guī)劃標(biāo)準(zhǔn)技術(shù)的申請(qǐng)。一個(gè)替代方案在需要時(shí)每一次會(huì)重新計(jì)算二次型。但是這變得非常的昂貴因?yàn)槎我?guī)劃技術(shù)是重復(fù)的并且在每次的重復(fù)中需要對(duì)二次型進(jìn)行計(jì)算。
如此的思路產(chǎn)生了支持矢量機(jī)器的一個(gè)新的訓(xùn)練算法的設(shè)計(jì)。在這篇文章中被推薦的算法是概念性的簡(jiǎn)單事情，一般很快而且比標(biāo)準(zhǔn)的二次規(guī)劃技術(shù)有更大規(guī)模的資產(chǎn)。
2 在支持向量機(jī)訓(xùn)練中的最優(yōu)化問(wèn)題
給一個(gè)訓(xùn)練樣本的，其中是模仿一個(gè)輸入樣本所屬于的目標(biāo)響應(yīng)指示,結(jié)合訓(xùn)練一個(gè)支持向量機(jī)的最佳化問(wèn)題能被寫(xiě)成如下：
OP1:
限制條件
其中間隙被兩個(gè)超平面所限定而且通過(guò)來(lái)測(cè)量，是允許間隙出現(xiàn)誤差的松弛變量，C是一個(gè)與有一些間隙誤差的寬大間隙交換的參數(shù)。當(dāng)時(shí)，機(jī)器被稱(chēng)為一個(gè)固定間隙支持向量機(jī)因?yàn)樗械挠?xùn)練樣本必須放在邊緣外部，是不允許有劃分誤差的。否則，機(jī)器被成為一個(gè)可變間隙支持向量機(jī)。
通過(guò)引入拉格朗日乘子和和拉格朗日函數(shù)
因此要對(duì)拉格朗日函數(shù)關(guān)于求最小值并且要對(duì)拉各朗日函數(shù)關(guān)于的最大值，其中我們有
并且OP1的二重形式如下：
其中定義為在特征空間中的兩個(gè)向量的內(nèi)積并被稱(chēng)為核函數(shù)。核函數(shù)的使用允許一個(gè)支持向量機(jī)，沒(méi)有以前明確的特征空間的描述，他的運(yùn)用限制了在特征空間的分類(lèi)超平面和在那個(gè)空間的分類(lèi)向量這樣的詳細(xì)描述特征向量的計(jì)算負(fù)擔(dān)沒(méi)有增加。
OP2本質(zhì)上是一個(gè)二次規(guī)劃問(wèn)題因?yàn)樗邢旅娴男问剑?br />
其中矩陣Q是二次型。對(duì)于支持向量機(jī)的訓(xùn)練，他被定義為
由【6】和【7】得Karush―Kuhn―Tucker(KKT)條件是對(duì)一組變量達(dá)到最優(yōu)得最優(yōu)化問(wèn)題得充分必要條件。對(duì)于問(wèn)題OP1運(yùn)用（KKT）條件，我們知道最優(yōu)解決必須要滿(mǎn)足
和
包含
方程式（9）以及方程式（8）和（10）顯示出只有那些在間隙邊界上的而不是那些處在變化的樣本是符合要求的 。方程（8）表明對(duì)于符合等于零的所有樣本必須要被正確的分類(lèi)并且放在間隙以外。方程（10）表明具有符合的間隙誤差要等于上面的受約束的C。此外，方程（7）顯示非零的松弛變量只有當(dāng)時(shí)存在而且所有的間隙誤差都要受到懲罰。
3 誤差中心基準(zhǔn)最優(yōu)化
一個(gè)二次規(guī)劃問(wèn)題的大小取決于二次型Q。在支持向量機(jī)訓(xùn)練中，矩陣Q的大小是，其中表示訓(xùn)練數(shù)據(jù)點(diǎn)的個(gè)數(shù)。如所描述的，有一個(gè)為明確存儲(chǔ)Q的標(biāo)準(zhǔn)解決技術(shù)的必要條件，但是在支持向量機(jī)訓(xùn)練中禁止運(yùn)用標(biāo)準(zhǔn)二次規(guī)劃去計(jì)算有大量數(shù)據(jù)組的支持向量機(jī)的訓(xùn)練。
考慮到這些，通過(guò)【8】一個(gè)新的支持向量機(jī)訓(xùn)練的技術(shù)產(chǎn)生了�；镜南敕ㄊ侨嚎s最初的訓(xùn)練組然后訓(xùn)練一個(gè)關(guān)于由最近壓縮群中心所組成的一個(gè)工作組的機(jī)器。在每次重復(fù)中壓縮通過(guò)分離每個(gè)將一個(gè)支持向量作為它的中心的群為兩個(gè)附屬群來(lái)進(jìn)行更新。因?yàn)檫@個(gè)新的算法從由群中心所組成的工作組中摘取分類(lèi)信息，所以被稱(chēng)為中心基準(zhǔn)最優(yōu)算法。關(guān)于各種訓(xùn)練組的試驗(yàn)已經(jīng)顯示出采用中心基準(zhǔn)最優(yōu)化方法的訓(xùn)練時(shí)間比標(biāo)準(zhǔn)技術(shù)所用的時(shí)間要少的多。對(duì)于大的訓(xùn)練任務(wù)，中心基準(zhǔn)最優(yōu)化算法能將所用的時(shí)間少于用標(biāo)準(zhǔn)技術(shù)所用時(shí)間的1/150。
可惜的是，雖然一個(gè)最優(yōu)邊界能夠通過(guò)中心基準(zhǔn)最優(yōu)化的方法找到，但是產(chǎn)生決定邊界的最優(yōu)化不能對(duì)每一次運(yùn)行有所保證。（參看Fig.1(a)和Fig.1(b)進(jìn)行比較）。這是因?yàn)橐粋�(gè)k方式計(jì)算法已被運(yùn)用于分離中心基準(zhǔn)最優(yōu)化方法。這個(gè)算法的上升性質(zhì)使他在不同的最優(yōu)化限制方面變得容易捕捉到。不管產(chǎn)生的決定邊界有不精確和多樣性，中心基準(zhǔn)的快速性展現(xiàn)了中心基準(zhǔn)算法的巨大潛力,它用于有大量訓(xùn)練組的支持向量機(jī)最優(yōu)化問(wèn)題的快速解決。
通過(guò)觀察Fig.1(b),失去支持向量的狀態(tài)或者在內(nèi)或者在間隙的誤差的一邊。而且因?yàn)樗麄儧](méi)有被包括在最后的訓(xùn)練中，他們的匹配是零。KKT條件表明結(jié)合零的樣本必須能被正確的分類(lèi)并且要放在間隙的外測(cè)。通過(guò)這個(gè)得到啟發(fā)，已經(jīng)對(duì)中心基準(zhǔn)最優(yōu)化進(jìn)行了修改�，F(xiàn)在，通過(guò)分離那些符合KKT條件的樣本，每一個(gè)群被分離成為了兩個(gè)附屬群并且這樣被放在了外部或者是放在來(lái)自那些違反KKT條件的當(dāng)前間隙和放在內(nèi)部或者是放在當(dāng)前間隙的誤差的一邊。一方面，如果在最初的至少一個(gè)群違反KKT條件的訓(xùn)練組有一些樣本，他們將被分離。另一方面，程序要反復(fù)到在最初的違反KKT條件的訓(xùn)練組沒(méi)有樣本為止。因?yàn)镵KT條件是解決最優(yōu)化問(wèn)題的必要充分條件，所以通過(guò)這個(gè)算法被找到的解決最優(yōu)化問(wèn)題的方法是能夠保證的。另一方面，這個(gè)新的算法建立了利用一組群中點(diǎn)的支持向量機(jī)。這里，我們將違反KKT條件的樣本指作間隙誤差。為了在每次重復(fù)中進(jìn)一步減少二次規(guī)劃問(wèn)題的數(shù)量，僅僅是需要將間隙誤差的群被包括在支持向量機(jī)訓(xùn)練中。剩余的群是通過(guò)在先前的重復(fù)中找到的支持向量來(lái)描述的。此外，他還能通過(guò)一個(gè)大的二次規(guī)劃問(wèn)題在一系列小的二次規(guī)劃附屬問(wèn)題中被解除的【10】來(lái)被證明。如果至少一個(gè)違反KKT條件的樣本被加到先前附屬問(wèn)題的樣本中，那么每一步將會(huì)簡(jiǎn)化所有的目標(biāo)函數(shù)并且支持一個(gè)可施行的遵守所有條件的解決方法。因此，一個(gè)總是加在至少一個(gè)違反樣本的二次規(guī)劃附屬問(wèn)題的結(jié)果將會(huì)被保正會(huì)趨于一致。考慮到這個(gè)結(jié)果，為了確保它在目標(biāo)函數(shù)中的絕對(duì)改進(jìn)以及因此使之集中，則新的計(jì)算要將一個(gè)誤差中心置于僅僅假設(shè)它違反了KKT條件的工作組。否則，在那個(gè)大多數(shù)違反KKT條件的群中的樣本將會(huì)被置于就如它的群所描述的工作組。因?yàn)榇蠖鄶?shù)工作組的樣本誤差群的中心（先前重復(fù)的支持向量必須是誤差群的中心），這個(gè)新的算法被稱(chēng)為誤差中心基準(zhǔn)最優(yōu)化算法（ECO）。ECO的執(zhí)行步驟列在表1中。
Fig.1利用中心基準(zhǔn)最優(yōu)化算法找到兩個(gè)可能的決定邊界。那些點(diǎn)是確定的樣本并且星狀物是不確定的點(diǎn)。群的中心被繪制成一些大點(diǎn)。實(shí)線(xiàn)表示的是決定邊界。在虛線(xiàn)中間的空間是間隙。在（b）中，在包含剩余支持向量的群中的樣本被小框所標(biāo)記。
表1 誤差中心基準(zhǔn)的最優(yōu)化算法的執(zhí)行步驟
給一個(gè)訓(xùn)練組S，將每一個(gè)S的模本看成是一個(gè)群
將工作組S初始化為這這兩個(gè)群的中心
重復(fù)
在S上訓(xùn)練支持向量機(jī)
將S設(shè)置為支持向量
對(duì)于S的每個(gè)群
通過(guò)確認(rèn)間隙誤差，將最近的群分解成兩個(gè)附屬群， 也就是說(shuō)，他們違反了KKT條件。如果誤差群的中心違反了KKT條件，將中點(diǎn)加到S中。否則，將違反KKT條件的最壞點(diǎn)的樣本加到S中。
直到?jīng)]有新的間隙誤差被找到。
S表示通過(guò)決定函數(shù)兩個(gè)模本被分類(lèi)的一個(gè)訓(xùn)練組。
S表示包括在附屬支持訓(xùn)練中的樣本組。
表示中心被定義成的S的第r個(gè)群。
【使用誤差中心基準(zhǔn)最優(yōu)化方式的支持向量機(jī)的快速訓(xùn)練(一)】相關(guān)文章：
關(guān)于行政機(jī)關(guān)法解釋的審查基準(zhǔn)06-03
談加料搗爐機(jī)液壓油泵與油馬達(dá)的使用與維護(hù)05-18
一種汽車(chē)用金鹵燈的快速點(diǎn)亮電路05-18
免費(fèi)畢業(yè)論文--茶葉修剪機(jī)(一)08-11
免費(fèi)盤(pán)磨機(jī)傳動(dòng)裝置(一)05-13
論我國(guó)消費(fèi)環(huán)境的優(yōu)化05-11
一年級(jí)口算訓(xùn)練05-13
自制快速干手器05-11