A Comparison of Optimization Methods for Large-scale L1-regularized Linear Classification

大規模線性分類器在文件分類以及計算語言學的領域上受到廣泛的運用。一次正規化的線性分類器則可以應用在特徵選擇上，然而其不可微分的性質卻造成求解時諸多困難。近幾年，各種求解一次正規化線性分類問題的最佳化方法相繼被提出，而至今卻並未受到嚴謹地討論與比較。本論文嚴格地探討一些具代表性的方法與實作上的相關議題，並且透過實驗進行徹底地比較。實驗結果顯示出：座標下降法在一般的狀況下，是最適合用來求解一次正規化線性分類問題的最佳化方法；然而，以牛頓法為基礎的最佳化方法則在求解後期能有最快速的收斂特性。A large-scale linear classifier is useful for document classification and computational linguistics. The L1-regularized form can be used for feature selection, but its non-differentiability causes more difficulties in training. Various optimization methods have been proposed in recent years, but no serious comparison among them has been made. In this paper, we carefully address implementation issues of some representative methods and conduct a comprehensive comparison. Results show that coordinate descent type methods may be the most suitable in general situationshough Newton method has the fastest final convergence.口試委員會審定書 : : : : : : : : : : : : : : : : : : : : : : : : i文摘要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iiBSTRACT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iiiIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : viHAPTER. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1I. A Survey of Existing Methods . . . . . . . . . . . . . . . . . . . . 4.1 Methods by Solving Constrained Optimization Problems . . . . 4.1.1 Problems with Smooth Constraints . . . . . . . . . . 4.1.2 Problems with Nonsmooth Constraints . . . . . . . . 6.2 Decomposition Methods . . . . . . . . . . . . . . . . . . . . . . 6.2.1 Coordinate Descent Methods . . . . . . . . . . . . . . 7.2.2 Gauss-Southwell Method . . . . . . . . . . . . . . . . 8.3 Other Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 9II. Methods by Solving Constrained Optimization Problems . . . 11.1 A Trust Region Newton Method . . . . . . . . . . . . . . . . . 11.1.1 Cauchy Point . . . . . . . . . . . . . . . . . . . . . . 12.1.2 Newton Direction . . . . . . . . . . . . . . . . . . . . 14.1.3 Hessian-vector Product . . . . . . . . . . . . . . . . . 16.2 An Interior Point Method . . . . . . . . . . . . . . . . . . . . . 17V. Decomposition Methods . . . . . . . . . . . . . . . . . . . . . . . . 20.1 Coordinate Descent Methods . . . . . . . . . . . . . . . . . . . 20.1.1 BBR . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.2 CD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24.2 A Coordinate Gradient Descent Method . . . . . . . . . . . . . 28. Other Methods for Solving L1-regularized Problem . . . . . . . 30.1 Generalized Linear Model with Elastic Net . . . . . . . . . . . 30.2 Bundle Methods for Regularized Risk Minimization . . . . . . . 31I. Numerical Experiments . . . . . . . . . . . . . . . . . . . . . . . . 34.1 Data Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34.2 Comparing Solvers for L1-regularized Logistic Regression . . . 35.2.1 Experiment Setting . . . . . . . . . . . . . . . . . . . 35.2.2 Experiments on Micro-array Data sets . . . . . . . . . 38.2.3 Experiments on Large Data sets . . . . . . . . . . . . 39.3 Comparing Solvers for L1-regularized L2-loss Linear SVM . . . 41II. Discussions and Conclusions . . . . . . . . . . . . . . . . . . . . . 55PPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 58IBLIOGRAPHY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7