Elamur Research⌕
☰
home / papers / 2022 / Improving Compositional Generalization with Latent Structure and Data Augmentation

Improving Compositional Generalization with Latent Structure and Data Augmentation

Paper · 2022 · Linlu Qiu, Peter Shaw, Panupong Pasupat et al.

Summary

Pre-trained sequence-to-sequence models such as T5 cope well with natural language variation. However, they often fail when test inputs combine familiar elements in unseen ways. Specialized models with discrete latent structure handle such compositions better, but their gains have mostly been limited to synthetic benchmarks. The authors bridge the two with data augmentation. They introduce the Compositional Structure Learner (CSL), a generative model built on a quasi-synchronous context-free grammar (QCFG) induced automatically from training pairs. CSL extends the earlier discriminative NQG model with richer rules, cheaper and parallelizable induction, and the ability to sample from a joint distribution over inputs and outputs. Synthetic utterance–program pairs drawn from CSL are mixed with the original data to fine-tune T5. On the diagnostic SCAN and COGS tasks, this moves most of CSL's compositional bias into T5. On compositional splits of GeoQuery and SMCalFlow-CS, the augmented T5 even surpasses a T5+CSL ensemble, setting new state-of-the-art results. The work shows that probabilistic models over induced latent structure can serve as general-purpose data generators for black-box pretrained models without task-specific engineering.

Key points

  • CSL generalizes earlier recombination methods. Compared with Jia and Liang (2016), it uses a generic grammar search over a larger rule space. Unlike GECA, it recombines examples recursively and defines a proper probability distribution for sampling.
  • Sampling with CSL's learned parametric model outperforms uniform sampling from the induced grammar on most splits. On the SMCalFlow-CS 8-shot split, raising the sampling temperature helps, producing over 15 times more cross-domain examples.
  • Evaluation covers the synthetic SCAN and COGS benchmarks plus the real-world GeoQuery and SMCalFlow-CS compositional splits.
  • Updating the model with unlabeled target-distribution inputs makes augmentation more sample-efficient. The effect fades when many synthetic examples can be drawn.
  • The authors note two limitations: QCFG cannot capture every language-to-logical-form phenomenon, and experiments cover English only. Code is released in the google-research/language repository (compgen/csl).

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

 Institutions

🏢GoogleMountain View · United States353 works · 364,806 citations🎓New York UniversityNew York · United States136 works · 86,390 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha and Kristina Toutanova. 2022. Improving Compositional Generalization with Latent Structure and Data Augmentation. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2022.naacl-main.323

@inproceedings{qiu2022improving,
  title = {{Improving Compositional Generalization with Latent Structure and Data Augmentation}},
  author = {Linlu Qiu, Peter Shaw, Panupong Pasupat, Pawel Nowak, Tal Linzen, Fei Sha and Kristina Toutanova},
  booktitle = {Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies},
  year = {2022},
  doi = {10.18653/v1/2022.naacl-main.323},
  url = {https://doi.org/10.18653/v1/2022.naacl-main.323}
}

References

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

  1. Alfred V Aho and Jeffrey D Ullman. 1972. The theory of parsing, translation, and compiling, volume 1. Prentice-Hall Englewood Cliffs, NJ. find
  2. Ekin Akyürek, Afra Feyza Akyürek, and Jacob Andreas. 2021. Learning to recombine and resample data for compositional generalization. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net. find
  3. Jacob Andreas. 2020. Good-enough compositional data augmentation. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 7556–7566, Online. Association for Computational Linguistics.
  4. Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, Hao Fang, Alan Guo, David Hall, Kristin Hayes, Kellie Hill, Diana Ho, Wendy Iwaszuk, Smriti Jha, Dan Klein, Jayant Krishnamurthy, Theo Lanman, Percy Liang, Chris…
  5. Jacob Andreas, Andreas Vlachos, and Stephen Clark. 2013. Semantic parsing as machine translation. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 47–52, Sofia, Bulgaria. Association for Computational Linguistics. find
  6. Yoav Artzi, Dipanjan Das, and Slav Petrov. 2014. Learning compact lexicons for CCG semantic parsing. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1273–1283, Doha, Qatar. Association for Computational Linguistics. find
  7. Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. 2018. Relational inductive biases, deep learning, and graph networks. ArXiv preprint, abs/1806.01261.
  8. Phil Blunsom, Trevor Cohn, and Miles Osborne. 2008. A discriminative latent variable model for statistical machine translation. In Proceedings of ACL-08: HLT, pages 200–208, Columbus, Ohio. Association for Computational Linguistics.
  9. Peter F. Brown, Stephen A. Della Pietra, Vincent J. Della Pietra, and Robert L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263– 311. find
  10. Xinyun Chen, Chen Liang, Adams Wei Yu, Dawn Song, and Denny Zhou. 2020. Compositional generalization via neural-symbolic stack machines. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtua… find
  11. David Chiang. 2007. Hierarchical phrase-based translation. Computational Linguistics, 33(2):201–228.
  12. John Cocke. 1969. Programming languages and their compilers: Preliminary notes. New York University. find
  13. Henry Conklin, Bailin Wang, Kenny Smith, and Ivan Titov. 2021. Meta-learning to compositionally generalize. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), p… find
  14. Róbert Csordás, Kazuki Irie, and Juergen Schmidhuber. 2021. The devil is in the detail: Simple tricks improve systematic generalization of transformers. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 619–634, Online and Punta Cana, Dominican Republic… find
  15. Li Dong and Mirella Lapata. 2018. Coarse-to-fine decoding for neural semantic parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 731–742, Melbourne, Australia. Association for Computational Linguistics. find
  16. Catherine Finegan-Dollak, Jonathan K. Kummerfeld, Li Zhang, Karthik Ramanathan, Sesh Sadasivam, Rui Zhang, and Dragomir Radev. 2018. Improving text-to-SQL evaluation methodology. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages…
  17. Daniel Furrer, Marc van Zee, Nathan Scales, and Nathanael Schärli. 2020. Compositional generalization in semantic parsing: Pre-training vs. specialized architectures. ArXiv preprint, abs/2007.08970. find
  18. Jonathan Gordon, David Lopez-Paz, Marco Baroni, and Diane Bouchacourt. 2020. Permutation equivariant models for compositional generalization in language. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net. find
  19. Peter Grünwald. 1995. A minimum description length approach to grammar inference. In International Joint Conference on Artificial Intelligence, pages 203–216. Springer. find
  20. Peter Grunwald. 2004. A tutorial introduction to the minimum description length principle. arXiv preprint math/0406077. find
  21. Demi Guo, Yoon Kim, and Alexander Rush. 2020. Sequence-level mixed sample data augmentation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 5547–5552, Online. Association for Computational Linguistics. find
  22. Yinuo Guo, Hualei Zhu, Zeqi Lin, Bei Chen, Jian-Guang Lou, and Dongmei Zhang. 2021. Revisiting iterative back-translation from the perspective of compositional generalization. In AAAI. find
  23. Jonathan Herzig and Jonathan Berant. 2019. Don’t paraphrase, detect! rapid and effective data collection for semantic parsing. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJ… find
  24. Jonathan Herzig and Jonathan Berant. 2021. Span-based semantic parsing for compositional generalization. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), page… find
  25. Jonathan Herzig, Peter Shaw, Ming-Wei Chang, Kelvin Guu, Panupong Pasupat, and Yuan Zhang. 2021. Unlocking compositional generalization in pre-trained models using intermediate representations. ArXiv preprint, abs/2104.07478. — [arXiv:2104.07478](https://arxiv.org/abs/2104.07478) find
  26. Theo MV Janssen and Barbara H Partee. 1997. Compositionality. In Handbook of logic and language, pages 417–473. Elsevier. find
  27. Rohit J Kate, Yuk Wah Wong, and Raymond J Mooney. 2005. Learning to transform natural to formal languages. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1062. find
  28. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999. find
  29. Daniel Keysers, Nathanael Schärli, Nathan Scales, Hylke Buisman, Daniel Furrer, Sergii Kashubin, Nikola Momchev, Danila Sinopalnikov, Lukasz Stafiniak, Tibor Tihon, Dmitry Tsarkov, Xiao Wang, Marc van Zee, and Olivier Bousquet. 2020. Measuring compositional generalization: A comprehensive method on… find
  30. Najoung Kim and Tal Linzen. 2020. COGS: A compositional generalization challenge based on semantic interpretation. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 9087–9105, Online. Association for Computational Linguistics. find
  31. Yoon Kim. 2021. Sequence-to-sequence learning with latent neural grammars. In Advances in Neural Information Processing Systems. find
  32. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A method for stochastic optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings. find
  33. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proceedings of the 41st Annual Meeting of the Association for Computational Linguistics, pages 423–430, Sapporo, Japan. Association for Computational Linguistics.
  34. Robin Jia and Percy Liang. 2016. Data recombination for neural semantic parsing. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 12–22, Berlin, Germany. Association for Computational Linguistics. find
  35. Tom Kwiatkowksi, Luke Zettlemoyer, Sharon Goldwater, and Mark Steedman. 2010. Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1223–1233, Cambridge, MA. Association fo… find
  36. Yichen Jiang and Mohit Bansal. 2021. Inducing transformer’s compositional generalization ability via auxiliary sequence prediction tasks. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 6253–6265, Online and Punta Cana, Dominican Republic. Association… find
  37. Tom Kwiatkowski, Eunsol Choi, Yoav Artzi, and Luke Zettlemoyer. 2013. Scaling semantic parsers with on-the-fly ontology matching. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1545–1556, Seattle, Washington, USA. Association for Computational Lingui…
  38. Mark Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):613–632.
  39. T. Kasami. 1965. An efficient recognition and syntax analysis algorithm for context-free languages. Technical Report AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, MA. find
  40. Brenden M. Lake. 2019. Compositional generalization through meta sequence-to-sequence learning. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 9788– 9798. find
  41. Brenden M. Lake and Marco Baroni. 2018. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 o… find
  42. Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman. 2017. Building machines that learn and think like people. Behavioral and brain sciences, 40. find
  43. Yuanpeng Li, Liang Zhao, Jianyu Wang, and Joel Hestness. 2019. Compositional generalization for primitive substitutions. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP),… find
  44. Percy Liang. 2013. Lambda dependency-based compositional semantics. ArXiv preprint, abs/1309.4408. find
  45. Chenyao Liu, Shengnan An, Zeqi Lin, Qian Liu, Bei Chen, Jian-Guang Lou, Lijie Wen, Nanning Zheng, and Dongmei Zhang. 2021. Learning algebraic recombination for compositional generalization. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 1129–1144, Online. Associ… find
  46. Qian Liu, Shengnan An, Jian-Guang Lou, Bei Chen, Zeqi Lin, Yan Gao, Bin Zhou, Nanning Zheng, and Dongmei Zhang. 2020. Compositional generalization by learning analytical expressions. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2… find
  47. Richard Montague. 1970. Universal grammar. Theoria, 36(3):373–398. find
  48. Benjamin Newman, John Hewitt, Percy Liang, and Christopher D. Manning. 2020. The EOS decision and length extrapolation. In Proceedings of the Third BlackboxNLP Workshop on Analyzing and Interpreting Neural Networks for NLP, pages 276–291, Online. Association for Computational Linguistics. find
  49. Maxwell I. Nye, Armando Solar-Lezama, Josh Tenenbaum, and Brenden M. Lake. 2020. Learning compositional rules via neural program synthesis. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, vir… find
  50. Santiago Ontanón, Joshua Ainslie, Vaclav Cvicek, and Zachary Fisher. 2021. Making transformers solve compositional tasks. ArXiv preprint, abs/2108.04378. find
  51. Inbar Oren, Jonathan Herzig, and Jonathan Berant. 2021. Finding needles in a haystack: Sampling structurally-diverse training sets from synthetic data for compositional generalization. In EMNLP. find
  52. Inbar Oren, Jonathan Herzig, Nitish Gupta, Matt Gardner, and Jonathan Berant. 2020. Improving compositional generalization in semantic parsing. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages 2482–2495, Online. Association for Computational Linguistics. find
  53. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of Machine Learning Research, 21:1–67.
  54. Jorma Rissanen. 1978. Modeling by shortest data description. Automatica, 14(5):465–471. find
  55. Luana Ruiz, Joshua Ainslie, and Santiago Ontañón. 2021. Iterative decoding for compositional generalization in transformers. ArXiv preprint, abs/2110.04169. — [arXiv:2110.04169](https://arxiv.org/abs/2110.04169) find
  56. Jake Russin, Jason Jo, Randall C O’Reilly, and Yoshua Bengio. 2019. Compositional generalization in a deep seq2seq model by separating syntax and semantics. ArXiv preprint, abs/1904.09708. find
  57. Markus Saers, Karteek Addanki, and Dekai Wu. 2013. Unsupervised transduction grammar induction via minimum description length. In Proceedings of the Second Workshop on Hybrid Approaches to Translation, pages 67–73, Sofia, Bulgaria. Association for Computational Linguistics. find
  58. Peter Shaw, Ming-Wei Chang, Panupong Pasupat, and Kristina Toutanova. 2021. Compositional generalization and natural language variation: Can a semantic parsing approach handle both? In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International… find
  59. David Smith and Jason Eisner. 2006. Quasi-synchronous grammars: Alignment by soft projection of syntactic dependencies. In Proceedings on the Workshop on Statistical Machine Translation, pages 23–30, New York City. Association for Computational Linguistics.
  60. Lappoon R Tang and Raymond J Mooney. 2001. Using multiple clause constructors in inductive logic programming for semantic parsing. In European Conference on Machine Learning, pages 466–477. Springer. find
  61. Ke Tran and Ming Tan. 2020. Generating synthetic data for task-oriented semantic parsing with hierarchical representations. In Proceedings of the Fourth Workshop on Structured Prediction for NLP, pages 17–21, Online. Association for Computational Linguistics. find
  62. Bailan Wang, Mirella Lapata, and Ivan Titov. 2021a. Structured reordering for modeling latent alignments in sequence transduction. Advances in Neural Information Processing Systems, 34. find
  63. Bailin Wang, Wenpeng Yin, Xi Victoria Lin, and Caiming Xiong. 2021b. Learning to synthesize data for semantic parsing. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2760–2766, Online. Associati… find
  64. Yuk Wah Wong and Raymond Mooney. 2006. Learning for semantic parsing with statistical machine translation. In Proceedings of the Human Language Technology Conference of the NAACL, Main Conference, pages 439–446, New York City, USA. Association for Computational Linguistics.
  65. Hao Zheng and Mirella Lapata. 2020. Compositional generalization via semantic tagging. ArXiv preprint, abs/2010.11818. find
  66. Victor Zhong, Mike Lewis, Sida I. Wang, and Luke Zettlemoyer. 2020. Grounded adaptation for zero-shot executable semantic parsing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 6869– 6882, Online. Association for Computational Linguistics.
  67. Wang Zhu, Peter Shaw, Tal Linzen, and Fei Sha. 2021. Learning to generalize compositionally by transferring across semantic parsing tasks. ArXiv preprint, abs/2111.05013. — [arXiv:2111.05013](https://arxiv.org/abs/2111.05013) find
  68. Yuk Wah Wong and Raymond Mooney. 2007. Learning synchronous grammars for semantic parsing with lambda calculus. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 960–967, Prague, Czech Republic. Association for Computational Linguistics.
  69. Pengcheng Yin, Hao Fang, Graham Neubig, Adam Pauls, Emmanouil Antonios Platanios, Yu Su, Sam Thomson, and Jacob Andreas. 2021. Compositional generalization for neural semantic parsing via span-level supervised attention. In Proceedings of the 2021 Conference of the North American Chapter of the Asso… find
  70. Daniel H Younger. 1967. Recognition and parsing of context-free languages in time n3. Information and control, 10(2):189–208. find
  71. John M Zelle and Raymond J Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proceedings of the thirteenth national conference on Artificial intelligence-Volume 2, pages 1050–1055.
  72. Luke Zettlemoyer and Michael Collins. 2007. Online learning of relaxed CCG grammars for parsing to logical form. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 678–687, Prague, Czech Rep… find
  73. Luke S Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form: structured classification with probabilistic categorial grammars. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 658–666. AUAI Press.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/qiu-2022-improving-compositional-generalization-latent-structure/