Elamur Research⌕
☰
home / papers / 2019 / Compositionality decomposed: how do neural networks generalise?

Compositionality decomposed: how do neural networks generalise?

Paper · 2019 · Dieuwke Hupkes, Verna Dankers, Mathijs Mul et al.

Summary

Researchers still disagree on whether neural networks are capable of compositional generalisation. The authors attribute this to the fact that everyone understands compositionality in their own way. They therefore collected conceptions of it from linguistics and philosophy and condensed them into five behavioural tests that are not tied to any specific task. The tests check whether a model can recombine known parts and rules in novel ways, whether it can handle sequences longer than those seen during training, whether it composes locally or globally, whether it is stable under synonym substitution, and what it favours during training: rules or exceptions. For the evaluation, the authors created an artificial and fully compositional dataset, PCFG SET. On it, they compared three seq2seq architectures: recurrent, convolutional and Transformer. Each model turned out to be strong in some aspects and weak in others. The conclusion is that a single overall accuracy score, even on a highly compositional task, does not show whether a model is truly compositional. The authors have made the data generator, test sets and trained models publicly available.

Key points

  • The five tests correspond to five aspects of compositionality: systematicity, productivity, localism, synonym substitution and overgeneralisation.
  • Three models were compared: LSTMS2S, ConvS2S and Transformer. All of them were trained on PCFG SET, an artificial dataset built using a PCFG.
  • When exceptions are rare (up to 0.1% of the frequency of the rarer function in the pair), all three models overgeneralise early in training. Hence, at this stage they have already learned the rule itself.
  • If exceptions make up only 0.01%, Transformer and LSTMS2S never learn them. ConvS2S also struggles with this, though to a lesser extent. LSTMS2S often produces an output that matches neither the rule nor the exception. From 0.5% exceptions onwards, overgeneralisation is practically not observed.
  • The work was published in JAIR (vol. 67, 2020). In future work, the authors plan to transfer the tests to natural language, in particular to translation and summarisation tasks.

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

🎓University of AmsterdamAmsterdam · Netherlands151 works · 174,506 citations🎓Universitat Pompeu FabraBarcelona · Spain48 works · 12,092 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

💡 Concepts 1Key ideas and methods explained on our concept pages.Semantics · 57 works

Cite

Cite as Dieuwke Hupkes, Verna Dankers, Mathijs Mul and Elia Bruni. 2019. Compositionality decomposed: how do neural networks generalise?. arXiv:1908.08351.

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

@misc{hupkes2019compositionality,
  title = {{Compositionality decomposed: how do neural networks generalise?}},
  author = {Dieuwke Hupkes, Verna Dankers, Mathijs Mul and Elia Bruni},
  year = {2019},
  doi = {10.48550/arxiv.1908.08351},
  eprint = {1908.08351},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1908.08351}
}

References

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

  1. Andreas, J. (2019). Measuring compositionality in representation learning. In Proceedings of the 7th International Conference on Learning Representations (ICLR). find
  2. Bahdanau, D., Cho, K., and Bengio, Y. (2015). Neural machine translation by jointly learning to align and translate. In Proceedings of the 3rd International Conference on Learning Representations (ICLR).
  3. Bahdanau, D., Murty, S., Noukhovitch, M., Nguyen, T. H., de Vries, H., and Courville, A. (2018). Systematic generalization: What is required and can it be learned? In Proceedings of the 6th International Conference on Learning Representations (ICLR).
  4. Bai, S., Kolter, J. Z., and Koltun, V. (2018). An empirical evaluation of generic convolutional and recurrent networks for sequence modeling. CoRR, abs/1803.0127. find
  5. Baroni, M. and Zamparelli, R. (2010). Nouns are vectors, adjectives are matrices: representing adjective-noun constructions in semantic space. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1183–1193. find
  6. Batali, J. (1994). Artificial evolution of syntactic aptitude. In Proceedings of the 16th Annual Conference of the Cognitive Science Society (CogSci), pages 27–32. find
  7. Belinkov, Y., Màrquez, L., Sajjad, H., Durrani, N., Dalvi, F., and Glass, J. (2017). Evaluating layers of representation in neural machine translation on part-of-speech and semantic tagging tasks. In Proceedings of the 8th International Joint Conference on Natural Language Processing (IJCNLP), volu…
  8. Blevins, T., Levy, O., and Zettlemoyer, L. (2018). Deep RNNs encode soft hierarchical syntax. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), volume 2, pages 14–19.
  9. Bojar, O., Buck, C., Chatterjee, R., Federmann, C., Graham, Y., Haddow, B., Huck, M., Jimeno-Yepes, A., Koehn, P., and Kreutzer, J., editors (2017). Proceedings of the Second Conference on Machine Translation (WMT). 19. https://github.com/i-machine-think/am-i-compositional ↗
  10. Boleda, G. and Herbelot, A. (2016). Formal distributional semantics: introduction to the special issue. Computational Linguistics, 42(4):619–635. find
  11. Bowman, S. R., Manning, C. D., and Potts, C. (2015). Tree-structured composition in neural networks without tree-structured architectures. In Proceedings of the 2015th International Conference on Cognitive Computation: Integrating Neural and Symbolic Approaches, pages 37–42. find
  12. Carnap, R. (1947). Meaning and necessity: A study in semantics and modal logic. University of Chicago Press. find
  13. Chomsky, N. (1956). Three models for the description of language. IRE Transactions on information theory, 2(3):113–124. find
  14. Chorowski, J. K., Bahdanau, D., Serdyuk, D., Cho, K., and Bengio, Y. (2015). Attention-based models for speech recognition. In Advances in Neural Information Processing Systems (NIPS), pages 577–585.
  15. Christiansen, M. H. and Chater, N. (1999). Toward a connectionist model of recursion in human linguistic performance. Cognitive Science, 23(2):157–205. find
  16. Chung, J., Gulcehre, C., Cho, K., and Bengio, Y. (2014). Empirical evaluation of gated recurrent neural networks on sequence modeling. CoRR, abs/1412.3555. find
  17. Clark, S. (2015). Vector space models of lexical meaning. The Handbook of Contemporary semantic theory, pages 493–522. find
  18. Coecke, B., Sadrzadeh, M., and Clark, S. (2010). Mathematical foundations for a compositional distributional model of meaning. Linguistic analysis, 36(1-4):345–384. find
  19. Denil, M., Demiraj, A., Kalchbrenner, N., Blunsom, P., and de Freitas, N. (2014). Modelling, visualising and summarising documents with a single convolutional neural network. CoRR, abs/1406.3830. — [arXiv:1406.3830](https://arxiv.org/abs/1406.3830) find
  20. Dessı̀, R. and Baroni, M. (2019). CNNs found to jump around more skillfully than RNNs: Compositional generalization in seq2seq convolutional networks. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), pages 3919–3923. find
  21. Dubois, Y., Dagan, G., Hupkes, D., and Bruni, E. (2019). Location attention for extrapolation to longer sequences. CoRR, abs/1911.03872. find
  22. Elman, J. L. (1991). Distributed representations, simple recurrent networks, and grammatical structure. Machine learning, 7(2-3):195–225. find
  23. Erk, K. (2012). Vector space models of word meaning and phrase meaning: A survey. Language and Linguistics Compass, 6(10):635–653. find
  24. Fodor, J. A. and Pylyshyn, Z. W. (1988). Connectionism and cognitive architecture: a critical analysis. Cognition, 28(1-2):3–71. find
  25. Gehring, J., Auli, M., Grangier, D., and Dauphin, Y. N. (2017a). A convolutional encoder model for neural machine translation. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL), volume 1, pages 123–135.
  26. Gehring, J., Auli, M., Grangier, D., Yarats, D., and Dauphin, Y. N. (2017b). Convolutional sequence to sequence learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1243–1252.
  27. Giulianelli, M., Harding, J., Mohnert, F., Hupkes, D., and Zuidema, W. (2018). Under the hood: Using diagnostic classifiers to investigate and improve how language models track agreement information. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks fo… find
  28. Goldberg, Y. (2019). Assessing BERT’s syntactic abilities. CoRR, abs/1901.05287.
  29. Goller, C. and Kuchler, A. (1996). Learning task-dependent distributed representations by backpropagation through structure. In Proceedings of International Conference on Neural Networks (ICNN), volume 1, pages 347–352. find
  30. Gulordava, K., Bojanowski, P., Grave, E., Linzen, T., and Baroni, M. (2018). Colorless green recurrent networks dream hierarchically. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), volume…
  31. He, X. and Golub, D. (2016). Character-level question answering with attention. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1598–1607. find
  32. Hirschberg, J. and Manning, C. D. (2015). Advances in natural language processing. Science, 349(6245):261–266. find
  33. Hochreiter, S. and Schmidhuber, J. (1997). Long short-term memory. Neural computation, 9(8):1735– 1780. find
  34. Hupkes, D., Singh, A., Korrel, K., Kruszewski, G., and Bruni, E. (2019). Learning compositionally through attentive guidance. In International Conference on Computational Linguistics and Intelligent Text Processing (CICLing). find
  35. Hupkes, D., Veldhoen, S., and Zuidema, W. (2018). Visualisation and ‘diagnostic classifiers’ reveal how recurrent and recursive neural networks process hierarchical structure. Journal of Artificial Intelligence Research, 61:907–926. find
  36. Husserl, E. (1913). Logische Untersuchungen. Max Niemeyer. find
  37. Jacobson, P. (2002). The (dis)organization of the grammar: 25 years. Linguistics and Philosophy, 25(5):601–626. find
  38. Janssen, T. (1983). Foundations and applications of Montague grammar. Mathematisch Centrum. find
  39. Johnson, J., Hariharan, B., van der Maaten, L., Fei-Fei, L., Zitnick, C. L., and Girshick, R. (2017). CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1988–1997.
  40. Jozefowicz, R., Vinyals, O., Schuster, M., Shazeer, N., and Wu, Y. (2016). Exploring the limits of language modeling. CoRR, abs/1602.02410. find
  41. Kalchbrenner, N., Grefenstette, E., and Blunsom, P. (2014). A convolutional neural network for modelling sentences. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (ACL), volume 1, pages 655–665.
  42. Kartsaklis, D. (2014). Compositional operators in distributional semantics. Springer Science Reviews, 2(1-2):161–177. find
  43. Kim, Y., Rush, A. M., Yu, L., Kuncoro, A., Dyer, C., and Melis, G. (2019). Unsupervised recurrent neural network grammars. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT), volume 1, pages 11… find
  44. Klein, G., Kim, Y., Deng, Y., Senellart, J., and Rush, A. M. (2017). OpenNMT: Open-source toolkit for neural machine translation. In Bansal, M. and Ji, H., editors, Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL), System Demonstrations, pages 67–72.
  45. Korrel, K., Hupkes, D., Dankers, V., and Bruni, E. (2019). Transcoding compositionally: using attention to find more generalizable solutions. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, page 111. find
  46. Lake, B. and Baroni, M. (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), pages 4487–4499. find
  47. Lakretz, Y., Kruszewski, G., Desbordes, T., Hupkes, D., Dehaene, S., and Baroni, M. (2019). The emergence of number and syntax units in LSTM language models. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolog…
  48. Le, P. and Zuidema, W. (2015). The forest convolutional network: compositional distributional semantics with a neural chart and without binarization. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1155–1164. find
  49. Lin, Y., Tan, Y. C., and Frank, R. (2019). Open sesame: Getting inside BERT’s linguistic knowledge. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 241–253.
  50. Linzen, T., Dupoux, E., and Goldberg, Y. (2016). Assessing the ability of LSTMs to learn syntax-sensitive dependencies. Transactions of the Association for Computational Linguistics, 4:521–535.
  51. Liška, A., Kruszewski, G., and Baroni, M. (2018). Memorize or generalize? Searching for a compositional RNN in a haystack. In Proceedings of AEGAP (FAIM Joint Workshop on Architectures and Evaluation for Generality, Autonomy and Progress in AI). find
  52. Loula, J., Baroni, M., and Lake, B. M. (2018). Rearranging the familiar: testing compositional generalization in recurrent networks. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 108–114.
  53. Manning, C. D., Surdeanu, M., Bauer, J., Finkel, J., Bethard, S. J., and McClosky, D. (2014). The Stanford CoreNLP natural language processing toolkit. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (ACL), System Demonstrations, pages 55–60.
  54. Marcus, G. F. (2003). The algebraic mind: Integrating connectionism and cognitive science. MIT press. find
  55. Marcus, G. F., Pinker, S., Ullman, M., Hollander, M., Rosen, T. J., Xu, F., and Clahsen, H. (1992). Overregularization in language acquisition. Monographs of the society for research in child development, pages i–178. find
  56. Mareček, D. and Rosa, R. (2018). Extracting syntactic trees from transformer encoder self-attentions. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 347–349. find
  57. McCoy, R. T., Linzen, T., Dunbar, E., and Smolensky, P. (2019). RNNs implicitly implement tensor-product representations. In Proceedings of the 7th International Conference on Learning Representations (ICLR). find
  58. Miller, G. A. and Charles, W. G. (1991). Contextual correlates of semantic similarity. Language and cognitive processes, 6(1):1–28. find
  59. Mitchell, J. and Lapata, M. (2008). Vector-based models of semantic composition. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technology (ACL-HLT), pages 236–244. find
  60. Mul, M. and Zuidema, W. (2019). Siamese recurrent networks learn first-order logic reasoning and exhibit zero-shot compositional generalization. CoRR, abs/1906.00180. — [arXiv:1906.00180](https://arxiv.org/abs/1906.00180) find
  61. Pagin, P. (2003). Communication and strong compositionality. Journal of Philosophical Logic, 32(3):287–322. find
  62. Pagin, P. and Westerståhl, D. (2010). Compositionality i: Definitions and variants. Philosophy Compass, 5(3):250–264. find
  63. Partee, B. (1995). Lexical semantics and compositionality. An invitation to cognitive science: Language, 1:311–360. find
  64. Penke, M. (2012). The dual-mechanism debate. In The Oxford handbook of compositionality. Oxford University Press. find
  65. Pinker, S. (1984). Language learnability and language development. Cambridge, MA: Harvard University Press. find
  66. Plate, T. (1991). Holographic reduced representations: convolution algebra for compositional distributed representations. In Proceedings of the 12th International Joint Conference on Artificial Intelligence (IJCAI), volume 1, pages 30–35. find
  67. Potts, C. (2019). A case for deep learning in semantics: Response to pater. Language. find
  68. Pullum, G. K. and Scholz, B. C. (2010). Recursion and the infinitude claim. Recursion in human language, 104:113–38. find
  69. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019). Language models are unsupervised multitask learners. OpenAI Blog, 1(8). find
  70. Raganato, A. and Tiedemann, J. (2018). An analysis of encoder representations in transformer-based machine translation. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 287–297.
  71. Rodriguez, P. (2001). Simple recurrent networks learn context-free and context-sensitive languages by counting. Neural computation, 13(9):2093–118. find
  72. Rodriguez, P., Wiles, J., and Elman, J. L. (1999). A recurrent neural network that learns to count. Connection Science, 11(1):5–40. find
  73. Rumelhart, D. E. and McClelland, J. L. (1986). Parallel distributed processing: explorations in the microstructure of cognition, volume 2, chapter On learning the past tenses of English verbs, pages 216–271. MIT Press, Cambridge. find
  74. Saxton, D., Grefenstette, E., Hill, F., and Kohli, P. (2019). Analysing mathematical reasoning abilities of neural models. In Proceedings of the 7th International Conference on Learning Representations (ICLR).
  75. Shi, X., Padhi, I., and Knight, K. (2016). Does string-based neural MT learn source syntax? In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1526–1534.
  76. Smolensky, P. (1990). Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial intelligence, 46(1-2):159–216. find
  77. Socher, R., Manning, C. D., and Ng, A. Y. (2010). Learning continuous phrase representations and syntactic parsing with recursive neural networks. In Proceedings of the NIPS2010 Deep Learning and Unsupervised Feature Learning Workshop, pages 1–9. find
  78. Soulos, P., McCoy, T., Linzen, T., and Smolensky, P. (2019). Discovering the compositional structure of vector representations with role learning networks. In Proceedings of the NeurIPS 2019 Workshop on Context and Compositionality in biological and artificial neural systems. find
  79. Sutskever, I., Vinyals, O., and Le, Q. V. (2014). Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems (NIPS), pages 3104–3112.
  80. Szabó, Z. (2012). The case for compositionality. The Oxford handbook of compositionality, 64:80. find
  81. Tenney, I., Das, D., and Pavlick, E. (2019a). BERT rediscovers the classical NLP pipeline. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), pages 4593–4601.
  82. Tenney, I., Xia, P., Chen, B., Wang, A., Poliak, A., McCoy, R. T., Kim, N., Van Durme, B., Bowman, S. R., Das, D., et al. (2019b). What do you learn from context? Probing for sentence structure in contextualized word representations. In Proceedings of the 7th International Conference on Learning Rep…
  83. Tran, K., Bisazza, A., and Monz, C. (2018). The importance of being recurrent for modeling hierarchical structure. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 4731–4736.
  84. Turney, P. D. and Pantel, P. (2010). From frequency to meaning: Vector space models of semantics. Journal of Artificial Intelligence Research, 37:141–188.
  85. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. (2017). Attention is all you need. In Advances in Neural Information Processing Systems (NIPS), pages 5998–6008.
  86. Veldhoen, S., Hupkes, D., and Zuidema, W. (2016). Diagnostic classifiers: Revealing how neural networks process hierarchical structure. In Proceedings of the NIPS2016 Workshop on Cognitive Computation: Integrating Neural and Symbolic Approaches. find
  87. Vig, J. and Belinkov, Y. (2019). Analyzing the structure of attention in a transformer language model. Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pages 63–76.
  88. Weiss, G., Goldberg, Y., and Yahav, E. (2018a). Extracting automata from recurrent neural networks using queries and counterexamples. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80, pages 5244–5253. find
  89. Weiss, G., Goldberg, Y., and Yahav, E. (2018b). On the practical computational power of finite precision RNNs for language recognition. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL), volume 2, pages 740–745.
  90. Wiles, J. and Elman, J. (1995). Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent networks. In Proceedings of the 17th Annual Conference of the Cognitive Science Society (CogSci), pages 482–487. find
  91. Wolf, T. (2019). Some additional experiments extending the tech report “Assessing BERTs syntactic abilities” by Yoav Goldberg. Technical report.
  92. Zadrozny, W. (1994). From compositional to systematic semantics. Linguistics and philosophy, 17(4):329–342. find
  93. Zaremba, W. and Sutskever, I. (2014). Learning to execute. CoRR, abs/1410.4615. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/hupkes-2019-compositionality-decomposed-neural-networks-generalise/