On Sampled Metrics for Item Recommendation (Extended Abstract)

1 Introduction

Item recommendation is, at its core, a retrieval task, where given a context, a catalogue of items is ranked and the top scoring ones are shown to the user. Ranking all items can be costly for large catalogues. Recently, it has become common in research papers to speed up evaluation by only ranking a small subset, consisting of the relevant items together with a random sample of irrelevant ones [He et al., 2017; Ebesu et al., 2018; Hu et al., 2018; Yang et al., 2018b; Yang et al., 2018a; Krichene et al., 2019; Wang et al., 2019]. While sampled training is well-studied [Yu et al., 2017], to the best of our knowledge, the implications of sampled evaluation have not been explored, and this work attempts to shed light on the topic. In particular, we show that findings from sampled metrics (even in expectation) can be inconsistent with exact metrics. This means that if a recommender A outperforms a recommender B on a sampled metric, this does not imply that A has a better metric than B when the metric is computed exactly. This problem occurs even in expectation; i.e., with unlimited repetitions of the measurement. Moreover, the smaller the sample size, the less difference there is between different metrics, and in the small sample limit, all metrics collapse to the area under the ROC curve (AUC). This is particularly problematic because many ranking metrics are designed to focus on the top positions, which is not the case for AUC.

Our analysis suggests that if a study is really interested in metrics that emphasize the top ranked items, sampling candidates should be avoided for the purposes of evaluation, and if the size of the problem is such that sampling is necessary, corrected metrics can provide a more accurate evaluation. Lastly, if sampling is used, readers should be aware that the reported metric has different characteristics than its name implies.

2 Evaluating ItemRecommendation

We briefly recap the evaluation scheme for item recommendation that we investigate in this work. Let there be a pool of n items to recommend from. For a given instance 1 x, a recommendation algorithm, A, returns a ranked list of the n items. In an evaluation, the position, r(A, x) ∈ {1, . . . , n}, of the withheld relevant itemwithin this ranking is computed - r will also be referred to as the predicted rank 2 . For example, r(A, x) = 3 means for an instance x recommender A ranked the relevant item at position 3. Then, a metric M translates the predicted rank into a quality value. This process is repeated for a set of instances, D, and an average metric is reported: 1 |D| ∑x∈D M(r(A, x)). For convenience, we will omit the arguments A, x from r(A, x) whenever the particular recommender, A, or instance, x, is clear from context. We now recap some popular examples for metrics M:

1 E.g., a user, context, or query.

2 For simplicity, we focus on the case where there is only one relevant item. See [Krichene and Rendle, 2020] for a more general case.

For metrics such as Average Precision and NDCG, it makes sense to also define their untruncated counterpart, i.e., for k = n: AP(r) = 1r and NDCG(r) = 1 log2 (r+1) . Figure 1 visualizes how the different ranking metrics trade-off the position vs. quality score. Average precision has the sharpest score decay, e.g., rank 1 is twice as valuable as rank 2, whereas for NDCG, rank 1 is 1.58 more valuable than rank 2. The least position-aware metric is AUC, which places a linear decay on the rank; e.g., improving the ranking of a relevant item from position 101 to 100 is as valuable as an improvement from position 2 to 1. Table 1 shows a toy example for an evaluation.

3 SampledMetrics

Ranking all items is expensive when the number of items, n, is large. Recently, it has become common to rank only a small set, consisting of the relevant item together with a random sample of m irrelevant ones. Let ˜ r be the rank of the relevant item within this random set - note that ˜ r is a random variable. The metric, M, is then computed on ˜ r instead of r. Examples of work that use this sampling protocol include [He et al., 2017; Ebesu et al., 2018; Hu et al., 2018; Yang et al., 2018b; Yang et al., 2018a; Krichene et al., 2019; Wang et al., 2019].

3.1 Inconsistency of SampledMetrics

A central goal of evaluation metrics is to make comparisons between recommenders, such as, recommender A has a higher value than B on metric M. When comparing recommenders among sampled metrics, we would hope that at least the relative order is preserved in expectation. This property can be formalized as follows.

Definition 1. Let the evaluation data D be fixed. A metric M is consistent under sampling if the relative order of any two recommenders A and B is preserved in expectation. That is, for all A, B,

If a metric is inconsistent, then measuring M on a subsample is not a good indicator of the true performance of M.

We illustrate this on our toy example. Table 2 shows the sampled metrics for the example from Table 1. An evaluation with a sampled metric is a random process, so for a better understanding of its outcome, we repeat the evaluation 1000 times and report the average and standard deviation. Compared to the exact metrics in Table 1, the relative ordering of metrics changed. On the exact metrics, C is clearly the best with a 10x higher average precision than B and A. But it has the lowest average precision when sampled measurements are used. A and B perform the same on the exact metrics, but A has a 2x better average precision on the sampled metrics. Sampled average precision does not give any indication of the true ordering among the methods. Similarly, sampled NDCG and sampled Recall at 10 do not agree with the exact metrics. Only AUC is consistent between sampled and exact computation. The other metrics are inconsistent.

Figure 2 shows the same study as in the previous table, as we vary the number of samples, m. The relative ordering of recommenders changes with an increasing sample size. For example, for average precision, depending on the number of samples, any conclusion could be drawn: A better than C better than B (for sample size < 50), A better than B better than C (for sample size ≈ 200), C better than A better than B (for sample size ≈ 500), and finally C better than A equal B (for large sample sizes). This example shows that the bias of sampled average precision is recommender dependent and sample size dependent. This is why the relative ordering of recommenders changes as we change the sample size. Only AUC is consistent for all m, and the expected metric is independent of sample size.

3.2 Rank Distribution Under Sampling

This section derives the distribution of the sampled rank ˜ r and discusses expected metrics. When an irrelevant item is sampled uniformly, it can either rank higher or lower than the relevant item. If the number of all items is n, then the probability that the sampled item j is ranked above r is:

For example, if r is at position 1, the likelihood of a random irrelevant being ranked higher is 0. If r = n, then the like-

.

lihood is 1. Note that the pool of all possible sampled items excludes the truly relevant item and thus has size n - 1.

Repeating the sampling procedure m times with replacement and counting how often an item is ranked higher, corresponds to a Binomial distribution. In other words, the rank ˜ r obtained from the sampling process follows ˜ r ∼ B (m, r-1 n-1 ) +1. If there are no successes in getting a higher ranked item, the rank is 1, if all m samples are successful, the rank is m+ 1. The expected value of the metrics under this distribution is

Note that this is implicitly a function of r, m and n, which appear as parameters of the Binomial distribution. Figure 3 visualizes the expected metrics E(M(˜ r)) as we vary r. The figure highlights the weight that the sampled metric assigns to different ranks. Metrics like Average Precision or NDCG are much less top heavy. Even sharp metrics such as recall become smooth. Only AUC remains unchanged. In general, all metrics converge to a linear function in the small sample limit, similar to AUC behavior. The observations are supported by a formal analysis in [Krichene and Rendle, 2020].

4 CorrectedMetrics

This section investigates whether we can design a sampled metric ˆM, a function from {1, . . . ,m + 1} to R, such that ˆM(˜ r) provides a good estimate of M(r).

4.1 Unbiased Estimator of the Rank

Our first approach is motivated by a simple observation. The sampled metrics that are commonly used are obtained by applying the exact metric M to the observed rank ˜ r, i.e. ˆM(˜ r) = M(˜ r). But ˜ r is a poor estimate of the true rank r, in fact it always under-estimates it. Instead, one can measure the metric not on the observed rank ˜ r, but on an unbiased estimator of r. Recall from Section 3.2 that ˜ r|r ∼ B (m, r-1 n-1 ) + 1. If we let p := r-1

n-1 , then an unbiased estimator of p is given by ˜ r-1 m . Thus an unbiased estimator of r = 1 + (n - 1)p is given by ˆ r := 1 + (n-1)(˜ r-1) m . This motivates using the following corrected metric:

Since the rank estimate is a real number in [1, n], and the original metric M is only defined on natural numbers, we can either round the rank estimate or extend M using e.g. linear interpolation. In our experiments, we round using floor ⌊·⌋.

4.2 Bias-Variance Trade-off

Another criterion one may seek to optimize is the average bias of ˆM(˜ r), that is, ∑r (E[ ˆM(˜ r)|r] -M(r))2 . One potential issue with the minimal bias estimator is that it could have high variance, which we observe numerically in Section 5. In order to alleviate this problem, we can introduce a variance term. Since ˆM is a function from {1, . . . ,m+ 1} to R, ˆM can equivalently be viewed as a vector in Rm+1 . Thus we seek to find a vector ˆM that minimizes the following biasvariance trade-off

where γ is a positive constant that controls the trade-off. Eq. (10) is a regularized least squares problem with a closed form solution, see [Krichene and Rendle, 2020] for additional discussion.

5 Experiments

In [Krichene and Rendle, 2020], an experimental study is performed on instances of real recommender algorithms and a real dataset. We summarize some of the findings here and refer to the full paper for details. The study uses the sampled item recommendation evaluation protocol from [He et al., 2017]. The data comes from the movie recommender Movielens [Harper and Konstan, 2015] where users rate movies.

Rank distribution. We find that real algorithms may result in different rank distributions, for example in the experiment, one of the recommenders is best in the top 10 but has poorer performance at higher ranks, while another recommender is more balanced and puts only few items at poor ranks.

Sampled Metrics. The experiment confirms that sampled metrics can become inconsistent with their exact counterpart. We find that uncorrected sampled metrics have low standard deviation, so the issue is not that of variance, but is due to the bias in the sampled metrics. In particular, for the recommender instances in the experiments, if the study would compare the recommenders only on the sampled metrics, it would draw the wrong conclusion for top-heavy metrics such as Recall, NDCG and AP, even with unlimited repetitions of the experiment. The worst recommender would be found to be the best one.

Corrected Metrics. Finally, the study shows that correction strategies proposed in Section 4 improve the metric estimates. Even though they often have an increased variance, corrected metrics are better at identifying the true order of algorithms. We repeat measurements and report the proportion of times the correct order is identified by each method and for each pairwise comparison, and find that despite the higher variance, corrected metrics have a higher success rate. In particular, the simple rank estimate (eq. 9), while trivial to implement (i.e., upscaling the rank before applying the metric), already gives a notable improvement. Other corrections such as bias-variance (eq. 10) yield better results, but can be more difficult to implement and apply because the biasvariance trade-off γ needs to be configured carefully.

6 Concluding Remarks

This work seeks to bring attention to some issues with sampling of evaluation metrics for item recommendation. It has shown that most metrics are inconsistent under sampling and can lead to false discoveries. Moreover, metrics are usually motivated by applications, e.g., does the top 10 list contain a relevant item? Sampled metrics do not measure the intended quantities - not even in expectation. This is mostly due to the large bias introduced by sampling.

For this reason, sampling should be avoided as much as possible during evaluation. If an experimental study needs to sample, we propose correction methods that give a better estimate of the true metric, however at the cost of increased variance. In this case it is important to rerun the experiment with different samples (e.g., different random seeds). Common practices already have several sources of variance (e.g. due to dataset splits, random initialization), and corrected metrics will introduce another source of variance. This means that it may be harder to find "statistically significant" differences between two recommenders. While corrected metrics are preferable to uncorrected ones, it is important to keep in mind that they are still prone to either not identifying differences (due to variance) or drawing false conclusions because of the bias. This bias can only be eliminated by avoiding sampling altogether.

Acknowledgements

We would like to thank Nicolas Mayoraz and Li Zhang for their helpful comments and suggestions.