支持向量機序貫最小優(yōu)化訓練速度的改進

支持向量機序貫最小優(yōu)化訓練速度的改進

0工作集固定方法支持向量機（svm支持向量機）。給定輸入空間的l個訓練樣本(x式中:e為全1向量;C為一個重要的參數(shù),從本質(zhì)上說是平衡經(jīng)驗風險和置信風險的,C越大置信風險越大,經(jīng)驗風險越小,并且所有的α都限制在邊長為C的正方形范圍內(nèi);Q為l×l的Hessian半正定矩陣,Q早期研究中,Vapnik提出了Chunking算法;Osuna等人提出了工作集固定的分解算法;Joachim將Zoutendijk的可行方向法、Shrinking法、KernelCache技術(shù)相結(jié)合實現(xiàn)了SVMLight軟件;Platt的SMO算法本文在分析SMO算法的基礎(chǔ)上,針對分類向量集過于龐大、算法后期工作集的選取策略、停機條件的設(shè)置等方面的問題進行了適當?shù)母倪M。通過對著名數(shù)據(jù)集的對比實驗,發(fā)現(xiàn)此項改進在縮短測試時間的基礎(chǔ)上,算法的精度沒有很大的變化,仍能達到滿意的效果。1lagrange乘子具體作法SMO是將大的QP問題分解成最小規(guī)模的QP問題,算法在固定其他參數(shù)的條件下,每次僅選擇兩個Lagrange乘子α具體做法是首先遍歷非邊界樣本選擇一個違反KKT條件的樣本αSMO算法在選擇兩個乘子配對優(yōu)化時,耗時主要是花費在優(yōu)化選擇和迭代次數(shù)上。SMO除了在處理線性SVM和具有稀疏二進制的數(shù)據(jù)時訓練速度較快之外,對一般數(shù)據(jù)是非常慢的。2種新的改進一方面,對于凸優(yōu)化問題,在實現(xiàn)時需要適當?shù)耐Ｖ箺l件來結(jié)束優(yōu)化過程,停止條件可以是:(1)目標函數(shù)W(α)的增長率,即W(α(2)原問題的KKT條件,對于凸優(yōu)化來說它是收斂的充要條件,由于KKT條件本身是比較苛刻的,所以也可以設(shè)定一個容忍值,即所有樣本在容忍值范圍內(nèi)滿足KKT條件則認為訓練可以停止;(3)可行間隙,即原目標函數(shù)值O(w,b)和對偶目標函數(shù)值W(α)的間隙,凸二次優(yōu)化問題的間隙是零。當(O(w,b)-W(α))O(w,b)小于某個容忍值就可以停止。恰當?shù)耐Ｖ箺l件可以使得算法提早結(jié)束訓練,從而節(jié)省訓練的時間。其實,從本質(zhì)上來說可以推廣到尋找經(jīng)驗風險和置信風險之間的平衡。另一方面,對于算法所依賴的物理條件而言,優(yōu)化可以從以下方面:(1)緩存的恰當運用,能用緩存的地方盡量用緩存,這樣可以減少重復(fù)計算的次數(shù),提高運行效率,但會增加算法的空間復(fù)雜度。(2)關(guān)注可以并行計算的地方,將其分成若干部分并行計算,從部分最優(yōu)尋找到全局最優(yōu)。2.1跳不穩(wěn)定區(qū)域的選擇在優(yōu)化過程中,考慮到只有部分樣本會成為支持向量,可以將明顯不是支持向量的樣本跳過來刪減大規(guī)模訓練集,從而減少樣本訓練的時間,提高訓練效率。但修剪的精度不容易掌握,對于邊界支持向量較多時,可能修剪的過于粗糙,對于較少時,可能誤刪了部分支持向量。因此可以計算樣本x到分類超平面H的距離d,若due08dξ,則保留此樣本,否則就跳過。ξ是一個可以調(diào)節(jié)的量,用它來控制刪減的力度。具體到算法中:(1)當樣本的Lagrange乘子兩次小于ξ時,下次循環(huán)選擇乘子優(yōu)化跳過此樣本而選擇其他樣本進行優(yōu)化;(2)當樣本的Lagrange乘子兩次趨近于C-ξ時,下次循環(huán)選擇乘子優(yōu)化跳過此樣本而選擇其他樣本進行優(yōu)化。也就是說最優(yōu)分類面大致確定下來后,由Lagrange乘子的大小直接判斷是否跳過該樣本。這樣操作簡便易行,它跳過了已經(jīng)是正確分類的樣本和分內(nèi)面之間的樣本,這樣大幅度的消減對分類沒有太大影響的待訓練的樣本個數(shù),從而提高訓練速度。2.2能配對成功乘子的循環(huán)在SMO算法中,程序經(jīng)過兩層循環(huán)不斷的尋找可以優(yōu)化配對的一些Lagrange乘子。從開始的大量需要優(yōu)化Lagrange乘子迅速下降到只有很少部分的Lagrange乘子能配對優(yōu)化。在少部分能配對成功的乘子中,由于程序的選取機制不變,導致內(nèi)外層循環(huán)在這幾對乘子之間來回優(yōu)化,這無疑增加了循環(huán)次數(shù),耗費了訓練時間。因此,在保證分類精度的前提下,可以松弛這個條件,提前結(jié)束循環(huán)以免浪費尋優(yōu)時間。雖然并沒有找出全部不滿足KKT條件的乘子以優(yōu)化所有的樣本,但改進的算法在后期尋優(yōu)策略上與快速找出最優(yōu)分類面目標是一致的。具體的方法是在程序的訓練過程中,置數(shù)據(jù)改變量numChanged一個閾值,當算法小于這個值時,就可以提前結(jié)束循環(huán),節(jié)省配對優(yōu)化的時間。在實驗中發(fā)現(xiàn),這樣的策略對于訓練的精度并沒有減少太多,但訓練的速度卻有著很大提高。2.3跳過部分非負局部約束的特點基于松弛KKT條件的思想,發(fā)現(xiàn)在SMO算法中,由于每次計算一對Lagrange乘子必然要涉及到w值的變化,w值的變化反應(yīng)到分類圖中是最優(yōu)分類面的微調(diào)。如果當w的值在變化小于一個閾值時,松弛不滿足KKT條件的α,使得很少一部分違反KKT條件的數(shù)據(jù)樣本在下次選擇優(yōu)化時,被判為無需優(yōu)化的樣本,從而跳過訓練的過程,這樣就可以加快訓練速度,節(jié)省訓練時間。其實這些數(shù)據(jù)樣本對于尋找最優(yōu)分類面是沒有太大進展的,它們所對應(yīng)的向量是在最優(yōu)分類面附近的樣本向量。具體做法是在程序中,當Δw小于某個閾值時,擴大源程序中tol變量的值,將tol的值乘以一個很小的倍數(shù)來收縮工作集,收縮部分需優(yōu)化的Lagrange乘子α,這樣處理后使得有部分的乘子在下次選擇優(yōu)化時被跳過,從而節(jié)省優(yōu)化時間。實驗結(jié)果表明,在處理數(shù)據(jù)時,算法也能快速定位分類面,且分類精度沒有顯著的變化,特別是數(shù)據(jù)集大的數(shù)據(jù),效果很好。3segmen集和saellity集在SMO源程序(VC++6.0)的基礎(chǔ)上進行修改,并選取了UCI兩個數(shù)據(jù)集Segment集和Satellite集進行測試,實驗的CPU為i3-380處理器,內(nèi)存為2GB。選用的核函數(shù)為RBF徑向基函數(shù),Segment集有2200個訓練樣本和110個測試樣本,類別有7類,σ調(diào)為10,C調(diào)為1.0。Satellite集有4435個訓練樣本和2000個測試樣本,類別有6類,σ調(diào)為15,C調(diào)為1。實驗中采用了標準SMO,去掉向量的SMO(RV-SMO),改變numchanged的SMO(CN-SMO)閾值取3,收縮工作集的SMO(SW-SMO)。分別進行訓練和測試。如表1所示。從表中可以清楚的發(fā)現(xiàn),文章中提出的策略相比標準SMO的用時有很大的縮減,且運行的精度并沒用衰減多少,對于規(guī)模較大的數(shù)據(jù)集更是明顯?？梢妼τ谔^部分向量、結(jié)束不必要的循環(huán)、松弛KKT條件的思路是可行的,能縮小搜索空間,提高SMO的性能。4弛軟件的策略針對標準SMO算法處理大規(guī)模數(shù)據(jù)集的耗時過長的問題,運用刪減部分支持向量,提