Abstract
Active learning (AL) reduces the burden of manual data annotation by identifying the most informative samples in an unlabeled pool. Traditional AL methods often face two primary challenges: high computational complexity when searching large data pools and a tendency toward model overconfidence, which leads to biased sample selection. We present Heapified Active Learning (HAL), a reinforcement learning (RL) framework that addresses these issues. HAL utilizes a tournament-style heap structure to reduce selection complexity from $O(M)$ to $O(\log M)$ and introduces a "bias-aware" feature to detect and mitigate model overconfidence. Our approach demonstrates superior efficiency and robustness on benchmarks including MNIST, Duplicated MNIST, and MNIST-M.
Introduction
The core objective of active learning is to "learn to ask the right questions." While heuristic-based methods (e.g., uncertainty sampling) are common, they often fail to adapt to complex data distributions. Policy-based reinforcement learning (PRL) offers a more flexible alternative by learning an optimal selection strategy. However, PRL agents typically struggle with massive action spaces in pool-based settings and can become trapped by the model's own biases. HAL overcomes these limitations through structural efficiency and a novel feature design that monitors the health of the model's internal representations.
Methodology
System Architecture
The HAL framework integrates feature extraction with a reinforcement learning policy. The system processes both labeled and unlabeled sets through a prediction model to generate various observation features, including disagreement, uncertainty, and bias-aware metrics.
The Heapified Policy
To handle large unlabeled pools, HAL structures the selection process as a maximum-heap. Instead of evaluating every image in the pool simultaneously, the RL agent performs a series of pairwise comparisons in a tournament-style bracket. This hierarchical approach reduces the search complexity for the most informative sample to $O(\log M)$, where $M$ is the size of the unlabeled pool. By recursively selecting the "winner" of each pair, the policy ensures that the final selected sample is globally optimal according to the learned strategy.
Bias-Aware Feature Design
A significant challenge in AL is the "overconfidence dilemma," where a model becomes certain of its predictions even in regions where it is incorrect. This often happens when the model's internal representation of a class is overly simplistic, failing to capture the true underlying data distribution.
To combat this, HAL introduces a Bias-Aware (BA) feature based on Maximum Component Suppression. By analyzing the eigenvalues of class-wise embedding features, the system can detect when a class is dominated by a single principal component—a hallmark of oversimplification and potential bias. When high bias is detected, the policy can shift its focus from simple uncertainty to "disagreement" samples that provide more diverse information to challenge the model's current assumptions.
Experiments and Results
The researchers evaluated HAL across three MNIST-based benchmarks to test efficiency, redundancy handling, and generalization.
- MNIST: HAL achieved over 85% accuracy using fewer than 100 labeled images, outperforming standard baselines like DBAL and K-center.
- Duplicated MNIST: To simulate real-world noise (e.g., video surveillance), 80% of the data was replaced with noisy duplicates. HAL demonstrated high resilience, reaching the 85% accuracy threshold with under 75 images, while other methods struggled to filter out redundant data.
- MNIST-M (Generalization): A policy trained on standard MNIST was applied to the more complex MNIST-M dataset (digits on natural backgrounds). The policy outperformed random sampling by 5%, indicating that the agent learned a transferable "meta-strategy" for data selection.
Conclusion
Heapified Active Learning (HAL) provides a scalable and robust solution for active learning in large-scale environments. By combining a tournament-style selection policy with bias-aware feature monitoring, HAL achieves state-of-the-art performance while remaining computationally efficient. Future work will explore end-to-end feature learning and the application of heapified policies to non-visual domains such as Natural Language Processing.
Summary updated