Introduction
In traditional supervised learning, human annotators are typically asked to provide a single "ground truth" label for each data instance. However, in many complex domains, such as medical diagnosis or sentiment analysis, experts often encounter ambiguity. A physician might identify a primary diagnosis while simultaneously considering several other likely possibilities, ranked by probability—a concept known as a "differential diagnosis."
In their research, Xue and Hauskrecht (AAAI-19) propose that forcing annotators to select a single class discards valuable information regarding their internal uncertainty and the relationships between classes. By leveraging Ordered Class Sets (OCS)—ranked lists of potential labels—and a specialized active learning strategy, the authors demonstrate that models can achieve higher accuracy with significantly fewer labeled samples.
The OCS Framework: AMSVM-OCS
The core of the proposed approach is the Approximate Multi-class Support Vector Machine for Ordered Class Sets (AMSVM-OCS). Standard multi-class SVMs typically enforce constraints that the score of the correct class must exceed the scores of all other classes by a margin.
AMSVM-OCS extends this by incorporating ordinal information. For any given OCS, the classes are partitioned into "higher-ranked" and "lower-ranked" subsets. The model is trained to ensure that the average projection (score) of the higher-ranked subset is greater than that of the lower-ranked subset. This formulation maintains computational efficiency—requiring only $O(KN)$ constraints—while effectively capturing the nuanced boundaries between similar categories.
Active Learning via Expected Model Change
To minimize human effort, the authors introduce a novel active learning strategy tailored for OCS. While traditional active learning often relies on "uncertainty sampling" (querying instances where the model is least confident), this paper advocates for Expected Model Change (EMC).
The EMC strategy selects instances that are expected to induce the greatest shift in the model's parameters if labeled. Because calculating the exact change for every possible ranked set is computationally prohibitive, the authors utilize a sub-sampling approximation. They employ a "Discounted Cumulative Gain" (DCG) metric to quantify how much the predicted class rankings shift during a simulated training step, ensuring that the most informative samples are prioritized for human review.
Experimental Evaluation
The framework was evaluated across five diverse datasets, ranging from synthetic simulations to real-world applications.
The datasets include:
- Synthetic OCS: Vehicle Silhouettes and Optical Digits, where OCS labels were simulated using a pre-trained model's probability distributions.
- Real-world OCS: Million Song (CD1 & CD2) for music genre prediction, and Face Sentiment, where rankings were derived from the consensus (or lack thereof) among multiple human voters.
Results and Discussion
The experimental results consistently show that the combined method, CMSVMA (incorporating both OCS labels and EMC active learning), outperforms baseline models.
Key findings include:
- Joint Gains: The synergy between OCS-aware modeling and EMC-based active learning leads to the highest Exact Match Rate (EMR) across all tested datasets.
- Annotation Efficiency: The efficiency gains are particularly striking in the Face Sentiment dataset. The OCS-aware active learner reached a performance level with approximately 60 labeled samples that standard methods failed to achieve even with 140 samples.
- Information Richness: The results validate the hypothesis that secondary and tertiary choices provide a "roadmap" of decision boundaries, helping the model learn complex class relationships more rapidly than single-label feedback.
Conclusion
By embracing the inherent ambiguity of human labeling through Ordered Class Sets, this research provides a more robust and efficient pathway for training multi-class classifiers. While calculating Expected Model Change introduces some computational overhead, the dramatic reduction in required human annotations makes it a compelling strategy for data-intensive machine learning tasks. Future work may focus on developing incremental solvers to further optimize the active learning loop.
Summary updated