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?
- 1Input
x̄ is the input representation supplied to the predictor.
- 2Prediction rule
h_w denotes the predictor associated with model weights w.
- 3Output
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.
- 1First entry
For 2.4, subtract θ = 0. The result is positive, so its binary output is 1.
- 2Second entry
For -0.7, subtract θ = 0. The result is negative, so its binary output is -1.
- 3Third entry
For 0.3, subtract θ = 0. The result is positive, so its binary output is 1.
- 4Loss 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
Common mistake Treating h_w(x̄) as the loss function.
What it looks likeAssuming that y′ = h_w(x̄) is already the final performance measure.
Why it failsh_w(x̄) is the predictor output. The loss depends on the binary vector induced by that output.
Do this insteadRead the chain in order: predictor output y′, induced binary vector, then loss.
Common mistake Treating y′ as though it were already binary.
What it looks likeCalling the predicted ranking vector and the induced vector the same object.
Why it failsThe source distinguishes the predictor output from the binary representation used by the loss.
Do this insteadApply sign(y′_i - θ) entry by entry before discussing the loss.
Common mistake Assuming the threshold must always be 0.
What it looks likeRejecting any threshold other than 0 without considering the problem setting.
Why it failsThe threshold is often 0, but additional problem constraints may motivate another value.
Do this insteadUse 0 when appropriate, while checking whether the problem specifies constraints that affect threshold selection.
Common mistake Reversing the meanings of 1 and -1 in the feedback vector.
What it looks likeInterpreting 1 as non-relevant and -1 as relevant.
Why it failsThe feedback vector uses 1 for relevant elements and -1 for non-relevant elements.
Do this insteadKeep 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
[-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
- 1Bipartite ranking divides elements into relevant and non-relevant groups.
- 2The linear ranking predictor produces y′ = h_w(x̄).
- 3The loss depends on the binary vector induced by y′, not on an unspecified direct replacement of the predictor.
- 4The conversion uses sign(y′_i - θ), producing 1 or -1 for each entry.
- 5The threshold is often 0, but additional problem constraints may motivate another value.
- 6The feedback vector y uses 1 for relevant elements and -1 for non-relevant elements.
At a glance
- 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.