DEEP ADAPTIVE SEMANTIC LOGIC (DASL): COMPILING DECLARATIVE KNOWLEDGE INTO DEEP NEURAL NETWORKS
Authors: Karan Sikka
Andrew Silberfarb
John Byrnes
Indranil Sur
Ed Chow
Ajay Divakaran
Richard Rohwer
Venue:  (2021)
Keywords: deep neural networks
first order logic
neuro-symbolic computing
knowledge
commonsense

Abstract: We introduce Deep Adaptive Semantic Logic (DASL), a novel framework for automating the generation of deep neural networks that incorporates user-provided formal knowledge to improve learning from data. We provide formal semantics that demonstrate that our knowledge representation captures all of first order logic and that finite sampling from infinite domains converges to correct truth values. DASL’s representation improves on prior neuro-symbolic work by avoiding vanishing gradients, allowing deeper logical structure, and enabling richer interactions between the knowledge and learning components. We illustrate DASL through a toy problem in which we add structure to an image classification problem and demonstrate that knowledge of that structure
reduces data requirements by a factor of 1000. We apply DASL on a visual relationship detection task and demonstrate that the addition of commonsense knowledge improves performance by 10.7% in a data scarce setting.

Under review as a conference paper at ICLR 2021
DEEP ADAPTIVE SEMANTIC LOGIC (DASL): COMPIL- ING DECLARATIVE KNOWLEDGE INTO DEEP NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
We introduce Deep Adaptive Semantic Logic (DASL), a novel framework for automating the generation of deep neural networks that incorporates user-provided formal knowledge to improve learning from data. We provide formal semanties that demonstrate that our knowledge representation captures all of first order logic and that finite sampling from infinite domains converges to correct truth values. DASL's representation improves prior neuro-symbolic work by avoiding vanish- ing gradients, allowing deeper logical structure, and enabling richer interactions between the knowledge and learning components. We illustrate DASL through toy problem in which we add structure to an image classification task and demon- strate that knowledge of that structure reduces data requirements by factor of 1000. We apply DASL on a visual relationship detection task and demonstrate that the addition of commonsense knowledge improves performance by 10. 10.7% conditions of data scarcity.
INTRODUCTION
Early work Artificial Intelligence focused on Knowledge Representation and Reasoning (KRR) through the application of techniques from mathematical logic [Genesereth & Nilsson [987]]. The compositionallty of KRR techniques provides expressive power for capturing expert knowledge in the form of rules or assertions (declarative knowledge), but they are brittle and unable to generalize or scale. Recent work has focused on Deep Learning (DL), in which the parameters of complex functions are estimated from data [LeC'un et al. a ). DL techniques learn to recognize patterns not easily captured by rules and generalize well from data, but they often require large amounts of data for learning and in most cases do not reason at all (Yngg et al. (2017); Garcez al, (2012) Marcus (2018); Weiss et al. (2016)]. J. In this paper we present (Deep Adaptive Semantic Logic (DASL)), a framework that attempts to take advantage of the complementary strengths of KRR and DL by fitting a model simultaneously to data and declarative knowledge. DASL enables robust abstract reasoning and application of domain knowledge to reduce data requirements and control model generalization.
DASL represents declarative knowledge as assertions in first order logic. The relations and functions that make up the vocabulary of the domain are implemented by neural networks that can have arbitrary structure. The logical connectives in the assertions compose these networks into a single deep network that trained to maximize their truth. Figure provides an example network that implements simple rule set through composition of network components performing image classification. Logical quantifiers "for all" and "there exists" generate subsamples of the data on which the network trained. DASI. treats labels like assertions about data, removing any distinction between knowledge and data. This provides mechanism by which supervised, semi-supervised, unsupervised, and distantly supervised learning take place simultaneously in single network under single training regime.
The field of neuro-symbolic computing [Garcez et al. [2019)] focuses on combining logical and neural network techniques in general, and the approach of [Seratini & Garcez (2016)) may be the closest of any prior work to DASL. To generate differentiable functions to support backpropagation, these approaches replace pure Boolean values of and for True and False with continuous values from [0, 1] and select fuzzy logic operators for implementing the Boolean connectives. These operators generally employ maximum or minimum functions, removing all gradient information at the limits,

---

Under review as a conference paper at ICLR 2021
DASL
Components:
Compledd DNN
Loes C
Precicatasi Functions
Biiisel F
Bilofo
Ridabile o)
Cankideis)
Logical operatore
Object Classifiors
Aboroja.o)
Relation Classifier
sublects
obbect
Image
L.Poroon(s) CanRide(a)
2.Biio)(o) Ridubleio)
3.Riding( + (CanRidee()) +))
A Ridable(o)
Parsing
A Abone(s.oi)
Expert Knoweddee
Input Data
Figure 1: DASL integrates user-provided expert knowledge with training data to leam DNNs. It achieves this by compiling DNN from knowledge, expressed in first order logie, and domain-specific neural components. This DNN is trained using backpropagation, fitting both the data and knowledge. Here DASL applies commonsense knowledge to the visual relationship detection task. A and + refer 'and' and 'implics' connectives respectively.
or else they use a product, which drives derivatives toward 0 that there is very little gradient for learning (see subsection A.7p. DASL circumvents these issues by using a logit representation of truth values, for which the range is all real numbers.
Approaches to knowledge representation, both in classical AI and in ncuro-symbolic computing, often restrict the language fragments of first order logic (FOL. in order to reduce computational complexity. We demonstrate that DASI. captures full FOL. with arbitrary nested quantifiers, function symbols, and equality by providing a single formal semantics that unifies DASL models with classical Tarski-style model theory [Chang & Keisler [173)]. We show that DASL is sound and complete for full FOL. FOL requires infinite models general, but we show that iterated finite sampling converges to correct truth values in the limit.
In this paper we show an application of DASL to learning from small amounts of data for two computer vision problems. The first problem is an illustrative toy problem based the MNIST handwritten digit classification problem. The second is a well-known challenge problem of detecting visual relationships in images. In both cases, demonstrate that the addition of declarative knowledge improves the performance of a vanilla DL model. This paper makes the following contributions:
The novel framework DASL, which compiles a network from declarative knowledge and bespoke domain-specific reusable component networks, enabling gradient-based learning of model components;
2. Grounding of the proposed framework in model theory, formally proving its soundness and completeness for full first order logic;
3. A logit representation of truth values that avoids vanishing gradients and allows deep logical structures for neural-symbolic systems;
4. Syntactic extensions that allow (i) restricted quantification over predicates and functions without violating first order logic constraints, and (ii) novel hybrid network architectures;
5. Evaluation on two computer vision problems with limited training data, demonstrating that knowledge reduces data requirements for learning deep models e.g. factor of 1000 for the MNIST toy problem and 70% improvement in accuracy for visual relationship detection in conditions of data scarcity.
2

---

Under review as a conference paper at ICLR 2021
2
RELATED WORK
Neuro-Symbolic Computing:
Early efforts to augment DNNs with logic focused on propositional logic. which supports only logical connectives between (atomic) propositions [Garcez et al. (2012)
2019)]. For example, KBANN [Twell& & Shavlik (1994) maps a set of propositions into a graph. constructs neural network, and then trains it. DASL follows this basic idea but fully supports full first order logic (FOL) as well as arithmetic expressions.
Similar to several prior efforts (Hu al. 2016); Rocktäschel et al. (2015) Li & Srikumar (2019) DASL replaces Booleans with real-valued aseudo-probabilitiee to make the logical operations differentiable. This circumstance has motivated the invention of a collection of ad hoc aggregation operators for representing logical connectives [Detyniecki (2001)]. These include the t-norm, used by Logic Tensor Networks (LTNs) [Serafini & Garcez (2016)] and the above works. Instead, DASL uses logit representation for truth values, which avoids vanishing gradients more comprehensively than the logarithmic representations of (Giannini et al. (2019); Rocktäschel et al. (2015)), enabling learning in deeper logical structures. DASL also differs in supporting multiple entity types, arithmetic, and non-traditional operations such as softmax that enable richer interaction between the NN and knowledge (Section 4).
Prior neuro-symbolic work has demonstrated the ability to represent predicate relations as neural networks, generally for formulas without any nested quantifiers. Full first-order logic allows arbitrary nesting of quantifiers and connectives, and allows function symbols and equality under "open world" semantics. DASL represents the first time that soundness and completeness have been established for a FOL system applied to neural networks, demonstrating that we can accommodate full first-order logic. There is also a body of work tensor representations of logic over finite domains that is focused on efficient evaluation of formulas but is not concerned with learning (Sat (2017); Nguyen al. [2018)].
Compositional DL: DASL is related to works that execute a task by composing trainable neural modules by parsing a query (in natural language) Andreas al. (2016); Yi et al. (2018a); Mao et al. (2019) Yi et al. (b)] For example, [Yi et al. (201 8b)] focuses on visual question answering and employs differentiable tree-structured logic representation, similar to DASL. However, it only does so to learn to translate questions, whereas DASL learns the semantics of the application domain and can also integrate useful domain knowledge.
Structured Learning: Other work exploits underlying structure in the data or the label space to learn DNNs using techniques such conditional random fields, graph neural networks, attention models, etc., including [Belanger et al. (2017); Kim et al. 22017); Battaglia et al. (2018) Peng et al. (2018); Zheng al. [0[5]]. These methods impose structure by either adapting the DNN architecture Battaglia et al. 2018) 8) or the loss function (Zheng et al. (201)). DASL instead imposes soft constraints by
compiling DNNs based on rules that can be stated in flexible manner using FOL.
By the semantics of a logical language we mean an interpretation of its symbols (which do not include logical connectives and quantifiers); a model in the sense of model theory [Weiss & D' D'Mello [199)]] In common with several methods [Xie et al. ), DASL grounds its entities
Semantic Reasoning:
vector spaces (embeddings) and its predicates and functions trainable modules. DASL builds on prior works on semantic representation techniques Pennington et al. (2014); Mikolov 2014):MMkkolov et al. 2013); Deerwester et al. (1990) by enabling logical statements to modify the mirror semantic similarity in the application. Another research direction
entity embeddings [Rocktäschel & Riedel 2017); Cohen et al. (2017); ): de Jong & Shal (2019)) is to structure DNNs and embedding spaces around proof trees to reduce the brittleness of theorem provers (Siekmann & Wrightson [1983].
An alternative to representing predicates by networks is restrict oneself to propositional knowledge [Xu et al. (2018) which can be applied to the outputs of a neural network. Propositional logic cannot represent the rules
Figure for example, but can be useful for placing restrictions fixed outputs.
Bayesian Belief Networks: Substitution of sscudo-probabilttie for Booleans fails to capture uncer- tainty the way fully Bayesian methods do [Jaynes (2003)]. Bayesian Belief networks [Pearl [2009)] accurately represent probabilities but lack expressivity and face computability challenges. Bayes nets most comfortably confined to propositional logic. Efforts extend them first-order logic
3

---

Under review as a conference paper at ICLR 2021
include Markov Logic Networks [Richardson & Domingos (006)], which undirected network to represent a distribution over a set of models, i.e., groundings or worlds that can interpret a theory. The lifted inference approach [Kimmig al. [2004)] reasons over populations of entities to render the grounded theory computationally tractable. These methods generally do not support the concept of (continuous) soft semanties through the use of semantic embedding spaces, DASL does, although DeepProbLog |Manhaeve et al. (2018) uses semantic embeddings and neural predicate representations within Bayesian Prolog rather than full FOL.
APPROACH
In this section we describe our approach to integrate data with relevant expert knowledge. Consider the task, depicted in Figure I] of predicting the relationship between bounding boxes containing a subject and an object. In addition to learning from labeled training samples, we want to incorporate the commonsense knowledge that if the predicted relationship is "Riding" then the subject must be able to ride, the object must be ridable, and the subject must be above the object. Incorporating such knowledge results in a more robust model that uses high-level semanties to improve generalization and learn from small number of examples. DASL achieves integration of the continuous representations in DNNs with the discrete representations typically used for knowledge representation by compiling DNN from the knowledge assertions and grounding the vocabulary of the domain in component networks, enabling gradient-basee based learning of the model parameters.
We begin by providing the theoretic underpinning of DASL in first-order logic. Full FOL with equality, as defined for example by the use of Tarski models, is more expressive than SQL, SPARQL, Datalog, Prolog, and OWI., all of which can be recognized as "fragments" of FOL.. We demonstrate here that DASL captures the full power of FOL with equality (i.e., that it reasons correctly over all assertions expressible in FOL when "=' taken to be defined as equality rather than an interpretable relation) by proving that DASL models are equivalent to Tarski models.
3.1 DASL MODEL THEORY
We follow a standard treatment of first order logic, starting with a language & consisting of variables, constants, function symbols, and relation symbols. We use standard connectives - ('not"), ), A ('and"), V ('or'), + ('implies"), ) and quantifiers A ('for all') and 3 ('there exists"). For simplicity, we assume that no variable occurs bound twice, meaning that we would always need to rewrite (Vz))((=) A (3z))/(G (x) as (Vx))p(x)) A (3)) We treat = ("equals") as a logical relation symbol. Terms are built up from variables, constants, and function symbols. Formulas are build up from terms, realtion symbols, and connectives. We restrict our attention to finite languages & and only consider finite formulas over L.
Terms and formulas provide the syntax of first order logic. The semantics for classical logic is provided by boolean Tarski models [Chang & Keisler (1973), Weiss & D Mello (199))] special case of infinite-valued Tarski models in which truth values range over the closed interval T = [0. 1] Hájekk (1998)] A Tarski model A with domain A consists of a function I which maps constants to elements of A, an n-ary function 1 A + A for each n-ary function symbol f. and an n-ary function IR A + T for each n--ry relation symbol R. We write A ( fi.......... I.m. IR............ IR.)) and |2| A. A sample finction maps variables to A; model 21 and set G of sample functions together map terms to A and formulas T, written (21, [s] and (2, [}].
I,
The logical symbols need a fixed interpretation in order to specify a full semantics. We define (21, G) - = 1 (21, G) (2l, () +) (A) G) * (A, [v]] and (3, (Vzz)) = Th 21, 6 I [x]] where 6 | u/x = (S S S(z) u). so we are interpreting universal statements as (possibly infinite) conjunctions over all possible instantiations of the bound variable. V, and 3 are defined in terms of -, A, and V. An interpretation of '=" is said to preserve equality for any terms and 8, (2I, () = s] = if and only if (21, G] = (21, (){s for every 2 and 6. interpretation, and we specify particular interpretation below. We write G* (AA for the class of all sample functions over A and 2[[{p] for (3I 6 ((2)))
For now, assume an gquaaity-preserrvee
(21, (gp) is well-defined whenever every S E G is defined over every (bound and free) variable of y and is consistent over every free variable of yp, and in particular [[{p] is well-defined if and only if y closed (meaning that every variable of &p is bound by a quantifier).
4

---

Under review as a conference paper at ICLR 2021
Proposition! 1 Let (p be a closed formula. Every infinite-vati valued Tarski model 2 such that 21[p] = 1 defines a classical boolean Tarski model of (p, and every boolean Tarski model of yp defines an infinite-valued Tarski model mapping (p 1.
This establishes that infinite-valued Tarski models fully capture the semantics of classical first order logic. While such models are not novel, their definitions vary significantly, and our use of sample functions instead of the usual variable interpretations is customized for our purposes below.
3.2 FINITARY COMPUTATION
DASL unifies machine learning and logical inference by generating infinite-valued Tarski models as described above which best fit both training data and logical formulas. A finite theory I' is represented in DASL by the conjunction of its formulas, so we can focus on operation over a single formula yp An embedding architecture is specified for the interpretation function I, and a network architecture is specified for each fr. The arithmetic semantic operators described above are applied as specified by the structure of se, composing the interpretation networks into single network, and this network is trained with target output of I.
We would like to prove that this technique completely captures full first order logic, but of course we know that some logical theories are only satisfied by infinite domains, and that all of our computation will be done over a finite number of finite samples. The constructed DASL network together with assigned parameter values specifies a unique model 21, so any optimization technique that moves from one set of parameter assignments to another defines a sequence of models 2gg A each of which evaluated over some finite set of samples, usually a mmini-batch" consisting of a relatively small subset of the domain. In order to relate this approach to infinitary models, we need to consider convergence in the limit. We begin by fixing domain A C RN for some N. If each A, is (A; Li, Li........ !m.i)) then we define lim A; = (A; lim, I,5 lim; ,s I,.))
Proposition 2 (Soundness) Let Lo..... be model sequence such that lim 24 2 and & Up G; be a sample set such that every S E G occurs in infinitely many of the G. For any formula sp, if (24, G,)(p] then (21', 6) G)(p] 1.
The above proposition assumes that all possible samples are continually revisited, but makes no other assumptions about sampling. It makes no assumptions about how we train models or whether training converges. Together with proposition]] [ this shows that when DASL models do converge on finite sampling, they converge to boolean Tarski model.
Proposition 3 (Completeness) For any boolean model 21 and formula such that [sp = 1, there is a family of finite sample sety Go. such that Uh_ G; = 6* ([al) and (21, G.)[p] = for all i.
The above proposition is proved by including in each set the sample function which contains witness for each existentially bound variable whenever one exists. Details are in section I.I This tells us that for any satisfiable formula, we can find the model that satisfies it even with only finite sampling.
3.3 IMPLEMENTING DASL NETWORKS
We implement DASL in the popular deep learning library Py (Paszke et al. (2019)] Any model that can be implemented in PyTorch can be used for the interpretation functions. We use a Py Torch dataloades to generate the mini-batches G, on which eachmodel 2, is evaluated.
Loss function. A simple and intuitive loss would be C(2 G, = (2, [)]] This loss works as desired at O and 1, but if (AI S)p] = for every S E 6 then (21, 6) (Vz){{] = I (el which has the disadvantage that loss depends the sample size and that it gets close to 1 as the sample size increases which can cause rounding errors to force a 0 gradient. Both of these challenges are addressed by using a logit representation of the truth value and using cross-entropy as loss function. For E T define logit(t) = In T and (zx) = T+e Then a (logit(t)) = t and logit(o (ont(oo(a (x) = T. The cross entropy between the distributions (t, () and (1,0) is - In)),, so when / = (2, 6) 6)[pp we ). We reason directly in logit space when computing the loss, deriving formulas from the above definitions (see (see (sbssecctn A.2 for more details).
define L(2 6,4p) = In(() In(1 + e logit()))
Equality. DASL functions can include standard regression tasks f(x) = y for realev y. This requires a differentiable interpretation that preserves equality. For (scalar-valued) terms and
5

---

Under review as a conference paper at ICLR 2021
v, we model d (2l, S)[u] (2,, G) by normal distribution with mean 0 and variance =i when equality holds and by a normal distribution with mean μ and variance E3 otherwise. We define the logit as the log ratio of the resulting densities for = |d]: logit((2l, G)lu ul)
In 252 x²
25, In(e /2/ + e /222)) For vector-valued u and we use the same distribution with ||u w|l. This interpretation approaches preserving equality E1 + 0.
Extending the logical language. We implement many- logic for convenience and efficiency. Sorts are subsets of the domain. Each quantifier ranges over a specified subset. Quantifiers can map variables to elements of tuples from enumerated sets, so a standard machine learning problem can be written as (V(z, v): Dzf y, where D lists the (z, y) training pairs.
In addition to learned models, arbitrary deterministic functions can coded in PyTorch. This allows us fix logical interpretations of <, 2, +, x, etc. We allow propositional constants (formulas of the language which are always interpreted either as or as 1) and we allow A and V to apply to arbitrary sequences of formulas. The connectives also generalize work component-wise on tensors and support broadcasting as is familiar for tensor operators in PyTorch. For example, if X is a matrix and y is vector, both of logits, then X y Z, where Zyj
Xiz A yi-
Finally, we provide an explicit operator softselect([] :) (denoted as (T')) which outputs the logit value for the jth formula of r after application of the logit version of the softmax operator. This allows us to directly specify standard architectures for multi-class classification problems and to allow rules operate on the classifier output within the model. Because is an integer argument, we can quantify over it, effectively quantifying over fixed finite list of predicates, providing syntactic convenience without violating the constraints of first order logic.
EXPERIMENTS
We evaluate DASL on two computer vision problems in conditions of data scarcity. The first task is a toy problem based on MNIST digit classification, where knowledge is provided as an arithmetic relation satisfied by unlabeled triplets of digit images that are arranged to satisfy that relation (subsection 4.1). We then focus on the problem of detecting visual relationships between object pairs and use commonsense knowledge about the plausible arguments of the relationship (subsection 4.2).
4.1 TOY EXAMPLE ON MNIST
Problem statement: We use toy example to demonstrate DASL's ability to train NN from few labeled samples and large number of unlabeled samples satisfying a rule. We denote a grayscale input image of a MNIST digit [eCun et al. 1998 X and its label (if provided) as y E Σ10, where Z.o = {0, 1,.,, 9}. The task is to learn a NN digit(X) to predict the digit in a test image.
We split the training data (50K images) into two disjoint sets: Labeled, containing small number Ner of labeled examples per digit class, and Unlabeled, used to generate the set Triples containing triplets of images (X1, Xz) satisfying the rule y(X,) + x(2))
y(X3) mod 10. Triples contains only unlabeled images that together satisfy this relationship. We wish to learn the classifier by using Labeled and Triples, and thus the challenge is to compensate for the small size of Labeled by leveraging the prior knowledge about how the unlabeled images in Triples are related. We formulate this problem within DASL by using its softselect operator n. that, applied to the NN output digit( X), returns the normalized score for the 7th class. This rule is written as:
(V(X,, X2, X²): Triples)(Vy) Zio) Zio)
[TTT (iigit(X))) A y (digit (X²)))
(g w2) mod io(digi((X.,
We quantify over the triplets from Triples and all possible pairs of digits from Zio. We use this theory to augment the theory corresponding to the labeled training examples (V(X) The model is required to correctly infer the (unknown) labels of the triplet members and then use them for indirect supervision. We evaluate the model using the average accuracy on the test set (10K images). For digit(X), we used a two-layer perceptron with 512 hidden units and a sigmoid non-linearity. We performed experiments in data scarce settings
Labeled) (reeled)(Ty(xe (digit((X))

---

Under review as a conference paper at ICLR 2021
with Nrr = 2, 5, 10. and 20, and report mean performance with standard deviation across 5 random training subsets as shown in/Figure 2| We use an equal number of examples per-class for constructing the triplets. We
curriculum based training strategy to prevent the model from collapsing to degenerate solution, especially for lower values of Ntr (see seelsuusection A.4 for details). We report performance after 30K training iterations. A test image is classified into the maximum scoring class.
Toy Example MNIST
100
90
Accuracy on Test Set
no-kknoledgge (Nv = all)
80
No-knowledge (N, = 20)
No- kn-klowweegge (Nu: 10)
No-knowledge (Nr = 5)
70
No-knowledge (N, = 2)
With-kriowledge (N,, 20)
With-knowledge (Mr 10)
with-knowwedge (Nr 5)
With-knowledge (Nr 2)
10a
10a
10a
# of samples per class used for creating (unlabeled) knowledge triplets (log-scale)
Figure 2: Figure showing the results for the MNIST toy example with plot of accuracy of digit classification versus number of samples per class used for creating the unlabeled knowledge triplets. The labels With-knowledge and No-knowledge denote whether the training included the goowledge-augmentt the given modular arithmetic isce/subscction 4.1). Ne. refers to the number of labeled training examples per class (all refers to the entire training set). Best seen in color.
unlabeled triplets satisfying
Results: Figure 2 shows plot of digit classification accuracy versus the number of samples per class used for creating the triplets. We observe that the NN trained with both knowledge and data (With-knowledge)) outperforms its counterpart trained with only labeled samples (No-knowledge). The improvement is particularly notable when training with smaller labeled training sets; e.g., for Ntr = using all the knowledge raises performance from 53.3 + 1.01 97.7 + 0.00. We also note that the performance of the With-knowledge model improves as the number of triplets increases and converges similar values for different values of Ntr. indicating that the knowledge renders extra labels largely superfluous. The mean performance is 97.6 + 0.00, which is competitive with the performance of model trained with all 50K labeled examples in MNIST (98.1 for N all). Results on related problem were also shown in [Manhaeve et al. (2018)).
4.2 VISUAL RELATIONSHIP DETECTION
We use the Visual Relationship Detection (VRD) benchmark [Lu et [ to evaluate the Predicate Detection Task: Given an image and set of bounding boxes with object category labels, predict the predicates that describe the relationships within object pairs. The VRD dataset contains 5000 images spanning 37993 relationships covering 100 object classes and 70 predicate classes. We use splits provided by the authors that contain 4000 train and 1000 test images. The dataset also provides zero-shot test subset of 1877 relationships built from the same classes as the training data but containing novel combinations of predicate classes with object class pairs.
Problem Statement:
We begin with NN vrd I, o) that outputs raw scores for predicate classes, where is the input RGB image and s and o are the indices the subject and object classes respectively. We implement two variants of vrd similar to that proposed in [Liang et al. (0018)). The first variant, referred to as VGG, extracts visual features from the last layer pre-trained VGG- 16 network from the bounding box of the subject, the object, and their union. These features are projected into 256 dimensional space by using a projection layer P (made a fully-connected (FC) layer and a ReLU non-linearity) and then fused by concatenation. The features are passed through another P layer
Baseline model:
7

---

Under review as a conference paper at ICLR 2021
followed by FC layer to predict the class-wise scores. The second variant, referred to VGG-SS, additionally incorporates the borddembeddingg features of the subject and the object (300 dimensional Glove features [Pennington et al. (2014)) along with the normalized relative spatial coordinates (see subbeetion A.5 for details). These features are first projected using additional P layers and then concatenated with visual features, as done for VGG, prior to predicting the clors.scores.
We express knowledge as vectors of formulas as discussed in subsection 3.3 We begin by defining CanRide as constant vector of truth values for all objects which is True indices of objects which can ride and False elsewhere. CanRide(s) (8) selects its 9th element. Similarly, we define Ridable as a vector which is True at exactly the indices of objects that can be ridden. Finally we define a one-hot vector of truth values hcls E RTD, which is True at the index of the predicate class "Cls" and False elsewhere. The theory that asserts that vrd should output the class labels assigned in the training data and that the "Riding" predicate should only apply when the subject can ride and the object can be ridden written as:
(A(I, 8, 0, (vra( ,8, 88
Ridding + CanRido(s)
A Ridable(o)))
where y is the given training label and Dura is the training dataset. This rule reduces the learning burden the classifier for "Riding" class by allowing feedback only when CanRide(s)) is True. We introduce a few more rules by adding them in conjunction with the above rules (see subsection A.6).
Evaluation: We follow Yu et al. (2017], reporting Recall @N (R@N), the recall of the top-N prediction scores in an image where we take into account all 70 predictions per object pair. This strategy different from [Lu et al. (2016 which only considers the top prediction for each object pair penalizing cases where multiple predicates apply equally well but were omitted by the annotators.
Method
R 50
R@ 100
Standard
Zero-Shot
Standard
Zero-Shol
1% Data
VGG (baseline)
60.8 6.7
40.7 5.8
75.4 + 7.8
59.4 8.1
+ Knowledge
68.5 1.8**
49.5 - 1.5*
83.1 1.6**
70.1 + 2.4
VGG-SS (bascline)
67.9 = 8.5
47.6 = 8.5
80.3 + 7.6
65.6 9.2
+ Knowledge
74.0 0.7*
54.4 + 1.4*
85.9 + 0.5*
73.4 1.2
5% Data
VGG (baseline)
70.3 1 0.5
48.4 = 1.0
83.5 1 0.4
68.3 + 0.9
+ Knowledge
73.8 0.5**
53.4 + 0.9
86.4 0.4
73.7 + 1.1
VGG-SS (baselinc)
79.6 + 0.4
58.1 = 1.2
89.6 + 0.3
77.1 + 1.1
+ Knowledge
79.9 = 0.4
59.6 + 0.9**
89.7 + 0.3
78.5 + 0.8
Table 1: Performance on the predicate detection task (Lu et al. (. We report Recall@N N averaged (with standard deviation) across 10 random subsets. We report the statistical significance between "baseline" and corresponding knowledge augmented model ("+ Knowledge") (p-value < 0.01 as and p-value < 0.05 +).
Results: Table I shows the results on the VRD dataset when training with knowledge (+ Knowledge) and without knowledge (baseline). We observe consistent improvements across all cases with augmentation of knowledge. The improvements are higher for the 1% data (+7.7% for R @ 100 for Standard) than the 5% data (+2.9% for R@ 100 for Standard) showing that knowledge has more benefits in lower data regimes. We made similar observation for the MNIST toy example. The improvements are generally higher for the zero-shot setting (+ (+1 for @ 100 the 1% case) since this setting is inherently data starved. We also note that the improvements are comparatively smaller for the VGG-SS network since semantic and spatial information are being explicitly injected as features into the model. We provide class-wise performance for few predicates in subsection A.8 We observe consistent improvement for predicates such as "Wear" and "Above" that were specified in the rules.
4.3 COMPARISON WITH RELATED SYMBOLCC METHODS
We empirically verified the advantage of the logit representation over two related methods (Serafini & Garcez (2016): Demeester et al. (2016)), both of which use product-t norms but represent the
8

---

Under review as a conference paper at ICLR 2021
final truth values using either probabilities log probabilities. We evaluated these methods on the task of learning a digit classifier through two variants of logical conjunctions that make assertions about images and their ground-truth labels. Both of these these techniques fail catastrophically when the numher of conjuncts (see Figure 3) is increased. In contrast, DASL, did not see any loss in performance, highlighting its better numerical stability. We refer readers to subsection A.7 for details.
We also compare our model with a recent neuro- weuro-symbollic method [Xie et al. (2019)] that uses graph neural networks with propositional formulas semantically regularize output embeddings for VRD. We observe clear improvements in the top-5 accuracy metric used in their work under similar training conditions. With 5% data, our model ("VGG-SS + Knowledge") achieves 77.7% accuracy versus 72.4% of [Xie et al. [2019]]. The improvements are higher for 1% data- 71.5% accuracy of ours versus 55.5% of [Xie et al. (2019)] highlighting the advantages of DASL, with small amount of training data. We refer readers to subsection A.8 for details.
5 CONCLUSION
We introduced Deep Adaptive Semantic Logic (DASL) to unify machine reasoning and machine learning. DASL is fully general, encompassing all of first order logic and arbitrary deep learning architectures. It improves deep learning by supplementing training data with declarative knowledge expressed in first order logic. The vocabulary of the domain is realized as a collection of neural networks. DASL composes these networks into single DNN and applies backpropagation both data and knowledge. We provided formal grounding that demonstrates the correctness and full generality of DASL for the representation of declarative knowledge in first order logie, including correctness of mini-batch sampling for arbitrary domains. This gives us the freedom to apply DASL to new domains without requiring new correctness analysis.
satisfy
We demonstrated a 1000-fold reduction in data requirements on the artificially constructed MNIST digit classification task by using declarative knowledge in the form of arithmetic relations satisfied by unlabeled image triplets. We then demonstrated the application of commonsense knowledge to visual relationship detection, improving recall from 59.4% to 70.1 1%. Here, the commonsense knowledge enabled us to better focus the model on cases not covered by knowledge.
REFERENCES
Somak Aditya, Yezhou Yang. Chitta Baral, and Yiannis Aloimonos. Combining knowledge and reasoning through probabilistic soft logic for image puzzle solving. In UAI, pp. 238-248, 2018.
Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Neural module networks. In CVPR, pp. 48. IEEE Computer Society, 2016. ISBN 978-1-4673-8851-11
Peter W Battaglia, Jessica B Hamrick, Victor Bapst. Alvaro Sunchez-Gonzaler Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: 1806.0/261, 2018.
David Belanger, Bishan Yang, and Andrew McCallum. End-to-end learning for structured prediction energy networks. In ICMI., pp. 429-439 JMLR. org, 2017.
Chen Chung Chang and H Jerome Keisler. Model theory. Elsevier, 1973.
William W Cohen, Fan Yang. and Kathryn Rivard Mazaitis. Tensorlog: Deep learning meets
probabilistic dbs. arXiv preprint arXiv: 05399, 2017.
Michiel de Jong and Fei Sha. Neural theorem provers do not learn rules without exploration. arXiv preprint /906 1906.06805, 2019.
S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis. Journal of American Society for Information Science, 41:391-407. 1990.
Thomas Demeester, Tim Rocktäschel, and Sebastian Riedel. Lifted rule injection for relation embeddings. In EMNLP, 2016.

---

Under review as a conference paper at ICLR 2021
Marcin Detyniecki. Fundamentals aggregation operators. Technical report, University of California, Berkeley, 2001.
Artur S d' Avila Garcez, Krysia B Broda, and Dov M Gabbay. Neural-symbolic learning systems: foundations and applications. Springer Science & Business Media, 2012.
Artur S. d' Avila Garcez, Marco Gori, Luís C. Lamb, Luciano Serafini, Michael Spranger, and Son N. Tran. Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning. Human Level Artificial Intelligence, 1:1-10, 2019.
M. R. Genesereth and J. Nilsson. Logical Foundations of Artificial Intelligence. Morgan Kaufmann, San Mateo, CA, 1987.
Francesco Giannini, Giuseppe Marra, Michelangelo Diligenti, Marco Maggini, and Marco Gori. On the relation between loss functions and t-norms. arXiv preprint wxXiv:907.00704, 2019.
Hájek. Metamathematics of Fuzzy Logic. Trends in Logic. Springer Netherlands, 1998. ISBN 9781402003707.
Zhiting Hu, Xuezhe Ma. Zhengzhong Liu, Eduard Hovy, and Eric Xing. Harnessing deep neural networks with logic rules. arXiv preprint 1603.066,, 2016.
E. T. Jaynes. Probability theory: The logic of science. Cambridge University Press, Cambridge, 2003.
Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. Structured attention networks. arXiv preprint arXiv: 700777000.08..... 2017.
Angelika Kimmig, Lilyana Mihalkova, and Lise Getoor. Lifted graphical models: survey, Machine Learning, 99:1-45, 2004.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.6988 2014.
Ranjay Krishna, Yuke Zhu, Oliver Groth, Justin Johnson, Kenji Hata, Joshua Kravitz, Stephanie Chen, Yannis Kalantidis, Li-Jia Li, David Shamma, et al. Visual genome: Connecting language and vision using crowdsourced dense image annotations. IJCV, 123(1):32-77) 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. traddeet-based learning applied to document recognition. Proceedings of the IEEE, (6(11):2278-23222 1998.
Yann LeCun, Yoshua Bengio, and Geoffrey Hinton. Deep learning. nature, 521 (2553)))433 2015.
Tao Li and Vivek Srikumar. Augmenting neural networks with first-order logic. arXiv preprint arXiv:1906.06298, 2019.
Kongming Liang, Yuhong Guo, Hong Chang, and Xilin Chen. Visual relationship detection with deep structural ranking. In AAAI, 2018.
Cewu Lu, Ranjay Krishna, Michael Bernstein, and Li Fei-Fei. Visual relationship detection with language priors. In ECCV, pp. 852-869. Springer, 2016.
Robin Manhaeve, Sebastijan Dumancic, Angelika Kimming, Tomas Demeester, and Luc DeRaedt. Deepproblog: Neural probabilistic logic programming. In NeurIPS 2018, 2018
Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. The neuro- symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision. In ICLR. OpenReview.net, 2019.
Gary Mareus. Deep learning: A critical appraisal. arXiv preprint arXiv:1801.0060 2018.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger (eds.), NIPS, pp. 311-3119 Curran Associates, Inc., 2013.
10

---

Under review as a conference paper at ICLR 2021
Dan Moldovan and Vasile Rus. Logic form transformation of wordnet and its applicability to question answering. In ACL, pp. 402 409, 2001.
Hien D. Nguyen, Chiaki Sakama, Taisuke Sato, and Katsumi Inoue. Computing logic programming semantics linear algebra. Lecture Notes Artificial Intelligence //48.. 2th International Conference Multi-disciplinary Trends in Artificial Intelligence (MIWAI 2018), Springer, 2018.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. NIPS, pp. 8024-8035, 2019.
Judea Pearl. Probabilistic reasoning in intelligent systems networks of plausible inference. Morgan Kaufmann, San Francisco, Calif., 2009. ISBN 9781538604797 1558604790.
Hao Peng, Sam Thomson, and Noah A Smith. Backpropagating through structured argmax using spigot. arXiv preprint a 040504468, 2018.
Jeffrey Pennington, Richard Socher, and Christopher D. Manning. Glove: Global vectors for word representation. In EMNLP. pp. 1532-1543, 2014.
Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62(1-2): 107-136, 2006. ISSN 0885-6125. doi: 10.10077/109944-06--8333---
Tim Rocktäschel and Sebastian Riedel. End-to-end differentiable proving. I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), NIPS, pp. Curran Associates, Inc., 2017.
Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge into embeddings for relation extraction. In ICML, pp. 1119-1129, 2015.
Taisuke Sato. Embedding tarskian semantics in vector spaces. In AAAI-17 Workshop on Symbolic Inference and Optimization, 2017.
Luciano Serafini and Artur S. d' Avila Garcez. Logic tensor networks: Deep learning and logical reasoning from data and knowledge. CoRR, abs/1 04422, 2016.
Jörg Sickmann and G. Wrightson. Automation of Reasoning. Springer, 1983.
Geoffrey G Towell and Jude W Shavlik. Knowledge-based artificial neural networks. Artificial 19-165, intelligence, 19--15) 1994.
Karl Weiss, Taghi M Khoshgoftaar, and DingDing Wang. A survey of transfer learning. Journal of Big data, 3(1):9, 2016.
William Weiss and Cherie D'Mello. Fundamentals of model theory, 1997.
Yaqi Xie, Ziwei Xu, Kuldeep Meel, Mohan Kankanhalli, and Harold Soh. Cemantically-regularia logic graph embeddings. CoRR, abs/1909.0116/ 161, 2019.
Jingyi Xu, Zilu Zhang, Tal Friedman, Yitao Liang, and Guy Van den Broeck. semantic loss function for deep learning with symbolic knowledge. In ICML, 2018.
Fan Yang, Zhilin Yang, and William W Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NIPS, pp. 2319-2328, 2017.
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. Neural- symbolic vqa: Disentangling reasoning from vision and language understanding. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), NIPS, pp. 1039-1050, 2018a.
Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum. Neural- symbolic vqa: Disentangling reasoning from vision and language understanding. In NIPS, pp. 1031-1042, 2018b.
11

---

Under review as a conference paper at ICLR 2021
Ruichi Yu, Ang Li, Vlad I Morariu, and Larry S Davis. Visual relationship detection with internal and external linguistic knowledge distillation. In CVPR, pp. 1974-1982, 2017.
Shuai Zheng, Sadeep Jayasumana, Bernardino Romera-Paredes. Vibhav Vineet, Zhizhong Su, Dalong Du, Chang Huang, and Philip HS Torr. Conditional random fields as recurrent neural networks. In ICCV, pp. 1529-1537, 2015.
12

---

I(a) Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 FORMAL SEMANTICS FOR DASL
A.1.1 SAMPLE FUNCTIONS
We assume the definitions provided in Section 3 and make explicit some of the details of sample functions. We fix the set V {.1....) be the set variables, independent of any language Fix language & with constants C1, function symbols f1.... with arities n....... and relation
symbols Ri.... with arities ......... Let be the model (,........RR........
A sample function for 2 is function S V + A. For Vo C V we say that sample functions Si and S2 are consistent over Vo (1) S2(v) for every v E Vo- We say that set G of sample functions is consistent over Vo if every pair of sample functions in 6 is consistent over Vo. For any term or formula & we say G is consistent for & if G consistent over the set of free variables of ø.
Let St.... be any terms of & and G be arbitrary set of sample functions for 2. We define for every
(3, (x,
S(x;) for S E G if G consistent for {
(2l. [a]
(3L, (
((, (2I, (5(,,,))
Under this definition, the pair (RI, G) maps every term of & to member of A (recalling from section 3.1 that maps constants to A) whenever & is consistent for the term. The map is undefined when & is not consistent for the term. It can be seen by recursion the definition that whenever G is consistent for the term on the left-hand side of any of the above equations, it is also consistent for all terms on that equation's 's right-hand side. It can also be seen that for any term 8, (21, [+})[s) (2I, (){ for every S E whenever G is consistent for s.
For brevity of presentation, we define:
5 V vb -(pp -p)
Φ + = -(p A mp)
(Br) (Vx)
We extend (2I, G) also map formulas truth values. Since A is boolean, the interpretation of = needs to always evaluate to or 1. There is only one such interpretation that preserves equality. Define:
(2), (R ,., 8ng,)
((1, 6)(s)) (2, ()
{
1 if (2, 6)[s] (21, G)
(8, 6) = s2]
0 otherwise
(8) 64
1 ((2), ()()
(2I 6) (21, G)
II ( 6 [//)|pp
The application of (21, G) to formulas depends on its application to terms, and therefore is still only well-defined if G consistent for the formula to which applied. As above, we can see by recursion that whenever G is consistent for the left-hand side of any equation other than the last (the equation) it consistent all formulas on the right-hand side of that equation. For Y we note that when G is consistent for (Vir)<)) then it is consistent for all free variables of other than z. G' 6 | u/v a subset of G, so it must also consistent for all free variables of yp other than x. By definition, for every S E G', S(z) u. G' is consistent for x as well and therefore is consistent for yo. Thus, the Y clause of the above definition decomposes the set G of sample functions into a class of sets of sample functions, each consistent for y,, and then conjoins the results of applying each to ip. This particular technique is convenient because it allows us to specify sampling algorithms formally for implementation.
13

---

Under review as a conference paper at ICLR 2021
The intent of the interpretation of V above is that we applying all of the sample functions in G but in general there could be some u E A for which & does not contain any sample function that maps a' to u, with the result that some of the terms the right hand side become (a), [sp,,,, which is undefined. In principle this could be resolved by taking the product over {u S(x) = u for some S E G), but instead define (RI, [ppp 1 for all yp just for notational convenience.
A.1.2 FINITE SAMPLES
We will describe construction of finite sample sets that allow for complete search of the infinite model domain, proving proposition 3 from Section 3 in the main text. For an arbitrary set G of sample functions, if F {6;
I} is family of finite sets and User G & then F called finite decomposition G. Given a model 21 and formula yp, we say that F preserves truth for A and yp (21, [pp (21, S [pp for every i. If G; is consistent for set V of variables for every i then say that F is consistent for V.
We prove generalization of proposition 3:
Proposition 4 Let 21 be a boolean model, A | y be formula, and 6 = (S; i I} be a set of sample functions consistent for ip for some infinite index set I. Assume |G| |A]. Then there is finite decomposition {6; i E I} of G that preserves truth for ip and is consistent for ip
Note that (A)] = ||, so the assumption on the size of the sample set is natural one and is met by proposition 3. To prove this claim we first note that whenever G, S G and G is consistent for then Go is consistent for yp, so every finite decomposition of will be consistent for sp. We proceed by induction on the structure of yp
Suppose yp R($1....,.. or $1 82. Choose any G.
(21, [R)) 8a)l = IR((21, (S))[=)),....... (21, (s))
IR((I) [1]) (2, (s.))
= (2), [8)]
Similarly, (3l [8) =2] = if and only if (3, (S)) = (M, [S)) which holds if and only if (21, 6) $1 = (21, {2] Thus in both cases [(S} S E G is a finite decomposition of 6 that preserves truth for yp.
Suppose & is -t. Let = (2, 6][b). so (21 G) F (G, i E Z) be truth-preserving finite decomposition of G for vb
t. By the induction hypothesis let
(21, [b) = 1 - (21, (v)
1 - (2, [v]
(21, (-/)
Thus F also preserves truth for -a6
Suppose to is vh A th2. By the induction hypothesis, let (6) E I) and (G? E Σ} be finite decompositions of G that preserve truth for 1i and 4/2, respectively. For each i.j E I define:
Gi, (S) S2
Si E G G3)
where we define
(x) S otherwise
if is bound in 1/2
(S, o 02)
Recall that all bound variables have been renamed to be distinct from each other and from all free variables. For each and j. Gt, and 6 are identical over all free and bound variables 1/1, since
none of these is bound in 2/2- Thus (vb) = (21, (1) = (21, () Similarly, G2 is
identical to 63 over all free and bound variables of 2/2. so (2I, G. [v2) (3, [ (3, [))] Thus
(21, G Vol
(2I, 141 (a.
[v))
(2), () (M, [v
=
(21, () A Ax)
14

---

Under review as a conference paper at ICLR 2021
To that {G.,) i.j I) is finite decomposition of 6, let arbitrary S 6 be given. Choose i and such that S E ; and S E 63. Then Gt,j contains 8 o S, which is S. Re-indexing the family requires mapping I to I, which is non-problematic since I is infinite.
Suppose @ is (Vx))s. Let L (2l, (V and Ly (21, G u/>)(vb for each E A. By the induction hypothesis, for each u E A let {6) i I} be a finite decomposition of | u/r that preserves truth for 2 and d. Note that G [ uur G if
and is {} otherwise, and recall that (21, [1xx for every formula x by definition, so IL (2), G u/z)(xl = (21, 6,]
If f then to for every
(2). (v)))))
= II (2l S [
(21. M
(21, w/
Thus F- { iie I, A} is finite decomposition of G that preserves truth for sp. Since A & |4, F 11 so F can be re-indexed in I.
If t 0, then since boolean, choose such that t. 0. For define G. G UG! As above, note that 6 uu/ is G if a is or w and is { otherwise.
(L) (( = II (2, G. [//)
(21, 6 (21, 6
(21, w/z) (21, 6 [p
Thus {6, i I, v E A] is finite decomposition of C that preserves truth for s.
This shows that proposition 4 holds for every case of sp, and by induction that it holds for all Proposition 3 of Section is direct consequence.
A.2 DASL MODELS AS NEURAL NETWORKS
For truth values t and to and corresponding logits 4 and lz, we define negation (-) and conjunction (A) operators as:
-4 = =logit(1 (1- - 41) = -11
4 A (ttt) lno lno((2) In(1 (11)((22)
This formula for A is numerically unstable when ta gets close to 1. Whenever this occurs, instead use the numerically stable approximation:
4 A4 - In(e + tl))
We use PyTorch functions logs i gmo i d and logsumexp that provide efficient and numerically robust computations for terms arising in these equations.
Conjunction and universal quantification are naturally represented as products of truth values, but the product of a large number of positive terms all less than 1 gets arbitrarily close to 0, and so does its derivative, meaning that learning is slow or will stop altogether. Under the logit space equations above, however, conjunctions are sums, so increasing the number of conjuncts does not diminish the gradient. Two typical alternatives for t A to in systems that operate directly on truth values are min(t,, t²) and max(0, f1 + t2 1) [Serafini & Garcez (2016)]. When many terms conjoined, the former formula yields gradient information only for the minimal truth value, and the second yields gradient information all whenever 4 + < 1, again restricting the ability of system to learn.
15

---

Under review as a conference paper at ICLR 2021
A.3 DETAILS REGARDING TRAINING FOR MNIST TOY EXAMPLE AND VISUAL RELATIONSHIP DETECTION
For both problems we trained the model with the Adan optimizer [Kingma & Ba (2014)) with learning rate of 5 x 10 The batch size was set to 64 and 128 for the MNIST toy problem and visual relationship detection respectively.
A.4 CURRICULUM LEARNING FOR MNIST TOY EXAMPLE
In Snssubscttonn 4.1 we trained a NN for digit classification on the MNIST dataset conditions of data scarcity. We used a few labeled samples and large number of unlabeled triplets satisfying some rules (modular arithmetic in our experiments). We used a curriculum based learning strategy to prevent the model from collapsing a degenerate solution, especially for cases with extremely small number of labeled samples (e.g. 2 samples per class). In such cases the model tends to get trapped in a local minimum where the axiom corresponding to the unlabeled triplets can be satisfied by solution with all digits being classified as O since 0 + 0 = O. Within the curriculum, we begin the training with all the labeled examples and small working set of the unlabeled triplets. We progressively expand the working set during training as the model becomes more confident on the unlabeled examples. The confidence score pt computed using low-pass filter:
-1- (111-0 a) * Pe + a * Pmaz
where is scalar multiplication, t is the iteration index. p. 0. a = 0.1, and Pmace the average probability of the highest scoring class on the first digit of the triplet. When p': > 0.9, we increase the size of the working set of unlabeled triplets by factor of until reaches the maximum number of unlabeled triplets. When p > 0.9, we reset p'. to 0 to let the model fit well to the new working set before reaching the condition again. This curriculum ensures that the model able to find decent initialization using the labeled examples and then progressively improve using the unlabeled samples. The initial set of unlabeled triplets contained 10 samples per class and the maximum number of triplets is bounded by the class with minimum number of samples. During the final curriculum step we remove all labeled data, allowing the model to train solely on the rules. This allows the model to trade off errors on the labeled data for better overall performance.
A.5 NORMALIZED RELATIVE SPATIAL FEATURES FOR VISUAL RELATIONSHIP DETECTION
We provide the implementation details for the spatial features used in the visual relationship detection experiments in subsection 4.2) These features capture the relative spatial configuration of the subject and the object bounding boxes and were used augment visual and semantic features for predicting the visual relationship (VGG-SS), We denote the coordinates of the object and subject bounding boxes as (I.: Us, w.. w,,h,) h2) and (Io. yo: Wo; he) respectively, where (Ir, y) are the coordinates of the (box) center with width and height h. The relative normalized features are captured in an eight dimen-
sional feature vector defined as
=._ Vo-9o Za No-2. loog( w. ), log( h. h. ), log( w. log( (i
No
h.
These features were also used in the baseline model [Liang al. (018)).
A.6 COMMONSENSE RULES FOR VISUAL RELATIONSHIP DETECTION
In addition to the rule for the "Riding" predicate described in subsection 4.2 we used rules for incorporating commonsense knowledge about number of the other predicates in predicting visual relationships using DASL. These rules follow the same format as the rule for "Riding" and are outlined below:
1. "Wear" only applies when the subject is a living entity and the object is wearable.
2. "Sleep-On" only applies when the subject is living entity and the object is sleepable.
3. "Eat" only applies when the object is eatable.
4. The predicates "A "Above", "Over", "Ride". "On-The- Top-Of", On", "Sit-On", and "Rest-On" apply only when the subject is spatially above the object. We defined above as function that is True when ys 2 yo-
TOn-The-Top-Or "Drive-on", "Park-On "Stand-
16

---

Under review as a conference paper at ICLR 2021
5. The predicates "Under". "Beneath". "Below", and "Sit-Under" apply only when the subject is spatially below the object. We defined below as a function that is True when ys S Yoo
6. The predicate Don-The-Righhe object. We defined right of as a function that is True when 2, Zo.
applies only when the subject is spatially right of the
7. The predicate "On-The-Lefte The-hhe-effOOf applies only when the subject is spatially left of the object. We defined left of as a function that is True when Ta S To.
These rules cover facts related to both semantic and spatial commonsense knowledge. We incorporated these rules by conjoining them with the implication in the original theory presented in subsection 4.2
(A s, o, y) D (vra)
A (hRuding + CanRide(s)
Ridable(o))
A (hWear + Living(s) Wcarable(o))...)
where hCls E I is a one-hot vector of truth values, which is True at the index of the predicate class "CIs" and False elsewhere. Living is constant vector of truth values for all objects which is True at indices of objects which are living entities and False elsewhere. Similarly, Wearable is a constant vector, which is True at exactly the indices of objects which are wearable. We refer readers to colsubsection 4.2 for detailed explanation about the application of these rules.
We would like to note two approaches for building such knowledge bases. The first method is manual method where a user can supply logical rules that are focused on classes where the model does not work well. The second method to exploit knowledge bases such as Concept-Net, WordNet or meta-data of prior datasets such as Visual Genome [Krishna et al. (2017)) For VRD, we started with Visual Genome to build our knowledge base and then kept subset of rules which we found to be most helpful. While building these rules we found it helpful to group the predicates in a rule set. For example, predicates such as "Above" and "Over" were part of the "Above" rule set (number in the list of rules) which verified whether the subject is above the object. We understand the general concern regarding the feasibility of constructing a knowledge base but in our view there is sufficient work in the literature showing how machine learning algorithms have exploited knowledge bases from pre-existing resources [Aditya et al. (2018): Moldovan & Rus (2001)).
A.7 EMPIRICAL COMPARISON WITH RELATED WORKS
Here we compare DASL to two closely related neuro-symbolic based methods: Logic Tensor Networks (LTN) (Serafini & Garcez [0166] and Rocktäschel et al. [Demeester et al. (2016)). Both use product t-norm for the conjunction operator on truth values and cross-entropy for the loss function, as does DASL. These operations are carried out directly in LTN, in log space in Rocktäschel et al., and in logit space in DASL. Operating directly on the raw truth values suffers from vanishing gradients because the product of many values between 0 and 1 approaches O. Operating on logs of truth values maintains precision near 0 but not near 1. The negation of conjunction has loss log(1 - II, [A.)), which again has vanishing gradient as the number of terms increases. DASL's logit transform maintains precision near both 0 and 1, enabling DASL to represent full FOL (in this case, including the negations of conjunctions) at scale. To verify these claims, we train the classification NN in subsection 4.1 on MNIST digits using two variants of logical conjunctions. The first variant trains the NN using a conjunction of multiple assertions about MNIST digits and their labels, i.e., (4(X,)) y) Labeled)( x (digit(X))) The second variant trains the NN using negation of conjunction for the same problem -(-(V(X, v) (abeled)(z,xxx (digit(X)) ()))). For a fair comparison we implement both the LTN and Rocktäschel et al. representations within the DASL's code by replacing DASL's logit space computations with truth value computations with probabilities and log- prgbbabbbillssess respectively for learning. To understand the sensitivity of different representations to the size of conjunction (batch-size in this case), we plot accuracies on the test-set against different batch-sizes in Figure 3, We see that the performance of LTN drops quickly as the number of assertions is increased for both variants since the raw representation fails to preserve
17

---

Under review as a conference paper at ICLR 2021
Rocktäschel et al.
LTN
DASL
1000
100
Conjuction
Negated Conjunction
80
80
80
60
60
60
Accurary
Accuracy
20
20
20
Conjuction
-+
Conjuction
Brggated-Cojjuncee
Negated-Corgunctte
25
50
75
100
125
25
50
75
100
125
25
50
75
100
125
Batch-size (No. conjuncts)
Batchisize (No. of conjuncts)
sizch (No. conjuncts)
Figure 3: Comparison of DASL with LTN [Garcez al. 2019 and Rocktäschel al. [emeester al 20166] for training a classify MNIST digits with conjunctions and negated conjunctions over training samples. We observe that the performance of prior methods saturate when increasing the number of terms in conjunction. However, this is not the case with DASL due to its logit representation, which prevents vamishing gradients and thus enables improved learning.
gradients. Rocktäschel et al. performs similar DASL for regular conjunction due the use of log truth values. However, when training with negated conjunctions. the converged Rocktäschel et al. model fails catastrophically for number of conjuncts 16. The DASL model shows no loss in performance, highlighting better numerical stability. This example highlights the improved numerical stability enabled by DASL which critical for scaling, especially when learning NN with deeper logical structures.
A.8 ADDITIONAL EXPERIMENTAL RESULTS FOR VISUAL RELATIONSHIP DETECTION
1% Data
5 % Data
Predicate
Baseline
Knowledge
Baseline
+ Knowledge
Wear (R)
0.90
1.00
0.86
1.00
Under (R)
0.02
0.38
0.25
0.49
Above (R)
0.30
0.37
0.44
0.58
On
0.63
0.80
0.71
0.77
Has
0.10
0.07
0.18
0.14
Next To
0.15
0.06
0.16
0.15
Table 2: Shows class-wise results (Top-1 accuracy) for top performing predicates from the predicate detection task. "Bascline" refers VGG (bascline) and "+ Knowledge" refers the knowledge augmented model (sec Table Tp. (R) means that the predicate was included in one of rules.
Class-wise performance: To provide further insights into VRD, we also report class-wise compar- ison (Top-1 accuracy) with and without knowledge in Table 2 We see consistent improvements for predicates which were included in one of the rules, e.g., "Wear" and "Under".. Interestingly, we also see improvements for the "On" predicate since has the most training samples and thus the baseline tends to confuse other predicates with "On" (common overfitting issue in DNNs). In such low-data regimes DASL improves performance for "On" by being able to correctly predict related predicates such as "Under" and "Above". We observe some loss in performance for predicates such as "Has" since these are hard to detect and we did not use any rules for them. We also conducted simple ablation study by removing all the spatial rules (with VGG-SS Knowledge) to their impact on performance. We observe a drop in performance for 1% training data (R@ 100=81.8, R @ 100-SS666.8 with all rules versus (R @ 100=75.3, R 100-7S=58.7 78 w/o spatial rules).
18

---

Under review as a conference paper at ICLR 2021
% Data
DASL
Xie et al. (2019)
Only Positive Relations
Additional
DASL
Negative Relations
1 1%
71.5
55.5
71.0
5%
77.7
72.4
77.6
Tahle 3: Comparison on Visual Relationship Detection with a recent neuro-symholic based method [Xie et al. (2019)]. We report Top-5 accuracy metric for comparison with their work. Here DASL refers to knowledge augmented model "VGG-SS Knowledge". We show results with [Xie et al. [2019] as using both positive and negative object pairs for training. In comparison DASL only uses positive object pairs training.
We would also like to note that the first-order constraints were always satisfied for VRD since we applied rules as vectors formulas as discussed subsection 3.3] Here the formulas are applied directly in conjunction with the output of the VRD and thus by definition the rules are always satisfied. We note that this is different from how the rules were satisfied for MNIST and is made possible by the ability of DASL to extend logical language by allowing formulas to work on output tensors.
Comparison with Xie et al. (2019)] Here we compare DASL with a recent neuro-symbolic method Xie et al. [2019)] on the VRD task. This work proposed a graph embedding network that is able to learn semantically weatticallycoonstraaet constraiied embeddings using propositional formulas and reported improvements on the VRD. The numbers reported in this work are not directly comparable to ours since they used 100% training data, while we use only 1% and 5% training data. Moreover, they reported performance on both positive pairs and negative object pairs (negative pairs are labeled with extra "no-relation" class). This experimental protocol is different from that commonly used the in literature [Lu al. (016)) (also used our work), which only evaluates on positive pairs. The number of object pairs with negative relationships is quite high (86% of total boxes), which results in higher chance performance leading to higher gains on their test set. For fair comparison we re-trained their model with 1% and 5% data and report Top-5 accuracy positive object pairs, as done in the literature, in Table 3
We use the variant "VGG-SS + Knowledge" for comparison since [Xie et al. (2019) also uses embedding vectors and bounding box coordinates in their model. We see consistent improvements with DASL with the improvements being higher for the 1% case compared to the 5% case. We also note that [Xie et al. (2019)) uses many more rules (e.g., using 10 spatial relations compared to our 4) than DASL, which gives them certain advantage. That is because as we showed earlier the performance in 1% data case substantially falls when the spatial rules were removed (R@) 100=81.8 versus R@ 100=75.3).
A.9 IMPACT OF FORMULAS ON TRAINING TIME
We haven't done any specific timing tests, though the runtimes were similar with and without logic. This theoretically expected as the logic is placed in series (after) the neural networks and is faster to compute. With sufficiently complex logic one could imagine logical computations (and backpropagation) to exceed the computation cost the neural networks, but we are far from this regime. We also heavily utilize the tensor operations in Pytorch, which allows to leverage the speedups in training general neural networks.
A. FUTURE WORK
First order logic provides uniform framework in which we plan to support transfer learning and zero-shot learning by training DASL models on theories where data is abundant and then creating new theories on the same vocabulary that address problems where data is sparse. We also plan to demonstrate the converse capability, training distinct models of single theory, allowing us to sample models as a technique for capturing true probabilities, similar to Markov Logic Networks [Richardson] & Domingos [. Finally, we exploring ways to allow DASL to learn rules from data while retaining explainability and integrating smoothly with user defined logic.
19


Reviews:
[{"review_id": "jlaIPuRFEfY", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on the problem of augmenting the user-provided knowledge into Neural networks. The core premise of the work is that the existing approaches tend to replace the True and False with values in [0,1] and then use maximum/minimum operators which have vanishing gradients. The key idea is to use logit representation and therefore, the authors hope to avoid the vanishing gradients problem. The paper presents empirical results to argue that embedding knowledge helps. \n\nI think its an interesting paper but somehow the comparison with prior work is not properly contrasted, which makes me believe that the paper has probably reinvented quite a bit of aspects. An important missing work is [1], which in fact uses product and addition instead of minimum/maximum.  (It is well known that exists and forall operators can be expressed using disjunction and conjunction)\n\nAlso, Xie et al (NeurIPS 2020) build on [1], and  do perform empirical on the same VRD dataset and achieve significant improvements; their numbers seem better than what is reported in Table 1.\n\nIn light of the above remarks, it is hard to understand the new contribution of the paper. \n\n\n[1] https://arxiv.org/abs/1711.11157 (Published at ICML 2018)", "extra_scores": {}, "extra_text": {}}, {"review_id": "fzBfbUAN43q", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper integrates a neural encoding of first-order logic with deep learning architectures, supplementing training data with declarative knowledge. The approach is experimentally evaluated on MNIST and visual predicate detection, demonstrating  a reduction in data requirements. \n\nThe paper deals with an important topic and provides very promising results. However, I would've liked to see a more extensive experimental evaluation. Also, which performance gain does additional knowledge produce for visual predicate detection, compared to the current SOTA for that task. So, are the first-order constraints always satisfied by the produced results? \n\nAfter rebuttal: The long discussion with the authors to clarify the questions in my review and further related questions actually shows that the paper is not really clear and would still benefit from a substantially improved presentation. So, I slightly downgraded my overall rating of the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_YW35qRncE4", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper introduces Deep Adaptive Semantic Logic (DASL) as a novel framework that automates the generation of deep neural networks on the basis of some background domain knowledge. A first-order logic formalism (which exploits Tarski models) is used to represent knowledge, and, subsequently, to model deep networks on the basis of such knowledge. This resembles ideas coming from the neuro-symbolic community, such as the pioneering work by Towel and Shavlik on KBANNs, and more recent approaches such as Neural Tensor Networks, DeepProblog, Lyrics.\n\nThe model is evaluated on a toy problem (extracted from MNIST) and the task of visual relationship detection, that aims to predict relations between objects in the scene.\n\nAlthough the work is interesting, and perfectly in scope with the conference, focusing on a very hot topic in AI, I have to raise some concerns regarding the experimental evaluation, which basically does not compare against similar approaches, nor it considers similar tasks in the literature.\n\nIn particular, no comparison is presented with other approaches from the Neuro-Symbolic community: more precisely, maybe some tasks could have been borrowed from previous works. For example, the DeepProbLog paper presents a similar task regarding sums with MNIST digits? Or, in the setting of image classification, the framework of \"Learning from constraints\" has been evaluated on a task which considers exploiting class hierarchies and commonsense (e.g., see \"Image Classification Using Deep Learning and Prior Knowledge\", AAAI Workshops, 2018).\n\nOther comments:\n\n* What is the state-of-the-art for the VRD task? Is DASL competitive?\n\n* The way references are used in the text should be made consistent. In Sections 1 and 2, there is no parentheses before references (e.g., \"...estimated from data LeCun et al. (2015)\") whereas in Section 3 there are parentheses, which is to be preferred (e.g., \"...by boolean Tarski models [Chang & Keisler (1973), Weiss & D’Mello (1997)]\").\n\n- \"techniques such conditional random fields\" -> \"techniques such as conditional random fields\"\n- \"data scarce conditions\" -> \"conditions of data scarcity\"\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "MF_VS1hjQXY", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper describes an approach to combine first-order knowledge bases with deep networks. The idea is to represent logical operators as neural components that produce continuous values (using a logistic output) instead of boolean values. The proposed approach is formalized using Tarski models. Here, it is shown that if we consider each parameterization as a model, the learning samples models from the logical theory. Results are proven that such an approach is both sound and complete for any first-order logic theory.\n\nNeuro-symbolic models seem very promising and therefore the paper addresses a very significant problem. The approach seems similar to Rockstachel et al. 2017’s approach for theorem proving in first-order logic. It seems like the main contribution though is that their model is more general and they prove soundness and completeness of their approach. Maybe a little bit more on why the approach is more general than existing approaches can help motivate the novelty aspect more clearly.\n\n\nThe experiments seem to be well thought-out though only 1 real domain and 1 toy domain are explored. However, I was not sure how the knowledge bases are constructed for the VRD problems. The single example seems clear. But how is it done for any problem in general? What types of logical formulas were pre-specified corresponding to visual relationships since I imagine this can be quite extensive. Is there any impact on training time/effort as the formulas become more complex since the architecture of the network becomes more complex. Also, does the expert knowledge change for each image? I think some more details on this task will help clarify the experiments and make the results more easily reproducible.\n\nIn summary, this seems like a nice paper but a little fuzzy on the details of the experiments which can be clarified better.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers and AC appreciate the improvements made to the paper and thank the authors for engaging with the reviewer questions.
There are now quite a few neuro-symbolic approaches, and they are all rather similar. This places a larger burden on the authors to have a thorough and systematic experimental comparison and related work discussion. Reviewers also believe the clarity of the paper should still be improved. The revised paper already made good progress in addressing these concerns, yet the reviewers still believe the paper would strongly benefit from another round of revisions.
Decision: Reject