Stochastic Models for Comparison-based Search

In this thesis we study a problem of searching in a space of objects using comparisons. To navigate through the space to the target object $t$, we ask a sequence of questions of the form ``which object $i$ or $j$ is closer to $t$?'' for which we observe noisy answers. We propose two new probabilistic models for triplet comparisons $(i,j;t)$, which fit the real world data better than the state-of-the-art. We study theoretical properties of these models and for both derive search algorithms that are scalable in the number of objects $n$ and that have convergence guarantees. Finally, we conduct two experiments with real users, in which we demonstrate the efficiency of the proposed methods.