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

Two-variable Block Dual Coordinate Descent Methods for Large-scale Linear Support Vector Machines

丘濟政(Chi-Cheng Chiu)

指導教授 ： 林智仁

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201801837

摘要

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

關鍵字

區塊座標下降法 ； 線性支持向量機

並列摘要

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.

並列關鍵字

block coordinate descent ； linear support vector machines

參考文獻

B. E. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144–152. ACM Press, 1992.

C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines. ACM Transactions on Intelligent Systems and Technology, 2(3):27:1–27:27, 2011. Software available at http://www.csie.ntu.edu.tw/˜cjlin/libsvm.

W.-L. Chiang, M.-C. Lee, and C.-J. Lin. Parallel dual coordinate descent method for large-scale linear classification in multi-core environments. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016. URL http://www.csie.ntu.edu.tw/˜cjlin/papers/multicore_cddual.pdf.

C.-C. Chiu and C.-J. Lin. Two-variable block dual coordinate descent methods for large-scale linear support vector machines. Technical report, National Taiwan University, 2018. URL https://www.csie.ntu.edu.tw/˜cjlin/papers/2var_cd/twocddual.pdf.

C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273–297, 1995.