請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37483
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林智仁(Chih-Jen Lin) | |
dc.contributor.author | Mi-Chen Tsai | en |
dc.contributor.author | 蔡宓真 | zh_TW |
dc.date.accessioned | 2021-06-13T15:29:43Z | - |
dc.date.available | 2008-07-24 | |
dc.date.copyright | 2008-07-24 | |
dc.date.issued | 2008 | |
dc.date.submitted | 2008-07-15 | |
dc.identifier.citation | BIBLIOGRAPHY
A. Asuncion and D. J. Newman. UCI machine learning repository, 2007. URL http://www.ics.uci.edu/$sim$mlearn/{MLR}epository.html. B. E. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classi ers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144-152. ACM Press, 1992. C.-C. Chang and C.-J. Lin. LIBSVM: a library for support vector machines, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm. Y.-H. Dai and R. Fletcher. New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Program., 106(3):403-421, 2006. R.-E. Fan, P.-H. Chen, and C.-J. Lin. Working set selection using second order information for training SVM. Journal of Machine Learning Research, 6:1889-1918, 2005. URL http://www.csie.ntu.edu.tw/~cjlin/papers/quadworkset.pdf. T. Joachims. Training linear SVMs in linear time. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD). ACM, 2006. S. S. Keerthi and D. DeCoste. A modi ed nite Newton method for fast solution of large scale linear SVMs. Journal of Machine Learning Research, 6:341-361,2005. D. D. Lewis, Y. Yang, T. G. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361-397, 2004. C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region Newton method for largescale logistic regression. In Proceedings of the 24th International Conference on Machine Learning (ICML), 2007. Software available at http://www.csie.ntu.edu.tw/~cjlin/liblinear. J. C. Platt. Fast training of support vector machines using sequential minimal optimization. In B. Sch�olkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods - Support Vector Learning, Cambridge, MA, 1998. MIT Press. B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, and R. C. Williamson. Estimating the support of a high-dimensional distribution. Neural Computation, 13(7):1443-1471, 2001. A. J. Smola, S. V. N. Vishwanathan, and Q. Le. Bundle methods for machine learning. In J. Platt, D. Koller, Y. Singer, and S. Roweis, editors, Advances in Neural Information Processing Systems 20. MIT Press, Cambridge, MA, 2008. C. H. Teo, A. Smola, S. V. Vishwanathan, and Q. V. Le. A scalable modular convex solver for regularized risk minimization. In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 727-736, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-609-7. doi: http://doi.acm.org/10.1145/1281192.1281270. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37483 | - |
dc.description.abstract | 稀疏資料分類的問題近年來在文件分類與自然語言處理等領域中很常見,線性支持向量機對於大規模稀疏資料分類便漸趨實用。傳統以斜率為基礎的方法無法用於解決一維範數損失函數支持向量機(L1-SVM)的問題,於是諸如綑集法和切面的技巧等就被利用在這類不可微分的問題上。在這篇論文中,我們在這篇論文中利用 libsvm 實作了 Smola et al. (2008) 中提出的綑集法,我們也列出了一些實驗上與 bmrm 函式庫的比較。 | zh_TW |
dc.description.abstract | Classification on data with sparse features are common in
document classification and natural language processing. Linear support vector machines (SVM) thus is for classifying large-scale sparse data. Some optimization formulations like L1-SVM cannot be minimized with traditional gradient based approaches. Methods like bundle methods and cutting plane techniques are useful for such non-differentiable SVM problems. In this thesis, we implement the bundle method proposed in Smola et al. (2008) by modifying libsvm. We also experimentally compare our implementation with another implementation mrm. | en |
dc.description.provenance | Made available in DSpace on 2021-06-13T15:29:43Z (GMT). No. of bitstreams: 1 ntu-97-R95922016-1.pdf: 1061642 bytes, checksum: 7f425a18630235553f705ba1e632369d (MD5) Previous issue date: 2008 | en |
dc.description.tableofcontents | TABLE OF CONTENTS
口試委員會審定書 : : : : : : : : : : : : : : : : : : : i 摘要 : : : : : : : : : : : : : : : : : : : : : : : : : ii ABSTRACT : : : : : : : : : : : : : : : : : : : : : : : iii LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : vi LIST OF TABLES : : : : : : : : : : : : : : : : : : : : vii CHAPTER I. Introduction . . . . . . . . . . . . . . . . . . . . 1 II. The Bundle Method . . . . . . . . . . . . . . . . . 4 2.1 Subgradient . . . . . . . . . . . . . . . . . . . . 4 2.2 The Algorithm . . . . . . . . . . . . . . . . . . . 5 2.3 Dual Problem . . . . . . . . . . . . . . . . . . . 7 2.4 Prediction . . . . . . . . . . . . . . . . . . . . 9 III. Implementation Details . . . . . . . . . . . . . . 10 3.1 Overview . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Used Data Structures and Parameters in LIBSVM . . 10 3.2 Preprocessing . . . . . . . . . . . . . . . . . . . 13 3.3 Solving the Dual Problem . . . . . . . . . . . . . 14 3.3.1 One-Class SVM Formulation . . . . . . . . . . . . 14 3.3.2 Solving Dual as One-Class SVM Problem . . . . . . 15 3.3.3 Warm Start . . . . . . . . . . . . . . . . . . . 16 3.3.4 Precomputed Kernel . . . . . . . . . . . . . . . 16 3.3.5 Remove Old Constraints . . . . . . . . . . . . . 18 3.4 Taylor Coecients for Loss Function . . . . . . . . 18 3.5 Stopping Condition . . . . . . . . . . . . . . . . 19 3.5.1 Computation . . . . . . . . . . . . . . . . . . . 19 3.5.2 Relative Stopping Condition . . . . . . . . . . . 20 3.6 Solving L2-SVM . . . . . . . . . . . . . . . . . . 21 IV. Experiment Results . . . . . . . . . . . . . . . . 23 4.1 Data Sets . . . . . . . . . . . . . . . . . . . . . 23 4.1.1 a9a . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.2 real-sim . . . . . . . . . . . . . . . . . . . . 23 4.1.3 news20 . . . . . . . . . . . . . . . . . . . . . 24 4.1.4 rcv1 . . . . . . . . . . . . . . . . . . . . . . 24 4.2 BMRM . . . . . . . . . . . . . . . . . . . . . . . 24 4.3 Experimental Settings . . . . . . . . . . . . . . . 26 4.3.1 Environment and Parameters . . . . . . . . . . . 26 4.3.2 Experiment Approach . . . . . . . . . . . . . . . 26 4.4 Enhancements . . . . . . . . . . . . . . . . . . . 27 4.4.1 Warm Start and Precomputed Kernel . . . . . . . . 27 4.4.2 Removing Old Constraints . . . . . . . . . . . . 27 4.5 Comparisons with BMRM . . . . . . . . . . . . . . . 28 V. Conclusions and Future Work . . . . . . . . . . . . 35 BIBLIOGRAPHY : : : : : : : : : : : : : : : : : : : : : 36 | |
dc.language.iso | en | |
dc.title | 實作以綑集法解線性支持向量機問題 | zh_TW |
dc.title | An Implementation of the Bundle Method | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 李育杰(Yuh-Jye Lee),鮑興國(Hsing-Kuo Pao) | |
dc.subject.keyword | 線性支持向量機,綑集法,切面法,副梯度,大規模稀疏資料分類, | zh_TW |
dc.subject.keyword | linear support vector machines,bundle method,cutting plane,subgradient,large-scale sparse data classification, | en |
dc.relation.page | 37 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-07-16 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 1.04 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。