使用誤差中心基準最優化方式的支持向量機的快速訓練(一)
外文資料譯文
使用誤差中心基準最優化方式的支持向量機的
快速訓練
L. Meng,Q. H. Wu。
電機工程和電子學學院，利物浦大學，利物浦， L69 3GJ 英國
摘要: 這篇文章為支持向量機 (SVM) 訓練提出一個新算法，這個算法是基于由現在的機器引起的誤差中心束來訓練一部機器的。從各種不同的訓練組合的實驗中展現出新的運算法則刻度的計算時間與訓練組合大小幾乎成線性關系，因此與二次規劃標準(QP)技術相比可被提供于更大的訓練組合。
keywords: 支持矢量機器, 二次規畫, 模式分類, 機器了解。
1 引言
在統計學理論中基于最近的進展，支持向量機 (SVMs) 組成一個勇于式樣分類的學習系統的新團體。訓練一個支持向量機相當于解決一個有著密集矩陣的二次規劃的問題。二次規劃標準的解決需要這個矩陣的所有儲存而且他們的效率在于他們的稀疏程度,他向有著大的訓練組合設定的支持向量機訓練提出申請。
被 Vapnik 和他的隊被提倡的支持向量機, 是一新的模式分類和非線性回歸技術.(參看【1】,【2】,和【3】)
由于線性分離的問題,一個支持向量機是一個從有最大值的一組反面樣本中分離出一組正面樣本的超平面。雖然簡單直觀, 但是這個最大值的觀點實際上開拓了在統計學理論中的結構風險最小化（SRM）原則【4】. 因此，所了解的機器不僅有最小的經驗風險還有好的推廣的能力。
對于非線性可分離的問題,在分類超平面被建立之前輸入一個非線性映射 ，而這個分類超平面將訓練樣本從輸入空間傳送到比較高維的特征空間。分類超平面是建立在特征空間的。他在輸入空間產生一個非線性決定邊界。這個決定邊界是由在特征空間的處于分類超平面的映射點組成的。非線性映射運用模式可分離定理通過【5】被一致運用.一個復雜的存在于一個高維非線性空間的模式分類問題比在一個低維空間更有可能是線性分離的。
對于支持向量機, 分類決定函數的新的樣本被定義為:
指一個分類樣本, 指相符合的特征向量，和b分別指常向量和分類超平面的截距，向量和常量b是最優參數。
w和b的優化相當于優化一個服從于一些線性約束的目標函數,。目標函數聯合支持向量機優化是一個凸二次函數而且因此最佳化問題沒有最大限度的限制。許多變量的二次函數的優化問題在優化理論方面被很好理解并且大多數與之接近的標準能直接應用于支持向量機的訓練。然而，大多數二次規劃標準技術需要在目標函數里面二次型的全部儲存空間。他們或者僅僅適合一些小問題或者僅僅適合二次型非常稀疏的假設，也就是說大多數的二次型元素是零。不幸地是，對于一個支持向量機佳化問題這不事實，問題中二次型方程不僅僅是密集的而且有一個在訓練組合中隨著數據點二次增長的能力。為了有1000個或者更多樣本的訓練任務，存儲器的需求將會超過百兆字節因此這是不可能碰到的。這禁止了對于有大的訓練組織問題的二次規劃標準技術的申請。一個替代方案在需要時每一次會重新計算二次型。但是這變得非常的昂貴因為二次規劃技術是重復的并且在每次的重復中需要對二次型進行計算。
如此的思路產生了支持矢量機器的一個新的訓練算法的設計。在這篇文章中被推薦的算法是概念性的簡單事情，一般很快而且比標準的二次規劃技術有更大規模的資產。
2 在支持向量機訓練中的最優化問題
給一個訓練樣本的，其中是模仿一個輸入樣本所屬于的目標響應指示,結合訓練一個支持向量機的最佳化問題能被寫成如下：
OP1:
限制條件
其中間隙被兩個超平面所限定而且通過來測量，是允許間隙出現誤差的松弛變量，C是一個與有一些間隙誤差的寬大間隙交換的參數。當時，機器被稱為一個固定間隙支持向量機因為所有的訓練樣本必須放在邊緣外部，是不允許有劃分誤差的。否則，機器被成為一個可變間隙支持向量機。
通過引入拉格朗日乘子和和拉格朗日函數
因此要對拉格朗日函數關于求最小值并且要對拉各朗日函數關于的最大值，其中我們有
并且OP1的二重形式如下：
其中定義為在特征空間中的兩個向量的內積并被稱為核函數。核函數的使用允許一個支持向量機，沒有以前明確的特征空間的描述，他的運用限制了在特征空間的分類超平面和在那個空間的分類向量這樣的詳細描述特征向量的計算負擔沒有增加。
OP2本質上是一個二次規劃問題因為他有下面的形式：
其中矩陣Q是二次型。對于支持向量機的訓練，他被定義為
由【6】和【7】得Karush―Kuhn―Tucker(KKT)條件是對一組變量達到最優得最優化問題得充分必要條件。對于問題OP1運用（KKT）條件，我們知道最優解決必須要滿足
和
包含
方程式（9）以及方程式（8）和（10）顯示出只有那些在間隙邊界上的而不是那些處在變化的樣本是符合要求的 。方程（8）表明對于符合等于零的所有樣本必須要被正確的分類并且放在間隙以外。方程（10）表明具有符合的間隙誤差要等于上面的受約束的C。此外，方程（7）顯示非零的松弛變量只有當時存在而且所有的間隙誤差都要受到懲罰。
3 誤差中心基準最優化
一個二次規劃問題的大小取決于二次型Q。在支持向量機訓練中，矩陣Q的大小是，其中表示訓練數據點的個數。如所描述的，有一個為明確存儲Q的標準解決技術的必要條件，但是在支持向量機訓練中禁止運用標準二次規劃去計算有大量數據組的支持向量機的訓練。
考慮到這些，通過【8】一個新的支持向量機訓練的技術產生了。基本的想法是去壓縮最初的訓練組然后訓練一個關于由最近壓縮群中心所組成的一個工作組的機器。在每次重復中壓縮通過分離每個將一個支持向量作為它的中心的群為兩個附屬群來進行更新。因為這個新的算法從由群中心所組成的工作組中摘取分類信息，所以被稱為中心基準最優算法。關于各種訓練組的試驗已經顯示出采用中心基準最優化方法的訓練時間比標準技術所用的時間要少的多。對于大的訓練任務，中心基準最優化算法能將所用的時間少于用標準技術所用時間的1/150。
可惜的是，雖然一個最優邊界能夠通過中心基準最優化的方法找到，但是產生決定邊界的最優化不能對每一次運行有所保證。（參看Fig.1(a)和Fig.1(b)進行比較）。這是因為一個k方式計算法已被運用于分離中心基準最優化方法。這個算法的上升性質使他在不同的最優化限制方面變得容易捕捉到。不管產生的決定邊界有不精確和多樣性，中心基準的快速性展現了中心基準算法的巨大潛力,它用于有大量訓練組的支持向量機最優化問題的快速解決。
通過觀察Fig.1(b),失去支持向量的狀態或者在內或者在間隙的誤差的一邊。而且因為他們沒有被包括在最后的訓練中，他們的匹配是零。KKT條件表明結合零的樣本必須能被正確的分類并且要放在間隙的外測。通過這個得到啟發，已經對中心基準最優化進行了修改。現在，通過分離那些符合KKT條件的樣本，每一個群被分離成為了兩個附屬群并且這樣被放在了外部或者是放在來自那些違反KKT條件的當前間隙和放在內部或者是放在當前間隙的誤差的一邊。一方面，如果在最初的至少一個群違反KKT條件的訓練組有一些樣本，他們將被分離。另一方面，程序要反復到在最初的違反KKT條件的訓練組沒有樣本為止。因為KKT條件是解決最優化問題的必要充分條件，所以通過這個算法被找到的解決最優化問題的方法是能夠保證的。另一方面，這個新的算法建立了利用一組群中點的支持向量機。這里，我們將違反KKT條件的樣本指作間隙誤差。為了在每次重復中進一步減少二次規劃問題的數量，僅僅是需要將間隙誤差的群被包括在支持向量機訓練中。剩余的群是通過在先前的重復中找到的支持向量來描述的。此外，他還能通過一個大的二次規劃問題在一系列小的二次規劃附屬問題中被解除的【10】來被證明。如果至少一個違反KKT條件的樣本被加到先前附屬問題的樣本中，那么每一步將會簡化所有的目標函數并且支持一個可施行的遵守所有條件的解決方法。因此，一個總是加在至少一個違反樣本的二次規劃附屬問題的結果將會被保正會趨于一致。考慮到這個結果，為了確保它在目標函數中的絕對改進以及因此使之集中，則新的計算要將一個誤差中心置于僅僅假設它違反了KKT條件的工作組。否則，在那個大多數違反KKT條件的群中的樣本將會被置于就如它的群所描述的工作組。因為大多數工作組的樣本誤差群的中心（先前重復的支持向量必須是誤差群的中心），這個新的算法被稱為誤差中心基準最優化算法（ECO）。ECO的執行步驟列在表1中。
Fig.1利用中心基準最優化算法找到兩個可能的決定邊界。那些點是確定的樣本并且星狀物是不確定的點。群的中心被繪制成一些大點。實線表示的是決定邊界。在虛線中間的空間是間隙。在（b）中，在包含剩余支持向量的群中的樣本被小框所標記。
表1 誤差中心基準的最優化算法的執行步驟
給一個訓練組S，將每一個S的模本看成是一個群
將工作組S初始化為這這兩個群的中心
重復
在S上訓練支持向量機
將S設置為支持向量
對于S的每個群
通過確認間隙誤差，將最近的群分解成兩個附屬群， 也就是說，他們違反了KKT條件。如果誤差群的中心違反了KKT條件，將中點加到S中。否則，將違反KKT條件的最壞點的樣本加到S中。
直到沒有新的間隙誤差被找到。
S表示通過決定函數兩個模本被分類的一個訓練組。
S表示包括在附屬支持訓練中的樣本組。
表示中心被定義成的S的第r個群。
【使用誤差中心基準最優化方式的支持向量機的快速訓練(一)】相關文章：
基于子空間和模糊支持向量機的說話人識別03-07
快速消費品配送中心選擇優化的模型與算法03-25
配送中心管理優化探討03-20
金融對產業結構調整和優化的支持03-22
挖掘機的選型和使用03-07
有限狀態機的VHDL優化設計03-07
基于大氣物理模型的快速視覺優化去霧算法03-17
物流配送中心優化方案探討03-07