https://scholars.lib.ntu.edu.tw/handle/123456789/118710
標題: | 座標下降法求解大規模二次漏失函數線性支持向量機 Coordinate Descent Method for Large-scale L2-loss Linear Support Vector Machines |
作者: | 謝卓叡 Hsieh, Cho-Jui |
關鍵字: | 線性支持向量機;文件分類;座標下降法;Linear support vector machine;Document classification;Coordinate descent | 公開日期: | 2009 | 摘要: | 線性支持向量機(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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/185435 |
顯示於: | 資訊工程學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ntu-98-R96922048-1.pdf | 23.32 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。