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.
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.
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