[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/acl-2019-luo-neural-decipherment-minimum-cost-flow/)

[home](https://md.mova.elamur.ai/free/en/) / [docs](https://md.mova.elamur.ai/free/en/docs/) / [papers](https://md.mova.elamur.ai/free/en/docs/papers/) / [Ancient Hebrew](https://md.mova.elamur.ai/free/en/docs/papers/hbo/) / Neural Decipherment via Minimum-Cost Flow: From Ugaritic to Linear B

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

**Authors:** [Jiaming Luo](https://md.mova.elamur.ai/free/en/docs/papers/authors/jiaming-luo/); [Yuan Cao](https://md.mova.elamur.ai/free/en/docs/papers/authors/yuan-cao/); [Regina Barzilay](https://md.mova.elamur.ai/free/en/docs/papers/authors/regina-barzilay/) · **Year:** 2019 · **Venue:** Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics **Link:** [aclanthology.org/P19-1303](https://aclanthology.org/P19-1303/) · library `acl-2019-luo-neural-decipherment-minimum-cost-flow` · **Licence:** [CC BY 4.0](https://creativecommons.org/licenses/by/4.0/) (ACL Anthology)

[**33** citations](https://openalex.org/works?filter=cites:W2951893044) openalex · 2026-10-18[**12** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/acl-2019-luo-neural-decipherment-minimum-cost-flow/) of the 140673 papers whose bibliographies we read[Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics](https://aclanthology.org/volumes/P19-1/)[licence](https://creativecommons.org/licenses/by/4.0/)

- [Publisher's page](https://aclanthology.org/P19-1303/)
- [PDF](https://aclanthology.org/P19-1303.pdf)
- [DOI 10.18653/v1/p19-1303](https://doi.org/10.18653/v1/p19-1303)
- [OpenAlex](https://openalex.org/W2951893044)

**Authors (3)**

1. [Jiaming Luo](https://openalex.org/A5029740891) h 4 · 76 citations · 8 works
2. [Yuan Cao](https://openalex.org/A5101989491) [ORCID](https://orcid.org/0000-0002-2495-4701) · h 28 · 9791 citations · 84 works
3. [Regina Barzilay](https://openalex.org/A5010124873) [ORCID](https://orcid.org/0000-0002-2921-8201) · h 93 · 36278 citations · 422 works

Citations and author metrics from openalex (2026-10-18); authors with the same name are not always told apart.

## 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](https://md.mova.elamur.ai/free/en/docs/languages/arc/lexicon/) and [Script and phonology](https://md.mova.elamur.ai/free/en/docs/languages/arc/script-phonology/), with I1 also sketched in [Aramaic in Mova: what it would need](https://md.mova.elamur.ai/free/en/docs/languages/arc/mova/). I3 is a test set for that work, not a release item.

Topics: [Akkadian and cuneiform NLP](https://md.mova.elamur.ai/free/en/docs/papers/topics/akkadian-cuneiform-nlp/)

## Cite

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.18653/v1/p19-1303](https://doi.org/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}
}
```

- [next → The Book of Isaiah: Morphological Clustering and Disputed Authorship](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-1969-kasher-book-isaiah-morphological-clustering-disputed/)
- [↑ back to Ancient Hebrew](https://md.mova.elamur.ai/free/en/docs/papers/hbo/)

## 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](https://scholar.google.com/scholar?q=Taylor+Berg%2DKirkpatrick+and+Dan+Klein%2E+2011%2E+Simple+effective+decipherment+via+combinatorial+optimization%2E+In+Proceedings+of+the+2011+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pa)
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](https://scholar.google.com/scholar?q=Taylor+Berg%2DKirkpatrick+and+Dan+Klein%2E+2013%2E+Decipherment+with+a+million+random+restarts%2E+In+Proceedings+of+the+2013+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+874%E2%80%93+878%2E+Ass)
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](https://scholar.google.com/scholar?q=Nishant+Kambhatla%2C+Anahita+Mansouri+Bigvand%2C+and+Anoop+Sarkar%2E+2018%2E+Decipherment+of+substitution+ciphers+with+neural+language+models%2E+In+Proceedings+of+the+2018+Conference+on+Empirical+Methods+in+Nat)
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. [↗](https://arxiv.org/abs/1412.6980)
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](https://scholar.google.com/scholar?q=Kevin+Knight%2C+Anish+Nair%2C+Nishit+Rathod%2C+and+Kenji+Yamada%2E+2006%2E+Unsupervised+analysis+for+decipherment+problems%2E+In+Proceedings+of+the+COL%2DING%2FACL+2006+Main+Conference+Poster+Sessions%2C+pages+499%E2%80%93506%2E)
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. [↗](https://arxiv.org/abs/1710.04087)
7. Kevin Knight and Kenji Yamada. 1999. A computational approach to deciphering unknown scripts. In Unsupervised Learning in Natural Language Processing. [find](https://scholar.google.com/scholar?q=Kevin+Knight+and+Kenji+Yamada%2E+1999%2E+A+computational+approach+to+deciphering+unknown+scripts%2E+In+Unsupervised+Learning+in+Natural+Language+Processing%2E)
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](https://scholar.google.com/scholar?q=Zi%2DYi+Dou%2C+Zhi%2DHao+Zhou%2C+and+Shujian+Huang%2E+2018%2E+Unsupervised+bilingual+lexicon+induction+via+latent+variable+models%2E+In+Proceedings+of+the+2018+Conference+on+Empirical+Methods+in+Natural+Language+Pr)
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](https://scholar.google.com/scholar?q=Tanmoy+Mukherjee%2C+Makoto+Yamada%2C+and+Timothy+Hospedales%2E+2018%2E+Learning+unsupervised+word+translations+without+adversaries%2E+In+Proceedings+of+the+2018+Conference+on+Empirical+Methods+in+Natural+Langua)
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](https://scholar.google.com/scholar?q=Manaal+Faruqui+and+Chris+Dyer%2E+2014%2E+Improving+vector+space+word+representations+using+multilingual+correlation%2E+In+Proceedings+of+the+14th+Conference+of+the+European+Chapter+of+the+Association+for+Co)
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](https://scholar.google.com/scholar?q=Jiatao+Gu%2C+Hany+Hassan%2C+Jacob+Devlin%2C+and+Victor+OK+Li%2E+2018%2E+Universal+neural+machine+translation+for+extremely+low+resource+languages%2E+In+Proceedings+of+the+2018+Conference+of+the+North+American+Cha)
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](https://scholar.google.com/scholar?q=Aria+Haghighi%2C+Percy+Liang%2C+Taylor+Berg%2DKirkpatrick%2C+and+Dan+Klein%2E+2008%2E+Learning+bilingual+lexicons+from+monolingual+corpora%2E+In+Proceedings+of+ACL%2D08%3A+HLT%2C+pages+771%E2%80%93779%2E+Association+for+Computatio)
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](https://scholar.google.com/scholar?q=David+Hall+and+Dan+Klein%2E+2010%2E+Finding+cognate+groups+using+phylogenies%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%2C+pages+1030%E2%80%931039%2E+Association+for+C)
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](https://scholar.google.com/scholar?q=Bradley+Hauer%2C+Ryan+Hayward%2C+and+Grzegorz+Kondrak%2E+2014%2E+Solving+substitution+ciphers+with+combined+language+models%2E+In+Proceedings+of+COLING+2014%2C+the+25th+International+Conference+on+Computational+L)
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](https://scholar.google.com/scholar?q=Toan+Nguyen+and+David+Chiang%2E+2018%2E+Improving+lexical+choice+in+neural+machine+translation%2E+In+Proceedings+of+the+2018+Conference+of+the+North+American+Chapter+of+the+Association+for+Computational+Lin)
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](https://scholar.google.com/scholar?q=Malte+Nuhn%2C+Julian+Schamper%2C+and+Hermann+Ney%2E+2013%2E+Beam+search+for+solving+substitution+ciphers%2E+In+Proceedings+of+the+51st+Annual+Meeting+of+the+Association+for+Computational+Linguistics+%28Volume+1%3A+)
17. Maurice Pope. 1975. The Story of Decipherment: From Egyptian Hieroglyphic to Linear B. Thames & Hudson. [find](https://scholar.google.com/scholar?q=Maurice+Pope%2E+1975%2E+The+Story+of+Decipherment%3A+From+Egyptian+Hieroglyphic+to+Linear+B%2E+Thames+%26+Hudson%2E)
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](https://scholar.google.com/scholar?q=Nima+Pourdamghani+and+Kevin+Knight%2E+2017%2E+Deciphering+related+languages%2E+In+Proceedings+of+the+2017+Conference+on+Empirical+Methods+in+Natural+Language+Processing%2C+pages+2513%E2%80%932518%2E)
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](https://scholar.google.com/scholar?q=Sujith+Ravi+and+Kevin+Knight%2E+2011%2E+Deciphering+foreign+language%2E+In+Proceedings+of+the+49th+Annual+Meeting+of+the+Association+for+Computational+Linguistics%3A+Human+Language+Technologies%2DVolume+1%2C+page)
20. Andrew Robinson. 2002. Lost languages: the enigma of the world’s undeciphered scripts. [find](https://scholar.google.com/scholar?q=Andrew+Robinson%2E+2002%2E+Lost+languages%3A+the+enigma+of+the+world%E2%80%99s+undeciphered+scripts%2E)
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](https://scholar.google.com/scholar?q=Shiqi+Shen%2C+Yong+Cheng%2C+Zhongjun+He%2C+Wei+He%2C+Hua+Wu%2C+Maosong+Sun%2C+and+Yang+Liu%2E+2016%2E+Minimum+risk+training+for+neural+machine+translation%2E+In+Proceedings+of+the+54th+Annual+Meeting+of+the+Association)
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](https://scholar.google.com/scholar?q=Benjamin+Snyder%2C+Regina+Barzilay%2C+and+Kevin+Knight%2E+2010%2E+A+statistical+model+for+lost+language+decipherment%2E+In+Proceedings+of+the+48th+Annual+Meeting+of+the+Association+for+Computational+Linguistics)
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](https://scholar.google.com/scholar?q=Zhaopeng+Tu%2C+Zhengdong+Lu%2C+Yang+Liu%2C+Xiaohua+Liu%2C+and+Hang+Li%2E+2016%2E+Modeling+coverage+for+neural+machine+translation%2E+In+Proceedings+of+the+54th+Annual+Meeting+of+the+Association+for+Computational+Li)