最小二乘損失在多視角學習中的應用

劉云瑞，周水生

(西安電子科技大學 數學與統計學院，陜西 西安 710126)

近年來，人們收集和存儲數據的能力得到了極大的提高。在科學研究和社會生活的各個領域，海量表現形式復雜的數據涌現。針對同一對象從不同途徑或不同層面獲得的特征數據被稱為多視角數據，其呈現出多態性、多源性、多描述性和高維異構性等特點。多視角數據廣泛存在于生物醫學研究[1-2]、工業生產實踐[3-4]和無監督學習等領域[5-6]。

多視角數據不僅可以從不同領域、不同特征提取獲得，而且也可以通過隨機劃分、主成分分析、降維等方法人工生成[7-8]。不同視角間既具有內在聯系，又存在差異，因此需要一種新的學習方法對這些數據和特征進行加工處理，從而充分合理地利用多視角數據中的信息。這就誕生了一個新的領域——多視角學習(Multi-View Learning，MVL)。經典的支持向量機(Support Vector Machines，SVM)屬于單視角學習范疇，可以很好地解決小樣本分類、回歸等學習問題，是一種基于結構風險最小化原則和最大間隔原理的機器學習方法。但是，支持向量機所用到的數據往往是單個視角的數據，并不能很好地發掘多視角數據之間的結構特性。目前圍繞支持向量機衍生出來的多視角學習算法越來越多，較為流行的有以下幾種算法：基于學習使用特權信息框架(Learning Using Privileged Information，LUPI)，是通過將特權信息確定的非負校正函數替換標準支持向量機中的松弛變量得到的SVM+模型[9-12]；將多視角學習理論應用于最大熵判別算法(Maximum Entropy Discrimination，MED)，得到多視角最大交叉熵模型(Multi-View Maximum Entropy Discrimination，MVMED)[13-14]；將正則化最小二乘孿生支持向量機(Regularized Least Squares Twin SVM，RLSTSVM)與多視角學習理論結合，可以得到正則化多視角最小二乘孿生支持向量機(Regularized Multi-view Least Squares Twin SVM，RMvLSTSVM)[15]。典型相關性分析(Canonical Correlation Analysis，CCA)和核典型相關性分析(Kernel Canonical Correlation Analysis，KCCA)[16-17]是兩種常用的子空間學習算法，利用映射后的基向量之間的相關關系來反映原始變量之間的相關性，得到多視角數據的共享子空間。FARQUHAR等[18]利用樣本的多個特征集和標簽信息，提出將KCCA和SVM相結合的SVM-2K多視角學習模型，由此也產生了許多新型的多視角子空間學習算法[19-20]。

在機器學習研究中，許多學者基于不同的損失函數提出了不同的支持向量機模型。最經典的就是基于合頁(hinge)損失函數提出的支持向量機模型，往往通過MATLAB求解二次規劃問題，算法復雜度較高。基于最小二乘損失，文獻[21-22]提出的最小二乘支持向量機(Least Squares SVM，LSSVM)模型，只需要求解線性方程組即可解決問題，降低了模型的計算復雜度，取得了廣泛的應用。多視角學習模型SVM-2K若通過對偶問題的二次規劃形式求得最優解，則不僅效率低下，而且精度較低。受傳統最小二乘支持向量機模型改進思路的啟發，筆者首先提出了對SVM-2K模型改進的LSSVM-2K模型，只需要求解一個線性方程組即可快速獲得良好的分類結果。同時，針對SVM-2K模型中不同的損失函數，可以構建另外兩種部分應用最小二乘思想的LSSVM-2KI和LSSVM-2KII學習算法，并輔助驗證LSSVM-2K模型的優劣性。實驗結果表明，LSSVM-2K模型在處理多視角數據分類問題上具有良好的分類性能，尤其是大大縮減了訓練時間，在較大規模的數據集上相比于SVM-2K模型訓練時間縮減了約90%。LSSVM-2KI具有比LSSVM-2K模型更好的分類效果，訓練時間比SVM-2K模型的短，但比LSSVM-2K模型的長一些。LSSVM-2KII在分類精度和訓練時間上均介于兩種模型之間。

1 相關算法

先簡述LSSVM和SVM-2K模型及算法，并在下一節提出引用了最小二乘思想的LSSVM-2K、LSSVM-2KI和LSSVM-2KII模型。

1.1 最小二乘支持向量機

由于引入了hinge損失，使得支持向量機成為一個非光滑的凸優化問題，往往要通過求解帶約束的對偶問題得到其最優解。顯然，對于非光滑的凸優化問題的求解比較復雜。在支持向量機中引入光滑的最小二乘損失，可以構造如下所示光滑的凸優化問題：

(1)

其中，lleastsquares(w，b)=(1-yi(wTφ(xi)+b))2，是最小二乘損失；φ是將樣本數據xi從低維映射到高維空間的特征映射；xi和yi分別是經典單視角學習模型的訓練樣本和標簽，i=1，2，…，l。

通過求解優化問題的KKT條件，可以立即寫出下式來求解問題：

(2)

1.2 SVM-2K模型

多視角數據的涌現使得多視角學習逐漸成為熱門話題，許多學者致力于多視角學習領域的研究。典型相關性分析和核典型相關性分析利用映射后的基向量之間的相關關系來反映原始變量之間的相關性，從而得到多視角數據的共享子空間，它們是兩種常用的子空間學習方法。FARQUHAR等[18]提出了將子空間學習方法和支持向量機相結合，進而構造出了SVM-2K模型。

(3)

通過拉格朗日函數，得到原問題(3)的沃爾夫對偶為

(4)

(5)

2 LSSVM-2K、LSSVM-2KI和LSSVM-2KII模型的建立及算法

上述有約束的SVM-2K算法可以改寫為如下所示的無約束優化問題：

(6)

A、B兩個視角松弛變量對應的hinge損失函數為

(7)

A、B兩個視角間一致性約束的松弛變量對應的ε不敏感損失函數為

(8)

SVM-2K模型雖然可以有效地利用多視角數據間的結構特性提高分類性能，但由于凸優化問題是非光滑的，這將花費更長的訓練時間和更大的內存空間來滿足計算需要，增大了問題的求解難度。最小二乘損失是一個光滑的凸函數，在計算上要比非光滑的凸hinge損失函數更容易求得最優解，可以大大地降低計算復雜度。SVM-2K模型中的ε是一個容許樣本違反約束的不敏感松弛變量，一般取較小值。此外，筆者研究的是具有核函數的非線性問題，為簡單起見，只考慮沒有偏置b的多視角學習器[23]。實際上，偏置b可以視為添加進每一個樣本中額外的值為1的屬性。借鑒最小二乘思想，一致性不等式約束可以改為等式約束，故可得到如下修正的一致性等式約束條件[24]：

(9)

將構造如下所示的最小二乘損失函數對SVM-2K模型進行改進，并在下文對如何有效利用最小損失函數展開討論。

A、B兩個視角各自的松弛變量對應的最小二乘損失函數為

(10)

衡量A、B兩個視角一致性約束的松弛變量對應的最小二乘損失函數為

(11)

2.1 LSSVM-2K模型建立

這里的模型假設和符號意義均和SVM-2K模型相同，不再重述。用最小二乘損失完全替換LSSVM模型中的兩個hinge損失和一個ε不敏感損失，最終得到LSSVM-2K模型：

(12)

(13)

對偶問題可以化簡為如下所示的簡潔形式：

(14)

(15)

(16)

(17)

2.2 LSSVM-2KI模型和LSSVM-2KII模型的建立

在單視角學習任務中，LSSVM模型相比于支持向量機最突出的優點便是大大縮短了訓練時間。那么，如何對擁有3個松弛變量的SVM-2K模型應用最小二乘思想，是筆者也要考慮的問題。在此通過對SVM-2K模型應用最小二乘損失，不同程度地替換原模型中的hinge損失。筆者分別構建了LSSVM-2KI和LSSVM-2KII模型，以便更好地研究最小二乘損失對SVM-2K模型的影響。這里的模型假設和符號意義均和SVM-2K模型的相同，不再贅述。

2.2.1 LSSVM-2KI模型

SVM-2K模型中的ξA，ξB表示A、B兩個視角分離超平面各自對應的松弛變量。SVM-2K模型中的松弛變量ξA，ξB與一致性約束的松弛變量ξ意義相近。因此，首先通過對SVM-2K模型中ξA，ξB應用最小二乘思想，同時保持原模型中一致性約束為不等式約束，構建了LSSVM-2KI模型：

(18)

通過拉格朗日函數得到原問題式(18)的沃爾夫對偶為

修復重復三元組不一致性，用R代表（s，p，o）[start，end]）是一條時態RDF數據記錄，Ri表示第i條記錄，Ri+1就是下一條記錄。首先在時態RDF數據庫中的記錄中匹配（s，p，o）三元組，找到三元組完全一樣的時態RDF數據記錄，通過比較兩個時間區間的起始時間點和結束時間點，計算出修改時間區間，對一條記錄的兩個時間點進行修改，再刪除另外一條記錄。

(19)

這里同樣可以將對偶問題轉化為一個簡單的有約束的二次規劃形式，證明方法與LSSVM-2K模型類似。然后，通過求解二次規劃問題即可求得最優解。

2.2.2 LSSVM-2KII模型

再通過對SVM-2K模型中一致性松弛變量ξ應用最小二乘思想，同時保持A，B兩個視角各自的松弛變量ξA，ξB不變，構建了LSSVM-2KⅡ模型和拉格朗日函數：

(20)

通過拉格朗日函數得到原問題式(20)的沃爾夫對偶為

(21)

這里同樣可以將對偶問題轉化為一個簡單的有約束的二次規劃形式，證明方法也與LSSVM-2K模型類似。然后，通過求解二次規劃問題即可求得最優解。

2.3 LSSVM-2K、LSSVM-2KI和LSSVM-2KII模型算法步驟

LSSVM-2K模型通過求解一個簡單線性方程組得到問題的最優解。對于LSSVM-2KI、LSSVM-2KII，通過二次規劃求解器解決問題。通過上述分析，設計了LSSVM-2K、LSSVM-2KI和LSSVM-2KII算法的步驟，3個模型的算法的不同之處將在括號中注明。

輸出：αA，αB，α(LSSVM-2KI模型輸出αA，αB，α+，α-)，決策函數如式(15)～(17)所示。

步驟2 通過交叉驗證選擇最優參數，構建并且求解線性方程組(LSSVM-2KI和LSSVM-2KII構建并且求解二次規劃問題，通過交叉驗證選擇最優參數)；

步驟4 通過決策函數式(15)～(16)分別預測單個視角A的測試樣本xA和單個視角B的測試樣本xB的標簽，最后通過決策函數式(17)共同預測兩個視角樣本(xA，xB)的標簽。

3 實驗驗證

本節將展示LSSVM-2K模型和另外兩個模型LSSVM-2KI、LSSVM-2KII的實驗結果，并與其他多視角分類方法進行比較。為了驗證筆者提出算法的普適性和有效性，將在動物特征數據集(Animals With Attributes，AWA)、UCI手寫數字集(UCI Digits Dataset)和森林覆蓋類型數據集(Forest CoverType Data)上進行實驗。這3組數據集在多視角學習領域應用較為廣泛。AWA數據集探究模型在固定視角下不同分類對象的分類精度和訓練時間，Digits數據集探究模型在固定分類對象下不同視角的分類精度和訓練時間，Forest CoverType Data數據集探究模型在不同數據規模情況下各個模型的分類精度和訓練時間。通過在這些不同的數據集上進行實驗，可以多視角、多維度地驗證模型的優劣性，同時也說明了多視角學習算法具有較強的普適性。實驗環境如下：Windows 7系統，8 GB內存，Intel(R)Core(TM)i7-4790 CPU的電腦，編程環境為Matlab R2017b。

當前，多視角學習理論在各個領域都有廣泛的應用。在支持向量機領域中具代表性的有SVM+、MVMED、RMvLSTSVM和SVM-2K。將筆者構建的LSSVM-2K，LSSVM-2KI和LSSVM-2KII模型與上述模型進行比較，以驗證新模型的優越性。

(1)SVM+：由特權信息確定的非負校正函數替換標準支持向量機中的松弛變量，就可得到SVM+模型。選擇其中一個視角作為訓練的標準信息，另一個視角作為特權信息，分別記為SVM+A(視角B為特權信息)和SVM+B(視角A為特權信息)，將這兩種情況均作為比較模型。

(2)MVMED：MVMED是在結合了最大熵和最大間隔原理的最大熵判別算法(MED)的基礎上應用了多視角學習理論的模型。

(3)RMvLSTSVM：正則化最小二乘孿生支持向量機(RLSTSVM)是一種新的不平行超平面分類器，它與多視角學習理論結合產生了RMvLSTSVM模型。

(4)SVM-2K：SVM-2K模型是一種結合了KCCA和SVM的經典多視角學習模型。

參數選取：模型中的參數均采用網格搜索法進行參數尋優。SVM+模型和MVMED模型中網格尋優參數范圍取C={10-3，10-2，…，100，…，102，103}。對于RMvLSTSVM模型，不失一般性，為了加快模型的求解，假設正類和負類中松弛變量的參數均相等，取c1=c2=c3=c4={10-3，10-2，…，100，…，102，103}，D=H={10-3，10-2，…，100，…，102，103}。在SVM-2K，LSSVM-2K，LSSVM-2KI和LSSVM-2KII模型中，網格尋優參數范圍取CA=CB={10-3，10-2，…，100，…，102，103}，D={10-3，10-2，…，100，…，102，103}，這里均采用高斯核函數κ(xi，xj)=exp(-‖xi-xj‖2/2σ2)，其中σ是核函數參數，取值范圍是σ={2-6，2-5，…，2-1，20，21，…，26}。為公平起見，以上所有模型的學習率γ取1，所有實驗數據均進行歸一化處理，并在同一條件下運行10次，取平均值來統計結果。

3.1 AWA數據集

通過將構建的模型應用在動物特征數據集上，探究在固定兩個視角下不同分類對象的模型分類情況。AWA由50個動物類別的30 475幅圖像組成，每幅圖像有6個預先提取的特征表示。這里選取顏色直方圖特征(Color Histogram Features)和加速穩健特征(SURF Features)兩種不同的特征提取方案，分別作為視角A和視角B。在A、B兩個視角中各自選取了4個測試類，即黑猩猩(chimpanzee)、美洲豹(leopard)、浣熊(raccoon)和斑馬(zebra)，共計2 712張照片的數據特征。通過一對一策略，為每個類共組合訓練了6組二分類器，如表1所示。在每種動物類中隨機選取100個樣本作為訓練集，其余的作為測試集。實驗結果如表1所示。

根據表1可知，對于固定兩個視角下不同分類對象的情況，LSSVM-2K、LSSVM-2KI和LSSVM-2KII模型的分類情況要明顯優于同類其他多視角模型。對這3種模型進一步進行比較，可以發現LSSVM-2K分類情況良好且所需要的平均訓練時間是同類中最少的，但它比LSSVM-2KI模型的分類效果在整體上略差一些。事實上，LSSVM-2KI是這3種模型中分類效果最好的，但訓練耗時較長。LSSVM-2KII的分類情況在整體上表現則較為一般。

表1 AWA數據集的實驗結果對比

3.2 Digits數據集

通過將構建的模型應用在UCI手寫數字集上，探究新模型在固定兩個分類對象下不同視角的分類情況。Digits數據集取自UCI數據庫，由從荷蘭公用事業地圖集合中提取的共2 000個手寫數字(0～9)構成。這些數字數據集由mfeat-fou、mfeat-fac、mfeat-kar、mfeat-pix、mfeat-zer和mfeat-mor提取方案的視角特征來表示，每個數字由200個被數字化成二進制圖像的樣本組成。取“0～4”之間的數字為“+1”類，“5～9”之間的數字為“-1”類。為了減少計算量，從每個類(正類或負類)隨機抽取100個樣本，每組實驗總共200個樣本作為訓練集，其余的作為測試集。在選取的200個樣本的基礎上，通過一對一的策略，每次選擇兩個視角組成實驗數據集，共訓練了15組二進制分類器，實驗結果如表2所示。

表2 Digits數據集上的實驗結果對比

根據表2可知，對于固定分類對象下不同視角的情況，LSSVM-2K、LSSVM-2KI和LSSVM-2KII模型的分類效果同樣要優于同類其他多視角學習模型。對這3種模型之間進一步進行比較，可以發現LSSVM-2K模型在此數據集上不僅分類效果在整體上表現更為良好一些，而且運算速度更快。LSSVM-2KI的分類效果在這3種模型中分類精度表現相對更穩定一些，但是平均訓練耗時最長。而LSSVM-2KII在數據集Digits的分類效果介于兩者之間，分類效果較為一般。

3.3 Forest Covertype Data數據集

通過將構建的模型在森林覆蓋類型數據集上應用，探究各個模型隨著訓練集規模逐漸增大的情況下，訓練時間的變化情況。實驗中采用的數據集來自UCI Forest Cover Type(Frank & Asuncion，2010)數據集。UCI森林覆蓋類型數據集包含581 012個實例，12個指標和54列數據(10個定量變量，4個荒野地區的二進制變量和40個土壤類型的二進制變量)以及7個目標類，代表從US Forest獲得的30 m×30 m cells的森林覆蓋類型。在UCI森林覆蓋類型數據集中，40個屬性為代表土壤類型的二進制列，4個屬性為代表荒野區域的二進制列，其余10個為連續地形屬性。在實驗中，根據一對一的策略，從原來的7種分類問題中的Aspen(9 493組數據)和Douglas-fir(17 367組數據)兩類數據集中隨機抽取每類8 000個數據作為二分類對象，取前者為“+1”類，后者為“-1”類。這里將10個連續屬性中的前5個屬性和4個荒野區域的二進制列結合構成一個9維的數據集作為視角A，將10個連續屬性中剩余的5個屬性和40個土壤類型二進制列結合構成另外一個45維的數據集作為視角B。通過此數據集探究隨著數據規模的逐漸增大，訓練時間的變化情況。

圖1說明了LSSVM-2K和LSSVM-2KI模型在Forest Covertype Data數據集上相比其他模型具有更好的分類性能，且模型隨著訓練集規模的增大，分類的精度也在逐漸提高。而且，LSSVM-2KI的分類效果相比LSSVM-2K模型要略勝一籌。

圖1 Forest Covertype Data的精度折線圖

為了更清晰地觀察到訓練時間的變化情況，對訓練時間取以10為底的對數做出如圖2所示的訓練時間折線圖。由于MVMED算法所需的訓練時間過長，暫不予以考慮，僅對SVM+，SVM-2K、LSSVM-2K、LSSVM-2KI和LSSVM-2KII模型進行比較。

圖2 Forest Covertype Data的訓練時間折線圖

圖2表明了隨著數據規模的增加，同類型的算法訓練時間增加較為明顯，而且SVM-2K模型的訓練時間的增加尤其突出。LSSVM-2KI模型相比其他同類模型可以得到更高的分類精度，但所消耗的訓練時間比LSSVM-2K和LSSVM-2KII更長。LSSVM-2KII模型是對SVM-2K模型的一致性約束的松弛變量添加了最小二乘思想，雖然分類效果上比SVM-2K模型略差一些，但是大大縮短了模型的訓練時間。LSSVM-2K模型相比其他同類模型既可以得到相對較好的分類精度，而且又比同樣應用了最小二乘思想的RMvLSTSVM耗時更少，所需的訓練時間是最短的。實際上，與SVM-2K模型相比，LSSVM-2K在訓練集規模達到2 000時，訓練時間縮短了約90%，證明了LSSVM-2K模型具有計算方便、速度快、精度高的優點。

4 結束語

通過對SVM-2K模型不同程度地應用最小二乘思想，筆者分別構建了LSSVM-2K、LSSVM-2KI和LSSVM-2KII 3種模型。在固定視角下不同分類對象和在固定分類對象下不同分類視角的情況，探究了3種模型的分類情況。同時，探究了3種模型在不同規模的數據集下模型訓練的耗時情況。實驗表明，筆者提出的LSSVM-2KI算法可以有效地提高數據的分類精度，但耗時相對較長；LSSVM-2KII模型在分類精度和訓練時間上整體表現較為一般；LSSVM-2K算法的分類效果雖然比LSSVM-2KI略差，但是與其他同類型的多視角分類模型相比要好，而且大大地縮短了模型的訓練時間，研究思想具有一定的推廣價值。