Distributionally Robust Multi-Output Regression Ranking

To compute this vector, first, the elements of ${{\mathbf{y}}}^{q}=(y_{1}^{q},\cdots,y_{n_{q}}^{q})$ are sorted in descending order of their individual relevance scores, and the document feature vectors ${\mathbf{X}}^{q}=({\mathbf{x}}_{1}^{q},\cdots,{\mathbf{x}}_{n_{q}}^{q})$ are also sorted correspondingly. We denote them by $\bar{{\mathbf{y}}}^{q}$ and $\bar{{\mathbf{X}}}^{q}$, respectively. The NDCG score for $\bar{{\mathbf{X}}}^{q}$ is equal to 1. If we switch two documents in $\bar{{\mathbf{X}}}^{q}$, the NDCG will decrease or in some cases may stay the same (i.e., if their relevance scores are equal). For document $d$ in query $q$, we define NDCG deviation score vector as ${\bm{\xi}}_{\Phi}=\left[{\lambda_{d1}},{\lambda_{d2}},...,{\lambda_{d{n_{q}}}}\right]$ where ${\lambda_{di}}$ is the NDCG score of $\bar{{\mathbf{X}}}^{q}$ when we switch the position of document $d$ with the document that is in $i$-th position of $\bar{{\mathbf{X}}}^{q}$ and can be formulated as follows:

Here, $\pi_{d}^{-1}$ is the position of the document $d$ in $\bar{{\mathbf{X}}}^{q}$, $\pi_{i}$ is the index of the document ranked at the $i$-th position of $\bar{{\mathbf{X}}}^{q}$, and $\Phi^{I}$ is the IDCG. The details about the derivation can be found in the supplementary materials. We can perceive the $i$-th element of the GTD vector as a score that indicates the degree of congruence between a document and the $i$-th rank.

This vector is defined to further push the relevant documents to the top of the ranking list, and penalize documents based on their position in the ranking list. Position deviation score works in conjunction with ${\bm{\xi}}_{\Phi}$. We defined it as ${\bm{\xi}}_{D}=\left[{\rho_{d1}},{\rho_{d2}},...,{\rho_{d{n_{q}}}}\right]$ where ${\rho_{di}}$ can be calculated by

where $h_{di}=\pi_{d}^{-1}-i$. As can be seen in Figure 1, $\alpha$ specifies the GTD’s maximum score and $\beta$ regulates the magnitude of the penalty for a position deviation. Here, we use the red dashed curve for positive deviations (i.e., when a document ranked higher than its optimal position) and the black curve for negative deviations. This would induce our model to tolerate a positive deviation more than a negative one. Consequently, the model pushes the relevant documents to the top of the ranking list.

It is defined to place greater emphasis on highly relevant documents and can be computed as follows:

where $\hat{y}$ is the maximum possible value for relevance scores. Figure 1 presents $\xi_{I}$ for different values of $\hat{y}$.

Ultimately, instead of a relevance score for each document, we have a GTD vector. The GTD vector characterizes different levels of importance for a document in a query where the first element is the first level of importance, the second element is the second level of importance, and so on. Since each query may have different number of documents, we just consider the first $K$ elements of ${\bm{\xi}}_{\Phi}$ and ${\bm{\xi}}_{D}$ in our model, corresponding to $K$ levels of importance. In this way, all GTD vectors are the same length. We prefer to use a low value for $K$ since it forces the model to focus on the most relevant documents. In case a large $K$ needs to be used and $K>n_{q}$, we can simply repeat the last element of ${\bm{\xi}}_{\Phi}$ and ${\bm{\xi}}_{D}$ to pad our ${\bm{\xi}}_{\Phi}$ vector.

We conducted experiments on two publicly available benchmark datasets: OHSUMED and Drug Response Prediction (DRP). As a subset of the MEDLINE database (a database on medical publications), the OHSUMED corpus Hersh et al. (1994) consists of about 0.3 million records from 270 medical journals from 1987 to 1991. A query set with 106 queries on the OHSUMED corpus has been extensively used in previous works, in which each query is represented by 45 features Qin et al. (2010). There are in total 16,140 query-document pairs with relevance judgments. LETOR Qin et al. (2010) defined three ratings 0, 1, 2, corresponding to “irrelevant,” “partially relevant,” and “definitely relevant,” respectively. In addition to OHSUMED, we trained and evaluated our method using the cell line data and drug sensitivity data from the Cancer Cell Line Encyclopedia (CCLE) CCLE (2021) and the Cancer Therapeutics Response Portal (CTRP v2) CTRP (2021). A total of 332 cell lines and 50 drug responses were used. The “Act Area” (the area above the fitted dose-response curve) was used to quantify drug sensitivity where lower response value indicates higher drug sensitivity. After several pre-processing steps, cell lines are represented by 251 numeric features (i.e., genes) and drug sensitivities are labeled with graded relevance from 0 to 2 (i.e., “insensitive,” “sensitive,” and “highly sensitive,” respectively) with larger labels indicating a higher sensitivity. Further details of the pre-processing steps can be found in the supplement.

We evaluated model performance using two metrics: NDCG@k and AP@k. NDCG@k is the top-k version of NDCG, where the discount function is $D(s)=0$ for $s>k$. Precision at position k (P@k) is the fraction of relevant documents in the top-k. Suppose we have binary relevance for the documents in a $q$-query; we define P@k as $P@k=\frac{1}{k}\sum_{j=1}^{k}\mathbbm{1}(y_{\pi_{j}}=1)$ where $\mathbbm{1}(\cdot)$ is the indicator function. We define Average Precision at position k as $AP@k=\frac{1}{m}\sum_{j=1}^{k}P@k\times\mathbbm{1}(y_{\pi_{j}}=1)$, where $m$ is the total number of relevant documents in the top-k of the ranking list. AP is a highly localized performance measure and captures the quality of rankings for applications where only the first few results matter. The main difference between AP and NDCG is that NDCG differentiates between “partially relevant” and “definitely relevant” documents while AP treats them equally. Given a set of testing queries and a performance metric, we are interested in the mean metric which is simply the mean of the performance metric for all queries. From now on, we use NDCG@k and AP@k to denote mean NDCG@k and mean AP@k, respectively.

Although the list of published LTR algorithms is endless, LamdaMART_MAP Wu et al. (2010), LamdaMART_NDCG Wu et al. (2010), and XE-MART_NDCG Bruch (2021) have been demonstrated repeatedly to outperfrom other algorithms including RankNet Burges et al. (2005), Coordinate Ascent Metzler and Croft (2007), ListNet Cao et al. (2007), Random Forests Breiman (2001), BoltzRank Volkovs and Zemel (2009), ListMLE Xia et al. (2008), Position-Aware ListMLE Lan et al. (2014), RankBoost Freund et al. (2003), AdaRank Xu and Li (2007), SoftRank Taylor et al. (2008), ApproxNDCG Qin, Liu, and Li (2010), ApproxAP Qin, Liu, and Li (2010), and several direct optimization methods Xu et al. (2008); Metzler, Croft, and McCallum (2005). Here, we rely on prior research Bruch (2021); Wang et al. (2018) and do not include the weaker methods in our experiments. It is important to note that the author of XE-MART_NDCG proposed this model as a robust alternative to LamdaMART-based models. We used open-source python packages (i.e., LightGBM Ke et al. (2017); Meng et al. (2016); Zhang, Si, and Hsieh (2017) and XGBoost Chen and Guestrin (2016)) to implement the baseline models.

In our experiments, we followed the standard supervised LTR framework Liu (2011). Authors of LETOR Qin et al. (2010) partitioned the OHSUMED data set into five parts for five-fold cross-validation where three parts are used for training, one part for validation (i.e., tuning the hyperparameters of the learning algorithms), and the remaining part for evaluating the performance of the learned model. Similarly, we partitioned the drug response data set into five folds and conducted five-fold cross-validation to train, validate and evaluate the ranking algorithms. In all experiments, the average on the test set over the 5 folds was reported. Algorithm parameters were tuned on the validation sets. We optimized the algorithm parameters to maximize NDCG@5 and NDCG@10. The details of the parameter-tuning procedure and the optimal parameters for each algorithm can be found in the supplement.

We added Gaussian noise to the test documents to deliberately corrupt them; therefore, depreciating their predictability. Gaussian noise was added to 75% of the test queries randomly. Experiments were conducted using various means and a fixed standard deviation of 0.001. We used the perturbed test data to evaluate the trained models in Sec. 4.2 (i.e., all algorithms were tested on the same perturbed test data). Fig. 2 demonstrates the performance of the algorithms on the perturbed test data. Two observations are in order: $(i)$ DRMRR outperformed the baseline models at different levels of noise; and $(ii)$ DRMRR demonstrated a relatively stable performance.

We built an adversarial model to introduce perturbations that break the neighborhood relationships by altering the input slightly. To that end, a pointwise linear regression ranking model was trained as the adversarial model on the clean training set. Then, 75% of the test queries were perturbed using the coefficient of the adversarial model and the Fast Gradient Sign Method (FGSM) method: $\bar{\bar{{\mathbf{x}}}}_{q}^{d}={{\mathbf{x}}}_{q}^{d}+\epsilon\cdot\text{sgn}(\nabla_{{{\mathbf{x}}}_{q}^{d}}J({{\mathbf{x}}}_{q}^{d},{y}_{q}^{d}))$ where $\bar{\bar{{\mathbf{x}}}}_{q}^{d}$ is the perturbed feature vector, $\epsilon$ controls the magnitude of the perturbations, and $J$ is the cost function of the adversarial model Goodfellow, Shlens, and Szegedy (2014).

All algorithms that we trained in Sec. 4.2 were evaluated on the same perturbed test data. In this case, the adversary had no knowledge of the ranking models; however, it was trained on the same training data. Fig. 3 shows the performance of the algorithms on the perturbed test data. As we increase the level of perturbations (i.e., $\epsilon$), we can see that DRMRR is less sensitive to adversarial perturbations in comparison with the competing methods. It demonstrated a stable performance across all metrics. Among the baselines, XE-MART_NDCG that performed well in terms of NDCG@5, demonstrated poor performance in terms of AP@5.

The black-box adversarial attack restricts the attacker’s knowledge only to the deployed model Bhambri et al. (2019). The setting of black-box attacks is closer to the real-world scenario; therefore, this is the most practical experiment to measure the robustness of our algorithm. Please refer to Bhambri et al. (2019) for more information on the black-box adversarial attacks. Since the adversary has no access to the model’s weights and parameters, the adversary can choose to train a parallel model called a substitute model to imitate the original model. Usually, the attacker can use a much superior architecture than the original models for the weight estimation. Here, we use Neural Networks (NN) as our substitute models. The architecture of this model is presented in the supplement. To construct the substitute models, the training data were independently fed to each model and the output was observed. Then, for each algorithm, an NN ranking model was trained as an adversarial substitute model using the training feature vectors and the observed output of that specific algorithm. Subsequently, 75% of the test queries were perturbed using the FGSM method and the parameters of the substitute model corresponding to each algorithm.

We trained four substitute models corresponding to each ranking algorithm. We used the specific perturbed test data to evaluate the best trained models (i.e., each model has a different perturbed test set). Fig. 4 demonstrates the performance of the algorithms on the perturbed test data. The values are the average of 5 folds. We can see that both figures show the same trend – increasing the level of perturbations (i.e., $\epsilon$) leads to significant differences between DRMRR and the baselines methods. The competing methods were greatly affected by this type of noise, whereas their performance was modest in the simpler experiments, namely universal adversarial attack and Gaussian attack. We conclude that DRMRR is robust to adversarial perturbations, an important property that leads to good generalization ability.

In practice, the vagueness of query intent, insufficient domain knowledge, and ambiguous definition of relevance levels make it hard for human judges to assign proper relevance labels to some documents. Practically speaking, the probability of judgment errors in various relevance degrees is not equal. Even if human annotators misjudge a document, they are more probable to label it closer to its ground-truth label. Inspired by Niu et al. (2015), we define the non-uniform error probabilities in Table 2 where entries of this table correspond to the probability that a document with ground-truth label $y_{i}^{q}$ is prone to be labeled as $y_{j}^{q}$. We randomly changed the labels of the training data using the probabilities in Table 2. Then, each model was trained on the noisy training data. Clean test data were used to evaluate each model. We conducted two sets of experiment, namely low label noise (i.e., $e=0.85$) and high label noise (i.e., $e=0.7$). Table 3 reports the performance of the algorithms on the clean test data. The values in these figures are the average of 5 folds. For the low noise scenario, the differences between the average AP@5 and NDCG@5 of the baseline models and DRMRR were 2.53% and 1.59%, respectively. Notably, the gaps were even larger for the high noise scenario (AP@5=3.08%, NDCG@5=1.68%). Since noise in human-labeled data is an inevitable issue, we can argue that the baseline models are susceptible and degrade more severely as more noise is added to the training set.