臺灣博碩士論文加值系統

在許多分類問題中，訓練資料量頗為龐大，不但資料筆數多，特徵值數量也不少，線性支持向量機是一個處理大型分類問題的熱門訓練模型。在論文中，我們提出一個新的對偶座標下降法，以求解一階及二階損失線性支持向量機，此方法不但簡單，且能在 O(log(1/e)個迭代內求得e精確度的最佳解。實驗結果顯示，與目前最先進的求解方法相比，如Pegasos、TRON、SVMperf，我們的方法能在更短的時間內求得解答。此外，我們還延伸對偶座標下降法，以求解大型多類分類問題，並且在本論文中介紹我們實做的LIBLINEAR軟體。

In many applications, data appear with a huge number of instances as well as features. Linear Support Vector Machines (SVM) is one of the most popular tools to deal with such large-scale sparse data. In this thesis, we present a novel dual coordinate descent method for linear SVM with L1- and L2-loss functions. The proposed method is simple and reaches an e-accurate solution in O(log (1/e)) iterations. Experiments indicate that our method is much
faster than state of the art solvers such as Pegasos, TRON, SVMperf, and a recent primal coordinate descent implementation. In addition, we extended the proposed method to solve multi-class problems. We also describe our implementation for the software LIBLINEAR.

口試委員會審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
中文摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi
LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
CHAPTER
I. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
II. A Dual Coordinate Descent Method for Linear SVM . . . . . . 5
III. Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.1 Random Permutation of Sub-problems . . . . . . . . . . . . . . 9
3.2 Shrinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 An Online Setting . . . . . . . . . . . . . . . . . . . . . . . . . 12
IV. Relations with Other Methods . . . . . . . . . . . . . . . . . . . . 14
4.1 Decomposition Methods for Nonlinear SVM . . . . . . . . . . . 14
4.2 Existing Linear SVM Methods . . . . . . . . . . . . . . . . . . 16
V. Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.1 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . 18
5.2 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 20
5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
VI. A Dual Coordinate Descent Methods for Multi-class SVM by Crammer and Singer . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.1 A Multi-class SVM Formulation by Crammer and Singer . . . . 27
6.2 The Sequential Dual Method for (6.2) . . . . . . . . . . . . . . 28
6.3 Solving the sub-problem (6.5) . . . . . . . . . . . . . . . . . . . 30
6.4 Stopping Condition . . . . . . . . . . . . . . . . . . . . . . . . 32
6.5 Shrinking Strategy . . . . . . . . . . . . . . . . . . . . . . . . . 33
VII. LIBLINEAR: A Library for Large Linear Classi cation . . . . . . 35
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.2 Large Linear Classi cation (Binary and Multi-class) . . . . . . 36
7.3 The Software Package . . . . . . . . . . . . . . . . . . . . . . . 36
7.3.1 Practical Usage . . . . . . . . . . . . . . . . . . . . . 37
7.3.2 Documentation . . . . . . . . . . . . . . . . . . . . . 37
7.3.3 Design . . . . . . . . . . . . . . . . . . . . . . . . . . 38
VIII. Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . 40
APPENDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

A. Bordes, L. Bottou, P. Gallinari, and J. Weston. Solving multiclass support
vector machines with LaRank. In ICML, 2007.
B. E. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin
classifiers. In COLT, 1992.
L. Bottou. Stochastic gradient descent examples, 2007. http://leon.bottou.
org/projects/sgd.
C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines,
2001a. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines,
2001b. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
K.-W. Chang, C.-J. Hsieh, and C.-J. Lin. Coordinate descent method for large-
scale L2-loss linear SVM. Journal of Machine Learning Research, 9:1369–1398,
2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/cdl2.pdf.
M. Collins, A. Globerson, T. Koo, X. Carreras, and P. Bartlett. Exponentiated
gradient algorithms for conditional random fields and max-margin Markov net-
works. JMLR, 9:1775–1822, 2008.
K. Crammer and Y. Singer. On the learnability and design of output codes for
multiclass problems. In COLT, 2000.
K. Crammer and Y. Singer. Ultraconservative online algorithms for multiclass
problems. JMLR, 3:951–991, 2003.
R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIB-
LINEAR: A library for large linear classification. Journal of Machine Learn-
ing Research, 9:1871–1874, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/
papers/liblinear.pdf.
T.-T. Friess, N. Cristianini, and C. Campbell. The kernel adatron algorithm: a
fast and simple learning procedure for support vector machines. In ICML, 1998.
C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundararajan. A
dual coordinate descent method for large-scale linear SVM. In Proceedings
of the Twenty Fifth International Conference on Machine Learning (ICML),
2008a. URL http://www.csie.ntu.edu.tw/~cjlin/papers/cddual.pdf. Soft-
ware available at http://www.csie.ntu.edu.tw/~cjlin/liblinear.
C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. S. Keerthi, and S. Sundararajan. A dual
coordinate descent method for large-scale linear SVM. In ICML, 2008b.
T. Joachims. Training linear SVMs in linear time. In ACM KDD, 2006.
T. Joachims. Making large-scale SVM learning practical. In B. Sch ̈lkopf, C. J. C.
Burges, and A. J. Smola, editors, Advances in Kernel Methods - Support Vector
Learning, Cambridge, MA, 1998. MIT Press.
W.-C. Kao, K.-M. Chung, C.-L. Sun, and C.-J. Lin. Decomposition methods for
linear support vector machines. Neural Comput., 16(8):1689–1704, 2004.
S. S. Keerthi and D. DeCoste. A modified finite Newton method for fast solution
of large scale linear SVMs. JMLR, 6:341–361, 2005.
S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, and K. R. K. Murthy. Improve-
ments to Platt’s SMO algorithm for SVM classifier design. Neural Comput., 13:
637–649, 2001.
S. S. Keerthi, S. Sundararajan, K.-W. Chang, C.-J. Hsieh, and C.-J. Lin. A
sequential dual method for large scale multi-class linear SVMs. In ACM KDD,
2008.
J. Langford, L. Li, and A. Strehl. Vowpal Wabbit, 2007. http://hunch.net/~vw.
C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region Newton method for large-
scale logistic regression. JMLR, 9:627–650, 2008.
Z.-Q. Luo and P. Tseng. On the convergence of coordinate descent method for
convex differentiable minimization. J. Optim. Theory Appl., 72(1):7–35, 1992.
O. L. Mangasarian and D. R. Musicant. Successive overrelaxation for support
vector machines. IEEE Trans. Neural Networks, 10(5):1032–1037, 1999.
E. Osuna, R. Freund, and F. Girosi. Training support vector machines: An
application to face detection. In CVPR, 1997.
J. C. Platt. Fast training of support vector machines using sequential minimal
optimization. In B. Sch ̈lkopf, C. J. C. Burges, and A. J. Smola, editors, Advances
o
in Kernel Methods - Support Vector Learning, Cambridge, MA, 1998. MIT Press.
S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos: primal estimated sub-
gradient solver for SVM. In ICML, 2007.
A. J. Smola, S. V. N. Vishwanathan, and Q. Le. Bundle methods for machine
learning. In NIPS, 2008.
T. Zhang. Solving large scale linear prediction problems using stochastic gradient
descent algorithms. In ICML, 2004.