Multiclass Classification

Ranking problems arrange instances by relevance rather than assigning an isolated label to one instance.

Programming

From Labels to Order

Many prediction tasks ask for a label for one instance. A ranking problem asks a different question: given several instances, how should they be arranged according to relevance? The result is not merely a collection of separate predictions. It is an ordered list, so the position of each instance matters.

Task	What is predicted?	What matters?
Isolated multiclass labeling	A label for one instance	The label assigned to that instance
Ranking	An arrangement of several instances	The relative order and position of the instances

Ranking compares several instances and arranges them by relevance instead of producing isolated labels.

How does ranking several instances by relative relevance differ from assigning one independent class label to each instance?

Ranking Hypothesis Inputs

A ranking hypothesis is written as h. Its input is a sequence of instances, written as x̄ = (x1, . . . , xr), where r is the number of instances in that sequence. The hypothesis does not receive just one instance in isolation. It receives the whole sequence so that the instances can be compared with one another.

The output determines a permutation of the positions 1 through r. This means that the hypothesis preserves the instances themselves but specifies the order in which their positions should be read. A ranking output is therefore an ordering of existing positions, not simply a new collection of unrelated labels.

What data enters a ranking hypothesis, and how is it transformed into scores and an ordered list of instances?

Scores and Ordering

A score vector y provides a convenient representation of a ranking hypothesis output. Each element of y corresponds to one position in the input sequence. To obtain the permutation π(y), sort the elements of y and track their original positions. The sorting supplies the order; the tracked positions identify which original instances occupy that order.

Worked example

Reading a Score Vector

Suppose three instances occupy positions 1, 2, and 3, and the score vector is y = (0.4, 0.9, 0.7). Determine the position assigned to each instance when the scores are sorted in ascending order, then identify the order from highest score to lowest score.

1
Identify the scores
Position 1 has score 0.4, position 2 has score 0.9, and position 3 has score 0.7.
2
Sort the values
In ascending order, the scores are 0.4, 0.7, and 0.9. Their original positions are 1, 3, and 2.
3
Assign sorted positions
The permutation described as the position of each original score in the sorted vector is π(y) = (1, 3, 2). Position 1 receives sorted position 1, position 2 receives sorted position 3, and position 3 receives sorted position 2.
4
Read highest relevance first
The highest value in π(y) identifies the original instance with the highest score. Reading from highest score to lowest score gives original positions 2, 3, and 1.

Result

Ascending sorting exposes π(y) = (1, 3, 2). The corresponding highest-to-lowest score order is positions 2, 3, 1.

How do the scores assigned to multiple instances determine their ranked order?

Permutation Positions

A permutation can be read in two closely related ways. One way lists the original positions in sorted order. The other way assigns each original element the position it occupies in the sorted result. The source notation π(y)i describes the second view: π(y)i is the position of yi in the sorted vector.

These two descriptions use the same sorting operation but answer different reading questions. A sorted-position list tells you which original instance comes first, second, and so on. A position-assignment permutation tells you the sorted position of each original instance. Do not treat the score values and the permutation positions as interchangeable: scores construct the ordering, while permutation positions describe the result of that ordering.

What does each position in the output permutation mean, and which instance occupies that position?

Common Interpretation Errors

Common mistake
Treating a ranking problem as several independent labeling problems
What it looks like
Predicting one label for each instance without specifying how the instances should be ordered
Why it fails
A ranking problem asks for a relevance-based arrangement of several instances, so the relationships between their positions matter.
Do this instead
Begin with the full sequence of instances and describe the ordered positions produced for that sequence.
Common mistake
Confusing a score vector with the permutation
What it looks like
Reading the values 0.4, 0.9, and 0.7 as if they were already the output positions
Why it fails
The scores are used to construct the ordering. The permutation records positions obtained from sorting those scores.
Do this instead
Sort the score values, track their original positions, and then interpret the resulting permutation.
Common mistake
Assuming π(y)i names the instance at sorted position i
What it looks like
Interpreting π(y) = (1, 3, 2) only as the list of instances in sorted order
Why it fails
The source notation describes π(y)i as the position of yi in the sorted vector. That is a position assignment for each original element.
Do this instead
State which reading you are using: a list of original positions in sorted order, or the sorted position assigned to each original score.
Common mistake
Ignoring the distinction between ascending sorting and highest-ranked interpretation
What it looks like
Assuming that the first item in an ascending sort must be the most relevant item
Why it fails
Ascending sorting exposes the permutation mechanically, while top-ranked instances are characterized by the highest values in the permutation positions.
Do this instead
First perform the stated sort, then interpret which permutation positions represent the highest-ranked instances.

MEDIUM

Given three instances with score vector y = (0.2, 0.8, 0.5), write the original positions in ascending score order. Then write the position assigned to each original element in the sorted vector, and identify the highest-to-lowest score order.

Hints

Pair each score with its original position before sorting.
Keep separate the list of positions in sorted order and the position assigned to each original score.
The highest score identifies the first instance when reading from highest to lowest.

Your attempt (not saved)

Key Takeaways

1
A ranking problem arranges several instances by relevance instead of assigning an isolated label to one instance.
2
A ranking hypothesis h receives a sequence of instances x̄ = (x1, . . . , xr) and determines an ordering of positions 1 through r.
3
A score vector y offers a convenient representation of the hypothesis output.
4
The permutation π(y) is obtained by sorting the score values and tracking their original positions.
5
Permutation positions describe the ordering induced by the scores; they should not be confused with the score values themselves.

At a glance

Ranking compares several instances and arranges them by relevance.
A ranking hypothesis maps a sequence of instances to an ordering of their positions.
A score vector induces an ordering when its values are sorted and their original positions are tracked.
The permutation can be read either as sorted original positions or as the sorted position assigned to each original element.
Scores create the ordering, while permutation positions describe that ordering.

More concepts starting with M