From RankNET $\to$ LambdaRank $\to$ LambdaMART

Paper Link.

This is an overview paper that explains the model behind LambdaMART, a technique used to learn Gradient Boosted Trees that optimize for NDCG on recommendation-type of datasets.

RankNET

RankNET is a generic framework for training a learn to rank model. Given a differentiable model $f:{\mathbb{R}}^d\mapsto \mathbb{R}$ that produces a score from an n-dimensional input vector, RankNET is able to train $f$ such that for a given query session with items $i=1,...n$ and corresponding features $x_i\in {\mathbb{R}}^d:i=1,...,n$, $f$ learns to predict the relationship $f(x_i)>f(x_j)$ for any two items $i,j$ in the query session when $i$ is a better recommendation than $j$. The differentiable model $f$ is typically a neural network or boosted trees.

RankNET uses revealed pair-wise preferences within each query session to train $f$. Specifically, suppose we have a data for one query session as follows:

We can transform this data into a pairwise dataset as follows, where $y^{jk}$ denotes the preference relationship between $ite{m}^j$ and $ite{m}^k$ which we inferred from the click data. Note that the pairwise comparisons are only made within the same query session (e.g. qid1), as it reflects a given user's preferences in the context of a query and the items impressed to him/her in that session.

The pairwise setting is now more amenable to modelling (compared to directly optimizing for a good ranking), since we can now treat the task as a classification problem. For each row of the pairwise dataset, we only need to model the probability that $ite{m}^j$ is preferred (or not) to $ite{m}^k$. This can be formalized using a cross entropy loss comparing the predicted preference of our model to the revealed preference in the dataset.

First, we model the predicted probability from the model. Given row $i$ of the pairwise dataset and $ite{m}^j$ and $ite{m}^k$ respectively, we model the predicted probability that $ite{m}^j$ is preferred to $ite{m}^k$ (using $▹$ to denote a preference relationship) by passing the score difference between the predicted scores ${\hat{y}}_i^j:=f(x_i^j)$ and ${\hat{y}}_i^k:=f(x_i^k)$ for items j and k respectively through a sigmoid function, like so:

$${\hat{P}}_i^{jk}:=\hat{P}(ite{m}_i^j▹ite{m}_i^k)=\frac{1}{1+exp(-a({\hat{y}}_i^j-{\hat{y}}_i^k))}$$

Now let us denote the revealed probability that $ite{m}^j$ is preferred to $ite{m}^k$ as $P_i^{jk}$ such that:

• $P_i^{jk}=1$ if we prefer item j to item k
• $P_i^{jk}=0.5$ if we have no preference between the two items
• $P_i^{jk}=0$ if we prefer item k to item j

The cross entropy loss of our model can then be expressed as:

$$L=\sum _i\left[-P_i^{jk}log{\hat{P}}_i^{jk}-(1-P_i^{jk})log(1-{\hat{P}}_i^{jk})\right]$$

For convenience, let us denote $y_i^{jk}:=2P_i^{jk}-1$ (and conversely, $P_i^{jk}=\frac{y_i^{jk}+1}{2}$), which translates into the following:

• $y_i^{jk}=1$ if we prefer item j to item k
• $y_i^{jk}=0$ if we have no preference between the two items
• $y_i^{jk}=-1$ if we prefer item k to item j

Let us also define the convenience variable $z:=-log{\hat{P}}_i^{jk}=log\left[1+exp(-a({\hat{y}}_i^j-{\hat{y}}_i^k))\right]$. The cross entropy loss then simplifies to: $$\begin{array}{rl}L& =\sum _i\left[-P_i^{jk}log{\hat{P}}_i^{jk}-(1-P_i^{jk})log(1-{\hat{P}}_i^{jk})\right]\\ & =\sum _i\left[\frac{1}{2}(1+y_i^{jk})z-\frac{1}{2}(1-y_i^{jk})\left[(-a)({\hat{y}}_i^j-{\hat{y}}_i^k)-z\right]\right]\\ & =\sum _i\left[z+\frac{a}{2}(1-y_i^{jk})({\hat{y}}_i^j-{\hat{y}}_i^k)\right]\end{array}$$

Note that in line 2 of the above, we use the useful identity that $log(1-sigmoid(x))=x+log(sigmoid(x))$ and $log{\hat{P}}_i^{jk}=-z$. In line 3, the first and last term of line 2 cancel out to simply return $z$.

Having written out the loss function, we now need to differentiate the loss with respect to the model scores and parameters to obtain the gradient descent formula used to train the RankNET model. Differentiating $L$ wrt ${\hat{y}}_i^j$ and ${\hat{y}}_i^k$ gives:

$$\begin{array}{rl}\frac{\partial L}{\partial {\hat{y}}_i^j}& =\frac{a}{2}(1-y_i^{jk})+\frac{-a\cdot exp(-a({\hat{y}}_i^j-{\hat{y}}_i^k))}{1+exp(-a({\hat{y}}_i^j-{\hat{y}}_i^k))}\\ & =\frac{a}{2}(1-y_i^{jk})-\frac{a}{1+exp(a({\hat{y}}_i^j-{\hat{y}}_i^k))}\\ & =-\frac{\partial L}{\partial {\hat{y}}_i^k}\end{array}$$

Note that the first line of the above uses the result $\frac{d}{dx}lnf(x)=\frac{f^{\prime }(x)}{f(x)}$. We obtain line 2 by multiplying the right term by $exp(a({\hat{y}}_i^j-{\hat{y}}_i^k))$ in both the numerator and denominator. We obtain line 3 by observing that $L$ is a function of $d:={\hat{y}}_i^j-{\hat{y}}_i^k$, such that $\frac{\partial L}{\partial {\hat{y}}_i^j}=\frac{\partial L}{\partial d}\cdot \frac{\partial d}{\partial {\hat{y}}_i^j}=\frac{\partial L}{\partial d}$ and likewise $\frac{\partial L}{\partial {\hat{y}}_i^k}=\frac{\partial L}{\partial d}\cdot \frac{\partial d}{\partial {\hat{y}}_i^k}=-\frac{\partial L}{\partial d}$. The symmetry of the derivative wrt $j$ and $k$ will be important for the next section on factorizing RankNET to speed it up.

Finally, we use the gradient to update individual parameters $w_l\in \mathbb{R}$ of the model $f$. In the below, $n$ denotes the number of data points in the pairwise dataset. This update procedure rounds up the discussion on RankNET and is sufficient for training a generic differentiable model $f$ from ranking data. $$\begin{array}{rl}{w}_l& \leftarrow w_l-\eta \frac{\partial L}{\partial w_l}\\ & =w_l-\frac{\eta }{n}\sum _i\left[\frac{\partial L}{\partial {\hat{y}}_i^j}\cdot \frac{\partial {\hat{y}}_i^j}{\partial w_l}+\frac{\partial L}{\partial {\hat{y}}_i^k}\cdot \frac{\partial {\hat{y}}_i^k}{\partial w_l}\right]\end{array}$$

Factorizing RankNET