Elamur Research⌕
☰
home / papers / 2019 / Vecalign: Improved Sentence Alignment in Linear Time and Space

Vecalign: Improved Sentence Alignment in Linear Time and Space

Summary

Sentence alignment pairs up minimal groups of sentences in parallel documents that translate each other. Older aligners are slow on long documents because their search grows quadratically, and stronger systems such as Bleualign rely on an MT system. Thompson and Koehn present Vecalign, an aligner that needs only multilingual sentence embeddings (LASER). Its scoring function is cosine distance, normalized against randomly sampled sentence pairs to counter hubness and weighted by the number of sentences involved, so that small one-to-one units are preferred over large many-to-many blocks. Because a group of sentences can be represented by averaging their vectors, the authors adapt a recursive coarse-to-fine dynamic programming scheme from dynamic time warping (Salvador and Chan, 2007). This makes time and memory linear in document length. Vecalign beats prior methods on a German–French benchmark and clearly outperforms Hunalign on low-resource Bible alignment. It also produces better NMT training data from web-crawled text. This matters for building bitext in low-resource languages, which applies directly to Ukrainian-related pairs.

Key points

  • On the Text+Berg De–Fr test set (from Bleualign), Vecalign reaches F1 0.90, compared with 0.85 for Coverage-Based and 0.84 for Bleualign using NMT output.
  • On Bible verse alignment across 10 pairs drawn from Arabic, Turkish, Somali, Afrikaans, Tagalog and Norwegian, verse-level F1 is on average 28 points higher than Hunalign. This holds even for Norwegian, which LASER was not trained on.
  • Re-aligning Paracrawl data improves NMT on FLoRes test sets by 1.7 BLEU for Sinhala→English and 1.6 BLEU for Nepali→English, relative to the Hunalign-based pipeline.
  • Vecalign aligns 32k sentences in about 30 s using about 1 GB of memory, with window size w = 10. Bleualign and Gargantua ran out of memory at that size.
  • The skip (insertion/deletion) cost is defined as a quantile of the 1–1 cost distribution, so it transfers across language pairs. The code is released at github.com/thompsonb/vecalign.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

Fields: Natural language processing

Topics: Machine translation

Cited by

80 papers of our library cite it (of the 140884 whose bibliographies we read); 5 of them have a page here, 75 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/d19-1136

@inproceedings{thompson2019vecalign,
  title = {{Vecalign: Improved Sentence Alignment in Linear Time and Space}},
  author = {Thompson, Brian and Koehn, Philipp},
  booktitle = {Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)},
  year = {2019},
  doi = {10.18653/v1/d19-1136},
  url = {https://doi.org/10.18653/v1/d19-1136}
}

References

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

  1. Sadaf Abdul-Rauf, Mark Fishel, Patrik Lambert, Sandra Noubours, and Rico Sennrich. 2012. Extrinsic evaluation of sentence alignment systems. Workshop on Creating Cross-language Resources for Disconnected Languages and Styles, pages 6–10. find
  2. Mikel Artetxe and Holger Schwenk. 2018. Massively multilingual sentence embeddings for zero-shot cross-lingual transfer and beyond. arXiv preprint arXiv:1812.10464. find our card
  3. Mikel Artetxe and Holger Schwenk. 2019. Margin-based parallel corpus mining with multilingual sentence embeddings. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 3197–3203, Florence, Italy. Association for Computational Linguistics. find our card
  4. Richard Bellman. 1953. An introduction to the theory of dynamic programming. Technical report, RAND Corporation, Santa Monica, CA. find
  5. Fabienne Braune and Alexander Fraser. 2010. Improved unsupervised sentence alignment for symmetrical and asymmetrical parallel corpora. In Coling 2010: Posters, pages 81–89, Beijing, China. find
  6. Coling 2010 Organizing Committee. find
  7. Peter F. Brown, Jennifer C. Lai, and Robert L. Mercer. 1991. Aligning sentences in parallel corpora. In Proceedings of the 29th Annual Meeting on Association for Computational Linguistics, ACL ’91, pages 169–176, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  8. Christian Buck and Philipp Koehn. 2016. Findings of the WMT 2016 bilingual document alignment shared task. In Proceedings of the First Conference on Machine Translation: Volume 2, Shared Task Papers, pages 554–563, Berlin, Germany. Association for Computational Linguistics. find
  9. Vishrav Chaudhary, Yuqing Tang, Francisco Guzmn, Holger Schwenk, and Philipp Koehn. 2019. Low-resource corpus filtering using multilingual sentence embeddings. In Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2), pages 263–268, Florence, Italy. Associ… find our card
  10. Christos Christodouloupoulos and Mark Steedman. 2015. A massively parallel corpus: the Bible in 100 languages. Language resources and evaluation, 49(2):375–395. find our card
  11. William A Gale and Kenneth W Church. 1993. A program for aligning sentences in bilingual corpora. Computational linguistics, 19(1):75–102. find our card
  12. Luı́s Gomes and Gabriel Pereira Lopes. 2016. First steps towards coverage-based sentence alignment. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), pages 2228–2231, Portorož, Slovenia. European Language Resources Association (ELRA). find
  13. Cyril Goutte, Marine Carpuat, and George Foster. 2012. The impact of sentence alignment errors on phrase-based machine translation performance. In The Tenth Biennial Conference of the Association for Machine Translation in the Americas (AMTA 2012). find
  14. Mandy Guo, Qinlan Shen, Yinfei Yang, Heming Ge, Daniel Cer, Gustavo Hernandez Abrego, Keith Stevens, Noah Constant, Yun-Hsuan Sung, Brian Strope, and Ray Kurzweil. 2018. Effective parallel corpus mining using bilingual sentence embeddings. In Proceedings of the Third Conference on Machine Translatio… find our card
  15. Hany Hassan, Anthony Aue, Chang Chen, Vishal Chowdhary, Jonathan Clark, Christian Federmann, Xuedong Huang, Marcin Junczys-Dowmunt, William Lewis, Mu Li, et al. 2018. Achieving human parity on automatic Chinese to English news translation. arXiv preprint arXiv:1803.05567. find our card
  16. Huda Khayrallah and Philipp Koehn. 2018. On the impact of various types of noise on neural machine translation. In Proceedings of the 2nd Workshop on Neural Machine Translation and Generation, pages 74–83, Melbourne, Australia. Association for Computational Linguistics. find our card
  17. Philipp Koehn. 2005. Europarl: A parallel corpus for statistical machine translation. In Machine Translation summit, volume 5, pages 79–86. find
  18. Philipp Koehn, Francisco Guzmn, Vishrav Chaudhary, and Juan Pino. 2019. Findings of the WMT 2019 shared task on parallel corpus filtering for low-resource conditions. In Proceedings of the Fourth Conference on Machine Translation (Volume 3: Shared Task Papers, Day 2), pages 56–74, Florence, Italy. A… find our card
  19. Angeliki Lazaridou, Georgiana Dinu, and Marco Baroni. 2015. Hubness and pollution: Delving into cross-space mapping for zero-shot learning. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Proces… find
  20. Robert C Moore. 2002. Fast and accurate sentence alignment of bilingual corpora. In Conference of the Association for Machine Translation in the Americas, pages 135–144. Springer. find
  21. Miloš Radovanović, Alexandros Nanopoulos, and Mirjana Ivanović. 2010. Hubs in space: Popular nearest neighbors in high-dimensional data. Journal of Machine Learning Research, 11(Sep):2487–2531. find
  22. Stan Salvador and Philip Chan. 2007. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5):561–580. find
  23. Rico Sennrich and Martin Volk. 2010. MT-based sentence alignment for OCR-generated parallel texts. In The Ninth Conference of the Association for Machine Translation in the Americas (AMTA 2010). find
  24. Jörg Tiedemann. 2012. Parallel data, tools and interfaces in OPUS. In Proceedings of the Eighth International Conference on Language Resources and Evaluation (LREC-2012), pages 2214–2218, Istanbul, Turkey. European Languages Resources Association (ELRA). find
  25. Dániel Varga, Péter Halácsy, András Kornai, Viktor Nagy, László Németh, and Viktor Trón. 2007. Parallel corpora for medium density languages. Amsterdam Studies In The Theory And History Of Linguistic Science Series 4, 292:247. find
  26. Martin Volk, Noah Bubenhofer, Adrian Althaus, Maya Bangerter, Lenz Furrer, and Beni Ruef. 2010. Challenges in building a multilingual alpine heritage corpus. In Proceedings of the Seventh conference on International Language Resources and Evaluation (LREC’10), Valletta, Malta. European Languages Res… find
  27. Pierre Zweigenbaum, Serge Sharoff, and Reinhard Rapp. 2018. Overview of the third BUCC shared task: Spotting parallel sentences in comparable corpora. In Proceedings of 11th Workshop on Building and Using Comparable Corpora, pages 39–42. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/thompson-2019-vecalign-improved-sentence-alignment-linear/