林智仁Lin, Chih-Jen臺灣大學:資訊工程學研究所謝卓叡Hsieh, Cho-JuiCho-JuiHsieh2010-06-092018-07-052010-06-092018-07-052009U0001-1206200915045900http://ntur.lib.ntu.edu.tw//handle/246246/185435線性支持向量機(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.TABLE OF CONTENTS試委員審定書 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : i文摘要 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iiBSTRACT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iiiIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : viIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : viiHAPTER. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1I. Solving Linear SVM via Coordinate Descent . . . . . . . . . . . 6II. Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . 12.1 Data Representation . . . . . . . . . . . . . . . . . . . . . . . . 12.2 Random Permutation of Sub-problems . . . . . . . . . . . . . . 13.3 An Online Algorithm . . . . . . . . . . . . . . . . . . . . . . . 13V. Related Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15.1 Pegasos for L1-SVM . . . . . . . . . . . . . . . . . . . . . . . . 15.2 Trust Region Newton Method (TRON) for L2-SVM . . . . . . . 18.3 CMLS: A Coordinate Descent Method for L2-SVM . . . . . . . 20. Experiments and Analysis . . . . . . . . . . . . . . . . . . . . . . . 22.1 Data Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.2 Comparisons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23.3 Stopping Conditions . . . . . . . . . . . . . . . . . . . . . . . . 30I. Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . 32v.1 Order of Sub-problems at Each Outer Iteration . . . . . . . . . 32.2 Coordinate Descents for Logistic Regression . . . . . . . . . . . 33.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35PPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 36IBLIOGRAPHY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 462461290 bytesapplication/pdfen-US線性支持向量機文件分類座標下降法Linear support vector machineDocument classificationCoordinate descentthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185435/1/ntu-98-R96922048-1.pdf