Decipherment with a Million Random Restarts

Taylor Berg-Kirkpatrick, Dan Klein

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},
}

Loading related content...

Figure