Soft-Unification in Deep Probabilistic Logic
Authors: Jaron Maene
Luc De Raedt
Venue: NeurIPS 2023 poster (2023)
Keywords: neuro-symbolic AI
probabilistic logic
embeddings
TL;DR: We propose a probabilistic integration of embeddings in logic programming using soft-unification.

Abstract: A fundamental challenge in neuro-symbolic AI is to devise primitives that fuse the logical and neural concepts. The Neural Theorem Prover has proposed the notion of soft-unification to turn the symbolic comparison between terms (i.e. unification) into a comparison in embedding space. It has been shown that soft-unification is a powerful mechanism that can be used to learn logic rules in an end-to-end differentiable manner. We study soft-unification from a conceptual point and outline several desirable properties of this operation. These include non-redundancy in the proof, well-defined proof scores, and non-sparse gradients. Unfortunately, these properties are not satisfied by previous systems such as the Neural Theorem Prover. Therefore, we introduce a more principled framework called DeepSoftLog based on probabilistic rather than fuzzy semantics. Our experiments demonstrate that DeepSoftLog can outperform the state-of-the-art on neuro-symbolic benchmarks, highlighting the benefits of these properties.

Soft-Unification in Deep Probabilistic Logic
Jaron Maene KU Leuven jaron. aaron.mane@kuleevenn. be
Luc De Raedt
KU Leuven & Örebro University luc. dewaeedtdulleeeennn be
Abstract
A fundamental challenge in neuro-symbolic Al to devise primitives that fuse the logical and neural concepts. The Neural Theorem Prover has proposed the notion soft-unification to turn the symbolic comparison between terms (i.e. unification) into comparison in embedding space. It has been shown that soft-unification is a powerful mechanism that can be used to learn logic rules in an end-to-ent differentiable manner. We study soft-unification from conceptual point and outline several desirable properties of this operation. These include non-redundancy in the proof, well-defined proof scores, and non-sparse gradients. Unfortunately, these properties are not satisfied by previous systems such as the Neural Theorem Prover. Therefore, introduce more principled framework called DeepSoftLog based on probabilistic rather than fuzzy semantics. Our experiments demonstrate that DeepSoftl log Log can outperform the state-of-the-art neuro-symbolic benchmarks, highlighting the benefits of these properties.
Introduction
Deep learning has become the most prominent paradigm in machine learning but still suffers from limitations such as poor interpretability, reasoning skills, and difficulties in incorporating knowledge. Neuro-symbolic AI (NeSy) is an emerging field that seeks address these limitations by combining the strengths of neural networks and symbolic systems [14] [6].
A key design question in NeSy is the used representation [4 [6.. Neural networks operate
tensors while symbolic reasoning operates on symbolic structures. Previous systems have broadly used ways deal with this dilemma. The first is keeping the neural and symbolic representations completely separate (e.g. DeepProbLogg (22). The second is relaxing the symbolic part, making continuous by mapping the symbols
vector spaces (e.g. Logic Tensor Networks (4). This allows principle - for a tighter integration, where both representations are retained and fused.
The Neural Theorem Prover (NTP) [29] is early system that pioneered such integra- tion, by linking the logical and neural representations with a mechanism called soft-unification. with grandfather john) or
For instance, in regular logic, matching grandpa(jef. event weenteerthhuake, and event (landslide) fails. However, by mapping grandfather and grandpa, resp. earthquake and landslide to vectors, they can be compared in embedding space. The NTP is an end-to-end differentiable prover that learns these embeddings from data.
Inspired by the success of the NTP, we analyze its key perspective. We identify several natural and desirable properties of soft-unification, which are not always satisfied by previous works. This motivates us to propose an alternative more principled definition of soft-unification based on distances. Next, we introduce DeepSoftLogg which makes principled integration of embeddings in probabilistic logic programming [10].
from theoretical
As an example, consider the DeepSofiLog program in listing [ with learnable embeddings (denoted with the ~ prefix), we turn regular finite state machine
By associating the constants
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

implementation into differentiable model. So if the program would be trained on e.g. the (01)* language, could learn set >>pre__stttell statel ~state2 and sarev_state2 ~statel.
In summary, this paper makes three contributions: (1) a theory for using learnable embeddings in logic through soft-unification, (2) DeepSoftLog. neuro-symbolic system that includes embeddings inside an end-to-end probabilistic logic prover, and (3) a demonstration of the practical advantages of Dog over slate-of-the-a NeSy systems several benchmarks.
run (~endd state, (]). X base X)
accepts (x) :- run cesstar_statee
state transitions run (>statell [~symbol11 [ :- run (~prev_statel, T).
(>sttate2, [>symbo12 [T]) run (~prev_state2, T). query (accepts ( [~00, ~1]))
Listing 1: Example of differentiable finite state machine implementation in DeepSoftLog.
2 Background
2.1 Logic programming
We summarise the basic logic programming concepts. An in-depth discussion can be found in 13
structured term ftt,,.... tx), where f is functor and t; are terms. Atoms are expressions of the form q(tı,..., tx), where q is predicate of arity i and or negated atoms. The meaning of such rule is that h holds whenever all the b,'s hold. The atom the head of the rule, while the conjunction of is is the body. Facts are rules with empty body.
Syntax A term is either constant c, variable
terms. rule is expression a
bı,..., by where is atom and b, are atoms
logic program set of rules. An expression ground if it does not contain variables. To ground expression
can apply substitution 0 {V1 ti .... Vx + tx), creating instantiated expression eø where every occurrence the variable V, is replaced with t;. An important operation unification. Two expressions and t2 unify when there exists substitution 0 such that t, tzO. For example, (a), X) and {g((), 2) have a unifier {x Z, a).
Semantics The set of all possible ground terms in program is called the Herbrand universe U. A possible world (or Herbrand interpretation) a subset of the possible ground atoms. A ground atom is true in possible world when E w. A possible world w is model for program T, written w += T, when every grounding every rule the program is true in the possible world.
Inference Proving relies on the repeated application of rules to a goal, using SLD resolution. Given rule h bj.... bn and goal g1.... gm. such that h and gi unify with substitution A, SLD resolution derives the new goal (bj,... Dn g..... ). A proof is a sequence of resolution steps that results an empty goal.
2.2 Probabilistic and Fuzzy Logic
ProbLog 10 extends logic programming with probabilistic facts :: f, where a ground fact is annotated with a probability p. As example, consider the well-known alarm Bayesian network:
event(landslide). 0.2 :: event(earthquake)
0.5 hears alarm(mary). 0.4 :: hears alarm(john) alarm :- event(landslide). alarm :- event event(earthquakeg calls(X) :- alarm, hears -aars__aarmm).....
Semantics Each ground probabilistie fact represents independent Boolean random variable. Hence, the probability of a possible world w is a product over the choice of probabilistic facts in w. The probability (or success score) of atom program 7' the sum over all the models of T where a is true.
P(w) II Ps II ps) f&
P(a)
Σ
P(w)

---

In the example, a choice of probabilistic facts F = has the corresponding model ur F UU (alarm, calls (mary)) with probability P(w) 0.1 0.5 (1-0.2) x (1 - 0.4) 0.024.
( (event(landsliiii hears al alarm (mar)))
We rely on proving approach (24]. Computing the success score P(g) of a query consists of the following steps. (I) Generate the set of all proof's (q)) using SLD resolution. (2) Disjoin the proofs into formula V VrEBiU) т. (3) Transform this formula using knowledge compilation 77. to ensure it can be evaluated correctly and efficiently. (4) Convert the compiled formula into an arithmetic circuit by replacing the
Inference There multiple ways perform inference in ProbL.gg 12]
OR and AND operations with SUM and PRODUCT operators from a semiring 220
calls (mary)
calls (mary)
0.14
OR
AND
AND
AND
OR
hears_alare alaam (mary)
0.4
AND
AND
X
event (burglary)
event (earthquake)
hears_al alarm(nary)
OR
event (landslide) 1 0.1
0.1
event (landslide) event (earthquuae -evnnt (earthquake)
0.2
1- 0.2
Figure 1: The circuits used during inference of calls(mary) in the alarm example. (left) AND/OR formula represented as tree. (middle) Compiled formula. (right) Arithmetic circuit.
We demonstrate our inference approach on the query calls(mary). The proofs: event (vent(earthquake) A hears_ alarm(mary and event(landslide) A hears alarm re- sult in the formula on the left of figure []] when disjoined. When working with probabilities, we cannot simply evaluate this formula. Indeed, the proofs are not independent as they both contain hears_alase (arrmaaaaa so P(A V B) * P(A) + P(B). Hence, we transform the formula into a circuit using knowledge compilation 7 (middle of figure []. The resulting circuit supports many types of inference, by evaluating with the appropriate semiring [19]. For probabilistic inference, we can simply use the standard + and x operators, as shown on the right of figure
Neural Theorem Prover We can also sketch the Neural Theorem Prover (NTP) (2 in this framework. The NTP is based on the Datalog subset of Prolog. So it does not include structured terms (e.g. lists) or negation. At the same time, rather than using the probabilistic semiring, the NTP uses the fuzzy semiring. Essentially, this means the fuzzy max and min operations are used instead of the probabilistic and x. This is also known as the Gödel t-norm or minimum t-norm. In contrast with probabilistic inference, disjunction in the fuzzy semiring is idempotent. This implies we can skip the expensive knowledge compilation step and evaluate the formula directly during proving [19]
Approximation As probabilistic inference is #P-hard, it is possible to approximate inference by only using the k-best proofs. The best proofs are those with the highest score. During proving, these can be found with A" search on the proof tree [24]. For instance, the 1-best proof for the example event event (eeetteathquaee) A hears_ al alarm(m alarm(mary) (mary). with a score of 0.08. Note that for the NTP, the 1-best proof captures the full success score due to the max aggregation of proofs. The NTP and Greedy NTP (26) introduced additional approximation methods to prune proofs during proving, such as imposing maximum depth and maximum branching factor.
2.3 Soft Unification
While in standard logic programming two constants landslide and earthquake do not unify (i.e. do not match), soft-unification returns a score based on how similar the symbols are in embedding space. We use the predicate to denote that two symbols are soft-unified (e.g. earthquake ~ landslide). The score of a soft-unification is determined by a soft-unification function S S [0, 1), so P(4 (2) = (21,,
Algorithm I states the simplified soft-unification algorithm for atoms and terms without functors. The algorithm returns the set of variable substitutions, that make two atoms equal while disregarding the
3

---

equality of the symbols. For example, the two atoms p b, X) Y) and p(c. d, Z, d) do not unify, but soft-unify with the substitution {X + Z, Y + d}. In practice, the algorithm usually also extracts the conjunction of the used soft-unifications (in this example (a c) A (b = d)). During inference, these can be conjoined with the proof just like probabilistic facts.
Algorithm 1 Soft-unification
function SOFTÜNIFY((1,
if 1 is variable then return (4 - [2) else if f22 is a variable then return {t2 - 11}
else if f and by are constants then return
else if & and l2 are atoms of the same arity & then
return (1. SoFTUNIYY(argumen i of 4, argument of (2)
else return Failure
end if end function
To illustrate soft-unification during proving, suppose that a[landslide, earthquake) = 0.5. We can now delete the fact event(landslide from example program and still derive the same probability for the query calls(mary). The first proof for event(landslide) event event(earthuuake) A hears alarm(nary)) is unaffected by the deletion of event event(landslide) But in the second proof, we need to derive event(lands) (landslide) by applying event event (earthquake), resulting in the proof event wrenteerthhuakke A (landslide lide = earthquake) A hears al (lrrr))
(namely
3 Soft-unification properties
In principle, any function be used for soft-unification. However, introduce some properties that make the soft-unification semantically meaningful and efficiently trainable.
Definition 1. The success score P(q) is well-defined iff for every soft-unification function query q. and pair of logically equivalent programs Tí and T2 (i.e. Va Ti a + T2 } a), the success score P(q) is the same for Ti and T2.
Definition 2. The soft-unification function is non-redundant, when given proof n, every other entailed proof of the form nt = (T\44 = 12}) U {4 = lx, lu = Li} has at most the same score: P(r') S P(T).
We motivate definition by returning our rumning example. Recall that we made a proof where event (rent(landslia idde) was obtained using the soft-unification: (landslide ~ ear earthquake). Suppose now that the program contains some extra rules: alarm varning(avalanche :- event event(avalanche) These rules could be interjected in the proof so that we use: (landslide ~ avalanche) A (avalanche earthquake). Definition 2 says that introducing these intermediary soft coft-unifications in the proof should not increase the proof score.
and
The soft-unification function is connected, when for every x and where # it is possible to have a y that is inbetween x and 2 (i.e. s(x,y) > s(x, 2) and s(y, 2) > 2))
Definition 3.
Definition] iss a statement on the expressivity of soft-unification. For example, it should be possible model that white and grey similar (e.g. s(whi te, grey) 0.5), and grey and black are similar (e.g. sgree,, black) = 0.5), but that white and black are dissimilar (e.g. swhite, black) = 0.25).
Definition 4.
We call the proof score P(g) effectively optimizable when the soft- coft-unification is differentiable, and possible to have a gradient with respect to every proof π in B(q)-
This last definition essentially asks that the soft-unification function should be trainable using gradient descent. It is important that every proof receives gradients, updating single proof at a time leads to local minima due to a lack of exploration 9 244. .. In short, if wrong proof starts of with a higher score due to an unfortunate initialization, it should not get pushed up greedily disregarding the other proofs. Otherwise, the correct proof might never discovered during training. Note that k-best approximate inference does not evaluate all possible proofs and hence cannot satisfy definition 4

---

Properties
Def.
Def. 2
Def.
Def. 4
Bousi~Prrolog
Yes
Depends (*)
Depends (*)
No
WHIRL [6]
No
No
Yes
No
NTP
12
No
No
Yes
No
LRNN B1
No
No
Yes
Yes
DeepSoftLog (Ours)
Yes
Yes
Yes
Yes
Table 1: Comparison of the soft-unification properties of different (neuro-Jsymbolic systems.
(*): Depends the choice of transitivity and t-norm.
3.1 Neural Theorem Prover
The current (euurr)--ymbolic systems unfortunately do not always respect the abovementioned properties. We focus mostly on the Neural Theorem Prover, though table I gives an overview of several related (neuro-)symbolic systems, which we later discuss in the related work. We start by introducing some necessary concepts, before giving the proof that the NTP is not always well-defined.
An atom term is linear when variable occurs multiple times. A rule is linear when its head is linear. A soft-unification function is A-transitive when s(x, z) 2 s(x, y) A s(y, z), and a A- similarity when it is reflexive, symmetric, and A-transitive. The specific meaning the conjunction operation A depends on the semantics, So A-transitivitty should be interpreted as min-transitivity for the NTP and X x-transitivity for ProbLog. Omitted proofs can found appendix A
Theorem 1. The Neural Theorem Prover is not well defined on programs with linear rules.
Proof. We give proof by example. Consider the following two programs:
eq(x, x) :- p(X). p(a). p(b). p(c). and eq(a, a). eq(b, b). eq(c, c). p(a). p(b). p(c).
These programs are logically equivalent but can have different proof score for the query = eq b). In Ti we obtain ((g) = s(a, b) in the straightforward manner. But in the second proof, we obtain P(q) max(s((a, b), (s(a, s(b, c))). because
also unify with eq(c, c). So with the right choice of s, the proof score P()) is higher in T2 than Ti.
This proof works in general for programs that contain linear rules. It might be tempting to suggest fix by making A-transitive, but this does not resolve the problem when negation is considered. Transitivity is still desirable for another reason however, as it relates to definition 2
Theorem 2. Definition holds when the soft-unification function is A-transitive.
We note that the NTP implements the coft-unification function using radial basis functions 5 (specifically the laplacian kernel -- which min-transitive. The situation in the NTP is further complicated as the choice of semantics links definition a Theorem 3. Under the fuzzy semiring, definition 3 cannot hold if is A-transitive.
In other words, by choosing the minimum t-norm, definitions 2 and 3 are mutually exclusive. A further disadvantage is that the minimum t-norm also does not satisty definition 4 By using the minimum conjoin facts, the success score of a proof is essentially determined by the weakest soft-unification. This is significant drawback as it heavily reduces training efficiency and leads to local minima
3.2 ProbLog
Motivated by the previous discussion, we will rely on probabilistic instead of fuzzy semantics. This allows us satisfy all the stated properties.
Theorem 4. If the soft-unification function a x-similarity with probabilistic semantics, we can satisfy all stated properties (from Def. 7 Def. 2 Def. I Def. F
Theorem 5. soft- fiff-unffication function is a x ximmilarryt, iff s(x, y) = =(=(((()))(( where d is distance function on an embedding space and & maps symbols to this space.
The last theorem shows that the soft-unification corresponds to distance under the modest assumptions of reflexivity, symmetry, and transitivity. This brings us to the final question of what concrete embedding space to choose. We do this based on two considerations.
embedding space
5

---

This first is the gradient norm of the soft-unification. It is undesirable to have large regions of near-zero gradients for many successive soff-unification steps (also known the vanishing gradient problem). Due to the exponential function, this can only be achieved by taking a bounded domain. We implement this by choosing a hypersphere as the embedding space, i.e. the set of normalized vectors {z E IR" ||a|| 1).
natural distance use on hyperspheres is the angle. drawback of using the angle is that two symbols on the opposites of the hypersphere are maximally dissimilar. This is undesirable as we cannot have many symbols that are all dissimilar each other. To solve this we use s(x, y) exp(- arccos| (xr) (t))) as the soft-unification. The À is scaling factor, which can be set based on the desired minimal soft- coft-unification score. The absolute value assures that maximum dissimilarity is achieved at 90 degrees instead of 180. So as random high-dimensional vectors are almost surely orthogonal, soft-unification scores initialization will be zero in expectation.
4 DeepSoftLog
The previous section discussed the combination of soft-unification with probabilistic semantics. We will now formally implement it as an extension of ProbLog, called DeepSoftL.gg
Syntax DeepSoftLog is a superset of the probabilistic logic programming language ProbLog. This means that every valid ProbLog program is also a valid DeepSoftLog program. Syntactically, DeepSoftLog only adds single syntactic element: embedded terms.
Definition 5. An embedded term is a term ~ t, where ~/1 is the embedding functor and is a term.
The embedding functor turns term into an embedded term ~t. As the embedding functor is unary, we do not write brackets. The embedding functor is idempotent, and applying it inside an embedded term has no effect. For example, ~ (~XX is equivalent to ~f (x). Embedded terms can be composed like any other term, c.g. f (~aa, g(x, (b)))) The embeddings are computed using a dictionary 'D which stores vector D(c) E RR" for all constants and a neural network R -> IR" for every functor f of arity k. The embedding of a ground term 3 U - R" is recursively defined as E(c)= = D(c) for a constant a and ((((t,....ba)
(t..))))))) tx)) = (()))
for structured term.
We note that we deviate from the NTP in several important regards concerning what we embed. (1) The embedding of terms is optional. This means the programmer is free to choose, where makes sense to rely on embeddings, and what to keep symbolic. This can help keep inference tractable, as letting everything soft-unify leads huge branching factors. (2) DeepSoftLog does not embed predicate symbols. However, this is not an actual restriction, and the NTP behavior can easily be simulated. For example, (x). - b(y) in NTP notation turns into r (~va, ~x). . [>~,, ~y) in DeepSoftLog notation. (3) DeepSoftLog can embed structured terms. Embedded functors map embeddings to new embeddings and are natural place to use neural networks.
Definition 6. A DeepSoftL.og program T tuple T5, TR). The soft-unification function s:l x u + J0, I] maps two embedded ground terms to the probability that they unify. Ty is a set of ground probabilistic facts and TR a set of linear rules. The atoms in Tr and TR can contain embedded terms.
Semantics We base the semantics of DeepSoftLog on ProbLog, by creating a source-to-source translation. The basic idea is to eliminate the embedded terms by simulating the soft-unification with a predicate >. More concretely, all embedded terms in the head of a rule are replaced by a new unique variable. Next, ~ atoms added at the start of the body to provide the soft-unification probabilities. An example of this transformation, p(~xx) :- q(>y). becomes p(~~V,) :- ~V, ~ ~xx q(~-)).
After applying this transformation to all rules in Tx and Ty. we obtain regular ProbLog program. The soft-unification function itself can also be encoded in ProbLog by adding facts for all pairs of ground terms: p :: ~t1 ~ ~22, where p = s(t1, tz). We provide some examples of this transforma- tion on full programs in appendix B We note that the resulting ProbLog program can be infinite, by grounding out the soft-unification predicate on an infinite set of ground terms. However, the Probl.og Log semantics are still well-defined on infinite programs, due to the use of Sato's 's distribution semantics [30].

---

We note that this program transformation is only for semantics, and we still apply the soft- coft-unification algorithm during inference. In appendix C we prove that the soft-unifictiinn algorithm equivalent to regular unification on the transformed program.
Non-linear rules The semantics of DeepSoftL.og only allow for linear rules, but non-linear rules can be supported as syntactic sugar. Similar to Bousi-Proloo (18), we linearize rules as follows. The variable X that occurs multiple times in the head is replaced by unique variables, and = predicates are added to the body to perform the soft-unification. For example, the linearization of p(x, x) :- qxx). pV1,. V2) :- V1= ~ 22, q(V2). This construction does entail some extra grounding work on =. We need to state the c = с fact for every constant c, to make sure p(X, x) in this example can still succeed with non-embedded constants. Similarly, we need rules fV.....VV. vx) [W1.
V1 ~ W,,...Vy = W/ for every functor f of arity k.
Exact inference can be- come intractable for large experiments, so we support approximate inference techniques (k-heet, maximum search depth, and maximum branching factor), similar the Greedy NTP [26]. An important constraint we apply is that the soft-unification predicate = needs to be ground upon evaluation, i.e. input mode (++, ++) in Prolog. Otherwise, the number of possible unifica- tions explodes. For example in a = f(),, X can unify with an infinite number of ground facts: ~ f(a), a ff(())), a ~ ((f(f
Inference We use proof-based inference, as deseribed in section 2.2
During training, we can use the gradient semiring of algebraic ProbLog to make the success score end-to-end differentiable [19]. We train using the AdamW optimizer [2] with cross-entropy loss.
Structure learning As in the NTP, we can add templates to the program to do rule learning via param- eter learning. For example, r(~tt, X, Y) :- r(~t,, X, 2), r(>t,, Z, Y). is a transitive template that could be used for the facts r(~sibbinge, alice,
(it.ss/iiiiiggs.... bob, charlie). by learning that wegillllinngge bigs ~t, These templates can also parameterize the rule symbol tı, similar to the conditional theorem prover [27] [(~T, x, Y) : ((~f, (T), Z.Y..
5 Experiments
We present three sets of experiments. First, we compare DeepSoftLog to the NTP on structure learning tasks, which requires learning rules from data. We show that DeepSoftLog significantly improves the performance over the NTP, and perform ablations to show that the properties introduced in section are instrumental to this. The second experiment requires learning the perception, while the background knowledge is given. The last experiment is the most challenging setting, as both perception and rules need to be learned jointly. For all experiments, we report the mean and standard deviation over 10 seeds. All code is available on htltttts:/gttuub.....t httpm//jmmmooo/eeeeeeoe SrrrooonDDeeSoft.....
5.1 Countries
Countries is a knowledge graph with the locatedIn and neighborOf relations between the countries and continents on Earth. There are three tasks of increasing difficulty (S1, S2 and S3). For example in S2, we need to derive DocatedIn(france, europe) using facts such as locatedIn DocatedIn(belgámm (belgium, europe) and neighborOf [france, belgium). For the full experimental setup, we refer to previous work [26] 29]. To keep the comparison fair, we use the same rule tem- plates, embedding dimensions, and training objective as the NTP. The hyperparameters can be found in appendix D.2. Table 2 reports the results and compares them with other state-of-the-ar NeSy systems that support structure learning.
In figure 2 we perform ablation on the properties of DeepSoftl-og, discussed in section As expected, DeepSoftl.gg no longer properly converges when switching from probabilistic semantics to fuzzy semantics (violating property o. Switching the soft-unification function s to Gaussian kernel (violating property ( also delays convergence. There is no ablation for property 3 as there no straightforward way to violate it in DeepSoftLog.
5.2 MNIST-addition
MNIST-addition is popular neuro- neuro-symbolic benchmark where, given two numbers as lists of MNIST
images, the task is to predict the sum (c.g. 52 8 3 135). An attractive feature of this task is
7

---

Countries
S1
S2
S3
NTP 229
90.93 + 15.4
87.40 11.7
56.68 17.6
GNTP 26
99.98 0.05
90.82 = 0.88
87.70 4.79
DeepSoftlogg (Ours)
100.0 + 0.00
97.67 = 0.98
97.90 1.00
Ne
100.0 0.0
75.1
92.2 0.2
CTP 27
100.0 + 0.00
91.81 = 1.07
94.78
MINERVA g
100.0 + 0.00
92.36 = 2.41
95.10 1.2
Table 2: AUC-PR on Countries link prediction [29]. Results are adapted from 27 The three methods top use templates, while the bottom ones do not.
1.25
None
1.00
Gödel
Ablations
VP
AUC-PR
0.75
Gaussian kernel
None
97.67
0.98
0.50
Gödel t-norm
2,
23.73 73 4.08
Gaussian kernel
28.33 + 3.64
0.25
0.00
200
400
600
800
1000
1200
1400
Iterations
Figure 2: (Left): Ablations of DeepSoftLogg on countries S2, with the corresponding properties that are violated. VP stands for violated properties. (Right): Loss curve during training the ablations. The shaded area represents the min/max over 10 seeds, while the line is the mean.
that it allows to increase the reasoning difficulty, by increasing the number of digits. We the same experimental setup and neural network as previous works, to which we refer for more details [22]
Existing NeSy solutions to the MNIST-addition problem typically represent all the possible sums explicitly, which means inference becomes exponential the number of digits. DeepSoftl.og Log allows an alternative encoding of the problem which scales linearly, by using the embeddings represent discrete probability distributions over the digits. In each iteration, the probability distribution of the carry and the digit classifier are used to calculate the probability distribution of the sum and the next carry. This factorization the problem is similar to the one used in A-NeSI [32,, although we do not approximate and use exact inference. The program and hyperparameters are included in appendix D.I Results are summarized table
Digits per number
15
100
LTN
4
80.3 23.3
77.5 - 35.6
timcout
NeuPSL.
28
97.3 0.3
93.9 0.4
timeout
DeepProbLogg
97.2
95.2
timeout
NeurASP
35
97.3 0.3
93.9 0.7
timeout
DeepStochLog
3
97.9 0.1
9..4
92.7 + 0.6
timeout
Embed2Sym 2
97.6 0.3
93.8
91.7 0.6
60.5 20.4 75.9 2.2 77.1 = 1.6
timeout
A-NeSI [32]
97.7 +
96.0
92.6 0.8
overflow 25.6 + 3.4
DeepSoftL.og (Ours)
98.4 0.1
96.6 0.3
93.5 - 0.6
Reference
98.17
96.37
92.87
75.78
15.43
Table Test accuracy of the sums the MNIST addition problem. Results adapted from [32] Reference equals 0.99072d where d is the number of digits per number. This is lower bound on the performance that can be achieved when single-digit supervision is available.
The performance DeepSoftLog line with previous exact systems like DeepStochLog, and we note that the improvement over other exact systems such DeepProbLogg log and NeurASP is likely due their suboptimal hyperparameters. More importantly, DeepSoftLogg outperforms the more specialized systems Embed2Sym and A-NeSI, while also scaling further.

---

Language
(01)*
00100
(0 10" 10
RNN
77.63
15.05
61.59 + 10.09
50.14 1.36
DeepSoftLog
83.93 25.87
87.01 + 7.18
56.12 + 15.98
Table 4: Results for the differentiable automata experiments. We evaluate with the AUC-PR and report the average and standard deviation over seeds.
5.3 Differentiable Automata
We can implement a differentiable finite state machine in DeepSoftLog by taking a regular finite state machine in Prolog and making the states and symbols embedded (see listing D. The resulting model can be trained end-to-end, jointly learning interpretable rules and a perception network.
As an example, consider the regular language (01)* represented by MNIST images. We learn from positive examples (e.g. O or
0 and negative examples (c.g. / 0001 We train on sequences of lengths up to 4 and test the generalization by evaluating sequences of length 8 with images not seen during training. Hyperparameters are in appendix D.3
We pre-train the perception network with 20 images, for which the ground truth image labels are given for each digit. This small amount of concept supervision prevents reasoning shorteuts (25) and eases the optimization problem. As baseline we use an RNN, which has the same perception network and receives the same pretraining.
Results are summarized in table 4 We repeat the experiment for different regular languages. Not only does DeepSoftLog achieve higher AUC, but it is also highly interpretable as we can inspect the learned state transitions.
6 Related Work
There are several neuro-symbolic systems built on the principle of neural reparametrizations in symbolic framework. DeepStochLog [33, NeurASP (35), and DeepProbLog (23 are neural extensions of stochastic grammars, answer set programming, and probabilistic logic programming respectively. Lifted Relational Neural Networks [ii and Logie Tensor Networks 4 are based on Datalog with fuzzy semantics (which cannot deal with structured terms) and use the logic program to construct the neural network. These systems make different trade-off's between expressivity and scalability, with fuzzy systems typically being more scalable and probabilistic systems being more expressive.
DecpSoftLog explores an alternative possibility, by neurally reparamcterizing the matching mecha- nism between symbolic symbols instead of the symbols themselves. DeepSofiLog is most closely related to DeepProbLogA' [24], as they both rely on probabilistic possible worlds semantics and backward proving. Hence, it is in principle possible to convert between the two.
The Neural Theorem Prover (NTP) 229 pioneered the association of learnable embeddings with symbols in logic prover. However, the fuzzy semanties of the NTP leads to gradient sparsity and local minima, as discussed in section Furthermore, the NTP lacks several key features of DeepSoftLog like neural functors, recursive rules, and negation. The Greedy Neural Theorem Prover 26 improved the scalability of the NTP. The Conditional Theorem Prover 27 extended the NTP to support rule learning without templates.
The soft matching of symbols in logic is already well-studied in the fuzzy logic programming community [15). A notable example is Bousi~-Prolog 18). which just like the NTP uses soft- unification and fuzzy semantics. These systems still differ considerably from DeepSoftLog as they not differentiable, and typically rely the user to manually specify the soft-unification function. operation also be
WHIRL [6] proposed to add embeddings in DataLog for more flexible data querying. Their soft-join
an early form of soft-unification, albeit a learnable one.
Many approaches towards embedding symbols have been investigated for knowledge graphs. Recently, some of these have also been combined with symbolic methods [[] 36). Generally, these methods are

---

less expressive than DegpSoftLog but far more scalable. MINERVA 8 uses reinforcement learning predict links by walking over a knowledge graph conditional on query.
7 Limitations
DeepSoftLog inherits the advantages of probabilistic logic programming, but also the disadvantages. Probabilistic inference is #P-hard, so exact inference is often not tractable and we need to rely on approximate inference techniques (e.g. [ 24 ) Crucially, some approximate inference methods like k-best reintroduce the local minima problem from the NTP. So in future work, we want to consider approximate methods that incorporate form of exploration, such as sampling methods. What still
could be investigated in further work is the use of embeddings to scale up inference in NeSy as in section 5.2
8
Conclusion
We analyzed how a more principled integration of embeddings in logic can be achieved for neuro- symbolic learning, by discussing the properties of learnable soft-unification. We discussed how previous systems do not always satisfy these, and how this can lead to optimization problems. We applied our analysis to create framework top of probabilistic logic programming with embeddings, called DeepSoftLog. DeepSoftLog demonstrated that two common methods to neurally extend logic, that of neural facts (as done by DeepProbL or neural unification (as done by the NTP) are essentially interchangeable. Lastly, we showed that DeepSoftl.o log can outperform existing neuro-symbolic methods both accuracy and scalability.
Acknowledgments and Disclosure of Funding
This research received funding from the Flemish Government (AI Research Program), the Flanders Research Foundation (FWO) under project G097720N, the KU Leuven Research Fund (C14/18/062) and TAILOR, a project from the EU Horizon 2020 research and innovation program under GA No 952215. Luc De Raedt is also supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.
We thank Gabriele Venturato for giving feedback draft of this paper. We are also grateful to Giuseppe Marra, Victor Verreet, and Robin Manhaeve for their helpful discussions.
References
[1] Kareem Ahmed, Kai- Wei Chang, and Guy Van den Broeck. Semantic strengthening of neuro- symbolic learning. In International Conference on Artificial Intelligence and Statistics, pages 10252-10261. PMLR, 2023.
[2] Yaniv Aspis, Krysia Broda, Jorge Lobo, and Alessandra Russo. Embed2Sym Scalable Neuro- Symbolic Reasoning via Clustered Embeddings. Proceedings of the International Conference on Principles of Knowledge Representation and Reasoning, 19(1):421 4311, July 2022.
[3] Eriq Augustine, Connor Pryor, Charles Dickens, Jay Pujara, William Yang Wang, and Lise Getoor. Visual sudoku puzzle classification: A suite of collective neuro-symbolic tasks. In Artur S. d' Avila Garcez. and Ernesto Jiménez Ruiz, editors, Proceedings of the 16th International Workshop on Neural- Symbal-Symbolic Learning and Reasoning as part of the 2nd International Joint Conference on Learning Reasoning (IJCLR 2022), Cumberland Lodge, Windsor Great Park, UK, September 28-30, 2022, volume 3212 of CEUR Workshop Proceedings, pages 15-29. TEUR-WS.org, 2022.
[4] Samy Badreddine, Artur d' Avila Garcez, Luciano Serafini, and Michael Spranger. Logic Tensor Networks, Artificial Intelligence, 303:103649, February 2022.
[5] David S. Broomhead and David Lowe. Radial Basis Functions, Multi- Variable Functional Interpolation and Adaptive Networks. Technical report, Royal Signals and Radar Establishment Malvern (United Kingdom), 1988.
10

---

[6] William W. Cohen. WHIRL: A word-based information representation language. Artificial Intelligence, 118(1):163-196, April 2000.
[7] A. Darwiche and P. Marquis. A Knowledge Compilation Map. Journal of Artificial Intelligence Research, 17:229-264, September 2002.
[8] Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, and Andrew McCallum. Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning. May 2023.
[9] Michiel de Jong and Fei Sha. Neural Theorem Provers Do Not Learn Rules Without Exploration. June 2019. arXiv: 1906.0685 [cs, stat].
[10] Luc De Raedt and Angelika Kimmig. Probabilistic (logic) programming concepts. Machine Learning, 100(1):5-444 July 2015.
[11] Lauren Nicole DeLong, Ramon Fernández Mir, Matthew Whyte, Zonglin Ji, and Jacques D. Fleuriot. Neurosymbolic AI for Reasoning Graph Structures: A Survey, February 2023.
arXiv:2302.07200 [cs, stat].
[12] Daan Fierens, Guy Van Den Broeck, Joris Renkens, Dimitar Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, and Luc De Raedt. Inference and learning in probabilistic logic programs using weighted Boolean formulas. Theory and Practice of Logic Programming, 15(3):358-40) Publisher: Cambridge University Press.
May 2015.
[13] Peter Flach. Simply logical: intelligent reasoning by example. John Wiley & Sons, Inc., 1994.
[14] Artur d' Avila Garcez and Luís C. Lamb. Neurosymbolic Al: the 3rd wave. Artificial Intelligence Review, March 2023.
[15] Lluís Godo and Ricardo O. Rodríguez. Logical approaches fuzzy similarity-based reasoning: an overview. In Giacomo Della Riccia, Didier Dubois, Rudolf Kruse, and Hans-Joachim Lenz, editors, Preferences and Similarities, CISM International Centre for Mechanical Sciences, pages 75-128. Springer, Vienna, 2008
[16] P. Hitzler. Neuro-Symbolic Artificial Intelligence: The State of the Art. IOS Press, January 2022. Google-Books Boalle-Boos--DD- AFICEAAAQBAJ.
[17] Pascual Julián-Iranzo and Clemente Rubio-Manzano. BOUSI-PROLOG- Fuzzy Logic Programming Language for Modeling Vague Knowledge and Approximate Reasoning: In Proceedings of the International Conference on Fuzzy Computation and 2nd International Conference Neural Computation, pages 93-98, Valencia, Spain, 2010. SciTePress Science and and Technology Publications.
[18] Pascual Jraián and Clemente Rubio-Manzano. A sound and complete semantics for similarity-base logic programming language. Fuzzy Sets and Systems, 317:1-26, June 2017.
[19] Angelika Kimmig, Guy Van den Broeck, and Lue De Raedt. An Algebraic Prolog for Reasoning about Possible Worlds. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1): 209-214, August 2011.
[20] Angelika Kimmig, Guy Van den Broeck, and Lue De Raedt. Algebraic model counting. Journal of Applied Logic, 22:46-62, July 2017.
[21] Uya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2018
[22] Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. DeepProbLog: Neural Probabilistic Logic Programming. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[23] Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Lue De Raedt. Neural probabilistic logic programming in DeepProbl.og Artificial Intelligence, 298: 103504, September 2021.

---

[24] Robin Manhaeve, Giuseppe Marra, and Luc De Raedt. Approximate Inference for Neural Probabilistic Logic Programming. In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, pages 475--86, 2021.
[25] Emanuele Marconato, Stefano Teso, Antonio Vergari, and Andrea Passerini. Not all Neuro- Symbolic Concepts are created Equal: Analysis and Mitigation of Reasoning Shortcuts. In Advances in Neural Information Processing Systems, 2023.
[26] Pasquale Minervini, Matko Bošnjak, Tim Rocktäschel, Sebastian Riedel, and Edward Grefen- stette. Differentiable Reasoning on Large Knowledge Bases and Natural Language. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04):5182-519 April 2020. Number: 04.
[27] Pasquale Minervini, Sebastian Riedel, Pontus Stenetorp. Edward Grefenstette, and Tim Rock- täschel. Learning Reasoning Strategies in End-to-Ena Differentiable Proving. In Proceedings of the 37th International Conference on Machine Learning, pages 6938 6949. PMLR, November
2020.
[28] Connor Pryor, Charles Dickens, Eriq Augustine, Alon Albalak, William Yang Wang, and Lise Getoor. NeuPSL: Neural Probabilistic Soft Logic. In Proceedings of the Thirty-Secome International Joint Conference Artificial Intelligence, pages 4145-4153, Macau, SAR China, August 2023. International Joint Conferences on Artificial Intelligence Organization.
[29] Tim Rocktäschel and Sebastian Riedel. End-to-end Differentiable Proving. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[30] Taisuke Sato. A statistical learning method for logic programs with distribution semantics. In Proceedings of the 12th international conference on logic programming (ICLP'95) 195, pages 715-729. Citeseer, 1995.
[31] Gustav Sourek, Vojtech Aschenbrenner, Filip Zelezny, Steven Schockaert, and Ondrej Kuzelka. Lifted Relational Neural Networks: Efficient Learning of Latent Relational Structures. Journal of Artificial Intelligence Research, 62:69-100, May 2018
[32] Emile van Krieken, Thiviyan Thanapalasingam, Jakub M. Tomezak, Frank van Harmelen, and Annette ten Teije. A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference. In Advances in Neural Information Processing Systems, 2023.
[33] Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt. DeepStochLog: Neural Stochastic Logic Programming. Proceedings of the AAAI Conference Artificial Intelligence, (099)-00000-1000, June 2022. Number: 9,
[34] Fan Yang, Zhilin Yang, and William W Cohen. Differentiable Learning of Logical Rules for Knowledge Base Reasoning. In Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
[35] Zhun Yang, Adam Ishay, and Joohyung Lee. NeurASP: embracing neural networks into answer set programming. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI'20, pages 1755 1762, Yokohama, Yokohama, Japan, January 2021.
[36] Jing Zhang, Bo Chen, Lingxi Zhang, Xirui Ke, and Haipeng Ding. Neural, symbolic and neural-symbolic reasoning on knowledge graphs. Al Open, 2:14-35, January 2021.
12

---

A Proofs
We first state the monotonicity of conjunction, which will be useful later.
Theorem 6. In both fuzzy and probabilistic semantics, it holds that when c is independent of both and b, we have P(a) S ((b) = P(a A e) S P)).c).
Proof. In fuzzy semantics, the t-norm is monotonous by definition. Under probabilistic semantics, it follows as P(a)c) P(bAc) reduces to P(c) S P(b) because of the independencies.
Theorem 2. Definition 2 holds when the soft-unification function is A-transitive.
Proof. Suppose b is the rest of the proof, such that P(π) = P(bA (t, = t,)) and P(r') = P(bA = 4x) A (tg = t,)). By the monotonicity of the conjunction and independence between b and the soft- unifications, now follows that P(4 = 14) 2 P((4 = (x) A (4x = 1,)) = P(T) 2 P(T'). Using the soft-unification function the first part becomes ((1,44) 2 s(1i, 4x) (1),)))) which is exactly the A-transitivityy rule.
Theorem 3. Under the fuzzy semiring, definition cannot hold if is A-transitive.
Proof. By the monotonicity of t-norms, s(x,, y) > s(x, 2) and s(y z) > s(x, z) implies s(x,y) A s(y. z) 2 s(x, =)As(r, 2). Due to the idempotence the minimum, this becomes ssz,)))s(,,2) y)
s(x,2). On the other hand, the A-transitivity of these inequalities implies s(x, y) A syy, < s(x,
This inequality is strict as s(x, y) = syy, S s(x, z) implies either s(x, y) = s(x, 2) or s 2) 2),
Theorem 4. the soft- ioff-uniifiationn function s is x-similarity with probabilistic semantics, we satisfy all stated properties (from Def.
Proof.
Def. I follows from the well-definedness of the ProbLog semantics, by considering = as regular probabilistic fact.
Def. follows from theorem as is transitive.
For Def. we can always create a y between some symbols and 2, by taking the mean in the embedding space (see theorem 5).
Def. follows from the symmetry and differentiability of addition and multiplication. Note that assume that differentiable.
Theorem 5. soft-unification function is a X-similarity, iff s(x, y) e -((()))))) where d is distance function on an embedding space and & maps symbols to this space.
Proof. We first prove that given that if is x-similarity, it can be written e d(x.)) We do this by showing that d(z, y) = (x(s v)) is a distance.
1. As sx, 1, we have that d(z, x) In(s(r, = In(1) = 0.
2. The symmetry of d is implied by the symmetry of s:
d(x, y) In(s v)) In(s(,, d(y,
3. The triangle inequality can be proven from the x-transitivity, and the monotonicity of In: d(x, 2) - (n(s(2, =)) < In(s(x,)) v) (y,z)) = d(z, v) + d(y. z)
As we do not have distinguishability (there can be a space is pseudometrie. The other direction can be proven in similar fashion, by evaluating that -d(,,) satisfies reflexivity, symmetry, and x-transitivity.
x + such that d(x, y) = 0), the embedding
13

---

B Example programs
We implement a variation on the alarm basian network in DeepSoftLog where the earthquake and landslide symbols are embedded. On the right, we show the translated ProbLog program.
0.2 :: event(vearthquake))
0.2 event(~V,) :- ~V1 ~ear wearthquake.
0.5 :: hears alarm(mary).
0.5 :: hears hears_alarm(ann alarm(mary).
alarm :- event(>landslidee
alarm :- event(~landslidde)
calls (X) :- alarm, hears aX)
calls(X) :- :-
alarm, hears_err _aars_aXarmm)
0.5 :: ~landslide ~ eartthquke.
0.5 wartthquae ~landslide.
~landslide = ~landslide.
eearthquake = earthquake.
Next, we also demonstrate an example with a linear rule.
X). - ee(f(~aa)) f(~b)).
eq(V1. 11 V2) :- V1 = V2.
q:- (q(f(~a))) f(~b)).
f f(11) ~ =(v1) V1 V2.
b
~a ~a ~v.
0.1 : ~a m..
0.1:war - (aa)
0.1:a-- ((b).
~b
011:<b2 .(()).
0.1:<b=00 x())
=(a))==(aa)
011:1(a)22 =a
0.1 01:rf(a)~~ ~a
=
=(b))=>(())
0.1:>f(b)=<a =~a
0.1:-1(b) = <b.
0.1 0.1:>f(b) = <f(a).
C Semantics
To prove the equivalence of the transformation with soft-unification, we need to prove two separate facts. First that two terms soft-unify, they will unify in the transformed program. Second that they will produce the same soft-unification facts.
Theorem 6. Consider two DeepSofiLog expressions and b, and the Problog expression a" which the translation of a. Now a will soft-unify with if and only if a" unifies with b (using regular unification). Furthermore, they will result in the same substitution (ignoring the extra introduced variables), and the same soft-unifications.
Proof. We prove the theorem by structural induction
1. If is variable constant, have a", so it holds trivially.
14

---

2. If a is an embedded term, we have that a" = ~V, where V is fresh variable. Hence both a will unify with b iff is embedded. If b embedded, both will add the soft soft-unfication fact b a, as the translated rule will have added this in the body.
3. If is a functor, have that f(.,,.... (a) and a" -(( - (g) If [(11,..,, 8s), both the soft-unification and unification will fail. In the other case, they will both give the result the unifications between 81 and l l give the same result by structural induction. As rules are linear, variables of the t; and ły do not overlap, meaning that the substitutions can be combined without conflicts.
of the form
4. If a an atom (i.e. a rule head), we can use an identical proof as for functors.
Suppose i and la is the corresponding term in the translated program. If i is variable or non-embedded term, we have 1 t2, which means both cases will result in the same substitution when unified with third term fz. In the case that t is an embedded term, t2 will be of the form ~V where V is a variable. Hence, when t3 not embedded, the soft unification with & will fail, and the regular unification with la will also fail. When <gg is embedded, the soft-unification with 82 succeeds and regular unification also succeeds with the substitution V - 1z. The substitutions returned by soft-unification are not exactly the same as in regular unification, because of the introduced variables. However, as these are unique and do not appear in the DeepSoftL.gg program, they can be safely ignored.
The above analysis can also be extended to the case of non-linear rules (see the section on lineariza- tion).
D Experiment details
D.1 MNIST-addition
The code for MNIST-addition is given in listing Hyperparameters are summarized in table 5 Of note in this example is that we encode as much background knowledge as possible. The green cut encodes the independency of the sum of lower digits from the higher digits, so can find the 1-best proof faster during evaluation (an alternative solution would be to use geometric mean heuristic (24). The embedded functors mod__a de_tte____ ten_add and carry could be learned by neural networks. However, for maximal performance, we hand-coded them. This possible as we know what the probability distribution of the modulo addition and carry should be.
Listing Code for the MNIST addition experiments
digit (X) :- member (X, [o, 1, 2, 3, 4, 5, 6, 7, 8, 9]) labed_dight (EMB, DIGIT) :- digit (DIGIT), (~DDIIT, EMB) (x,
add (X,Y, Y2 :- add_ (X, Y, 2, ~0)
add_ ((), [] [] ~))
add_ (0), [] [1], ~1).
add_
[YY] [HZ] [Z], CARRY) :-
embed_digit (wmod (>moo_teenadde (HX, HY, CARRY), H2).
!, X green cut for faster evaluation add_ (TX, TY, TZ, caarr (HX, HY, CARRY)).
We ran the experiments on CPU (Intel TM 17-2600 CPU @ 3.40GHz) with 16GB of RAM.
D.2 Countries
Hyperparameters summarized in table We ran all experiments single CPU (Apple M2).
15

---

optimizer learning rate learning rate schedule
Adam W
0.0003
cosine
training epochs
100
weight decay
0.00001
batch size embedding dimensions embedding initialization neural networks
4
10
one-hot, fixed LeNet5
max search depth
Table 5: Hyperparameters for the MNIST-addition experiments.
optimizer
Adam
learning rate
0.01
learning rate schedule
cosine
training epochs
6
weight decay
0
batch size embedding dimensions embedding initialization
4
100
uniform over hypersphere
neural networks max search depth max branching factor
/
2 (S1, S2) (S3)
4
Table 6: Hyperparameters for the countries experiments.
D.3 Differentiable Turing Machine
Hyperparameters are summarized in table We ran all experiments on single CPU (Apple M2).
optimizer
AdamW
learning rate embeddings
0.1
learning rate perception
0.0001
learning rate schedule
cosine
training epochs weight decay
25
0.00001
batch size embedding dimensions embedding initialization
8
3
uniform over hypersphere
neural networks
LeNet5
max search depth
Table 7: Hyperparameters for the differentiable finite state machine experiment.
E
Embeddings as fuzzy logic
different perspective on embeddings from what we considered in this paper, is to see them as discrete distribution (i.c. the embedding is probability vector). When make sure embeddings normalized (i.e. positive and sum to one) and take the dot product as a soft-unification function, we essentially get the probability that two embeddings equal. By conjoining different soft-unifications,, we have a fuzzy interpretation, as the coft-unifications are assumed to be independent.
As a demonstration, we apply this to the visual sudoku problem [ This benchmark requires classifying grid of images constitutes a valid sudoku puzzle. follow same protocol as in 32 Hyperparameters for the visual sudoku experiment are in table 9 The learning rate, weight decay, and gradient clipping were chosen by Bayesian optimization on the 1ith validation split. We averaged the results over the other 10 splits. We ran all experiments on CPU (Intel(R) Xcon(R) CPU
16

---

Visual Sudoku
4 4
9 9
CNN
51.5 + 3.34
51.2 2.20
NeuPSL
28
89.7 2.20
51.5 - 1.37
A-NeSI
33
89.8 2.08
62.3 2.20
DeepSoftLog
94.2 1 1.84
65.0 + 1.94
Table Accuracy on visual sudoku classification. Previous results are adapted from
E3-1225 v3 @ 3.20GHz). The x 4 and 9 runs took about 95 and 630 seconds per experiment respectively.
Table 8 summarizes the results of DeepSoftLog and compares them with current state-of-the-art. Surprisingly, the crude fuzzy approximation outperforms all existing systems by a considerable margin.
4 X
9 9
optimizer learning rate
AdamW
Adam
0,00162
0.000671
training epochs
100
300
weight decay
0.0000144
0.000116
batch size
gradient clipping
2.445
2.753
embedding dimensions
10
10
Table 9: Hyperparameters for the visual sudoku experiments.
17


Reviews:
[{"review_id": "ga9lLWjzjh", "reviewer": "Reviewer_nJ1y", "summary": "This work proposes DeepSoftLog, a neuro-symbolic framework that generalizes ProbLog by combining soft-unification with probabilistic semantics. It first defines some properties of the soft-unification that it believes to be required for meaningful semantics and efficient training. Further, it examines some of the existing neuro-symbolic systems and shows that they satisfy a few but not all of the defined properties. In contrast, the proposed DeepSoftLog is able to satisfy all the properties. In the empirical evaluations, three experiments are performed where the proposed DeepSoftLog is able to outperform the baselines for the first two. ", "questions": "- Can the authors provide more motivations on why the four properties of soft-unification can improve performance and some analysis on how they affect complexity?\n- Can the authors explain how the soft-unification scores are incorporated during inference?\n- I don't understand the example in the introduction: what is the meaning of Listing 1, what are the ~newstate1 & ~newstate4, and why DeepSoftLog would learn to set ~newstate1 = ~state2 & ~newstate4 = ~state1?\n- Why there's no baseline for experiment in Sec. 5.3?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical analysis of learnable soft-unification is technically sound and is potentially interesting to the other neuro-symbolic systems where unification is present. From the first two experiments, the proposed DeepSoftLog achieves significant improvements and also ablation study on the proposed soft-unification properties is included. The paper has provided sufficient background for the readers to understand this work.", "weaknesses": "- My main concern is that the technical details are not clear to me. From Algorithm 1, it is unclear how the score in soft unification is set; how the soft-unification is incorporated during inference and knowledge compilation step is not explained while this is key to understanding the probabilistic semantics of soft-unification.\n- Another concern is that the motivation for the soft-unification is not adequately justified. I want to see more about why the defined four properties can improve performance and why soft unification with the defined four properties can outperform the other neuro-symbolic systems. Also, I wonder how these properties affect computational complexity.\n- At Line 165, both s(x, y) and s(y, z) are real numbers in [0, 1]. I wonder what a conjunction of two numbers means.\n- Both \\land-transitive and \\times-similarity are not defined, while they are used in Theorem 2&4 respectively.\n- In Definition 3, should it be that x \\neq z.\n- Authors should justify why there's no baseline included in the differentiable finite state machine experiment in Sec. 5.3 to make the empirical evaluation thorough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We first sincerely thank the reviewer for taking the time to read and review our paper.\n\n> I don't understand the example in the introduction: what is the meaning of Listing 1, what are the ~newstate1 & ~newstate4, and why DeepSoftLog would learn to set ~newstate1 = ~state2 & ~newstate4 = ~state1?\n\nFirst we note that ~new_state1 and ~new_state4 on line 39 should have been ~prev_state1 and ~prev_state2 respectively. We apologize for this typo.\n\nThe example in Listing 1 implements a finite state machine in DeepSoftLog. However, the states (e.g. ~state1 or ~prev_state2) are not purely symbolic but are represented with embeddings. Hence DeepSoftLog can learn the transitions of the automata from data. In this example, DeepSoftLog can create a transition from state 1 to state 2 by assigning the same embedding to ~prev_state1 and ~state2. During training, we optimize these embeddings by giving positive and negative examples, and minimizing the cross-entropy loss with gradient descent (see experiment in section 5.3, where the automata is learned jointly with the perception).\n\n> My main concern is that the technical details are not clear to me. From Algorithm 1, it is unclear how the score in soft unification is set; how the soft-unification is incorporated during inference \n> Can the authors explain how the soft-unification scores are incorporated during inference?\n\nA main contribution of the paper is that soft-unification can be transformed into probabilistic logic by explicitly encoding the soft-unifications as probabilistic facts. As an example, suppose we have the following DeepSoftLog program:\n\n```\np(~a)\nquery :- p(~b).\n```\n\nThen we can transform it into an equivalent ProbLog program:\n\n```\n0.5 :: ~a ≃ ~b.\np(X) :- ~a ≃ X.\nquery :- p(~b)\n```\n\nSo after this transformation, which introduces the probabilistic fact  ~a ≃ ~b to implement soft unification,  we can do regular probabilistic inference. We explain this transformation more formally on lines 235-267. We also prove that this is equivalent to regular soft-unification (proof is in appendix C). Some more elaborate examples of this transformation are included in appendix B.\n\n> knowledge compilation step is not explained while this is key to understanding the probabilistic semantics of soft-unification.\n\nWe first want to stress that knowledge compilation (KC) is unrelated to the probabilistic semantics, but is the standard way to do probabilistic inference in probabilistic logics such as Problog. We chose not to introduce KC because (1) understanding it is not really relevant to the content of the paper, besides solving the disjoint sum problem, and (2) KC would require a fairly lengthy introduction. We refer to [3] for more details.\n\n> At Line 165, both s(x, y) and s(y, z) are real numbers in [0, 1]. I wonder what a conjunction of two numbers means.\n\nHow the conjunction is evaluated depends on the semantics. So e.g. for probabilistic logic, this conjunction is evaluated as a multiplication. This is explained in lines 166-167.\n\n> Both $\\land$-transitive and $\\times$-similarity are not defined, while they are used in Theorem 2&4 respectively.\n\nThe definitions of $\\land$-transitivity and $\\times$-similarity can be found on lines 165 and 168 respectively.\n\n> Another concern is that the motivation for the soft-unification is not adequately justified. I want to see more about why the defined four properties can improve performance and why soft unification with the defined four properties can outperform the other neuro-symbolic systems. \n> Can the authors provide more motivations on why the four properties of soft-unification can improve performance and some analysis on how they affect complexity?\n\nWe summarize the main points of how DeepSoftLog concretely improves the performance and how this relates to the proposed properties:\n- DeepSoftLog optimizes better compared to previous systems (e.g. NTP). This is mostly due to satisfying Def4. It has previously been shown [1] that gradient descent gets stuck in local minima if not all proof paths are updated simultaneously (see lines 151-158).\n- Def2 also improves the training stability by disallowing redundancy in the proof paths (see also the ablations in figure 2). \n- Soft-unification has so far been only used in fuzzy systems, while DeepSoftLog is based on probabilistic semantics. The use of probabilities as opposed to fuzzy values gives DeepSoftLog a performance advantage. Note that this is the only aspect that impacts the computational complexity (which is the same as for ProbLog, see section 7). This trade-off of fuzzy and probabilistic logic between performance and scalability is well-known in the literature.\n- Def3 has previously been found to be necessary to make the soft-unification sufficiently expressive [2].\nFor a more in depth discussion, we refer to section 3.\n\n> Why there's no baseline for experiment in Sec. 5.3?\n\nThis is a good point, and we also considered it. However, we are unaware of an existing neuro-symbolic framework that could properly implement this experiment, as it requires both learnable perception and learned structure. We have since implemented an RNN as a simple neural baseline. You can find the results in the pdf attached to the “Author Rebuttal”.\n\n> In Definition 3, should it be that x \\neq z.\n\nWe will correct this typo, thank you for noticing.\n\n[1]: de Jong, Michiel, and Fei Sha. \"Neural theorem provers do not learn rules without exploration.\" arXiv preprint arXiv:1906.06805 (2019).  \n[2]: Julián-Iranzo, Pascual, Clemente Rubio-Manzano, and Juan Gallardo-Casero. \"Bousi~ Prolog: a Prolog extension language for flexible query answering.\" Electronic Notes in Theoretical Computer Science 248 (2009): 131-147.  \n[3]: Fierens, Daan, et al. \"Inference and learning in probabilistic logic programs using weighted boolean formulas.\" Theory and Practice of Logic Programming 15.3 (2015): 358-401.\n"}, {"review_id": "UxI5igvhfI", "reviewer": "Reviewer_4neU", "summary": "This paper studies the notion of *soft-unification*, first employed by the Neural Theorem Prover to learn logic rules in an end-to-end differentiable manner. They outline several properties that need to hold for soft-unification to be semantically meaningful and efficiently trainable; properties which previous frameworks fail to satisfy. Consequently, the authors introduce a framework satisfying such properties, which they term *DeepSoftLog*, which is essentially an integration of embeddings (as opposed to symbols) with probabilistic logic programming.", "questions": "- Could you please explain what you meant by the paragraph on lines 204-208? \n- On lines 219-221 you mention that you need a neural network for every functor. I'm guessing this does not scale if you have a large logic program?\n- On lines 247-248 you mention that you \"do not actually ground the soft-unification function s, but provide it as a built-in\". Could please clarify what you mean by that? It is my understanding that when compiling into a circuit, everything is grounded?\n- On lines 259-260 you mention that \"An important constraint we apply is the soft-unification predicate needs to be ground upon evaluation\". Could you clarify what that means? Is that not at odds with the statement in the above question?", "limitations": "I believe the authors have adequately stated the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- While the idea of soft-unification is certainly not new, the authors tackle the problem in a principled manner by integrating\nembeddings with problog, a language for probabilistic logic programming.\n\n- The paper is very well written for the most part, with the authors using examples throughout to help elucidate the exposition.\n\n- While doing a good job with exposition, the authors also managed to stay rigorous throughout the paper, with definition and theorems throughout.\n\n", "weaknesses": "\n- I find the paper to be lacking in terms of experimental evaluation. The experimental section does not offer much that convinces me of the merits of proposed approach:\n\n  - The advantage of using probabilistic semantics as opposed to fuzzy semantics is well documented in the literature, which seems to be the main conclusion of section 5.1.\n\n  - I'm not really sure what the point of evaluating on MNIST-addition is. The authors seems to be using it to argue for the scalability of their approach. However, I don't see how their approach is more scalable compared to DeepProbLog since they incur an extra branching factor owing soft-unification. They mention the use of approximate inference techniques, but then they have to deal with the pitfalls of sparse gradients, but is understandable given the intractability of exact inference. Furthermore, since such approximations were not proposed by the authors, it seems only fair to also utilize them when comparing against DeepProbLog.\n\n  - Section 5.3 is to me, maybe what this entire paper is all about. However, I feel it would need to be expanded considerably.\n\n- There has been a lot of work on Neuro-Symbolic AI, and in my opinion, the related works section does not do it justice.\n\nTypos:\n- I believe line 87 should read as \"(2) Disjoin the proofs...\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We want to sincerely thank the reviewer for taking the time to read and review our paper. We are happy to hear that the reviewer found the paper very well written.\n\n> I'm not really sure what the point of evaluating on MNIST-addition is. The authors seems to be using it to argue for the scalability of their approach. However, I don't see how their approach is more scalable compared to DeepProbLog since they incur an extra branching factor owing soft-unification. They mention the use of approximate inference techniques, (...). Furthermore, since such approximations were not proposed by the authors, it seems only fair to also utilize them when comparing against DeepProbLog.\n\nWe will try to make this more clear in the paper.\n- First, we stress that the MNIST-addition experiment does not use approximate inference techniques but is exact (see line 299). Our solution to MNIST-addition uses a different encoding compared to DeepProbLog, which avoids the combinatorial explosion for higher digits. \n- The new, more efficient encoding relies on embeddings. When such an encoding can be used, this \"tensorization\" is asymptotically faster (comparable to lifted inference vs ground inference). You are right that this could also be done in DeepProbLog if the implementation supports embeddings and neural functors, but this would just give you a very similar system to DeepSoftLog.\n- The authors believe this experiment is relevant to the community as it shows that MNIST-addition is solvable exactly in linear time in the number of digits, which has not been demonstrated before. This suggests that the use of embeddings in neuro-symbolic methods can be very powerful.  It also suggests that the MNIST-addition experiment (one of the most common neuro-symbolic benchmark) actually rather easy when embeddings can be used.\n\n> Section 5.3 is to me, maybe what this entire paper is all about. However, I feel it would need to be expanded considerably.\n\nWe agree that this experiment is the most interesting setting for DeepSoftLog. We have since performed experiments on more grammars and added a neural baseline (You can find the expanded section 5.3 in the pdf attached to the Author Response). On the other hand, these experiments are limited significantly due to the scalability of knowledge compilation and would require approximation techniques to properly scale up, which we leave for further research. \n\n> Could you please explain what you meant by the paragraph on lines 204-208?\n\nIn this paragraph, we motivate our concrete choice for the soft-unification function s. Theorem 5 gives us the exponential form for s, but the choice of distance function d is still open. We use the angular distance (i.e. arcos of cosine similarity) as this optimizes well. But as the soft-unification function is the negative exponential of the distance function (theorem 5), this would mean that the minimal soft-unification is achieved when two vectors lie opposite on the sphere. In other words, we can pack very few symbols in our embedding space, before they all start to soft-unify with each other, which is undesirable (creates big branching factors, or requires high embedding dimensions). By taking an absolute value, the minimum soft-unification is achieved by orthogonal vectors, which means we get exponentially more positions with low soft-unification.\n\n> On lines 219-221 you mention that you need a neural network for every functor. I'm guessing this does not scale if you have a large logic program?\n\nIf you have a very large number of different functors, this could indeed become a problem. In our experience, this has not been an issue because in practice the more pressing concern for scalability is the probabilistic inference.\n\n> On lines 247-248 you mention that you \"do not actually ground the soft-unification function s, but provide it as a built-in\". Could please clarify what you mean by that? It is my understanding that when compiling into a circuit, everything is grounded?\n\nYou are correct that when compiling a circuit, everything is grounded. What we mean is that we do not explicitly create the full grounding of the soft-unification function, as most of these soft-unifications would not be used. Instead, our implementation provides a built-in that generates these facts as needed. \n\nCompare this with how in ProbLog, a first-order rule also has a large (or infinite) number of groundings, but only the subset that is actually needed for the query is generated  (a concept known as the relevant grounding).\n\n> On lines 259-260 you mention that \"An important constraint we apply is the soft-unification predicate needs to be ground upon evaluation\". Could you clarify what that means?\n\nConsider this DeepSoftLog program:\n\n```\np(~a).\nquery :- p(~X).\n```\n\nIn this example, if we query `query`, the variable `X` does not get instantiated before we arrive at the soft-unification (between `~a` and `~X`). This is still well-defined: `X` could be instantiated with every possible element in the domain, but this usually results in an infinite amount of unifications. To avoid this problem, we constrain our inference to cases where this X would be already instantiated. Otherwise, we throw a runtime error.\n\nNote that this is very similar to regular ProbLog, where you can have first-order probabilistic facts, as long as the grounding with respect to the query is finite.\n\n> I believe line 87 should read as \"(2) Disjoin the proofs...\"\n\nWe will correct this mistake, thank you for noticing.\n"}, {"review_id": "222ijiTmc8", "reviewer": "Reviewer_bQCz", "summary": "This work proposes a neural symbolic framework, DeepSoftLog, which extends DeepProbLog with a soft equivalent operation. \nThe authors also develops four properties that such a soft equivalency operation should hold. \nThe experimental results demonstrate that DeepSoftLog has better performance than the state-of-the-art baselines.", "questions": "Can you address what are the benefits that the four properties bring?", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Originality: 2/5\nThe idea of soft equivalency is not new, which has been adopted by works such as NTP. \nAlthough the authors raise a novel suite of 4 standards that a good soft equivalency function should enjoy, they have not developed deep enough from these definitions, to discuss the theoretical benefits that these properties could bring, such as convergence, relaxation, and learning efficiency.\n\nQuality: 2/5 \nPros: The authors provide proof that the soft equivalency function satisfies all four properties.\nCons: In the experiment section, all images are encoded with one-hot embedding, which is quite problematic. This embedding not only creates an unfair comparison against the baselines but is also not meaningful for future references.\n\nClarity: 3/5 \nPros: The writing is pretty clear and the four properties are quite easy to understand.\nCons: The program syntax is hard to understand and not quite user-friendly. For example, p(~x):- q(~y) is not intuitive to understand, as y is not used in the head, and a new, unknown variable is introduced in the context. \n\nSignificance: 1/5\nThe theory part is not developed in-depth enough, which undermines the necessity of why the properties are required. \nFurther, although the experiment results outperform the SOTA quite a lot, the embedding is synthesized, which also undermines the credibility of the result.", "weaknesses": "See \"Strength\" section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for taking the time to read and review our paper. We will address the reviewer's comments, ordered by topic.\n\n> In the experiment section, all images are encoded with one-hot embedding, which is quite problematic.\n\nThe authors want to stress that the images are embedded by a neural network and are _not_ one-hot encoded. Perhaps the statement in appendix D1 was confusing, which says that the digits for the (symbolic) ground truth labels are represented as one-hot vectors. We will clarify this sentence.\n\n> Further, although the experiment results outperform the SOTA quite a lot, the embedding is synthesized, which also undermines the credibility of the result.\n\nWe stress again that the embeddings in all experiments are learned from data by gradient descent. This is stated e.g. in the introduction when we say that we are \"using learnable embeddings\".\n\n> \"The program syntax is hard to understand and not quite user-friendly.\"\n\nWe adopt the syntax of the Prolog language (with some very minor additions), which we summarize in section 2.1. Prolog is by far the most popular and well-known language to represent logic knowledge and has been extensively used for this purpose. We therefore feel it is a natural choice for this paper, as it builds on the probabilistic and neural extensions of Prolog: ProbLog and DeepProbLog.\n\n> \"For example, p(x):- q(y) is not intuitive to understand, as y is not used in the head, and a new, unknown variable is introduced in the context.\"\n\nWe follow the Prolog convention where lowercase symbols are constants (see section 2.1). So `x` and `y` are not variables here. The rule `p(x) :- q(y).` means that if the atom `q(y)` is true, the atom `p(x)` is also true.\n\n> \"The theory part is not developed in-depth enough, which undermines the necessity of why the properties are required.\"\n> \"Although the authors raise a novel suite of 4 standards that a good soft equivalency function should enjoy, they have not developed deep enough from these definitions, to discuss the theoretical benefits that these properties could bring, such as convergence, relaxation, and learning efficiency.\"\n\nWe address the specific points that are mentioned.\n- (Convergence) Giving proper convergence proofs for gradient-based optimization is very challenging, and often even impossible for neural network based systems [1]. We note that the related frameworks in neuro-symbolic AI also do not provide this. We do discuss local minima and gradient flow of our method and compare it with previous fuzzy methods (see e.g. lines 151-158 and 199-203).\n- (Relaxation) Soft-unification is indeed a relaxation of the regular (i.e. hard) logic. This is known and has been shown in previous work [2].\n- (Learning efficiency) We do make claims about the learning efficiency. Most crucially, our method gives gradients to all embeddings during a training step (disregarding critical points), while previous methods which used the Godel t-norm only give a gradient to at most 2 embeddings. We also demonstrate this empirically, see the ablations in figure 2.\nIf there are other concrete points where the reviewer feels our theoretic analysis is lacking, we would be happy to address those.\n\n> Can you address what are the benefits that the four properties bring?\n\nWe summarize the important benefits. An in-depth discussion can be found in section 3.\n- DeepSoftLog optimizes better compared to previous systems (e.g. NTP). This is mostly due to satisfying Def4. It has previously been shown [1] that gradient descent gets stuck in local minima if not all proof paths get updated simultaneously (see lines 151-158).\n- Def2 also improves the training stability by disallowing redundancy in the proof paths (see also the ablations in figure 2). \n- Soft-unification has so far been only used in fuzzy systems, while DeepSoftLog equips probabilistic semantics. The use of probabilities as opposed to fuzzy values gives performance advantages. Note that this is the only aspect that impacts the computational complexity (see section 7). In summary, the computational complexity is the same as for ProbLog. The trade-off of fuzzy and probabilistic logic between performance and scalability is well-known in the literature.\n- Def3 has previously been found to be necessary to make the soft-unification sufficiently expressive [4].\n\n[1]: Swirszcz, Grzegorz, Wojciech Marian Czarnecki, and Razvan Pascanu. \"Local minima in training of neural networks.\" arXiv preprint arXiv:1611.06310 (2016).  \n[2]: Sessa, Maria I. \"Approximate reasoning by similarity-based SLD resolution.\" Theoretical computer science 275.1-2 (2002): 389-426.  \n[3]: de Jong, Michiel, and Fei Sha. \"Neural theorem provers do not learn rules without exploration.\" arXiv preprint arXiv:1906.06805 (2019).  \n[4]: Julián-Iranzo, Pascual, Clemente Rubio-Manzano, and Juan Gallardo-Casero. \"Bousi~Prolog: a Prolog extension language for flexible query answering.\" Electronic Notes in Theoretical Computer Science 248 (2009): 131-147.\n"}]

Author rebuttal:
As was requested by some reviewers, we have expanded section 5.3 with additional experiments and a neural baseline. We have attached the new section 5.3 as a pdf.

Meta-review: First of all, thanks for understanding we are one review short on this one. It is an exceptional circumstance. After careful discussion, we are clear on this paper’s acceptance. Though soft unification of logic is certainly not a novel idea in this community, the reviews and senior reviewers all agree that this paper is rigorous and the proposed method is insightful. Still, we would like to note two aspects for further improvements. First of all, the empirical results are not convincing enough. Though MNIST-addition is a well-adopted setting in our community, the benefit of adopting this experiment is not really in favor of this paper. The reviews suggest that this argues for scalability of the proposed method. However, the empirical results do not fully back up this claim. We would highly recommend this paper to continue exploration an additional experiment setting. It is not just this paper’s duty, but we as the whole community needs to keep working on it so that principled neuro-symbolic methods can be more well accepted into other domains. Secondly, the theoretical parts can be more elaborate. The current analysis does not justify the necessaries of the four properties. What exactly benefits do those four properties bring to this method, and where can this benefit be fully demonstrated?
Decision: Accept (poster)