Semi-Supervised Streaming Learning with Emerging New Labels

Yong-Nan Zhu, Yu-Feng LiAAAI 2020 · OpenReview

Abstract: In many real-world applications, the modeling environment is usually dynamic and evolutionary, especially in a data stream where emerging new class often happens. Great efforts have been devoted to learning with novel concepts recently, which are typically in a supervised setting with completely supervised initialization. However, the data collected in the stream are often in a semi-supervised manner actually, which means only a few of them are labeled while the great majority miss ground-truth labels. Besides, new classes hidden in unlabeled instances bring more challenges for the learning task. In this paper, we tackle these issues by a new approach called SEEN which consists of three major components: an effective novel class detector based on clustering random trees, a robust classifier for predictions on the known classes, and an efficient updating process that ensures the whole framework adapts to the changing environment automatically. The classifier produces known labels via label propagation that utilizes all labeled and part unlabeled data in the past which naturally describe the entire stream seen so far. Empirical studies on several datasets validate that the algorithm can accurately classify points on a dynamic stream with a small number of labeled examples and emerging new classes.

Introduction

Most traditional machine learning models operate under the assumptions of stationarity—where the set of classes is fixed—and an abundance of labeled data. In reality, data streams such as social media feeds or sensor logs are dynamic. New categories of data (novel classes) emerge unexpectedly, and labeling every incoming data point is often impossible.

Existing novel class detection methods typically require a fully supervised starting point. This paper introduces SEEN (SEmi-supervised streaming learning with Emerging New labels), a framework designed to handle the "wild west" of real-world data: streams where labels are rare and new categories appear over time. SEEN addresses the semi-supervised challenge of detecting and learning new classes when only a handful of labels for known classes are available.

The SEEN Framework

The SEEN framework consists of three synergistic components that form a continuous learning loop:

  1. SeenForest (The Detector): Inspired by Isolation Forests, this component detects if an incoming point belongs to a known class or a new one. It builds trees using a random subset of features. Instead of simple splits, it uses clustering to define "balls" of known data at each node. If a point consistently falls outside these balls across many trees, it is flagged as "novel."
  2. SeenLP (The Classifier): This is a robust, graph-based Semi-Supervised Learning (SSL) classifier. It uses Label Propagation, where labels "flow" from a few labeled points to many unlabeled ones based on their similarity. To handle the computational expense of standard label propagation ($O(n^3)$), SeenLP utilizes a star-mesh transform. This allows the model to "forget" old unlabeled points to save memory while preserving their structural influence on the graph, keeping computation time independent of the stream's total length.
  3. The Updating Process: When the system detects enough novel instances to fill a buffer, it automatically defines them as a new class, updates the classifier to include this new label, and retrains the detector to recognize these points as "known" in the future.
The SEEN framework architecture, illustrating the flow from data stream to SeenForest detection, SeenLP classification, and the automated update process.

Experimental Evaluation

The authors evaluated SEEN on four multi-class benchmark datasets, simulating a streaming environment where new classes are introduced sequentially:

  • segment: Outdoor image features (7 classes).
  • satimage: Satellite multi-spectral pixel data (6 classes).
  • usps: Handwritten digits from the U.S. Postal Service (10 classes).
  • pendigits: Hand-written digit samples (10 classes).

SEEN was compared against several state-of-the-art competitors, including iForest, RRCF, ECSMiner, and SENC-Mas.

Key Results and Discussion

SEEN consistently outperformed all competitors across all datasets in terms of accuracy and label efficiency. For example, on the pendigits dataset, SEEN achieved an accuracy of 0.849, while the next best specialized streaming method (ECSMiner) trailed at 0.765. The macro-averaged F1-score showed an average improvement of 0.044 over the best-performing baseline.

Accuracy performance of SEEN compared to baselines (SENC-Mas, RRCF, ECSMiner, iForest) across four benchmark datasets as the data stream evolves.

Key insights from the evaluation include:

  • Minimalist Initialization: SEEN can start with just a handful of labeled examples per class, unlike previous methods that need a large "warm-up" period.
  • Structural Memory: The star-mesh transform effectively solves the infinite-growth problem of graph methods, allowing the model to remain computationally efficient over long streams.
  • Self-Evolving Loop: The detector and classifier form a feedback loop where the detector finds new classes, the classifier incorporates them, and the detector is updated to treat those classes as "known."

Limitations and Future Work

While highly effective, the current SEEN framework has some limitations. It primarily focuses on classes emerging sequentially; future work aims to explore scenarios where multiple new categories appear simultaneously. Additionally, performance is sensitive to the buffer size used for novel instances—too small a buffer leads to noisy models, while too large a buffer slows adaptation. Finally, while the star-mesh transform aids efficiency, the cubic complexity relative to the buffer size ($O((\tau+K)^3)$) still imposes limits on the number of active points or classes that can be tracked on modest hardware.

Summary updated

Abstract

In many real-world applications, the modeling environment is usually dynamic and evolutionary, especially in a data stream where emerging new class often happens. Great efforts have been devoted to learning with novel concepts recently, which are typically in a supervised setting with completely supervised initialization. However, the data collected in the stream are often in a semi-supervised manner actually, which means only a few of them are labeled while the great majority miss ground-truth labels. Besides, new classes hidden in unlabeled instances bring more challenges for the learning task. In this paper, we tackle these issues by a new approach called SEEN which consists of three major components: an effective novel class detector based on clustering random trees, a robust classifier for predictions on the known classes, and an efficient updating process that ensures the whole framework adapts to the changing environment automatically. The classifier produces known labels via label propagation that utilizes all labeled and part unlabeled data in the past which naturally describe the entire stream seen so far. Empirical studies on several datasets validate that the algorithm can accurately classify points on a dynamic stream with a small number of labeled examples and emerging new classes.
BibTeX
@inproceedings{zhu2020semi,
  author = {Yong-Nan Zhu and Yu-Feng Li},
  title = {{Semi-Supervised Streaming Learning with Emerging New Labels}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=QzdjQ-uVOe},
}
Figure