Sequential Maximum Margin Classifiers for Partially Labeled Data

Elizabeth Hou, Alfred O. Hero Iii

Abstract

This paper presents a novel framework for updating maximum margin classifiers, such as Support Vector Machines (SVMs), in a sequential manner as data streams arrive. By integrating Maximum Entropy Discrimination (MED) with manifold regularization, the proposed model efficiently learns from continuous data streams, even when labels are sparse. The approach avoids the computational burden of re-training on historical data while maintaining performance levels comparable to full-batch learning.

Introduction

In modern data environments, information is frequently generated as continuous streams from sources like sensors, social media, and satellite transmissions. Traditional "batch" learners, including standard SVMs, are ill-suited for these scenarios as they require all data to be available simultaneously. Re-training these models from scratch with every new data arrival is computationally prohibitive. Furthermore, obtaining labels for streaming data is often expensive and slow, resulting in a "firehose" of raw data but only a "trickle" of labels. This research addresses two primary challenges: enabling sequential model updates and leveraging unlabeled data through semi-supervised learning.

Methodology

The core of the proposed solution is the Maximum Entropy Discrimination (MED) principle, which provides a bridge between frequentist margin-based classifiers and Bayesian inference.

Recursive Bayesian Updates

The framework treats MED as a recursive estimation problem. The posterior distribution of model parameters (weights and bias) from a previous time step serves as the prior for the current step. This recursive structure allows the model to accumulate knowledge over time without storing the entire history of observations.

Sequential Laplacian MED (SeqLapMED)

To incorporate unlabeled data, the authors employ Manifold Regularization. By utilizing a graph Laplacian—a representation of local data geometry—the model ensures that the decision boundary remains "smooth" relative to the underlying data distribution. To maintain computational efficiency, the authors introduce a kernel approximation method that averages the eigenvalues and eigenvectors of graph Laplacians over time.

Experimental Evaluation

The approach was tested across three distinct scenarios:

  1. High-Dimensional Simulated Data: 200 variables with sparse informative features.
  2. Semi-Supervised Simulation: A 3D "sphere" problem with only 10% labeled data.
  3. Real-World Speech Recognition: The Isolet Speech Database, simulated as a stream of 24 sequential groups.

Results and Discussion

Experimental results demonstrate that the sequential models achieve performance nearly identical to full-batch counterparts.

Performance in Supervised and Semi-Supervised Settings

In fully labeled simulations, the SeqMED model performed almost as well as the "Full SVM" gold standard, which re-trains on the entire dataset at each step.

Figure 1: Accuracy of SeqMED vs. Full SVM and standard SVM over time points in a supervised setting.

As shown in Figure 1, the sequential update mechanism allows the model to quickly converge toward the performance of a full-batch learner, significantly outperforming a standard SVM that only considers the current batch.

Real-World Application: Isolet Speech Data

On the Isolet dataset, the sequential approach demonstrated rapid learning. The model's "memory" of previous batches allowed it to maintain high accuracy even as new, potentially difficult samples arrived.

Figure 2: Performance of SeqLapMED on the Isolet speech database across 24 sequential time points.

Figure 2 illustrates that SeqLapMED significantly outperforms a standard LapSVM that resets at each time point. The Lagrange multipliers from previous steps act as weights, ensuring that difficult-to-classify samples from the past continue to inform the current decision boundary.

Conclusion

The proposed sequential framework offers a scalable and effective solution for learning from partially labeled data streams. By utilizing the geometry of unlabeled data and a recursive update rule, the model achieves near-batch performance with a fraction of the computational cost. Future work may address non-stationary data through "forgetting factors" to handle concept drift and further optimize graph construction for high-dimensional spaces.

Summary updated

BibTeX
@inproceedings{hou2018sequential,
  author = {Elizabeth Hou and Alfred O. Hero III},
  title = {{Sequential Maximum Margin Classifiers for Partially Labeled Data}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2018},
  doi = {10.1109/icassp.2018.8461913},
}
Figure