Ranking Problems

A multiclass prediction chooses one class for an instance from a finite collection of possible classes. A ranking problem asks for something different: it receives several instances and arranges them according to relevance, so the position of each instance matters. This article connects both ideas. It first traces how binary classifiers can be combined into a multiclass predictor, then shows how scores become an ordering in a ranking problem.

The distinction is important. A class prediction answers, “Which category does this instance belong to?” A ranking prediction answers, “In what order should these instances be considered?” The output of a ranking hypothesis is therefore not an isolated label for each instance. It is an ordering of the positions in the input sequence.

One-versus-All builds one binary problem for each class. Suppose the original task has classes A, B, and C. To train the classifier devoted to A, relabel every example from A as +1 and every example from B or C as -1. Repeat the process for B and then for C. Each binary learner therefore separates one selected class from the rest of the classes.

The relabeling is the central construction step. The examples are not discarded from the original data; their labels are reinterpreted for the selected binary question. The same original training set can therefore produce several binary training sets, one for each class.

After training one binary predictor for every class, One-versus-All applies all of them to a new instance. The class-specific outputs are compared, and the class with the largest output is selected. This is an argmax decision: choose the class whose predictor supplies the greatest value.

All-Pairs uses a different reduction. Instead of training one classifier against the entire remainder, it trains one binary classifier for every pair of distinct classes. For a pair of classes i and j, keep only examples labeled i or j, mark class i as +1, mark class j as -1, and train a predictor for that pair.

With three classes, the pairwise classifiers are class 1 versus class 2, class 1 versus class 3, and class 2 versus class 3. When a new instance is evaluated, these pairwise decisions are converted into wins. The class with the greatest number of wins becomes the final prediction.

A reduction method can make each binary component look reasonable while the combined multiclass predictor behaves poorly. The binary problems do not contain exactly the same information as the original multiclass decision. One-versus-All changes the question into several class-versus-rest questions, while All-Pairs keeps only two classes in each training set. The final rule must reconstruct one coherent multiclass decision from those partial views.

A ranking hypothesis receives a sequence of instances, written as x̄ = (x1, ..., xr), where r is the number of instances. It produces an ordering of the positions 1 through r. One convenient representation is a score vector y: one score for each instance. Sorting the scores and tracking the original positions produces a permutation, written as π(y).

The input is a sequence rather than one isolated instance. The output preserves the instances but specifies the order in which their positions should be read. This makes ranking different from multiclass classification: classification selects a category, while ranking arranges the supplied instances.