(3.239.56.184) 您好!臺灣時間:2021/05/13 12:22
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李靜沛
研究生(外文):Ching-Pei Lee
論文名稱:大規模線性排序支持向量機
論文名稱(外文):Large-scale Linear RankSVM
指導教授:林智仁林智仁引用關係
指導教授(外文):Chih-Jen Lin
口試委員:林軒田李育杰
口試委員(外文):Hsuan-Tien LinYuh-Jye Lee
口試日期:2013-05-17
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:資訊工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:59
中文關鍵詞:大規模學習排序支持向量機
外文關鍵詞:Learning to rankRanking support vector machinesLarge-scale learningLinear model
相關次數:
  • 被引用被引用:0
  • 點閱點閱:220
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在排序學習中,線性排序支持向量機是一個廣泛使用的方法。雖然其排序表現可
能較核排序支持向量機以及決策樹組合模型等非線性方法為差,但因可以快速地得
到一個基準模型作為比較,因此此模型仍相當有用。有許多研究探討了線性支持向
量機,他們主要的著眼點為當資料中形成的成對偏好量極大時的計算效率。在本論
文中,我們系統地回顧了過往的研究,討論其中的優缺點並提出一個有效率的演算
法。我們也探討了各種實作議題以及可能的延伸並以詳細的實驗驗證。最後,我們
將此論文中提出的演算法實作為一套公開工具以供使用。

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.

口試委員會審定書: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : i
中文摘要: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : ii
ABSTRACT : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : iii
LIST OF FIGURES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : vi
LIST OF TABLES : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : vii
CHAPTER
I. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
II. E cient Calculation Over Relevance Pairs . . . . . . . . . . . . 6
2.1 Newton, Truncated Newton and Trust Region Newton Methods 6
2.2 E cient Function/Gradient Evaluation and Matrix-vector Products
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 A Direct Method to Calculate . . . . . .. . . . . . .12
2.4 E cient Calculation by Storing Values in an Order-statistic Tree 14
2.5 A Di erent 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 so a-ml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
IV. Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.1 Experiment Setting . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2 A Comparison Between Methods in Chapter II: a Direct Counting
Method and Di erent Order-statistic Trees . . . . . . . . . 26
4.3 A Comparison Between Di erent 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

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. Scholkopf, 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. Jarvelin and J. Kekalainen. 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. Scholkopf, 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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
系統版面圖檔 系統版面圖檔