林智仁Lin, Chih-Jen臺灣大學:資訊工程學研究所張凱崴Chang, Kai-WeiKai-WeiChang2010-06-092018-07-052010-06-092018-07-052009U0001-1206200910164700http://ntur.lib.ntu.edu.tw//handle/246246/185437在許多分類問題中，訓練資料量頗為龐大，不但資料筆數多，特徵值數量也不少，線性支持向量機是一個處理大型分類問題的熱門訓練模型。在論文中，我們提出一個新的對偶座標下降法，以求解一階及二階損失線性支持向量機，此方法不但簡單，且能在 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 muchaster 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 BSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii IST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi IST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii HAPTER . Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 I. A Dual Coordinate Descent Method for Linear SVM . . . . . . 5 II. Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . 9 .1 Random Permutation of Sub-problems . . . . . . . . . . . . . . 9.2 Shrinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10.3 An Online Setting . . . . . . . . . . . . . . . . . . . . . . . . . 12 V. Relations with Other Methods . . . . . . . . . . . . . . . . . . . . 14 .1 Decomposition Methods for Nonlinear SVM . . . . . . . . . . . 14.2 Existing Linear SVM Methods . . . . . . . . . . . . . . . . . . 16 . Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 .1 Experimental Settings . . . . . . . . . . . . . . . . . . . . . . . 18.2 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . 20.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 I. A Dual Coordinate Descent Methods for Multi-class SVM by Crammer and Singer . . . . . . . . . . . . . . . . . . . . . . . . . . 27 .1 A Multi-class SVM Formulation by Crammer and Singer . . . . 27 .2 The Sequential Dual Method for (6.2) . . . . . . . . . . . . . . 28 .3 Solving the sub-problem (6.5) . . . . . . . . . . . . . . . . . . . 30 .4 Stopping Condition . . . . . . . . . . . . . . . . . . . . . . . . 32 .5 Shrinking Strategy . . . . . . . . . . . . . . . . . . . . . . . . . 33 II. LIBLINEAR: A Library for Large Linear Classi cation . . . . . . 35 .1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 .2 Large Linear Classi cation (Binary and Multi-class) . . . . . . 36 .3 The Software Package . . . . . . . . . . . . . . . . . . . . . . . 36 .3.1 Practical Usage . . . . . . . . . . . . . . . . . . . . . 37 .3.2 Documentation . . . . . . . . . . . . . . . . . . . . . 37 .3.3 Design . . . . . . . . . . . . . . . . . . . . . . . . . . 38 III. Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . 40 PPENDICES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 IBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492364065 bytesapplication/pdfen-US線性分類模型線性支持向量機座標下降法Linear classificationLinear support vector machinesCoordinate descentthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185437/1/ntu-98-R96922050-1.pdf