座標下降法求解大規模二次漏失函數線性支持向量機

Coordinate Descent Method for Large-scale L2-loss Linear Support Vector Machines

謝卓叡(Cho-Jui Hsieh)

指導教授 ： 林智仁

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

https://doi.org/10.6342/NTU.2009.00894

摘要

線性支持向量機(SVM)是分類大規模資料時很有用的方法。在文件分類和自然語言處理的問題中，特徵向量常常是稀疏的。在這篇論文中，我們提出一個新的座標下降法來求解二次漏失函數的線性支持向量機。我們提出的方法在每一步過程中固定其他變數，只針對某個變數做最小化。而針對這個變數最小化的過程是用牛頓法配上線性搜尋的技巧。我們的演算法會以線性的速度收斂到函數的最小值。因為在最佳化每個變數時，我們的演算法必須找到擁有某個特徵值得所有資料，所以比較適合處理能方便的取得這種資訊的訓練資料。實驗結果顯示出我們的方法比其他目前最新的方法例如Pegasos和Tron還快且穩定。

關鍵字

線性支持向量機 ； 文件分類 ； 座標下降法

並列摘要

Linear support vector machines (SVM) are useful for classifying large-scale sparse data. Problems with sparse features are common in applications such as document classi cation and natural language processing. In this thesis, we propose a novel coordinate descent algorithm for training linear SVM with the L2-loss function. At each step, the proposed method minimizes a one-variable sub-problem while fixing other variables. The sub-problem is solved by Newton steps with the line search technique. The procedure globally converges at the linear rate. As each sub-problem involves only values of a corresponding feature, the proposed approach is suitable when accessing a feature is more convenient than accessing an instance. Experiments show that our method is more e cient and stable than state of the art methods such as Pegasos and TRON.

並列關鍵字

Linear support vector machine ； Document classification ； Coordinate descent

參考文獻

L. Bottou. Stochastic gradient descent examples, 2007. http://leon.bottou.org/projects/sgd.

M. Dud k, S. J. Phillips, and R. E. Schapire. Performance guarantees for regularized maximum entropy density estimation. In Proceedings of the 17th Annual Conference on Computational Learning Theory, pages 655{662, New York, 2004. ACM press.

I. S. Du , R. G. Grimes, and J. G. Lewis. Sparse matrix test problems. ACM Transactions on Mathematical Software, 15:1{14, 1989.

L. Grippo and M. Sciandrone. Globally convergent block-coordinate techniques for unconstrained optimization. Optimization Methods and Software, 10:587{637, 1999.

Z.-Q. Luo and P. Tseng. On the convergence of coordinate descent method for convex di erentiable minimization. Journal of Optimization Theory and Applications, 72(1):7{35, 1992.