Open-world Semi-supervised Novel Class Discovery

Jiaming Liu, Yangqiming Wang, Tongze Zhang, Yulu Fan, Qinli Yang, Junming ShaoIJCAI 2023 · DOI

TL;DR

This paper introduces OpenNCD, a novel approach for "open-world" semi-supervised learning where unknown classes can appear in unlabeled data. OpenNCD uses a bi-level contrastive learning strategy with multiple prototypes to simultaneously recognize known classes and discover new ones, outperforming existing methods.

What Problem Does This Paper Address?

Traditional machine learning models often assume a "closed-world" scenario, meaning all classes present during testing were seen during training. However, real-world applications, like autonomous driving or cybersecurity, frequently encounter novel, previously unseen classes in unlabeled data. This poses a significant challenge: how can a model not only classify known objects but also detect and categorize entirely new ones without prior knowledge of their existence or number? This paper tackles this "open-world semi-supervised novel class discovery" problem, which involves three key challenges:

  1. Recognizing known classes and detecting unknown ones: Distinguishing between familiar and novel samples in unlabeled data.
  2. Clustering novel classes: Grouping newly discovered samples into distinct categories, even with a separate, disjointed labeled dataset.
  3. Estimating the number of novel classes: Determining how many new classes exist without prior information.

Methods

The proposed method, OpenNCD, addresses these challenges through a progressive, bi-level contrastive learning framework.

  • Bi-level Contrastive Learning: This is the core of OpenNCD's representation learning. It operates on two levels:
  • Prototype-level Similarity: It learns to make instances from the same class have similar "assignment probabilities" to a set of learned prototypes (representative feature vectors). This is achieved through a contrastive loss that pulls positive pairs (an instance and its augmented version, or a labeled instance and its unlabeled counterpart) closer in the prototype space.
  • Group-level Similarity: To capture a coarser class hierarchy, prototypes are progressively grouped into "prototype groups." A similar contrastive loss is applied at this group level, encouraging instances to have similar assignment probabilities to these groups.
  • Prototype Regularization: To prevent prototypes from collapsing (all instances mapping to a single prototype) and ensure diverse representation, a KL divergence loss is used to keep prototype assignments close to a uniform prior.
  • Multi-Prototype Cross-Entropy: To improve known class recognition, a supervised cross-entropy loss is incorporated. This loss uses a Hungarian algorithm to match learned prototype groups to known class labels, allowing for direct supervision.
  • Progressive Prototype Grouping: This is the novel class discovery mechanism. It uses a new similarity metric based on the Jaccard distance of "representing instances" (instances that strongly associate with a prototype). Prototypes with high similarity are progressively grouped. This grouping is guided by the learned representations and can adapt to the unknown number of novel classes. The threshold for grouping is adjusted to maximize accuracy on known classes, ensuring a stable hierarchy.

Datasets

The proposed method was evaluated on three standard image classification datasets:

  • CIFAR-10
  • CIFAR-100
  • ImageNet-100 (a subset of ImageNet)

For each dataset, 50% of the classes were designated as "known" and the other 50% as "novel." Crucially, only 10% of the known classes were labeled, with the rest of the known classes and all novel classes being unlabeled. This setup simulates a challenging open-world scenario.

Key Insights and Ideas

  • Multiple Prototypes are Key: The paper demonstrates that using a large number of prototypes (far exceeding the actual number of classes) is crucial. These prototypes act as building blocks that can be progressively grouped to discover novel classes, offering more flexibility than a single prototype per class.
  • Bi-level Contrastive Learning for Richer Representations: Learning similarities at both fine-grained (prototype) and coarse-grained (group) levels leads to more discriminative and well-separated feature representations, as visualized by T-SNE.
  • Jaccard Distance for Prototype Similarity: The novel similarity metric based on common representing instances provides a robust way to group prototypes, effectively capturing semantic relationships between them.
  • Progressive Grouping Adapts to Unknown Class Counts: The method's ability to progressively group prototypes and adjust grouping thresholds based on known class performance allows it to handle an unknown number of novel classes, a significant advantage over methods requiring this information upfront.

Key Results

  • State-of-the-Art Performance: OpenNCD achieved superior performance across all three datasets (CIFAR-10, CIFAR-100, ImageNet-100) in terms of accuracy for known classes, novel classes, and overall. For example, on CIFAR-100, OpenNCD achieved 53.6% known, 33.0% novel, and 41.2% all-class accuracy, outperforming baselines like ORCA (52.5%, 31.8%, 38.6%) and GCD (49.7%, 27.6%, 38.0%).
  • Effective Class Number Estimation: When tested without prior knowledge of the number of novel classes, OpenNCD outperformed traditional unsupervised methods like X-means and G-means, and a recent deep clustering method (DipDeck), demonstrating its capability in estimating class numbers.
  • Robustness to Novel Class Ratio: The method showed strong performance even as the proportion of novel classes increased, indicating its ability to handle highly open-world scenarios.
  • Improved Feature Visualization: T-SNE visualizations showed that OpenNCD produces more compact and well-separated clusters compared to raw ResNet-18 features or ORCA's representations.

Limitations and Future Work

  • Predefined Number of Prototypes: While the number of classes is unknown, the number of prototypes (K) is predefined. The paper explores the effect of K, showing that more prototypes generally help, but an optimal, data-driven selection of K is not discussed.
  • Computational Cost: The bi-level contrastive learning and progressive grouping might incur significant computational costs, especially with very large datasets or a high number of prototypes.
  • Future Work: The authors suggest that further research could explore more sophisticated methods for prototype selection and grouping, potentially leading to even better performance and efficiency. Investigating the impact of different backbone architectures and exploring more complex real-world scenarios would also be valuable.

Summary updated

BibTeX
@inproceedings{liu2023open,
  author = {Jiaming Liu and Yangqiming Wang and Tongze Zhang and Yulu Fan and Qinli Yang and Junming Shao},
  title = {{Open-world Semi-supervised Novel Class Discovery}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/445},
}
Figure