Decipherment with a Million Random Restarts

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 874–878, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Decipherment with a Million Random Restarts Taylor Berg-Kirkpatrick Dan Klein Computer Science Division University of California, Berkeley {tberg,klein}@cs.berkeley.edu Abstract This paper investigates the utility and effect of running numerous random restarts when us- ing 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 partic- ularly difficult homophonic ciphers, we find that big gains in accuracy are to be had by run- ning 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 proper- ties of decipherment problems, including the famously uncracked Zodiac 340. 1 Introduction What can a million restarts do for decipherment? EM frequently gets stuck in local optima, so running between ten and a hundred random restarts is com- mon practice (Knight et al., 2006; Ravi and Knight, 2011; Berg-Kirkpatrick and Klein, 2011). But, how important are random restarts and how many random restarts does it take to saturate gains in accuracy? We find that the answer depends on the cipher. We look at both Zodiac 408, a famous homophonic sub- stitution cipher, and a more difficult homophonic ci- pher constructed to match properties of the famously unsolved Zodiac 340. Gains in accuracy saturate af- ter only a hundred random restarts for Zodiac 408, but for the constructed cipher we see large gains in accuracy even as we scale the number of ran- dom restarts up into the hundred thousands. In both cases the difference between few and many random restarts is the difference between almost complete failure and successful decipherment. We also find that millions of random restarts can be helpful for performing exploratory analysis. We look at some empirical properties of decipherment problems, visualizing the distribution of local op- tima encountered by EM both in a successful deci- pherment of a homophonic cipher and in an unsuc- cessful attempt to decipher Zodiac 340. Finally, we attack a series of ciphers generated to match proper- ties of Zodiac 340 and use the results to argue that Zodiac 340 is likely not a homophonic cipher under the commonly assumed linearization order. 2 Decipherment Model Various types of ciphers have been tackled by the NLP community with great success (Knight et al., 2006; Snyder et al., 2010; Ravi and Knight, 2011). Many of these approaches learn an encryption key by maximizing the score of the decrypted message under a language model. We focus on homophonic substitution ciphers, where the encryption key is a 1-to-many mapping from a plaintext alphabet to a cipher alphabet. We use a simple method introduced by Knight et al. (2006): the EM algorithm (Demp- ster et al., …

Content truncated to 500 words