summaries: This paper studies how the FiLM visual question answering (VQA) model answer questions involving the quantifier ‘most’. This quantifier is chosen for study because it cannot be expressed in first order logic (i.e., high-order logic is required), and secondly because there are two different algorithmic approaches to answering questions involving ‘most’ (cardinality-based strategy and pairing-based strategy). Experiments are performed by designing abstract visual scenes with controlled numerosity and spatial layouts, and applying methodologies from pyscholinguistics. The paper concludes that the model learns an approximate number system (ANS), consistent with the cardinality-based strategy, with implications for understanding the conditions under which existing VQA models should perform well or badly (and possibly for improving VQA models).

summaries: The paper analyzes the strategy that a visual question answering model (FiLM) uses to verify statements containing the quantifier "most" ("most of the dots are red"). It finds that the model is sensitive to the ratio of objects that satisfy the predicate (that are red) to objects that do not; as the ratio decreases (e.g. 10 red dots compared to 9 blue dots), the model's performance decreases too. This is consistent with human behavior.

abstractText: The correct interpretation of quantifier statements in the context of a visual scene requires non-trivial inference mechanisms. For the example of “most”, we discuss two strategies which rely on fundamentally different cognitive concepts. Our aim is to identify what strategy deep learning models for visual question answering learn when trained on such questions. To this end, we carefully design data to replicate experiments from psycholinguistics where the same question was investigated for humans. Focusing on the FiLM visual question answering model, our experiments indicate that a form of approximate number system emerges whose performance declines with more difficult scenes as predicted by Weber’s law. Moreover, we identify confounding factors, like spatial arrangement of the scene, which impede the effectiveness of this system.

authors:
Aishwarya Agrawal
Dhruv Batra
Devi Parikh

title: Analyzing the behavior of visual question answering models

venue: In Proceedings of the Conference on Empirical Methods in Natural Language Processing,

authors:
Stanislaw Antol
Aishwarya Agrawal
Jiasen Lu
Margaret Mitchell
Dhruv Batra
C. Lawrence Zitnick
Devi Parikh

title: VQA: Visual question answering

authors:
Prithvijit Chattopadhyay
Ramakrishna Vedantam
Ramprasaath R. Selvaraju
Dhruv Batra
Devi Parikh

title: Counting everyday objects in everyday scenes

venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,

authors:
Felix A. Gers
Jürgen Schmidhuber

title: LSTM recurrent networks learn simple context-free and context-sensitive languages

venue: Transactions on Neural Networks,

authors:
Yash Goyal
Tejas Khot
Douglas Summers-Stay
Dhruv Batra
Devi Parikh

title: Making the V in VQA matter: Elevating the role of image understanding in Visual Question Answering

title: On the grammar and processing of proportional quantifiers: most versus more than half

venue: Natural Language Semantics,

authors:
Drew A. Hudson
Christopher D. Manning

title: Compositional attention networks for machine reasoning

venue: In Proceedings of the International Conference on Learning Representations,

authors:
Justin Johnson
Bharath Hariharan
Laurens van der Maaten
Li Fei-Fei
C. Lawrence Zitnick
Ross Girshick

title: CLEVR: A diagnostic dataset for compositional language and elementary visual reasoning

authors:
Justin Johnson
Bharath Hariharan
Laurens van der Maaten
Judy Hoffman
Li Fei-Fei
C Lawrence Zitnick
Ross Girshick

title: Inferring and executing programs for visual reasoning

venue: In Proceedings of the IEEE International Conference on Computer Vision, ICCV 2017,

authors:
Alexander Kuhnle
Ann Copestake

title: ShapeWorld - A new test methodology for multimodal language understanding

venue: ArXiv e-prints

authors:
Jeffrey Lidz
Paul Pietroski
Justin Halberda
Tim Hunter

title: Interface transparency and the psychosemantics of most

authors:
Ethan Perez
Florian Strub
Harm de Vries
Vincent Dumoulin
Aaron C. Courville

title: FiLM: Visual reasoning with a general conditioning layer

venue: In AAAI,

authors:
Sandro Pezzelle
Ionut-Teodor Sorodoc
Raffaella Bernardi

title: Comparatives, quantifiers, proportions: A multi-task model for the learning of quantities from vision

venue: In Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics,

authors:
Paul Pietroski
Jeffrey Lidz
Tim Hunter
Justin Halberda

title: The meaning of ’most’: Semantics, numerosity and psychology

venue: Mind and Language,

authors:
Samuel Ritter
David G.T. Barrett
Adam Santoro
Matt M. Botvinick

title: Cognitive psychology for deep neural networks: A shape bias case study

venue: In Proceedings of the 34th International Conference on Machine Learning,

authors:
Adam Santoro
David Raposo
David G.T. Barrett
Mateusz Malinowski
Razvan Pascanu
Peter Battaglia
Timothy P. Lillicrap

title: A simple neural network module for relational reasoning

venue: In Proceedings of the Annual Conference on Neural Information Processing Systems,

authors:
Ionut Sorodoc
Angeliki Lazaridou
Gemma Boleda
Aurélie Herbelot
Sandro Pezzelle
Raffaella Bernardi

title: Look, some green circles!”: Learning to quantify from images

venue: In Proceedings of the 5th Workshop on Vision and Language, Berlin,

authors:
Ionut Sorodoc
Sandro Pezzelle
Aurélie Herbelot
Mariella Dimiccoli
Raffaella Bernardi

title: Learning quantification from images: A structured neural architecture

venue: Natural Language Engineering,

authors:
Ivilin Stoianov
Marco Zorzi

title: Emergence of a ‘visual number sense’ in hierarchical generative models

venue: Nature Neuroscience,

authors:
Alane Suhr
Mike Lewis
James Yeh
Yoav Artzi

title: A corpus of natural language for visual reasoning

venue: In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics,

authors:
Xiaolin Wu
Xi Zhang
Xiao Shu

title: On numerosity of deep convolutional neural networks

authors:
Guangyu Robert Yang
Igor Ganichev
Xiao-Jing Wang
Jonathon Shlens
David Sussillo

title: A dataset and architecture for visual reasoning with a working memory

authors:
Jianming Zhang
Shuga Ma
Mehrnoosh Sameki
Stan Sclaroff
Margrit Betke
Zhe Lin
Xiaohui Shen
Brian Price
Radomı́r Měch

title: Salient object subitizing

authors:
Yan Zhang
Jonathon Hare
Adam Prügel-Bennett

title: Learning to count objects in natural images for visual question answering

heading: 1 INTRODUCTION

text:
Deep learning methods have been very successful in many natural language processing tasks, ranging from syntactic parsing to machine translation to image captioning. However, despite significantly raised performance scores on benchmark datasets, researchers increasingly worry about interpretability and indeed quality of model decisions. We see two distinct research endeavors here, one being more pragmatic, forward-oriented, and guided by the question “Can a system solve this task?”, the other being more analytic, reflective, and motivated by the question “How does a system solve this task?”. In other words, the former aspires to improve performance, while the latter aims to increase our understanding of deep learning models.
By ‘understanding’ here we mean observing a reasoning mechanism that, if not resembling human behavior, at least is cognitively plausible. This is by no means necessary for practically solving a task, however, we highlight two reasons why being able to explain model behavior is nonetheless important: On the one hand, cognitive plausibility increases confidence in the abilities of a system – one is generally more willing to rely on a reasonable than an incomprehensible mechanism. On the other hand, pointing out systematic shortcomings inspires systematic improvements and hence can guide progress. Moreover, particularly in the case of a human-centered domain like natural language, ultimately, some degree of comparability to human performance is indispensable.
In this paper we are inspired by experimental practice in psycholinguistics to shed light on the question of how deep learning models for visual question answering (VQA) learn to interpret statements involving the quantifier “most”. We follow Pietroski et al. (2009) in designing abstract visual scenes where we control the ratio of the objects quantified over and their spatial arrangement, to identify whether VQA models exhibit a preferred strategy of verifying whether “most” applies. Figure 1 illustrates how visual scenes can be configured to favor one over another mechanism.
We want to emphasize the experimental approach and its difference to mainstream machine learning practice. For different interpretation strategies, conditions are identified that should or should not affect their performance, and test instances are designed accordingly. By comparing the accuracy of subjects on various instance types, predictions about a subject’s performance for these mechanisms can be verified and the most likely explanation identified. Note that our advocated evaluation methodology is entirely extrinsic and does not constrain the system in any way (like requiring attention maps) or require a specific framework (like being probabilistic).
Psychology as a discipline has focused entirely on questions around how humans process situations and arrive at decisions, and consequently has the potential to inspire a lot of experiments (like ours) for investigating the same questions in the context of machine learning. Similar to psychology, we advocate the preference of an artificial experimentation environment which can be controlled in detail, over the importance of data originating from the real world, to arrive at more convincing and thus meaningful results.
Artificial data has a history in deep learning of establishing new techniques – most prominently, LSTMs were introduced by showing their ability to handle various formal grammars (Gers & Schmidhuber, 2001) – and our higher-level goal with this paper is to demonstrate the potential for more informative evaluation of machine learning models in general. This is motivated by our belief that, in the long term, true progress can only be made if we do not just rely on the narrative of neural networks “learning to understand/solve” a task, but can actually confirm our theories experimentally. Taking inspiration from psychology seems particularly appropriate in the context of powerful deep learning models, which recently are not infrequently described by anthropomorphizing words like “understanding”, and compared to “human-level” performance.

heading: 2 THE MEANING OF “MOST”

text: In this section we will introduce the two mechanisms of interpreting “most”, discuss cognitive differences and implications, and introduce relevant cognitive concepts.

heading: 2.1 GENERALIZED QUANTIFIERS AND “MOST”

text:
“Most” has a special status in linguistics due to the fact that it is the most prominent example of a quantifier whose semantics cannot be expressed in first-order logic, while other simple natural language quantifiers like “some”, “every” or “no” directly correspond to the quantifier primitives ∃ and ∀ (plus logical operators ∧, ∨ and ¬). This situation is not just a matter of introducing further appropriate primitives, but requires a fundamental extension of the logic system and its expressivity.
In the following, by x we denote an entity, A and B denote predicates (“square”, “red”), A(x) is true if and only if x satisfies A, and SA = {x : A(x)} is the corresponding set of entities satisfying this predicate (“squares”). Thus we can define the semantics of “some” and “every”:
some/every(A,B)⇔ ∃/∀x : A(x)⇒ B(x) (1) Importantly, these definitions do not involve the concept of set cardinality and indeed can be formulated without involving sets. This is not possible for “most”, which is commonly defined in one of the following ways:
most(A,B)⇔ |SA∧B| > 1/2 · |A| ⇔ |SA∧B| > |SA∧¬B| (2)
This makes “most” an example of a generalized quantifier, and in fact all generalized quantifiers can be defined in terms of cardinalities, indicating the apparent importance of a cardinality concept to human cognition.

heading: 2.2 ALTERNATIVE CHARACTERIZATION

text:
There is another way to define “most” which uses the fact that whether two sets are equinumerous can be determined without a concept of cardinality, based on the idea of a bijection:
A↔ B :⇔ ∀x : [A(x)⇔ B(x)] (3) ⇔ |SA| = |SB| (4)
The definition of equinumerosity can be generalized to “more than” (and, correspondingly, “less than”), which lets us define “most” as follows:
most(A,B)⇔ ∃S ( SA∧B : S↔ SA∧¬B (5) Although, at a first glance, this definition looks similar to the one above, it can be seen as suggesting a different algorithmic approach to interpreting “most”, as we will discuss below.

heading: 2.3 TWO INTERPRETATION STRATEGIES

text:
The two characterizations of “most” are of course truth-conditionally equivalent, that is, every situation in which one of them holds, the other holds, and vice versa. In particular, if we are just interested in solving a task involving “most” statements, we can be agnostic about which definition our system prefers. Nevertheless, the subtle differences between these two characterizations suggest different algorithmic mechanisms of verifying or falsifying such statements, meaning that a system processes a visual scene differently to come to the (same) conclusion about a statement’s truth.
Characterization (2) represents the cardinality-based strategy of interpreting “most”:
1. Estimate the number of entities satisfying both predicates (“red squares”) and the number satisfying one predicate but not the other (“non-red squares”).
2. Compare these number estimates and check whether the former is greater than the latter.
We want to add that, actually, the two definitions in (2) already suggest a minor variation of this mechanism – see Hackl (2009) for a discussion on “most” versus “more than half”. However, we do not focus on this detail here, and assume the second variant in (2) to be ‘strictly’ simpler in the sense that both involve estimating and comparing cardinalities, but the first variant additionally involves the rather complex operation of halving one number estimate.
Characterization (5) utilizes the concept of a bijection, which is a comparatively simple pairing mechanism and as such could be imagined to be a primitive cognitive operation. This gives us the pairing-based strategy of interpreting “most”:
1. Successively match entities satisfying both predicates (“red squares”) uniquely with entities satisfying one predicate but not the other (“non-red squares”).
2. The remaining entities are all of one type, so pick one and check whether it is of the first type (“red square”).

heading: 2.4 COGNITIVE IMPLICATIONS

text:
Finding evidence for one strategy over the other has substantial implications with respect to the ‘cognitive abilities’ of a neural network model. In particular, evidence for a cardinality-based processing of “most” suggests the existence of an approximate number system (ANS), which is able to simultaneously estimate the number of objects in two sets, and perform higher-level operations on the resulting number representations themselves, like the comparison operation here. Explicit counting would be an even more accurate mechanism here, but neither available to the subjects in the experiments of Pietroski et al. (2009) due to very short scene display time, nor likely to be learned by the ‘one-glance’ feed-forward-style neural network we evaluate in this work1.
1By “one-glance feed-forward-style networks” we refer to the predominant type of network architecture which, by design, consists of a fixed sequence of computation steps before arriving at a decision. In particular, such models do not have the ability to interact with their input dynamically depending on the complexity of an instance, or perform more general recursive computations beyond the fixed recurrent modules built into their design. Important for the discussion here is the fact that precise – in contrast to approximate or subitizing-style – counting is by definition a recursive ability, thus impossible to learn for such models.
The ANS (see appendix in Lidz et al. (2011) for a summary) is an evolutionary comparatively old mechanism which is shared between many different species throughout the animal world. It emerges without explicit training and produces approximate representations of the number of objects of some type. They are approximate in the sense that their number judgment is not ‘sharp’, but resulting behavior exhibits variance – like interpreting “most” statements with a cardinality-based strategy, as described above. This variance follows Weber’s law which states that the discriminability of two quantities is a function of their ratio2. The precision of the ANS is thus usually indicated by a characteristic value called Weber fraction which relates quantity and variance. The ANS of a typical adult human is often reported to have a Weber fraction of 1.14 or, more tangibly, it can distinguish a ratio of 7:8 with 75% accuracy. Finding evidence for the emergence of a similar system in deep neural networks indicates that these models can indeed learn and utilize more abstract concepts (approximate numbers) than mere superficial pattern matching (“red squares” etc).
Both mechanisms to interpret “most” suggest conditions in which they should perform well or badly. For the cardinality-based one, the difference in numbers of the two sets in question is expected to be essential: smaller differences, or greater numbers for the same absolute difference, require more accurate number estimations and hence make this comparison harder, according to Weber’s law. The pairing-based mechanism, on the other hand, is likely affected by the spatial arrangement of the objects in question: if the objects are more clustered within one set, pairing them with objects from the other set becomes harder. Importantly, these conditions are orthogonal, so each mechanism should not substantially be affected by the other condition, respectively. By constructing (artificial) scenes where one of the conditions dominates the configuration, and measuring the accuracy of being able to correctly interpret propositions involving “most”, the expected difficulties can be confirmed (or refuted) and thus indicate which mechanism is actually at work.
Using this methodology, Pietroski et al. (2009) show that humans exhibit a default strategy of interpreting “most”, at least when only given 200ms to look at the scene and hence having to rely on an immediate subconscious judgment. This strategy is based on the approximate number system and the cardinality-based mechanism. Moreover, the behavior is shown to be sub-optimal in some situations where humans would, in principle, be able to perform better if deviating from their default strategy. Since machine learning models are trained by optimizing parameters for the task at hand, it is far from obvious whether they learn a similarly stable default mechanism, or instead follow a potentially superior adaptive strategy depending on the situation. While the latter is likely more efficient in solving at least a narrowly defined task, the former would instead suggest that the system is able to acquire and utilize core concepts like an approximate number system.
We may speculate about the innate preference of modern network architectures for either of the strategies: Most of the visual processing is based on convolutions which, being an inherently local computation, we assume would favor the pairing-based strategy via locally matching and ‘cancelling out’ entities of the two predicates. On the other hand, the tensors resulting from the sequence of convolution operations are globally fused into a final embedding vector, which in turn would support the more globally aggregating cardinality-based strategy. However, the type of computations and representations learned by deep neural networks are poorly understood, making such speculations fallacious. We thus emphasize again that the higher-level motivation for this paper is to demonstrate how we need not rely on such speculative ‘narratives’, but can experimentally substantiate our claims.

heading: 3 EXPERIMENTAL SETUP

text:
The setup in this paper closely resembles the psychological experiments conducted by Pietroski et al. (2009), but aimed at a state-of-the-art VQA model and its interpretation of “most”.
2We want to emphasize that there is evidence for Weber’s Law in a range of other approximate systems, some of them non-discrete and thus rendering a pairing-based strategy impossible. While this does not rule out such a strategy when observing performance decline as predicted by Weber’s Law (which is probably not possible based on extrinsic evaluation alone), it strongly suggests that similar and thus non-pairing-based mechanisms are at work in all of these situations.

heading: 3.1 TRAINING AND EVALUATION DATA

text:
We use the ShapeWorld framework (Kuhnle & Copestake, 2017) as starting point to generate appropriate data. ShapeWorld is a configurable generation system for abstract, visually grounded language data. A data point consists of an image, an accompanying caption, and an agreement value indicating whether the caption is true given the image. The underlying task, image caption agreement, essentially corresponds to yes/no questions and as such is a type of visual question answering. Internally, the system samples an abstract world description from which a semantic caption representation is extracted. Both are then turned into ‘natural’ (but still abstract) representations as image and natural language statement, respectively. The latter transformation is based on a semantic grammar formalism (see their paper for details).
We use the pre-implemented quantifier captioner component, both in its unrestricted version and one with available quantifiers restricted to “more than half” and “less than half”3. The former contains various additional (generalized) quantifiers (“no”, “a/three quarter(s)”, “a/two third(s)”, “all”) and numbers (ranging from “zero” to “five”), each in combination with a comparing modifier (“less than”, “at most”, “exactly”, “at least”, “more than”, “not”). We refer to the unrestricted version as Q-full, the other one as Q-half. Figure 2 shows two images together with potential Q-full captions.
We also use the default world generator to produce training data (up to 15 randomly positioned objects, as seen in figure 2). However, all of the pre-implemented generator modules are too generic for our evaluation purposes, since they do not allow to control attributes and positioning of objects to the desired degree. We thus implemented our own custom generator module with the following functionality to produce test data.
Attribute contrast: For each instance, either the attribute ‘shape’ or ‘color’ is picked4, and subsequently two values for this attribute and one value for the other is randomly chosen. This means that the only relevant difference between objects in every image is either one of two shape or color values (for instance, red vs blue squares, or red squares vs circles).
Contrast ratios: A list of valid ratios between the contrasted attributes can be specified, from which one will randomly be chosen per instance. For instance, a ratio of 2:3 means that there are 50% more objects with the second than the first attribute. We look at values close to 1:1, that is, 1:2, 2:3, 3:4, 4:5, etc. The increasing difficulty (for humans) resulting from closer ratios is illustrated in figure 3. Multiples of the smaller-valued ratios are also generated (e.g., 2:4 or 6:9), within the limit of up to 15 objects overall.
Area-controlled: If this option is set, object sizes are not chosen uniformly across the entire valid range, but size ranges for the two contrasting object types are adapted to the given contrast ratio and size of the chosen shape(s), so that both attributes cover the same image area on average. This means that the more numerous attribute will generally be represented by smaller objects, and the difference in covered area between, for instance, squares and triangles is taken into account.
3We use these two instead of “most” since ShapeWorld generates them by default. The VQA model is trained from scratch on this data, so we do not expect any of the differences between “most” and “more than half” one observes with humans to matter (Hackl, 2009).
4Note that we chose the examples in figures to always vary in color only.
While objects are still positioned randomly in the basic version of this new generator module, we define two modes which control this aspect as well. Figure 1 in the introduction illustrates the different modes.
Partitioned positioning: An angle is randomly chosen for each image, and objects of the contrasting attributes are consistently placed either on one side or the other.
Paired positioning: If there are objects of the contrasted attribute which are not yet paired, one of them is randomly chosen and the new object is placed next to it.
The captions of these evaluation instances are always of the form “More/less than half the shapes are X”. with “X” being the attribute in question, for instance, “squares” or “red”. Note that this is an even more constrained captioner than the one used for Q-half, since the subject is always fully underspecified as “shape”. We also emphasize that, in contrast to this new evaluation generator module, the default generator configuration of the ‘quantification’ dataset pre-specified in ShapeWorld is used to generate the training instances in Q-half and Q-full. So these images generally contain many more than just two contrasted attributes, and ratios between attributes tend to be accordingly smaller. The examples in figure 2 are chosen to illustrate this fact: the second example contains a “half” statement with ratio 7:8, and the first contains one about a 0:4 ratio, while the image would also allow for a more ‘interesting’ 3:4 ratio (color of semicircles).
While we generally try to stay close to the experimental setup of Pietroski et al. (2009), in the following we point out some differences. Most importantly, instead of just using yellow and blue dots, we use all eight shapes and seven colors that ShapeWorld provides. This increases the visual variety of the instances and thus encourages the system to actually learn the fact that shape and color are attributes that can be combined in any way, instead of just straightforward binary pattern matching. Note that the humans in the psychological experiments have learned language in even more complex situations, which we cannot hope to approximate here. Moreover, our data does not contain yes/no questions but true/false captions, and “most”-equivalent phrasings “more/less than half”. Since the model is trained from scratch on such data, this should not affect results.
We do not implement their ‘column pairs mixed/sorted’ modes since they would require comparatively big and mostly empty images, hence require bigger networks and might cause practical learning problems due to sparseness, which we do not want to address here. In contrast, our ‘partitioned’ mode is more difficult than the ones investigated by Pietroski et al. (2009), at least for a pairing-based mechanism.
We will publish the generator configurations and custom generator modules required to reproduce the datasets we used here on acceptance of the paper.

heading: 3.2 MODEL

text:
We focus on the FiLM model (Perez et al., 2018) here since it exhibited close-to-perfect accuracy on the CLEVR dataset (Johnson et al., 2017a), a diagnostic dataset for VQA which also consists of abstract images. We interpret the ShapeWorld captions and agreement values as questions and answer, respectively. The image is processed using either a pre-trained CNN or a four-layer CNN trained from scratch on the task. The question is processed by a GRU. In a sequence of four residual blocks, the image information is processed with its features linearly modulated (scale, offset) conditioned on the processed question embedding. Finally, the classifier module produces the answer, true or false. We use the code made available by the authors of the FiLM model, without changing any parameters. The only aspect we adapt is the trainable four-layer CNN, which uses a kernel size of 3, batch normalization and a stride of 2 in the second and fourth layer.
We considered investigating other models as well: The PG+EE model (Johnson et al., 2017b) is openly available and achieved very good performance on CLEVR, however, it relies on the ‘program tree’ provided by CLEVR, and while there exists a basic conversion of ShapeWorld caption models to CLEVR program trees, first, the CLEVR-specific modules do not cover quantifiers like “most” and, second, these program trees encode the interpretation strategy, which would defeat the purpose of our investigation to analyze precisely this mechanism as learned from data. The RelationNet architecture (Santoro et al., 2017) explicitly implements a pairing-based mechanism and hence we considered its evaluation less interesting than FiLM. For similar reasons, we did not focus on the VQA model of Zhang et al. (2018), whose architecture includes an explicit counting component. While our aim is to investigate the strategy for understanding “most” learned from data, it would be interesting to examine in both cases whether their architectural prior does indeed have the expected effect. Finally, we only learned about the MAC model (Hudson & Manning, 2018) after we started this project and so decided to leave it for future work, but we definitely consider it one of the most interesting candidate models to evaluate, since its architecture does not suggest an obvious preference for either strategy.

heading: 3.3 TRAINING DETAILS

text: The training set for both Q-full and Q-half consists of around 100k (25x 4096) images with 5 captions per image, so overall around 500k instances. The model is trained for 100k iterations with a batch size of 64. Training performance is measured on an additional validation set of 20k instances. Moreover, we produced 1024 instances for each of the overall 48 evaluation configurations, to investigate the trained model in more detail.

heading: 4 RESULTS

text:
Training. We train two versions of the FiLM model, with CNN trained from scratch on the task: one on the Q-full dataset which contains all available quantifier and number caption types, the other on the Q-half dataset which is restricted to captions involving the quantifier “half” only. Performance of the system over the course of the 100k training iterations is shown in figure 4. The two models, referred to by Q-full and Q-half below, learn to solve the task quasi-perfectly, with a final accuracy of 98.9% and 99.4% respectively. Not surprisingly, the system trained on the more diverse Q-full training set takes longer to reach this level of performance, but nevertheless plateaus after around 70k iterations.
For the sake of completeness, we also include the performance of other models in this figure, which failed to show clear improvement over the first 50k iterations. This includes the FiLM model with pre-trained instead of trainable CNN module (Q-full-pre, Q-half-pre), and an earlier trial on Q-half (Q-half-coll) where we did not constrain the data generation to not produce object collisions (the default in ShapeWorld is to allow up to 25% area overlap). We note, however, that we have not done any hyperparameter search which might alleviate these learning problems.
Evaluation. Table 5 presents a detailed breakdown of system performance on the evaluation settings. Before discussing the results in detail, we want to reiterate three key differences between the evaluation data and the training data:
• The visual scenes here do all exhibit close-to-balanced contrast ratios, while this is not the case for the training instances.
• The evaluation scenes only contain objects of two different attribute pairs, and consequently the numbers to compare are generally greater than in the training instances, where more attributes are likely present in a scene.
• Q-full contains not just statements involving “half” – in fact, a random sample of 100 images / 500 captions suggests that they constitute only around 8% of the dataset (and this includes combinations with modifiers beyond “more/less than”).
Considering that, the relatively high accuracy on test instances throughout indicates a remarkable degree of generalization.
More balanced ratios. The most consistent effect is that more balanced ratios of contrasted attributes cause performance to decrease. This is certainly affected by the tendency of the training data to not include many examples of almost balanced ratios. However, if this were the only reason, one would expect a much more sudden and less uniformly linear decrease. More importantly, since Q-full generally contains fewer “half” statements, the decline should be more pronounced here. We do not observe either of these effects, and thus conclude that both models may actually have developed an approximate number system. This is further discussed at the end of this section.
Random vs paired vs partitioned. There is definitely a clear negative effect of the partitioned configuration on performance for the model trained on Q-full, which indicates that the learned mechanism is not robust to a high degree of per-attribute clustering. This does not indicate a preference for the pairing-based strategy, though, since both models perform best on the random configuration. While this suggests that there is neither a preference for the perfectly clustered partitioned nor for the perfectly mixed paired arrangement, we note that the effect is not strong, and that these instances are most similar to the random placement of objects in the training data, which might cause this effect.
Size- vs area-controlled. The performance in both cases is comparable, showing that the models do not (solely) learn to rely on comparing the overall covered area, which would only work well in the size-controlled mode. Nevertheless, we note a tendency for area-controlled instances to be somewhat more difficult in random and paired mode, more so for Q-half, which suggests that the model(s) learn to use covered area as a feature to inform a correct decision in some cases.
Q-full vs Q-half. There seems to be a tendency of the system trained on Q-full to perform marginally better, except for the partitioned mode discussed before. The fact that this model performs at least on a par with the one trained on Q-half, while only seeing a fraction of directly relevant training captions, indicates that the learning process is not ‘distracted’ by the variety of captions, and indeed might profit from it.
Ratios and Weber fraction. We generated evaluation sets of even more balanced ratios (8:9, 9:10, 10:11, increasing the overall number of objects accordingly to 17/19/21), and in figure 6 plotted the accuracy of the Q-full model on increasingly balanced sets for all three spatial configuration modes,
not controlling for area (which for greater numbers only has a negligible effect anyway). The figure also contains a diagram with accuracy plotted against ratio fraction, which is more common in the context of Weber’s law. The characteristic Weber fraction can be read off directly as the ratio at which a subject is able to distinguish two values with 75% accuracy. We observe around 1.11 for random/paired and 1.16 for partitioned, which corresponds to 9:10 and 6:7 as closest integer ratios. These values are in the same region as the average human Weber fraction, which is often reported as being 1.14, or 7:8.
We emphasize that these curves align well with the trend predicted by Weber’s law, even for the ratios with more than 15 objects overall, where such situations have never been encountered during training. All this strongly suggests that the model learns a mechanism similar to an ANS, which is able to produce representations that can (at least) be utilized for identifying the more numerous set. It can in particular be concluded that the system does not actually learn to explicitly count, since we would then not expect to observe such fuzziness characteristic to an ANS.
Moreover, since performance is affected somewhat by the partitioned and the area-controlled modes, the interpretation of “most” seems to be informed by other features as well. As we noted earlier, since the model is trained to optimize this task, an adaptive strategy is not unexpected. On the contrary, more surprising is the fact that an ANS-like system emerges as a dominating ‘backbone’ mechanism, with additional factors acting as less influential ‘secondary’ features.

heading: 5 RELATED WORK

text:
Visual question answering (VQA) is the general task of answering questions about visual scenes. Since the introduction of the VQA Dataset (Antol et al., 2015), this dataset was widely used as evaluation benchmark for multimodal deep learning. It provides a shallow categorization of questions, including basic count questions, however, these categories are far too coarse for our purposes.
Motivated by various problems with the VQA Dataset (Goyal et al., 2017; Agrawal et al., 2016), a range of artificial abstract datasets have been introduced recently. CLEVR (Johnson et al., 2017a) consists of rendered images of geometric objects and questions generated based on templates, covering some abilities like number or attribute comparison in more detail, but still in a fixed categorization. NLVR (Suhr et al., 2017) contains crowdsourced statements about abstract images, but does not sort them according to some criteria. Recently, the COG dataset (Yang et al., 2018) was introduced, which most explicitly focuses on replicating psychological experiments for deep learning models, hence most related to our work. However, their dataset does not contain any number or quantifier statements.
There is some work on investigating deep neural networks which look at numerosity from a more psychologically inspired viewpoint. Stoianov & Zorzi (2012) find that visual numerosity emerges from unsupervised learning on abstract image data. Zhang et al. (2015) look at salient object subitizing in real-world images, formulated as a classification task over five classes ranging from ‘0’
to ‘4 or more’. In a more general number-per-category classification setup, Chattopadhyay et al. (2017) investigate different methods of obtaining counts per object category, one of them inspired by subitizing. Moving beyond explicit number classification, Zhang et al. (2018) recently introduced a dedicated counting module for visual question answering.
Other work looks at a similar classification task, but for proper quantifiers like “no”, “few”, “most”, “all”, first on abstract images of circles (Sorodoc et al., 2016), then on natural scenes (Sorodoc et al., 2018). Recently, Pezzelle et al. (2018) investigated a hierarchy of quantifier-related classification abilities, from comparatives via quantifiers like the ones above to fine-grained proportions. Wu et al. (2018), besides investigating precise numerosity via number classification as above, also look at approximate numerosity as binary greater/smaller decision, which closely corresponds to our experiments. However, their focus is on the subitizing ability, not the approximate number system, and their experiments follow a different methodology in that they already train models on specifically designed datasets, while we deliberately leverage such targeted data only for evaluation.
On a methodological level, our proposal of inspiring experimental setup and evaluation practice for deep learning by cognitive psychology is in line with that of Ritter et al. (2017) and their shape bias investigation for modern vision architectures.

heading: 6 CONCLUSION

text: We identify two strategies of algorithmically interpreting “most” in a visual context, with different implications on cognitive concepts. Following experimental practice of similar investigations with humans in psycholinguistics, we design experiments and data to shed light on the question whether the state-of-the-art FiLM VQA model shows preference for one strategy over the other. Performance on various specifically designed instances does indeed indicate that a form of approximate number system is learned, which generalizes to more difficult scenes as predicted by Weber’s law. The results further suggest that additional features influence the interpretation process, which are affected by the spatial arrangement and relative size of objects in a scene. There are many opportunities for future work from here, from strengthening the finding of an approximate number system and further analyzing confounding factors, to investigating the relation to more explicit counting tasks, to extending the evaluation to other visual question answering models which also exhibit good performance on related tasks (Hudson & Manning, 2018; Zhang et al., 2018; Santoro et al., 2017).


summaries: The paper presents a probabilistic treatment of knowledge graph embeddings, motivating it in parameter uncertainty estimation and easier hyperparameter optimisation. The authors present density-based DistMult and ComplEx variants, where the posterior parameter distributions for entity and relation embeddings are approximated by diagonal Gaussians q_\gamma. Variational EM is used to infer the variational parameters \gamma as well as the per-entity/per-relation precision (\lambda) hyperparameters. The training process proposed by the authors consists of three phases: (1) pretraining a MAP estimate that’s used as initial means of the posterior approximating Gaussians, (2) variational EM (see above) to find better hyperparameters and (3) another MAP training phase that uses the updated per-entity/per-relation hyperparameters. Finally, experimental results indicate a slight improvement in MRR and HITS@10 across FB and WN datasets.

summaries: In this paper, authors propose a probabilistic extension of classic Neural Link Prediction models, such as DistMult and ComplEx. The underlying assumption is that the entity embeddings and the relation embeddings are sampled from a prior Multivariate Normal distribution, whose (hyper-)parameters can be estimated via maximum likelihood. In this paper, authors use Variational Inference (VI) for approximating the posterior distribution over the embeddings, and use Stochastic VI for maximising the Evidence Lower BOund (ELBO) while scaling to large datasets. In Sect. 3, authors introduce the generative process, and show how MAP estimation of the embedding matrices can recover the original models. In Sect. 4, authors start from the intractable marginal likelihood over the data (Eq. 5) for deriving the corresponding ELBO (Eq. 6), which is defined over:

abstractText: We develop a probabilistic extension of state-of-the-art embedding models for link prediction in relational knowledge graphs. Knowledge graphs are collections of relational facts, where each fact states that a certain relation holds between two entities, such as people, places, or objects. We argue that knowledge graphs should be treated within a Bayesian framework because even large knowledge graphs typically contain only few facts per entity, leading effectively to a small data problem where parameter uncertainty matters. We introduce a probabilistic reinterpretation of the DistMult (Yang et al., 2015) and ComplEx (Trouillon et al., 2016) models and employ variational inference to estimate a lower bound on the marginal likelihood of the data. We find that the main benefit of the Bayesian approach is that it allows for efficient, gradient based optimization over hyperparameters, which would lead to divergences in a non-Bayesian treatment. Models with such learned hyperparameters improve over the state-of-the-art by a significant margin, as we demonstrate on several benchmarks.

authors:
Robert Bamler
Stephan Mandt

title: Dynamic word embeddings

venue: Proceedings of the 34th international conference on Machine learning,

title: Bayesian neural word embedding

authors:
JM Bernardo
MJ Bayarri
JO Berger
AP Dawid
D Heckerman
AFM Smith
M West

title: The variational Bayesian EM algorithm for incomplete data: with application to scoring graphical model structures

venue: Bayesian statistics,

title: Pattern Recognition and Machine Learning (Information Science and Statistics)

authors:
David M Blei
Alp Kucukelbir
Jon D McAuliffe

title: Variational inference: A review for statisticians

venue: Journal of the American Statistical Association,

authors:
Kurt Bollacker
Colin Evans
Praveen Paritosh
Tim Sturge
Jamie Taylor

title: Freebase: a collaboratively created graph database for structuring human knowledge

venue: In Proceedings of the 2008 ACM SIGMOD international conference on Management of data,

authors:
Antoine Bordes
Nicolas Usunier
Alberto Garcia-Duran
Jason Weston
Oksana Yakhnenko

title: Translating embeddings for modeling multi-relational data

venue: In Advances in neural information processing systems,

authors:
Antoine Bordes
Xavier Glorot
Jason Weston
Yoshua Bengio

title: A semantic matching energy function for learning with multi-relational data

venue: Machine Learning,

authors:
Arthur P Dempster
Nan M Laird
Donald B Rubin

title: Maximum likelihood from incomplete data via the EM algorithm

venue: Journal of the Royal Statistical Society. Series B (methodological),

authors:
Tim Dettmers
Pasquale Minervini
Pontus Stenetorp
Sebastian Riedel

title: Convolutional 2d knowledge graph embeddings

title: Knowledge graph based search

venue: US Patent App

authors:
Nir Friedman
Lise Getoor
Daphne Koller
Avi Pfeffer

title: Learning probabilistic relational models

venue: In IJCAI,

authors:
Prem Gopalan
Francisco J Ruiz
Rajesh Ranganath
David Blei

title: Bayesian nonparametric poisson factorization for recommendation systems

venue: In Artificial Intelligence and Statistics,

authors:
Prem Gopalan
Jake M Hofman
David M Blei

title: Scalable recommendation with hierarchical poisson factorization

venue: In UAI, pp

title: The expression of a tensor or a polyadic as a sum of products

venue: Journal of Mathematics and Physics,

authors:
Patrick Jähnichen
Florian Wenzel
Marius Kloft
Stephan Mandt

title: Scalable generalized dynamic topic models

authors:
Geng Ji
Robert Bamler
Erik B Sudderth
Stephan Mandt

title: Bayesian paragraph vectors

venue: Symposium on Advances in Approximate Bayesian Inference,

authors:
Guoliang Ji
Kang Liu
Shizhu He
Jun Zhao

title: Knowledge graph completion with adaptive sparse transfer matrix

authors:
Michael I Jordan
Zoubin Ghahramani
Tommi S Jaakkola
Lawrence K Saul

title: An introduction to variational methods for graphical models

venue: Machine learning,

authors:
Rudolf Kadlec
Ondrej Bajgar
Jan Kleindienst

title: Knowledge base completion: Baselines strike back

venue: In Proceedings of the 2nd Workshop on Representation Learning for NLP,

authors:
Kristian Kersting
Sriraam Natarajan
David Poole

title: Statistical relational ai: logic, probability and computation

venue: In Proceedings of the 11th International Conference on Logic Programming and Nonmonotonic Reasoning

authors:
Diederik P Kingma
Max Welling

title: Auto-encoding variational bayes

venue: In International Conference on Learning Representations (ICLR),

authors:
Timothée Lacroix
Nicolas Usunier
Guillaume Obozinski

title: Canonical tensor decomposition for knowledge base completion

venue: In Proceedings of the 35th International Conference on Machine Learning,

authors:
Dawen Liang
Rahul G. Krishnan
Matthew D. Hoffman
Tony Jebara

title: Variational autoencoders for collaborative filtering

venue: In Proceedings of the 2018 World Wide Web Conference,

authors:
Yankai Lin
Zhiyuan Liu
Maosong Sun
Yang Liu
Xuan Zhu

title: Learning entity and relation embeddings for knowledge graph completion

authors:
Stephan Mandt
Matthew D Hoffman
David M Blei

title: Stochastic gradient descent as approximate bayesian inference

venue: The Journal of Machine Learning Research,

title: An overview of embedding models of entities and relationships for knowledge base completion

venue: arXiv preprint arXiv:1703.08098,

authors:
Maximilian Nickel
Kevin Murphy
Volker Tresp
Evgeniy Gabrilovich

title: A review of relational machine learning for knowledge graphs

venue: Proceedings of the IEEE,

authors:
Maximilian Nickel
Lorenzo Rosasco
Tomaso A Poggio

title: Holographic embeddings of knowledge graphs

authors:
Feng Niu
Ce Zhang
Christopher Ré
Jude W Shavlik

title: Deepdive: Web-scale knowledge-base construction using statistical learning and inference

authors:
Jay Pujara
Hui Miao
Lise Getoor
William W Cohen

title: Using semantics and statistics to turn data into knowledge

venue: AI Magazine,

authors:
Danilo Jimenez Rezende
Shakir Mohamed
Daan Wierstra

title: Stochastic backpropagation and approximate inference in deep generative models

venue: In Proceedings of the 31st International Conference on Machine Learning,

authors:
Yelong Shen
Po-Sen Huang
Ming-Wei Chang
Jianfeng Gao

title: Implicit reasonet: Modeling large-scale structured relationships with shared memory

authors:
Baoxu Shi
Tim Weninger

title: Proje: Embedding projection for knowledge graph completion

authors:
Nathan Srebro
Ruslan R Salakhutdinov

title: Collaborative filtering in a non-uniform world: Learning with the weighted trace norm

venue: In Advances in Neural Information Processing Systems,

authors:
Kristina Toutanova
Danqi Chen

title: Observed versus latent features for knowledge base and text inference

venue: In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality,

authors:
Théo Trouillon
Johannes Welbl
Sebastian Riedel
Éric Gaussier
Guillaume Bouchard

title: Complex embeddings for simple link prediction

venue: In Proceedings of the 33rd International Conference on Machine Learning,

authors:
Zhen Wang
Jianwen Zhang
Jianlin Feng
Zheng Chen

title: Knowledge graph embedding by translating on hyperplanes

authors:
Zhigang Wang
Juan-Zi Li

title: Text-enhanced representation learning for knowledge graph

authors:
Han Xiao
Minlie Huang
Lian Meng
Xiaoyan Zhu

title: Ssp: Semantic space projection for knowledge graph embedding with text descriptions

authors:
Bishan Yang
Wen-tau Yih
Xiaodong He
Jianfeng Gao
Li Deng

title: Embedding entities and relations for learning and inference in knowledge bases

authors:
Cheng Zhang
Judith Butepage
Hedvig Kjellstrom
Stephan Mandt

title: Advances in variational inference

venue: arXiv preprint arXiv:1711.05597,

heading: 1 INTRODUCTION

text:
In 2012, Google announced that it improved the quality of its search engines significantly by utilizing knowledge graphs (Eder, 2012). A knowledge graph is a dataset of facts represented in terms of triplets (head, relation, tail), where head and tail represent entities in the world, and a relation is a property that describes the relationship between the two entities. As an example, when the head entity is ’Paris’, and the relation is ’is in’, then the tail entity could be ’France’ or ’Europe’.
While the number of possible relations among entities is enormous, the amount of edges in empirical knowledge graphs is often rather small. It is therefore desirable to complete the missing edges in a knowledge graph algorithmically based on patterns detected in the observed part of he graph (Nickel et al., 2016a). Such link prediction has become an important subfield of artificial intelligence (Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015; Nickel et al., 2016c; Trouillon et al., 2016; Wang & Li, 2016; Ji et al., 2016; Shen et al., 2016; Xiao et al., 2017; Shi & Weninger, 2017; Lacroix et al., 2018).
In statistical relational learning, link prediction is done by inferring/learning explicit rules about relationships and then applying these inferred rules in order to reason about unobserved facts (Friedman et al., 1999; Kersting et al., 2011; Niu et al., 2012; Pujara et al., 2015). A complementary, highly scalable approach relies on embedding models (Kadlec et al., 2017; Nguyen, 2017). These models represent entities and relationships in terms of low-dimensional semantic vectors and implicitly encode the relationships in the knowledge graphs in terms of three-way mathematical operations among these vector triplets (Yang et al., 2015; Trouillon et al., 2016). In the early works, different embeddings were used for the two tasks of head and tail prediction. Lacroix et al. (2018) proposed to map these two tasks to just the tail prediction task by augmenting the data by reciprocal facts with inversed relations. In the present work, we also use this data augmentation technique to pave the way for a probabilistic interpretation of knowledge graph embedding models. The probabilistic formulation allows us to keep track of parameter uncertainty by applying Bayesian methods.
We argue that the parameter uncertainty in knowledge graph embedding models can be significant, calling for a Bayesian approach. As the number of parameters grows linearly with the number of entities, and every entity is only connected to a small number of other entities by observed links, this effectively leads to a small data problem, even if the knowledge graph as a whole may be huge. For example, Figure 1 shows that for a popular large-scale knowledge base, about 80% of entities have
less than 80 observed facts. Similar observation have been made for recommender systems, where most users interact only with a small subset of the items (Gopalan et al., 2014; 2015; Liang et al., 2018). As in recommender systems, we show that a Bayesian approach can be highly beneficial in knowledge graph embeddings. This paper presents such a Bayesian formulation and presents an interpretation of popular embedding models as generative models of relational facts.
The benefits of a Bayesian formulation of knowledge graph embeddings are two-fold. First, this formulation allows us to infer posterior distributions of embedding vectors, giving us uncertainty estimates. An arguably more important aspect is that of hyperparameter tuning, as the state-of-the-art embedding models employ a large number of hyperparameters (regularizers), one for every entity (Lacroix et al., 2018). Kadlec et al. (2017) showed that careful hyperparameter tuning can dramatically increase predictive performance. While there is no classical way to scalably tune hyperparameters on a per-entity level without some heuristic, our Bayesian approach allows for gradient-based hyperparameter optimization on the marginal likelihood of the data (Bishop, 2006). This approach, termed variational expectation maximization (variational EM (Bernardo et al., 2003)), still works if variational approximations are used (Jordan et al., 1999; Blei et al., 2017; Zhang et al., 2017).
We propose a simple, principled, and efficient way to tune hyperparameters using variational EM. This approach lower-bounds the marginal likelihood of the data and allows this bound to be optimized for hyperparameters without running into degenerate solutions (Bernardo et al., 2003; Mandt et al., 2017). This is in contrast to point estimation, which results in degeneracies when jointly optimizing over model parameters and hyperparameters. As a result, our approach learns a macroscopic number of hyperparameters, resulting in a new state-of-the-art performance on link prediction.
Our contribution in this work can be summarized as follows: • We present a probabilistic interpretation of existing knowledge graph embedding models such as
ComplEx and DistMult. We reformulate these models as generative models for relational facts, which paves the way for Bayesian inference in these models. • We apply stochastic variational inference to scalably estimate an approximate posterior for each entity and relation embedding in the knowledge graph. This approach not only allows us to estimate uncertainty, but more importantly allows for gradient-based hyperparameter optimization by stochastic gradient descent on the optimized variational bound (variational EM). Implementing our methodology in existing models requires only a few lines of additional code, and it does not increase the computational complexity compared to a non-Bayesian training approach. • We show experimentally that our method reaches new state-of-the-art results in link prediction. We present results on several large data sets using two popular models which we trained using variational EM. We observe that our improvements are most notable for entites with few training points, as we show by introducing a new, balanced evaluation metric.
The paper is structured as follows. In Section 2, we review the related work about knowledge graph embeddings and variational inference. In Section 3, we present the generative model for relational facts and reinterpret existing loss functions as the maximum a posterior estimator of the generative
model. In Section 4, we propose our approximate Bayesian expectation maximization algorithm for finding the hyperparameters. Finally, in Section 5 we test the hyperparameter learning algorithm for the link prediction task on two different embedding algorithms using standard performance metrics.

heading: 2 RELATED WORK

text:
Related work to this paper can be grouped into link prediction algorithms and variational inference.
Link Prediction. Knowledge graphs and link prediction gained a lot of attention; for a review see (Nickel et al., 2016b). Most link prediction algorithms use latent features of entities or relationships, also termed embeddings. TransE proposed by Bordes et al. (2013) is one example, where each entity and relation are embedded in a K-dimensional space. The embeddings are found such that for a given fact (h, r, t), the sum of embeddings of h plus r be close to t, and far from other entities.
Many models are based on tensor factorization, where an adjacency tensor is built from the triplet facts, and entities and relations are embedded to a K-dimensional space. Different methods differ in the structure of the embedded vectors. Hitchcock (1927) assume that an entity’s embedding depends on whether the entity appears as the head or tail of a fact. DistMult simplified the model by assuming that tails and heads have the same embeddings (Yang et al., 2015; Toutanova & Chen, 2015). ComplEx extended DistMult by embedding the entities and relations to a complex space to allow for nonsymmetric relations. Lacroix et al. (2018) introduced reciprocal relations and trained with the full log-loss instead of binary loss with negative sampling, which improved the results.
Link prediction algorithms are susceptible to overfitting, and the importance of hyperparameter choices has been pointed out by several authors, e.g., (Kadlec et al., 2017; Lacroix et al., 2018). Different reguralizers have been proposed, the most standard one being the 2-norm (Yang et al., 2015). A heuristic that often produces the best results (e.g., in (Lacroix et al., 2018)) is to choose the strength of the regularizer proportional to the frequency of the entities (see e.g., (Srebro & Salakhutdinov, 2010)). In contrast, our approach learns entity-dependend hyperparameters without relying on heuristics. Also, Lacroix et al. (2018) showed that the 2-norm is not a valid tensor norm, and that the 3-norm is more appropriate for triplet data.
Variational Inference. Variational inference (VI) is a powerful technique to approximate a Bayesian posterior over latent variables given observations (Jordan et al., 1999; Blei et al., 2017; Zhang et al., 2017). Besides approximating the posterior, VI also estimates the marginal likelihood of the data. This allows for gradient-based hyperparameter tuning, a technique called variational EM (Bernardo et al., 2003), which is the main benefit of the Bayesian approach used in this paper.
Our paper builds on recent probabilistic extensions of embedding models to Bayesian models, such as word (Barkan, 2017) or paragraph (Ji et al., 2017) embeddings. In these works, the words are embedded into a K-dimensional space. It has been shown that using a probabilistic approach leads to better performance on smaller data, and allows these models to be combined with powerful priors, such as for time series modeling (Bamler & Mandt, 2017; Jähnichen et al., 2018). Yet, the underlying probabilistic models in these papers are very different from the ones considered in our work.

heading: 3 KNOWLEDGE GRAPH EMBEDDINGS AS GENERATIVE MODELS OF FACTS

text:
In this section, we describe a generative model for relational facts. Then, we show that existing tensor factorization models can be interpreted as a maximum a posteriori (MAP) estimation of the parameters of the generative model (Bishop, 2006). In Section 4, we move to our main contribution. We use our generative model to derive an approximate Bayesian inference algorithm to optimize over hyperparameters (regularizers) in a principled way.
Let S = {(hi, ri, ti)}i=1,...,n be the set of n triplet facts, with heads hi ∈ [Ne], tails ti ∈ [Ne], and relations ri ∈ [Nr]. Here, Ne and Nr are the number of distinct entities and relations that we model.
From now on, we use the data augmentation technique used in (Lacroix et al., 2018) (see Remark 2 in
the appendix). It reduces the task of performing both head and tail predictions to that of performing only tail predictions by introducing reciprocal relations. Thus, given a head h and relation r, the link prediction boils down to finding the tail t in the fact (h, r, t).
For simplicity, we present the generative process at the example of the DistMult model (Yang et al., 2015). Generalization to other models, such as ComplEx (Trouillon et al., 2016) or CP (Hitchcock, 1927) is straight-forward. In DistMult, each entity and relation is embedded in the latent vector space RK . Let E ∈ RNe×K (similarly R ∈ RNr×K) be the embedding matrix for entities (relations), where Ee ∈ RK (Rr ∈ RK) is the embedding vector for entity e ∈ [Ne] (relation r ∈ [Nr]).
The Score. Embedding models such as DistMult rely on a score Xh,r,t which plays a role both in the probabilistic and classical formulation of the model. This score assigns a scalar value to each combination of the embeddings Eh, Rr, and Et. In DistMult, the score is Xh,r,t = ∑K i=1 EhiRriEti. In the conventional approach, the embedding vectors are trained in such a way that observed triplets have high scores. As we show below, the score also enters the probabilistic extension of the model.
Generative Process. We can now present our perspective of knowledge graph embeddings as generative models. Figure 2 shows a graphical model. The generative process is as follows:
• For each entity e ∈ [Ne], draw an embedding Ee ∈ RK from a prior p(Ee|λe), e.g., a normal distribution. Similarly, for each relation r ∈ [Nr], draw an embedding Rr ∈ RK from a prior p(Rr|λr). Here, λe and λr are hyperparameters. • Repeat for each triplet index i ∈ {1, . . . , n}:
– Draw a head hi and a relation ri from a discrete joint distribution P (hi, ri). – Draw a tail ti ∼ Multinomial(softmaxt(Xhi,ri,t)).
Above, the softmax normalizes the scores over the tail index, softmaxt(Xh,r,t) = exp Xh,r,t∑ t′ exp Xh,r,t′
. We see that the resulting generative model produces fact triplets conditioned on semantic embeddings of entities and relations. This concludes the generative process perspective.
MAP Estimation Recovers Original Model. The cost function used for learning E and R in the existing works can be seen as maximum a posteriori (MAP) estimation of the generative model above, where we optimize the log joint distribution over the embeddings E and R:
E?,R? = arg max E,R log p(E,R,S|λ) = arg max E,R
{ log p(S|E,R) + log p(E,R|λ) } . (1)
In the DistMult model, the loss function with a Gaussian prior with precision λ becomes
L(E,R, λ) = − log p(S|E,R)− log p(E,R|λ), (2) where the negative log likelihood is just the cross entropy,
− log p(S|E,R) = ∑
(h,r,t)∈S
( −Xh,r,t + log
∑ t′ exp Xh,r,t′
) + c, (3)
and the negative log prior leads to the regularizer
− log p(E,R|λ) = 1 2 ∑ e∈[Ne] ( λe‖Ee‖2 −K log(λe) ) + 1 2 ∑ r∈[Nr] ( λr‖Rr‖2 −K log(λr) ) + c. (4)
Up to the terms K log(λe/r) in Eq. 4, which do not affect the minimization over E and R, Eqs. 2-4 recover precisely the loss function used in (Lacroix et al., 2018).

heading: 4 GRADIENT-BASED HYPERPARAMETER TUNING VIA VARIATIONAL EM

text:
In this section, we describe an efficient method to learn optimized hyperparameters λe and λr for each entity and each relation embedding in the model. We stress that such optimization could not be achieved via classical grid search due to the sheer number of hyperparameters; this number would
have to be reduced by some heuristic (Srebro & Salakhutdinov, 2010). Our method is based on optimizing the marginal likelihood over λe and λr using variational inference.
Recall that in a knowledge graph, the number of triplets per entity is typically small (see Figure 1). Therefore, the cross entropy (log likelihood, Eq. 3) contains only few terms per entity, and thus the regularizer (log prior, Eq. 4) has a strong influence on the optimization.
Finding good hyperparameters λe and λr for each entity e and relation r would usually involve expensive cross validations and grid search over many parameters. Simply minimizing the loss L in Eqs. 2-4 over both hyperparameters λe/r and model parameters E and R does not work because L is not bounded from below. Setting E and R to zero and λe, λr → ∞ would send L → −∞ due to the terms −K2 log(λe/r) in Eq. 4. Note that ignoring these terms would not solve the problem, as the optimization would then set λe and λr to zero and the model would become unregularized.
Algorithm 1 Gradient Based Tuning of Hyperparameters λ 1: Input: Number of training steps T ; number of initialization steps T0 2: Initialize: λ and γ = (µ, σ) 3: Pre-train the model using SGD: µE , µR = arg minE,R L(E,R, λ) 4: for t = 0 : T do . Variational EM update for T iterations 5: draw mini-batch B ∈ S 6: draw uniform noise samples, e ∼ N(0, I) and r ∼ N(0, I) 7: γ ← γ −∇γ [ L ( µE + EσE , µR + RσR, λ ) − log σE − log σR ] . L = loss, see Eq. 2
8: if t ≥ T0 then λ← arg maxλ Eqγ [log p (E,R|λ)] . See appendix for analytic solution 9: else do not update hyperparameters λ
10: Re-train model with learned hyperparameters: E∗,R∗ = arg minE,R L(E,R, λ)
Variational Expectation Maximization. A well-known approach to avoid degenerate solutions in gradient-based hyperparameter optimization is the expectation-maximization (EM) algorithm (Dempster et al., 1977). This algorithm optimizes the marginal likelihood of a model with hidden variables over hyperparameters by alternating between a gradient step on hyperparameters, and a step in which the hidden variables are integrated out. We use a version of EM based on variational inference, termed variational EM (Bernardo et al., 2003) that avoids the integration step.
The measure of how well a probabilistic model fits the data S is the marginal likelihood, p(S|λ) = ∫ p(E,R,S|λ) dE dR. (5)
We want to find hyperparameters λ that maximize the marginal likelihood p(S|λ); however, since the integral in Eq. 5 is intractable, the marginal likelihood is unavailable in closed form. To circumvent this problem, we use variational inference (VI) (Jordan et al., 1999). In VI, one first chooses a family of variational distributions qγ(E,R), which is parameterized by so-called variational parameters γ. Evoking Jensen’s inequality, the marginal likelihood is then lower-bounded by the evidence lower bound (Blei et al., 2017; Zhang et al., 2017), or ELBO, as
log p(S|λ) ≥ EE,R∼qγ [log p(E,R,S|λ)− log qγ(E,R)] =: ELBO(λ, γ). (6) The bound is tight if the variational distribution qγ is the true posterior of the model for given λ. Therefore, maximizing the ELBO over the variational parameters γ closes the gap between ELBO and true marginal likelihood, and the ELBO can be taken as a proxy for the latter.
We use the ELBO as a proxy for the marginal likelihood p(S|λ), and we maximize it concurrently over both γ and λ using Black Box Variational Inference with reparameterization gradients (Kingma & Welling, 2014; Rezende et al., 2014). Since p(S|λ) is a discrete probability distribution, it is upper bounded by 1, so the optimization over λ is well defined. As discussed above, this is in contrast to the loss L, which is not bounded as a function of λ.
We choose a fully factorized variational distribution qγ(E,R). This is called the mean field approximation. Specifically, we use a fully factorized Gaussian variational distribution with means µEei and µRri, and standard deviations σ E ei and σ R ri for the parameters Eei and Rri, respectively. The collection of all means and standard deviations comprises the variational parameters γ.
Learning Optimal Hyperparameters. Algorithm 1 summarizes our method. It consists of three steps: (i) Pre-train a point-estimated model using the MAP estimator L (Eqs. 2-4) with a reasonable choice of hyperparameters λ (Line 3 in Algorithm 1). (ii) Use variational EM to maximize the lower bound on the marginal likelihood over the hyperparameters (Lines 4-9); here, we use the pretrained model to initialize the means of the variational distribution, see below. (iii) Plug the learned hyperparameters λ into the MAP estimator and train the final model (Line 10).
Implementing these three steps requires only few changes compared to a MAP estimated model. Steps (i) and (iii) are just the existing MAP estimation of the latent parameters. The implementation of step 2 is also very similar. To optimize the ELBO with the reparameterization gradient trick, one injects parameter noise into the loss L of the MAP estimator (see Lines 6-7). One then optimizes over the optimal amplitude σE/R of the noise using stochastic gradient descent. The additional entropy term − log σE − log σR in Line 7 prevents mode collapse of the variational distribution. Lines 6-7 in Algorithm 1 describe the most generic way to estimate the gradient of the ELBO using reparameterization gradients. For specific models, parts of the ELBO can be evaluated analytically, which typically reduces the gradient noise. In the appendix, we derive an analytic expression for the contribution of the regularizer (log prior) to the ELBO. We find a solution in closed form for regularization with both the 2-norm and the 3-norm. The expected log prior prevents degenerate solutions of the kind discussed above because it penalizes sending λe/r to infinity.
After maximizing ELBO over λ and γ, we plug the learned λ into the original MAP estimator and improve the performance of the model, see Line 10 in Algorithm 1. We also experimented with using the learned variational distribution qγ(E,R) directly for link prediction using a Bayesian inference approach. In this setup, we evaluate the predictive probability of, e.g., a tail t given head h and relation r by taking the expectation of the conditional probability p(t|h, r,E,R) under the variational distribution. We find that, when the embedding dimensions K is small, these Bayesian predictions outperform point estimates. However, for a large embedding dimensionK, MAP estimators perform better. We speculate that this may be because the match between variational distribution and true posterior may be worse in high dimensions, where the true posterior can have a more complicated structure that the mean field variational distribution cannot capture. We find that the main advantage of the variational treatment of the models that we considered is the efficient optimization over hyperparameters.

heading: 5 EXPERIMENTAL RESULTS

text:
We test the performance of DistMult and ComplEx on four standard data sets, where we optimized hyperparameters in two different ways. Our baseline is standard grid search, and our proposed approach for hyperparameter tuning is variational EM (Algorithm 1). The latter relies on the probabilistic formulation provided in this paper. We considered two types of metrics: mean reciprocal rank, and hits at 10 (explained below). Our approach sets a new state-of-the-art in hits at 10 on all four data sets, and in mean reciprocal rank on three out of four data sets.
Performance Metrics. We report the standard metrics used in the knowledge graph embedding literature. We perform head and tail prediction and report all results in the ‘filtered’ setting introduced in (Bordes et al., 2013). In tail prediction, one tries to find the correct tail t of a fact (h, r, t) from the test set when given only head h and relation r. We do this by ranking all candidate tails according to their probabilities under the model. The ‘filtered’ rank, denoted below by rank(t|h, r), takes into account that more than one tail may be a correct answer. One removes from the ranking all other tails t′ 6= t for which a fact (h, r, t′) exists in either the training, validation, or test set. We evaluate the following metrics of the filtered ranks (for all metrics, higher is better):
• Mean Reciprocal Rank (MRR), see, e.g., (Yang et al., 2015). It is defined by
MRR = 100 # of facts in test set S′ ∑
(h,r,t)∈S′
1
rank(t|h, r) . (7)
• Balanced Mean Reciprocal Rank (MRRb). As discussed in the introduction, standard data sets for knowledge graphs are highly imbalanced, i.e., most facts involve only a small subset of all entities. This biases the standard MRR metric. We therefore propose a new metric that is more
balanced than the standard MRR by averaging over entities rather than relations,
MRRb = 100
Ne ∑ e∈[Ne]
1
# of test triplets with tail t  ∑ triplets with tail t
1
rank(t|h, r)  . (8) • Hits at 10 (H@10), see, e.g., (Bordes et al., 2013). It is the percentage of test facts for which
the 10 highest ranked predictions contain the correct prediction, i.e., for which rank(t|h, r) ≤ 10.
Baselines. We study two models, ComplEx (Trouillon et al., 2016; Lacroix et al., 2018) and DistMult (Yang et al., 2015; Kadlec et al., 2017), with and without the variational EM algorithm. As in (Lacroix et al., 2018), our baseline for ComplEx, uses the weighted 3-norm regularizer that reached the previous state-of-the-art performance, i.e., λe/r are proportional to the frequency of entity e (relation r) in the dataset. We implemented our own version of DistMult using reciprocal relations and full log-loss with weighted 3-norm regularizer. The results were consistent with (and even slightly improved) the best results reported in the literature (Yang et al., 2015; Kadlec et al., 2017). Datasets. We used four standard datasets. The first two are FB15K from the Freebase project (Bollacker et al., 2008) and WN18 from the WordNet database (Bordes et al., 2014). The other two datasets, FB15K-237 and WN18RR, are modified versions of FB15K and WN18 due to (Toutanova & Chen, 2015; Dettmers et al., 2018). The motivation for the modified datasets is that FB15K and WN18 contain near duplicate relations that make link prediction trivial for some facts, thus encouraging overfitting. In FB15K-237 and WN18RR these near duplicates were removed.
Results. Tables 1 and 2 summarize our results. We see that the balanced metric MRRb is generally lower than its unbalanced counterpart MRR, confirming the intuition that MRR is biased towards the easier predictions. Table 1 shows results for the ComplEx model. We see that variational EM improves the performance of the ComplEx model on three out of the four datasets. On the fourth dataset, FB15K, variational EM improves H@10 over the baseline, but MRR and MRRb are better in the baseline model. The latter may be explained by the fact that the FB15K data set is known to contain near duplicates in the test-training split, thus favoring models that tend to overfit the data.
For DistMult the improvements are more significant (Table 2). In WN18, variational EM improves both MRR and MRRb by 2 percentage points, and in WN18RR all metrics are improved almost by 1 percent. MRRb is improved by 0.5 percent in FB15K237, and H@10 is improved by 0.5 percent in FB15K. Although a more exhaustive hyper-parameter tuning using cross validation might further improve the performance of DistMult, the goal of this work is to reach such performance without a need to do an expensive grid search. Using variational EM hyperparameter learning algorithm, we can learn good hyperparameters λ easily and reach the state-of-the-art results without spending many resources on hyperparameter tuning.
Finally, we study the influence of the frequency of entities in the training data on the hyperparameters learned by the variational EM algorithm. Figure 3a shows the learned λe for all entities e as a function of the entities’ frequencies. The red line compares this to the weighted regularizer proposed in (Srebro & Salakhutdinov, 2010), which sets λe and λr proportional to the frequency. Qualitatively, our findings confirm the heuristic to use stronger regularization for entities with more training data. Quantitatively, however, we find that a linear relation between frequency and regularization strength is too strong. Our result might point to a better frequency based heuristics to choose λ.
To study the evolution of regularizations over the training time, we divide the entities into three bins [L,M,H] of low, medium, and high frequency. Each bin contains one third of the entities. In Figure 3b shows the evolution of the average λ within each bin as a function of the training epoch. The λ are initialized with the baseline (i.e., λ proportional to their frequency). We hold the hyperparameters fixed for the first 15 epochs of the EM algorithm to allow for the variational distribution qγ to come close to the actual posterior before we start updating λ. We see that on average, the hyperparameters learned by our approach converge to a different optimal value than the heuristic suggested by Srebro & Salakhutdinov (2010). In our experiments, we also see that, as expected, the inferred uncertainties σEe and σ R r are higher for entities and relations with fewer training facts (see appendix for more details).

heading: 6 CONCLUSIONS

text:
We showed that two of the most popular knowledge graph embedding models—DistMult and ComplEx—have an interpretation as probabilistic generative models of facts. Drawing on this view, we presented a scalable variational inference algorithm to learn a lower bound of the marginal likelihood of the data. We used this bound to optimize the many hyperparameters of these models by gradient descent (variational EM); an approach that would not be possible when point estimating model parameters. Using this methodology of optimizing hyperparameters, we outperformed the state of the art in link prediction on several popular benchmark data sets. The approach enjoys the same scalability properties as conventional maximum likelihood learning.
Our approach amounted to training the model twice: once in a Bayesian fashion to optimize hyperparameters, and then by point-estimating model parameters, using the hyperparameters obtained from the previous optimization. One may wonder why the approximate posterior was not used for link prediction. Our experiments revealed that using the posterior for link prediction worked well in low dimensions, but underperformed in high dimensions (not shown). We interpret this as a failure of the variational approximation in high dimension where the true posterior may locally not look Gaussian, pushing the variational Gaussian means away from the posterior maximum. For learning hyperparameters via variational EM, however, the variational approach works in all considered embedding dimensions. In the future, it would be interesting to explore more sophisticated posterior approximations that avoid this double-training procedure. However, a fully-Bayesian prediction task would be expensive to evaluate, making the proposed approach the most relevant one in practice.

heading: A APPENDIX

text:
A.1 COMPUTING THE TERMS IN ELBO
In this section , we compute the expectations appear in the ELBO in Eq. 6. For simplicity, we choose DistMult as the embedding model, but the computations are similar for the other models such as ComplEx (Trouillon et al., 2016) or CP (Hitchcock, 1927). The term −Eqγ [log qγ(E,R)] is the entropy of the Gaussian distribution, and it is
− Eqγ [log qγ(E,R)] = ∑ e∈[Ne] ∑ i∈[K] log σEei + ∑ r∈[Nr] ∑ i∈[K] log σRri + c, (9)
where c is a constant and can be ignored in the optimization process. Now, let us focus on the evaluation of the expected prior. We derive the equations for Eqγ [log p(E|λe)] and Eqγ [log p(R|λr))] can be computed in a similar way.
Gaussian prior. First, let us focus on the Gaussian prior p(Ee|λe) = √
( λe 2π )K exp(−λe‖Ee‖2/2).
The log of Gaussian prior is
log p(Ee|λe) = − λe 2 ‖Ee‖2 + K 2 log λe + c. (10)
The expectation of Eq. 10 with respect to the variational distribution qγ is
Eqγ [log p(Ee|λe)] = − λe 2
( ‖µEe ‖2 + ‖σEe ‖2 ) + K
2 log λe + c., (11)
where ‖σEe ‖2 = ∑ i∈[K](σ E ei)
2, (details can be found in Appendix B of (Kingma & Welling, 2014)). Notice that λe only appears in p(Ee|λe), so for a given µEe and σEe we can easily find its optimal value by maximizing Eqγ [log p(Ee|λe)] over λ as follows,
λe = K
‖µEe ‖2 + ‖σEe ‖2 , (12)
Nuclear 3-norm prior. Now, let us consider the prior
p(Ee|λe) = 1 Z exp(−λe 3 ‖Ee‖33),
where Z is the normalization factor. The normalization factor Z is only a function of λe and not the variational parameters γ, hence Eqγ [logZ] = logZ. We start the analysis by computing the normalization factor Z,
Z = ∫ Ee∈RK exp(−λe 3 ‖Ee‖33) dEe, (13)
we compute the integral with the change of the variables ζ = λ1/3e Ee
Z = 1
λ K/3 e ∫ ζ∈RK exp(−1 3 ‖ζ‖33) dζ = c λ K/3 e , (14)
where c = ∫ ζ∈RK exp(− 13‖ζ‖33) dζ. Therefore,
Eqγ [logZ] = logZ = − K
3 log λe + c (15)
Now, let us focus on computing
Eqγ [ λe 3 ‖Ee‖33] = Eqγ [ λe 3 ∑ i∈[K] |Eei|3].
Given the Gaussian variational distribution N(µEei, (σ E ei) 2), the samples of N(µEei, (σ E ei) 2) can be written as Eei ∼ µEei + σEei , (16) where ∈ R is the noise sampled from the Gaussian distribution N(0, 1). Using this reparametrization, we get
Eqγ [ ‖Eei‖33 ] =
1√ 2π ∫ ∞ −∞ |µEei + σeix|3e− 1 2x 2 dx
µ0= µEei σei=
σ3ei√ 2π ∫ ∞ −∞ |µ0 + x|3e− 1 2x 2 dx
= σ3ei√ 2π [ − ∫ ∞ µ0 (−µ0 + x)3e− 1 2x 2 dx+ ∫ ∞ −µ0 (µ0 + x) 3e− 1 2x 2 dx ] =
σ3ei√ 2π
[ 2 ∫ ∞ µ0 (3µ20x+ x 3)e− 1 2x 2 dx+ ∫ µ0 −µ0 (3µ0x 2 + µ30)e − 12x 2 dx ] =
σ3ei√ 2π
[ 2(µ20 + 2)e − 12µ 2 0 + √ π
2
( 6µ0 + 2µ 3 0 ) erf(
µ0√ 2 ) ] = √ 2
π
( (µEei) 2σei + 2(σei) 3 ) e − 12 ( µEei σei )2 + ( 3|µEei|(σei)2 + |µEei|3 ) erf ( |µEei|√
2σei
) ,
(17) where erf(·) is the error function. Given Eqγ [ ‖Ee‖33 ] we can compute the optimal λ for a given γ by maximizing ELBO as
λe = K
Eqγ [‖Ee‖33] . (18)
Arbitrary prior. For an arbitrary prior, we can always use the reparameterization trick to compute a stochastic estimate of log prior and its gradient (check Lines 4-6 in Algorithm 1).
A.2 FURTHER REMARKS
Remark 1. DistMult is further improved by Trouillon et al. (2016). The improved algorithm (ComplEx) embeds the entities and relations to a K dimensional complex space CK rather than RK , and Xh,r,t = Re (∑K i=1 EhiRriĒti ) . Using complex numbers increases the flexibility of the algorithm and allows ComplEx to capture the non-symmetry in the triplet facts, meaning that Xh,r,t 6= Xt,r,h. This happens when the imaginary parts of the entries of the Rr are non-zero, while if the imaginary parts of the entries of the Rr are zero, the model can learn the symmetric relations, i.e., Xh,r,t = Xt,r,h. This is in contrast to DistMult, where always Xh,r,t = Xt,r,h. Remark 2. Lacroix et al. (2018) presented a data augmentation technique, which simplifies the presentation of the model. Given the set of the triplet facts {(hi, ri, ti)}i=1,...,n, one first augments the data set by adding a new ‘reciprocal’ fact for each existing fact (hi, ri, ti). Then, for each fact (hi, ri, ti) in the original data set, one adds a new fact by swapping head hi and tail ti and replacing the relation with its reciprocal relation. The new dataset S = {(hi, ri, ti)}i=1,...,2n has 2n facts, Ne entities and 2Nr relations (Nr relations plus Nr reciprocal relations). This augmentation of the data maps the head and tail prediction task to just tail prediction. Two advantages are: (i) better performance, this is because the relations are trained specifically for the task of tail predictions rather than training a relation for both head and tail predictions (Lacroix et al., 2018); and (ii) it establishes a consistent causal direction (h, r) → t that enables us to reuse the generative model for both head and tail predictions.
A.3 UNCERTAINTY ANALYSIS
Figure 4 depicts the average standard deviation (i.e., σE and σR) of the embeddings inferred by variational EM algorithm. As it is seen, on average, the frequent entities or relations have a lower
uncertainty and variational EM algorithm learns more confident embeddings for the frequent entities or relations. Also, on average, the relations’ embeddings have lower uncertainty compared to the embeddings’ uncertainty. This is because there are fewer relations compared to entities, hence on average, there are more facts for a relation compared to an entity.