Decipherment with a Million Random Restarts

Taylor Berg-Kirkpatrick, Dan Klein

Introduction

The Expectation-Maximization (EM) algorithm is a cornerstone of unsupervised learning, yet it is frequently hampered by its tendency to converge to local optima. While standard practice involves a handful of random restarts, researchers Taylor Berg-Kirkpatrick and Dan Klein investigated the impact of scaling this approach to a million restarts. By leveraging GPU acceleration, they addressed the "local optima problem" in the context of historical cryptography, specifically homophonic substitution ciphers.

The Challenge of Homophonic Ciphers

Homophonic ciphers present a significant challenge for automated decipherment. Unlike simple substitution ciphers, they map a single plaintext character to multiple ciphertext symbols, effectively flattening frequency distributions and rendering traditional frequency analysis ineffective. The search space for decryption keys is characterized by a "jagged" landscape with numerous false peaks. If a cipher is short or has many symbols, EM almost always fails to find the global optimum in a small number of trials.

Scaling EM with GPUs

To explore this search space exhaustively, the authors implemented a parallelized version of EM using the CUDA API on NVIDIA GPUs. This implementation achieved a speedup of approximately 1,000x over serial CPU execution, enabling the evaluation of a million restarts in a practical timeframe. The model employed was a Hidden Markov Model (HMM) where hidden states represent plaintext characters and emissions represent ciphertext symbols, guided by a fixed trigram language model.

The Power of Massive Restarts

The study revealed that the necessity of restarts depends heavily on cipher complexity. For "easy" ciphers like the Zodiac 408, accuracy plateaus quickly. However, for more difficult cases like "Synth 340"—a synthetic cipher designed to mimic the unsolved Zodiac 340—performance continues to improve significantly as the number of restarts increases into the hundreds of thousands.

Figure 2: Accuracy and log-likelihood for the Synth 340 cipher continue to improve well beyond 10,000 restarts, highlighting the value of massive search.

Diagnostic Insights from Likelihood Histograms

By analyzing the distribution of log-likelihoods across a million restarts, the authors identified that the most accurate solutions often correspond to "rare peaks"—high-likelihood local optima that are found only a tiny fraction of the time. In one experiment, the best local optimum was found only 90 times out of a million tries.

Figure 3: The log-likelihood histogram for Synth 340 reveals rare, high-quality peaks. The best solution (74% accuracy) is a rare outlier on the far right of the distribution.

This histogram analysis also served as a diagnostic tool. While synthetic ciphers showed clear, sparse peaks of high likelihood, the real Zodiac 340 cipher produced a dense, low-likelihood distribution. This discrepancy provided early statistical evidence that the Zodiac 340 was not a simple row-major homophonic cipher. This hypothesis was confirmed years later when the cipher was finally solved in 2020 and found to contain a complex diagonal transposition step.

Conclusion

The work demonstrates that brute-force search through massive random restarts can overcome the local optima problem in unsupervised learning. Their findings emphasize that for complex problems, the "best" solution may be extremely rare, requiring scale to discover. Furthermore, the shape of the optimization landscape itself can provide critical clues about whether a model's underlying assumptions match the data.

Summary updated

Abstract

This paper investigates the utility and effect of running numerous random restarts when using EM to attack decipherment problems. We find that simple decipherment models are able to crack homophonic substitution ciphers with high accuracy if a large number of random restarts are used but almost completely fail with only a few random restarts. For particularly difficult homophonic ciphers, we find that big gains in accuracy are to be had by running upwards of 100K random restarts, which we accomplish efficiently using a GPU-based parallel implementation. We run a series of experiments using millions of random restarts in order to investigate other empirical properties of decipherment problems, including the famously uncracked Zodiac 340.
BibTeX
@inproceedings{bergkirkpatrick2013decipherment,
  author = {Taylor Berg-Kirkpatrick and Dan Klein},
  title = {{Decipherment with a Million Random Restarts}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
  doi = {10.18653/v1/d13-1087},
}
Figure