請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41311完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 林智仁(Chih-Jen Lin) | |
| dc.contributor.author | Kai-Wei Chang | en |
| dc.contributor.author | 張凱崴 | zh_TW |
| dc.date.accessioned | 2021-06-15T00:15:38Z | - |
| dc.date.available | 2009-07-16 | |
| dc.date.copyright | 2009-07-16 | |
| dc.date.issued | 2009 | |
| dc.date.submitted | 2009-06-15 | |
| dc.identifier.citation | 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. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41311 | - |
| dc.description.abstract | 在許多分類問題中，訓練資料量頗為龐大，不但資料筆數多，特徵值數量也不少，線性支持向量機是一個處理大型分類問題的熱門訓練模型。在論文中，我們提出一個新的對偶座標下降法，以求解一階及二階損失線性支持向量機，此方法不但簡單，且能在 O(log(1/e)個迭代內求得e精確度的最佳解。實驗結果顯示，與目前最先進的求解方法相比，如Pegasos、TRON、SVMperf，我們的方法能在更短的時間內求得解答。此外，我們還延伸對偶座標下降法，以求解大型多類分類問題，並且在本論文中介紹我們實做的LIBLINEAR軟體。 | zh_TW |
| dc.description.abstract | 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. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T00:15:38Z (GMT). No. of bitstreams: 1 ntu-98-R96922050-1.pdf: 2364065 bytes, checksum: fc7d10e2adf845f95e92b21d0fb555c4 (MD5) Previous issue date: 2009 | en |
| dc.description.tableofcontents | 口試委員會審定書 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Classication . . . . . . 35 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 7.2 Large Linear Classication (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 | |
| dc.language.iso | en | |
| dc.subject | 線性支持向量機 | zh_TW |
| dc.subject | 線性分類模型 | zh_TW |
| dc.subject | 座標下降法 | zh_TW |
| dc.subject | Linear support vector machines | en |
| dc.subject | Coordinate descent | en |
| dc.subject | Linear classification | en |
| dc.title | 對偶座標下降法求解線性支持向量機 | zh_TW |
| dc.title | Dual Coordinate Descent Methods for Large-scale Linear Support Vector Machines | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 97-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林軒田(Hsuan-Tien Lin),李育杰(Yuh-Jye Lee) | |
| dc.subject.keyword | 線性分類模型,線性支持向量機,座標下降法, | zh_TW |
| dc.subject.keyword | Linear classification,Linear support vector machines,Coordinate descent, | en |
| dc.relation.page | 51 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2009-06-15 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-98-1.pdf 未授權公開取用 | 2.31 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。