XGBoost › Ranking Example

Let's work through a concrete ranking example to demonstrate how XGBoost handles learning-to-rank problems. We'll use a search engine scenario where we want to rank documents for a given query.

Consider a query "machine learning tutorial" with 4 documents that need to be ranked:

Step 1: Initialize predictions We start with initial predictions (typically zeros or small random values):

• Doc 1: $\hat{y}^{(0)}_1 = 0$
• Doc 2: $\hat{y}^{(0)}_2 = 0$
• Doc 3: $\hat{y}^{(0)}_3 = 0$
• Doc 4: $\hat{y}^{(0)}_4 = 0$

Step 2: Calculate pairwise ranking loss For the pairwise ranking loss, we consider all pairs where one document should be ranked higher than another based on relevance scores.

Relevant pairs (Doc i should rank higher than Doc j):

• (Doc 1, Doc 2): relevance 3 > 1
• (Doc 1, Doc 3): relevance 3 > 2
• (Doc 1, Doc 4): relevance 3 > 2
• (Doc 3, Doc 2): relevance 2 > 1
• (Doc 4, Doc 2): relevance 2 > 1

The pairwise loss for each pair $(i,j)$ is:

$$L_{ij} = \log(1 + \exp(-(\hat{y}_i - \hat{y}_j)))$$

Since all initial predictions are 0, the loss for each pair is:

$$L_{ij} = \log(1 + \exp(-(0 - 0))) = \log(1 + 1) = \log(2) \approx 0.693$$

Step 3: Calculate gradients for ranking For ranking problems, the gradient calculation is more complex as it involves the pairwise relationships. The gradient for document $i$ is:

$$g_i = \sum_{j: rel_i > rel_j} \frac{\exp(-(\hat{y}_i - \hat{y}_j))}{1 + \exp(-(\hat{y}_i - \hat{y}_j))} - \sum_{j: rel_j > rel_i} \frac{\exp(-(\hat{y}_j - \hat{y}_i))}{1 + \exp(-(\hat{y}_j - \hat{y}_i))}$$

With initial predictions of 0, this simplifies to:

• Doc 1: $g_1 = 3 \times 0.5 - 0 = 1.5$ (should rank higher than 3 docs)
• Doc 2: $g_2 = 0 - 3 \times 0.5 = -1.5$ (should rank lower than 3 docs)
• Doc 3: $g_3 = 1 \times 0.5 - 1 \times 0.5 = 0$ (should rank higher than 1, lower than 1)
• Doc 4: $g_4 = 1 \times 0.5 - 1 \times 0.5 = 0$ (should rank higher than 1, lower than 1)

Step 4: Build the first ranking tree Let's say we create a tree that splits on the first feature < 0.75:

• Left leaf (feature 1 < 0.75): Doc 2, Doc 4
• Right leaf (feature 1 ≥ 0.75): Doc 1, Doc 3

For the left leaf:

$$w_{left} = -\frac{g_2 + g_4}{h_2 + h_4 + \lambda} = -\frac{-1.5 + 0}{2 + \lambda}$$

For the right leaf:

$$w_{right} = -\frac{g_1 + g_3}{h_1 + h_3 + \lambda} = -\frac{1.5 + 0}{2 + \lambda}$$

With $\lambda = 1$:

• $w_{left} = \frac{1.5}{3} = 0.5$
• $w_{right} = -\frac{1.5}{3} = -0.5$

Step 5: Update predictions After the first tree:

• Doc 1: $\hat{y}^{(1)}_1 = 0 + (-0.5) = -0.5$
• Doc 2: $\hat{y}^{(1)}_2 = 0 + 0.5 = 0.5$
• Doc 3: $\hat{y}^{(1)}_3 = 0 + (-0.5) = -0.5$
• Doc 4: $\hat{y}^{(1)}_4 = 0 + 0.5 = 0.5$

The ranking after the first tree is: Doc 2, Doc 4 (tied), Doc 1, Doc 3 (tied). This is not the correct ranking yet, so subsequent trees will continue to refine the predictions to achieve the desired ranking order.