Unsupervised Sequence Classification using Sequential Output Statistics

Yu Liu, Jianshu Chen, Li Deng

In traditional machine learning, "unsupervised learning" typically refers to finding patterns in data, such as clustering, or learning features to assist a downstream supervised task. However, the true "holy grail" is learning to predict specific output labels from inputs without relying on any human-provided labels.

Labeling data is notoriously expensive and time-consuming. Conversely, sequential output statistics—such as language models that map the frequencies of English words or character sequences—are often available for free from massive text corpora. The core challenge is figuring out how to force a classifier to learn the mapping from an input (like an image of a handwritten 'a') to a label ('a') using only these generalized statistics.

Previous attempts to solve this often failed due to "mode-seeking" behavior, where the model would collapse into a trivial solution—such as predicting the most common character (like a "space") for every single input—and get permanently stuck. To address this, researchers have introduced Empirical Output Distribution Match (Empirical-ODM), a method that achieves error rates only twice as high as fully supervised models, marking a massive improvement over previous unsupervised attempts.

The Empirical-ODM Framework

The authors propose a novel framework built on three core pillars:

1. The Caesar Cipher Inspiration Just as a simple substitution cipher can be broken by matching the frequency of "encrypted" letters to the known frequency of letters in the English language, Empirical-ODM matches the N-gram frequencies of a classifier's predictions to a known language model (LM).

2. Coverage-Seeking Cost Function To prevent the model from collapsing into trivial, repetitive predictions, the authors utilize a specific formulation of Kullback-Leibler (KL) divergence. By swapping the order of the distributions compared to previous work, they create a "coverage-seeking" objective. This penalizes the model if it fails to predict the full variety of outputs expected by the language model.

3. Stochastic Primal-Dual Gradient (SPDG) Standard optimization techniques like Stochastic Gradient Descent (SGD) fail in this setup because the mathematical "average" of the data sits inside a logarithm in their cost function. To resolve this, the researchers employ a "convex conjugate" trick to transform the problem into a min-max (saddle point) problem.

This transformation is crucial: it not only makes the math work for stochastic gradients but also "smooths" the optimization landscape. By doing so, it helps the model jump over high mathematical "barriers" that usually trap models in local minima.

Comparison of the original cost function landscape and the smoothed primal-dual formulation.

Experimental Validation

The researchers evaluated Empirical-ODM on two primary tasks:

  • Optical Character Recognition (OCR): Using the UWIII English Document Image Database, images were segmented into character tiles and processed using VGG19 features.
  • Spelling Correction (Spell-Corr): Using the English Gigaword database, the team simulated "misspelled" text and tasked the model with recovering the original sequences.

To test robustness, the language model "priors" were trained on various partitions of the English Gigaword (e.g., New York Times, Xinhua) to see how the model performs when the prior comes from a different domain than the test data.

Key Results

The results represent a significant leap forward for label-free learning:

  • Unprecedented OCR Performance: The unsupervised SPDG method achieved a 9.59% error rate. For context, a fully supervised model (with all labels provided) achieved 4.63%. Previous unsupervised methods were essentially non-functional, hovering around an 83% error rate—no better than blindly guessing the most common character.
  • Highly Accurate Spelling Correction: The model reached a 1.94% error rate without seeing a single corrected pair during training.
  • Scaling with Data: Larger mini-batches in the SPDG algorithm led to lower errors, as they provided a more stable estimate of the global output statistics.

Insights and Future Directions

A major takeaway from this research is that N-grams are the key to structural constraint. Matching single-letter frequencies (unigrams) isn't enough to learn a mapping; the context provided by 2-grams or 3-grams is required for the model to successfully "solve" the mapping. Furthermore, the method proved surprisingly robust to domain shifts. Even if the language model is trained on news text and the input data consists of old documents, the structural rules of the language remain strong enough to guide the classifier.

The success of the SPDG method also highlights that how we optimize is just as important as what we optimize in unsupervised settings. The transition to a primal-dual domain significantly lowered the barriers in the non-convex loss landscape.

While this paper focuses on linear classifiers, it lays the groundwork for future expansion. The authors note that summing over all possible N-grams becomes computationally expensive as the vocabulary or N-gram order increases. Future work will look toward generalizing this to non-linear models like Deep Neural Networks, potentially utilizing Recurrent Neural Networks (RNNs) to approximate dual variables and beam search to handle larger vocabularies. This would allow the method to scale to full-word language models, pushing the boundaries of what is possible in unsupervised sequence classification.

Summary updated

Abstract

We consider learning a sequence classifier without labeled data by using sequential output statistics. The problem is highly valuable since obtaining labels in training data is often costly, while the sequential output statistics (e.g., language models) could be obtained independently of input data and thus with low or no cost. To address the problem, we propose an unsupervised learning cost function and study its properties. We show that, compared to earlier works, it is less inclined to be stuck in trivial solutions and avoids the need for a strong generative model. Although it is harder to optimize in its functional form, a stochastic primal-dual gradient method is developed to effectively solve the problem. Experiment results on real-world datasets demonstrate that the new unsupervised learning method gives drastically lower errors than other baseline methods. Specifically, it reaches test errors about twice of those obtained by fully supervised learning.
BibTeX
@inproceedings{liu2017unsupervised,
  author = {Yu Liu and Jianshu Chen and Li Deng},
  title = {{Unsupervised Sequence Classification using Sequential Output Statistics}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=rJED0ub_br},
}
Figure