Sorting algorithm for ranking hundreds of Images based on pairwise comparison

Question

I am facing the task of designing an algorithm to rank some hundred of images (around 300). The ranking is to be based on pairwise comparison judged by human (done through Amazon mechanical Turk). I have read many papers on ranking inference based on a subset of all possible pairwise comparisons (e.g. Jamieson and Nowak 2011). But I think because I don't have many images, exact ranking should be achievable with properly designed pairwise comparison sequences using some sorting algorithm.

Nonetheless this is different from the standard array sorting in the sense that, comparison result is not known with certainty prior to arranging the pair for comparison and letting the human judge decide. Thus there is a bit of adaptive selection involved. Moreover since it is based on the perception of one human judge, no parallel processing is possible to expedite the sorting. What is worse, transitivity is not guaranteed. Therefore some standard sorting algorithms may not be applicable.

Would somebody please recommend some sorting algorithm for my task?

Many thanks!

Answer 1

If you're actually using humans (e.g., MTurk) and there is any subjectivity at all, I expect that standard sorting algorithms may perform poorly. Standard sorting algorithms expect that there will be zero errors or mistakes in any of the comparisons. If a single comparison returns a faulty value, the sorting algorithm might fail badly. However, in practice, humans make mistakes; and if the rating task is subjective, humans don't always agree on all rating decisions. Consequently, I expect standard algorithms are likely to be a poor match.

If transitivity is not guaranteed, standard sorting algorithms are definitely not suitable.

There are better approaches that can tolerate some errors and mistakes and disagreements. For instance, you might be interested in the Bradley-Terry-Luce model; see https://cs.stackexchange.com/a/134416/755. It helps you infer an overall ordering, based on individual pairwise comparisons. That model does not support nontransitivity, though.

We could also consider how to choose which pairwise comparisons to make (i.e., the experiment design question, instead of the inference question). I don't know if there is literature on that; but Peer grading design - choosing a graph, to get accurate rankings/ratings might be of interest, and it might be worth checking Stats.SE or asking there about this aspect of the problem.