求解大規模非凸優化問題的多階段MM方法*

袁友宏 周 凱

（陸軍炮兵防空兵學院 合肥 230031）

1 引言

支持向量機（Supporting Vector Machine，SVM）是由Vapnik等人于1992年提出的一種標準的機器學習算法［1］。從最初的“邊緣最大化”發展到如今的“正則化項+損失函數［2］”，學者們對SVM的研究從未停止。SVM應用廣泛，然而在處理大規模數據時，會因為過多的支持向量，使得計算代價明顯增大，特別是在預測階段［3］。利用截斷Hinge損失函數，可以得到稀疏的支持向量，降低計算代價，但卻令凸優化問題轉變為非凸優化問題。2013年，Mairal將解決非凸優化問題的CCCP［4］和DCA（Difference Convex Algorithm，DCA）［5］等常用方法，歸結為一個統一的MM框架［6］，在非凸優化領域中受到廣泛應用。

從理論上分析，基于0-1損失的分類誤差是最好的，然而是一個NP難問題［7～8］。因此，有很多近似0-1損失的其它損失函數，例如Hinge損失，最小二乘損失和指數損失等。研究表明，SVM優化問題中使用的Hinge損失（或稱為L1損失）是其成功的關鍵［9］。2007年，Singer使用隨機投影次梯度對大規模SVM進行求解（稱為Pegasos），取得了轟動一時的實際效果［10］。盡管SVM獲得了巨大成功，但對于大規模問題，有如下不足：

1）對于訓練數據中的噪聲樣本，SVM十分敏感。

2）支持向量的數量會隨著樣本數線性增加，從而導致在大規模問題中，支持向量集合過大，預測階段所需時間大大增加。

3）過多的支持向量導致SVM魯棒性較差。

適當的修改Hinge損失可能顯著提升SVM的表現。著名學者Shen提出了截斷Hinge損失函數（稱為截斷L1-SVM問題）方法［11］，其中通過截斷損失函數去逼近0-1損失函數，能夠有效減少離群點對分類超平面的干擾，并且減少了支持向量的數目。然而，截斷Hinge損失為非凸函數，這就使得原凸優化問題變為了棘手的非凸優化問題。由于非凸優化問題不存在“局部最優即全局最優”這一特性，傳統的凸優化一階梯度方法，例如投影次梯度算法［12］、鏡面下降算法［12］、對偶平局算法［13］和交替方向乘子法［14］等，無法直接應用于非凸優化問題的求解。

2013年，Mairal將這類方法統一為MM框架，其核心思想就是先尋找原目標非凸函數的一個凸上界，再對凸上界進行優化，反復迭代，求解得到最優值［15］。并在此基礎上，針對大規模優化問題，提出了一種隨機MM方法［6］，取得了較好效果。MM框架非常適用于有限和形式的目標函數，2015年，又將隨機MM方法拓展到增量MM方法，相比批處理方法，計算復雜度明顯降低［16］。但這兩種方法都要求目標函數為光滑非凸函數，滿足一階穩定點條件，才具有收斂性。

對于大規模數據，本文利用截斷Hinge損失求解SVM問題，得到了稀疏的支持向量，降低了計算復雜度，并證明了是KKT條件使得支持向量稀疏。此外，在MM框架下提出了一種多階段MM優化方法，針對非光滑非凸問題，理論上證明了算法具有收斂性。最后，進行了實驗驗證，證明了算法的收斂性和高效性。

2 截斷L1-SVM的稀疏性分析

本節僅對截斷L1-SVM進行分析。首先定義集合，其中(xi,yi)∈,i=1,2,…,m，并且樣本為獨立同分布。令L1(u)=(1-u)+，其中：

L1-SVM是最小化如下目標函數：

其中參數C＞0。

定義1滿足下式條件的樣本點，稱為outlier點。

其中Ot代表第t階段的outlier點的集合。

截斷形式的Hinge損失定義如下：

圖1 截斷損失函數

令Hδ(u)=(δ-u)+，顯然Hδ是一個凸函數。

并且對于每項L1[yi(w,xi+b)]引入一個非負松弛變量ξi，即：

然后推導出式（6）的對偶形式如下：

并且KKT互補條件是：

算法1截斷L1-SVM的CCCP算法

初始化權重向量β0；

重復：

1）通過式（9）計算得到αt；

2）由式（9）的KKT條件計算得到(wt+1,bt+1)；

3）通過式（7）計算βt；

直到：βt=βt+1。

文獻［17］指出浮點運算已經嚴重影響了L1正則化隨機算法和在線算法的稀疏性。這從另一個角度啟發了我們為什么不利用多階段算法，在每個階段迭代之前盡可能剔除過多的離群點。

3 多階段MM算法

針對非凸優化問題，MM框架通過尋找目標函數的凸上界，再利用梯度下降等方法優化其凸上界替代函數，得到原目標函數的最優解。非凸問題可以在某些條件下恰當的轉化為凸問題，得到很好的解決。而MM框架的精髓就在于如何去找到一個合適的凸上界，這也是一個難點。首先介紹一下MM框架原理。

在歐氏空間里的一個子集Θ，對于一些比較難以操作的目標函數f，假設希望得到如下結果：

由于目標函數f為非凸的，因此不直接對函數f進行優化，反而可以在一些v∈Θ的點，考慮函數f的更容易操作的majorizer項來進行優化。

定義2稱函數g(w;v)是目標函數f(w)的一個majorizer，如果有：

1）對于每個點w∈Θ，有f(w)=g(w;v)成立；

2）對于每個點θ,v∈Θ，當θ≠v時，有f(θ)≤g(θ;v)成立。

定義3令w(0)為初始值，w(r)是第r次的迭代值。則稱w(r+1)是MM算法的第(r+1)次迭代值，如果滿足下式：

根據定義2和定義3，我們能夠得到所有MM算法的單調性。也就是說，如果w(r)是MM算法的一系列迭代值，那么目標函數是隨著迭代步驟r單調下降的。

定理1如果g(w;v)是目標函數f(w)的一個majorizer，w(r)是MM算法的一系列迭代值，那么有：

有了以上的定義，我們在這里給一個一般性的MM算法描述。

1）第一個M步驟：尋找目標函數的一個比較容易優化的majorizer函數；

2）第二個M步驟：對這個majorizer函數進行最小化操作。

算法2基本MM算法

輸入：w0∈Θ，T，t=1；

重復：

1）在wt-1附近找一個f的替代函數gt；

2）最小化替代函數gt，求得最優解wt；

t=t+1

直到：t=T

輸出：wT。

綜上所述，本文提出一個簡單有效的多階段MM算 法（Multi-stage Majorization-minimization SVM，MM-SVM）來解決截斷L1-SVM問題。算法描述如下：

算法3多階段MM算法（MM-SVM）

輸入：初始化w0，b0，t=1

重復：

1）計算St=S-Ot；

2）計算

直到：Ot+1=Ot

其中S為初始樣本集，St為第t截斷的樣本集。

由于每次都是對截斷損失函數的一個凸上界進行優化，所以MM-SVM算法屬于MM框架下的一種算法。如式（6）所示，CCCP算法利用所有樣本，通過二次優化問題求解(wt,bt)，并利用KKT條件提出outlier點。與此相反，MM-SVM算法通過SVM子問題得到(wt,bt)，且outlier點在每個階段之前提前被剔除。直觀地說，MM-SVM算法旨在不斷地從先前的SVs集合中剔除所有當前異常值，朝著一個最佳子集凸優化移動。收斂性證明后，很容易知道MM-SVM中用于解決截斷損失問題的SVs完全由最終階段的SVM子問題決定。這就是為什么MS-SVM算法可以充分改善稀疏性。

定理2?w0∈RN，假設wt是由MM-SVM算法得到，則有：

2）若存在一個正常數t0使得St0+1=St0，則St=St0?t≥t0；

3）存在一個向量w*∈RN+1，使得wt在有限步驟收斂到w*；

4）w*是的一個局部最小點。

4 實驗驗證

這一節主要對本文提出的方法進行對比實驗驗證。算法采用Matlab編程，以LIBSVM為基礎進行修改。常用的大規模標準數據庫均來自林智仁小 組（https：//www.csie.ntu.edu.tw/～cjlin/libsvmtools/datasets/）。如表1所示。

表1 數據集描述

在表1中的數據集上，將MM-SVM算法分別與CCCP算法和SVM算法作比較。我們設置參數C=1，δ=0。由于CCCP算法存在浮點問題，很難得到βt=βt+1，為了較早的終止CCCP算法，終止條件設為‖βt-βt+1‖≤0.1。為了表明MM-SVM算法在稀疏性上的優勢，并且降低了計算復雜度，我們以SVs的數量、CPU時間、階段數量和準確率為指標，實驗結果如表2～表5所示。

表2 在數據集Covtype上的線性分類

表3 在數據集Ijcnn1上的線性分類

表4 在數據集A9a上的線性分類

表5 在數據集Rcv1上的線性分類

從表中數據可知，MM-SVM算法能夠產生更稀疏的SVs，驗證了截斷Hinge損失的有效性。在大規模數據上，相比CCCP算法，消耗的CPU時間大大減少，并且準確度也有所提高。與SVM算法相比，支持向量減少的更為明顯，但是由于SVM利用凸的Hinge損失，而MM-SVM是復雜的非凸截斷Hinge損失，因此CPU時間不具有可比性。圖2給出了MM-SVM算法的收斂性曲線，算法在不同數據集上的目標函數值均在有限時間內收斂到穩定值，驗證了文中的理論收斂性分析。

圖2 MM-SVM算法的收斂性

5 結語

SVM方法在處理大規模問題時，支持向量過多，計算復雜度高，針對這一問題，本文提出了一種求解非凸非光滑問題的多階段MM算法。MM-SVM對Hinge損失進行截斷，得到一個非凸優化問題，而后巧妙利用MM框架和多階段策略，將其轉化為凸優化問題，克服了傳統SVM在處理大規模問題時的缺點。最后，從實驗角度驗證了算法的有效性與收斂性。但是，MM-SVM算法在求解每一個SVM子問題時，采用批處理方法求解，效率不如隨機或增量方法，下一步的主要工作是如何將其擴展為隨機算法。