TL;DR
This paper bridges the gap between theoretical machine learning and practical computer vision by applying the Learning-with-Rejection (LwR) framework to character recognition. Unlike traditional methods that reject samples based on post-hoc heuristics (like low confidence scores), LwR co-optimizes a classification function and a rejection function simultaneously, allowing the model to ignore ambiguous training samples and achieve superior accuracy on non-rejected test data.
What Problem Does This Paper Address?
In real-world recognition tasks, classifiers are often forced to make a decision even when a sample is highly ambiguous. This ambiguity typically stems from three sources: outliers, incorrect labels, or—most commonly—samples residing in the overlapping regions of class distributions.
Traditional rejection strategies are usually "afterthoughts." For example, a Support Vector Machine (SVM) might reject samples that fall too close to the decision boundary, or a Convolutional Neural Network (CNN) might reject samples with low softmax confidence. The authors argue that these heuristic approaches have a fundamental flaw: they require an accurate classification boundary to be established before rejection is considered. However, ambiguous samples in the training set can "pollute" that very boundary during the learning phase.
Methods
The authors adopt the Learning-with-Rejection (LwR) framework, which treats rejection as a first-class citizen during training.
Co-optimization
Instead of training just a classifier $f(x)$, the model simultaneously trains a rejection function $r(x)$. If $r(x) \leq 0$, the sample is rejected. The optimization goal is to minimize a risk function that balances classification error against a rejection penalty $c$. To make this computationally feasible, they use a convex surrogate loss that transforms the problem into a quadratic programming (QP) task, similar to an SVM.
Multi-Layer Feature Extraction
A key innovation in this paper is the use of different feature spaces for classification and rejection. The authors use a pre-trained CNN as a feature extractor:
- Classification features: Extracted from the final convolutional layer.
- Rejection features: Extracted from the second-to-last layer.
The intuition is that the features best suited for distinguishing between classes might differ from those that indicate whether a sample is "junk" or inherently ambiguous.
Datasets
The researchers evaluated their approach on two challenging binary classification tasks:
- Similar Character Recognition: Distinguishing between "I" and "J" from the notMNIST dataset (a collection of A-J characters in various stylized fonts).
- Character vs. Non-Character: Distinguishing natural scene characters from the Chars74k dataset against general object images from CIFAR-100.
Key Insights and Ideas
- Rejection as Data Cleansing: By incorporating rejection into the training phase, the model effectively performs "on-the-fly" data cleansing. Ambiguous training samples are rejected and thus do not negatively influence the classification boundary.
- Theoretical Grounding: Unlike softmax thresholding, LwR has a strong background in machine learning theory (specifically regarding Rademacher complexity), providing a theoretical guarantee on generalization performance.
- Feature Diversity: The experiment confirms that using different feature spaces for $f(x)$ and $r(x)$ is beneficial. If the same layer is used for both, the model loses the advantage of LwR and degrades toward a standard SVM-like performance.
Key Results
The LwR approach consistently outperformed standard SVMs with heuristic rejection and generally surpassed CNNs using confidence-based rejection.
In the notMNIST ("I" vs "J") task, LwR achieved a significantly better trade-off between accuracy and rejection rate compared to the SVM. While the CNN performed well at low rejection rates, LwR achieved the highest overall accuracy in the experimental range as the rejection cost $c$ was adjusted.
In the Character vs. Non-Character task, LwR proved even more robust. Notably, at certain penalty settings ($c=0.3, 0.4$), LwR predicted labels for all test samples (zero rejection) while maintaining higher accuracy than the baseline CNN, demonstrating the strength of the co-optimized boundary.
Limitations and Future Work
The current study is limited to binary classification tasks. Real-world character recognition involves dozens or hundreds of classes. The authors acknowledge this and plan to extend the framework to multi-class settings in future work. Additionally, while they used a pre-trained CNN for feature extraction, they suggest that a fully end-to-end co-training framework—where the CNN weights themselves are optimized alongside the LwR functions—could yield even better results.
Summary updated