Active preference learning for ordering items in- and out-of-sample

R: The response is assumed to be: $P(C_{ij}=1) = \sigma(\theta_*(x_i-x_j))$.

While this assumption underlies our theoretical analysis and motivates the current version of GURO, we believe that we have taken many steps to highlight the practical usefulness of our algorithm and that the results are more generally applicable.

• We describe in Appendix D.3 how one can derive similar results for other generalized linear models, meaning that one can extend these results beyond the logistic feedback setting.

• We introduce a hybrid model that is aimed at overcoming model misspecification. In Figure 5 in Appendix F.2 we show that these hybrid models still perform comparably to non-contextual algorithms even when features are completely uninformative.

• In Figure 2, we evaluate comparisons made by human annotators. While the algorithm uses a logistic model, the data does not adhere to this. Still, we observe good convergence properties. GURO outperforms TrueSkill, an algorithm that does not assume a logistic model.

Finally, we thank reviewer tuDy for noting that these are common assumptions.

R: The optimization problem for choosing a pair (eq 5 and 7) seems hard.

The motivating example for this paper is the annotation of medical images. As annotations made by radiologists are expensive, our main goal has been to minimize sample complexity, or as stated in the introduction: ''... how can we learn the best ordering possible from a limited number of comparisons?''. We believe that the algorithm is already practically applicable as the bottleneck will in most cases be the time it takes the user to perform a comparison (e.g., about 6 seconds in the case of IMDB-WIKI-SbS). It is however true that for large collections, computational bottlenecks can be encountered if we evaluate all possible comparisons at every iteration, a problem shared by most active preference learning algorithms [1,2,3]. As we describe in Appendix F, in the cases where $n^2$ is large we can instead evaluate our sampling criterion on a uniform subsample of candidate comparisons with no noticeable impact on performance, similar to [2].

Since the computational complexity of GURO was of interest to reviewer LY2M as well, we have written a discussion regarding this in the general rebuttal which we intend to include in a final version. This discussion also includes a potential alternative version of the sampling criterion that scales linearly with $n$.

R: There is no notion of annotation noise here, since the labels are set, right?

The label for each annotation is set, but there is still noise in the comparisons. This is perhaps most clear for the ImageClarity dataset where each comparison has been annotated more than 5 times on average by different annotators. As these annotators can disagree with each other, we get different comparison outcomes depending on which annotation we sample. Furthermore, even in the case where we don't have multiple annotations for each comparison, we still observe noise since annotations can be inconsistent. Say the true order is $a \succ b \succ c$. We might observe the three annotations: $a \succ b$, $b \succ c$, and $c \succ a$. The final annotation is inconsistent with the best possible ordering, but we likely observe this in our data as human annotators disagree with each other and do not necessarily provide responses consistent with their previous comparisons. These inconsistencies are the reason for the error on the held-out comparisons not converging toward $0$ in Figure 2.

R: What is the number of available annotations for each dataset in figure 2?

The number of available comparisons for each dataset is provided in Table 1 (located above Figure 2) under "#comparisons".

• ImageClarity - 27 730

• WiscAds - 9 528

• IMDB-WIKI-SbS - 110 349

R: What is $\Delta_*$? Is it $\Delta_* = \min_{ij} \Delta_{ij}/|i-j|$?

You are correct, $\Delta_*$ should be defined as $\Delta_* = \min_{ij} \Delta_{ij}/|i-j|$ and we will add an explicit definition. Note, that we in the proof of Thm 1 assume, w.l.o.g, that the items are indexed such that $i > j$ implies $y_i > y_j$. This means that $|i-j|$ is the distance between the elements in the ordered list. Hence, we can lower bound $\Delta_{ij}$ by a constant times the difference in position in the ordered list. Substituting $\Delta_{ij}$ by $\Delta_* |i-j|$ in the lower bound on line 158 allow us to simplify that expression since all items in the sum now only depends on $\Delta_* |i-j|$ and we can apply results for geometric sums.

R: Clarification regarding ''algorithms based only on preference feedback'' on line 74.

As also pointed out by LY2M, this sentence can be improved. By "based only on preference feedback" we mean sorting algorithms that disregard attributes/features, regardless of whether they are present. This is the case for TrueSkill, and Figure 2d highlights its inability to generalize to new items. We will improve our formulation for the final version. For example, ''algorithms based only on preference feedback that ignore contextual information''.

R: I suggest adding the assumption on response (eq 2) and the $O(n^2)$ complexity to the list of limitations.

We thank the reviewer for this suggestion and believe that while we have addressed the former limitation in our first answer above, and will add a discussion on complexity to the final version, both topics warrant being mentioned as potential future directions to explore further.

We thank tuDy for their suggestions for improving the text and have incorporated these into the updated manuscript.

References

• [1] Qian, et al. (2015). Learning user preferences by adaptive pairwise comparison.

• [2] Canal, et al., (2019). Active embedding search via noisy paired comparisons.

• [3] Houlsby, et al., (2011) Bayesian Active Learning for Classification and Preference Learning

R: Please provide more discussion on how difference the proposed method is comparing to logistic bandits.

As mentioned in our submission (l109, l138), our theory builds on the same techniques as previous papers on logistic bandits. However, we want to highlight that the problem considered here differs substantially from the standard bandit problem. Lemma 1 is a standard argument used in the literature (even before logistic bandits) which we include and tailor to our setting for completeness. Moreover, Theorem 1 is tailored toward our setting and justifies a selection criterion that is good for ranking but not for (regret minimization) bandits.

Reviewer 6ajg did not specify which paper "[1]" is referring to but if it is Faury et al. (2020), the reviewer is correct that Lemma 1 is similar to their Lemma 3. An important distinction is that we provide a bound on the probability of error while they offer a high-probability upper bound on the prediction error. In principle, one can turn a bound on the prediction error to a bound on the probability of error. However, in the case of Lemma 3 in Faury et al. (2020), this would require solving a difficult expression involving squares of logarithmic terms. We are not sure this can be done in an analytical way that results in a parsable final bound. The reason that we can present a clean upper bound is due to the decomposition on l687 where we decompose the prediction error into first and second-order terms and then proceed to bound them independently. This is a new contribution in our work.

R: The proposed approach actually does not always perform better than baselines, especially BALD. [...] Therefore, I am not convinced with the claimed statement in the paper.

We assume that the reviewer is referring to the claim of superior sample efficiency. This claim refers to a comparison with previously published algorithms (Uniform, BALD, CoLSTIM, TrueSkill). In all cases in Figures 1-2, a method proposed in this work (GURO, GURO Hybrid or BALD Hybrid) performs better than these baselines, although the difference on ImageClarity is smaller. For the fully contextual versions, GURO consistently uses fewer samples than BALD to reach the same ordering quality, thus having superior sample efficiency. GURO Hybrid and BALD Hybrid are close but GURO Hybrid is never worse. Both are consistently better than TrueSkill. These are new results that were not known in previous research.

In Section 6.2 we reason that the cause of the similar performance between BALD Hybrid and GURO Hybrid is the increased dimensionality due to item-specific terms leading to BALD attributing more of the errors to epistemic uncertainty. It is possible that we would eventually see a similar plateau for BALD Hybrid in 2b as in 2c, but due to us having a limited amount of pre-collected annotations, these experiments can't be extended much further without the overlap of comparisons selected by the algorithms becoming too large. We emphasize that the Hybrid model is a novel contribution presented in this work. It is a pragmatic solution to utilize contextual attributes even when they are not sufficient to produce a complete ordering.

We agree that our claims regarding the empirical results can be clarified further in the abstract and the introduction, and will therefore take steps to:

• Clarify what we mean by GURO having superior performance to active preference learning baselines.

• Further highlight that BALD Hybrid is new to this work.

Finally, beyond GURO and Hybrid variants, we believe that one of this paper's main contributions is the evaluation of existing algorithms when applied to recover a complete ordering. To the best of our knowledge, this is the first time BALD has been used explicitly to order a list. Our experiments, where we also apply our hybrid modification, offer insights into when this works well (BALD in Figure 2a, BALD Hybrid in 2b), and when this does not (BALD in all Figures except 2a, BALD Hybrid in 2c).

We thank reviewer 6ajg for their critique and will use this input to clarify our claims and contributions for the final version of the paper.

R: Baseline methods are weak. Though many related studies are mentioned in the related work section, performances of baselines are not shown in the experiments.

• We argue that the baselines we have included are state-of-the-art and come from diverse fields: Active Preference Learning, Logistic Bandits, Non-Contextual Sorting. Since there is limited work on recovering a complete ordering using contextual attributes, there are no well-established benchmarks to beat.

• We have selected baselines to study three main questions: the effects of including contextual information, the impact of the sampling criterion and the difference between in-sample and out-of-sample ordering. Most algorithms discussed in the related work section are related but are not designed to solve our problem, and would not give evidence for these questions.

• Many algorithms would either perform poorly or do not work in the offline setting where we are limited to a subset of comparisons. [1] does not work on a subset of comparisons and assumes no noise. [2] account for noise by collecting $N$ annotations for every comparison pair, which is not resourceful and is not possible in most practical settings, including the tasks in our empirical study. Several methods in the related work section do not use contextual information, and TrueSkill (which is included in our study) is considered the state-of-the-art for this group. We welcome specific suggestions for stronger baselines to include.

R: Performances should be emphasized in terms of the prediction ordering quality.

We agree that obtaining a good ordering is the focus of this paper, but a ground-truth ordering does not exist for most datasets where comparisons have been made by human annotators since individual annotators often disagree and no annotator labels all pairs. In Figure 7 in Appendix F.2, we perform the same experiments as in Figure 2, but we instead measure the ordering error compared to an ordering estimated from all available comparisons. While this offers similar results, we discuss why this approach can be problematic and highlight this with an example below. In the case of ImageClarity, where the true ordering was available, we evaluate against this in Figure 6 in Appendix F.2. as well, and show that the results mirror our findings in Figure 2.

R: The assumption 1 and 2 are not so intuitive. It is better to illustrate an example.

We thank reviewer nNXZ for this suggestion and will include the motivation behind these assumptions in the updated manuscript.

• Assumption 1 implies that the $\theta_*$ lies in some bounded ball and cannot have unbounded coefficients. We use this assumption on line 705 and we believe this assumption to be necessary since it wouldn't be possible to bound the maximum distance between some unknown $\theta'$ and the true $\theta_*$ otherwise. Note that this assumption is not limiting since the bound on $\theta_*$ is not used by our algorithms.

• Assumption 2 states that there exists an upper bound on the norm of the feature vectors. This assumption is trivially satisfied whenever we have a finite set of data points.

Both assumptions are standard in the literature and only required for the analysis.

R: The number of comparisons is not reduced tremendously on the ImageClarity in Table1.

This is true. We state in Section 6.2 that this is most likely a result of it being easy to order the images in ImageClarity based on their extracted features due to the low semantic level of image distortion. We still include this experiment to highlight that:

• Hybrid models are sometimes not necessary.

• There is still a clear difference between the contextual and non-contextual algorithms.

• Uniform performs worse than active sampling criteria.

We cannot expect any method to beat all other methods on every task, and we are happy to show examples where several methods work well.

R: Limitation should be added.

Is there a specific limitation you are referring to? In Section 7 we cover limitations, such as the lack of a lower bound, and future directions, such as applying representation learning and performing experiments in an online setting. We are happy to include other limitations in an expanded discussion for the final version.

References

• [1] Nir Ailon. Active learning ranking from pairwise preferences with almost optimal query complexity" Advances in Neural Information Processing Systems, 2011

• [2] Kevin G Jamieson and Robert Nowak. "Active ranking using pairwise comparisons" Advances in neural information processing systems, 2011

R: The definition of "general preference learning'' and its distinction from the current setting

We agree that this can be clarified further. This paper focuses on learning a map to recover a complete ordering, but we leverage active preference learning to achieve this. By ''the general preference learning setting'' we refer to existing literature that adaptively samples pairwise comparisons, subsequently observing which of two items is preferred, to learn a comparison function $h(i, j)$. Much of this related work focuses on learning a parameter vector ($\theta$) [1,2,3]. Our approach is a special case of this, and while we are trying to learn $\theta$, we are only doing so as far as it helps us order our list of items. Existing work emphasizes getting good approximations of $\theta$, with [1] maximizing $\hat{\theta}^T \theta$, while [2,3] try to minimize $|\hat{\theta} - \theta|_2$. If the true vector $\theta$ is known, it is sufficient to order the list. However, reducing uncertainty in all directions will likely be wasteful; we do not care about the accuracy of $\theta$ in directions that do not help determine the ordering. As highlighted in Figures 1a and 2c in our paper, while BALD is constructed to efficiently learn parameters by sampling pairwise comparisons, it is ill-suited for full rank recovery.

R: In GURO Hybrid, how are these parameters actually learned? Is there some sort of regularization in practice?

Yes, the parameters are learned through joint MLE on $\theta$ and $\zeta_i$, with regularization, as you suggest. The regularization prohibits the algorithm from learning an arbitrary $\theta$. We cover experimental details, including regularization, in Appendix F. However, we agree that this information is essential for the hybrid model and will include this motivation in the main paper for the final version.

R: Line 198 is too vague: Can you comment more on what constitutes acceptable vs unacceptable discrepancies between $\mathcal{I}$ and $\mathcal{I_D}$?

To learn the ordering perfectly, the feature differences for pairs of items in $\mathcal{I_D}$ must span the space spanned by the feature differences for pairs in $\mathcal{I}$. This is true with high probability when $\mathcal{I_D}$ is a random subset of $\mathcal{I}$, the dimension $d$ is small relative to $|\mathcal{I_D}|$ and the variation in directions of $z_{ij}$ for $i,j \in \mathcal{I}$ is sufficient (i.e., each direction is sufficiently covered). An ``unacceptable'' case would be where one dimension of $z_{ij}$ has large variance for some pairs $i,j \in \mathcal{I}$ but is constant for pairs in $\mathcal{I_D}$. In this case, the component of $\theta$ in this dimension would not be learned consistently, and the model would generalize poorly to $\mathcal{I}$.

R: Clarification regarding sorting "using per-item scores alone" in the introduction

The assumption here is that you don't have any contextual features available (or that your sorting algorithm does not utilize them) and that per-item scores are not known from the beginning but have to be estimated by observing pairwise comparisons. In this scenario, when new items are added to the collection we have no way of estimating their underlying scores (apart from arbitrary initial values such as the average) before observing further comparisons where they are included. This is exemplified by TrueSkills performance in Figure 2d.

R: Line 159: Why can one lower bound $\Delta_{ij}$ by a factor depending on the index difference $|i-j|$?

This follows from the definition of $\Delta_* = \min_{i\neq j} \Delta_{ij} /(i-j)$. The indecies are actually not arbitrary but we assume, w.l.o.g, that the items are ordered such that $i > j$ implies $y_i > y_j$. This was stated in the appendix and we will move it to the main paper. The idea is that we can now lower bound $\Delta_{ij}$ by a constant, $\Delta_*$, times how close the two items are to each other in the ordered list, $|i-j|$. This allow us to simplify the lower bound stated on line 158 since each element in the sum now depends on $\Delta_* |i-j|$ and we can treat it as a geometric sum.

R: Discussion on the computational complexity of GURO and its variants

Thank you for suggesting this addition. We include a discussion on this topic in the general rebuttal since two reviewers raised the issue. We intend to add this discussion to the final version of the paper.

R: For completeness, can you include a figure in the Appendix showing the experiment in Fig 1b, but just plotting $R_{I_D}$ instead of the difference?

We agree with the reviewer that this would be good for completeness and will include this figure in the appendix for the final version. We have attached the produced figure to the general rebuttal.

R: in line 166, should the dependence not be on $\theta_T$ rather than $\theta_*$? See line 157 which uses $\theta_T$. line 169 also jumps back to $\theta_T$

Yes it should be $\theta_T$, thank you for pointing this out.

R: line 189 is missing an important point: by definition, the entirety of $\mathcal{I}$ is unavailable, only $\mathcal{I_D}$ is available to select from. This should be commented on.

Yes, this is correct, direct minimization of (4) would be impossible considering we only have access to a subset $\mathcal{I_D}$. We will note this in the final version of the paper.

We thank LY2M for the thorough feedback and for believing that our contributions are of great value. The remaining comments (including minor ones) have been addressed in the updated manuscript.

References

• [1] Qian, et al. (2015). Learning user preferences by adaptive pairwise comparison. Proceedings of the VLDB Endowment.

• [2] Canal, et al., (2019). Active embedding search via noisy paired comparisons. International Conference on Machine Learning.

• [3] Massimino, and Davenport (2021). As you like it: Localization via paired comparisons. Journal of Machine Learning Research.