summaries: This paper tackles the problem of modeling monotonic and non-monotonic reasoning rules in different embeddings spaces, mostly vectors, but under different score functions used by the vector embeddings. The paper first provides the definition of monotonic reasoning, then iterates through a few vector-based embedding and label functions to check if they are able to model the monotonic reasoning part. Then the paper proposed a Relu based model that is able to model both monotonic and non-monotonic reasoning.

summaries: This paper looks at entity embeddings and theoretically tries to answer which kinds of semantic dependencies can be modeled by them. Mainly focusing on settings where the entity embeddings are obtained by pooling the embeddings of its attributes (although this is a strong assumption), this paper presents various theoretical limitations of the embedding approaches in learning logical/structured attribute representations with known logical or structured dependencies in practice. The paper shows that some of the most popular embedding models are not able to capture basic logical rules.

summaries: This paper provides a thorough analysis of the representational capacity of KB embedding models, analyzing the extent to which they can capture logical dependencies of a knowledge base. The authors consider a large range of common scoring functions, and both monotonic and non-monotonic dependencies. The authors make salient points as to the relevance of this sort of analysis - i.e. if a model is incapable of representing such dependencies then it cannot possible capture them from data - however there are a few limitations. For one, the authors are focusing on a setting where entity embeddings are pooled representations of attribute representations, which is not particularly standard (as acknowledged by the authors). Furthermore, there is a question of the extent to which the counterexamples as presented often manifest in real data, and how poorly a model which compromises to meet its objective would perform on various relevant queries. Both of these are reasonable limitations, however, in that they make the theoretical analysis possible and suggest conclusions that may reasonably apply to real-world data settings.

abstractText: 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.

authors:
Arindam Banerjee
Inderjit S. Dhillon
Joydeep Ghosh
Suvrit Sra

title: Clustering on the unit hypersphere using von mises-fisher distributions

venue: J. Mach. Learn. Res.,

authors:
Kayhan N. Batmanghelich
Ardavan Saeedi
Karthik Narasimhan
Samuel Gershman

title: Nonparametric spherical topic modeling with word embeddings

venue: In Proceedings ACL,

authors:
Rajarshi Das
Manzil Zaheer
Chris Dyer

title: Gaussian LDA for topic models with word embeddings

authors:
Jacob Devlin
Ming-Wei Chang
Kenton Lee
Kristina Toutanova

title: BERT: pre-training of deep bidirectional transformers for language understanding

venue: In Proceedings NAACLHLT,

authors:
Adji B Dieng
Francisco JR Ruiz
David M Blei

title: Topic modeling in embedding spaces

venue: Transactions of the Association for Computational Linguistics,

authors:
Andrea Frome
Greg S Corrado
Jonathon Shlens
Samy Bengio
Jeffrey Dean
Marc’Aurelio Ranzato
Tomas Mikolov

title: DeViSE: a deep visual-semantic embedding model

venue: In Proceedings NIPS,

authors:
Octavian Ganea
Gary Bécigneul
Thomas Hofmann

title: Hyperbolic entailment cones for learning hierarchical embeddings

venue: In Proceedings ICML,

authors:
Dinesh Garg
Shajith Ikbal
Santosh K Srivastava
Harit Vishwakarma
Hima P Karanam
L Venkata Subramaniam

title: Quantum embedding of knowledge for reasoning

venue: In Proceedings NeurIPS,

authors:
Vı́ctor Gutiérrez-Basulto
Steven Schockaert

title: From knowledge graph embedding to ontology embedding? an analysis of the compatibility between vector space representations and rules

venue: In Proceedings KR,

authors:
Takuo Hamaguchi
Hidekazu Oiwa
Masashi Shimbo
Yuji Matsumoto

title: Knowledge transfer for out-of-knowledge-base entities : A graph neural network approach

venue: In Proceedings IJCAI,

authors:
Junxian He
Zhiting Hu
Taylor Berg-Kirkpatrick
Ying Huang
Eric P Xing

title: Efficient correlated topic modeling with topic embedding

venue: In Proceedings KDD,

authors:
Mikhail Khodak
Nikunj Saunshi
Yingyu Liang
Tengyu Ma
Brandon M Stewart
Sanjeev Arora

title: A la carte embedding: Cheap but effective induction of semantic feature vectors

authors:
Ondrej Kuzelka
Jesse Davis
Steven Schockaert

title: Interpretable encoding of densities using possibilistic logic

venue: In Proceedings ECAI,

authors:
Christoph H Lampert
Hannes Nickisch
Stefan Harmeling

title: Attribute-based classification for zero-shot visual object categorization

venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,

authors:
Daniel Lehmann
Menachem Magidor

title: What does a conditional knowledge base entail

venue: Artificial intelligence,

authors:
Omer Levy
Yoav Goldberg

title: Dependency-based word embeddings

authors:
Shaohua Li
Tat-Seng Chua
Jun Zhu
Chunyan Miao

title: Generative topic embedding: a continuous representation of documents

authors:
Yu Meng
Jiaxin Huang
Guangyuan Wang
Chao Zhang
Honglei Zhuang
Lance M. Kaplan
Jiawei Han

title: Spherical text embedding

authors:
Tomas Mikolov
Kai Chen
Greg Corrado
Jeffrey Dean

title: Efficient estimation of word representations in vector space

venue: In Proceedings ICLR,

authors:
Maximilian Nickel
Douwe Kiela

title: Poincaré embeddings for learning hierarchical representations

authors:
Özgür Lütfü Özçep
Mena Leemhuis
Diedrich Wolter

title: Cone semantics for logics with negation

authors:
Jeffrey Pennington
Richard Socher
Christopher D. Manning

title: GloVe: Global vectors for word representation

venue: In Proceedings EMNLP,

authors:
Shikhar Vashishth
Manik Bhandari
Prateek Yadav
Piyush Rai
Chiranjib Bhattacharyya
Partha Talukdar

title: Incorporating syntactic and semantic information in word embeddings using graph convolutional networks

authors:
Ivan Vendrov
Ryan Kiros
Sanja Fidler
Raquel Urtasun

title: Order-embeddings of images and language

authors:
Luke Vilnis
Xiang Li
Shikhar Murty
Andrew McCallum

title: Probabilistic embedding of knowledge graphs with box lattice measures

authors:
Guangxu Xun
Yaliang Li
Wayne Xin Zhao
Jing Gao
Aidong Zhang

title: A correlated topic model using word embeddings

heading: 1. Introduction

text:
Vector space embeddings are currently the dominant representation framework in Natural Language Processing, Computer Vision and Machine Learning. Essentially, these embeddings represent each entity of interest as a dense vector in some fixed-dimensional space. In addition, the attributes that are used to describe these entities are typically also encoded as vectors. For example, in the case of word embeddings, the entities correspond to words and the attributes correspond to the contexts in which these words occur, e.g. in the form of co-occurring words [Mikolov et al., 2013, Pennington et al., 2014], syntactic dependencies [Levy and Goldberg, 2014, Vashishth et al., 2019] or even full sentences [Devlin et al., 2019]. In inductive knowledge graph embedding, the entities from our framework correspond to the previously unseen entities for which we want to learn a representation, with the attributes representing links to known entities [Hamaguchi et al., 2017]. In the case of embeddingbased topic models, the entities correspond to documents and the attributes correspond to the associated topics and words [Das et al., 2015, Li et al., 2016, He et al., 2017, Xun et al., 2017, Dieng et al., 2020]. In zero-shot learning, the entities of interest are the category prototypes and the attributes correspond to semantic attributes of the categories [Lampert et al., 2013] or associated natural language terms [Frome et al., 2013].
An important advantage of attribute embeddings is that they can implicitly capture some of the dependencies that hold between the attributes. For instance, the use of embeddings for topic modelling stems from the desire to capture topic correlations [He et al., 2017, Xun et al., 2017]. However, it is currently unclear what kinds of dependencies can be
captured in this way. Before we can address this question, we first need to clarify what it means that an embedding captures some dependency. To this end, consider an embedding model in which σ(a·e) represents the probability that entity e has attribute a, where σ is the sigmoid function and a and e are the embeddings of a and e. Among many others, the popular skip-gram word embedding model is of this kind [Mikolov et al., 2013]. Now consider the attributes parent, female and mother, and the associated dependency that mother ≡ parent∧female. What condition would need to be satisfied for the embedding to capture this dependency? One possibility is to require that σ(mother ·e) = σ(parent ·e) ·σ(female ·e) for each vector e in the embedding space Rn. However, this condition can clearly not be satisfied; e.g. for e = 0 we obtain the condition 0.5 = 0.25. Similarly, it is easy to see that the condition σ(mother · e) = min(σ(parent · e), σ(female · e)) only admits trivial solutions. Viewed from this angle, it is clear that popular embedding models are not able to capture even basic logical dependencies. For this reason, several alternative models have been proposed, in which attributes are modelled as linear subspaces [Garg et al., 2019], axis-aligned cones [Vendrov et al., 2016, Özçep et al., 2020], hyperboxes [Vilnis et al., 2018] or polytopes [Gutiérrez-Basulto and Schockaert, 2018], among others.
In this paper, we follow a different direction, analysing whether embedding models can capture logical dependencies in a less demanding sense. In particular, we consider the common setting where the embedding of an entity e has to be learned from its known attributes, and the aim of the resulting embedding is to infer what other attributes e is likely to satisfy. We then say that the rule a1 ∧ ... ∧ an → b is captured if an entity which is known to have the attributes a1, ..., an would be represented by a vector from which the attribute b would be predicted. Note that different variants of this setting can be considered, which depend on (i) how exactly entity vectors are constructed and (ii) how the resulting vectors are used for predicting the attributes of the entity. The aim of this paper is to analyse, for different variants, whether it is always possible to find an embedding which captures the rule a1 ∧ ... ∧ an → b iff that rule is entailed by some propositional knowledge base K. Note that in practice we typically do not have access to such a knowledge base K. However, the question of whether arbitrary propositional knowledge bases can, in principle, be modelled by a given embedding strategy is important, because if this is not the case, then it also means that some (combinations of) dependencies cannot be learned.
In addition to standard propositional entailment, we also look at non-monotonic consequence relations, which is important because attribute dependencies are often defeasible or probabilistic in nature. For instance, in a topic modelling context, we may assume that a document containing the word safari is related to the topic nature, and a document containing the word apple is related to the topic food. However, documents containing both of these words are more likely to be related to technology instead, given that Safari is the name of Apple’s internet browser. We may thus want that the rule safari→ topic:nature is captured, while the rule safari ∧ apple→ topic:nature is not.

heading: 2. Problem Setting

text:
We assume that each entity is associated with some attributes from a given set A. In the context of word embeddings, for instance, the set A could be the set of all contexts. Note that we do not consider knowledge graphs, where entities are described in terms of their
relationship to other entities, rather than attributes. However, many inductive knowledge graph embedding models can still be cast as special cases of our framework, with the attributes then representing links to entities with known (or pre-computed) embeddings.
Embedding and Labelling Functions If an entity e is associated with the attributes a1, ..., an, we assume that its embedding is given by e = Emb(a1, ..., an) for some embedding function Emb : 2A → Rm. The embedding functions that we consider in this paper will rely on pooling attribute vectors. In particular, we consider embedding functions of the following form: Emb(a1, ..., an) = φ(a1, ...,an) for some pooling function φ, where a ∈ Rm represents the embedding of attribute a ∈ A. For instance, we may have Emb(a1, ..., an) = 1 n(a1 + ... + an). Let us furthermore assume that we have a function Lab : R
m → 2A that predicts attributes of entities based on their embeddings. Similar as for Emb, we will assume that the labelling function Lab relies on a scoring function that compares the embedding of e with an embedding of the considered attribute. In particular, we consider labelling functions of the following form: Lab(e) = {b ∈ A |ψ(e, b̃) ≥ λb}. The embedding b̃ of the attribute b may in general be different from the attribute embedding b that is used for Emb, similar to how word embedding models learn two types of embeddings for each word. The scalar λb represents a threshold, which we allow to be attribute-dependent for generality. For instance, we could have Lab(e) = {b ∈ A |σ(e · b) ≥ 0.5} = {b ∈ A | e · b ≥ 0}. In the following, we will refer to (φ, ψ) as an embedding strategy and to (Emb,Lab) as an embedding. Note that the embedding (Emb,Lab) is determined by the embedding strategy (φ, ψ), together with the embeddings a and ã of the attributes in A.
Consequence Relations The function Lab ◦ Emb can be viewed as a logical consequence relation. In particular, we say that an embedding (Emb,Lab) captures the rule a1 ∧ ... ∧ an → b iff b ∈ Lab(Emb(a1, ..., an)), i.e. if an entity that is initially associated with the attributes a1, ..., an would be predicted to have attribute b based on its embedding. Note that under this view, the dependency mother ≡ parent∧ female can be satisfied for the aforementioned choices of Emb and Lab, for instance by choosing parent = (−1, 1), female = (1, 1) and mother = (0, 1). However, now the issue is that a number of unwanted dependencies are also satisfied, such as female→ mother and parent→ mother. Therefore, rather than treating rules in isolation, the question we are interested in is the following: given a propositional knowledge base K and a given embedding strategy (φ, ψ), does there exist a corresponding embedding (Emb,Lab) (or, equivalently, do there exist attribute embeddings) such that for all b ∈ A and {a1, ..., an} ⊆ A we have that b ∈ Lab(Emb(a1, ..., an)) iff K |= a1 ∧ ... ∧ an → b holds, where |= is the standard entailment relation from propositional logic. If this is the case, we say that the embedding strategy (φ, ψ) can simulate K. In Section 4, we will similarly look at whether non-monotonic consequence relations can be simulated with embeddings. Throughout this paper, we will assume that the number of dimensions m can be chosen arbitrarily large, as our focus is on identifying limitations that exist regardless of dimensionality. An overview of our results is shown in Table 1.

heading: 3. Monotonic Reasoning

text:
In Sections 3.1–3.3, we first discuss embedding strategies which are not capable of capturing certain kinds of propositional knowledge bases. Crucially, these strategies cover many of
the most popular embedding models. Section 3.4 then discusses embedding strategies which are capable of modelling arbitrary propositional knowledge bases.

heading: 3.1 Averaging Based Embeddings

text:
One of the most natural choices for the embedding function Emb consists in averaging the attribute embeddings, i.e.:
Embavg(a1, ..., an) = 1
n (a1 + ...+ an) (1)
This choice corresponds, among many others, to the common strategy of learning sentence or document vectors by averaging word vectors. It is also closely related to the CBOW model from Mikolov et al. [2013]. As the labelling function, we first consider the common choice to model the probability that entity e has attribute a as σ(e · a). However, since each condition of the form σ(e · a) ≥ δ, with 0 < δ < 1, is equivalent to the condition e · a ≥ σ−1(δ), we use a simple dot product in the formulation:
Labdot(e) = {b ∈ A | e · b̃ ≥ λb} (2)
where λb ∈ R is a threshold that may in general be attribute-specific. We will use φavg and ψdot to denote the pooling functions associated with Embavg and Labdot. For the ease of presentation, throughout the paper, we will similarly use subscripts to link embedding and labelling functions to their corresponding pooling functions, rather than each time introducing these notations explicitly. Note that the embedding strategy (φavg, ψdot) also covers models where a linear transformation is applied to the average of the attribute embeddings, as is the case for the à la carte method from Khodak et al. [2018].
As the following counterexample shows, not all propositional knowledge bases can be simulated with embeddings of the form (Embavg,Labdot).
Counterexample 1. Let K = {a ∧ b → x, c ∧ d → x}. We show that K cannot be simulated by (φavg, ψdot). Indeed, if a suitable embedding existed, among others the following inequalities would have to be satisfied:
a + b
2 · x̃ ≥ λx
c + d
2 · x̃ ≥ λx
a + c
2 · x̃ < λx
b + d
2 · x̃ < λx
This is not possible, since the first two inequalities imply (a + b + c + d) · x̃ ≥ 4λ whereas the last two imply (a + b + c + d) · x̃ < 4λ.
Another natural choice for the labelling function is to rely on Euclidean distance:
Labdist(e) = {b ∈ A | d(e, b̃) ≤ θb} (3)
where θb ≥ 0. It is easy to verify that the knowledge base from Counterexample 1 can be simulated by choosing a = (−1, 0), b = (1, 0), c = (0,−1), d = (0, 1) and x̃ = (0, 0). However, as the following counterexample shows, not all knowledge bases can be simulated using Embavg and Labdist either.
Counterexample 2. Let K = {a ∧ b → x, c ∧ d → x, a ∧ c → y, b ∧ d → y}. We show that K cannot be simulated by (φavg, ψdist). Indeed, suppose that a suitable embedding (Embavg,Labdist) existed. From the rules with x in the head, it follows that d 2 ( a+b 2 , x̃ ) +
d2 ( c+d 2 , x̃ ) < d2 ( a+c 2 , x̃ ) + d2 ( b+d 2 , x̃ ) . This is equivalent with:
‖a‖2 + ‖b‖2 + ‖c‖2 + ‖d‖2 + 8‖x‖2 + 2(a · b + c · d)− 4(a + b + c + d) · x̃ < ‖a‖2 + ‖c‖2 + ‖b‖2 + ‖d‖2 + 8‖x‖2 + 2(a · c + b · d)− 4(a + b + c + d) · x̃
which simplifies to a · b + c · d < a · c + b · d. In the same way, using the rules with y in the head, we find a · b + c · d > a · c + b · d, which is a contradiction.
To illustrate the relevance of these results, let the attributes a1, ..., an correspond to the words that are observed in a document d, and suppose that other attributes, which are not observed, correspond to document categories. We may want the embedding model to capture rules such as tennis ∧ player ∧ won→ cat:sports, meaning that if the words tennis, player and won appear in a document, then it should belong to the category sports. Our results show that, in general, such dependencies cannot be captured when Embavg is used in combination with Labdot or Labdist. For instance, this means that there are theoretical limitations to the kinds of categories that may be predicted from document embeddings when using the à la carte method from [Khodak et al., 2018] together with a linear classifier.

heading: 3.2 Embeddings as Normalised Averages

text:
Let us now consider the following embedding function, which represents entities using normalised vectors:
Embnorm(a1, ..., an) = a1 + ...+ an ‖a1 + ...+ an‖
(4)
provided ‖a1 + ... + an‖ > 0, and Embnorm(a1, ..., an) = 0 otherwise. Entity vectors can then be understood as maximum likelihood estimates, if we view attributes as von MisesFisher distributions, which is a common choice when modelling text [Banerjee et al., 2005,
Batmanghelich et al., 2016, Meng et al., 2019]. In particular, if p(e|a) is a von Mises-Fisher distribution with mean a‖a‖ and concentration parameter ‖a‖, for each a ∈ A, then we have:
Embnorm(a1, ..., an) = arg max e n∏ i=1 p(e|ai) s.t. ‖e‖ = 1
= arg max e n∑ i=1 e · ai s.t. ‖e‖ = 1
The question of whether propositional knowledge bases can be simulated with Embnorm is thus relevant for understanding the limitations of von Mises-Fisher based topic models and document representations [Meng et al., 2019, Batmanghelich et al., 2016]. The following counterexample shows that not all knowledge bases can be simulated with Embnorm. While the use of normalised averages is intuitively similar to the averages from Section 3.1, the counterexample in this case is more involved.
Counterexample 3. Let K = {a∧b→ x, c∧d→ x, a∧c→ y, b∧d→ y, a∧d→ y, b∧c→ y}. We show that K cannot be simulated by (φnorm, ψdot). Indeed, suppose that a suitable embedding (Embnorm,Labdot) existed. Then we must have λx > 0 and λy > 0, which follows immediately from the fact that Embnorm(∅) = 0 while K 6|= > → x and K 6|= > → y. For the ease of presentation, let us introduce the following abbreviations: yab = a+b ‖a+b‖ and similar for yac,yad,ybc,ybd,ycd. Consider the hyperplane H defined by H = {e | e·(λxỹ−λyx̃) = 0}. If e belongs to the positive half-space H+ = {e | e · (λxỹ − λyx̃) ≥ 0}, we have:
e · ỹ ≥ λy λx e · x̃
This implies that either e · x̃ < λx or e · ỹ ≥ λy. We thus find in particular that yab and ycd do not belong to this positive half-space H
+. In the same way, we find that yac, ybd, yad and ybc do not belong to the negative half-space H
− = {e | e · (λxỹ − λyx̃) ≤ 0}. Note that when e1, e2 ∈ H+, we also have e1 + e2 ∈ H+ and e1+e2‖e1+e2‖ ∈ H +, and similar for H−. Since yab,ycd ∈ H−, at least one of a,b must thus belong to H− and at least one of c,d must belong to H−. Assume for instance that a ∈ H− and c ∈ H−; the other cases follow by symmetry. From a ∈ H− and c ∈ H−, we find that yac ∈ H−, which is a contradiction.
While we used Labdot in the above counterexample, the result also holds for Labdist. Indeed, since ‖e‖ = 1, we have d(e, b̃) ≤ θb iff d2(e, b̃) ≤ θ2b iff e · b̃ ≥ 1 2(1 + ‖b̃‖
2 − θ2b ). We thus have that K can be simulated by (φnorm, ψdot) iff it can be simulated by (φnorm, ψdist).

heading: 3.3 Sigmoid Based Embeddings

text:
We now turn to the common choice of modelling attribute probabilities using the sigmoid function, i.e. let us assume that σ(e ·a) represents the probability that entity e has attribute a. A natural choice for inferring the embedding of e is then to maximise the likelihood of the observed attributes a1, ..., an:
Embsig(a1, ..., an) = arg max e n∑ i=1 log σ(e · ai) + κ‖e‖2 (5)
where κ > 0 is a constant. This embedding strategy closely corresponds to the skip-gram model [Mikolov et al., 2013], with two differences. First, the standard skip-gram model does not include the regularisation term κ‖e‖2. Here, we need to add this term, which amounts to imposing a Gaussian prior, to ensure that Embsig is well-defined
1. Second, the skip-gram model also includes negative samples. However, since 1 − σ(e · a) = σ(−e · a), negative samples can be considered as a special case where some of the attributes ai capture the fact that another attribute bi is not present, by constraining the embedding such that ai = −bi. The limitations of the embedding function Embsig thus still apply to settings where negative samples are used. The following counterexample shows that arbitrary propositional knowledge bases cannot be modelled with Embsig and Labdot.
Counterexample 4. The main idea is to follow the same strategy as in Counterexample 3, which is possible thanks to the fact that Embsig(a, b) is a conical combination of Embsig(a) and Embsig(b), provided cos(a,b) > −1. Some care is needed to ensure that the latter condition is satisfied for various pairs of attributes.
Let K = {a ∧ b→ x, c ∧ d→ x, a ∧ c→ y, b ∧ d→ y, a ∧ d→ y, b ∧ c→ y, a→ zab, b→ zab, a→ zac, c→ zac, a→ zad, d→ zad, b→ zbc, c→ zbc, b→ zbd, d→ zbd, c→ zcd, d→ zcd}. We show that K cannot be simulated by (φsig, ψdot). Suppose that a suitable embedding (Embsig,Labdot) existed. Note that ya = αaa and yb = αbb for some αa, αb > 0. Since we have λzab > 0 (which follows in the same way as λx > 0), it must be the case that cos(ya, z̃ab) > 0 and cos(yb, z̃ab) > 0, which means cos(a, z̃ab) > 0 and cos(b, z̃ab) > 0, which implies cos(a,b) > −1. This, in turn, implies that yab is a conical combination of ya and yb. We similarly have that yac, yad, ybc, ybd and ycd are conical combinations of the corresponding attribute vectors. Consider again the hyperplane H defined by H = {e | e · (λxỹ − λyx̃) = 0} from Counterexample 3, and the positive and negative half-spaces H+ and H−. When e1, e2 ∈ H+, we also have µ1e1 + µ2e2 ∈ H+ for µ1, µ2 ≥ 0, i.e. if e1 and e2 are in H
+ then the same is true for any conical combination of e1 and e2, and similar for H−. We thus obtain a contradiction in the same way as in Counterexample 3.
In the appendix, we provide a similar counterexample for the strategy (φsig, ψdist). Note that Counterexample 4 only relies on the fact that Embsig(a1, ..., an) is a conical combination of a1, ...,an. The same counterexample can thus be used for other embeddings strategies that rely on a weighted average of attribute vectors with non-negative weights.

heading: 3.4 Modelling Monotonic Dependencies with Embeddings

text:
Thus far, we have found that standard embedding strategies are not capable of simulating even basic sets of Horn rules. It turns out, however, that this limitation can be solved by adding a non-linearity to the labelling function:
Labrelu(e) = {b ∈ A |ReLU(e) · b ≥ 0} (6)
where the ReLU function is applied component-wise. Note that in the definition of Labrelu we fixed the threshold at 0 and we fixed a = ã for all a ∈ A, to highlight the fact that this restricted definition is already sufficient for modelling propositional dependencies.
1. In particular, this ensures that the maximum is attained for a vector with finite coordinates. This vector may not be unique, however, in which case we assume that an arbitrary maximising vector e is chosen.
Proposition 1. For any propositional knowledge base K over A, there exist embeddings of the attributes in A such that b ∈ Labrelu(Embavg(a1, ..., an)) iff K |= a1 ∧ ... ∧ an → b.
Proof. Let mod(K) = {ω1, ..., ωl} be the set of models of K. We define the embedding a = (xa1, ..., x a l+1) of the attribute a as follows:
xai =  1 if i ≤ l and ωi |= a −δ if i ≤ l and ωi 6|= a 1 if i = l + 1
where δ is a constant which is chosen such that δ > 2|A|. Let e = (y1, ..., yl+1) = Embavg(a1, ..., an). Let ni be the number of atoms from {a1, ..., an} that are satisfied in ωi. Then we have yl+1 = 1 and for i ≤ l we have
yi = 1
n (ni − (n− ni)δ)
In particular, we have yi = 1 if ωi |= {a1, ..., an} and yi < 0 otherwise (since δ > |A| ≥ ni). We thus have:
ReLU(yi) = { 1 if ωi |= {a1, ..., an} 0 otherwise
For b ∈ A, we find
ReLU(e) · b =1 + |{ω |ω |= K ∪ {a1, ..., an, b}| − δ|{ω |ω |= K ∪ {a1, ..., an,¬b}|
In particular, we have ReLU(e) · b ≥ 0 iff |{ω |ω |= K ∪ {a1, ..., an,¬b}| = 0, which is equivalent to K |= a1 ∧ ... ∧ an → b.
Note that the proof can be straightforwardly adapted to other types of non-linearities. For instance, with sigmoid instead of ReLU, by choosing δ sufficiently large, we can ensure that σ(yi) is arbitrarily close to 0 when ωi 6|= {a1, ..., an}, and rely on the same argument.
Next we consider the following embedding function:
Embhad(a1, ..., an) = a1 ... an (7)
where we write for the Hadamard product (i.e. the component-wise product of vectors). In the appendix, we show the following result, using a construction that is very similar to the one from the proof of Proposition 1.
Proposition 2. For any propositional knowledge base K over A, there exist embeddings of the attributes in A such that b ∈ Labdot(Embhad(a1, ..., an)) iff K |= a1 ∧ ... ∧ an → b.
Note that in contrast to the setting from Proposition 1, here we allow a 6= ã. It is easy to see that this additional freedom is necessary, since otherwise any embedding modelling a rule of the form a → b would also model the reversed rule b → a. Finally, we consider the embedding strategy that is used in the order embeddings from Vendrov et al. [2016]:
Embord(a1, ..., an) = max(a1, ...,an) Labord(e) = {b ∈ A |b e}
where we write max for the component-wise maximum of the vectors and is the product order, i.e. (x1, ..., xn) (y1, ..., yn) iff xi ≤ yi for all i ∈ {1, ..., n}. This embedding model was proposed to improve how hierarchical relations can be encoded. However, as the next result shows, it also allows us to simulate other kinds of propositional dependencies.
Proposition 3. For any propositional knowledge base K over A, there exist embeddings of the attributes in A such that b ∈ Labord(Embord(a1, ..., an)) iff K |= a1 ∧ ... ∧ an → b.
Proof. Let mod(K) = {ω1, ..., ωl} be the set of models of K. If K is inconsistent, we can simply choose a = 0 for every a ∈ A, with 0 a vector of zeroes of an arbitrary dimension. Now suppose |mod(K)| > 0. We define the embedding a = (xa1, ..., xal ) of the attribute a as follows:
xai = { 0 if ωi |= a 1 otherwise
Let e = (y1, ..., yl) = Embord(a1, ..., an). Then we have yi = 0 if ωi |= {a1, ..., an} and yi = 1 otherwise. We thus have b e iff ∀i.(xbi = 1)⇒ (yi = 1) iff ∀i.(ωi 6|= b)⇒ (ω 6|= {a1, ..., an}) iff K |= a1 ∧ ... ∧ an → b.
Order embeddings essentially represent each attribute as an axis-aligned cone (where the vector components are viewed as lower bounds). Other region based embedding models can be used to model monotonic dependencies in a similar way, including e.g. box embeddings [Vilnis et al., 2018] and hyperbolic entailment cones [Ganea et al., 2018].

heading: 4. Non-Monotonic Reasoning

text:
We now consider a standard ranking-based semantics of default rules [Lehmann and Magidor, 1992]. Let Θ be a stratified knowledge base, i.e. a ranked list of formulas (α1, ..., αk). Then we say that Θ |= α B β iff there is some i ∈ {0, ..., k} such that α1 ∧ ... ∧ αi ∧ α |= β and α1 ∧ ... ∧ αi ∧ α 6|= ¬β. The formula α B β intuitively means that “if α holds then typically also β holds”. This semantics of default rules can equivalently be characterised in terms of the maximum a posteriori (MAP) consequences of a probabilistic model, i.e. α B β is inferred iff β is true in the most probable models of α [Kuzelka et al., 2016].
Example 1. Consider the following stratified knowledge base:
Θ = (¬cat:technology ∨ ¬cat:food, apple ∧ safari→ cat:technology, apple→ cat:food)
It can be verified that Θ |= apple B cat:food and Θ |= apple ∧ safari B cat:technology, while Θ 6|= apple ∧ safari B cat:food.
We now analyse whether an embedding can be found such that b ∈ Lab(Emb(a1, ..., an)) iff Θ |= a1 ∧ ... ∧ an B b. Clearly, embedding strategies which cannot be used to simulate monotonic reasoning cannot be used to simulate this form of non-monotonic reasoning either. This is because we can choose Θ1 = (α1), where α1 is the conjunction of all formulas in a propositional knowledge base K. However, we find that the strategy (φavg, ψrelu) can be used to model non-monotonic attribute dependencies.
Proposition 4. For any stratified knowledge base Θ over A, there exist embeddings of the attributes in A such that b ∈ Labrelu(Embavg(a1, ..., an)) iff Θ |= a1 ∧ ... ∧ an B b.
Proof. Let Θ = (α1, ..., αm) and let ω1, ..., ωl be an enumeration of all interpretations over A. To define the embeddings a = (xa1, ..., xal ), we use the mapping µ defined by µ(ω) = max{i |ω |= α1 ∧ ... ∧ αi}, where we assume µ(ω) = 0 if ω 6|= α1. We define:
xai = { δ2µ(ωi) if ωi |= a −δ(1+2µ(ωi)) otherwise
where δ is chosen such that δ > 2|A|. Let e = (y1, ..., yl) = Embavg(a1, ..., an). Similar as in the proof of Proposition 1 we then find yi < 0 iff ωi 6|= {a1, ..., an}, i.e.:
ReLU(yi) = { δ2µ(ωi) if ωi |= {a1, ..., an} 0 otherwise
For b ∈ A, we find that ReLU(Embavg(a1, ..., an)) · b is given by∑ ωi|={a1,...,an,b} δ4µ(ωi) − ∑ ωi|={a1,...,an,¬b} δ(1+4µ(ωi))
We thus have ReLU(Embavg(a1, ..., an)) · b ≥ 0 iff∑ ωi|={a1,...,an,b} δ4µ(ωi) ≥ ∑ ωi|={a1,...,an,¬b} δ(1+4µ(ωi)) (8)
Let m+ = max{µ(ωi)|ωi |= {a1, ..., an, b}} and m− = max{µ(ωi)|ωi |= {a1, ..., ab,¬b}}, where we define m− = −1 if {a1, ..., an,¬b} is inconsistent (i.e. if b = ¬ai for some i). Then we have that Θ |= a1 ∧ ... ∧ an B b is equivalent to m+ > m−. If m+ > m−, we find∑
ωi|={a1,...,an,b}
δ4µ(ωi) ≥ δ4m+ = δ3 · δ1+4(m+−1) > δ · δ1+4(m+−1) > 2|At| · δ1+4(m+−1)
≥ 2|At| · δ1+4(m−) ≥ ∑
ωi|={a1,...,an,¬b}
δ(1+4µ(ωi))
Conversely, if m+ ≤ m− we find∑ ωi|={a1,...,an,b} δ4µ(ωi) ≤ ∑ ωi|={a1,...,an,b} δ4m + ≤ 2|At| · δ4m+ < δ · δ4m+ = δ1+4m+ ≤ δ1+4m−
≤ ∑
ωi|={a1,...,an,¬b}
δ(1+4µ(ωi))
where the last step relies on the fact that m+ ≤ m− implies m− ≥ 0 and thus there must be some ωi such that ωi |= {a1, ..., an, b}. We thus have that Θ |= a1 ∧ ...∧ an B b is equivalent to m+ > m−, which is equivalent to (9) and ReLU(Embavg(a1, ..., an)) · b ≥ 0.
In the appendix we show the following result, using a similar construction.
Proposition 5. For any stratified knowledge base Θ over A, there exist embeddings of the attributes in A such that b ∈ Labdot(Embhad(a1, ..., an)) iff Θ |= a1 ∧ ... ∧ an B b.
Finally, we show that the combination Embord and Labord cannot be used to model nonmonotonic dependencies. A similar limitation arises for all approaches which learn embeddings by taking the intersection of region-based attribute representations.
Counterexample 5. Let Θ = (a ∧ b → ⊥, a → x). To simulate Θ with an embedding of the form (Embord,Labord), we need x a and x 6 max(a,b). However, this is impossible since a max(a,b).

heading: 5. Concluding Remarks

text: It remains poorly understood how we can design embedding models to encourage different kinds of dependencies to be captured (with the problem of embedding hierarchies being a notable exception [Vendrov et al., 2016, Nickel and Kiela, 2017, Ganea et al., 2018]). The analysis presented in this paper provides a step towards such an understanding. The ability of the ReLU-based labelling function to model monotonic and non-monotonic attribute dependencies seems of particular interest, given how close it stays to standard embedding models. While we have focused on propositional dependencies, our results also have implications for knowledge graph embedding. For instance, bilinear models can be viewed as instances of the sigmoid based embedding strategy, where attributes represent links to other entities. The attribute vectors then depend on the embeddings of other entities, which are iteratively updated. This makes it possible to capture certain types of relational dependencies. Developing a better understanding of which types of relational dependencies can be modelled in this way is an important avenue for future work. However, the results presented in this paper already show that such models are not able to capture arbitrary dependencies.

heading: Appendix B. Proof of Proposition 2

text:
Let mod(K) = {ω1, ..., ωl} be the set of models of K. We define the embeddings a = (xa1, ..., x a l+1) and ã = (x̃ a 1, ..., x̃ a l+1) of the atom a as follows:
xai =  1 if i ≤ l and ωi |= a 0 if i ≤ l and ωi 6|= a 1 if i = l + 1
x̃ai =  1 if i ≤ l and ωi |= a −δ if i ≤ l and ωi 6|= a 1 if i = l + 1
where δ is a constant satisfying δ > 2|A|. Let us write Embhad(a1, ..., an) = y = (y1, ..., yl+1). Then we clearly have:
yi = { 1 if ωi |= {a1, ..., an} 0 otherwise
For b ∈ A, we find
y · b̃ = 1 + |{ω |ω |= K ∪ {a1, ..., an, b}| − δ|{ω |ω |= K ∪ {a1, ..., an,¬b}|
Note that we have y · b̃ ≥ 0 iff |{ω |ω |= K∪{a1, ..., an,¬b}| = 0, since we assumed δ > 2|A|. We have |{ω |ω |= K ∪ {a1, ..., an,¬b}| = 0 iff K ∪ {a1, ..., an} |= b iff K |= a1 ∧ ...∧ an → b. In particular, we have:
(Embhad(a1, ..., an) · b̃ ≥ 0) ⇔ (K |= a1 ∧ ... ∧ an → b)

heading: Appendix C. Proof of Proposition 5

text:
Let Ω = (α1, .., αm) and let ω1, ..., ωl be an enumeration of all interpretations over A. We define the embedding a = (xa1, ..., x a l ) as follows:
xai = { 1 if ωi |= a 0 otherwise
To define the embedding ã = (x̃a1, ..., x̃ a l ), we use the mapping µ defined by µ(ω) = max{i |ω |= α1 ∧ ... ∧ αi}, where we assume µ(ω) = 0 if ω 6|= α1:
x̃ai = { δ2µ(ωi) if ωi |= a −δ(1+2µ(ωi)) otherwise
where δ is a constant which is chosen such that δ > 2|A|. Let us write Embhad(a1, ..., an) = y = (y1, ..., yl). Note that we have:
yi = { 1 if ωi |= {a1, ..., an} 0 otherwise
For b ∈ A, we find
y · b̃ = ∑
ωi|={a1,...,an,b}
δ2µ(ωi) − ∑
ωi|={a1,...,an,¬b}
δ(1+2µ(ωi))
We thus have y · b̃ ≥ 0, i.e. b ∈ Labdot(y), iff∑ ωi|={a1,...,an,b} δ2µ(ωi) ≥ ∑ ωi|={a1,...,an¬b} δ(1+2µ(ωi)) (9)
Let m+ = max{µ(ωi)|ωi |= {a1, ..., an, b}} and m− = max{µ(ωi)|ωi |= {a1, ..., an,¬b}}, where we define m− = −1 if {a1, ..., an,¬b} is inconsistent (i.e. if b = ¬ai for some i). Then we have Θ |= a1 ∧ ... ∧ an B b iff m+ > m−. If m+ > m−, we find∑
ωi|={a1,...,an,b}
δ2µ(ωi) ≥ δ2m+ = δ · δ1+2(m+−1) > 2|A| · δ1+2(m+−1) ≥ 2|A| · δ1+2(m−)
≥ ∑
ωi|={a1,...,an,¬b}
δ(1+2µ(ωi))
Now, conversely, suppose m+ ≤ m−. Then we have∑ ωi|={a1,...,an,b} δ2µ(ωi) ≤ ∑ ωi|={a1,...,an,b} δ2m + ≤ 2|A| · δ2m+ < δ · δ2m+ = δ1+2m+ ≤ δ1+2m−
≤ ∑
ωi|={a1,...,an,¬b}
δ(1+2µ(ωi))
where the last step relies on the fact thatm+ ≤ m− impliesm− ≥ 0, and hence {a1, ..., an,¬b} must be consistent. We thus have that m+ > m− is equivalent to ∑ ωi|={a1,...,an,b} δ
2µ(ωi) ≥∑ ωi|={a1,...,an¬b} δ (1+2µ(ωi)), which is equivalent to b ∈ Labdot(Embhad(a1, ..., an)).

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