# Optimal and Efficient Binary Questioning for Human-in-the-Loop Annotation

arXiv: https://arxiv.org/abs/2307.01578 · HTML: https://mlsanity.com/paper/2307.01578/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 4 Jul 2023.

## Builds on (most cited first, 19 of 19)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Segment Anything](https://mlsanity.com/paper/2304.02643/) (2023)
- [DINOv2: Learning Robust Visual Features without Supervision](https://mlsanity.com/paper/2304.07193/) (2023)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2204.05862/) (2022)
- [Harnessing the Power of LLMs in Practice: A Survey on ChatGPT and Beyond](https://mlsanity.com/paper/2304.13712/) (2023)
- [A Cookbook of Self-Supervised Learning](https://mlsanity.com/paper/2304.12210/) (2023)
- [SimpleClick: Interactive Image Segmentation with Simple Vision Transformers](https://mlsanity.com/paper/2210.11006/) (2022)
- [A Comparative Survey of Deep Active Learning](https://mlsanity.com/paper/2203.13450/) (2022)
- [Gone Fishing: Neural Active Learning with Fisher Embeddings](https://mlsanity.com/paper/2106.09675/) (2021)
- [Towards Fewer Annotations: Active Learning via Region Impurity and Prediction Uncertainty for Domain Adaptive Semantic Segmentation](https://mlsanity.com/paper/2111.12940/) (2021)
- [Effective Evaluation of Deep Active Learning on Image Classification Tasks](https://mlsanity.com/paper/2106.15324/) (2021)
- [Unifying Approaches in Active Learning and Active Sampling via Fisher Information and Information-Theoretic Quantities](https://mlsanity.com/paper/2208.00549/) (2022)
- [A Lagrangian Duality Approach to Active Learning](https://mlsanity.com/paper/2202.04108/) (2022)
- [One-bit Supervision for Image Classification](https://mlsanity.com/paper/2009.06168/) (2020)
- [Active Self-Supervised Learning: A Few Low-Cost Relationships Are All You Need](https://mlsanity.com/paper/2303.15256/) (2023)
- [Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach](https://mlsanity.com/paper/2211.10298/) (2022)
- [Rollout Algorithms and Approximate Dynamic Programming for Bayesian Optimization and Sequential Estimation](https://mlsanity.com/paper/2212.07998/) (2022)

## Abstract (arXiv)

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.