Neural Decipherment via Minimum-Cost Flow: From Ugaritic to Linear B

What it is about

The paper deciphers a lost language without parallel text: the words of the lost language are aligned with cognates in a known, related language. Ugaritic is matched to Hebrew (the data of Snyder et al. 2010), and Linear B, a syllabic script, to Greek, using 919 Linear B words. The model is a character-level sequence-to-sequence network with a shared universal character embedding, trained in an EM-style loop. The one-to-one word alignment is chosen by a minimum-cost flow whose edge costs are expected edit distances. The reported results are a 5.5% absolute improvement over the earlier Bayesian system on Ugaritic, and 67.3% of Linear B cognates translated correctly into their Greek equivalents. Three training devices keep the network out of poor local optima: flow decay, a norm limit on the residual term, and a reset of the network after each iteration.

Ideas

• I1. Cognate matching as a minimum-cost flow over an Aramaic-Hebrew word list: one side is Aramaic lexicon entries, the other Hebrew lemmas, each edge costed by a weighted consonant edit distance, each word matched at most once. The solver is deterministic, so this needs no neural model at all.
• I2. Charge every insertion and deletion in a character alignment, with a larger (quadratic) cost for multi-character gaps. The Linear B case, where one syllabogram corresponds to two Greek letters, is handled by changing the gap window. The same rule fits Aramaic sound correspondences, where a letter is often lost or added.
• I3. The paper's split shapes (a large noisy lost-language vocabulary against a smaller clean one) are a good test pattern for alignment work. Measure the share of correct top alignments, held out, on any Aramaic-Hebrew pair whose licence allows a test.

For Mova

I1 and I2 go into The lexicon of Biblical Aramaic and Script and phonology, with I1 also sketched in Aramaic in Mova: what it would need. I3 is a test set for that work, not a release item.

Topics: Akkadian and cuneiform NLP

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/p19-1303

@inproceedings{luo2019neural,
  title = {{Neural Decipherment via Minimum-Cost Flow: From Ugaritic to Linear B}},
  author = {Luo, Jiaming and Cao, Yuan and Barzilay, Regina},
  booktitle = {Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  doi = {10.18653/v1/p19-1303},
  url = {https://doi.org/10.18653/v1/p19-1303}
}

References

23 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Taylor Berg-Kirkpatrick and Dan Klein. 2011. Simple effective decipherment via combinatorial optimization. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 313–321. Association for Computational Linguistics. find
2. Taylor Berg-Kirkpatrick and Dan Klein. 2013. Decipherment with a million random restarts. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 874– 878. Association for Computational Linguistics. find
3. Nishant Kambhatla, Anahita Mansouri Bigvand, and Anoop Sarkar. 2018. Decipherment of substitution ciphers with neural language models. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 869–874. Association for Computational Linguistics. find
4. Diederik P. Kingma and Jimmy Ba. 2015. A method for stochastic optimization. abs/1412.6980. Adam: CoRR, Lyle Campbell. 2013. Historical Linguistics: An Introduction. Edinburgh University Press. ↗
5. Kevin Knight, Anish Nair, Nishit Rathod, and Kenji Yamada. 2006. Unsupervised analysis for decipherment problems. In Proceedings of the COL-ING/ACL 2006 Main Conference Poster Sessions, pages 499–506. Association for Computational Linguistics. find
6. Alexis Conneau, Guillaume Lample, Marc’Aurelio Ranzato, Ludovic Denoyer, and Hervé Jégou. 2017. Word translation without parallel data. arXiv preprint arXiv:1710.04087. ↗
7. Kevin Knight and Kenji Yamada. 1999. A computational approach to deciphering unknown scripts. In Unsupervised Learning in Natural Language Processing. find
8. Zi-Yi Dou, Zhi-Hao Zhou, and Shujian Huang. 2018. Unsupervised bilingual lexicon induction via latent variable models. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 621–626. Association for Computational Linguistics. find
9. Tanmoy Mukherjee, Makoto Yamada, and Timothy Hospedales. 2018. Learning unsupervised word translations without adversaries. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 627–632. find
10. Manaal Faruqui and Chris Dyer. 2014. Improving vector space word representations using multilingual correlation. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, pages 462–471. Association for Computational Linguistics. find
11. Jiatao Gu, Hany Hassan, Jacob Devlin, and Victor OK Li. 2018. Universal neural machine translation for extremely low resource languages. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), volume 1, pages 344–354. find
12. Aria Haghighi, Percy Liang, Taylor Berg-Kirkpatrick, and Dan Klein. 2008. Learning bilingual lexicons from monolingual corpora. In Proceedings of ACL-08: HLT, pages 771–779. Association for Computational Linguistics. find
13. David Hall and Dan Klein. 2010. Finding cognate groups using phylogenies. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1030–1039. Association for Computational Linguistics. find
14. Bradley Hauer, Ryan Hayward, and Grzegorz Kondrak. 2014. Solving substitution ciphers with combined language models. In Proceedings of COLING 2014, the 25th International Conference on Computational Linguistics: Technical Papers, pages 2314–2325. Dublin City University and Association for Computational Linguistics. find
15. Toan Nguyen and David Chiang. 2018. Improving lexical choice in neural machine translation. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), volume 1, pages 334–343. find
16. Malte Nuhn, Julian Schamper, and Hermann Ney. 2013. Beam search for solving substitution ciphers. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1568–1576. Association for Computational Linguistics. find
17. Maurice Pope. 1975. The Story of Decipherment: From Egyptian Hieroglyphic to Linear B. Thames & Hudson. find
18. Nima Pourdamghani and Kevin Knight. 2017. Deciphering related languages. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2513–2518. find
19. Sujith Ravi and Kevin Knight. 2011. Deciphering foreign language. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1, pages 12–21. Association for Computational Linguistics. find
20. Andrew Robinson. 2002. Lost languages: the enigma of the world’s undeciphered scripts. find
21. Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. 2016. Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 1683–1692. find
22. Benjamin Snyder, Regina Barzilay, and Kevin Knight. 2010. A statistical model for lost language decipherment. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1048–1057. Association for Computational Linguistics. find
23. Zhaopeng Tu, Zhengdong Lu, Yang Liu, Xiaohua Liu, and Hang Li. 2016. Modeling coverage for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 76–85. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/acl-2019-luo-neural-decipherment-minimum-cost-flow/