Paper: Decipherment with a Million Random Restarts

ACL ID D13-1087
Title Decipherment with a Million Random Restarts
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2013

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.