In machine learning, a Ranking SVM is an variant of the support vector machine algorithm, which is used to solve certain ranking problems (via learning to rank). The ranking SVM algorithm was published by Thorsten Joachims in 2003. The original purpose of the algorithm was to improve the performance of an internet search engine. However, it was found that Ranking SVM also can be used to solve other problems such as Rank SIFT.
Contents
Description
The Ranking SVM algorithm is a learning retrieval function that employs pair-wise ranking methods to adaptively sort results based on how 'relevant' they are for a specific query. The Ranking SVM function uses a mapping function to describe the match between a search query and the features of each of the possible results. This mapping function projects each data pair (such as a search query and clicked web-page, for example) onto a feature space. These features are combined with the corresponding click-through data (which can act as a proxy for how relevant a page is for a specific query) and can then be used as the training data for the Ranking SVM algorithm.
Generally, Ranking SVM includes three steps in the training period:
- It maps the similarities between queries and the clicked pages onto a certain feature space.
- It calculates the distances between any two of the vectors obtained in step 1.
- It forms an optimization problem which is similar to a standard SVM classification and solves this problem with the regular SVM solver.
Ranking Method
Suppose
Kendall’s Tau
Kendall's Tau also refers to Kendall tau rank correlation coefficient, which is commonly used to compare two ranking methods for the same data set.
Suppose
where
Information Retrieval Quality
Information retrieval quality is usually evaluated by the following three measurements:
- Precision
- Recall
- Average Precision
For a specific query to a database, let
where
Let
where
SVM Classifier
Suppose
The solution of the above optimization problem can be represented as a linear combination of the feature vectors
where
Loss Function
Let
The negative
where
Since the expected loss function is not applicable, the following empirical loss function is selected for the training data in practice.
Collecting training data
Feature Space
A mapping function
Optimization problem
The points generated by the training data are in the feature space, which also carry the rank information (the labels). These labeled points can be used to find the boundary (classifier) that specifies the order of them. In the linear case, such boundary (classifier) is a vector.
Suppose
The above optimization problem is identical to the classical SVM classification problem, which is the reason why this algorithm is called Ranking-SVM.
Retrieval Function
The optimal vector
So the retrieval function could be formed based on such optimal classifier.
For new query
Application of Ranking SVM
Ranking SVM can be applied to rank the pages according to the query. The algorithm can be trained using click-through data, where consists of the following three parts:
- Query.
- Present ranking of search results
- Search results clicked on by user
The combination of 2 and 3 cannot provide full training data order which is needed to apply the full SVM algorithm. Instead, it provides a part of the ranking information of the training data. So the algorithm can be slightly revised as follows.
The method