LambdaMART Lambda Gradients

Background

LambdaMART approximates gradients of the (non-differentiable) NDCG metric by attaching a per-pair "lambda" weighted by the absolute NDCG change from swapping ranks. The state-of-the-art listwise learning-to-rank algorithm for tabular features for over a decade.

Problem statement

Implement lambda_gradients(scores, labels) returning a length-$n$ array of gradients. For every pair $(i, j)$ with $y_i > y_j$:

$$\rho_{ij} = \sigma(-(s_i - s_j)),\qquad \Delta_{ij} = |\,(\text{gain}(y_i) - \text{gain}(y_j))(\text{disc}(r_i) - \text{disc}(r_j))\,|,\qquad \lambda_{ij} = -\rho_{ij}\cdot\Delta_{ij}$$

where gain $g = 2^y - 1$, discount $d(p) = 1/\log_2(p+1)$, and $r$ is the rank in the current scores. The per-item gradient (for maximising NDCG) is $g_i = \sum_j (\lambda_{ji} - \lambda_{ij})$.

Input

• scores — 1-D array of floats, model output scores.
• labels — 1-D array of integers, graded relevance.

Output

Returns np.ndarray of length $n$, the per-item gradient.

Examples

Example 1 — all same label → zero gradients

scores=[1,2,3], labels=[1,1,1]
Output: all zeros

Example 2 — positive below negative gets pushed up

scores=[1.0, 2.0], labels=[1, 0]
Output: g[0] > 0  and  g[1] < 0

Constraints

• Length mismatch is invalid.
• Walk all pairs $(i, j)$ where $y_i > y_j$ (skip $y_i = y_j$).
• Returns np.ndarray.

Notes

• Why "lambda". Each pair contributes a single quantity (the lambda); summing them gives a gradient. There's no closed-form gradient of NDCG, so we approximate.
• MART = Multiple Additive Regression Trees. The lambdas become regression targets for gradient-boosted trees; that's the full LambdaMART recipe.