3
$\begingroup$

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!

$\endgroup$
2
  • $\begingroup$ What's wrong with merge sort? $\endgroup$
    – Pål GD
    Feb 27 at 16:16
  • $\begingroup$ @PålGD merge sort seems worth considering, thanks for the suggestion! $\endgroup$ Feb 27 at 16:56
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Many thanks for your suggestion! I am actually not sure of how bad the impact of nontransitivity is on sorting. Somebody suggests merge sort which does not involve explicit transitivity test. $\endgroup$ Mar 1 at 16:04
  • $\begingroup$ @PhysicsMath, all standard sorting algorithms assume transitivity, and are inappropriate if you have nontransitivity. The fact that they don't do an explicit transitivity test doesn't make them OK to use with nontransitive comparisons. $\endgroup$
    – D.W.
    Mar 1 at 17:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.