PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer

We focus on the pairwise ranking models because of their advantageous effectiveness reported in prior offline LTR studies (Chapelle and Chang, 2011), and their ability to tackle implicit feedback. Specifically, we adopt a single layer RankNet model with a sigmoid activation function (Burges, 2010) as our pairwise ranker. This choice is based on the promising empirical performance of RankNet and the feasibility of analyzing the resulting online solution’s convergence.

In a single layer RankNet, the probability that a document $i$ is more relevant than document $j$ under query $q$ is computed as $\mathbb{P}(i\succ j|q)=\sigma({\mathbf{x}^{\top}_{i}}\boldsymbol{\theta}-{\mathbf{x}^{\top}_{j}}\boldsymbol{\theta})$, where $\boldsymbol{\theta}\in\mathbb{R}^{d}$ and $\|\boldsymbol{\theta}\|\leq Q$ is the model parameter and $\sigma(x)={1}/({1+\exp(-x)})$. To simplify our notations, we use $\mathbf{x}_{ij}$ to denote $\mathbf{x}_{i}-\mathbf{x}_{j}$ in our subsequent discussions.

With the knowledge of $\boldsymbol{\theta}$, due to the monotonicity and transitivity of the sigmoid function, the ranking of documents in $\mathcal{X}$ can be uniquely determined by $\{{\mathbf{x}^{\top}_{1}}\boldsymbol{\theta},{\mathbf{x}^{\top}_{2}}\boldsymbol{\theta},\dots,{\mathbf{x}^{\top}_{L}}\boldsymbol{\theta}\}$. Therefore, the key of learning a RankNet model is to estimate its parameter $\boldsymbol{\theta}$. As RankNet specifies a distribution on pairwise comparisons, the objective function for $\boldsymbol{\theta}$ estimation can be readily derived as the cross-entropy loss between the predicted pairwise distribution on documents and those inferred from user feedback till round $t$:

where $\lambda$ is the L2 regularization coefficient, $\mathcal{G}_{s}$ denotes the set of document pairs that received different click feedback at round $s$, i.e., $\mathcal{G}_{s}=\{(m,n):c_{m}^{s}\neq c_{n}^{s},\forall\tau(m)<\tau(n)\leq o_{s}\}$, ${\mathbf{y}_{mn}^{s}}$ indicates whether the document $m$ is preferred over document $n$ in the click feedback, i.e., ${\mathbf{y}_{mn}^{s}}=\frac{1}{2}(c_{m}^{t}-c_{n}^{t})+\frac{1}{2}$ (Burges, 2010). Due to the log-convexity of the loss function defined in Eq (1), the global optimal solution $\hat{\boldsymbol{\theta}}_{t}$ at round $t$ exists and can be efficiently obtained by gradient descent.

Online learning of RankNet boils down to the construction of $\{\mathcal{G}_{s}\}^{T}_{s=1}$ over time. However, the conventional practice of using all the inferred pairwise preferences from click feedback (Joachims, 2002; Agichtein et al., 2006) imposes a higher risk in an online setting. In the presence of click noise (e.g., a user mistakenly clicks on an irrelevant document), pairing documents would cause a quadratically increasing number of noisy training instances, which impose strong negative impact on the quality of the learned ranker (Carvalho et al., 2008). As the updated ranker is immediately executed, cascading of ranker deterioration is possible. To alleviate this deficiency, we propose to only use independent pairs inferred from the feedback, e.g., $\mathcal{G}_{s}^{ind}=\{(m,n):c_{m}^{s}\neq c_{n}^{s},\forall(\tau_{s}(m),\tau_{s}(n))\in D\}$, where $D$ represents the set of disjointed position pairs, for example, $D=\{(1,2),(3,4),...(L-1,L)\}$. In other words, we will only use a subset of non-overlapping pairwise comparisons for our online ranker update.

As discussed in Section 3.1, $\hat{\boldsymbol{\theta}}_{t}$ is obtained based on the acquired feedback from what has been presented to the user, which is subject to various types of biases and noises (Joachims et al., 2005; Agichtein et al., 2006; Joachims et al., 2007). Hence, $\hat{\boldsymbol{\theta}}_{t}$ only reflects what the ranker knows so far; and it is vital to effectively explore the unknowns to complete its knowledge. In PairRank, we propose to explore in the pairwise document ranking space spanned by $\mathcal{X}_{t}$ under $q_{t}$, with respect to the current ranker’s uncertainty about the pairwise comparisons.

Accurate quantification of the current ranker’s uncertainty on pairwise preference estimation is the key to such exploration. The model estimation uncertainty is caused by the existence of click noise, i.e., $\|\hat{\boldsymbol{\theta}}_{t}-\boldsymbol{\theta}^{*}\|\neq 0$, where $\boldsymbol{\theta}^{*}$ is the underlying ground-truth model parameter. And this model estimation uncertainty directly leads to the uncertainty in the ranker’s pairwise preference estimation. To quantify the source of uncertainty, we follow conventional click models to assume the clicks are independent of each other given the true relevance of documents, so as their noise (Joachims et al., 2005; Guo et al., 2009b; Guo et al., 2009a). As a result, the pairwise noise becomes the sum of noise from the two associated clicks. Because we only use the independent document pairs $\mathcal{G}^{ind}$, the pairwise noise is thus independent of each other in PairRank and the history of result serving, which directly leads to the following proposition.

According to the property of sub-Gaussian random variables, such assumption can be easily satisfied in practice as long as the pointwise click noise follows a sub-Gaussian distribution. For example, the pointwise noise can be modeled as a binary random variable related to the document’s true relevance under the given query, which follows $\frac{1}{2}$-sub-Gaussian distribution.

Therefore, based on the solution of Eq (1), the uncertainty of the estimated pairwise preference $\sigma({\mathbf{x}_{ij}^{t}}^{\top}\hat{\boldsymbol{\theta}}_{t})$ by RankNet at round $t$ can be analytically bounded with a high probability, as shown in the following lemma.

The detailed proof of Lemma 2 can be found in the appendix. This lemma provides a tight high probability bound of the pairwise preference estimation uncertainty under a RankNet specified by $\hat{\boldsymbol{\theta}}_{t}$, which enables us to perform efficient pairwise exploration for model update. To better illustrate our exploration strategy based on the pairwise estimation uncertainty, we introduce the following definition on document pairs.

Intuitively, based on Lemma 2, if $(i,j)$ is in a certain rank order, with a high probability that the estimated preference (order) between document $i$ and $j$ is consistent with the ground-truth. For example, as shown in Figure 2, $\hat{\sigma}^{t}_{ij}$ and $\hat{\sigma}_{mn}^{t}$ represent the estimated pairwise preference on document pair $(i,j)$ and $(m,n)$ based on $\hat{\boldsymbol{\theta}}_{t}$, while $CB_{ij}^{t}$ and $CB_{mn}^{t}$ represent the corresponding confidence bound defined in Lemma 2, i.e., $CB_{ij}^{t}=\alpha_{t}\|{\mathbf{x}_{ij}^{t}}\|_{\mathbf{M}_{t}^{-1}}$ and $CB_{mn}^{t}=\alpha_{t}\|{\mathbf{x}_{mn}^{t}}\|_{\mathbf{M}_{t}^{-1}}$. According to Lemma 2, we know that the ground-truth pairwise preferences, $\sigma_{ij}^{*}$ and $\sigma_{mn}^{*}$, lie within the corresponding confidence intervals with a probability at least $1-\delta_{1}$, i.e., $\sigma_{ij}^{*}\in[\hat{\sigma}_{ij}^{t}-CB_{ij}^{t},\hat{\sigma}_{ij}^{t}+CB_{ij}^{t}]$. In Figure 2, for pair $(m,n)$, the lower bound of its pairwise estimation, $\hat{\sigma}_{mn}^{t}-CB_{mn}^{t}$, is greater than $\frac{1}{2}$. This indicates that with a high probability $1-\delta_{1}$, the estimated preference between document $m$ and $n$ is consistent with the ground-truth model $\boldsymbol{\theta}^{*}$; and thus there is no need to explore this pair. In contrast, with $\hat{\sigma}_{ij}^{t}-CB_{ij}^{t}<\frac{1}{2}$, the estimated order $(i\succ j)$ is still with uncertainty as the ground-truth model may present an opposite order; hence, exploration on this pair is necessary.

We use $\mathcal{E}_{c}^{t}$ to represent the set of all certain rank orders at round $t$. Accordingly, the set of uncertain rank orders at round $t$ is defined as: $\mathcal{E}_{u}^{t}=\{(i,j)\in[L_{t}]^{2}:(i,j)\notin\mathcal{E}_{c}^{t}\wedge(j,i)\notin\mathcal{E}_{c}^{t}\}$.

With the aforementioned pairwise estimation uncertainty and the corresponding sets of certain and uncertain rank orders, i.e., $\mathcal{E}_{c}^{t}$ and $\mathcal{E}_{u}^{t}$, we can effectively explore the unknowns. Intuitively, we only need to randomize the ranking of documents among which the model is still uncertain about their ranking orders, i.e., the uncertain rank orders, and therefore obtain feedback to further update the model (and reduce uncertainty). For example, in the document graph shown in Figure 1, the solid lines represent certain rank orders, while the dash lines represent the uncertain rank orders. When generating the ranked list, we should randomly swap the order between document 1 and 2 (i.e., to explore) while preserving the order between document 1 and documents 3, 4, 5 (i.e., to exploit).

This naturally leads to a divide-and-conquer exploration strategy in the space of pairwise document comparisons. Specifically, we partition $\mathcal{X}_{t}$ into different parts (referred to as blocks hereafter) based on $\mathcal{E}_{c}^{t}$ and $\mathcal{E}_{u}^{t}$ such that the ranking orders between any documents belonging to different blocks are certain, shown in the block graph in Figure 1. The ranked list can thus be generated by topological sort across blocks and random shuffling within each block. As the exploration is confined to the pairwise ranking space, it effectively reduces the exponentially sized action space to quadratic.

Algorithm 1 shows the detailed steps of PairRank. At round t, we first construct $\mathcal{E}_{c}^{t}$ and $\mathcal{E}_{u}^{t}$ according to the current mode $\hat{\boldsymbol{\theta}}_{t-1}$. Then, we create blocks of $\mathcal{X}_{t}$ according to the definition below.

Intuitively, each block is a subset of documents linked to each other by the uncertain rank order. It can be viewed as a connected component in an undirected graph with documents as vertices and uncertain rank order as edges under a given query. The connected components (blocks) can be found by linearly scanning through the vertices, based on breadth-first search or depth-first search if a vertex is not visited before. When the algorithm stops, each vertex (document) will be assigned to a connected component (block). Once the blocks are constructed, the order of the blocks can be obtained by topological sort (line 6). Let $\mathcal{B}_{t}=\{\mathcal{B}_{1}^{t},\mathcal{B}_{2}^{t},...\mathcal{B}_{d_{t}}^{t}\}$ be the ordered block list for $\mathcal{X}_{t}$ at round $t$, the ranked list $\tau_{t}$ is generated as $\tau_{t}=\{\pi(\mathcal{B}_{1}^{t}),\pi(\mathcal{B}_{1}^{t}),...,\pi(\mathcal{B}_{d_{t}}^{t})\}$, where $\pi(\cdot)$ randomly permutes its input set as output.

To further improve exploration efficiency, we propose two options to generate the ranked list. As shown in Figure 1, the first ranked list is generated by randomly shuffling all documents within each block (referred to as random exploration), while in the second list, only the uncertain rank orders are shuffled, and the certain ones are preserved (referred to as conservative exploration). In our empirical studies, we observe such conservative exploration gives better improvement than random exploration, which further confirms the importance of efficient exploration in OL2R.

In offline evaluation, while the algorithm is learning, we evaluate the learned rankers on a separate testing set using its ground-truth relevance labels. We use Normalized Discounted Cumulative Gain at 10 (NDCG@10) to assess different algorithms’ ranking quality. We compare all algorithms over 3 click models and 2 datasets. We set the hyper-parameters, such as learning rate, in DBGD, MGD, and PDGD according to their original papers. For SGD RankNet, $\epsilon$-Greedy, and our proposed PairRank, we set the hyper-parameters via the best performance on the validation data for each dataset. We fix the total number of iterations $T$ to 5000. We execute the experiments 20 times with different random seeds and report the averaged result in Figure 3. For comparison purposes, we also include the performance of an offline RankNet trained on the ground-truth relevance labels on the training set, whose performance can be considered as an upper bound in our evaluation.

We can clearly observe that PairRank achieved significant improvement over all the baselines. Across the two datasets under different click models, DBGD and MGD performed worse than other OL2R solutions. This is consistent with previous studies’ findings: DBGD and MGD depend on interleave test to determine the update direction across rankers. But such model-level feedback is hard to directly inform the optimization of any rank-based metric (e.g., NDCG). PDGD consistently outperformed DBGD-type solutions under different click models and datasets. However, its document sampling-based exploration limits its learning efficiency, especially when users only examine a small number of documents (e.g., the navigational users). $\epsilon$-Greedy seriously suffered from its random exploration, which is independent of how the current ranker performs. Oftentimes as shown in Figure 3(a), its performance is even worse than MGD, although $\epsilon$-Greedy can directly optimize the pairwise ranking loss. One interesting observation is that SGD RankNet performs comparably to PDGD. Exploration in SGD RankNet is implicitly achieved via stochastic gradient descent. However, because this passive exploration is subject to the given queries and noise in user feedback, its performance in online result serving is hard to predict. We attribute PairRank’s fast convergence to its uncertainty based exploration: it only explores when its estimation on a pair of documents is uncertain. As proved in our regret analysis, the number of such pairs shrinks at a logarithmic rate, such that more and more documents are presented in their correct ranking positions as PairRank learns from user feedback. This conclusion is further backed by the comparison between PairRank_R and PairRank_C: by respecting the certain rank orders within a partition, PairRank_C further improves result ranking quality. When click noise is small, i.e., from perfect users, PairRank converges to its offline counterpart with only a few thousand impressions.

In OL2R, in addition to the offline evaluation, a model’s ranking performance during online optimization should also be evaluated, as it reflects user experience. Sacrificing user experience for model training will compromise the goal of OL2R. We adopt the cumulative Normalized Discounted Cumulative Gain (Oosterhuis and de Rijke, 2018) to assess models’ online performance. For $T$ rounds, the cumulative NDCG (cNDCG) is calculated as

which computes the expected NDCG reward a user receives with a probability $\gamma$ that he/she stops searching after each query (Oosterhuis and de Rijke, 2018). Following the previous work (Oosterhuis and de Rijke, 2018; Wang et al., 2019; Wang et al., 2018a), we set $\gamma=0.9995$.

Figure 4 shows the online performance of PairRank and all the other baselines. It is clear to observe that directly adding model-independent exploration, e.g., $\epsilon$-greedy, strongly hurts a model’s online ranking performance, and therefore hurts user experience. Compared to PDGD, SGD RankNet showed consistently better performance, especially under the navigational and informational click models. We attribute this difference to the exploration strategy inside PDGD: though SGD RankNet has limited exploration and focuses more on exploiting the learned model in ranking the documents, PDGD’s sampling-based exploration might introduce unwanted distortion in the ranked results, especially at the early stage of online learning.

We should note in cumulative NDCG, the earlier stages play a much more important role due to the strong shrinking effect of $\gamma$. Our proposed PairRank demonstrated significant improvements over all the baselines. Such improvement indicates the effectiveness of our uncertainty based exploration, which only explores when the ranker’s pairwise estimation is uncertain. We can also observe the difference between PairRank_C and PairRank_R in this online evaluation. This is because PairRank_C preserves the certain rank order within blocks, which further eliminates unnecessary exploration (random shuffling) in result serving.

In this experiment, we view the offline trained RankNet model on the complete annotated relevance as the ideal model, denoted as $w^{*}$, and compare the cosine similarities between $w^{*}$ and the online estimated models in Figure 5. We can observe that all the pairwise models push the learned ranker closer to the ideal one with more iterations, while PairRank converges faster and closer to $w^{*}$. Apparently, the rankers obtained by DBGD and MGD are quite different from the ideal model. This confirms our earlier analysis that DBGD-type ranker update can hardly link to any rank-based metric optimization, and thus it becomes less related to the offline learned ranker. The difference in objective function can also explain why SGD RankNet converges faster than PDGD, as PDGD adopts the pairwise Plackett-Luce model while SGD RankNet has the same objective function as the offline model.

To further verify the effectiveness of the exploration strategy devised in PairRank, we zoom into the trace of its block size across queries during the online model update. As PairRank uses random shuffling within each block for exploration, a smaller block size, especially at the top-ranked positions, is preferred to reduce regret. Figure 6 shows the size of document blocks at rank position 1, 5 and 10.

First, we can clearly observe that after hundred rounds of interactions, the sizes of blocks quickly converge to 1, especially at the top-ranked positions. This confirms our theoretical analysis about PairRank’s block convergence. And by comparing the results across different click models, we can observe that the block size converges slower under the navigational click model. Similar trends can be observed in Figure 7(b). In this figure, the number of blocks is calculated by averaging in every 200 iterations to reduce variance. We can observe that at the early stages, PairRank under the navigational click model has fewer blocks (hence more documents in one block), which indicates a higher uncertainty in model estimation. The key reason is that much fewer clicks can be observed in each round under the navigational click model, as the stop probability is much higher, i.e., stronger position bias. As a result, more interactions are needed to improve model estimation. For the same reason, in Figure 6, the block size at rank position 10 shrinks much slower than that at other positions also suggests position bias is the main factor that slows down the learning of PairRank.

In Figure 7(a), we show the block size at each rank position in PairRank under the informational click model at different time points. One interesting finding is the blocks in the middle ranks, i.e., rank 300 - 400, tend to have more documents, while for the ranks at both the top and the bottom, the corresponding blocks tend to have fewer documents. We attribute it to the pairwise learning in PairRank, where the uncertainty is calculated on the pairwise preferences, and thus it is easy to identify the document pairs with greater differences.