Integrating human expertise into machine learning systems often reduces the role of experts to labeling oracles, a paradigm that limits the amount of information exchanged and fails to capture the nuances of human judgment. We address this challenge by developing a human-in-the-loop framework to learn binary classifiers with rich query types, consisting of item ranking and exemplar selection. We first introduce probabilistic human response models for these rich queries motivated by the relationship experimentally observed between the perceived implicit score of an item and its distance to the unknown classifier. Using these models, we then design active learning algorithms that leverage the rich queries to increase the information gained per interaction. We provide theoretical bounds on sample complexity and develop a tractable and computationally efficient variational approximation. Through experiments with simulated annotators derived from crowdsourced word-sentiment and image-aesthetic datasets, we demonstrate significant reductions on sample complexity. We further extend active learning strategies to select queries that maximize information rate, explicitly balancing informational value against annotation cost. This algorithm in the word sentiment classification task reduces learning time by more than 57% compared to traditional label-only active learning.
Figures & tables
Fig. 1: Scores for words (a, b) and image (c, d) attributes as a function of the inner product between their pre-defined embedding and the ground truth classifier. We observe there exists an approximately affine relationship. Pre-trained embeddings naturally encode score information as distance from decision boundary, enabling information-rich queries beyond binary labels.
Query Type
Outcome
Information
Expected Response
Interactions to
Space (N)
per Query (bits)
Time (s)
75% Accuracy
Label only
2
≤1
4.37
1310
Label + Selection
2∣S∣
≤1+log2∣S∣
4.01+0.63∣S∣
468
( qhigh,qlow )
( ∣S∣=4 : ∼ 3 bits)
( ∣S∣=4 : 6.5s)
( ∣S∣=4 )
Label Threshold + Ranking
(∣S∣+1)!
≤log2(∣S+1∣!)
−0.32+4.41∣S∣
191
( qrank )
( ∣S∣=4 : ∼ 4.3 bits)
( ∣S∣=4 : 17.3s)
( ∣S∣=4 )
TABLE I: Comparison of Query Types for Human-in-the-Loop Learning
Fig. 2: Block diagram for human-in-the-loop learning for sentiment word classification. At each interaction, the human annotator receives the query with items that maximize the information gain about the ground truth classifier θ . In the example, we ask the annotator to select a word from a list, and provide its label. The answer to the query is used to update the estimator of the classifier and select the next query items.
Fig. 3: Performance of the human in the loop learning algorithms with human data on the word sentiment analysis task. All configurations are run with 10 different random initializations. The lines represent the mean of those experiments, while the shaded areas represent the standard error. Adding word selection or ranking to the queries together with actively selecting the word set reduces the number of iterations needed to achieve a good performance.
Fig. 4: Performance of Algorithm 2 with human data on word sentiment classification. The larger the word set, the faster the decrease of MSE, as suggested by the lower bound in Theorem III.5 .
Fig. 5: Performance of the human in the loop learning algorithms with human data on the image aesthetic classification task across 10 initializations. There are ∣S∣=4 candidate images for ranking and selection questions. The accuracy increases faster when asking richer queries.
Fig. 6: User interface for selection query. User must select the most positive word in the list, in this case “bad” and label the word according to its connotation, in this case “negative”.
Fig. 7: User interface for ranking query. The user must rank the words from the most negative word in the list “terrified” to the most positive “safe”, and then use the vertical bar to separate words with positive and negative connotations.
Fig. 8: Mean response time from crowdsourced experiments and linear model for different question types and word set sizes. The points show the empirical mean of the data, and the bars show the standard error among all the combined response times collected. We observe that the linear models closely track the empirical means across word set sizes.
Fig. 9: Estimated information gain for several query types. We empirically observe that the ratio of information gain between query types stays approximately constant with interactions.
Fig. 10: Estimated information gain for different slope and noise factor ratios a/σ .
Fig. 11: Predicted ratio of information gain over response time on the word sentiment classification task for different response time models. To maximize the rate with the interface we tested, we should query ranking questions with 10 words. However, if an interface resulted on response time model in (b) we should query selection questions with 2 words.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Fig. 13: Relationship between the empirical mean score of words, given by the NRC [ 17 ] or SocialSent [ 16 ] lexicons, and the distance of their word2vec embeddings to the ground truth classifier. We observe there is an approximately linear relationship.
Fig. 14: Goodness-of-fit diagnostics for the Gumbel-Max and Gumbel-Min noise assumption in the linear score model. Each row shows, from left to right, the empirical residual density vs. fitted Gumbel PDFs, the empirical CDF vs. fitted Gumbel CDFs, and a Q–Q plot comparing empirical and theoretical Gumbel quantiles.
Fig. 15: Age distribution of participants. The mean age is 43.25 years and median 44 years.
Ethnicity
Count
White
68
Asian
15
Black
11
Mixed
4
Other
1
Not available
2
Appendix
TABLE II: Ethnicity distribution
Country
Count
United States
55
United Kingdom
36
Nigeria
2
Bulgaria
1
China
1
Hungary
1
Appendix
TABLE III: Country of birth distribution
Fig. 16: Distribution of total study completion time per participant (including instructions and all word-selection and word-ranking queries).
N
Ranking
Selection
2
142
147
3
184
272
4
175
269
5
204
234
6
176
276
7
191
225
Appendix
TABLE IV: Counts by word set size after preprocessing (gold-standard queries removed).
Query Type
Model
β0 (SE)
β1 (SE)
R2
Adjusted R2
MSE
N
Selection
Linear
4.01 (0.24)
0.63 (0.04)
0.112
0.111
11.22
1648
Selection
Logarithmic
3.10 (0.32)
1.84 (0.14)
0.097
0.097
11.36
1648
Ranking
Linear
−0.32 (0.88)
4.41 (0.16)
0.373
0.372
125.44
1256
Ranking
Quadratic
9.69 (0.57)
0.42 (0.02)
0.356
0.356
127.69
1256
Appendix
TABLE V: Comparison of candidate response time models fitted using least-squares regression.
Fig. 17: Query Response time versus query set size stratified by stage of the learning process. Queries were sampled from early (first 5 queries), mid (iteration 200), and late stages (iteration 1000). The shaded area represents the standard error. The three categories show highly overlapping trends, indicating that learning stage contributes minimal variance beyond set size.
Efficient learning of user preferences is crucial for many modern decision making systems but typically requires costly labeled data. Active learning reduces this cost, yet standard methods are computationally expensive due to pool-based evaluation. Further, most methods assume all query feedback is equally reliable, ignoring that pairwise queries between nearly identical or entirely dissimilar items yield ambiguous, low-confidence responses. To address the issue of feedback reliability, we introduce a novel confidence aware response model that explicitly accounts for these ambiguous comparisons. To overcome the computational bottleneck of pool-based evaluation, we propose an active query synthesis framework, Info-Synth that generates optimal queries by maximizing a mutual information-based objective within a continuous space. Moreover, we propose two strategies, Pair M-dist and Pair Opt-dist, that extend Info-Synth to select effective queries even when restricted to finite query pools. We demonstrate our framework's versatility and performance across synthetic preference learning, constrained text summary datasets, and subjective, continuous-space controller gain tuning for a simulated mobile robot.
Active Learning (AL) is commonly used in applications where labeling data is expensive or time-consuming. In practice, however, labels are often noisy due to varying labeler expertise and annotation uncertainty, especially for complex or ambiguous samples. Learning from such imperfectly labeled data can degrade classifier performance. We propose an AL framework that explicitly accounts for label noise by optimally assigning labelers and selecting samples to minimize labeling error. Our approach, called OLAS (Optimal Labeler Assignment and Sampling), uses a noise model that depends on both labeler accuracy and model uncertainty to guide these decisions. We develop two tractable optimization formulations: one for assigning samples to labelers to minimize worst-case noise, and another for selecting samples while controlling overall label noise. Theoretical results provide closed-form solutions under mild conditions. Empirical evaluations on benchmark datasets and a real-world warranty claim classification problem show that OLAS achieves the highest or near-highest classification accuracy among existing AL strategies across most settings, using only a single label per sample.
Pouya Ahadi, Blair Winograd, Camille Zaug +3
School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332, USA · Ford Motor Company
This work revisits a fundamental question in active learning: how powerful is the ability to synthesize arbitrary queries? Compared to pool-based active learning, where the learner only selects queries from a given unlabeled pool, it has been observed that this seemingly mild change in query ability may dramatically alter the difficulty of statistical learning. In particular some hypothesis classes, such as two dimensional halfspaces, permit only polynomial error decay in the number of samples when the learner must draw its labels from the pool, yet become exponentially learnable once synthesized queries are allowed. This striking gap suggests that membership query synthesis induces a fundamentally different mode of learning, one that is not adequately captured by existing active learning theory and calls for new analytical tools to characterize its sample complexity for general hypothesis classes. Motivated by this phenomenon, we develop several sufficient conditions, present intriguing examples, and propose a conjectural perspective toward understanding which hypothesis classes admit efficient learning through synthesized queries.
Ganghua Wang, Shaddin Dughmi
Department of Mathematics, University of Arizona · Department of Computer Science, University of Southern California