大規模線性排序支持向量機

Large-scale Linear RankSVM

李靜沛(Ching-Pei Lee)

指導教授 ： 林智仁

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2013年)

https://doi.org/10.6342/NTU.2013.00305

摘要

在排序學習中，線性排序支持向量機是一個廣泛使用的方法。雖然其排序表現可
能較核排序支持向量機以及決策樹組合模型等非線性方法為差，但因可以快速地得
到一個基準模型作為比較，因此此模型仍相當有用。有許多研究探討了線性支持向
量機，他們主要的著眼點為當資料中形成的成對偏好量極大時的計算效率。在本論
文中，我們系統地回顧了過往的研究，討論其中的優缺點並提出一個有效率的演算
法。我們也探討了各種實作議題以及可能的延伸並以詳細的實驗驗證。最後，我們
將此論文中提出的演算法實作為一套公開工具以供使用。

關鍵字

大規模學習 ； 排序支持向量機

並列摘要

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.

並列關鍵字

Learning to rank ； Ranking support vector machines ； Large-scale learning ； Linear model

參考文獻

C.-H. Ho and C.-J. Lin. Large-scale linear support vector regression. Journal of

A. Airola, T. Pahikkala, and T. Salakoski. Training linear ranking SVMs in linearithmic

1336, 2011.

A. Andersson. Balanced search trees made simple. In Proceedings of the Third

Workshop on Algorithms and Data Structures, pages 60{71, 1993.