Bipartite Ranking
A linear predictor for ranking is represented through the output y′ = h_w(x̄).
Two Groups, One Ranking Question
Some ranking problems do not require distinguishing every element from every other element. Instead, the important question is whether each element belongs to one of two groups: relevant or non-relevant. Bipartite ranking is the ranking setting for this two-group case.
The Predictor Output
A linear predictor for ranking is represented by the output y′ = h_w(x̄). Here, h_w(x̄) names the predictor applied to the input representation x̄ using model weights w. The result is the predicted ranking vector y′. The notation h_w(x̄) therefore identifies the step that produces the predictor output; it is not itself the loss function.
Reading a Predictor Output
Suppose a linear ranking predictor receives an input representation x̄ and model weights w. Its output is written as y′ = h_w(x̄). What does each part of this expression represent?
Input: x̄ is the input representation supplied to the predictor.
Prediction rule: h_w denotes the predictor associated with model weights w.
Output: y′ is the predicted ranking vector produced by applying h_w to x̄.
The expression y′ = h_w(x̄) identifies the predictor output before the loss function uses the binary vector induced by that output.
From Scores to Loss
The loss function is a multivariate performance measure. It does not use the predictor output y′ arbitrarily. Instead, it depends on the binary vector induced by y′. The essential reasoning chain is therefore: predictor output, induced binary vector, and then loss.
This means that y′ and the binary vector are different objects. The predictor produces y′. A thresholding rule converts y′ into a binary vector. The loss then depends on that induced binary representation. The loss is not a replacement for the predictor, and the binary vector is not the same thing as the original predicted ranking vector.
Thresholding Each Entry
The predicted ranking vector is converted into binary labels through sign(y′_i - θ). For each entry y′_i, the threshold θ determines whether the corresponding binary output is 1 or -1. The threshold is often set to 0, although additional problem constraints may motivate another value.
Inducing a Binary Vector
Use θ = 0 and suppose the predicted ranking vector is y′ = [2.4, -0.7, 0.3]. Apply sign(y′_i - θ) to each entry.
First entry: For 2.4, subtract θ = 0. The result is positive, so its binary output is 1.
Second entry: For -0.7, subtract θ = 0. The result is negative, so its binary output is -1.
Third entry: For 0.3, subtract θ = 0. The result is positive, so its binary output is 1.
Loss input: The induced binary vector is then the representation passed into the loss dependency described by the source.
The predicted ranking vector [2.4, -0.7, 0.3] induces the binary vector [1, -1, 1] when θ = 0.
Feedback Labels
The feedback vector y uses two labels. An entry of 1 represents a relevant element, while an entry of -1 represents a non-relevant element. These labels express the two groups that define the bipartite ranking problem.
| Feedback entry | Meaning |
|---|---|
| 1 | Relevant element |
| -1 | Non-relevant element |
The two possible labels in the feedback vector y.
Do not confuse the feedback vector y with the predicted ranking vector y′. The feedback vector records the two-label feedback: relevant or non-relevant. The predictor produces y′, and thresholding y′ produces a binary vector that the loss function uses.
Common Reasoning Errors
Treating h_w(x̄) as the loss function.
h_w(x̄) is the predictor output. The loss depends on the binary vector induced by that output.
Fix:
Read the chain in order: predictor output y′, induced binary vector, then loss.Treating y′ as though it were already binary.
The source distinguishes the predictor output from the binary representation used by the loss.
Fix:
Apply sign(y′_i - θ) entry by entry before discussing the loss.Assuming the threshold must always be 0.
The threshold is often 0, but additional problem constraints may motivate another value.
Fix:
Use 0 when appropriate, while checking whether the problem specifies constraints that affect threshold selection.Reversing the meanings of 1 and -1 in the feedback vector.
The feedback vector uses 1 for relevant elements and -1 for non-relevant elements.
Fix:
Keep the label meanings fixed: 1 means relevant and -1 means non-relevant.
Practice the Chain
A predictor produces y′ = [-1.2, 0.4, 2.1]. Using θ = 0, determine the induced binary vector. Then state which object the loss function depends on: y′ itself or the induced binary vector.
Hints
- Apply sign(y′_i - θ) separately to all three entries.
- With θ = 0, compare each entry with zero.
- The loss depends on the binary vector induced by y′.
What do you think happens?
What binary vector is induced by y′ = [-1.2, 0.4, 2.1] when θ = 0?
Reveal answer
Answer: [-1, 1, 1]
The first entry is below 0 and produces -1. The second and third entries are above 0 and produce 1.
Key Takeaways
- Bipartite ranking divides elements into relevant and non-relevant groups.
- The linear ranking predictor produces y′ = h_w(x̄).
- The loss depends on the binary vector induced by y′, not on an unspecified direct replacement of the predictor.
- The conversion uses sign(y′_i - θ), producing 1 or -1 for each entry.
- The threshold is often 0, but additional problem constraints may motivate another value.
- The feedback vector y uses 1 for relevant elements and -1 for non-relevant elements.
Key Takeaways
- Bipartite ranking is a two-label ranking problem involving relevant and non-relevant elements.
- A linear predictor produces the predicted ranking vector y′ = h_w(x̄).
- Thresholding converts y′ into a binary vector using sign(y′_i - θ).
- The loss function depends on that induced binary vector.
- The feedback labels use 1 for relevant and -1 for non-relevant elements.