Paper: Simple Effective Decipherment via Combinatorial Optimization

ACL ID D11-1029
Title Simple Effective Decipherment via Combinatorial Optimization
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2011
Authors

We present a simple objective function that when optimized yields accurate solutions to both decipherment and cognate pair identifica- tion problems. The objective simultaneously scores a matching between two alphabets and a matching between two lexicons, each in a different language. We introduce a simple coordinate descent procedure that efficiently finds effective solutions to the resulting com- binatorial optimization problem. Our system requires only a list of words in both languages as input, yet it competes with and surpasses several state-of-the-art systems that are both substantially more complex and make use of more information.