正當式svm總則化路徑算法

正當式svm總則化路徑算法

默認路徑算法（raguardimport）是路徑跟蹤理論。SVMpath算法跟蹤Karush-Kuhn-Tucker(KKT)條件隨正則化參數(shù)變化的情況,利用hinge損失函數(shù)的分段線性建立活動集,并根據(jù)正則化參數(shù)與活動集之間的關(guān)系確定路徑拐點,求解各拐點處Lagrange乘子向量,建立完整的正則化路徑.該算法為建立SVM正則化路徑提供了完整的框架,已被推廣到各種類型SVM,如平方損失函數(shù)SVM本文在已有SVM正則化路徑算法的基礎(chǔ)上,結(jié)合正定矩陣分解方法1研究背景本節(jié)將介紹SVM正則化表示形式和建立SVM正則化路徑的主要步驟.1.1svm是校正的表達令!表示輸入空間,通常有!ue020R其中,其中,ξ為樣本空間R如圖1所示.優(yōu)化問題(1)的對偶形式為其中,1.2svm的完全解路徑正則化路徑算法是基于活動集(activeset)與正則化參數(shù)λ之間的相互影響,利用Lagrange乘子α與正則化參數(shù)λ的分段線性關(guān)系,求解正則化參數(shù)λ從+∞到0變化過程中所有SVM,從而得到SVM的完全解路徑.首先建立優(yōu)化問題式(1)的Lagrange函數(shù),然后對各目標變量求偏導(dǎo),再結(jié)合KKT條件,綜合分析可得:對于任意i(1≤i≤n),當y其中,集合與集合事件1.初始事件:集合事件2.事件3.事件4.若用l表示事件發(fā)生的次數(shù),可將第l次事件發(fā)生后上述各變量分別表示為此外,由于總是滿足設(shè)集合由式(4)(5)得到m其中:由式(7)并結(jié)合δ2基于面向虛設(shè)矩陣的算法PDSVMP算法主要采用2種新策略:首先,將方程組式(6)轉(zhuǎn)換為系數(shù)矩陣為正定矩陣的線性方程組,該方法可以解決現(xiàn)有算法適用范圍受限問題,并可以利用Cholesky分解提高算法效率;然后,在上述工作基礎(chǔ)上,根據(jù)活動集變化情況確定正則化參數(shù)增量,并由此計算下一事件發(fā)生時正則化參數(shù)值λ2.1現(xiàn)記矩陣擬合Hastie等人首先,由式(3)和式(4)及δ其矩陣形式為同時,式(5)的矩陣形式為現(xiàn)記即由此可得:并結(jié)合式(9)可得等式:綜上所述,方程組式(6)可重新寫為=(其中,0表示m由于K由矩陣K然后,利用式(12)求出各變量:進而可以求得δ2.2正則化參數(shù)求解下一拐點處正則化參數(shù)λ求得λ針對發(fā)生事件類型的不同,本文提出如下3種方法計算正則化參數(shù)增量.1)事件1由于事件1為初始化事件,因此正則化參數(shù)λ取初始值λ2)事件2事件2是指樣本點從活動集此時,若b3)事件3或事件4這兩類事件都是樣本點進入活動集可得,對任意i(1≤i≤n):λζ其中,令綜上所述,正則化參數(shù)增量δ因此,下一事件發(fā)生時正則化參數(shù)值為進一步,活動集$中樣本點對應(yīng)的Lagrange乘子為2.3正則化路徑建立過程首先,PDSVMP算法中初始化是給定正則化參數(shù)λ的最大值λ算法1.初始化過程.算法2.正則化路徑建立過程PDSVMP算法1中,n第l+1個事件發(fā)生時,主要計算負擔為求解m3實驗環(huán)境及實驗平臺本節(jié)設(shè)計實驗來驗證PDSVMP算法的可行性和計算效率.實驗數(shù)據(jù)包括8個標準數(shù)據(jù)集和1個實例數(shù)據(jù)本文的實驗環(huán)境是DELL,IntelCore2QuadQ82002.33GHzCPU,4.0GB內(nèi)存,實驗平臺為R2.8.1.3.1svmpah算法正則化路徑反映Lagrange乘子α與正則化參數(shù)λ的分段線性關(guān)系.若樣本個數(shù)為n,則正則化路徑上有n條折線(對應(yīng)于n個Lagrange乘子{α首先,通過在數(shù)據(jù)集上生成分段線性正則化路徑α由于SVMpath算法只能處理系數(shù)A滿秩的情況,在A不滿秩時可能得不到正確結(jié)果,該算法在處理這種實例時有可能得到錯誤的正則化路徑.現(xiàn)構(gòu)造實例數(shù)據(jù)3.2優(yōu)化正則化路徑下面實驗對比PDSVMP算法與ISVMP算法在UCI標準數(shù)據(jù)集上的運行時間,以驗證PDSVMP算法的計算效率.為降低實驗的隨機誤差,從數(shù)據(jù)集中隨機選取部分樣本作為訓(xùn)練數(shù)據(jù),如表1所示,每個數(shù)據(jù)集均重復(fù)選取10次,然后計算平均運行時間.該實驗選擇高斯徑向基核(RBF)并設(shè)置核參數(shù)γ=1.該實驗中,正則化參數(shù)λ的最大值設(shè)為λISVMP算法應(yīng)用奇異值分解方法保證系數(shù)矩陣A不滿秩時仍能得到正確正則化路徑,且通過求解一個線性規(guī)劃問題以確定λ4pdsvmp算法本文提出基于正定矩陣的SVM正則化路徑求解算法PDSVMP.正定矩陣線性方程組求解方法應(yīng)用于SVM正則化路徑的求解,一方面通過Cholesky分解提高了求解SVM的計算效率,另一方面降低了求解正則化參數(shù)的計算開銷.更為重要的是,基于正定矩陣的SVM正則化路徑算法可適用于包含輸入向量線性相關(guān)的樣本集,拓展了SVM正則化路徑算法