請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9050
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林智仁(Chih-Jen Lin) | |
dc.contributor.author | Yin-Wen Chang | en |
dc.contributor.author | 張瀠文 | zh_TW |
dc.date.accessioned | 2021-05-20T20:07:41Z | - |
dc.date.available | 2009-08-18 | |
dc.date.available | 2021-05-20T20:07:41Z | - |
dc.date.copyright | 2009-08-18 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-08-06 | |
dc.identifier.citation | B. E. Boser, I. Guyon, and V. Vapnik. A training algorithm for optimal margin classifiers. In Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pages 144–152. ACM Press, 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, 2001. Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm. C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273–297, 1995. K. Crammer and Y. Singer. On the learnability and design of output codes for multiclass problems. Machine Learning, (2-3):201–233, 2002. 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. R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classification. Journal of Machine Learning Research, 9:1871–1874, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/liblinear.pdf. Y. Goldberg and M. Elhadad. splitSVM: Fast, space-efficient, non-heuristic, polynomial kernel computation for NLP applications. In Proceedings of ACL, 2008. 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), 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/cddual.pdf. C.-W. Hsu, C.-C. Chang, and C.-J. Lin. A practical guide to support vector classification. Technical report, Department of Computer Science, National Taiwan University, 2003. URL http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf. H. Isozaki and H. Kazawa. Efficient support vector classifiers for named entity recognition. In Proceedings of COLING, pages 390–396, 2002. T. Joachims. Training linear SVMs in linear time. In Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD). ACM, 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. S. S. Keerthi and C.-J. Lin. Asymptotic behaviors of support vector machines with Gaussian kernel. Neural Computation, 15(7):1667–1689, 2003. S. S. Keerthi, S. K. Shevade, C. Bhattacharyya, and K. R. K. Murthy. Improvements to Platt’s SMO algorithm for SVM classifier design. Neural Computation, 13:637–649, 2001. S. S. Keerthi, O. Chapelle, and D. DeCoste. Building support vector machines with reduced classifier complexity. Journal of Machine Learning Research, 7:1493–1515, 2006. 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 Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/sdm_kdd.pdf. T. Kudo and Y. Matsumoto. Fast methods for kernel-based text analysis. In Proceedings of the 41st Annual Meeting of the Association of Computational Linguistics (ACL), 2003. J. Langford, L. Li, and T. Zhang. Sparse online learning via truncated gradient. Journal of Machine Learning Research, 10:771–801, 2009. Y.-J. Lee and O. L. Mangasarian. RSVM: Reduced support vector machines. In Proceedings of the First SIAM International Conference on Data Mining, 2001. C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region Newton method for large- scale logistic regression. Journal of Machine Learning Research, 9:627–650, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/logistic.pdf. R. A. Lippert and R. M. Rifkin. Infinite-σ limits for Tikhonov regularization. Journal of Machine Learning Research, 7:855–876, 2006. S. Shalev-Shwartz, Y. Singer, and N. Srebro. Pegasos:primal estimated subgradient solver for SVM. In Proceedings of the 24th International Conference on Machine Learning (ICML), 2007. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9050 | - |
dc.description.abstract | 支持向量機常使用非線性映射函數將資料點映到高維度空間,以便於將非線性分布的資料點分類。核心函數則可以解決映射到高維度空間之後的資料向量有過多特徵而難以訓練的問題。然而,在大規模資料上訓練支持向量機所需的時間相當長。本論文根據最近在訓練大規模線性支持向量機(不使用非線性核心的支持向量機)上的研究,提出一個在所需訓練時間與測試準確度之間取得平衡的方法。本研究將線性支持向量機的快速訓練方法應用於以低階多項式映射函數展開的資料上。此方法有快速訓練的好處,同時可以達到與使用高度非線性核心函數相近的測試準確度。實驗顯示在特定大規模資料集上,所提方法確實可以以較少的時間得出相近的準確度。 | zh_TW |
dc.description.abstract | Non-linear mapping functions have long been used in SVM to transform data into a higher dimensional space, allowing the classifier to separate non-linearly distributed data instances. Kernel tricks are used to avoid the problem of a huge number of features of the mapped data point. However, the training/testing for large data is often time consuming. Following the recent advances in training large linear SVM (i.e., SVM without using nonlinear kernels), this work proposes a method that strikes a balance between the training/testing speed and the testing accuracy. We apply the fast training method for linear SVM to the expanded form of data under low-degree polynomial mappings. The method enjoys the fast training/testing, but may achieve testing accuracy close to that of using highly nonlinear kernels. Empirical experiments show that the proposed method is useful for certain large-scale data sets. | en |
dc.description.provenance | Made available in DSpace on 2021-05-20T20:07:41Z (GMT). No. of bitstreams: 1 ntu-98-R96922032-1.pdf: 15117154 bytes, checksum: 0d7003c6182c75152d681de9fb1c81e4 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | TABLE OF CONTENTS
口試委員審定書 . .. . . . . . . . . . . . . . . . . . . . i 中文摘要 . . . . . . . . . . . . . . . . . . . .. .. . . ii ABSTRACT . . . . . . . . . . . . . . . . . . . . . . .. iii LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . vi CHAPTER I. Introduction . . . . . . . . . . . . . . . . . . . . . 1 II. Support Vector Machines . . . . . . . . . . . . . . . 4 2.1 Linear Support Vector Machines . . . . . . . . . . . 4 2.2 Nonlinear Support Vector Machines . . . . . . . . . . 5 III. Decomposition Methods. . . . . . . . . . . . . . . . 7 3.1 Decomposition Methods for Nonlinear SVM . . . . . . . 7 3.2 Decomposition Methods for Linear SVM. . . . . . . . . 9 IV. Training/Testing Low-degree Polynomial Mappings of Data Using Linear SVM . . . . . . . . . . . . . . . . . . . . 12 4.1 Low-degree Polynomial Mappings . . . . . . . . . . . 12 4.2 Number of Nonzero Features per Instance. . . . . . . 13 4.3 Training by Decomposition Methods. . . . . . . . . . 14 4.4 Training by Other Methods for Linear SVM . . . . . . 16 4.5 Relations with the RBF kernel. . . . . . . . . . . . 16 4.6 Parameter Selection. . . . . . . . . . . . . . . . . 17 4.7 Prediction . . . . . . . . . . . . . . . . . . . . . 17 4.8 Multi-class Classification. . . . . . . . . . . . . . 18 V. Experiments . . . . . . . . . . . . . . . . . . . . . 19 5.1 Data Sets and Implementations. . . . . . . . . . . . 19 5.2 Analysis of φ(x) and w. . . . . . . . . . . . . . . 21 5.3 Calculating or Storing φ(xi) . . . . . . . . . . . 22 5.4 Accuracy and Time of Using Linear, Degree-2 Polynomial, and RBF . . . . . . . . . . . . . . . . . . . . . . . . 23 VI. Discussions and Conclusions . . . . . . . . . . . . 27 APPENDICES . . . . . . . . . . . . . . . . . . . . . . . 29 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . 31 | |
dc.language.iso | en | |
dc.title | 低階多項式資料映射與支持向量機 | zh_TW |
dc.title | Low-degree Polynomial Mapping of Data for SVM | 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 | decomposition methods,low-degree polynomial mapping,kernel functions,support vector machines, | en |
dc.relation.page | 32 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2009-08-06 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf | 14.76 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。