Mova0.5 pre-release⌕
☰
home / docs / papers / Machine translation / Semantics-Based Machine Translation with Hyperedge Replacement Grammars

Semantics-Based Machine Translation with Hyperedge Replacement Grammars

What it is about

The paper translates through a graph-shaped meaning representation. A source sentence is analysed into a graph, the graph is the pivot, and the target sentence is generated from it. The grammar is a weighted synchronous hyperedge replacement grammar. Its rules are learned from aligned string and graph pairs by an unsupervised string-to-graph aligner and two extraction algorithms: one uses only semantic annotation, the other also uses syntax. The system is tested on GeoQuery with two meaning formats, one shaped like English syntax and one language-neutral, and in several translation directions. Syntax helps analysis and generation. The canonical, language-neutral extraction does better on translation, which the authors attribute to one consistent derivation per meaning, so that a wrong rule is shared across languages. The results are called preliminary, and k-best lists show many equivalent outputs.

Ideas

For Mova

The code is tools/translate/profile.rs (the standard encoder) and measure.rs (the residual). The paper's idea that a language-neutral derivation shares errors across languages bears on open problem 6: the standard leans to the Bibles, and I1 is a way to test whether a neutral derivation reduces that lean. Mova does not use a hyperedge grammar; only the canonical-versus-syntactic comparison carries over.

Topics: Machine translation

Cite

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

@inproceedings{jones2012semantics,
  title = {{Semantics-Based Machine Translation with Hyperedge Replacement Grammars}},
  author = {Jones, Bevan and Andreas, Jacob and Bauer, Daniel and Hermann, Karl Moritz and Knight, Kevin},
  booktitle = {Proceedings of COLING 2012},
  year = {2012},
  url = {https://aclanthology.org/C12-1083/}
}

References

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

  1. Bar-Hillel, Y. (1960). The present status of automatic translation of languages. In Alt, F. L., editor, Advances in Computers. Academic Press, New York. find
  2. Bodlaender, H. L. (1998). A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci., 209(1-2):1–45. find
  3. Bohnet, B. and Wanner, L. (2010). Open source graph transducer interpreter and grammar development environment. In Proceedings of the Seventh conference on International Language Resources and Evaluation, Valletta, Malta. European Language Resources Association (ELRA). find
  4. Brown, P. F., Cocke, J., Pietra, S. A. D., Pietra, V. J. D., Jelinek, F., Lafferty, J. D., Mercer, R. L., and Roossin, P. S. (1990). A statistical approach to machine translation. Computational Linguistics, 16(2):79–85. find
  5. Cai, S. and Knight, K. (2012). Smatch: an evaluation metric for semantic feature structures. submitted. find
  6. Chiang, D. (2007). 33(2):201–228. Hierarchical phrase-based translation. find our card
  7. Chiang, D. (2010). Learning to translate with source and target syntax. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, ACL ’10, pages 1443–1452. find our card
  8. Computational Linguistics, Collins, M., Koehn, P., and Kučerová, I. (2005). Clause restructuring for statistical machine translation. In Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, ACL ’05, pages 531–540. find
  9. Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., and Tommasi, M. (2007). Tree Automata Techniques and Applications. INRIA. find
  10. DeNeefe, S. and Knight, K. (2009). Synchronous tree adjoining machine translation. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 2-Volume 2, pages 727–736. Association for Computational Linguistics. find
  11. DeNero, J., Pauls, A., and Klein, D. (2009). Asynchronous binarization for synchronous grammars. In Proceedings of the ACL-IJCNLP 2009 Conference Short Papers, ACLShort ’09, pages 141–144. find
  12. DeVault, D., Traum, D., and Artstein, R. (2008). Practical grammar-based NLG from examples. In Proceedings of the Fifth International Natural Language Generation Conference, INLG ’08, pages 77–85. find
  13. Drewes, F., Habel, A., and Kreowski, H. (1997). Hyperedge replacement graph grammars. In Rozenberg, G., editor, Handbook of Graph Grammars and Computing by Graph Transformation, pages 95–162. World Scientific. find
  14. Dyer, C., Lopez, A., Ganitkevitch, J., Weese, J., Ture, F., Blunsom, P., Setiawan, H., Eidelman, V., and Resnik, P. (2010). cdec: A decoder, alignment, and learning framework for finite-state and context-free translation models. In Proceedings of ACL. find
  15. Eisner, J. (2003). Learning non-isomorphic tree mappings for machine translation. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 2, pages 205–208. Association for Computational Linguistics. find our card
  16. Galley, M., Graehl, J., Knight, K., Marcu, D., DeNeefe, S., Wang, W., and Thayer, I. (2006). Scalable inference and training of context-rich syntactic translation models. In ACL 2006. find our card
  17. Galley, M., Hopkins, M., Knight, K., and Marcu, D. (2004). What’s in a translation rule. In Proceedings of HLT/NAACL, volume 4, pages 273–280. Boston. find our card
  18. Ge, R. and Mooney, R. J. (2005). A statistical semantic parser that integrates syntax and semantics. In Proceedings of the Ninth Conference on Computational Natural Language Learning, CONLL ’05, pages 9–16. Association for Computational Linguistics. find
  19. Genzel, D. (2010). Automatically learning source-side reordering rules for large scale machine translation. In Proceedings of the 23rd International Conference on Computational Linguistics, pages 376–384. Association for Computational Linguistics. find
  20. Gildea, D. (2003). Loosely tree-based alignment for machine translation. In Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 1, pages 80–87. Association for Computational Linguistics. find
  21. Graehl, J. and Knight, K. (2004). Training tree transducers. In HLT-NAACL, pages 105–112. find our card
  22. Hajič, J., Ciaramita, M., Johansson, R., Kawahara, D., Martí, M. A., Màrquez, L., Meyers, A., Nivre, J., Padó, S., Štěpánek, J., Straňák, P., Surdeanu, M., Xue, N., and Zhang, Y. (2009). The conll-2009 shared task: Syntactic and semantic dependencies in multiple languages. In Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL 2009): Shared Task, pages 1–18, Boulder, Colorado. Association for Computational Linguistics. find our card
  23. Heafield, K. (2011). KenLM: Faster and smaller language model queries. In Proceedings of the Sixth Workshop on Statistical Machine Translation, Edinburgh, UK. Association for Computational Linguistics. find
  24. Hovy, E., Marcus, M., Palmer, M., Ramshaw, L., and Weischedel, R. (2006). OntoNotes: the 90% solution. In Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers, pages 57–60. Association for Computational Linguistics. find
  25. Jones, B., Johnson, M., and Goldwater, S. (2012). Semantic parsing with bayesian tree transducers. In ACL 2012. find
  26. Knight, K. and May, J. (2009). Applications of weighted automata in natural language processing. In Handbook of Weighted Automata. Springer. find
  27. Koehn, P., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., Bertoldi, N., Cowan, B., Shen, W., Moran, C., Zens, R., Dyer, C., Bojar, O., Constantin, A., and Herbst, E. (2007). Moses: open source toolkit for statistical machine translation. In Proceedings of the 45th Annual Meeting of the ACL on Interactive Poster and Demonstration Sessions, ACL ’07, pages 177–180. find
  28. Kwiatkowski, T., Zettlemoyer, L., Goldwater, S., and Steedman, M. (2010). Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1223–1233. Association for Computational Linguistics. find
  29. Landsbergen, J. (1989). The Rosetta project. In Machine Translation Summit II, Munich, Germany. find
  30. Lautemann, C. (1988). Decomposition trees: Structured graph representation and efficient algorithms. In Proceedings of the 13th Colloquium on Trees in Algebra and Programming, CAAP ’88, pages 28–39, London, UK, UK. Springer-Verlag. find
  31. Levy, R. and Manning, C. D. (2003). Is it harder to parse Chinese, or the Chinese Treebank? In Proceedings of ACL 2003, pages 439–446. find
  32. Lu, W., Ng, H., Lee, W., and Zettlemoyer, L. (2008). A generative model for parsing natural language to meaning representations. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 783–792. Association for Computational Linguistics. find
  33. Lu, W. and Ng, H. T. (2011). A probabilistic forest-to-string model for language generation from typed lambda calculus expressions. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 1611–1622. Association for Computational Linguistics. find
  34. Moore, R. C. (1989). Unification-based semantic interpretation. In Proceedings of ACL 1989, pages 33–41. find
  35. Nirenburg, S. (1989). New developments in knowledge-based machine translation. In Alatis, J. E., editor, Georgetown University Round Table on Languages and Linguistics 1989: “Language teaching, testing, and technology: lessons from the past with a view toward the future”, pages 344–357. Georgetown University Press. find
  36. Oates, T., Doshi, S., and Huang, F. (2003). Estimating maximum likelihood parameters for stochastic context-free graph grammars. In Inductive Logic Programming: 13th International Conference, pages 281–298. find
  37. Och, F. J. and Ney, H. (2003). A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1):19–51. ↗
  38. Oepen, S. and Lønning, J. (2006). Discriminant-based MRS banking. In 5th International Conference on Language Resources and Evaluation. find our card
  39. Palmer, M., Gildea, D., and Kingsbury, P. (2005). The proposition bank: An annotated corpus of semantic roles. Computational Linguistics, 31(1):71–106. find our card
  40. Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J. (2002). BLEU: a method for automatic evaluation of machine translation. In Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, ACL ’02, pages 311–318. find our card
  41. Quernheim, D. and Knight, K. (2012). Towards Probabilistic Acceptors and Transducers for Feature Structures. In Proceedings of the Sixth Workshop on Syntax, Semantics and Structure in Statistical Translation. find
  42. Shen, L., Xu, J., and Weischedel, R. (2010). String-to-dependency statistical machine translation. Computational Linguistics, 36(4):649–671. find
  43. Shieber, S. M. (2004). Synchronous grammars as tree transducers. In Proceedings of TAG+7, pages 88–95. find our card
  44. Tang, L. R. and Mooney, R. J. (2001). Using multiple clause constructors in inductive logic programming for semantic parsing. In 12th European Conference on Machine Learning. find
  45. Uchida, H. (1987). ATLAS: Fujitsu machine translation system. In Machine Translation Summit, Japan. find
  46. Varges, S. and Mellish, C. (2001). Instance-based natural language generation. In Proceedings of the second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies, pages 1–8. Association for Computational Linguistics. find
  47. Venugopal, A. and Zollmann, A. (2006). Syntax augmented machine translation via chart parsing. In Proceedings on the Workshop on Statistical Machine Translation. New York City: Association for Computational Linguistics, pages 138–141. find
  48. Weaver, W. (1955). Translation. In Machine translation of languages, volume 14, pages 15–23. MIT Press, Cambridge, MA. find
  49. Wong, Y. W. and Mooney, R. J. (2006). Learning for semantic parsing with statistical machine translation. In Proceedings of the main conference on Human Language Technology Conference of the North American Chapter of the Association of Computational Linguistics, HLT-NAACL ’06, pages 439–446. find
  50. Yamada, K. and Knight, K. (2001). A syntax-based statistical translation model. In Proceedings of the 39th Annual Meeting on Association for Computational Linguistics, ACL ’01, pages 523– 530. find our card
  51. Zettlemoyer, L. and Collins, M. (2005). Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the Twenty-First Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-05), pages 658–666, Arlington, Virginia. AUAI Press. find
  52. Zollmann, A., Venugopal, A., Och, F., and Ponte, J. (2008). A systematic comparison of phrase-based, hierarchical and syntax-augmented statistical MT. In Proceedings of the 22nd International Conference on Computational Linguistics - Volume 1, COLING ’08, pages 1145– 1152. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/jones-2012-semantics-based-machine-translation-hyperedge/