請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/6237
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 林智仁(Chih-Jen Lin) | |
dc.contributor.author | Ching-Pei Lee | en |
dc.contributor.author | 李靜沛 | zh_TW |
dc.date.accessioned | 2021-05-16T16:23:50Z | - |
dc.date.available | 2013-07-08 | |
dc.date.available | 2021-05-16T16:23:50Z | - |
dc.date.copyright | 2013-07-08 | |
dc.date.issued | 2013 | |
dc.date.submitted | 2013-07-04 | |
dc.identifier.citation | G. M. Adelson-Velsky and E. M. Landis. An algorithm for the organization of
information. Proceedings of the USSR Academy of Sciences, 146:263{266, 1962. A. Airola, T. Pahikkala, and T. Salakoski. Training linear ranking SVMs in linearithmic time using red{black trees. Pattern Recognition Letters, 32(9):1328{ 1336, 2011. A. Andersson. Balanced search trees made simple. In Proceedings of the Third Workshop on Algorithms and Data Structures, pages 60{71, 1993. R. Bayer. Symmetric binary B-trees: Data structure and maintenance algorithms. Acta Informatica, 1:290{306, 1972. 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. L. Breiman. Random forests. Machine Learning, 45(1):5{32, 2001. C. J. C. Burges. From RankNet to LambdaRank to LambdaMART: An overview. Technical Report MSR-TR-2010-82, Microsoft Research, 2010. Y.-W. Chang, C.-J. Hsieh, K.-W. Chang, M. Ringgaard, and C.-J. Lin. Training and testing low-degree polynomial data mappings via linear SVM. Journal of Machine Learning Research, 11:1471{1490, 2010. URL http://www.csie.ntu. edu.tw/~cjlin/papers/lowpoly_journal.pdf. O. Chapelle. Training a support vector machine in the primal. Neural Computa- tion, 19(5):1155{1178, 2007. O. Chapelle and Y. Chang. Yahoo! learning to rank challenge overview. In JMLR Workshop and Conference Proceedings: Workshop on Yahoo! Learning to Rank Challenge, volume 14, pages 1{24, 2011. O. Chapelle and S. S. Keerthi. E cient algorithms for ranking with SVMs. In- formation Retrieval, 13(3):201{215, 2010. D. Christensen. Fast algorithms for the calculation of Kendall's . Computational Statistics, 20:51{62, 2005. A. R. Conn, N. I. M. Gould, and P. L. Toint. Trust-region Methods. Society for Industrial and Applied Mathematics, Philadelphia, 2000. C. Cortes and V. Vapnik. Support-vector network. Machine Learning, 20:273{ 297, 1995. R.-E. Fan, K.-W. Chang, C.-J. Hsieh, X.-R. Wang, and C.-J. Lin. LIBLINEAR: A library for large linear classi cation. Journal of Machine Learn- ing Research, 9:1871{1874, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/ papers/liblinear.pdf. J. H. Friedman. Greedy function approximation: A gradient boosting machine. Annals of Statistics, 29(5):1189{1232, 2001. D. A. Heger. A disquisition on the performance behavior of binary search tree data structures. European Journal for the Informatics Professional, 5(5):67{75, 2004. R. Herbrich, T. Graepel, and K. Obermayer. Large margin rank boundaries for ordinal regression. In P. J. Bartlett, B. Sch olkopf, D. Schuurmans, and A. J. Smola, editors, Advances in Large Margin Classi ers, pages 115{132. MIT Press, 2000. C.-H. Ho and C.-J. Lin. Large-scale linear support vector regression. Journal of Machine Learning Research, 13:3323{3348, 2012. URL http://www.csie.ntu. edu.tw/~cjlin/papers/linear-svr.pdf. K. J arvelin and J. Kek al ainen. Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems, 20(4):422{446, 2002. T. Joachims. Making large-scale SVM learning practical. In B. Sch olkopf, C. J. C. Burges, and A. J. Smola, editors, Advances in Kernel Methods { Support Vector Learning, pages 169{184, Cambridge, MA, 1998. MIT Press. T. Joachims. A support vector method for multivariate performance measures. In Proceedings of the Twenty Second International Conference on Machine Learning (ICML), 2005. T. Joachims. Training linear SVMs in linear time. In Proceedings of the Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing, 2006. G. S. Kimeldorf and G. Wahba. A correspondence between Bayesian estimation on stochastic processes and smoothing by splines. The Annals of Mathematical Statistics, pages 495{502, 1970. D. E. Knuth. The Art of Computer Programming, volume 3. Addison-Wesley, Reading, MA, 1973. C.-J. Lin and J. J. Mor e. Newton's method for large-scale bound constrained problems. SIAM Journal on Optimization, 9:1100{1127, 1999. C.-J. Lin, R. C. Weng, and S. S. Keerthi. Trust region Newton method for largescale logistic regression. Journal of Machine Learning Research, 9:627{650, 2008. URL http://www.csie.ntu.edu.tw/~cjlin/papers/logistic.pdf. K.-Y. Lin. Data selection techniques for large-scale rankSVM. Master's thesis, Department of Computer Science and Information Engineering, National Taiwan University, 2010. O. L. Mangasarian. A nite Newton method for classi cation. Optimization Methods and Software, 17(5):913{929, 2002. A. Mohan, Z. Chen, and K. Weinberger. Web-search ranking with initialized gradient boosted regression trees. In JMLR Workshop and Conference Proceedings: Workshop on Yahoo! Learning to Rank Challenge, volume 14, pages 77{89, 2011. Y. Niu, Y. Wang, G. Sun, A. Yue, B. Dalessandro, C. Perlich, and B. Hamner. The Tencent dataset and KDD-Cup'12. In ACM SIGKDD KDD-Cup WorkShop, 2012. T. Qin, T.-Y. Liu, J. Xu, and H. Li. LETOR: A benchmark collection for research on learning to rank for information retrieval. Information Retrieval, 13(4):346{ 374, 2010. D. Sculley. Large scale learning to rank. In NIPS 2009 Workshop on Advances in Ranking. 2009. T. Steihaug. The conjugate gradient method and trust regions in large scale optimization. SIAM Journal on Numerical Analysis, 20:626{637, 1983. C. H. Teo, S. Vishwanathan, A. Smola, and Q. V. Le. Bundle methods for regularized risk minimization. Journal of Machine Learning Research, 11:311{365, 2010. V. Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, New York, NY, 1995. K.-W. Wu, C.-S. Ferng, C.-H. Ho, A.-C. Liang, C.-H. Huang, W.-Y. Shen, J.-Y. Jiang, M.-H. Yang, T.-W. Lin, C.-P. Lee, P.-H. Kung, C.-E. Wang, T.-W. Ku, C.-Y. Ho, Y.-S. Tai, I.-K. Chen, W.-L. Huang, C.-P. Chou, T.-J. Lin, H.-J. Yang, Y.-K. Wang, C.-T. Li, S.-D. Lin, and H.-T. Lin. A two-stage ensemble of diverse models for advertisement ranking in KDD Cup 2012. In ACM SIGKDD KDD-Cup WorkShop, 2012. H. Yu, J. Kim, Y. Kim, S. Hwang, and Y. H. Lee. An e cient method for learning nonlinear ranking SVM functions. Information Sciences, 209:37{48, 2012. G.-X. Yuan, C.-H. Ho, and C.-J. Lin. Recent advances of large-scale linear classi cation. Proceedings of the IEEE, 100(9):2584{2603, 2012. URL http: //www.csie.ntu.edu.tw/~cjlin/papers/survey-linear.pdf. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/6237 | - |
dc.description.abstract | 在排序學習中,線性排序支持向量機是一個廣泛使用的方法。雖然其排序表現可
能較核排序支持向量機以及決策樹組合模型等非線性方法為差,但因可以快速地得 到一個基準模型作為比較,因此此模型仍相當有用。有許多研究探討了線性支持向 量機,他們主要的著眼點為當資料中形成的成對偏好量極大時的計算效率。在本論 文中,我們系統地回顧了過往的研究,討論其中的優缺點並提出一個有效率的演算 法。我們也探討了各種實作議題以及可能的延伸並以詳細的實驗驗證。最後,我們 將此論文中提出的演算法實作為一套公開工具以供使用。 | zh_TW |
dc.description.abstract | Linear rankSVM is one of the widely used methods for learning to rank. Although
its performance may be inferior to nonlinear methods such as kernel rankSVM and gradient boosting decision trees, linear rankSVM is useful to quickly produce a baseline model. Furthermore, following the recent development of linear SVM for classi cation, linear rankSVM may give competitive performance for large and sparse data. Many existing works have studied linear rankSVM. Their focus is on the computational e ciency when the number of preference pairs is large. In this thesis, we systematically study past works, discuss their advantages/disadvantages, and propose an e cient algorithm. Di erent implementation issues and extensions are discussed with detailed experiments. Finally, we develop a robust linear rankSVM tool for public use. | en |
dc.description.provenance | Made available in DSpace on 2021-05-16T16:23:50Z (GMT). No. of bitstreams: 1 ntu-102-R00922098-1.pdf: 1483921 bytes, checksum: 3b476cbbade290c0a879a96551e6e256 (MD5) Previous issue date: 2013 | en |
dc.description.tableofcontents | 口試委員會審定書: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : i
中文摘要: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : ii ABSTRACT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iii LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : vi LIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : vii CHAPTER I. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 II. Ecient Calculation Over Relevance Pairs . . . . . . . . . . . . 6 2.1 Newton, Truncated Newton and Trust Region Newton Methods 6 2.2 Ecient Function/Gradient Evaluation and Matrix-vector Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.3 A Direct Method to Calculate . . . . . .. . . . . . .12 2.4 Ecient Calculation by Storing Values in an Order-statistic Tree 14 2.5 A Dierent Implementation by Storing Keys in Leaves of a Tree 19 2.6 A Discussion on Tree Implementations . . . . . . . . . . . . . . 20 III. Comparison with Existing Methods . . . . . . . . . . . . . . . . . 22 3.1 PRSVM and PRSVM+ . . . . . . . . . . . . . . . . . . . . . . . 22 3.2 TreeRankSVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.3 soa-ml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 IV. Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 4.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . 25 4.2 A Comparison Between Methods in Chapter II: a Direct Counting Method and Dierent Order-statistic Trees . . . . . . . . . 26 4.3 A Comparison Between Dierent Methods for Linear RankSVM 27 4.4 A Comparison Between Linear RankSVM, Linear Support Vector Regression, GDBT, and Random Forest . . . . . . . . . . . 32 4.5 A Comparison Between Linear and Nonlinear Models on Sparse Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 V. Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.1 Using Partial Pairs to Train Models . . . . . . . . . . . . . . . 39 5.2 The Possibility of Solving the Dual Problem . . . . . . . . . . . 41 5.3 Extension to Kernel RankSVM . . . . . . . . . . . . . . . . . . 42 5.4 Optimize the Measurement via Weighting . . . . . . . . . . . . 44 5.5 Nonlinear Approach Without Kernel . . . . . . . . . . . . . . . 46 VI. Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 APPENDICES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 49 BIBLIOGRAPHY : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56 v | |
dc.language.iso | en | |
dc.title | 大規模線性排序支持向量機 | zh_TW |
dc.title | Large-scale Linear RankSVM | en |
dc.type | Thesis | |
dc.date.schoolyear | 101-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 林軒田(Hsuan-Tien Lin),李育杰(Yuh-Jye Lee) | |
dc.subject.keyword | 大規模學習,排序支持向量機, | zh_TW |
dc.subject.keyword | Learning to rank,Ranking support vector machines,Large-scale learning,Linear model, | en |
dc.relation.page | 59 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2013-07-04 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-102-1.pdf | 1.45 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。