Boosting and Perceptron Learning for Ranking

Boosting can be considered to be a greedy algorithm for finding the parameter w that minimize the loss function. w initially is set to (w0,0,...,0), w0 is set based on the base model. When applied to ranking problems, the loss function is an upper bound on the number of "ranking errors", a ranking error being a case where an incorrect candidate gets a higher value than a correct candidate. The iterations is going through all the possible features where a single feature is chosen(greedy) and its weight is updated at each iteration. The number of rounds of iteration will be decided using the cross validation. The final output is the final parameter setting w.

Perceptron algorithm for ranking makes a pass over the traning set instead of features, at each tranining example storing a parameter vector w(i) i=1,2,...,n, which is initially set to be all zeros, only modified when a mistake is made on an example. The update would be the difference of the offending examples' representations(between the 1st rank candidate and the candidate of this example with the highest score based on current w). Generally w(n) is taken as the final parameter to decide the ranking given a new test example. Since during the training, n parameter settings have been constructed, each of which will have its own highest ranking candidate. The idea of taking each of the settings to "vote" for a candidate is called voted perceptron.

The ranking function for both cases: F(x,w)=w*h(x) where h(x) is the feature vectors representing x.