Elamur Research⌕
☰
home / papers / 2009 / Binarization of Synchronous Context-Free Grammars

Binarization of Synchronous Context-Free Grammars

Summary

Syntax-based machine translation built on synchronous context-free grammars (SCFGs) or tree transducers, such as rules extracted following Galley et al. (2004), is expensive to decode. The cost grows exponentially with the number of nonterminals in a rule, because the two languages can reorder constituents freely. Unlike monolingual CFGs, synchronous rules cannot always be broken into binary pieces. The authors formalize synchronous binarization, which splits a rule so that every intermediate (virtual) nonterminal covers a contiguous span in both languages. This lets n-gram language model scores be applied early in decoding. They give a linear-time algorithm that binarizes any rule for which this is possible. On a large Chinese-to-English syntax-based system, almost all extracted rules were binarizable. The binarized grammar made decoding both faster and more accurate than a baseline that binarizes only the source side. For the rare non-binarizable rules, the paper proves results that shrink the space of parsing strategies. It also offers an exact search method and a polynomial-time approximation.

Key points

  • With monolingual (source-side-only) binarization, m-gram-integrated decoding costs O(|w|^(3+2n(m−1))), which grows with rule size n. Synchronous binarization reduces this to O(|w|^(3+4(m−1))), which does not depend on rule size.
  • The binarization algorithm runs in linear time. The resulting rule set supports efficient synchronous parsing and decoding with an integrated n-gram LM.
  • The end-to-end evaluation uses a large-scale Chinese-to-English syntax-based system. It compares synchronous binarization against monolingual binarization and against a state-of-the-art phrase-based system.
  • The paper presents what it describes as the first real non-binarizable examples, each checked by native speakers.
  • Finding the optimal strategy for arbitrary SCFG rules is believed to be NP-complete. The authors prove that strategies respecting decomposition boundaries are never worse. In one worked example, this reduces the complexity from O(|w|^(7m−3)) to O(|w|^(5m−2)).

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: Machine translation · Natural language processing

Cited by

28 papers of our library cite it (of the 140673 whose bibliographies we read); 1 of them have a page here, 27 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1162/coli.2009.35.4.35406

@article{huang2009binarization,
  title = {{Binarization of Synchronous Context-Free Grammars}},
  author = {Huang, Liang and Zhang, Hao and Gildea, Daniel and Knight, Kevin},
  journal = {Computational Linguistics},
  year = {2009},
  doi = {10.1162/coli.2009.35.4.35406},
  url = {https://doi.org/10.1162/coli.2009.35.4.35406}
}

References

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

  1. Aho, Albert V. and Jeffery D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume 1. Prentice-Hall, Englewood Cliffs, NJ. find
  2. Arnborg, Stefen, Derek G. Corneil, and Andrzej Proskurowski. 1987. Complexity of finding embeddings in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8:277–284. ↗
  3. Bodlaender, H. L. and D. M. Thilikos. 1997. Treewidth for graphs with small chordality. Discrete Applied Mathematics, 79:45–61. ↗
  4. Catalan, Eugène. 1844. Note extraite d’une lettre adressée. Journal fürdie reine und angewandte Mathematik, 27:192. find
  5. Chiang, David. 2005. A hierarchical phrase-based model for statistical machine translation. In Proceedings of the 43rd Annual Conference of the Association for Computational Linguistics (ACL-05), pages 263–270, Ann Arbor, MI. (A.9) (A.10) find our card
  6. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA. find
  7. Eisner, Jason. 2003. Learning non-isomorphic tree mappings for machine translation. In Proceedings of the 41st Meeting of the Association for Computational Linguistics, pages 205–208, Sapporo, Japan. find our card
  8. Galley, Michel, Mark Hopkins, Kevin Knight, and Daniel Marcu. 2004. What’s in a translation rule? In Proceedings of the 2004 Meeting of the North American chapter of the Association for Computational Linguistics (NAACL-04), pages 273–280, Boston, MA. ↗ our card
  9. Gildea, Daniel and Daniel Štefankovič. 2007. Worst-case synchronous grammar rules. In Proceedings of the 2007 Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-07), pages 147–154, Rochester, NY. find
  10. Graham, Ronald. 1972. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1:132–133. find
  11. Huang, Liang. 2007. Binarization, synchronous binarization, and target-side binarization. In Proceedings of the NAACL/AMTA Workshop on Syntax and Structure in Statistical Translation (SSST), pages 33–40, Rochester, NY. find
  12. Huang, Liang and David Chiang. 2005. Better k-best parsing. In International Workshop on Parsing Technologies (IWPT05), pages 53–64, Vancouver. find
  13. Huang, Liang, Hao Zhang, and Daniel Gildea. 2005. Machine translation as lexicalized parsing with hooks. In International Workshop on Parsing Technologies (IWPT05), pages 65–73, Vancouver. find
  14. ISI Machine Translation Team. 2006. ISI at NIST-06. Working Notes of the NIST MT Evaluation Workshop, September. Washington, D.C. find
  15. Knight, Kevin and Jonathan Graehl. 2005. An overview of probabilistic tree transducers for natural language processing. In Conference on Intelligent Text Processing and Computational Linguistics (CICLing), pages 1–24. Mexico City. find
  16. Knuth, D. 1977. A generalization of Dijkstra’s algorithm. Information Processing Letters, 6(1):1–5. ↗
  17. Liu, Yang, Qun Liu, and Shouxun Lin. 2005. Log-linear models for word alignment. In Proceedings of the 43rd Annual Conference of the Association for Computational Linguistics (ACL-05), pages 459–466, Ann Arbor, MI. find
  18. Melamed, I. Dan. 2003. Multitext grammars and synchronous parsers. In Proceedings of the 2003 Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL-03), pages 158–165, Edmonton. find
  19. Mihalcea, Rada and Ted Pederson. 2003. An evaluation exercise for word alignment. In HLT-NAACL 2003 Workshop on Building and Using Parallel Texts: Data Driven Machine Translation and Beyond, pages 1–10, Edmonton. find our card
  20. Nederhof, M.-J. 2003. Weighted deductive parsing and knuth’s algorithm. Computational Linguistics, 29(1):135–144. ↗
  21. Och, Franz Josef and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Computational Linguistics, 30(4):417–449. ↗
  22. Rambow, Owen and Giorgio Satta. 1999. Independent parallelism in finite copying parallel rewriting systems. Theoretical Computer Science, 223(1-2):87–120. ↗
  23. Rounds, William C. 1970. Mappings and grammars on trees. Mathematical Systems Theory, 4(3):257–287. ↗
  24. Satta, Giorgio and Enoch Peserico. 2005. Some computational complexity results for synchronous context-free grammars. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 803–810, Vancouver. find
  25. Schröder, E. 1870. Vier combinatorische Probleme. Zeitschrift für Mathematik und Physik, 15:361–376. find
  26. Shapiro, L. and A. B. Stephens. 1991. Bootstrap percolation, the Schröder numbers, and the n-kings problem. SIAM Journal on Discrete Mathematics, 4(2):275–280. ↗
  27. Shieber, Stuart M. 2004. Synchronous grammars as tree transducers. In Proceedings of the Seventh International Workshop on Tree Adjoining Grammar and Related Formalisms (TAG+ 7), pages 88–95, Vancouver. find our card
  28. Shieber, Stuart and Yves Schabes. 1990. Synchronous tree-adjoining grammars. In Proceedings of the 13th International Conference on Computational Linguistics (COLING-90), volume III, pages 253–258, Helsinki. find our card
  29. Wellington, Benjamin, Sonjia Waxmonsky, and I. Dan Melamed. 2006. Empirical lower bounds on the complexity of translational equivalence. In Proceedings of the International Conference on Computational Linguistics/Association for Computational Linguistics (COLING/ACL-06), pages 977–984, Sydney. find
  30. Wu, Dekai. 1996. A polynomial–time algorithm for statistical machine translation. In 34th Annual Meeting of the Association for Computational Linguistics, pages 152–158, Santa Cruz, CA. find
  31. Wu, Dekai. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–403. find our card
  32. Zhang, Hao and Daniel Gildea. 2007. Factorization of synchronous context-free grammars in linear time. In NAACL Workshop on Syntax and Structure in Statistical Translation (SSST), pages 25–32, Rochester, NY. find
  33. Zhang, Hao, Liang Huang, Daniel Gildea, and Kevin Knight. 2006. Synchronous binarization for machine translation. In Proceedings of the NAACL, pages 256–263, New York. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/huang-2009-binarization-synchronous-context-free-grammars/