Ranking Support Vector Machine with Kernel Approximation

Kai Chen, Rongchun Li, Yong Dou, Zhengfa Liang, Qi LvComput. Intell. Neurosci 2017 · DOI

TL;DR

This paper tackles the computational bottleneck of kernelized Support Vector Machines for ranking (RankSVM) by introducing kernel approximation techniques. By using Nyström or random Fourier features, they significantly speed up training while maintaining or even improving ranking performance compared to existing methods.

What Problem Does This Paper Address?

Learning to rank (LTR) is crucial for applications like information retrieval and recommender systems, where the goal is to order items based on relevance. RankSVM is a popular LTR algorithm, but its kernelized version, which can handle complex non-linear relationships, suffers from prohibitively long training times. This is because computing and storing the kernel matrix, which involves pairwise comparisons of all data points, scales quadratically with the dataset size. This computational burden limits the applicability of kernel RankSVM to large-scale real-world problems.

Methods

The core innovation of this paper is the application of kernel approximation techniques to RankSVM. Instead of explicitly computing the kernel matrix, they use two methods to approximate the kernel mapping:

  • Nyström Method: This method approximates the kernel matrix with a low-rank matrix by strategically sampling a subset of the data points.
  • Random Fourier Features: This method approximates shift-invariant kernels by mapping data points into a lower-dimensional space using random Fourier features.

After this kernel approximation, the problem is transformed into a linear RankSVM problem in the approximated feature space. The authors then employ a primal truncated Newton method to efficiently optimize the L2-loss (squared Hinge-loss) objective function of this linear RankSVM model. This approach avoids the explicit computation and storage of the full kernel matrix, drastically reducing computational complexity.

Datasets

The authors evaluated their proposed methods on three benchmark datasets from the LETOR (Learning to Rank Datasets) collection:

  • TD2004
  • OHSUMED
  • MQ2007

These datasets are commonly used for evaluating LTR algorithms and contain query-document pairs with relevance labels.

Key Insights and Ideas

  • Kernel Approximation as a Game Changer: The paper demonstrates that kernel approximation is a viable and effective strategy to overcome the scalability issues of kernel RankSVM, a problem that has long hindered its practical application.
  • Nyström vs. Random Fourier Features: While both methods offer significant speedups, the Nyström method generally provides better approximations, especially for smaller sampling sizes, though random Fourier features can be slightly faster.
  • L2-Loss Advantage: The use of the L2-loss (squared Hinge-loss) in conjunction with the primal truncated Newton method proves to be efficient and effective for optimizing the approximated kernel RankSVM.
  • Performance on Par with State-of-the-Art: The proposed methods not only achieve substantial speedups but also deliver competitive or superior ranking performance compared to both linear and kernel-based state-of-the-art algorithms.

Key Results

  • Dramatic Speedup: The proposed kernel approximation methods achieved training times orders of magnitude faster than traditional kernel RankSVM. For example, on the MQ2007 dataset, their methods took about ten seconds, while kernel RankSVM-TRON took over 13 hours.
  • Competitive Performance: The RankNyström and RankRandomFourier methods achieved comparable or better MeanNDCG and MAP scores than existing state-of-the-art ranking algorithms across the tested datasets.
  • Scalability: The performance of the approximation methods improved with an increased number of samples used for approximation, indicating their scalability.

Limitations and Future Work

  • Hyperparameter Tuning: The performance of the kernel approximation methods is sensitive to hyperparameters like the number of samples ($m$) for approximation and the regularization parameter ($C$). Grid search was used for tuning, which can be computationally intensive.
  • Future Directions: The authors suggest exploring more efficient kernel approximation techniques and investigating more advanced ranking models for large-scale ranking problems in future work. They also note that the L2-loss RankSVM can outperform L1-loss RankSVM in some scenarios.

Summary updated

BibTeX
@article{chen2017ranking,
  author = {Kai Chen and Rongchun Li and Yong Dou and Zhengfa Liang and Qi Lv},
  title = {{Ranking Support Vector Machine with Kernel Approximation}},
  journal = {Comput. Intell. Neurosci.},
  year = {2017},
  doi = {10.1155/2017/4629534},
}
Figure