20
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Monte Carlo Sort for unreliable human comparisons

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Algorithms which sort lists of real numbers into ascending order have been studied for decades. They are typically based on a series of pairwise comparisons and run entirely on chip. However people routinely sort lists which depend on subjective or complex judgements that cannot be automated. Examples include marketing research; where surveys are used to learn about customer preferences for products, the recruiting process; where interviewers attempt to rank potential employees, and sporting tournaments; where we infer team rankings from a series of one on one matches. We develop a novel sorting algorithm, where each pairwise comparison reflects a subjective human judgement about which element is bigger or better. We introduce a finite and large error rate to each judgement, and we take the cost of each comparison to significantly exceed the cost of other computational steps. The algorithm must request the most informative sequence of comparisons from the user; in order to identify the correct sorted list with minimum human input. Our Discrete Adiabatic Monte Carlo approach exploits the gradual acquisition of information by tracking a set of plausible hypotheses which are updated after each additional comparison.

          Related collections

          Most cited references1

          • Record: found
          • Abstract: not found
          • Article: not found

          Recursive merge sort with erroneous comparisons

            Bookmark

            Author and article information

            Journal
            2016-12-27
            Article
            1612.08555
            ebecc59e-e3ff-4456-aa6b-a668510604f7

            http://arxiv.org/licenses/nonexclusive-distrib/1.0/

            History
            Custom metadata
            4 pages
            cs.AI cs.DS cs.HC

            Data structures & Algorithms,Artificial intelligence,Human-computer-interaction

            Comments

            Comment on this article