使用誤差中心基準(zhǔn)最優(yōu)化方式的支持向量機的快速訓(xùn)練(一)

1、使用誤差中心基準(zhǔn)最優(yōu)化方式的支持向量機的快速訓(xùn)練(一)    外文資料譯文使用誤差中心基準(zhǔn)最優(yōu)化方式的支持向量機的快速訓(xùn)練L. Meng,Q. H. Wu。電機工程和電子學(xué)學(xué)院，利物浦大學(xué)，利物浦， L69 3GJ 英國 摘要: 這篇文章為支持向量機 (SVM) 訓(xùn)練提出一個新算法，這個算法是基于由現(xiàn)在的機器引起的誤差中心束來訓(xùn)練一部機器的。從各種不同的訓(xùn)練組合的實驗中展現(xiàn)出新的運算法則刻度的計算時間與訓(xùn)練組合大小幾乎成線性關(guān)系，因此與二次規(guī)劃標(biāo)準(zhǔn)(QP)技術(shù)相比可被提供于更大的訓(xùn)練組合。 keywords: 支持矢量機器, 二次規(guī)畫, 模式分

2、類, 機器了解。 1 引言 在統(tǒng)計學(xué)理論中基于最近的進展，支持向量機 (SVMs) 組成一個勇于式樣分類的學(xué)習(xí)系統(tǒng)的新團體。訓(xùn)練一個支持向量機相當(dāng)于解決一個有著密集矩陣的二次規(guī)劃的問題。二次規(guī)劃標(biāo)準(zhǔn)的解決需要這個矩陣的所有儲存而且他們的效率在于他們的稀疏程度,他向有著大的訓(xùn)練組合設(shè)定的支持向量機訓(xùn)練提出申請。 被 Vapnik 和他的隊被提倡的支持向量機, 是一新的模式分類和非線性回歸技術(shù).(參看【1】,【2】,和【3】)  由于線性分離的問題,一個支持向量機是一個從有最大值的一組反面樣本中分離出一組正面樣本的超平面。雖然簡單直觀, 但是這個最大值的觀點實際上開拓

3、了在統(tǒng)計學(xué)理論中的結(jié)構(gòu)風(fēng)險最小化（SRM）原則【4】. 因此，所了解的機器不僅有最小的經(jīng)驗風(fēng)險還有好的推廣的能力。 對于非線性可分離的問題,在分類超平面被建立之前輸入一個非線性映射 ，而這個分類超平面將訓(xùn)練樣本從輸入空間傳送到比較高維的特征空間。分類超平面是建立在特征空間的。他在輸入空間產(chǎn)生一個非線性決定邊界。這個決定邊界是由在特征空間的處于分類超平面的映射點組成的。非線性映射運用模式可分離定理通過【5】被一致運用.一個復(fù)雜的存在于一個高維非線性空間的模式分類問題比在一個低維空間更有可能是線性分離的。  對于支持向量機, 分類決定函數(shù)的新的樣本被定義為:  指一個

4、分類樣本, 指相符合的特征向量，和b分別指常向量和分類超平面的截距，向量和常量b是最優(yōu)參數(shù)。 w和b的優(yōu)化相當(dāng)于優(yōu)化一個服從于一些線性約束的目標(biāo)函數(shù),。目標(biāo)函數(shù)聯(lián)合支持向量機優(yōu)化是一個凸二次函數(shù)而且因此最佳化問題沒有最大限度的限制。許多變量的二次函數(shù)的優(yōu)化問題在優(yōu)化理論方面被很好理解并且大多數(shù)與之接近的標(biāo)準(zhǔn)能直接應(yīng)用于支持向量機的訓(xùn)練。然而，大多數(shù)二次規(guī)劃標(biāo)準(zhǔn)技術(shù)需要在目標(biāo)函數(shù)里面二次型的全部儲存空間。他們或者僅僅適合一些小問題或者僅僅適合二次型非常稀疏的假設(shè)，也就是說大多數(shù)的二次型元素是零。不幸地是，對于一個支持向量機佳化問題這不事實，問題中二次型方程不僅僅是密集的而且有一個在訓(xùn)練

5、組合中隨著數(shù)據(jù)點二次增長的能力。為了有1000個或者更多樣本的訓(xùn)練任務(wù)，存儲器的需求將會超過百兆字節(jié)因此這是不可能碰到的。這禁止了對于有大的訓(xùn)練組織問題的二次規(guī)劃標(biāo)準(zhǔn)技術(shù)的申請。一個替代方案在需要時每一次會重新計算二次型。但是這變得非常的昂貴因為二次規(guī)劃技術(shù)是重復(fù)的并且在每次的重復(fù)中需要對二次型進行計算。 如此的思路產(chǎn)生了支持矢量機器的一個新的訓(xùn)練算法的設(shè)計。在這篇文章中被推薦的算法是概念性的簡單事情，一般很快而且比標(biāo)準(zhǔn)的二次規(guī)劃技術(shù)有更大規(guī)模的資產(chǎn)。2 在支持向量機訓(xùn)練中的最優(yōu)化問題 給一個訓(xùn)練樣本的，其中是模仿一個輸入樣本所屬于的目標(biāo)響應(yīng)指示,結(jié)合訓(xùn)練一個支持向量機的最

6、佳化問題能被寫成如下：OP1:  限制條件             其中間隙被兩個超平面所限定而且通過來測量，是允許間隙出現(xiàn)誤差的松弛變量，C是一個與有一些間隙誤差的寬大間隙交換的參數(shù)。當(dāng)時，機器被稱為一個固定間隙支持向量機因為所有的訓(xùn)練樣本必須放在邊緣外部，是不允許有劃分誤差的。否則，機器被成為一個可變間隙支持向量機。    通過引入拉格朗日乘子和和拉格朗日函數(shù)因此要對拉格朗日函數(shù)關(guān)于求最小值并且要對拉各朗日函數(shù)關(guān)于的最大值，其中我們

7、有并且OP1的二重形式如下：其中定義為在特征空間中的兩個向量的內(nèi)積并被稱為核函數(shù)。核函數(shù)的使用允許一個支持向量機，沒有以前明確的特征空間的描述，他的運用限制了在特征空間的分類超平面和在那個空間的分類向量這樣的詳細(xì)描述特征向量的計算負(fù)擔(dān)沒有增加。    OP2本質(zhì)上是一個二次規(guī)劃問題因為他有下面的形式：      其中矩陣Q是二次型。對于支持向量機的訓(xùn)練，他被定義為    由【6】和【7】得KarushKuhnTucker(KKT)條件是對一組變量達到最優(yōu)得最優(yōu)化問題得充分必要條件。對于

8、問題OP1運用（KKT）條件，我們知道最優(yōu)解決必須要滿足      和     包含             方程式（9）以及方程式（8）和（10）顯示出只有那些在間隙邊界上的而不是那些處在變化的樣本是符合要求的 。方程（8）表明對于符合等于零的所有樣本必須要被正確的分類并且放在間隙以外。方程（10）表明具有符合的間隙誤差要等于上面的受約束的C。此外，方程（7）顯示非零的松弛變量只有當(dāng)時存在而且所

9、有的間隙誤差都要受到懲罰。3 誤差中心基準(zhǔn)最優(yōu)化   一個二次規(guī)劃問題的大小取決于二次型Q。在支持向量機訓(xùn)練中，矩陣Q的大小是，其中表示訓(xùn)練數(shù)據(jù)點的個數(shù)。如所描述的，有一個為明確存儲Q的標(biāo)準(zhǔn)解決技術(shù)的必要條件，但是在支持向量機訓(xùn)練中禁止運用標(biāo)準(zhǔn)二次規(guī)劃去計算有大量數(shù)據(jù)組的支持向量機的訓(xùn)練。    考慮到這些，通過【8】一個新的支持向量機訓(xùn)練的技術(shù)產(chǎn)生了?；镜南敕ㄊ侨嚎s最初的訓(xùn)練組然后訓(xùn)練一個關(guān)于由最近壓縮群中心所組成的一個工作組的機器。在每次重復(fù)中壓縮通過分離每個將一個支持向量作為它的中心的群為兩個附屬群來進行更新。因為這個新的算法從由群中心所組成的工作組中摘取分類信息，所以被稱為中心基準(zhǔn)最優(yōu)算法。關(guān)于各種訓(xùn)練組的試驗已經(jīng)顯示出采用中心基準(zhǔn)最優(yōu)化方法的訓(xùn)練時間比標(biāo)準(zhǔn)技術(shù)所用的時間要少的多。對于大的訓(xùn)練任務(wù)，中心基準(zhǔn)最優(yōu)化算法能將所用的時間少于用標(biāo)準(zhǔn)技術(shù)所用時間的1/150。    可惜的是，雖然一個最優(yōu)邊界能夠通過中心基準(zhǔn)最優(yōu)化的方法找到，但是產(chǎn)生決定邊界的最優(yōu)化不能對每一次運行有所保證。（參看Fig.1(a)和Fig.1(b)進行比較）。這是因為一個k方式計算法已被運用于分離中心基準(zhǔn)最優(yōu)化方法。這個算法的上升性質(zhì)使他在不同的最優(yōu)化限制方面變