Elamur Research⌕
☰
home / papers / 2019 / Compositional Generalization for Primitive Substitutions

Compositional Generalization for Primitive Substitutions

Paper · 2019 · Yuanpeng Li, Liang Zhao, Jianyu Wang et al.

Summary

Neural sequence models often fail to generalize compositionally. A model that has seen "jump" only in isolation may still be unable to execute "jump twice," even though humans find such recombination trivial. The authors argue that this stems from encoding the input with a single representation. They propose giving each word two embeddings. A "function" embedding feeds a seq2seq decoder that produces a sequence of attention maps over input positions, which determines output order. A "primitive" embedding is pooled through those maps and mapped to output symbols, which determines action identity. Both representations are made low-entropy through L2 regularization plus Gaussian noise during training. The decoder also does not receive previous output symbols, so primitive information cannot leak into the ordering path. Evaluated with exact sequence-level accuracy on SCAN Primitive tasks and other instruction-learning and translation tasks, the method sharply outperforms earlier attention and pointer baselines. It also exceeds human scores on a few-shot learning task. This makes it an early, simple demonstration that architectural priors can encode compositionality.

Key points

  • On the SCAN Jump task, accuracy rises from 14.0% (best prior baseline, Ptr-Loung) to 98.8 ± 1.4%. On TurnLeft, it rises from 92.0% to 99.7 ± 0.4%. Results are averaged over five random seeds.
  • Ablations on Jump show that each component matters:
    • With a single representation, accuracy is 63.4%.
    • With no entropy regularization at all, accuracy is 14.1%.
    • Feeding the last output back into the decoder gives 68.8%.
  • On the SCAN Simple and Length splits, performance is roughly unchanged (99.9% and 20.3%). This indicates the method does not hurt tasks outside its target.
  • The authors introduce SCAN-ADJ, an extended version of SCAN with additional compositional challenges. They report gains across five NLP tasks, including machine translation.
  • Code is released at github.com/yli1/CGPS (Baidu Research, arXiv:1910.02612).

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

🎓Shanghai Jiao Tong UniversityShanghai · China232 works · 20,323 citations🏢BaiduBeijing · China87 works · 17,855 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

Cite

Cite as Yuanpeng Li, Liang Zhao, Jianyu Wang and Joel Hestness. 2019. Compositional Generalization for Primitive Substitutions. arXiv:1910.02612.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1910.02612 · arXiv 1910.02612

@misc{li2019compositional,
  title = {{Compositional Generalization for Primitive Substitutions}},
  author = {Yuanpeng Li, Liang Zhao, Jianyu Wang and Joel Hestness},
  year = {2019},
  doi = {10.48550/arxiv.1910.02612},
  eprint = {1910.02612},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1910.02612}
}

References

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

  1. Martı́n Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016. Tensorflow: A system for large-scale machine learning. In 12th {USENIX} Symposium on Operating Systems Design and Implementation ({OSDI} 16)…
  2. Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars. 2018. Memory aware synapses: Learning what (not) to forget. In Proceedings of the European Conference on Computer Vision (ECCV), pages 139–154.
  3. Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. 2015. Vqa: Visual question answering. In Proceedings of the IEEE international conference on computer vision, pages 2425–2433. find
  4. Joost Bastings, Marco Baroni, Jason Weston, Kyunghyun Cho, and Douwe Kiela. 2018. Jump to better conclusions: SCAN both left and right. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 47–55, Brussels, Belgium. Association for Computati…
  5. Philémon Brakel and Stefan Frank. 2009. Strong systematicity in sentence processing by simple recurrent networks. In 31th Annual Conference of the Cognitive Science Society (COGSCI-2009), pages 1599–1604. Cognitive Science Society. find
  6. Paco Calvo and John Symons. 2014. The Architecture of Cognition: Rethinking Fodor and Pylyshyn’s Systematicity Challenge. MIT Press. find
  7. Michael B Chang, Abhishek Gupta, Sergey Levine, and Thomas L Griffiths. 2018. Automatically composing representation transformations as a means for generalization. arXiv preprint arXiv:1807.04640. — [arXiv:1807.04640](https://arxiv.org/abs/1807.04640) find
  8. Arslan Chaudhry, Marc’Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny. 2019. Efficient lifelong learning with a-gem. In ICLR. find
  9. Noam Chomsky. 1957. Syntactic structures. Walter de Gruyter. find
  10. Abhishek Das, Samyak Datta, Georgia Gkioxari, Stefan Lee, Devi Parikh, and Dhruv Batra. 2018. Embodied question answering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 2054–2063. find
  11. Jerry A Fodor and Ernest Lepore. 2002. The compositionality papers. Oxford University Press. find
  12. Jerry A Fodor and Zenon W Pylyshyn. 1988. Connectionism and cognitive architecture: A critical analysis. Cognition, 28(1-2):3–71. find
  13. K. He, X. Zhang, S. Ren, and J. Sun. 2016. Deep residual learning for image recognition. In CVPR.
  14. Andrej Karpathy and Li Fei-Fei. 2015. Deep visual-semantic alignments for generating image descriptions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3128–3137.
  15. Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980.
  16. Markus Kliegl and Wei Xu. 2018. More systematic than claimed: Insights on the scan tasks. OpenReview. find
  17. A. Krizhevsky, I. Sutskever, and G.E. Hinton. 2012. Imagenet classification with deep convolutional neural networks. In NIPS.
  18. Brenden Lake and Marco Baroni. 2018. Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. In International Conference on Machine Learning, pages 2879–2888. find
  19. Brenden M Lake, Tal Linzen, and Marco Baroni. 2019. Human few-shot learning of compositional instructions. arXiv preprint arXiv:1901.04587. find
  20. 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
  21. Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. 2015. Deep learning. nature, 521(7553):436. find
  22. Tal Linzen, Emmanuel Dupoux, and Yoav Goldberg. 2016. Assessing the ability of lstms to learn syntax-sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521–535.
  23. Adam Liška, Germán Kruszewski, and Marco Baroni. 2018. Memorize or generalize? searching for a compositional rnn in a haystack. arXiv preprint arXiv:1802.06467. — [arXiv:1802.06467](https://arxiv.org/abs/1802.06467) find
  24. Joao Loula, Marco Baroni, and Brenden M Lake. 2018a. Rearranging the familiar: Testing compositional generalization in recurrent networks. arXiv preprint arXiv:1807.07545.
  25. Joao Loula, Marco Baroni, Brenden M, and Linzen. 2018b. Rearrange the familiar: testing compositional generalization in recurrent networks. arXiv preprint arXiv:1807.07545.
  26. Gary F Marcus. 1998. Rethinking eliminative connectionism. Cognitive psychology, 37(3):243–282. find
  27. Gary F Marcus. 2003. The algebraic mind: Integrating connectionism and cognitive science. MIT press. find
  28. Marvin Minsky. 1986. Society of mind. Simon and Schuster. find
  29. Richard Montague. 1970. Universal grammar. Theoria, 36(3):373–398. find
  30. Paul Rodriguez and Janet Wiles. 1998. Recurrent neural networks can learn to implement symbol-sensitive counting. In Advances in Neural Information Processing Systems, pages 87–93. find
  31. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112.
  32. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems, pages 5998–6008.
  33. Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer networks. In Advances in Neural Information Processing Systems, pages 2692–2700. find
  34. Gail Weiss, Yoav Goldberg, and Eran Yahav. 2018. On the practical computational power of finite precision rnns for language recognition. arXiv preprint arXiv:1805.04908.
  35. Francis CK Wong and William SY Wang. 2007. Generalisation towards combinatorial productivity in language acquisition by simple recurrent networks. In 2007 International Conference on Integration of Knowledge Intensive Multi-Agent Systems, pages 139–144. IEEE. find
  36. Y. Wu and et al. 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation. In arXiv:1609.08144. find
  37. Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. 2015. Show, attend and tell: Neural image caption generation with visual attention. In International conference on machine learning, pages 2048–2057.
  38. Guangyu Robert Yang, Madhura R Joglekar, H Francis Song, William T Newsome, and Xiao-Jing Wang. 2019. Task representations in neural networks trained to perform many cognitive tasks. Nature neuroscience, page 1. find
  39. D. Yu and L. Deng. 2012. Automatic Speech Recognition. Springer. find
  40. Friedemann Zenke, Ben Poole, and Surya Ganguli. 2017. Continual learning through synaptic intelligence. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3987–3995. JMLR. org. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-2019-compositional-generalization-primitive-substitutions/