基于DYCORS算法的OVA-SVM參數優化與應用研究

余晨曦,尹彥力

重慶師范大學 數學科學學院,重慶 401331

1 引 言

支持向量機(SVM)是一種常見的二元分類模型,它分為硬間隔SVM、軟間隔SVM、核化SVM等,主要用于模式識別、數據分析、分類問題等領域。由于SVM通常能解決二元分類問題,因此它在解決多元分類問題時需要先將其轉化為二元分類問題,再用SVM進行分類。對于二元分類問題,通常將能使數據完美分成兩部分的分割面稱為超平面,二維空間中的超平面是一條直線,三維空間中的超平面是一個平面。SVM的目標就是尋找一個最優超平面,使得所有數據點都盡可能地遠離此分割平面,從而將一個空間中不同類別的數據完美地分為兩類。

一對多法(One Versus All,簡稱OVA)[1]是最早的基于SVM對多類別進行分類的方法,其思想是將多類別問題轉化為兩類別問題來實現。

OVA-SVM是把支持向量機(SVM)和One Versus All(OVA)方法結合后提出的一個多類別分類判別模型,其性能依賴于模型參數的選擇,其參數包括懲罰參數C、核函數類型k(k,kernel)、RBF核函數參數γ(γ,gamma)、ploy核函數的參數d(d,degree),以及迭代終止參數t等。如何選取最優的參數設置,進一步提升模型性能至關重要。OVA-SVM是目前應用比較多的一種機器學習模型,具有良好的泛化能力,其性能依賴于超參數的選擇。當前較為常見的超參數優化方法有手動調參、網格尋優、隨機尋優、貝葉斯優化方法、基于梯度的優化方法、進化尋優等。

手動調參,即研究者們通過一步步地手動調節超參數來實現對其的優化。研究者們可以判斷如何設置超參數可以獲得更好的模型效果,但這一方法依賴大量的經驗,且人工調節較為耗時。

網格尋優,王興玲等[2]將網格搜索用于向量機核函數的參數確定問題。使用網格尋優,首先需要為每一個超參數構建其各自的模型,再對各個模型的性能進行評析,從而獲得性能最佳的模型和最優超參數。其優點在于該方法中的所有樣本均能得到驗證;其缺點在于當超參數的個數較多時,計算量會直線上升,比較耗時,并且這一方法無法保證能獲得最優的超參數值,也難以保證能獲得全局最優解。

隨機尋優,Droste等[3]對黑盒優化中隨機搜索啟發式算法進行了研究。該方法可以基于時間和計算資源情況,選擇合理的計算次數,并控制組合的數量,在超參數網格的基礎上隨機選擇組合來訓練模型。通常情況下,隨機尋優方法可以分辨哪些超參數對模型性能影響最大,從而優先獲得這些超參數的最優值。與網格尋優相比,該方法能更快地找到最優參數,也能通過較少的迭代次數獲得正確的參數設置;其缺點在于它只適用于低維數據情況,并且只能夠針對單獨的超參數組合模型進行訓練,并評估各自的性能。

貝葉斯優化,Shukla等[4]提出通過貝葉斯優化算法自動設置超參數,走向自主強化學習。該方法通過構造一個函數的后驗分布來工作,它可以在前一模型的基礎上對后一模型的超參數選擇產生影響,在一定程度上解決了模型獨立時,各模型之間失去聯系的問題。隨著觀測次數的增加,后驗分布得到改善,算法更加確定參數空間中哪些是值得探索的區域,哪些是不值得探索的區域。其優點在于該方法通過不斷采樣來推測函數的最大值,但采樣點不多;其缺點在于容易陷入局部最優值的區域內重復采樣,難以找到全局最優解,并且需要進行多次迭代,時間長且成本高。

基于梯度的優化方法,Lu等[5]提出基于梯度下降法的機器學習增強優化方案。該方法應用場景并不廣泛,主要通過梯度下降算法對超參數進行優化。其優點在于梯度下降算法并不高的計算量,使其可以應用于大部分高規模數據集中;其缺點在于由于超參數優化通常是非凸的,并不是一個完全平穩的過程,所以這一方法的應用場景并不廣泛,難以在各場景中找到全局最優解。

進化尋優,嚴盛雄[6]提出了基于進化算法的LCL型濾波器參數優化設計。該算法是一個動態過程,類似于自然進化中不斷變化的環境,它經常被用來尋找其他技術不易求解的近似解。由于優化問題可能太耗時并且計算資源占用很大,因此通常難以找到精確的解決方案,在這種情況下,進化算法通?？梢哉业揭粋€局部最優解。其優點在于可以產生出不受人類偏見影響的解決方案;其缺點在于不能保證找到全局最優解,沒有可靠的算法終止條件和足夠的理論基礎,并且算法復雜度較高,容易造成資源的消耗。

綜上所述,現有的參數優化方法多樣,但普遍還存在以下問題:時間成本較大,內存占用較大,難以解決高維數據情況,難以找到全局最優解?，F有工作表明:OVA-SVM的性能高度依賴其模型參數的選擇,如何選取最優的參數設置,進一步提升模型性能至關重要,而DYCORS算法可以在節約時間成本和內存的前提下,對高維數據問題也能找到全局最優解。故本文針對現有參數優化方法存在的問題,提出針對OVA-SVM模型參數分塊優化的YDYCORS算法,該算法在參數優化過程中,與現有方法相比更高效,使用范圍更廣,更易找到全局最優解。

2 DYCORS算法與參數優化過程設計

2.1 DYCORS算法

DYCORS算法由Regis等[7]提出,算法結合了動態坐標擾動與算法重啟策略,是目前最有效的昂貴“黑箱”函數優化算法之一。對于大部分測試函數,DYCORS 算法最終都能求得目標函數值。大部分高維問題最有效的算法還是DYCORS,它不僅能解決上文中提到的時間成本與內存占用較大的問題,而且也能適用于高維數據的情況,并得到全局最優解。該算法通過動態坐標擾動,每次按照擾動概率(一個單調遞減的函數)對當前最優點的每一維坐標進行擾動,以此獲得一個新的采樣點。本文將該算法應用于OVA-SVM的參數優化問題,以提升OVA-SVM的性能。其中DYCORS算法如表1所示。

表1 DYCORS算法框架

擾動概率φn(對應Step5)是關于迭代次數n0≤n≤Nmax-1的嚴格單調遞減函數,其計算表達式為

由于φn表示概率,所以其函數值在[0,1],并且φ0=1。Step7和Step8是從候選點中選出最有潛力的點作為新的采樣點,通過計算每一個候選點的函數值度量Vev(t)與距離度量Vdm(t)作為其度量標準,函數定義如下:

DYCORS算法可以在減少迭代次數的前提下,對于高維數據問題也能找到全局最優解,故本文擬采用DYCORS算法調節OVA-SVM的懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代終止參數t等,獲得較現有方法更優的參數配置,進一步提升模型性能。

2.2 參數優化過程設計

針對OVA-SVM參數優化時出現的問題,提出優化后的參數調節方法,提升模型性能,本文的主要貢獻包含以下兩個方面:

(1) OVA-SVM模型的性能十分依賴于模型參數的選擇,而該模型需要調節的參數有懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代終止參數t,這些參數中既包含整數又包含連續實數,并且模型本身的訓練時間成本也較高。而運用DYCORS算法進行參數調節可以減少迭代次數,并且對整數和連續實數超參進行優化,因此DYCORS算法是適用于OVA-SVM模型參數優化的方法。

(2) 由于同時調節5個參數計算量較大,可能難以找到全局最優解,因此本文針對OVA-SVM參數優化時出現的問題,在DYCORS算法的基礎上進行參數分塊調節,提出了改進后的YDYCORS算法。該算法先用DYCORS調節對OVA-SVM的性能影響最大的參數:懲罰參數C、核函數類型k、RBF核函數參數γ;再固定最優懲罰參數C、核函數類型k、RBF核函數參數γ,用DYCORS調節剩余參數中影響較大的參數:ploy核函數的參數d與迭代的終止參數t;最后再用DYCORS一起調節已獲得的5個最優參數。先對參數進行分析,再對參數進行分塊調節,可以在避免出現計算量過大的前提下,提升參數優化的效果。

本文中運用DYCORS算法優化參數的主要過程如圖1所示。

圖1 運用DYCORS算法優化參數的主要過程

2.3 OVA-SVM模型的參數影響分析

影響OVA-SVM性能的參數主要有懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代的終止參數t等。

懲罰參數C[11],即對誤差的寬容度,表示對離群點的重視程度。C越大,表示重視程度越高,允許它們被分類錯誤率高;C越小,表示重視程度越低,允許它們被分類錯誤率低。

核函數[12]的引入是為了將高維空間中的內積運算轉化至低維空間,從而解決線性不可分問題。核函數的選取,使得線性不可分的樣本通過映射至更高維的空間中而變得線性可分,并且能解決映射過程中由于樣本維數過高而造成的“維數災難”,在操作過程中也可以忽略低維向高維映射函數的計算,只需計算低維空間中的核函數即可。常見的核函數類型(x,y表示輸入空間的向量)如表2所示。

表2 常見核函數類型

3 基于DYCORS算法的OVA-SVM參數優化

本文涉及的參數主要有懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d、迭代終止參數t。

針對現有超參數優化方法在調節OVA-SVM參數過程中存在的時間成本較大、內存占用較大、難以解決高維數據,且難以找到全局最優解等問題,提出運用DYCORS算法調節OVA-SVM參數的方法。以下將從DYCORS算法對參數C、k、γ、d、t同時調節,并對其參數優化過程進行分析。

3.1 DYCORS同時調節參數C、k、γ、d、t

DYCORS算法與現有的手動調參、網格尋優、隨機尋優、貝葉斯優化方法、基于梯度的優化方法、進化尋優等超參數優化方法相比,可以更高效地完成參數優化,減小內存占用空間,同時能適用于高維數據問題,得到全局最優解,故DYCORS是一種十分適用于OVA-SVM參數優化的方法。

為實現DYCORS算法對OVA-SVM參數的優化,進一步提升OVA-SVM的性能,本節將運用DYCORS算法同時調節懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代的終止參數t。

3.2 YDYCORS算法的參數優化過程

由于同時調節5個參數計算量較大,可能難以獲得全局最優解,因此本節對原有的DYCORS算法進行優化,提出改進后的YDYCORS算法。YDYCORS算法對5個參數進行了分塊,將調參過程分為了以下3個步驟:第一步,固定ploy核函數參數d與迭代終止參數t,用DYCORS同時調節懲罰參數C、核函數類型k、RBF核函數參數γ;第二步,在固定最優懲罰參數C、核函數類型k、RBF核函數參數γ的前提下,用DYCORS同時調節ploy核函數參數d與迭代終止參數t;第三步,用DYCORS同時調節最優懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代終止參數t。

3.2.1 固定參數d、t,DYCORS同時調節參數C、k、γ

據研究表明[8],懲罰參數C、核函數類型k以及RBF核函數參數γ很大程度上影響了OVA-SVM的性能,懲罰參數C通過影響學習機器置信范圍和經驗風險的比例,進而影響OVA-SVM的泛化能力,核函數類型與核函數的參數通過影響樣本被映射到特征空間的復雜程度,進而影響OVA-SVM的性能。因此在提升OVA-SVM模型性能的過程中,懲罰參數C、核函數類型k以及RBF核函數參數γ較其他參數更為重要。故第一步先固定參數d、t,此時d、t的參數值是任意設置的,再運用DYCORS算法先對參數C、k、γ進行調節,具體步驟同上一節。

3.2.2 固定最優參數C、k、γ,DYCORS同時調節參數d、t

第二步選擇多項式核函數作為OVA-SVM的核,因此除懲罰參數C、核函數類型k以及RBF核函數參數γ以外,ploy核函數參數d和迭代終止參數t對OVA-SVM性能的影響較大。因此,固定上一小節得到的最優懲罰參數C、核函數類型k以及RBF核函數參數γ,運用DYCORS算法同時調節ploy核函數參數d和迭代終止參數t,具體步驟同上一節。

3.2.3 DYCORS同時調節最優參數C、k、γ、d、t

在經過前兩步的參數調節后,OVA- SVM參數優化的效果得到了進一步提升。為了使效果達到最佳,本小節利用參數之間的相互依賴性,在第三個步驟中用前兩步獲得的最優參數為初始參數值,同時調節最優懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代終止參數t,具體步驟同上一節。

4 實驗驗證與結果分析

4.1 數據集

MNIST數據集[9]來自美國國家標準與技術研究所, National Institute of Standards and Technology (NIST),是NIST數據庫的一個子集,也是機器學習中評估模型性能時常用的數據集。MNIST數據集分為訓練集與測試集,訓練圖片一共有60 000張,可采用學習方法訓練出相應的模型,測試圖片一共有10 000張,可用于評估訓練模型的性能。

IRIS數據集[10],也稱鳶尾花卉數據集,其中共包含150個樣本數據,該數據集是機器學習中常見的數據集,共分為以下3類:山鳶尾(Iris Setosa)、雜色鳶尾(Iris Versicolour)、維吉尼亞鳶尾(Iris Virginica)。該數據集以鳶尾花的特征作為數據來源,包含4個特征:花瓣長度、花瓣寬度、花萼長度、花萼寬度。IRIS數據集是一類多重變量分析的數據集,也是在數據分類中十分常用的測試集和訓練集。

4.2 評估指標

本文實驗的評估指標[9]主要是準確率,為闡述準確率(Acc)的含義,先介紹以下兩個概念:

TP(True Positives):表示模型將正實例預測為正實例的數據個數,用NTP表示;TN(True Negatives):表示模型將負實例預測為負實例的數據個數,用NTN表示;準確率指標的公式:

4.3 實驗環境

本文實驗在具有64 GB內存和NVIDIA GeForce GTX 1050 Ti GPU和Intel(R) Core(TM) i7-8750H CPU的個人工作站上進行。

4.4 實驗結果

針對現有方法存在的4個問題,設計如下實驗:第一部分,手動調節OVA-SVM參數,獲得在該參數設置下的模型準確率;第二部分,運用DYCORS算法同時調節參數C、k、γ、d、t,獲得在該參數設置下的模型準確率;第三部分,首先固定參數d、t,運用DYCORS算法調節參數C、k、γ,然后固定最優參數C、k、γ,調節參數d、t,最后同時調節最優參數C、k、γ、d、t,獲得在該參數設置下的模型準確率。本實驗針對MNIST和IRIS兩個數據集,將DYCORS算法運用于OVA-SVM的參數優化中,其中先確定各參數的取值范圍:C的取值范圍為[0, 10],k的取值范圍為[linear, poly, rbf, sigmoid],γ的取值范圍為[0, 10],d的取值范圍為[0, 5],t的取值范圍為[0.000 1,0.001],經過以上實驗后可得如表3、表4中的結果。

表3 在MNIST數據集上的實驗結果(60%訓練,40%測試)

表4 在IRIS數據集上的實驗結果(60%訓練,40%測試)

如表3在MNIST數據集上的實驗結果所示:運用DYCORS算法調節OVA-SVM模型的參數時,由于同時調節5個參數工作量較大,得到的模型準確率為98.19%,但在運用YDYCORS算法調節OVA-SVM模型的參數后,模型準確率達到了98.61%,能得到更好的效果。

由表4在IRIS數據集上的實驗結果可知:在運用DYCORS算法和YDYCORS算法調節OVA-SVM的參數時,都能得到較高的準確率與良好的模型效果。為了更清晰地反映模型準確率在不同數據集與不同調參方法下的具體情況,本文再將上述兩個數據集的實驗結果進行對比,如表5所示。

表5 兩個數據集上的實驗結果對比

通過MNIST和IRIS兩個數據集上的實驗結果對比可以發現:由于數據集的選擇不同,呈現的模型準確率也不同,明顯在IRIS數據集上的模型準確率更高,但在MNIST數據集上,YDYCORS算法的優勢體現得更明顯。運用DYCORS算法直接同時優化5個參數,計算量較大,可能無法斷定是否能得到較高的模型準確率,但在運用YDYCORS算法對OVA-SVM的參數進行分塊調節后,能得到與手動調參和直接用DYCORS同時調節5個參數相比更高的模型準確率,從而也能進一步提升其模型性能。綜上實驗,可以進一步說明本文提出的YDYCORS算法可以在一定程度上解決現有超參數優化方法還存在的問題,因此本文對OVA-SVM參數的優化也取得了比較理想的效果。

5 結論及展望

5.1 結 論

本文針對現有的超參數優化方法存在的時間成本較大,內存占用較大,難以解決高維數據,難以找到全局最優解等問題,運用DYCORS算法對模型影響較大的懲罰參數C、核函數類型k、RBF核函數參數γ、ploy核函數參數d以及迭代終止參數t這5個參數進行調節,提出將參數進行分塊調節的YDYCORS算法:先用DYCORS調節對OVA-SVM的性能影響最大的參數:C、k、γ;再固定最優參數C、k、γ,用DYCORS調節剩余參數中影響較大的參數d和t;最后用DYCORS一起調節已獲得的5個最優參數。先對參數進行分析,再對參數進行分塊調節,可以在避免出現計算量過大的前提下,提升參數優化的效果。

通過MNIST和IRIS兩個數據集上的實驗結果對比可以發現:運用DYCORS算法直接同時優化5個參數,由于計算量較大,可能無法斷定是否能得到較高的模型準確率,但在運用YDYCORS算法對OVA-SVM的參數進行分塊調節后,能得到與手動調參和直接用DYCORS同時調節5個參數相比更高的模型準確率,從而也能進一步提升模型性能,取得了較佳的模型效果。

5.2 展 望

雖然本文提出的方法可以在一定程度上解決現有超參數優化方法存在的問題:如時間成本較大、內存占用較大、難以解決高維數據問題、難以找到全局最優解,但該方法能否解決超參數優化中可能存在的其他問題還有待研究。另外,本文只對懲罰參數C、核函數類型k、 RBF核函數參數γ、ploy核函數參數d和迭代終止參數t進行優化,而如何更全面地優化OVA-SVM的參數還值得未來進一步探索。同時,本文提出的YDYCORS算法只對5個參數進行了一種形式的分塊,其余的分塊形式能否取得更佳的模型效果還值得研究。