Supervised Discovery of Unknown Unknowns through Test Sample Mining (Student Abstract)

Zheng Wang, Bruno D. Abrahao, Ece KamarAAAI 2020 · DOI

Introduction

In machine learning, "unknown unknowns" (u.u.s) represent a critical failure mode where models encounter categories of data absent from their training sets. Instead of signaling uncertainty, models often assign these novel samples to known classes with high confidence. Traditional solutions to this "structural mismatch" typically rely on expensive human intervention (Oracles) to identify and label missing classes. This paper introduces Random Test Sampling and Cross-Validation (RTSCV), a framework designed to automatically mine these blind spots by exploiting the geometric properties of feature space.

The Problem: Silent Failures in Static Models

When a model's internal representation of the world is incomplete, it lacks the vocabulary to describe new phenomena. For instance, a diagnostic tool trained only on common ailments might misclassify a rare disease as a known condition. Current state-of-the-art methods for discovering these gaps often involve budgeted queries to human experts, which is neither scalable nor cost-effective for large-scale production environments. The authors propose a method to discover these hidden classes algorithmically, without human oversight.

The RTSCV Framework

The RTSCV method treats class discovery as a mining operation through a four-step process:

  1. Random Sampling: A small subset of unlabeled test data ($X_s$) is integrated into the training set as a temporary "dummy" class.
  2. Cross-Validation Trap: The system performs $(m+1)$-fold cross-validation on this augmented dataset. The dummy class, being a high-variance mixture of various data points, acts as a filter.
  3. Isolation: During cross-validation, samples belonging to known classes are naturally "pulled" back into their established categories. In contrast, truly novel data points—the unknown unknowns—remain "trapped" in the dummy class due to their distinct feature signatures.
  4. Retraining: These isolated samples ($X_u$) are used to define a formal new class, and the model is retrained to incorporate this new knowledge.

This approach leverages the intuition that unknown classes tend to form separable clusters that do not align with the concise representations of known classes.

Experimental Setup

The framework was evaluated using both synthetic and real-world data:

  • Synthetic Data: A controlled environment with 10 known classes and one hidden class to test structural reconstruction capabilities.
  • Real-World Benchmarks: Three standard UCI datasets—Iris, Wine, and Knowledge Modelling—were modified by intentionally withholding one class during training to simulate unknown unknowns.

Key Results and Discussion

The RTSCV framework demonstrated significant performance gains over traditional baselines, such as standard clustering or simple probabilistic thresholds.

Figure 2: Accuracy of RTSCV variants compared to benchmarks across varying Silhouette scores.

As shown in the performance analysis, RTSCV variants (KNN and SVM based) consistently maintain high accuracy even as the separability (Silhouette score) of the unknown class varies. This robustness suggests that the method can identify hidden classes even when they are relatively close to known ones in the feature space.

Figure 3: Accuracy improvements on real-world datasets (baseline in parentheses).

On the Iris dataset, the framework improved accuracy from a baseline of 0.61 to a perfect 1.0. Similar substantial improvements were recorded for the Wine (0.62 to 0.91) and Knowledge (0.64 to 0.88) datasets, confirming the effectiveness of the "dummy class" isolation strategy.

Conclusion and Future Work

RTSCV provides a scalable, oracle-free pathway for models to "learn what they don't know." By automating the discovery of unknown unknowns, it allows for the reconstruction of the true data structure in dynamic environments. Future research will focus on providing formal theoretical guarantees for performance and investigating the method's sensitivity to initial sample sizes and cases of extreme feature overlap.

Summary updated

BibTeX
@inproceedings{wang2020supervised,
  author = {Zheng Wang and Bruno D. Abrahao and Ece Kamar},
  title = {{Supervised Discovery of Unknown Unknowns through Test Sample Mining (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i10.7252},
}
Figure