%0 Conference Paper %1 radinsky2011ranking %A Radinsky, Kira %A Ailon, Nir %B Proceedings of the Fourth ACM International Conference on Web Search and Data Mining %C New York, NY, USA %D 2011 %I ACM %K learning preference relatedness semantic supervised %P 105--114 %R 10.1145/1935826.1935850 %T Ranking from Pairs and Triplets: Information Quality, Evaluation Methods and Query Complexity %U http://doi.acm.org/10.1145/1935826.1935850 %X Obtaining judgments from human raters is a vital part in the design of search engines' evaluation. Today, a discrepancy exists between judgment acquisition from raters (training phase) and use of the responses for retrieval evaluation (evaluation phase). This discrepancy is due to the inconsistency between the representation of the information in both phases. During training, raters are requested to provide a relevance score for an individual result in the context of a query, whereas the evaluation is performed on ordered lists of search results, with the results' relative position (compared to other results) taken into account. As an alternative to the practice of learning to rank using relevance judgments for individual search results, more and more focus has recently been diverted to the theory and practice of learning from answers to combinatorial questions about sets of search results. That is, users, during training, are asked to rank small sets (typically pairs). Human rater responses to questions about the relevance of individual results are first compared to their responses to questions about the relevance of pairs of results. We empirically show that neither type of response can be deduced from the other, and that the added context created when results are shown together changes the raters' evaluation process. Since pairwise judgments are directly related to ranking, we conclude they are more accurate for that purpose. We go beyond pairs to show that triplets do not contain significantly more information than pairs for the purpose of measuring statistical preference. These two results establish good stability properties of pairwise comparisons for the purpose of learning to rank. We further analyze different scenarios, in which results of varying quality are added as "decoys". A recurring source of worry in papers focusing on pairwise comparison is the quadratic number of pairs in a set of results. Which preferences do we choose to solicit from paid raters? Can we provably eliminate a quadratic cost? We employ results from statistical learning theory to show that the quadratic cost can be provably eliminated in certain cases. More precisely, we show that in order to obtain a ranking in which each element is an average of O(n/C) positions away from its position in the optimal ranking, one needs to sample O(nC2) pairs uniformly at random, for any C > 0. We also present an active learning algorithm which samples the pairs adaptively, and conjecture that it provides additional improvement. %@ 978-1-4503-0493-1

@inproceedings{radinsky2011ranking, abstract = {Obtaining judgments from human raters is a vital part in the design of search engines' evaluation. Today, a discrepancy exists between judgment acquisition from raters (training phase) and use of the responses for retrieval evaluation (evaluation phase). This discrepancy is due to the inconsistency between the representation of the information in both phases. During training, raters are requested to provide a relevance score for an individual result in the context of a query, whereas the evaluation is performed on ordered lists of search results, with the results' relative position (compared to other results) taken into account. As an alternative to the practice of learning to rank using relevance judgments for individual search results, more and more focus has recently been diverted to the theory and practice of learning from answers to combinatorial questions about sets of search results. That is, users, during training, are asked to rank small sets (typically pairs). Human rater responses to questions about the relevance of individual results are first compared to their responses to questions about the relevance of pairs of results. We empirically show that neither type of response can be deduced from the other, and that the added context created when results are shown together changes the raters' evaluation process. Since pairwise judgments are directly related to ranking, we conclude they are more accurate for that purpose. We go beyond pairs to show that triplets do not contain significantly more information than pairs for the purpose of measuring statistical preference. These two results establish good stability properties of pairwise comparisons for the purpose of learning to rank. We further analyze different scenarios, in which results of varying quality are added as "decoys". A recurring source of worry in papers focusing on pairwise comparison is the quadratic number of pairs in a set of results. Which preferences do we choose to solicit from paid raters? Can we provably eliminate a quadratic cost? We employ results from statistical learning theory to show that the quadratic cost can be provably eliminated in certain cases. More precisely, we show that in order to obtain a ranking in which each element is an average of O(n/C) positions away from its position in the optimal ranking, one needs to sample O(nC2) pairs uniformly at random, for any C > 0. We also present an active learning algorithm which samples the pairs adaptively, and conjecture that it provides additional improvement.}, acmid = {1935850}, added-at = {2016-08-30T15:30:33.000+0200}, address = {New York, NY, USA}, author = {Radinsky, Kira and Ailon, Nir}, biburl = {https://www.bibsonomy.org/bibtex/2a04b059e3c72a972ae2a50d12ae8645a/thoni}, booktitle = {Proceedings of the Fourth ACM International Conference on Web Search and Data Mining}, description = {Ranking from pairs and triplets}, doi = {10.1145/1935826.1935850}, interhash = {4ad1a1dfcd87e6265c0868c1f0e338da}, intrahash = {a04b059e3c72a972ae2a50d12ae8645a}, isbn = {978-1-4503-0493-1}, keywords = {learning preference relatedness semantic supervised}, location = {Hong Kong, China}, numpages = {10}, pages = {105--114}, publisher = {ACM}, series = {WSDM '11}, timestamp = {2016-11-02T06:50:19.000+0100}, title = {Ranking from Pairs and Triplets: Information Quality, Evaluation Methods and Query Complexity}, url = {http://doi.acm.org/10.1145/1935826.1935850}, year = 2011 }