Optimal and Efficient Binary Questioning for Human-in-the-Loop
  Annotation
Franco Marchesoni-Acland Jean-Michel Morel Josselin Kherroubi Gabriele Facciolo
Even though data annotation is extremely important for interpretability,
research and development of artificial intelligence solutions, most research
efforts such as active learning or few-shot learning focus on the sample
efficiency problem. This paper studies the neglected complementary problem of
getting annotated data given a predictor. For the simple binary classification
setting, we present the spectrum ranging from optimal general solutions to
practical efficient methods. The problem is framed as the full annotation of a
binary classification dataset with the minimal number of yes/no questions when
a predictor is available. For the case of general binary questions the solution
is found in coding theory, where the optimal questioning strategy is given by
the Huffman encoding of the possible labelings. However, this approach is
computationally intractable even for small dataset sizes. We propose an
alternative practical solution based on several heuristics and lookahead
minimization of proxy cost functions. The proposed solution is analysed,
compared with optimal solutions and evaluated on several synthetic and
real-world datasets. On these datasets, the method allows a significant
improvement ($23-86\%$) in annotation efficiency.