Optimal and Efficient Binary Questioning for Human-in-the-Loop Annotation
This addresses the problem of reducing annotation costs for AI developers, though it is incremental as it builds on coding theory and heuristics.
The paper tackles the problem of efficiently annotating binary classification datasets using a predictor, by minimizing the number of yes/no questions needed. It proposes a practical heuristic-based method that achieves a 23-86% improvement in annotation efficiency on synthetic and real-world datasets.
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.