A Complexity-Based Theory of Compositionality

• URL: http://arxiv.org/abs/2410.14817v1
• Date: Fri, 18 Oct 2024 18:37:27 GMT
• Title: A Complexity-Based Theory of Compositionality
• Authors: Eric Elmoznino, Thomas Jiralerspong, Yoshua Bengio, Guillaume Lajoie,
• Abstract summary: In AI, compositional representations can enable a powerful form of out-of-distribution generalization. Here, we propose a formal definition of compositionality that accounts for and extends our intuitions about compositionality. The definition is conceptually simple, quantitative, grounded in algorithmic information theory, and applicable to any representation.
• Score: 53.025566128892066
• License:
• Abstract: Compositionality is believed to be fundamental to intelligence. In humans, it underlies the structure of thought, language, and higher-level reasoning. In AI, compositional representations can enable a powerful form of out-of-distribution generalization, in which a model systematically adapts to novel combinations of known concepts. However, while we have strong intuitions about what compositionality is, there currently exists no formal definition for it that is measurable and mathematical. Here, we propose such a definition, which we call representational compositionality, that accounts for and extends our intuitions about compositionality. The definition is conceptually simple, quantitative, grounded in algorithmic information theory, and applicable to any representation. Intuitively, representational compositionality states that a compositional representation satisfies three properties. First, it must be expressive. Second, it must be possible to re-describe the representation as a function of discrete symbolic sequences with re-combinable parts, analogous to sentences in natural language. Third, the function that relates these symbolic sequences to the representation, analogous to semantics in natural language, must be simple. Through experiments on both synthetic and real world data, we validate our definition of compositionality and show how it unifies disparate intuitions from across the literature in both AI and cognitive science. We also show that representational compositionality, while theoretically intractable, can be readily estimated using standard deep learning tools. Our definition has the potential to inspire the design of novel, theoretically-driven models that better capture the mechanisms of compositional thought.

Related papers

• Geometric Signatures of Compositionality Across a Language Model's Lifetime [47.25475802128033]
  We show that compositionality is reflected in representations' intrinsic dimensionality. We also show that the relationship between compositionality and geometric complexity arises due to learned linguistic features over training.
  arXiv  Detail & Related papers  (2024-10-02T11:54:06Z)
• What makes Models Compositional? A Theoretical View: With Supplement [60.284698521569936]
  We propose a general neuro-symbolic definition of compositional functions and their compositional complexity. We show how various existing general and special purpose sequence processing models fit this definition and use it to analyze their compositional complexity.
  arXiv  Detail & Related papers  (2024-05-02T20:10:27Z)
• Semantic Composition in Visually Grounded Language Models [0.0]
  We show that visually-grounded language models drastically fail to represent compositional structure. We introduce WinogroundVQA, a new compositional visual question answering benchmark. We discuss connections of our work to neuroscience, psycholinguistics, formal semantics, and philosophy.
  arXiv  Detail & Related papers  (2023-05-15T03:19:42Z)
• On the Complexity of Bayesian Generalization [141.21610899086392]
  We consider concept generalization at a large scale in the diverse and natural visual spectrum. We study two modes when the problem space scales up, and the $complexity$ of concepts becomes diverse.
  arXiv  Detail & Related papers  (2022-11-20T17:21:37Z)
• The paradox of the compositionality of natural language: a neural machine translation case study [15.37696298313134]
  We re-instantiate three compositionality tests from the literature and reformulate them for neural machine translation (NMT) The results highlight two main issues: the inconsistent behaviour of NMT models and their inability to (correctly) modulate between local and global processing.
  arXiv  Detail & Related papers  (2021-08-12T17:57:23Z)
• Compositional Processing Emerges in Neural Networks Solving Math Problems [100.80518350845668]
  Recent progress in artificial neural networks has shown that when large models are trained on enough linguistic data, grammatical structure emerges in their representations. We extend this work to the domain of mathematical reasoning, where it is possible to formulate precise hypotheses about how meanings should be composed. Our work shows that neural networks are not only able to infer something about the structured relationships implicit in their training data, but can also deploy this knowledge to guide the composition of individual meanings into composite wholes.
  arXiv  Detail & Related papers  (2021-05-19T07:24:42Z)
• Modelling Compositionality and Structure Dependence in Natural Language [0.12183405753834563]
  Drawing on linguistics and set theory, a formalisation of these ideas is presented in the first half of this thesis. We see how cognitive systems that process language need to have certain functional constraints. Using the advances of word embedding techniques, a model of relational learning is simulated.
  arXiv  Detail & Related papers  (2020-11-22T17:28:50Z)
• Natural Language Rationales with Full-Stack Visual Reasoning: From Pixels to Semantic Frames to Commonsense Graphs [106.15931418425906]
  We present the first study focused on generating natural language rationales across several complex visual reasoning tasks. We present RationaleVT Transformer, an integrated model that learns to generate free-text rationales by combining pretrained language models with object recognition, grounded visual semantic frames, and visual commonsense graphs. Our experiments show that the base pretrained language model benefits from visual adaptation and that free-text rationalization is a promising research direction to complement model interpretability for complex visual-textual reasoning tasks.
  arXiv  Detail & Related papers  (2020-10-15T05:08:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.