Compositional Structures in Neural Embedding and Interaction Decompositions

Matthew Trager, Alessandro Achille, Pramuditha Perera, Luca Zancato, Stefano SoattoarXiv 2024 · OpenReview

Abstract

We describe a basic correspondence between linear algebraic structures within vector embeddings in artificial neural networks and conditional independence constraints on the probability distributions modeled by these networks. Our framework aims to shed light on the emergence of structural patterns in data representations, a phenomenon widely acknowledged but arguably still lacking a solid formal grounding. Specifically, we introduce a characterization of compositional structures in terms of "interaction decompositions," and we establish necessary and sufficient conditions for the presence of such structures within the representations of a model.

Introduction

For years, researchers have observed that neural networks organize information in surprisingly linear ways. The classic example is the word embedding analogy: the vector for "King" minus "Man" plus "Woman" roughly equals "Queen." This suggests that models learn a linear, compositional structure of the world. However, these observations have remained largely empirical—we see it happening, but we don't fully understand why or under what exact conditions it must happen. This paper provides a formal mathematical "dictionary" that links statistical independence in data to geometric patterns in neural network embeddings, proving that these linear structures are necessary consequences of how models represent conditional probability.

Methodology: Interaction Decompositions

The authors bridge the gap between statistics and geometry using interaction decompositions. This framework breaks down a complex vector into a sum of simpler parts: a "mean" component, "first-order" components (representing individual variables like "color" or "shape"), and "higher-order" interaction components (representing how variables combine).

Geometric representation of interaction decomposition where object and attribute vectors sum to form a combined embedding.

The paper’s core contribution, Theorem 3, establishes that if two sets of variables in the data are conditionally independent, then the corresponding interaction components in the model's embeddings must be orthogonal or zero. This provides an "if and only if" condition, meaning geometric patterns in embeddings directly reveal statistical dependencies in the training data.

Experimental Validation

The authors validated their framework using synthetic datasets and pre-trained models like ST5-XL. By analyzing object-attribute pairs (e.g., "big boat"), they demonstrated how embeddings decompose into additive parts. In their Transformer experiments, when they trained a model on data where variables were independent, the "interaction norm" dropped to near zero, exactly as Theorem 3 predicted.

Heatmap of interaction component norms for object-attribute pairs in ST5-XL.

As shown in the heatmap of interaction component norms, for independent pairs, the interaction terms are minimized. This confirms the theoretical prediction that statistical independence leads to geometric additivity and non-interfering components.

Key Insights and Discussion

  • The Analogy as a Special Case: The classic "parallelogram" structure of word analogies is shown to be a direct result of vanishing pairwise interaction terms. When a model treats "gender" and "royalty" as independent factors, the mathematics forces the vectors into a linear parallelogram.
  • Transformer Compositional Bias: Interestingly, the research found that Transformers often possess a "compositional bias" at initialization. Their architecture is predisposed to representing data as a sum of parts, which may explain their efficacy in language modeling.
  • Contextual Non-linearity: The framework also accounts for non-linear structures. If variables are only independent in specific contexts, the linear structure of the embeddings shifts or rotates accordingly.

Limitations and Future Work

While the current proof establishes a solid foundation for variables in finite sets, extending this to continuous spaces (such as raw audio) is a priority for future research. Additionally, while this work focuses on the final embedding layers, investigating how these structures emerge and evolve within the internal layers of deep networks remains an open question.

Summary updated

Abstract

We describe a basic correspondence between linear algebraic structures within vector embeddings in artificial neural networks and conditional independence constraints on the probability distributions modeled by these networks. Our framework aims to shed light on the emergence of structural patterns in data representations, a phenomenon widely acknowledged but arguably still lacking a solid formal grounding. Specifically, we introduce a characterization of compositional structures in terms of "interaction decompositions," and we establish necessary and sufficient conditions for the presence of such structures within the representations of a model.
BibTeX
@misc{trager2024compositional,
  author = {Matthew Trager and Alessandro Achille and Pramuditha Perera and Luca Zancato and Stefano Soatto},
  title = {{Compositional Structures in Neural Embedding and Interaction Decompositions}},
  year = {2024},
  eprint = {2407.08934},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.08934},
}
Figure