Abstract
Sequence classification tasks, such as speech recognition and optical character recognition (OCR), typically rely on large-scale labeled datasets. This paper presents a novel unsupervised framework that circumvents the need for paired training data by leveraging sequential output statistics, such as N-gram language models. We introduce the Empirical Output Distribution Match (Empirical-ODM) cost function, which adopts a coverage-seeking approach to avoid trivial solutions. To optimize this objective, we develop a Stochastic Primal-Dual Gradient (SPDG) algorithm based on convex conjugate reformulations. Experimental results on OCR and spelling correction tasks demonstrate that our method achieves performance levels approaching supervised baselines, significantly outperforming existing unsupervised techniques.
Introduction
The acquisition of labeled data for sequence classification is a significant bottleneck in machine learning. While raw input signals (audio, images) and unpaired output sequences (text) are abundant, pairing them is labor-intensive. Traditional unsupervised approaches often struggle with "mode-seeking" behavior, where models collapse to predicting only the most frequent classes to minimize error.
This work addresses these challenges by proposing a method that trains classifiers using only input data and a statistical prior of the output distribution. By shifting from mode-seeking to coverage-seeking objectives and employing a specialized optimization strategy, we enable effective unsupervised learning for sequence classifiers.
The Empirical-ODM Objective
The core of our approach is the Empirical Output Distribution Match (Empirical-ODM) cost function. Unlike standard cross-entropy which can lead to mode-seeking behavior, Empirical-ODM minimizes the divergence between the prior N-gram distribution and the expected frequency of the model's predictions across the dataset.
This "coverage-seeking" property ensures the model reproduces the diversity found in the language model prior, penalizing it if it fails to output the full range of expected sequences. However, the objective function contains an empirical average inside a logarithm, making standard Stochastic Gradient Descent (SGD) biased and ineffective.
Optimization via Stochastic Primal-Dual Gradient
To overcome the optimization challenges of Empirical-ODM, we utilize convex conjugate functions to transform the cost into a min-max (primal-dual) problem. This reformulation allows the empirical average to be moved outside the non-linear operator, enabling unbiased mini-batch updates.
We introduce the Stochastic Primal-Dual Gradient (SPDG) algorithm, which simultaneously updates primal variables (classifier weights) and dual variables. Beyond enabling unbiased gradients, this approach provides a "smoothing" effect on the loss landscape.
As shown in the visualizations of the loss landscape, the objective is highly non-convex. The primal-dual reformulation helps mitigate the impact of local minima and high-energy barriers that plague the original objective.
Experimental Evaluation
We evaluated the SPDG method on two primary tasks:
- Optical Character Recognition (OCR): Using the UWIII English Document Image Database with an out-of-domain language model prior from the English Gigaword database.
- English Spelling Correction: Recovering original text from misspelled sequences generated from the Gigaword database.
Key Results
The unsupervised SPDG method demonstrated remarkable robustness:
- OCR: Achieved a 9.59% error rate, compared to 4.63% for a fully supervised baseline. Previous unsupervised methods and standard SGD failed, with error rates exceeding 56%.
- Spelling Correction: Achieved a 1.94% error rate, significantly outperforming the ~82% error rate of baseline unsupervised approaches.
The importance of sequential context was also highlighted: using a 3-gram prior resulted in a 10.17% error rate in OCR, whereas a 1-gram prior (ignoring sequence) led to a 71.83% error rate. This confirms that exploiting the statistical structure of the output sequence is vital for successful unsupervised learning.
Conclusion
This research demonstrates that sequential output statistics provide a powerful signal for unsupervised training. By combining a coverage-seeking objective with a primal-dual optimization framework, we can train effective classifiers without labeled data. While currently demonstrated on linear models, the success of this approach suggests a promising path for extending these principles to deep neural networks and more sophisticated neural language models.
Summary updated