From Caesar Cipher to Unsupervised Learning: A New Method for Classifier Parameter Estimation

Yu Liu, Li Deng, Jianshu Chen, Chang Wen ChenarXiv 2019 · arXiv

Introduction

Modern machine learning relies heavily on supervised learning, a paradigm requiring vast quantities of paired input-output labels. However, the manual labeling process is both prohibitively expensive and time-consuming. This paper introduces a novel approach to unsupervised classification: learning a mapping from inputs to labels without ever observing a single labeled pair. By leveraging the sequential statistics of target labels—much like a cryptanalyst breaking a simple cipher—the proposed method achieves performance levels comparable to supervised models.

The Caesar Cipher Analogy

The core intuition of this research stems from classical cryptography. To decrypt a Caesar cipher without a key, one does not need a parallel corpus of encrypted and decrypted sentences. Instead, one relies on the statistical properties of the target language. For instance, in English, the letter 'e' occurs with the highest frequency. By matching the frequency of characters in the ciphertext to known English letter frequencies, the decryption parameters (the shift) can be recovered.

The Caesar Cipher analogy: decrypting a message by shifting letters to match known language statistics.

The authors translate this concept into a machine learning framework where the "ciphertext" is the set of unlabeled inputs and the "language statistics" serve as a prior for the classifier's predictions.

Mathematical Framework and the Prior

The method assumes access to a "Language Model" (typically a Unigram or Bigram model) that describes the statistical structure of the labels. The learning objective is formulated using Kullback-Leibler (KL) divergence, where the classifier's parameters are adjusted so that the distribution of its predictions aligns with the known label prior.

A critical finding of the study is the necessity of sequential dependencies for "symmetry breaking." While Unigram statistics (simple frequencies) often lead to "majority guessing" or failures in label anchoring, Bigram statistics (transition probabilities between classes) provide sufficient structural information to correctly map labels to specific input features.

Optimization via Stochastic Primal-Dual Gradient (SPDG)

The resulting unsupervised loss function is often non-convex and characterized by a complex optimization landscape. Standard gradient descent methods frequently become trapped in local minima or fail to converge due to the "messy" nature of the objective surface.

Visualization of the optimization landscape, illustrating the saddle-point problem addressed by the SPDG algorithm.

To overcome this, the authors employ convex conjugates to transform the objective into a saddle-point (min-max) problem. They utilize a Stochastic Primal-Dual Gradient (SPDG) algorithm, which updates classifier parameters (primal variables) alongside auxiliary dual variables. This approach effectively smooths the optimization surface, allowing the model to navigate toward a global optimum that would otherwise be inaccessible to standard SGD.

Experimental Validation

The method was rigorously tested on synthetic datasets consisting of 2D Gaussian vectors and labels generated via a 1st-order Markov model. Across ten distinct datasets with varying transition matrices, the SPDG method demonstrated remarkable stability and accuracy.

In the Bigram case, the unsupervised model achieved error rates within 1% of a fully supervised counterpart. For example, on the "SynData5" dataset, both the supervised and unsupervised models yielded an identical error rate of 1.06%. Conversely, models relying solely on Unigram statistics performed poorly, with error rates climbing to 30-40%, confirming that temporal structure is vital for label recovery.

Conclusion and Future Directions

This research demonstrates that unsupervised classification is achievable by matching prediction statistics to sequential label priors. While the current work focuses on synthetic 2D data, it lays the groundwork for applications in high-dimensional domains such as unsupervised speech recognition, OCR, and cross-modal translation. Future efforts will explore the integration of more complex priors and scaling the method to larger label spaces and real-world modalities.

Summary updated

Abstract

Many important classification problems, such as object classification, speech recognition, and machine translation, have been tackled by the supervised learning paradigm in the past, where training corpora of parallel input-output pairs are required with high cost. To remove the need for the parallel training corpora has practical significance for real-world applications, and it is one of the main goals of unsupervised learning. Recently, encouraging progress in unsupervised learning for solving such classification problems has been made and the nature of the challenges has been clarified. In this article, we review this progress and disseminate a class of promising new methods to facilitate understanding the methods for machine learning researchers. In particular, we emphasize the key information that enables the success of unsupervised learning - the sequential statistics as the distributional prior in the labels. Exploitation of such sequential statistics makes it possible to estimate parameters of classifiers without the need of paired input-output data. In this paper, we first introduce the concept of Caesar Cipher and its decryption, which motivated the construction of the novel loss function for unsupervised learning we use throughout the paper. Then we use a simple but representative binary classification task as an example to derive and describe the unsupervised learning algorithm in a step-by-step, easy-to-understand fashion. We include two cases, one with Bigram language model as the sequential statistics for use in unsupervised parameter estimation, and another with a simpler Unigram language model. For both cases, detailed derivation steps for the learning algorithm are included. Further, a summary table compares computational steps of the two cases in executing the unsupervised learning algorithm for learning binary classifiers.
BibTeX
@misc{liu2019from,
  author = {Yu Liu and Li Deng and Jianshu Chen and Chang Wen Chen},
  title = {{From Caesar Cipher to Unsupervised Learning: A New Method for Classifier Parameter Estimation}},
  year = {2019},
  eprint = {1906.02826},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.02826},
}
Figure