Learning synchronous context-free grammars with multiple specialised non-terminals for hierarchical phrase-based translation

What it is about

Hierarchical phrase-based translation uses one nonterminal, which the authors take to be overloaded. They give every gap of every extracted phrase pair its own nonterminal, which yields about 850,000 nonterminals on a small English-Spanish EMEA corpus (sentences up to 20 words). Two nonterminals are then merged when their counts agree: a test on the ratio of rule counts to nonterminal counts, with a dissimilarity measure whose confidence level is a continuous knob. Merging uses a Blue-Fringe style procedure or k-medoids over the most frequent nonterminals. Blue-Fringe at confidence 0.01 reached BLEU 0.5868 with 2,346 nonterminals, against 0.5818 for the baseline; k-medoids with three final nonterminals reached 0.6000, the best result, with a few hundred clustered candidates.

Ideas

• I1. A count test for lexicon merges. Merge two concepts (or two meta tokens) only when their proportions over the same contexts agree under a dissimilarity like the paper's, computed from counts. This targets open problem 2. Measure the merges kept, including the be/have case, and the reader plus encoder bits on dev.
• I2. A representative per merged class. Let a merged concept use one existing chunk as its medoid, not a blend of chunks, as the paper requires. Compare the residual with and without blends.
• I3. Context splits, then merges. Split the encoder's contexts by the function word in the gap, then merge contexts whose counts agree, the paper's order of operations. Start on a small verse subset, as the paper limits sentence length.
• I4. Controls. The paper's best k-medoids result depends on the number of clusters, so report a sweep and a random-merge control with the same number of merges.

For Mova

The method is count-based and deterministic, with an explicit equivalence test, which fits the translator's rule that a lexicon merge must lower the bits. The paper's warning that the best merge size is small and specific suggests that Mova should sweep its merge thresholds before claiming any gain.

Topics: Machine translation

Cite

The paper itself, not this card. BibTeX from the library's record of the work. arXiv 2004.01422

@misc{sanchezmartinez2020learning,
  title = {{Learning synchronous context-free grammars with multiple specialised non-terminals for hierarchical phrase-based translation}},
  author = {Sanchez-Martinez, Felipe and Perez-Ortiz, Juan Antonio and Carrasco, Rafael C.},
  year = {2020},
  eprint = {2004.01422},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.01422}
}

References

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

1. Artetxe, Mikel, Gorka Labaka, and to 250 and the number of cluster to obtained is Eneko Agirre. 2018. Unsupervised statistical maset to 3 are better than those obtained with the chine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Blue-Fringe algorithm and better that the results Processing. achieved by the baseline. The k-medoids allow us to get an 3% improvement in BLEU with just three [Carrasco and Oncina1999] Carrasco, Rafael C. and non-terminals, in contrast with the thousand non-José Oncina. 1999. Learning deterministic reg-terminals obtained by the Blue-Fringe algorithm. ular grammars from stochastic samples in polyno-7 Conclusions This work extends the well-known algorithm for rule extraction in hierarchical statistical machine translation originally proposed by Chiang (2007). Our proposal allows for more than one nonterminal in the resulting synchronous context-free grammar, thus incorporating a specialisation in the resulting non-terminals. Our method works by initially creating a different non-terminal for every possible gap when extracting the initial set of rules; this may easily result in millions of non-terminals which are then merged following a novel equivalence criterion for non-terminals. Two merging strategies are proposed: one inspired on the Blue-Fringe algorithm that joins non-terminals on a one-by-one basis, and another one that performs a k-medoids clustering over a reduce set of nonterminals. A statistically significant improvement in BLEU as with respect to the original method is obtained with both merging criteria. For the experiments we used a small parallel corpus and restricted the length of the parallel sentences in the training corpus to 20 words. This was necessary in order to be able to run the merging algorithm in reasonable time. Recall that, in contrast to (2007), we do not restrict the length of the phrase pairs in order to be able to reproduce the parallel sentences in the training corpus; otherwise long-range reorderings happening near the root of the parse tree of the sentences would not be possible. We tried different methods for filtering the rule table before applying the approach described in this paper so as to be able to use larger corpora and longer sentences, although with no success. A deeper exploration of potential optimizations is necessary. mial time. Informatique Théorique et Applications, [Lang et al.1998] Lang, Kevin J., Barak A. Pearlmutter, and Rodney A. Price. 1998. Results of the 33(1):1–20. Abbadingo One DFA learning competition and a find
2. Carrasco, Rafael C., José Oncina, new evidence-driven state merging algorithm. In and Jorge Calera-Rubio. 2001. Stochastic infer-Proceedings of the 4th International Colloquium ence of regular tree languages. Machine Learning, on Grammatical Inference, ICGI ’98, pages 1–12. 44(1/2):185–197. Springer-Verlag. find
3. Charniak, Eugene. 1994. Statistical [Lewis II and Stearns1968] Lewis II, P. M. and R. E. Language Learning. MIT Press. Stearns. 1968. Syntax-directed transduction. Journal of the ACM, 15(3):465–488. find
4. Chiang, David. 2005. A hierarchical phrase-based model for statistical machine transla- find
5. tion. In Proc. ACL, pages 263–270. Maillette de Buy Wenniger, Gideon and Khalil Sima’an. 2015. Labeling hierarchical phrase-based find
6. Chiang, David. 2007. Hierarchical models without linguistic resources. Machine phrase-based translation. Computational Linguis-Translation, 29(3):225–265. tics, 33(2):201–228. find
7. Durrani, Nadir, Helmut Schmid, [Marcus et al.1993] Marcus, Mitchell P., Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Alexander Fraser, Philipp Koehn, and Hinrich Building a large annotated corpus of english: the Schutze. 2015. The operation sequence model – Penn Treebank. Comput. Linguist., 19(2):313–330, combining n-gram-based and phrase-based statisti-June. cal machine translation. Computational Linguistics, 41(2):157–186. find
8. Habrard, Amaury, Marc Bernard, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann and Marc Sebban. 2003. Improvement of the state Bies, Mark Ferguson, Karen Katz, and Britta Schas-merging rule on noisy data in probabilistic grammat-berger. 1994. The Penn Treebank: Annotating pred-ical inference. In Proceedings of ECML 2003, 14th icate argument structure. In Human Language Tech-European Conference on Machine Learning, pages nology, Proceedings of a Workshop held at Plains-169–180. boro, New Jerey, USA, March 8-11, 1994. Morgan Kaufmann. find
9. Hoeffding, Wassily. 1963. Probability inequalities for sums of bounded random vari- [Matsuzaki et al.2005] Matsuzaki, Takuya, Yusuke ables. Journal of the American Statistical Associa-Miyao, and Jun’ichi Tsujii. 2005. Probabilistic cfg tion, 58(301):13–30. with latent annotations. In Knight, Kevin, Hwee Tou Ng, and Kemal Oflazer, editors, ACL 2005, 43rd find
10. Juillé, Hugues and Jordan B. Annual Meeting of the Association for Computa-Pollack. 1998. A sampling-based heuristic for tree tional Linguistics, Proceedings of the Conference, search applied to grammar induction. In Mostow, 25-30 June 2005, University of Michigan, USA. The Jack and Chuck Rich, editors, Proceedings of the Fif-Association for Computer Linguistics. teenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intel- find
11. Mylonakis, Markos and ligence Conference, AAAI 98, IAAI 98, pages 776– Khalil Sima’an. 2011. Learning hierarchical trans-783. AAAI Press / The MIT Press. lation structure with linguistic annotations. In Proceedings of the 49th Annual Meeting of the Associ- find
12. Koehn, Philipp, Hieu Hoang, ation for Computational Linguistics: Human Lan-Alexandra Birch, Chris Callison-Burch, Marcello guage Technologies, pages 642–652. Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan [Och and Ney2003] Och, Franz Josef and Hermann Ney. 2003. A systematic comparison of vari-Herbst. 2007. Moses: Open source toolkit for ous statistical alignment models. Comput. Linguist., statistical machine translation. In Proceedings of 29(1):19–51. the 45th Annual Meeting of the ACL on Interactive Poster and Demonstration Sessions, ACL ’07, pages 177–180. Association for Computational [Och1999] Och, Franz Josef. 1999. An efficient method for determining bilingual word classes. In Linguistics. Ninth Conf. of the Europ. Chapter of the Association for Computational Linguistics, EACL’99, pages 71– find
13. Koehn, P. 2004. Statistical significance 76, June. tests for machine translation evaluation. In Proceedings of the 2004 Conference on Empirical Methods find
14. Och, Franz Josef. 2003. Minimum error rate in Natural Language Processing, pages 388–395. training in statistical machine translation. In Proceedings of the 41st Annual Meeting on Association find
15. Koehn, Philipp. 2010. Statistical ma-for Computational Linguistics, pages 160–167. chine translation. Cambridge University Press. find
16. Pereira, Fernando C. N. and Yves Schabes. 1992. Inside-outside reestimation from partially bracketed corpora. In Thompson, Henry S., editor, Proceedings 30th Annual Meeting of the Association for Computational Linguistics, pages 128–135. find
17. Petrov, Slav and Dan Klein. 2007. Improved inference for unlexicalized parsing. In Sidner, Candace L., Tanja Schultz, Matthew Stone, and ChengXiang Zhai, editors, Proceedings Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, pages 404–411. The Association for Computational Linguistics. find
18. Petrov, Slav, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Calzolari, Nicoletta, Claire Cardie, and Pierre Isabelle, editors, Proceedings ACL 2006, 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics. The Association for Computer Linguistics. find our card
19. Stahlberg, F., E. Hasler, A Waite, and B Byrne. 2016. Syntactically guided neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 299–305. find
20. Stolcke, Andreas and Stephen M. Omohundro. 1992. Hidden Markov Model induction by bayesian model merging. In Hanson, Stephen Jose, Jack D. Cowan, and C. Lee Giles, editors, Advances in Neural Information Processing Systems 5, pages 11–18. Morgan Kaufmann. find
21. Vilar, David, Daniel Stein, Stephan Peitz, and Hermann Ney. 2010. If I only had a parser: Poor man’s syntax for hierarchical machine translation. In Proc. of the Int. Workshop on Spoken Language Translation (IWSLT). find
22. Williams, Philip, Rico Sennrich, Matt Post, and Philipp Koehn. 2016. Syntax-based statistical machine translation. Morgan & Claypool Publishers. find
23. Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–403. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/sanchez-2020-martinez-learning-synchronous-context-free-grammars/