Optimal Clustering from Noisy Binary Feedback
  We study the problem of clustering a set of items from binary user feedback.
Such a problem arises in crowdsourcing platforms solving large-scale labeling
tasks with minimal effort put on the users. For example, in some of the recent
reCAPTCHA systems, users clicks (binary answers) can be used to efficiently
label images. In our inference problem, items are grouped into initially
unknown non-overlapping clusters. To recover these clusters, the learner
sequentially presents to users a finite list of items together with a question
with a binary answer selected from a fixed finite set. For each of these items,
the user provides a noisy answer whose expectation is determined by the item
cluster and the question and by an item-specific parameter characterizing the
{\it hardness} of classifying the item. The objective is to devise an algorithm
with a minimal cluster recovery error rate. We derive problem-specific
information-theoretical lower bounds on the error rate satisfied by any
algorithm, for both uniform and adaptive (list, question) selection strategies.
For uniform selection, we present a simple algorithm built upon the K-means
algorithm and whose performance almost matches the fundamental limits. For
adaptive selection, we develop an adaptive algorithm that is inspired by the
derivation of the information-theoretical error lower bounds, and in turn
allocates the budget in an efficient way. The algorithm learns to select items
hard to cluster and relevant questions more often. We compare the performance
of our algorithms with or without the adaptive selection strategy numerically
and illustrate the gain achieved by being adaptive.
