# Ranking problem and imbalanced dataset

I know about the problems that imbalanced dataset will cause when we are working on classification problems. And I know the solution for that including undersampling and oversampling.

I have to work on a Ranking problem(Ranking hotels and evaluate based on NDCG50 score this link), and the dataset is extremely imbalanced. However, the example I saw on the internet use the dataset as it is and pass it to train_test_split without oversampling/undersampling.

I am kind of confused if that is true in the Ranking problems in which the imbalanced data does not matter and we do not need to fix this before passing the data to the model?

And if that is the case why?

Thanks

You are completely right, imbalance of labels does have an impact on ranking problems and people are using techniques to counter it.

The example in your notebook applies list-wise gradient boosting. Since pairwise ranking can be made list-wise by injecting the NDCG into the gradient, I will focus on pair-wise rank loss for the argument. I will base myself on this paper (https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf).

$$C = -\bar{P}_{ij}$$log$$P_{ij} - (1 - \bar{P}_{ij})$$log$$(1 - P_{ij})$$

with, $$P_{ij}\equiv P(U_{i}\rhd U_{j})\equiv {1\over{1 + e^{-\sigma(s_{i} - s_{j})}}}$$ and $$\bar{P}_{ij} = {1\over2}(1 + S_{ij})$$ for $$S_{ij}$$ being either $$0$$ or $$1$$.

This is actually just a classification problem, with 0 being article i being less relevance than article j and 1 in the opposite case.

Imagine that now you are working with queries which have a lot of matching documents but only a couple of documents have been tagged as relevant. Often such sparse tagging does not mean that ONLY these documents were relevant, but only is caused by the limitation of the estimation of relevance (https://www.cs.cornell.edu/people/tj/publications/joachims_etal_05a.pdf).

Hence, it is not uncommon to down-sample high rated documents.

Another reason for applying imbalance methods such as reweighting labels, is for example bias due to position (see for example https://ciir-publications.cs.umass.edu/getpdf.php?id=1297). The loss is reweighted based on the observed position of the documents when their relevance was tagged.

• Thanks a lot @Benoit. So based on your explanations is that true to say that for ranking we need to treat the data set appropriately? To be honset I did not quite get the part you mention about list-wise gradient boosting. Does that mean that because that notebook is using list-wise gb they do not need to consider downsampling/upsampling? Thanks. Nov 15, 2020 at 19:02
• @sarii They should use it. The notebook just looks like a demo. They probably did not have time to apply it. Nov 15, 2020 at 19:04
• Got it, Thanks again. When I use downsampling my ndcg score is higher than when I apply the algorithm without downsampling. Do you have any idea what could be the reason? Nov 15, 2020 at 19:06
• Yes, this normal as you are treating queries as if they have more relevant document. for example, let say you have documents A,B,C with relevance 1,0,0. Then possible sorting are 1,0,0 (ndcg@2= 1), 0,1,0 and 0,0,1 (ndcg@2= 1). If you downsample, you will now have groups that might have relevance 1,1,0. All possible sorting combinations (1,1,0; 0,1,1 ; 1,0,1) have ndcg@2 stricly higher than 0. Nov 15, 2020 at 19:10
• It should be the same as classification. If you are still dealing with higher performing test than train even by overfitting your model, most likely there is a hidden bias somewhere. Typically this happens if you have a lot of similar queries, or trivial queries. It could also be due to a difference in distribution of relevance between train and test. For example, some queries in test have all document with 0 relevance. These will automatically have ndcg=1 and thus increasing total ndcg Nov 15, 2020 at 19:20