Modelling Monotonic and Non-Monotonic Attribute Dependencies with Embeddings: A Theoretical Analysis

Steven Schockaert

TL;DR

This paper theoretically analyzes the limitations of common embedding strategies in capturing attribute dependencies. It reveals that many popular methods struggle with even basic logical rules, but demonstrates that certain non-linear embedding and labeling functions can indeed model both monotonic and non-monotonic dependencies.

What Problem Does This Paper Address?

Entity embeddings are a cornerstone of modern AI, representing entities and their attributes as dense vectors. A key promise of attribute embeddings is their ability to implicitly capture semantic relationships between attributes. However, there's a significant gap in our understanding of which types of dependencies these embedding models can actually represent. This paper aims to bridge this gap by theoretically investigating the expressive power of various embedding strategies, particularly those where an entity's embedding is derived by pooling its attribute embeddings. The authors focus on understanding the fundamental limitations of these models, rather than their practical performance on specific tasks.

Methods

The core of the paper involves defining a formal framework for analyzing how embedding strategies (combinations of embedding and labeling functions) can "simulate" logical rules.

  • Embedding Functions (Emb): These functions take a set of attribute embeddings and produce an entity embedding. The paper considers various pooling strategies, including:
  • Averaging: `Embavg(a1, ..., an) = (a1 + ...
  • an) / n`
    • Normalized Averaging: `Embnorm(a1, ..., an) = (a1 + ...
  • an) / ||a1 + ...
  • an||`
    • Sigmoid-based: Embsig(a1, ..., an) = argmax_e log(e·ai) + κ||e||^2 (similar to skip-gram)
    • Hadamard Product: Embhad(a1, ..., an) = a1 ⊙ ... ⊙ an
    • Order Embeddings: Embord(a1, ..., an) = max(a1, ..., an) (component-wise maximum)
  • Labeling Functions (Lab): These functions predict attributes of an entity based on its embedding. Common choices include:
  • Dot Product: Labdot(e) = {b | e · b ≥ θ}
    • Euclidean Distance: Labdist(e) = {b | d(e, b) ≤ θ}
    • ReLU-based: Labrelu(e) = {b | RELU(e) · b ≥ 0} (a key non-linearity)

The authors then analyze whether a given embedding strategy (Emb, Lab) can simulate a propositional knowledge base K (for monotonic reasoning) or a stratified knowledge base Θ (for non-monotonic reasoning). This means checking if the predicted attributes Lab(Emb(a1, ..., an)) perfectly correspond to the logical entailment K |= a1 ^ ... ^ an → b or default entailment Θ |= a1 ^ ... ^ an ▷ b.

Datasets

Not discussed in the paper. The analysis is theoretical and does not involve empirical evaluation on specific datasets.

Key Insights and Ideas

  • Many Popular Models Fall Short: The paper demonstrates through counterexamples that common embedding strategies like averaging attributes with dot-product or distance-based labeling (Embavg, Labdot/Labdist) are surprisingly limited. They cannot capture even simple Horn rules (e.g., a → x, c → x cannot be simulated if a and c are distinct).
  • The Power of Non-Linearity: The introduction of a non-linear activation function, specifically the ReLU-based labeling function (Labrelu), is a crucial breakthrough. This allows the Embavg strategy to simulate any propositional knowledge base. This is a significant finding, as it shows that a relatively simple modification can drastically increase expressive power.
  • Monotonic vs. Non-Monotonic: The paper distinguishes between monotonic (where adding attributes can only add to entailments) and non-monotonic (where adding attributes can invalidate previous entailments, like in default reasoning) dependencies. While many standard methods fail at monotonic reasoning, the Labrelu approach is shown to be capable of handling both monotonic and non-monotonic reasoning.
  • Hadamard Product and Order Embeddings: The paper also explores other strategies. Embhad (Hadamard product) combined with Labdot can simulate monotonic rules, and Embord (order embeddings) with Labord can also simulate monotonic rules, but Embord and Labord fail for non-monotonic reasoning.
  • Theoretical Limitations are Fundamental: The analysis highlights that the limitations are not due to specific data or hyperparameters but are inherent to the mathematical structure of certain embedding strategies.

Key Results

  • Negative Results:
    • (Embavg, Labdot) and (Embavg, Labdist) cannot simulate arbitrary propositional knowledge bases.
  • (Embnorm, Labdot) cannot simulate arbitrary propositional knowledge bases.
  • (Embsig, Labdot) cannot simulate arbitrary propositional knowledge bases.
  • (Embord, Labord) cannot simulate non-monotonic dependencies.
  • Positive Results:
    • The strategy (Embavg, Labrelu) can simulate any propositional knowledge base (monotonic reasoning).
  • The strategy (Embavg, Labrelu) can simulate any stratified knowledge base (non-monotonic reasoning).
  • The strategy (Embhad, Labdot) can simulate monotonic rules.
  • The strategy (Embord, Labord) can simulate monotonic rules.

Limitations and Future Work

  • Focus on Theoretical Power: The paper focuses on whether a strategy can model dependencies in principle, not on how efficiently or effectively it does so in practice. Real-world performance might differ.
  • Specific Pooling/Labeling Functions: The analysis is limited to the specific embedding and labeling functions considered. Other variations might have different expressive powers.
  • Future Work:
    • Knowledge Graph Embeddings: The authors suggest that their findings have implications for knowledge graph embedding, particularly for models that iteratively update embeddings. Understanding how relational dependencies can be modeled is an important avenue.
  • Other Non-Linearities: The success of ReLU suggests exploring other non-linear activation functions for labeling.
  • Practical Implementations: Investigating how these theoretically capable strategies perform in practice and developing efficient implementations would be valuable.

Summary updated

Abstract

During the last decade, entity embeddings have become ubiquitous in Artificial Intelligence. Such embeddings essentially serve as compact but semantically meaningful representations of the entities of interest. In most approaches, vectors are used for representing the entities themselves, as well as for representing their associated attributes. An important advantage of using attribute embeddings is that (some of the) semantic dependencies between the attributes can thus be captured. However, little is known about what kinds of semantic dependencies can be modelled in this way. The aim of this paper is to shed light on this question, focusing on settings where the embedding of an entity is obtained by pooling the embeddings of its known attributes. Our particular focus is on studying the theoretical limitations of different embedding strategies, rather than their ability to effectively learn attribute dependencies in practice. We first show a number of negative results, revealing that some of the most popular embedding models are not able to capture even basic Horn rules. However, we also find that some embedding strategies are capable, in principle, of modelling both monotonic and non-monotonic attribute dependencies.
BibTeX
@inproceedings{schockaert2021modelling,
  author = {Steven Schockaert},
  title = {{Modelling Monotonic and Non-Monotonic Attribute Dependencies with Embeddings: A Theoretical Analysis}},
  booktitle = {AKBC},
  year = {2021},
  url = {https://openreview.net/forum?id=U2adryQpew5},
}
Figure