基於兩變量區塊座標下降法解大規模線性支持向量機

Abstract

座標下降法已經是解大規模線性支持向量機的最新技術，最常是用在解無偏差項支持向量機的對偶問題，對於更新過程中一次更新一個變量的座標下降法是可以輕易的實作出來。在這篇論文中我們將從一個變量拓展至兩個，看似簡單實則不然，必須有一些複雜的推導才能得到單純的步驟，我們的演算法在一般情況下可匹敵且困難問題中有良好的表現。我們進一步討論雙變量座標下降法解有偏差項支持向量機，研究後發現此法再有偏差項上表現較差，與核方法支持向量機結果不同，因此過去單變量坐標下降法的成功並非偶然，像是選擇非正規的無偏差支持向量機使得計算上更為效率。綜觀所述本篇在線性支持向量機提供許多新的角度。

Coordinate descent (CD) methods have been a state-of-the-art technique for training large-scale linear SVM. The most used setting is to solve the dual problem of an SVM formulation without the bias term, for which the CD procedure of updating one variable at a time is very simple and easy to implement. In this thesis, we extend the one-variable setting to use two variables at each CD step. The extension, while looks simple, is not trivial. Some complicated derivations are needed to get a simple CD procedure. Our resulting algorithm is generally competitive with one-variable CD and is superior for difficult problems. We further discuss the two-variable CD for the standard SVM formulation with a bias term. The analysis shows that CD methods are less effective for this SVM formulation, a situation very different from that of kernel SVM. Thus the success of simple one-variable CD in the past decade is not a coincidence. Some design choices such as the SVM formulation considered help to make it computationally efficient. Overall this thesis sheds many new insights on CD methods for training linear SVM.