In machine learning, a ranking SVM is a 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 2002. 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.
Description
The ranking SVM algorithm is a learning retrieval function that employs pairwise 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.
Background
Ranking method
Suppose is a data set containing elements . is a ranking method applied to . Then the in can be represented as a binary matrix. If the rank of is higher than the rank of , i.e. , the corresponding position of this matrix is set to value of "1". Otherwise the element in that position will be set as the value "0".
Kendall's tauA. Mood, F. Graybill, and D. Boes. Introduction to the Theory of Statistics. McGraw-Hill, 3rd edition, 1974
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 and are two ranking method applied to data set , the Kendall's Tau between and can be represented as follows:
where is the number of concordant pairs and is the number of discordant pairs (inversions). A pair and is concordant if both and agree in how they order and . It is discordant if they disagree.
Information retrieval qualityY. Yao. "Measuring retrieval effectiveness based on user preference of documents." Journal of the American Society for Information Science, 46(2): 133–145, 1995.
Information retrieval quality is usually evaluated by the following three measurements: Precision Recall Average precision
For a specific query to a database, let be the set of relevant information elements in the database and be the set of the retrieved information elements. Then the above three measurements can be represented as follows:
where is the of .
Let and be the expected and proposed ranking methods of a database respectively, the lower bound of Average Precision of method can be represented as follows:
where is the number of different elements in the upper triangular parts of matrices of and and is the number of relevant elements in the data set.
SVM classifier
Suppose is the element of a training data set, where is the feature vector and is the label (which classifies the category of ). A typical SVM classifier for such data set can be defined as the solution of the following optimization problem.
The solution of the above optimization problem can be represented as a linear combination of the feature vectors s.
where is the coefficients to be determined.
Ranking SVM algorithm
Loss function
Let be the Kendall's tau between expected ranking method and proposed method , it can be proved that maximizing helps to minimize the lower bound of the Average Precision of . Expected loss runction The negative can be selected as the loss function to minimize the lower bound of average precision of
where is the statistical distribution of to certain query .
Empirical loss function
Since the expected loss function is not applicable, the following empirical loss function is selected for the training data in practice.
Collecting training data
i.i.d. queries are applied to a database and each query corresponds to a ranking method. The training data set has elements. Each element contains a query and the corresponding ranking method.