Differentiable Logic Machines
Authors: Matthieu Zimmer
Xuening Feng
Claire Glanois
Zhaohui JIANG
Jianyi Zhang
Paul Weng
Dong Li
Jianye HAO
Wulong Liu
Venue: Accepted by TMLR ()

Abstract: The integration of reasoning, learning, and decision-making is key to build more general artificial intelligence systems. As a step in this direction, we propose a novel neural-logic architecture, called differentiable logic machine (DLM), that can solve both inductive logic programming (ILP) and reinforcement learning (RL) problems, where the solution can be interpreted as a first-order logic program. Our proposition includes several innovations. Firstly, our architecture defines a restricted but expressive continuous relaxation of the space of first-order logic programs by assigning weights to predicates instead of rules, in contrast to most previous neural-logic approaches. Secondly, with this differentiable architecture, we propose several (supervised and RL) training procedures, based on gradient descent, which can recover a fully-interpretable solution (i.e., logic formula). Thirdly, to accelerate RL training, we also design a novel critic architecture that enables actor-critic algorithms. Fourthly, to solve hard problems, we propose an incremental training procedure that can learn a logic program progressively. Compared to state-of-the-art (SOTA) differentiable ILP methods, DLM successfully solves all the considered ILP problems with a higher percentage of successful seeds (up to 3.5x). On RL problems, without requiring an interpretable solution, DLM outperforms other non-interpretable neural-logic RL approaches in terms of rewards (up to 3.9%). When enforcing interpretability, DLM can solve harder RL problems (e.g., Sorting, Path) than other interpretable RL methods. Moreover, we show that deep logic programs can be learned via incremental supervised training. In addition to this excellent performance, DLM can scale well in terms of memory and computational time, especially during the testing phase where it can deal with much more constants (>2x) than SOTA.

Published in Transactions on Machine Learning Research (07 /023)
Differentiable Logic Machines
Matthicu Zimmer
malthiee..bmmmerrhaansscooo
Huowei Nooh's 's Ark Lab, London, United Kingdom.
Xuening Feng
cindyfeng@80198sjuu.cuu
UM-SJTU Joint Institute, Shanghai Jiao Tong University, Shanghai, China.
Claire Glanois
cigl@ita. dk
IT University of Copenhagen, Copenhagen, Denmark.
Zhaohui Jiang
finnghaaohui@jjlu.dd... edu.cn
UM-SJTU Joint Institute, Shanghai Jiao Tong University, Shanghai, China.
Jianyi Zhang
zhangigf77@ssiu..duuom
UM-SJTU Joint Institute, Shanghai Jiao Tong University, Shanghai, China.
Paul Weng
UM-SJTU Joint Institute, Shanghai Jiao Tong University, Shanghai, China.
Dong Li
bidong1106@hwwsees..comm
Huowei Nooh Ark Lab, China.
Jianye Hao
Maojannye@euaweiicco
Huowei Nooh's 's Ark Lab, China. School of Computing end Intelligence, Tianjón University, China
Wulong Liu
liwwalong wlw.llonngguuuuee.commm
Huowei Noah's s Ark Lab, Canada.
Reviewed on OpenReview:
httpes//opennrerivu.nett/// http://iew...eeeooooommmdddaaaaa
Abstract
The integration of reasoning, learning, and decision-making is key to build more general artificial intelligence systems. As a step in this direction, we propose a novel ncural-logic architecture, called differentiable logic machine (DLM), that can solve both inductive logic programming (TI.P) and reinforcement learning (RT) problems, where the solution can be interpreted as first-order logic program. Our proposition includes several innovations. Firstly, architecture defines restricted but expressive continuous relaxation of the space of first-order logic programs by assigning weights to predicates instead of rules, in contrast to most previous neural-logic approaches. Secondly, with this differentiable ar- chitecture, we propose several (supervised and RL) training procedures, based on gradient descent, which can recover a fully-interpretabble solution (i.e., logic formula). Thirdly, to accelerate RL training, we also design a novel critic architecture that enables actor-critic algorithms. Fourthly, solve hard problems, we propose an incremental training procedure that can learn logic program progressively. Compared to state-of-the-ate (SOTA) differen- tiable ILP methods, DLM successfully solves all the considered ILP problems with higher percentage of successful seeds (up to 3.5x). On RL problems, without requiring an inter- pretable sonution, DLM oulperforms other non-inlerpretable neural-logie RL approaches in terms of rewards (up to 3.9%). When enforcing interpretability, DLM can solve harder RL problems (c.g., Sorting, Path) than other interpretable RL methods. Morcover, we show that deep logic programs can be learned via incremental supervised training. In addition to this excellent performance, DLM scale well in terms of memory and computational

---

Published in Transactions on Machine Learning Research (07/2023)
time, especially during the testing phase where it can deal with much more constants (>2x) than SOTA.
1 Introduction
Following the successes of deep learning and deep reinforcement learning, research trend (Dong et al, 2019 Jiang & Luo 2019 Manhaeve et al. 2018), whose goal is to combine reasoning, learning, and decision- making into one architecture has become very active. This research may unlock the next generation of artificial intelligence (AI) (Lake et al.) 2017 Marcus 2018). Simultaneously, a second research trend has flourished under the umbrella term of explainable Al Barredo Arrieta et al. 2020). This trend is fueled by the realization that solutions obtained via deep learning-bassee techniques are difficult to understand, debug, and deploy. Notably, interpretability crucial high-stake domains (c.g., autonomous driving), where the decisions made by a trained model should be understandable.
In this context, neural-logic approaches (see Section 2 have been proposed to integrate reasoning and learn- ing, notably via first-order logic and neural networks. Recent works have demonstrated good achievements by using differentiable methods to learn a logic program (Evans & Grefensteute 2018) or by applying a logical inductive bias to create a neural-logic architecture (Dong et al. 2019). The latter approach currently obtains the best performance at the cost of interpretability, while the former can yield an interpretable solution, but at the cost of scalability. Therefore, one important research problem regards the design of an efficient method with good performance and better scalability while preserving interpretability. The main motivation of our work is to provide such algorithm.
In this paper, we propose a novel neural-logic architecture (see Section 3 for background notions and Section 4 for our proposition) that offers a better tradeoff in terms of interpretability vs. performance and scalability. This architecture defines a continuous relaxation over first-order logic expressions defined on input predicates. In contrast to most previous approaches (see Section 2). one key idea is to assign learnable weights on predicates instead of template rules, which allows for a much better scalability. This architecture can be trained both in the supervised learning (SL) and reinforcement learning (RL) scttings for which we introduce several training techniques to find interpretable solutions. Notably, to accelerate the RL training, adapted critic to train our architecture in actor-critic scheme. In addition, to help scale further the approach, we propose an incremental training methodology that can be applied to both SL and RL training.
propose
We experimentally compare our proposition with peviiously-proossee neural-logic architectures in both the SL. and RT settings on inductive logic programming (II.P) and RL tasks respectively (see Section 5 Our architecture can achieve state-of-the-art (SOTA) performances in both ILP and RL tasks while maintaining interpretability and achieving better scalability. More precisely, our proposition is superior to all considered interpretable methods in terms of success rates, computational time, and memory consumption. Compared to non-interpretable ones, our method compares favorably, but can find fully-interprotable solutions (i.c.,
logic programs) that are faster and use less memory during the testing phase.
The contributions of this paper can be summarized as follows: (1) a novel neural-logic architecture that can produce an interpretable solution and that can scale better than SOTA mothods, (2) several training algorithms to obtain an interpretable solution, and (3) a thorough empirical evaluation in both RL and ILP tasks. Hence, to the best of our knowledge, our approach is the first neural-logic method able to output the end of training a fully-interpretable solution for complex tasks like Path Blocksworld.
2 Related Work
The literature aiming at integrating reasoning, learning, and possibly decision-making is very rich. Our work is related to statistical relational AI (De Raedt et al. 2016), which aims at combining relational reasoning and learning. However, a key difference is that our focus is to learn a logic program, although we have a probabilistic interpretation of predicate evaluations. Our work is also related relational RL (Džcroski] et al. 2001 Tadepalli et al. [0004] van Otterlo 2012), whose goal is combine RL with First- Order Logic (FOL)) representation. To the best of our knowledge, such approach does not scale well as those resorting
2

---

Published in Transactions on Machine Learning Research (07/2023)
to neural networks. Thus, the investigation of neural approaches to tackle this integration has become very
active in recent years (de Raedt. et. al. 2020 d' d'Avila Garcez et al. 2019 Besold et al. 2017). For space reasons, we focus on the recent work closest to ours below.
(Differentiable) ILP and their extensions to RL II.P (Muggleton 1991 Cropper et al. 2020 aims to extract lifted logical rules from examples, Since traditional ILP systems can not handle noisy, uncertain or ambiguous data, they have been extended and integrated into neural and differentiable frameworks. For instance, Evans & Grefenstette (2018) proposed éILP, a model based on a continuous relaxation of the logic reasoning process, such that the parameters can be trained via gradient descent, by expressing the satisfiability problem of ILP as binary classification problem. This relaxation is defined by assigning weights to templated rules. .Jiang & Luo (2019) adapted èILP to RL problems using vanilla policy gradient. Despite being interpretable, this approach does not scale well in terms of both memory and computation, which is notably due to how the relaxation is defined.
Payani & Fekri (2019)) proposed differentiable Neural Logic ILP (dNL-ILP), another ILP solver where in contrast to dILP, weights are placed on predicates like in our approach. Their architecture is organized as sequence of one layer of neural conjunction functions followed by one layer of neural disjunction functions to represent expressions in Conjunctive Normal Form (CNF) or Disjunctive Normal Form (DNF), which provides high expressivity. In this architecture, conjunctions and disjunctions are defined over all predicates of any arity in contrast to DLM. Payani & Fekri (2019b) did not provide any experimental evaluation of dNL-ILP on any standard ILP benchmarks. But, in our experiments, our best effort to evaluate it suggests that dNT.-ILP performs worse than OIP. We believe this is due to the too generic form imposed on the logic program to be learned. Payani & Fekri (2020) extended their model to RL and showed that initial predicates can be learned from images if sufficient domain knowledge under the form of auxiliary rules is provided to the agent. However, they do not show that their approach can learn good policies without this domain knowledge.
Another way to combine learning and logic reasoning is to introduce some logical architectural inductive bias, as in Neural Logic Machine (NLM) (Dong et al., 2019). This approach departs from previous ones by learning rules with multilayer perceptrons (MLPs), which prevent this method provide any final interpretable solution. NLM can generalize and its inference time is significantly reduced compared to AILP; by avoiding rule templates as in traditional neural-symbolic approaches, it also gains in expressivity. Our architecture is inspired by NLM, but we use interpretable modules instead of MLPs
Since the search space of traditional and disferent ILP methods is often very different, it is difficult to produce a fair comparison. As far as we know, traditional ILP methods often rely on carefully hand-designed and task-specific templates which is less the case with our approach. This difficulty and the difference between these approaches may explain the limited comparative evaluation in past work on ILP (Law et al. 2018 Glanois et al., 2022). Glanois et al. (2022) state that traditional methods are superior to neuro-symbolic ones only when the dataset is small and frese In the RL setting, it is also not clear how to extend non-differentiable methods.
Other neural-symbolic approaches In order to combine probabilistic logic rcasoning and neural net- works, Manhaeve et al. (2018) proposed DeepProbLog, which exlends ProbLog De Raedt et al. (2007), a probabilistic logic language, with neural predicates. While this approach is shown to be capable of pro- gram induction, is not obvious how apply it for solving generic ILP problems, since partially-specifiedd programs need to be provided.
Another line of work in relational reasoning specifically targets Knowledge- Base (KB) reasoning. Although these works have demonstrated huge gain in scalability (w.r.t. the number of predicates or entities), they are usually less concerned about predicate invention Some recent works (Yang et al., 2017 Yang & Song 2020) extend the multi-hop reasoning framework to IIP problems. The latter work is able to learn more expressive rules, with the use of nested attention operators. In the KB completion literature, a recurrent idea is jointly learn symboli embeddings of entities and predicates, which are then used for approximate
TTypically, rules learned in KB reasoning are chain-like rules (l.e., paths on graphs), which form subset of Horn clauses: Q(x,)) Y) (x( Ps(71, 72) ^ ... (7, 7a))
3

---

Published in Transactions on Machine Learning Research (07/2023)
inference. However, the expressivity remains too limited for more complex ILP tasks and these works are typically more data-hungry.
3 Background
We present the necessary notions in ILP and RL. We also recall NLM, since our work is based on it.
3.1 Inductive Logic Programming (ILP)
ILP (uggleton 1991] refers the problem of learning a logic program that entails a given set of positive examples and does not entail given set of negative examples. This logic program is generally written in (a fragment of) FOL.
FOT, is a formal language defined with several elements: constants, variables, functions, predicates, and formulas. Constants correspond to the objects in the domain of discourse. Let C' denote the set of m constants (e.g., objects). They will be denoted in lowercase (e.g., o). Variables refer to unspecified constants. They will be denoted uppercase (e.g., X, Y, or Z). Functions allow denote some constants using other constants (e.g., s(0) may refer to 1). Like previous work, we consider a fragment of FOL without any functions. A predicale can be thought of a relation between constants, which can be evaluated true T false F. A predicate is said to be b-ary if it is relation between b constants. Note that O-ary predicate is simply Boolean value. Predicates will be denoted in uppercase (e.g., P or Q). Let P denote the set of predicates used for a given problem. An alom is an barr predicate with its arguments P(x,,...,,,, where &; are either variables or constants. For simplicity, we may refer to atoms as predicates when there no risk of confusion. A formula is a logical expression composed of atoms, logical connectives (e.g., negation 7, conjunction A, disjunction v, implication -), and possibly existential 3 and universal quantifiers.
Since solving ILP task involves searching exponentially large space, this problem is generally handled by focusing formulas of restricted forms, such subset of if-then rules, also referred to clauses. A definite clause is a rule of the form:
- Ak
which means that the head atom H is implied by the conjunction of the body atoms A A Horn clauses extend definite rules by allowing H to be possibly negated. More general rules can defined by allowing logical operations (e.g., disjunction or negation) in the body. A ground rule (resp. ground atom) is rule (resp. atom) whose variables have been all replaced by constants.
In ILP tasks, given some initial predicates (e.g., for natural numbers, Zero(X) meaning "X = 0", Succ XX, Y) meaning "X = Y + 1"), and a target predicate (c.g., Even(X) meaning "X is even"), the goal is to learn a logical formula defining the target predicate. Expressing directly this target predicate in terms of initial ones may require a very long logical formula, which may therefore be hard to learn. usual approach is to rely on predicate invention, which consists learning intermediate auriliary predicales with which the target predicate can be defined. Below, we show simple example of such predicate invention with the created auxiliary predicate (X (meaning "X Y + 2"):
Euen(X) - Zero(X) v (Succ2 (X,). A Even(Y)), Succ2(X, XY - Suco( X, Z) Suce (Y))..
3.2 Reinforcement Learning (RL)
For any finite set X, lct A(X) denote the set of probability distributions over X. The Markou Decision Process (MDP) model (Bellman) 1957 is defined as a tuple T,,,, 7), where S is a set of states, A is a set of actions, T: x A A(S) is a transition function, r A + IR is a reward function, μ E A(S) is a distribution over initial states, and y e [o, 1) is discount factor. A (stationary Markov) policy S A(A) is a mapping from states distributions over actions; T(a s) stands for the probability of taking action a given state We consider parametrized policies no with parameter 0 (e.g., neural networks). The aim in
4

---

Published in Transactions on Machine Learning Research (07/2023)
discounted MDP settings is to find policy maximizing the expected discounted total reward:
((0) E Tu
Σ ((r(st,a)) an)
(1)
where T, me is the expectation w.r.t distribution μ,, transition function T, and policy ne. The state value function of a policy wo for state is defined by:
v (s)
Br,
Σ rrr(s = s
(2)
where mx is the expectation w.r.t. transition function T and policy тo. defined by:
The action value function is
(s, ET 7'r(st, at) 80 8,00 a)
and the advanlage function [Sutton Barlo 2018 defined by:
(x, (s a) - (s).
RL (Sutton & Barto 2018). which based on MDP, is the problem of learning a policy that maximizes the expected discounted sum of rewards without knowing the transition and reward functions. Policy Gradient (PG) methods constitute widespread approach for tackling RL problems in continuous large state-action spaces. They are based on iterative updates of the policy parameter in the direction of (policy) gradient expressed as:
VoJ(O) =
(s. a) Vo log no(a {+]]
where the expectation is taken w.r.t. (s) = E., u(so) E 7 s|so), the discounted state distri- bution induced by policy тœ- Algorithms like REINFORCE (Willimss 1992) that estimate this gradient via Monte Carlo sampling are known to suffer from high variance (due to the stochasticity the environment and/or policy) Sutton & Barto (2018). To address this issuc, actor-critic (AC) schemes (Konda Tsitsiklis/ 2000) have been proposed. In such framework, both an actor (Tτ) and a critic (e.g., depending on the AC algorithm, v (Sutton & Barto 2018 Schulman et al. (017)or Q" (Lillicrap et al. 2016 Mnih et al. 2016). from which A can be estimated) are jointly learned. Using a critic to estimate the policy gradient reduces variance, but at the cost of introducing some bias.
Prosimal Policy Oplimization (PPO) (Schulman et al. 2017 is a SOTA AC algorithm, which optimizes a clipped surrogate objective function (P):(O);
E
ml a,), (0)
where 0 is the parameter of the policy that generated the training data, wr (i tatallia (sx)
8x) the advantage
function A is estimated with Generalised Advantage Estimation (GAE) (Shuulan et al. 2016 and clip(:,)) is the function to clip between [] - 4,1+]], This surrogate objective was motivated as an approximation
of that used in Trust Region Policy Optimization (TRPO) (Schulman et al. 2015), which was introduced to
ensure monotonic improvement after a policy parameter update. Some undeniable advantages of PPO over TRPO lie in its simplicity and lower computational and sample complexity.
3.3 Neural Logic Machine (NLM)
NLMs (Dong et al. 2019 are neural networks designed with a strong architectural inductive bias to solve ILP (and RL) problems. The NLM architecture is composed of ML.Ps organized in hicrarchical fashion. Its input corresponds to the initial predicates and its output corresponds to the target predicate. The MLPs approximate logic operations and define invented auxiliary predicates based previously-created initial
5

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Leyer (Irpu))
Layer1
Layer L (Oulpul)
Layer
Brondth b-1
Breadth b-1
and
Breadth
Breadth
Breadth b+1
Breadth
(a) High-level architecture of NLM (and DLM) zoomed in around breadth b, where boxes represent computation units (except for layer 0), blue arrows correspond to reduction, and yellow arrows expansion. Permutation is applied the imputs of each computation unit.
(b) A DLM computation unit at breadth b and layer I. Af- ter the NLM operations (le., reduction, expansion, and per- mutation), negation (green arrow) and preservation (violet arrow) with true (T) or false (F) are applied to generate the inputs of the logic modules.
Figure 1: (Left) High-level architecture NLM (and DLM), (Right) Computation unit DLM.
predicates. Thus, this architecture simulates forward chaining, a form of reasoning, which computes target predicate from the truth values of initial predicates via sequence of invented ones. Training NLM therefore approximates the inductive definition of logic formulas.
More specifically, an NLM is comprised of learnable computation units organized into L successive layers, each layer having a maximum breadth B (see Fig. Lap. A computation unit at layer / for given breadth corresponds some b-ary predicates and is connected to units the previous and next layers. An NLM processes aloms (i.e., predicates with all its arguments) represented tensors. For any barr predicate P, its corresponding tensor P, denoted in bold, is of order b with shape [m,..., m] (recall that m is the number of constants present in the ILP problem). For instance, the tensor representation of binary (b 2) predicate would be P [0, mmm A value .(. is) E [0, 1] (with iz {1...., m) and j e (1....,b)) is interpreted as the probability of the truth value of the corresponding grounded atom.
Apart from layer 0, which directly corresponds to the initial predicates, a computation unit at breadth e {0, .... B} and layer I E {1..... L} takes as inputs the b-ary predicates of set Qj and then outputs a set Pf of newly-invented b-ary predicates. For > O, the set Qj is obtained from the sets p of the previous layer according three operations: expansion, reduction, and permutation:
Expansion:
Any baary predicate P can be expanded into a (b+ 1)-ary predicate P, where the last argument does not play any role in its truth value, i.e., P(X P(. Xt). The set of expanded predicates obtained from P)-1 denoted P/-1
Reduction: Any (b+ l)arry predicate can be reduced into a bary predicate 1s by marginalizing out its last argument with existential (resp. universal) quantifier, i.c., P(XI....,, X₂) 3X,+, I(. X,,1) (resp. P( X₂) VXo+1 , X0+1)). Those operations (resp. min) on the corresponding component, i.e., P(i,,..., is) max, P(i...... (a. (resp. P(i is)
tensors are performed by max
=min, ((..).......).. The set of reduced predicates obtained from Pl-1 is denoted p
Permutation:
Let S, be the set all permutations of {1, b} for be (1...., B). For a given b ary predicate P and a given permutation a S,, Po.X,.... X2) = P(X arguments allows build more expressive formulas.
Permuting
In blocks world enviroumend, consider the Unslack lask where the goal is to move all the blocks on the floor. Therefore, a constant in C is a block. The current configuration of the blocks can be described by the following initial predicates: IsFloor(X) (i.e., true if X the floor), On(X, Y) (i.e., true if X is on Y), and Top(X) (i.e., true if there no block on X). The target predicate Move(X, (x,e Y) be learned indicates which block X could be moved on Y so that the next configuration of the blocks is closer to
Example 1.

---

Published in Transactions on Machine Learning Research (07 2003))
the goal specified by the Unstack task. A possible solution is:
Move( X, Y) - IsFloor(Y) Top(X) 32, P(X, 2), P(X,Y) - On(X, A '2, O0(OOn(Y))))) Z),
where P is an invented predicate, which can be formulated thanks those three previous operations. Indeed, reduction applied on On yield Q(Y) 3Z, On(Y, Z). Applying expansion it yields VX, X) Q(Y). Using permatation a that swaps two arguments gives Qx(X,Y) - Q(Y, Finally, P can be expressed with On(X,Y) Y) and (X,Y).
The input predicates of a computation unit at layer 1 and breadth b are therefore the elements of set % = (Po P P P p E 8 assuming Pj = Ø and P PB1 = Ø. computation unit outputs no new predicates, which form the elements of set Pj of b-ary predicates invented at layer 1. For each such predicale, a corresponding MLP computes its outputs: its evaluation for any given grounding (i.e., its arguments 0I....,o, o,)) is computed with the same MLP using as inputs all predicates in 2 grounded on 01,...,05, Ob. Thus, the NLM architecture is independent of the number of constants and therefore a trained network can be applied on new instances with any number of constants.
NLM offers expressive neural network architecture, whose model complexity is controlled by setting the number L of layers, breadth B, and number no of output predicates of the computation units, in addition to the MLP size. However, by using MLPs, NLM cannot provide an interpretable solution after training.
4 Differentiable Logic Machine (DLM)
We present our novel neural-logic architecture, called Differentiable Logic Machines (DLM), which offers a good trade-off between expressivity and trainability. We first discuss its architecture, then present several training methods, and finally explain how to extract interpretable solutions.
4.1 Architecture
At a high level, DLM has a similar architecture (Fig. lab as NLM (Dong et all 2019). i.c., it contains computation units organized into a hierarchical fashion with breadth B and I. layers. In contrast to NLM, the computation units correspond to soft logic operators, which means that DLM defines a continuous relaxation over FOL programs. Next, we explain the three main innovations in DLM and compare its computational complexity with respect to other related neural-logic methods. In Appendix A provide further discussions about DLM, notably its interpretation, expressivity, and implementation details.
Innovations The first two innovations correspond to two novel operations, negation and preservution, which we introduce to increase expressivity. They are used in addition to the three operations in NLM (expansion, reduction, and permutation) to compute the input predicates of computation unit. For the third innovation, we replace the MLPs of NLM's computation units by logic modules to promote interpretability. We present the two operations next, and then describe the logic modules:
Negation:
On any set of predicates P, this operation yields the set (7P) containing the negation of the predicates in P. On tensor representations, the negation is computed via the involutive function f(x) x applied component-wisely.
Preservation: To add more flexibility in the architecture, we augment any set of predicates P with T or F, which can be seen as a predicate that is always true or false respectively. The rationale for introducing those constant predicates T and notably to allow predicate one layer to be preserved for later layer (sce Example below).
From the set Øf of input predicates computed with expansion, reduction, and permutation, the application of negation and preservation yields four sets 0 U (T), Ø, (F), n(Q)) u (T), and ny( (()) (F). The union of these sets, denoted Ry is used as input of logic module, which explain next.
7

---

Published in Transactions on Machine Learning Research (07/2023)
Logic module: In DLM, computation unit (sce Fig. [b] at layer I and breadth b outputs no new predicates like in NLM. However, in contrast to NTM, each invented predicate is based on input predicates from R2 and is computed with a (soft) logic operator. For simplicity, we only use and and or, but other logic operators could be considered.
An and (resp. or) logic module at any layer and breadth outputs a conjunction (resp. disjunction) over RA terms of Ry which represents a predicate Cj((,,...,, Xo) (resp. D) (o(X) In terms of tensor, a conjunctive predicate C)( Xo) is computed with fuzzy and and is obtained as follows (for na 2, which easily extends to nA > 2):
C. - QOQ'
(3)
where Q = EPER upP, Q' = EP'RR up P', O is the component-wise product, wp E [0, 1J and wp E [0,1] are learnable weights for selecting prodicates and P' such that ΣPER; wp = and EpEERE Wp Similarly, a disjunctive predicate DI.,,...., Xb) is computed with a fuzzy or and is defined as follows (for nA = 2, which easily extends to nA 2):
D Q Q0Q'.
(4)
Each logic module (i.e., each conjunction or disjunction) has its own set of weights wp's 's (and wy 's), which are learned as softmax of parameters Op (and 0p:)) with temperature 7 as a hyperparameter:
exp(Op/T)
Wp EPERY exp(Or=TT)
(5)
Example 2. Assume n.A 2. Consider a blocks world environment with an invitial predicale: On(X, Y) (i.e., block X is on Y). If it were not initially provided, predicate Top(X) (i.e., block is X) could be learned thanks to the negation and preservation operations (in addition to reduction and permutation). Indeed, since Top(X) can be expressed as T -(3Y On(Y, it can be obtained as follows. As Q) contains a predicate P(X)= = 3Y On(Y,, X) (by reduction and permutation), an and logic module could express (op(X) as a conjunction of T E O U {T) (by preservation) and -P E n(()) (by negation). Since -P is on input predicate in R1 T (resp. F) can preserve vía and (resp. or) logic modules for the next layer.
Computational Complexity In one computation unit, the number of parameters grows as O(pnAnd) where p is the number of input predicates of the unit, na is the number of atoms used to define an invented predicate, and no is the number of output predicates invented by the unit. In comparison with related work (see Scction 2 to obtain the same expressivity, the alternative approach CILP (Evans & Grefenstette 2018) (and thus its extension to RL, NLRL (Jiang & Luo 2019 would need O( x no) because the weights are defined for all the na-combinations of p predicates. In contrast, dNI.-IL.P and NT. would be better with only Opmo). However, the components of dNL-ILP and NLM are not really comparable to those of our model or ØILP. Indeed, the NLM units are not interpretable, and the dNL-ILP architecture amounts to learning a CNF DNF formula, where component of that architecture corresponds to part of that formula. While expressive, the space of logic program induced in dNL-ILP is much less constrained than that in our architecture, making it much harder to train, shown in our experiments (see Table 4
Assuming that B (the maximum arity) is a small constant, the complete DLM network has ((TMARO²) parameters where L is the maximum number of layers. NLM has instead O(Lno²) parameters. The com- plexity of a forward pass in DLM is 8 Lnano²) where m is the number of constants. For NLM, it is O(m" B "Lno)) 2) (assuming that single-layer perceptrons are used). Once a logic program is extracted (see Section 4.3 can reduce the forward pass complexity to O(mPp) where p is the number of elements in the graph. Note that, by construction, p & Lno² & LNAnO?
4.2 Training
As a differentiable model, DLM can be trained in both the SL and RL settings. Since any computation unit directly corresponds to (possibly soft) logic expression, DLM is also independent of the number of
8

---

Published in Transactions on Machine Learning Research (07/2023)
constants: it can be trained on small number of constants and generalize to larger number. Next, we discuss supervised training, then present RI, training with actor-critic scheme. In addition, we also present an incremental training approach to tackle hard tasks. Apart from the latter incremental approach, the algorithms are quite standard. We present their pscudo-codes in Appendix A
4.2.1 Supervised Training
SL training can be applied to solve ILP tasks (see Section B.1 for concrete examples): Given a dataset D expressed with a set of constants C and the initial predicates in po = Ub Pg. learn to predict an r-ary target predicate pt, DLM can be trained by minimizing a binary cross-entropy loss (e.g,, via stochastic mini-batch gradient descent):
Co(P",p4)
Σ 01HH,,,EC
o,) log( (o),..,,))) (1 ( - p (oi,...,o)))
or))
where 0 corresponds to all the DLM parameters, pr (P is the output atom computed by DLM, and pe contains the grounded atoms given in D (i.e., all P(o 0o), Yb, vog...., E C, C. P.). As reported in previous ncural-logic work, this loss function generally admits many local optima. Besides, there may be global optima that reside in the interior of the continuous relaxation (i.e., not interpretable). Therefore, if we train our model with standard supervised (or RT training) technique, there is no reason that interpretable solution would be obtained, even if we manage to completely solve the task.
In order to help training and guide the model towards an interpretable solution, we propose to use three techniques: (a) inject some noise in the softmax defined in (5), (b) decrease temperature т during training,
and (c) use dropout. For the noise, we use a Gumbel distribution. Thus, the softmax in 5 replaced by Gumbel--offtma (Jang et al. 2017
exp((Gp+0r)/ 0r)/T EPERY exp((Gpr 0/r)
(6)
where Gp (and Gp.) are i.i.d. samples from a Gumbel distribution Gumbel(O, B). The injection of noise during training corresponds to a stochastic smoothing technique: optimizing by injecting noise with gradient descent amounts to performing stochastic gradient descent on a smoothed loss function. This helps avoid early convergence a local optimum and find global optimum. The decreasing temperature favors the convergence towards interpretable solutions. To further help learn an interpretable solution, additionally use dropout during training procedure. Dropout helps learn more independent weights, which also promotes interpretability. The scale B of the Gumbel distribution and the dropout probability are also decreased with the temperature during learning.
4.2.2 Actor-Critic (AC) Training
For RL tasks (see Section 5 for concrete examples), states are assumed to be encoded with given set C of constants and the initial predicates in pD = U, Ph. while action selection can be expressed by an b-ary action predicate PA, i.e., PA(oi...., 0%) corresponds to an action. In contrast to ILP, the truth values of grounded atoms (describing a state) may change after performing an action to reflect a new state. The RL problem consists in learning a policy that takes as inputs po (all the grounded atoms of the initial predicates) and that returns an action predicate such that the expected cumulative reward ① maximized by selecting actions according to the action predicate.
Example 3. Consider blocks world environment with the initial predicate On(X, Y) (L.e., block X is on Y). The state is defined by all the slate aloms (i.e., ground predicales), e.g., keeping only the posilive ones, On(a, b) and On(b, floor) could define state. The action is defined by an action atom, for instance Move(a, floor). The policy network only takes as input the state atoms (represented as tensors) containing their valuations over all the constants and predicts the truth values of the predicate Move over all the constants. A possible resulting next state after laking action Move(a, floor) would be On(b, floor), On(a, floor).
9

---

Published in Transactions on Machine Learning Research (07/200) 2022)
arty
arl
GRU
MLP
GRU
VB0
Figure Architecture our critic, assuming that max arity P is 2. On the left are depicted atoms of arity 0, and 2, where [C]. is the number of predicates of arity i, and E is the output dimension of GRU. Each GRU unit sequentially reads slices depicted with black lines. The architecture can generalized to larger arity by introducing more GRU units. The number of parameters of the critic is independent of the number of constants and only depends on the possible arities and the possible number of predicates in p
To the best of our knowledge, all previous neural-logic work rely on REINFORCE (Williams 1992 instead of an AC algorithm, which can generally be much more sample-efficient One reason may be the difficully of designing neural network for the critic that can directly receive as inputs po (i.e., the same input given to the policy based on a DLM architecture). To overcome this issue, we propose recurrent neural network architecture based on Gated Recurrent Unit (GRU) (Cho et al. 2014) for the critic. Once an architecture for the critic is defined, different actor-critic algorithms could applied. In this work, we use the SOTA AC algorithm, PPO (Schulman al. 2017). We present next the design of our critic and actor.
Critic This GRU-based critic estimates the value (2) of state deseribed by the atoms in p Recall GRU unit (Cho et al. 2014) processes input sequence as follows:
= oWW + Uphi-1 + bz), & oWW,,, + U, br), he = 2, O h (1 - 21) O @0WWa + Un(E O h1-1) + bn),
where 2, (resp. & the update (resp. reset) gate vector, hy is the output vector, a (resp. o) is the sigmoid (resp. tanh) activation function, O the component-wise product, and Wa, Un be for (2,r,h) are learnable parameters.
Our GRU-based critic (see Fig. includes, for each arity b > in P b independent GRU units. Each of them reads all the atoms in Ph. but focuses a different component of the b-ary predicates. For simplicity, we present the procedure for the first component, the other components are treated in a similar fashion. The GRU unit for the first component processes for each o E C, the input sequence I; whose element is defined by Vt = (02.... 0b) E cd-1_ Fz (Polo, 02..,,0...... PLEpp- Its output, taken as the computed last h,, corresponds to (0) O (o)) F where E a hyperparameter. Intuitively, the b GRU units compute for each constant summary (i.e., vector of dimension x E)) of the objects that are relation with
2 Althoough not discussed Jiang & Luo 2019 found in their source code attempt apply AC scheme, but they do by converting states into images (i.c. by activating the associated pixcls in the Cartesian space when block preseut at specific location), which may only be unsuitahle for some problems, but may also lose information during the conversion and prevent good generalization.
10

---

Published in Transactions on Machine Learning Research (07/2023)
After processing all the atoms of arity b > 1, all the combined outputs of these GRU units (i.e., 2b's) in addition to the initial unary predicates are read by another GRU unit, which outpuis a vector (Q), (Q...., Qf) E E This latter GRU unit takes as inputs Vt = o C, E R where N1 is the total number of Q3 's plus the number of initial unary predicates. The computed vector, in addition to any initial O-ary predicates if any, are given as inputs to an MIP, which outputs the estimated state value. Note that the number of parameters of this critic, like DLM, is independent of the number of constants.
An NLM architecture could also be used for the critic, but we find out that our proposed GRU-based architecture more efficient in practice. It enables more expressive aggregation function to compute value from set of input tensors. With NLM the reduction of the inputs to a scalar would only use the min-pooling operation across objects, which leads to a too simple aggregation function.
Actor The actor's output should idcally correspond to a predicate that evaluates to true for only one action and false for all other actions, which corresponds to a deterministic policy. For instance, in blocks world domain, the target predicate would be move(X, Y) and would be true for only one pair of objects, corresponding to the optimal action, and false for all other pairs. While not impossible to achieve (at least for certain small tasks), an optimal deterministic policy may involve an unnecessarily complex logic program. Indeed, for instance, for the blocks world domain, in many states, there are several equivalent actions, which the deterministic policy would have to order.
Thus, as done in previous works, we separate the reasoning part and the dreision-maaingg part. The reasoning part follows the architocture presented in Fig. La which provides tensor representing the target predicate corresponding to the actions. A component of this lensor can be interpreted as whether the respective action is good or not. The decision part takes as input this tensor and outputs a probability distribution over the actions using a softmax with fixed low temperature. Note that this temperature used for the actions is different from that used in Equation
4.2.3 Incremental Training
Learning an interpretable solution amounts to searching in discrete space whose size increases ex exponentially with the size of the solution (i.e., L). In complex tasks whose solution requires a logic program with a large depth, the SL or RL training we have just discussed may not be sufficient.
To face this difficulty, we also experimented with a more elaborate training procedure where potentially useful auxiliary predicates are incrementally learned and added to the initial predicates, which can then facilitate finding good interpretable solution. This is achieved by repcatedly training fixed DLM architecture with an increasing number of initial predicates. More specifically, we repeat the following training phase. At phase i, we apply the SL. or RL training method discussed previonsly on randomly initialized DLM to obtain an interpretable solution using as initial predicates the set p(i of predicates, which includes the predicates of po = Us P (i.e., all initial predicates of the problem) in addition to predicates invented in previous phases (if any). Thus, during the first phase, p(1) po_ At the end of a training phase, if the learned interpretable solution solves the problem, the procedure ends. Otherwise, although the obtained solution is imperfect, it may still contain some useful invented predicates. Therefore, we extract (see Section 4.3) the invented predicates from this interpretable solution, which are then added to p() to form p(++1) for the next phase.
Intuitively, incremental training stacks many DLM networks (cach with L layers) to obtain large DLM network whose number of layers can be up to the number of phases times L, depending on which invented predicates are used. Thus, incremental training can be seen as a training procedure for training a very deep DLM architecture. Note that this procodure increases the number of Icarnable parameters (as we iteratively increase the input size) but the overall architecture still remains independent of the number of objects.
4.3 Logic Program Extraction
During evaluation and deployment, both the time and space complexity will increase quickly as the number of constants increases. To speed up inference and have an interpretable model, we post-process the trained model to extract the logical formulas instead of using it directly. For each used module, we replace the
11

---

Published in Transactions on Machine Learning Research (07/2023)
Gumbel-softmax by argmax to choose the predicates deterministically. The fuzzy operations can then be replaced by their corresponding Boolean ones. Formula extraction can be done recursively from the output of the model. All the non-selected input predicates coming from the previous layer do not need to be computed. A graph containing only the selected predicates is built from the output to the input predicates. The extracted interpretable model can then operate on Boolean tensors, which further saves space and computation time.
5 Experimental Results
We performed four series of experiments. The first (resp. sccond) series evaluate DLM with SOTA basc- lines on ILP (resp. RL) (asks. The third series correspond to an ablation study that justifies the different components (i.e., critie, Gumbel-softmax, dropout) of our method. The last series present comparison of the methods in terms of computational costs. Examples of interpretable policies lcarned by DLM are pro- vided in Appendix B.2 Other details about the experiments (computer specifications, curriculum learning,
hyperparameters used in DLM and baselines) are provided in Appendix D
The first series, which focuses on SL training, confirm that DLM is competitive with SOTA baselines on ILP tasks. Compared to interpretable models (Payani & Fekri, 2019a Evans & Grefenstette 2018)), DLM performs better and compared to SOTA non-interpretable model (Dong al.) 2019), DLM is easier to
train successfully. To keep the paper short, present the details of those results in Appendix B The results for the other experiments are discussed next.
5.1
RL Tasks
For the RL experiments, we justify the baselines used, provide short description of the tasks with their corresponding training procedures, explain the performance metrics, and discuss the experimental results.
RL Baselines Our evaluation on ILP tasks suggests that the best neural-logic architectures, apart from DLM, are éILP and NLM. While the authors of NLM directly demonstrated it in an RL setting, AILP was later extended into an RL method called NLRL (Jiang & Luo 2019). Basod on these observations, we selected NLM and NLRL as strong RL neural-logic baselines to compare DLM with.
RL Task Description Our evaluation is performed on six RL tasks: three Blocks World tasks from Jiang & Luo (2019), three other tasks (two algorithmic tasks and one Blocks World task) from Dong et al. (2019 We provide short description below, but more details can be found in Appendix C
In the first three, Stack, Unstack, and On, the agent is trained to learn prodicate Move(X, Y), which moves block X on block (or floor) Y if possible. The observable predicates are: IsFloor(X), Top(X), and On(X, Y) with an additional predicate OnGool(XX Y) for the On task only. Tn Stack, the agent needs to stack all the blocks whatever their order. In Unstack, the agent needs to put all the blocks on the floor. In On, the agent needs to reach the goal specified by onGoal.
The last three are Sorting, Path and Blocksworld. In Sorting, the agent must learn Swap( X,Y) where X and Y are two elements of a list to sort. The binary observable predicates are SmallerInder, Samelndez, GreaterIndez, SmallerValte SameValue, and Greater In Path, the agent is given a graph as a binary predicate with a source node and a target. node as two unary predicates. Tt must learn the shortest path with a unary prodicate To(X) where X is the destination node. Blocksworld is the most complex task: it features a target world and a source world with numbered blocks, which makes the number of constants to be 2(m + 1) where is the number of blocks and 1 corresponds to the floor. The agent learns Move(X, Y) by moving blocks in the source world. It is rewarded if both worlds match exactly. The binary observable WorldII,, Larger WorldID, SumelD, SmallerID, LargerID, Left, SameX,
predicates are Same WorldID, Right, Below, Same and Above.
All those domains are goal-basod sparsc-reward RL problems. Since the first three domains are relatively simple, they can be trained and evaluated on fixed instances with a fixed number of blocks. In contrast, for the last three domains, the training and testing instances are generated randomly. Those last three domains,
12

---

Published in Transactions on Machine Learning Research (07/2023)
Table Average rewards of NLRL, NLM, and DLM on RL tasks for the best seed.
Average rewards
NLRL
NLM
n1DLM
DLM
+incr
DLM++ner (SL)
Interpretable
yes
no
no
yes
yes
yes
Unstack
5 vari.
0.914 + 0.01
0.920 + 0 0.920 +: 0
0.920 + 0
0.920 + 0
0.920 + 0
Stack
5 vari.
0.877 + 0.09
0.920 +: 0
0.920 + 0
0.920 i 0
0.920 + 0
0.920 + 0
On
5 vari.
0.885 + 0.01
0.896 + 0
0.896 + 0 0.896 + 0
0.896 + 0
0.896 + 0
Sorting
m 10
0.866 0.1
0.939 + 0.02
0.939
0.02
0.939
0.02
0.939
0.02
0.939 0.02
M = 50
N/A
0.556 1 0.02
0.556 i 0.02
0.559 1 0.02
0.559 + 0.02
0.559 + 0.02
Path
m 10
N/A
0.970 + 0
0.970 + 0
0.319 + 0.2
0.970 + 0
M 50
0.970 1
0.970 1
-0.004 1 0.4
0.970 0
Blocksworld
m = 10
N/A
0.888 + 0.02
0.904 + 0.02
0.894 + 0.02
M 50
0.153 0.04
0.159 0.11
0.230 0.04
N/A: Out of memory issue.
Could not extract working interpretable policy for given architecture size.
which are much harder than the first three, require training with curriculum learning (CL), which was also used by Dong et al. (2019). The difficulty of a lesson in CL is defined by the number of objects. Further details about the training with CL are provided in Appendix D.2 After training with m 10, we evaluate the learned model on test instances with m = 10, but also M = 50 to assess its generalizability.
RL Metrics Like ILP tasks, the performance can be measured in terms of success rates, i.e., percentage of times a trained policy can solve an RL task (i.c., reach a goal). In addition, another natural metric in RL is the average reward obtained during testing.
RL Results Table | provides the success rates of all the algorithms on different RL tasks. For DLM, we provide the results obtained by RL training (see Section 4.2.2) where we enforce the convergence to an interpretable policy (DLM) not (nIDLM). DLM+iner and DLM+iner (SL) correspond to our architecture trained in an incremental way via RL and SL training respectively (see below). Each subrow of an RL task corresponds to some instance(s) on which a trained model is evaluated.
The experimental results show that NLRL docs not scale to harder RL tasks, as expected from its performance on ILP tasks. On Sorting where we can learn a fully-interpretable policy, DLM is better than NLM in terms of computational time and memory usage during testing. Thus, DL.M is always superior to NLRL and can match the performance of NLM for simpler tasks.
For the harder RL tasks (Path, Blocksworld), when we do not enforce the convergence to an interpretable policy, our method with RL training (nIDLM) can reach similar or better performances than NLM. Inter- estingly, although both NLM and nIDLM learn a non-interpretable policy, nIDLM can generalize better than NLM in Blocksworld, which suggests that the architectural inductive bias of DLM is more suitable for problems described with FOT. However, obtaining good interpretable policy with CT reveals to be difficult: there is a contradiction between lcarning to solve a lesson and converging to a final interpretable policy that generalizes. Indeed, on the one hand, we can learn an interpretable policy for lesson with a small number of objects, however that policy will probably not generalize and training that interpretable policy the next lesson is hard since the softmaxes are nearly argmaxes. On the other hand, we can learn to solve all the lessons with non-interpretable policy, but that final policy is hard to turn into an interpretable one, because of the many local optima in the loss landscape. This training difficulty explains why we did not manage to learn an interpretable policy for Path and Blocksworld using RL training.
To demonstrate that this issue is due to RL training (and not to our DLM architecture), we also evaluated it with incremental training (see Section 4.2.3 In the incremental training phases, we tried both SL and
13

---

Published in Transactions on Machine Learning Research (07/2023)
Table 2: Average percentage of successful seeds (PSS) and average success rates (SR) on all the tasks of Family Tree and Graph Reasoning during testing with interpretable rules. Score computed with 5 seeds for each task.
Average PSS (%)
Average SR (%)
Softmax without noise Constant & with Dropout
58
97.3 t 6.1
68
97.7 t 9.3
Without Dropout
70
99.3 t 1.6
Gaussian noise
80
99.7 t 0.8
DLM
95
99.8 + 0.7
perfomeece
1.0-
without critic
tcsting perfortna perfomarre
1.0-
DLM without
NIM with critie
DJLM with critie
0.5
0.0
2000
episodes
epieodes
Figure Learning performance with or without our proposed critic with NLM (left) and DLM (right)..
RL training. While incremental RL training does increase the performance compared to RL training alone, notably in Path, it is not sufficient to solve Blocksworld nor Path completely.
However, incremental ST. training is successful, as reported column DLM++nnr (ST.) in Table 1 Tt cor- responds to an imitation learning scenario where the agent tries to copy a good policy given by a teacher (possibly the one learned by nIDLM which does not enforce interprotabilltyy. With DLM+iner (SL), unlike vanilla DLM and inM+ were able to extract good interpretable policy for Blocksworld. It needed stacking of 4 DLMs of depth 8, which shows the difficulty of finding an interpretable formula for this task. Interestingly, the generalization performance of DLM+iner (SL) is the best on Blocksworld, which suggests that enforcing interpretability is beneficial. We leave for future work the investigation of alternative RL training methods that scale better than CL for sparse-reward RL problems like Path and Blocksworld.
5.2 Ablation and Computational Cost Studies
For simplicity, these studies are performed in ILP tasks. Their description can be found on Appendix B
Ablation We performed an ablation study to understand the different features (e.g., Gumbel noise in softmaxes, decreasing 3, use of Dropout) in DLM. We trained our model on ILP tasks by using only softmax without injecting noisc, without decreasing the noise over time, without having dropout noise and finally by replacing the Gumbel distribution with Gaussian one. In those experiments, during evaluation, still used an argmax to retrieve the interpretable rules. Table 2 shows that all our choices help our model reach interpretable rules. Succoss rate (SR) is the proportion of examples well-classifidd by a trained model. Percentage of successful seeds (PSS) the proportion of seeds for which a trained model reaches an SR of 100%.
In addition, to evaluate the quality of our proposed critic architecture, we used it train both NLM and DLM. Fig. shows the testing performance of NLM DLM trained with REINFORCE with an actor-critic scheme with our proposed critic architecture. Recall the testing performance corresponds to the evaluation of the latest trained policy in terms of success rates at regular training steps. It has been averaged over 3 environments and 5 random seeds: Unslack, Stack, and On. As shown in Fig. 3 using our proposed critic architecture greatly accelerates the RL training for both NLM and DLM.
Comparative computational costs We compare now the different algorithms with respect to compu- fational times and memory usage during testing (Figure 4 and training (see Table 5 in Appendix). During
14

---

Published in Transactions on Machine Learning Research (07/202) 2023)
laGrandParent
2-outdegree
IsGrandParent
2-outdegren
30-
ANL-ILP
90
dNL-ILP
Memory (MIB)
10000
4NL-ILP
[MIIP]
0000
4NL-ILP
25-
NLM
70
8000
NLM
5000
NLM
Time
20-
DLM (Ouzs)
line
50
G0
(Ouns)
6000
DLM (Oure]
DLM (Ours)
15
10
30003
10-
30
2000
20
10
2
10
12
14
5
10
15
20
25
30
35
8
7
10
11
12
5
10
16
20
25
30
35
personx
persons
persoss
(x
persoor
10)
(a) Computational time
(b) Memory usage
Figure 4: Comparison during test IsGrandPorent and 2-ouldegree. On 2- 2-uudeegeee, NLM is rapidly out memory and dNL-ILP does not achieve a 100% success rate.
testing, we extracted the compact representation of the produced solution by DLM (see Section 4.3 Figure clearly shows that DLM scales better than the other baselines in terms of both memory and computational times. Note that in the second task (2-ouldegree), dNL-ILP does not achieve 100% success rate and searches instead in much smaller space.
6 Conclusion
We proposed a novel neural-logic architecture that is capable of learning fully-interpretablee solution, ie., logic program. Among differentiable methods, it obtains state-of-the-art results for inductive logic programming tasks, while retaining interprctability and scaling much better. For reinforcement learning tasks, it is superior to previous interpretable neuro-logic models. Compared to non-interpretable models, it can achieve comparable or higher performances using incremental training. Moreover, it can generalize better, and more importantly, it scales much more advantageously in terms of computational times and memory usage during testing.
Our results suggest that learning fully-interpretable solution using supervised learning with our approach could be practical, but enforcing interpretability in more complex reinforcement learning tasks, especially with RL training using sparse rewards, a much harder problem, which calls for novel neural-logic archi- tectures or novel training techniques. Another interesting phenomenon that we have observed that there is a tension between learning interpretable solutions and curriculum learning. We leave a study of this phenomenon for future work.
Acknowledgments
This work has been supported in part by a project funded by Huawei (HF2020055001) and the program of National Natural Science Foundation of China (No. 62176154).
References
Alejandro Barredo Arrieta, Natalia Díaz-Rodrigues Javier Del Ser, Adrien Bennetot, Siham Tabik, Alberto Barbado, Salvador Garcia, Sergio Gil-Lopez, Daniel Molina, Richard Benjamins, and et al. Explainable artificial intelligence (XAI): Concopts, taxonomics, opportunities and challenges toward responsible ai. Informalion Fusion, 58:82 115, 2020.
Richard Bellman. A Markovian decision process. Journal of mathematics and mechanics, pp. 679-684, 1957.
Tarek R. Besold, Artur d' Avill Garcez, Sebastian Bader, Howard Bowman, Pedro Domingos, Pascal Hitzler, Kai-Uwe Kuchnberger, Luis C. Lamb, Daniel Lowd, Priscila Machado Vieira Lima, Leo de Penning, Gadi Pinkas, Hoifung Poon, and Gerson Zaverucha. Neural-symbolic learning and reasoning: A survey and interpretation. arv:: 171 1009002 2017.
15

---

Published in Transactions on Machine Learning Research (07/2023)
Kyunghyun Cho, Bart van Merrienboer, Caglar Gulcehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations ions using rmn encoder-decoder for statisti- cal machine translation. In EMNLP, 2014.
Andrew Cropper, Sebastijan Dumančić, and Stephen H. Muggleton. Turning 30: New ideas in inductive logic programming. In IJCAI, 2020.
Luc De Racdt, Angelika. Kimmig, and Hannu Toivonen. Problog: a probabilistic prolog and its application in link discovery. IJCAI, 2007.
Lue De Raedt, Kristian Kersting, Sriraam Natarajan, and David Poole. Statistical Relational Al: Logic, Probabilily and Compulation. Morgan & Claypool, 2016.
Lue de Raedt, Sebastijan Dumančić, Robin Manhaeve, and Giuseppe Marra. From Statistical Relational Neuro-Symbolic Artificial Intelligence. In IJCAI, 2020.
Honghua Dong, Jiayuan Mao, Tian Lin, Chong Wang, Lihong Li, and Denny Zhou. Neural Logic Machines. In ICLR, 2019.
Saão Džeroski, Lue De Raedt, and Kurt Driessens. Relational reinforcement learning. Machine Learning, 43 (1):7 52, 2001.
Artur d' Avila Garcez, Marco Gori, Luis C. Lamb, Luciano Serafini, Michael Spranger, and Son N. Tran. Neural-symbolic computing: An effective methodology for priucipled integration of machine learning and reasoning. arXiv: 1905.06088 2019.
Richard Evans and Edward Grefenstette. Learning explanatory rules from noisy data. Journal of AI Research, 2018.
Claire Glanois, Zhaohui Jiang, Xuening Feng, Paul Weng, Matthieu Zimmer, Dong Li, Wulong Liu, and Jianye Hao. Neuro-symbolic hierarchical rule induction. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato (eds.), Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pp. 17-23 Jul 2022. URL htttps:/pproccooooe mir. press pross/v162 /222 /g2///aano222ahmm
PMLR,
A Graves, G Wayne, M. Reynolds, T Harley, Danihelka, A Grabska-Barwiiae SG Colmenarejo, E Grefen- stette, T Ramalho, J Agapiou, and et al. Hybrid computing using neural network with dynamic external memory. Nature, (38(7626):471-111
2016.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In ICLR, 2017.
Zhengyao Jiang and Shan Luo. Neural Logic Reinforcement Learning. In ICML, 2019.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. In NeurIPS, volume 12, 2000.
Robert A Kowalski. Logic programming. In Computational Logic, volume 9, pp. 523-569, 2014.
Brenden M. Lake, Tomer D. Ullman, Joshua B. Tenenbaum, and Samuel J. Gershman. Building machines that learn and think like people. Behavioral and Brain Sciences, 40, 2017.
Mark Law, Alessandra Russo, and Krysia Broda. Inductive learning of answer set programs from noisy examples. Advances in Cognitive Systems, 2018.
Timothy P. Lillicrap, Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Sil- ver, and Daan Wicrstra. Continuous control with deep reinforcement learning. In International Conference on Learning Representations, 2016.
Robin Manhaeve, Sebastijan Dumančić, Angelika Kimmig, Thomas Demeester, and Luc De Raedt. Deep- problog: Neural probabilistic logic programming. In NewrIPS, 2018.
16

---

Published in Transactions on Machine Learning Research (07/2023)
Gary Marcus. Deep learning: A critical appraisal. arXiv: 1801.00631, 2018.
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukeuoglu. Asynchronous methods for deep reinforcement learning. In JOML, 2016.
Stephen Muggleton. Inductive logic programming. New Generation Computing, 8(4):295 -18, Feb 1991.
Ali Payani and Faramarz Fekri. Inductive logic programming via differentiable deep neural logic networks. arXiv:1906.03553 2019a.
Ali Payani and Faramarz Fekri. Learning algorithms via neural logic networks. arXiv: arXiv:194.001 1904.0154,, 2019b.
Ali Payani and Faramarz Fekri. Incorporating relational background knowledge into reinforcement learning via differentiable inductive logic programming. arv:220033. 10386, 2020.
J. Schulman, S. Levine, P. Abbeel, M.I. Jordan, and P. Moritz. Trust region policy optimization. In 1CML, 2015.
J. Schulman, Moritz, S. Levine, M.I. Jordan, and P. Abbeel. High-dimensional continuous control using generalized advantage estimation. In International Conference on Learning Representations, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Opti- mization Algorithms. arXiv preprint: 1707.06347, August 2017.
Sainbayar Sukhbaatar, Arthur Szlam, Jason Weston, and Rob Fergus. End-to-end memory networks. In NewrIPS, 2015.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Prasad Tadepalli, Robert Givan, and Kurt Driessens. Relational reinforcement learning An overview. In ICML workshop on relational reinforcement learning, 2004.
Martijn Otterlo. Solving relational and first-order logical markov decision processes: A survey. In Reinforvement Learning, volume 12, pp. 253-292. 2012.
Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 8(3):229 2,6,26, 1992.
Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge base reasoning. In NewrIPS, 2017.
Yuan Yang and Le Song. Learn to explain efficiently via neural logic inductive learning. In ICLR, 2020.
17

---

Published in Transactions on Machine Learning Research (07/202) 2023)
A Details About DLM
A.1 Tensor Representation
DLM processes predicates by working the concatenation of their corresponding tensors. We define be- low the concatenation, provide some illustrative examples, and list the pseudo-code (Algorithm for the inference in DLM.
A set Pb of b-ary predicates can be represented as tensor, denoted Pb. of order + with shape [m,... m., [P.l.
The concatenation of two tensors Ps and 2: representing two sets of d-ary predicates, Po and Qu, is performed over the last dimension. It results in lensor of order b ++1 1 with shape [m,...m [Psl + 12x1]-
We provide some examples of how the different operations (i.e., expansion, reduction, permutation) work on tensors:
Example 4. Expansion: A unary predicate XXp(X) represented over 3 constants with the vector (0, 0, 1) would be expanded into Top(X,Y) Y) as the following matrix ((0, 0, 0), (0, 0),, 11). Reduction: A binary predicale Y) represented with the malric ((0, 1),, (0, 0, 1), (0, 0,0) would be reduced to the vector (1, 1,00 with the existential quantifier representing whether X is "On" " any objects.
Permutation: A binary predicate On(X,Y) represented with the matrir 1,0,1,0), (0, O, 1), (0,0,0) would permuted to the matriz ((0,0, (1,
0) (0, 1, 1,))) representing the relation Under(X,Y*
We provide a detailed example for understanding DLM's architecture:
Example 5. Consider blocks world environment with m = 4 objects: 3 blocks (u, u, w) and the floor (floor). Assuming that only two initial predicates are available, the following facts { (On(u, e), On(v, floor), Onl w. floor), Top( u), Top(w)} are encoded by two tensors. The first tensor encoding the unary predicate (X) is a vector of length 4, since there are 4 objects. The second tensor for the binary predicate On(X, Y) is 4 x 4-matriz. Those two tensors will feed the DLM network at layer on different breadths (1 and respectively).
We first focus what happens in the first layer of breadth 1 -1 1). By assumption, there is exponsion. Since the previous layer 1-1 with breadth b+1 is not empty, the reduction operation generates two predicates OnR1(X)= < VY, On( X, Y) and OnR2(X) < B,, On((X,)) Hence, the possible (posilive) inpul predicates R1 are {Top(X), OnR1(X), OnR2(X)). Since we deal with wnary predicates, the permutation operation does not play a role.
Now, consider the first layer of brendth (1 1,bb 2)b=2). operation generates one predicnte TopE(X,Y) whose truth value is given by Top(X). Therefore, after the permutation operation, R1 YO,(X,Y), TopB(X, Y), On(Y, TopE(Y,
2). By assumplion, there is no reduction. The expansion
Assume that we want to detect the objects that are neither the floor, nor on the top of a stack (t.e., v here) with a unary predicate, which we call BlockNotTop((T)) This predicate can be invented as a conjunction with
a negative first alom. As R = 3, wp and wp are vectors of length 4 due to the preservation operation. To build BlockNotTop((X)
TXp(X) A OnRX(X), wp should be zero everywhere except for selecting - -To((X) in (T) n RR). Accordingly, up should be zero everywhere except for selecting OnR2(X) inside (T) u R/--
We provide the formulas for the inference of NLM and DLM units in the first layer associated with Example 5
in Table 3
A.2 Interpretability and Expressivity
Interpretation Following NLM, we keep the probabilistic interpretation of the tensor representations of the prodicates in DLM. This interpretation justifies the application of statistical machine learning tech- niques train DLM via cross-entropy minimization for supervised tasks (i.e., ILP) for instance. In this interpretation, using the fuzzy conjunctions and disjunctions can be understood making the assumption
18

---

Published in Transactions on Machine Learning Research (07/2023)
Table 3: First layer of NLM and DLM on Example S The imput predicates are composed of Top(X), represented by vector U1 of length m, and On(X,Y) represented x matrix U2. The operation || denotes the concatenation of tensors on new dimension. Note that min and mar operations for the reduction are always performed on the last dimension of the input tensor. The expansion operation is denoted ç, it repeats tensor times new last dimension. The permutation operation is denoted P and permutes a tensor according to all the possible permutations temsor, would result in new
without repetitions stacked in new dimension. For instance, ((U2), m x m x m x 3! tensor. Note that for DLM we assumed nA = 2 for readability.
Output breadth
NLM
DLM
0 (nullary predicates)
MLP (MI((i((Ui)]lmmm(()))
Fuzzy (U3, Uz)
FuzzyORe, (U3, U3) with U3 = miinUi)l|maz(U]]
1 (unary predicates)
(LP(min(U2))) (1)
FuzzyAND,, (Us, U4)
PuzzyANDo,r (U4, 1- Ua)
FuzzyORg, (U,, U4)
FuzzyORg, (U4, U4)
with U4 minmminn)))))) (U2) (ax(UU)))(
2 (binary predicates)
(U,, Us)
FuzzyANDo,,r (U,, Us)
FuzzyORe, U3) (Us Us) with U3 = U2|U (|(
3 (ternary predicates)
MLP(v(((U2)))
Fuzzy BowxyNNDD,,r (U,, U6)
FuzzyANDo, (U,, Us)
FuzzyORa, (U,, Ua)
FuzzyORg, (Uo. U6)
with Up v(((U2)))
Algorithm Inference of a module at layer and breadth b
Require: P p/-1, Pi-l (tensor representations of the sets of predicates at layer 1 with breadth b 1, b, and b+ respectively), 0 (parameters of the module) and (temperature)
Ensure: Pj (Lensor representation of the set of the output predicales)
P b-1 + Reduction (P-
1-1
A/- 1-1
P 1-1 < Expansion (apannion(PPE1) (P
Q - Permutation (Concatenation(?) 1-1 P
i--1
Q Preservation (0))
R Negation( 2
// Assuming nA = 2 for readability
F - Fuzzy AND,, / 2,)
Eq.
3
F2 FuzzyANDo,F Q R!.)
Eq.
F 3 FuzzyORa Q 2
Eq-
FuzzyORa, e R
Eq. 4
P + Concatenation( F3.
return P/
of probabilistic independence between the truth values of any pairs of atoms in R/. This may seem strong assumption, however this is not detrimental since we want to learn logic program operating on Boolean tensors.
19

---

Published in Transactions on Machine Learning Research (07/2023)
Expressivity Previous work like CILP NLM (Evan & Grefenstette; 2018 Jiang & Luo 2019 Dong
et al. 2019) can express Datalog programs, a subset of FOL. composed of Horn clauses that do not contain function symbols. With the negation operation, DLM is more expressive than @ILP. With sufficient breadth B and depth L, it can express any normal logic programs, i.c,, Horn clauses with negative literals (Kowalski 2014j, that do not contain function symbols. We refer the reader to the proof present (Dong el al. 2019)) extension with the negation is trivial. Hence, the only FOL formulas not covered by DLM are the ones containing function symbols.
In practice, the expressivity of DLM can not only be controlled by setting hyperparameters L, B, nA, and no but also by restricting the inputs of logic modules (e.g., no negation or no existential or universal quantifiers). Therefore, a priori knowledge can be injected in this architecture by choosing different values for B at each layer, different values for no for each computation unit, different values for nA for each logic module, or by removing some inputs of logic modules for instance.
A.3 Implementation Remarks
In our implementation, half of the no outputs of each computation unit corresponds to and logic modules and the other half corresponds to or modules. Moreover, to enforce a stronger bias, among the and (resp. or) logic modules, half of them only takes Ø u (T) (resp. O u (I)) as inputs. Note that there is no expressivity loss with this bias, as long as the architecture is large enough.
For the other half of the and (resp. or) modules, half of the n. terms used to build conjunction (resp. disjunction) is from O o (T) (resp. O u (F)) and the other half is from n/ ()) u (T} (resp. ny( ()) u (F)).
A.4 Training Algorithms
For completeness, we provide the pscudo-code of the training algorithms we used. They are mostly standard, apart from the incremental training technique.
Here the pseudo-code for supervised training:
Algorithm 2 Supervised training of DLM
Require: (Po, pT) (input and target predicates describing an II.P task), 0 (randomly-initialize) DLM parameters), with hyperparameters T, (softmax temperature), 3, (Gumbel scale), pi (dropout probability), 0g (learning rate)
Ensure: 0 (trained DLM parameters)
for == 0, 2... do
Sample a batch of ILP instances described by atoms (PD, pr - D-DMM(PP) with softmax temperature тı, Gumbel noise 3r and dropout probability pa
Compute binary cross-entropy loss L
0- 0 VoT ) end for return
The algorithm could naturally also be applied to train on a fixed unique ILP instance. The hyperparameters are scheduled to decrease so that a convergence to a fully interpretable solution possible (see Table 10 for more details).
Here is the pseudo-code for RL. training, which is actually based on PPO Schulman et al. 201
20

---

Published in Transactions on Machine Learning Research (07/2023)
Algorithm 3 RL training of DLM
Require: (Po, PA) (predicates describing an RL task), trandomly-inttaalle DLM parameters), (randomly-imitialzze)) critic parameters), with hyperparameters тi (softmax temperature), 3 (Gumbel scale), p (dropout probability), and p (learning rates)
Ensure: 0 (Irained DLM paramelers) for i = 2,....... do
for j = 1,2,.... do Sample initial state sj (described by PD)
Generate j-th trajectory (s) of ......) using DLM, with softmax temperature T3, Gumbel noise & and dropout probability p:
Compute rewards-lo-go R2 of j-th trajectory (i.e., if goal reached and otherwise) end for Compute Å from (1))sa and critic (v (s())s, with GAE
0 - 0 + aVo.ppo +b 1/ &S v( o(s))s. u (8()))))
end for return
Recall in PPO, the update of the parameters of the critic is performed by minimizing the mean square error (MSE) between the output of the critic and the Generalized Advantage Estimate (GAE) (Schulman et al. 2017) through gradient descent.
Here the pseudo-code for incremental training:
Algorithm Incremental training of DLM
Require: (PO,PA) PA) (prodicates describing an RL task)
Ensure: po (initial predicates and those invented during incremental training), (trained DLM parameters)
pD for 0, 1, do Randomly initialize 0
0 - train DLMs on 1p",p4 performance is satisfying then return (P",0)
else
(kk) extract predicates used in DLM,
p0 po u (())
end if end for
Incremental training is written here for solving an RL lask, but could be adapted to solve a hard ILP task as well. Inside the for loop, DLM can be trained via SL or RL, depending on the training method the necessary hyperparameters need to be passed. In addition for RL training, the critic parameters would also be needed and should be randomly initialized before RL training.
B
Additional Experimental Results and Details
B.1
ILP Tasks
For the ILP experiments, we justify the basclines we selected, provide short description of the tasks, explain the performance metrics used for the evaluation, and discuss the results we obtained in terms of performance and computational costs. During this discussion, provide the training details.
21

---

Published in Transactions on Machine Learning Research (07/2023)
ILP Baselines Since DLM is neural-logic architecture, only compare with other neural-logic ap- proaches: TTP (Evans & Grefenstette 2018), NLM (Dong et al. 2019), and dNI.--LP (Payani & Fekri 2019a]. Differentiable architectures such as MEM-NN (Sukhbaatar et al. 2015 or DNC (Graves et al, 2016) are not included, since they have been shown to be inferior on ILP tasks compared to NLM and they, Turthermore, do not provide any interpretable solutions. Also, the approaches in multi-hop reasoning (Yang ct al. 2017 Yang & Song. 2020) are also left out because although they can scale well, the rules they can learn are much less expressive, which prevent them from solving any complex ILP tasks in an interpretable way. Besides, DeepProbLog (Manhaeve et al., 2018), which is based on backward chaining, is not included since it is not easy to perform predicate invention with it.
ILP Task Description For the ILP tasks, we evaluate on two domains: Family Tree and Graph Reason- ing. In the Family Tree domain, different tasks are considered corresponding to different target prodicates to be learned from an input graph where nodes representing individuals are connected with relations: Is- MXther(X, (), IsFather(X, (x,beer(XX)))) IsSon(X, Y), and IsDaughter(X..) Y). The target predicates are HasFather, HasSister, Prent,, IsUncle, and Unale (i.e., maternal great uncle). In the Graph Reasoning domain, the different target prodicates to be learned from an input graph are AdjacentToRed, 4- --Conecttvityy, 6- Conneellvvily 1- D-greeegree, 2- 2-OulDegree (see Appendix C.1 for their definitions).
ILP Metrics The performance of an ILP method on a task can be measured in terms of success rale, which is the percentage of relations in a test. instance that are correctly classified by a trained model. Following previous work, we report it an average over 250 random instances for the best model obtained over 10 random seeds. In addition, we also report the percentage of successful sceds (PSS), which is the percentage of those 10 seeds that reach a 100% success rate on the testing instances. PSS indicates how reliable a model and its training arc.
Performance on ILP Tasks In Table 4 we report those two metrics for DLM and the baselines we selected. All the methods are trained on random instances with the number of constants m = 20, except for AIL.. Since its authors did not release its source code, the reported success rates for éILP are from (Dong et al. (2019) and its PSS missing. For NLM and dNL-ILP, we use the source codes shared by their authors. For the latter, Payani & Fekri (019aa) did not evaluate their method in any standard ILP tasks. Using their source code, we did our best to find the best set of hyperparameters (see Appendix D.3 for each ILP task.
Column m = 20 provides the success rates for test instances with the same number of constants as in the training instances, while column M = 100 provides the success rates for test instances with 100 constants, which allow to measure the generalization capability of the trained models. N/A means that the method ran out of memory. For dNLL-ILP, the memory issue comes from the fact that, both learning auxiliary predicates and increasing the number of variables of predicates increase memory consumption sharply with a growing number of constants (see details in Appendix D.3.1)
The experimental results demonstrate that the previous interpretable methods, dNI.--I.P and @TI., do not scale to difficult ILP tasks and to a larger number of constants. However, DLM can solve all the ILP tasks like NLM, while DLM can in addition provide an interpretable rule in contrast to NLM. Moreover, we can observe that DLM is more stable, in terms of successful seeds, than all the other methods including NLM. To further demonstrate the stability of DLM, we also report the standard deviations of its success rates over the different seeds in Table 4 (values in parentheses). They show that even when 100% success rale is not reached for given seed, the trained model still reaches a success rate close to 100%.
Computational Costs ILP Tasks In Table 5 we provide the computational time (column T) and memory usage (column M) during training and testing on two different representative ILP tasks: IsGrand- parent and 2- 2-Outdegree. The Training rows provides the computational costs observed during training while the subsequent rows give the costs measured during testing for different numbers of constants. The dNL-ILP method can scale very well, but both NLM and DLM perform much better than dNL-ILP as shown in our previous experiments. While the training costs for DLM are slightly higher than NLM, they are still reason- able. More interestingly, DLM scales much better than NLM during testing, which is the most important, since these computational costs are incurred after the trained model is deployed.
22

---

Published in Transactions on Machine Learning Research (07/2023)
Table 4: Success rates (%) and percentage of successful seeds of dNL-ILP, ALLP, NLM, and DLM on Family Tree and Graph Reasoning.
dNL-ILP
AILP
NLM
DLM (Ours)
Family 'rree
m
20
100
PSS
m7
M
100
m
20
PSS
M 100
PSS
HasFather
100
100
100
100
100
100
100
100
100 (+0)
100 (+:0)
100
HosSister
100
100
40
100
100
100
100
100
100 (+0)
100 (+0)
100
Is Granddparent
100
100
80
100
100
100
100
100
100 (+0)
100 (+0)
100
Is IsUncle IsMGUndle
97.32
96.77
0
100
100
100
100
90
100 (1:)
100 (1:)
100
99.09
N/A
0
100
100
100
100
20
100 (10.01)
100 (10.08)
70
Graph Reasoning
m
10
M
50
PSS
m
M = 50
m
10
50
PSS
m
10
M 50
PSS
Adjacent ToRed
100
100
100
100
100
100
100
90
100 (+0.02)
100 (+0.01)
90
4- Connectivity
91.36
85.30
0
100
100
100
100
100
100 (+0)
100 (+0)
100
6- Connectivity
92.80
N/A
0
100
100
100
100
60
100 (+0.00)
100 (+0)
90
1- Ougregree
82.00
78.44
0
100
100
100
100
100
100
(+0)
100 (+0)
100
2- OulDegree
83.39
8.24
0
N/A
N/A
100
100
100
100 (10)
100 (10)
100
N/A: Out of memory issues.
PSS: Percentage of Successful Seeds reaching 100% of success rates on the testing instances.
Table 5: Compulational costs of dNL-ILP, NLM, and DLM on IsGrandParend and 2- 2-Ouldegree.
dNL-ILP
NLM
DLM (Ours)
Is IsCrnndpaeent
T
M
T
M
T
M
Training
201
30
1357
70
1629
382
m 10
27
24
2
20
30
70
24
m 30
42
188
24
40
13
99
414
74
m 50
31
198
820
124
m 60
65
358
m 70
119
596
8
2089
4
344
m 80
192
932
500
90
303
1390
13
4434
8
724
T 100
464
1994
6093
10
1002
110
656
2771
21
8079
13
1321
m 120
915
3751
27
10056
16
1710
130
1247
4964
N/A
N/A
19
2161
2. Outdegree
T
M
T
M
T
M
Training
966
22
2522
844
3238
1372
m 5
22
78
2
4
m 10
22
844
m 15
3
42
9
4342
3
254
m 20
112
N/A
N/A
732
25
21
314
N/A
N/A
10
1751
m 30
47
682
N/A
N/A
19
3594
35
93
1332
N/A
N/A
33
6666
T: time (s), M: Memory (MB).
DLM used depth 4,
breadth 3 for IsGrondparent, and depth 6, breadth 4 for Outddgree. N/A: Out of memory issues.
23

---

Published in Transactions on Machine Learning Research (07 (07/2023)
B.2 Examples of Interpretable Rules Policies
B.2.1 Discussion of Two Examples
As illustration for ILP, we provide the logic program learned by our method the task IsGrandParend. We used L 5 layers, = 3 breadth, nA = 2 atoms, and no 8 outputs per logic modules. For better legibility, give more meaningful names to the learned rules and remove the expansions and reductions:
IsChidi (a, b) - IsSon(a, b) v IsDaughter(a, b) [a b) IsSon(a, IsDonghter(a, TsGOP(a, b, - IsChild2 c) A TsChild2 (sCPCI(a,b,)) IsChildi (c. a) IsChild(b,c)
IsCPC2(a,b,c) - IsCPCI c) v IsCCP(b,a,)
TsGP(a, aC, I&GPC2 C) 3C, (aGPC((a, IsGrandPavent((,, b) - TsGP((, (a, b) IsGP(a,
The logie program extracted from the trained DLM has redundant parts (e.g., P A P), because used a relatively large architecture to ensure sufficient expressivity. Note that being able to learn interpretable solutions with large architecture is a desirable feature when the designer does not know the solution beforehand. Redundancy could be reduced by using a smaller architecture, otherwise the redundant parts (e-g. P A P) could easily be removed by post-processing the extracted logic program, as we did. After simplification, the solution is given by the following program, which shows that the target predicate has been perfectly learned:
IsChild(a, b) IsSon(a,b) IsDaughter(a, b) IsCPCI(a,,,.) - IsChild(e, a) A IsChild(b,d) IsGrandParend(a. b) 3C, IsGPC1
As an illustration for RL, we provide the simplified logic program learned by our method on the task On. which corresponds to the output of the reasoning part:
Move(a, b) (OnGoal(a, b) IsFloor(bi) -On(a, Top(a).
Using this program, the decision-making part (stochastically) moves blocks the floor and moves the good block on its goal position when it can. For completeness, we provide the complete logic program:
Pred1 (a, b) OnGoal(b, a) IsFloor(a)
Pred2 (a, b) - Onla, b) Top(a)
Pred3 (a, b) Pred1 (b, a) Predē(a,
Pred4 (a, b) - Pred1 (b, a) A Pred1 (b, a)
Move(a, b) PredS b) Pred4
Being able to find solutions a large architecture is a desirable feature when the designer does not know the solution before hand. Besides, note that we directly output an interpretable logic program. In contrast, with previous interpretable models, logic rules with high weights are extracted to be inspected. However, those rules may not generalize because weights usually not concentrated one element.
24

---

Published in Transactions on Machine Learning Research (07 (072))
B.2.2 Other ILP Examples
Here are other examples on the family tree domain:
Pred1 (a) + 3B, IsPather(a, B3 3B, IsMother B))
Pred2 (a] 3B, IsFather(a, B) 3B, IsMother(a, B)
Pred3 < 1B, IsMother(a, B) JB, IsMother(a, B)
Pred4 (a) Pred1 (a) (a)
Pred5 (a) - (a) (a)
Pred6 (a) Pred4 (a) (a)
(red7(a) - (a)d Pred
Pred8 (a) Pred6(a)
HasFalherra) - Pred7(a) A Pred8(a)
Predl (a, b) IsDaughter a) A IsMother b)
Pred2 (a, b) < TsDaughter (b, a) A IsFather (a, b)
(aed3 b) IsDaughter a) v IsMother
Pred4 (a, b) - 3C, Pred2 (b, C) 3C, Pred1 (b, C)
Pred5 (a, b) 3C, Pred3 (b, n, C) 3C, Pred1 (b, a, C)
Pred6 (a) - BB Pred4 (a, B) A 3B, Pred5 B)
(a)d7(a) Pred6 (a) v (red6(a)
HasSister (a) - (a) A Pred7(a)
Predi (a, 6) IsSon(b, a) A Is)on(b,
Pred2 b) - DsDughtl a) IsSom(b, a)
Pred3 b) IsSom a) v IsMother a)
Pred4 (a, b) - IsFather(a, 6) IsFather(a, b)
Pred5 b.c) -IsMother (a. 6) A IsMother(a, b)
Pred6 b) < IsSon(b, a) ^ IsDaughter(B, a)
(a)d7(a) < 3B, Pred1 (a, B) v 3B, Pred1 (a, B)
Pred8 (a, b) - 3C, Pred5 (a. 6, C) 3C, Pred5 (a, b, C*)
Pred9 b) -C, Pred6 (b, a, C²) A 3C, Pred4 (b. a, C)
Pred10(a,,, b. < - -Pred2 (b, a) (a,
Predl (a,b) - Pred8 (a. b) (bed7(b,
Pred12 b, <- -Pred (a, b) (re,)O(b,e,a))
Pred13(a, Predil (a, b) VC, Pred12(a,b, C)
TsUncle(a, b) - Pred13 b) Pred13(a,
C
Task Description
C.1
ILP
C.1.1
Family Tree
For family tree tasks, they have the same initial prodicates: IsFather(X, Y), IsMother(X, Y), IsSon(XX Y) and IsDaughter(X,11 Y). IsFather(X,Y) is True when Y is X's father. The other three predicates have the similar meaning.
25

---

Published in Transactions on Machine Learning Research (07/2023)
HasFather: HasFather(X) is True when X has father. It can be expressed by:
HasFather(X) - 3Y, IsFather(X,
HasSister: HasSister(X) is True when has at least one sister. It can be expressed by:
HasSister( (X) - R,, IaSister( X, Y)
IsSister(X,) Y) 32, (IsDaughter Zz Y) IsMother Z))
IsGrandparent: 1x Y) is True when Y is X's grandparent. It can be expressed by:
IxGrandparent(Xx Y) - 32, ((IsSon(Y, 2) a IsFather(X, (X, Z))
v (IsDaughter((Y, Z) IsMother( (X, Z)))
IsUncle: IsUncle(X,X Y) is True when Y is X's uncle. It can be expressed by: IsUncle(X, Y) 32, (JsMothhr((X, Z) A IsBrother(2. Z, Y)))
(IsFather(X) Z) IsBrother (2, Y))
IsBrother X, 3Z, ((IsSon Z Y) IsSon(Z, X))
V (IsSon( IsDaughter(Z, (X)))
IsMGUncle: LsM)U) True when is X's maternal great uncle. can be expressed by:
IsMGUncle(X,Y) - -7, (IsMother 2) A IsUncle(Z,
C.1.2 Graph Reasoning
For graph tasks, HasEdge task have the same initial predicates: XXsEd HasEdge(XX,Y) Y) True when there an undirected edge between node X and node Y.
Adjacent ToRed: AdjacentTooRed(X X) is True node X has an edge with a red node. In this task, it also use Colors(X, Y) another initial predicate besides XY), Color(X, when the color node X is It can be expressed by:
is True
AdjacentToRed(() 3Y, (HasEdge(X,,Y) rolor(Y,red))
4-Connetivityy 4- J-Connectivity( YX is True if there exists path between node X and node Y within 4 edges. It can be expressod by:
4- 4-Connettivity(XX (X,) Y) - 32, (HasEdge(XX YYv
Distance2 (X, Y) (Distance2 (X, Z) A HosEdye(Z,
(Distance2 (X, Z) (Z,
Distance2 (X, - 37, (HasFdge 2) A HasEdge((ZyY))
6-Connectivily: 6- Connectiviily X, X) is True if there exists path between node X and node Y within 6 edges. It can be expressed by:
@-Connectivily (X, Y) 3Z, (HasEdge Yvv
Distance2 (X, Y) v Distance3 (X,Y)* Y)v
(Distancc2 X,
Distance? (Z, Y))
(Distance3 ( (X, 7) x Distance2) (Z, V))
(Distance: 2X ^ Distancc3(2,
Distance2 2 (X, Y) - 32, (HasEdge({ X, Z) A HasEdge Z2, Y))
Distance (XX Y) 37, (HasEdgel X, 7) A Distancell (7, Y))
26

---

Published in Transactions on Machine Learning Research (07/2023)
1-Outdegree: 1- I-Outdegree(X) is True if there the outdegree of node X is exactly 1. It can be expressed by:
1- I-Outdegree(X) + 3Y, (HosEdge(X) Y)
- -HaxFdge(Xx X,Z) 7))
2-Outeegre:: 2- (-Ottdegre((X) is True if there the outdegree of node X is exactly 2. It be expressed by: 2- O-ttdeerre(()) 3Y, K (HosEdge(X,) -HHasEdgeXX 2) a -HasEdge(X,, K))
C.2 RL
C.2.1 NLRL Tasks
For the three NLRL tasks, Unstack, Stack, and On, the agent is trained move the blocks to reach certain configuration.
The action is represented by a binary predicate Move(X, (X, Y), which indicates moving block X block (or floor) Y. This action can be executed if it is legal, i.e., X is not the ground, block X has no blocks on it, and the same for Y if is a block. The three NLRL tasks share the same initial predicates IsFloor(X), Top( X), and On(X, Y). Besides, there one additional predicate OnGoal(XX Y) for the On task only. IsFloor (X) is True when the floor. Top(X) True when block X has no blocks on it. On(X, Y) is True when block X on Y. OnGoal(X, Y) indicates that the goal for the On task is move block X onto block Y.
Unstack: In this task, the goal is to move all the blocks on the floor. A policy that solves this task is:
Move(X,Y) Y) - IsPloor(Y) Pred(X)
Pred(X) - (X)d2(X) Top(X)
Pred2 =Y, Z, (Om(X, On(Y, 2))
This solution actually learned by DLM, where Predicates Pred(X) and Pred2 (X) invented during training. (X) indicates that block X is on top of another block, i.e., X is not directly on the floor. (red(X) indicates that block X is on top of a column of blocks and is not directly on the floor.
Stack: The goal in this task is to stack all the blocks into one column. A policy for this task can be expressed as:
Mone(X X, Y) Pred(V) A Pred/ (X,
Pred4 (X, Y) - Pred3(X) Pred2 (Y, X)
Pred2 (X, Y') 3Z, (On(X, Z) Top(Y))
Pred3 (X) - On(X, Y) a IsPloor (Y)
Pred(X) On(X, Pred2 X)
This solution was actually found by DLM where Predicates Pred(X), Pred2(X, Pred3 and Pred4 (X) invented during training. Predicate Pred( (r) here has the same meaning as the invented in Unstack task. Pred2 (X,Y) indicates that X is block and block Y is has no blocks it. (X) indicates that block X is directly the floor. Pred4 (X,Y) indicates that block X is directly on the floor and there is no block on it, and Y is block.
On: The goal is to reach a configuration indicated by OnGoal. A policy for the On task can be expressed by:
Move(X; V. (OnGoal(X, Y) IsPloor(Y)) -On(X,V) Top(X)
27

---

Published in Transactions on Machine Learning Research (07 (022))
C.2.2 Path
This is a single-source and single-targel path linding problem an undirected graph. For a given graph, the algorithm need find there at least one path from the source node to the target node within d steps.
The initial predicates Adjacent(X, Y), IsStart(X) and IsTarget(X). The graph is described as adja- cency matrix and Adjacent(X,)) is True when node X and node Y are connected by an undirected edge. IsStart(X) (resp. Is TsTarget( (X) is True when node X is the source (resp. target) node.
The action predicate is GoTo(X). If True, moves from the current node to the next node X. A working policy for Path, requiring recursive predicates, can be expressed by:
GoTo)Y) ix, ISttrrt(( Adjacent(X,, Y),
(IsTarget(\) v (HasEdge(Y,, Z) A IsTarget(Z]) HasEdge(X. X, Y) (x,jacend(X,Y)))
(#2, Hasbigee 2) ^ (asbdge((,)))
C.2.3 Sorting
In this problem, the algorithm needs sort an array of m integers into ascending order, by swapping those integers iteratively. Each index of array a is treated a constant.
The initial predicates are SmallerInder(XX, Y), SameIndez(X X, Y), GreaterInder(X Y), Smaller Valuel (X, Y), SameValue X, Y), and Greater GreaterValue(XX Y). The first three describe index relations and the last three describe value relations. For example, SmallerIndez(X,7 Y) is True when X < Y, and Smaller ValleerValle(X,, Y) is Truc when a[x] < a[Y].
The action predicate is Swap(XX Y). If True, it swaps a[X] and a[Y]. Therefore, we have m x (m - 1) available actions.
The difficulty of the problem comes from the fact that the number of performed swap operations is limited. Hence, if the number of integers is small, working policy for Sorting can be expressed by:
Swap(X, X, Y) < GreaterValuc(X, (Y, Y) A Smaller IndallerInde(X... (X,,)
However, the general solution for any m cannot be expressod without recursive predicates.
C.2.4 Blocksworld
Recall that in this problem, there are two worlds: the source world where blocks can be moved and the target world that describes the desired block configurations. Each constant (block ground) has 4 properties: a world ID, an object ID, an X coordinate, and Y coordinate. The ground has fixed position (0,0).
The initial predicates are Same WorldID(X, Y), Smaller (or Y), WorldDDD Y), SamelD(X, Y), SmallerID(X, Y), LargerID(X, Y), Left(X, Y), SameX(X, Y), Right(X, Y), Below(X, Y), Same Y(X, Y), and Above(X, Y). The first three compare two constants' world IDs, while the next three compare object DDs. The last ones compare two constants' X or Y coordinates.
28

---

Published in Transactions on Machine Learning Research (07 (07/2023)
The action predicate is Move(X, Y). If true, it moves block X onto Y in the source world if it is legal operation. can implemented as follows (found by a human expert):
Move(X, Y) - PlanA(X,Y) Y) v PxanBOnlyf((xXX) PlonBOnlydf - PlanB(X,X)) Y) -lalnAWWor() PlanAWork() - 1X, Y, PX,nA(XXY))
PlanB(X,Y) ShouldMove(X) NoGoodY IsGround(Y)
A Initial)Wrld())))
PlanA(X,Y) ShouldMove(X)) ShouldMox(O((X,))
NoGoodY(X) < -Jy, ShouldMoz<On(X..
ShouldMoveOO(XX WellPlaced(Y)) Clear(Y)
A UnderBlock(X, Y)
ShouldMove(X) Worlda))) Moveable(X)
- -WeliPlaced(XX
UnderBlock (X, Y) - (Target(X X,
(2
WellPlaced (X) < (X) a HHve Hlave/rmaaccheeBlloo((X
UnderBlockTT Y) 32, (Trrge((Y Z)
Directiy 7))
HaveUnmatchedBBllouWXX (SameX X,Y)),
-Matched(Y))
(xme:XDDirerrHyAAooo(((1 SameX(X,Y)
DirectlyAboue(X. X,
Moveable(X) Clear(X) - -IsGround(X)
DirecthyAbowe(X,, (X, Y) - Above( X, Y) ^ -3Z, Between X, Z,Y)
Matched X) RY, Match(X, Y)
Clear (X) - -B,, SameX (Y, X)
Between X,, 2) - Above(ox Y) Above(Y, Z)
Target( X, Y) + Smaller WorldTrDDolddD X, Y) Sa,eID(X,) Y)
Match(X, Y) Same WorldID Y) SamelD(X,Y)
SameX Y) Same (X,Y)
InitialWorld(X) -YY, S SameXAbove(X; - Same (Xr Y) x SameX(X,W)
Above(X,
IsGround(X) - -3Y, (el
Experimental Set-Up
D.1 Computer Specifications
The experiments are ran by one CPU thread and one GPU unit on the computer with specifications shown in Table f
Table 6: Computer specification.
Attribute
Specification
CPU 2 x Intel(R) Xeon(R) CPU E5-2678 v3
Threads
48
Memory
64GB (4x 16GB 2666)
GPU
4 x GeForce GTX 1080 Ti
29

---

Published in Transactions on Machine Learning Research (07 2022)
D.2 Curriculum Learning
Every 10 epochs, we test the performance of the agent over 100 instances with deterministic policy and a stochastic policy. If one of them reaches 100% then it can move to the next lesson. Our agents are trained only on one lesson at a time.
In the NLRL lasks, curriculum learning is not needed: the number of blocks during training is always
In Path, the first lesson starts with objects and finish with 10. In Sorting, we start with objects and finish with 15. In Blocksworld, start with 2 blocks (6 objects) and finish with 12 blocks (26 objects). In those 3 domains, the decreasing of the temperature and noise to obtain interpretable policy is only applied during the last lcsson.
For DLM-iner, curriculum learning is not needed: the number of blocks during training is always 7. The teacher produces the trajectories to learn. A new DLM is stacked only if the extracted formula is better than the previous onc. If it not, the parameters of the last DLM are reinitialized.
D.3 Hyperparameters
D.3.1 Hyperparameters for dNL-ILP
For dNL-ILP, we train each task with most 80, 000 iterations. Morcover, at cach itcration, lamily tree graph as training data, which is randomly generated from the same data generator in NLM and DLM, as backgrounds for training the model. For task HasFather, IsGrandparent and Adjacenttofted, dNL-ILP can achieve 100% accuracy without learn- ing any auxiliary predicates. For other ILP tasks, it has to learn at Ieast one auxiliary predicate to induct the larget. In practice, the performance decrease with increasing number of auxiliary predicates or variables, therefore here we only use at most one auxiliary predicate and at most three variables. Table is the no- tions for all the hyperparameters for testing dNL-ILP. Table shows hyperparamoters for defining rules in dNL-ILP that achieve the best performance.
new
Table 7: Notions for hyperparameters used in testing Payani & Fekri
2019a work.
Hyperparameter
Explanation
Narg
The number of arguments
Neor Nterms
The number of variables
The number of terms amalgamate function
Fam Nivas T
The number of nodes for training
The number of forward chain
N Nitter Ir
The number of tests for rules filter
Learning rate
N Nepoch
Maximum number of epochs for training model
Niter
The number of iterations for one epoch Maximum number of terms in each clanse
Mterms
0mean
Fast convergence total loss threshold MEAN Fast convergence total loss threshold MAX
0maz
91
ADAM B
32
ADAM B2
ADAM
Moreover, we use the same Ntrain from NLM to train dNL-ILP (i.e. We set Ntrain = 20 for HasFather, HasSister, TsGrandprennt, IsUncle and IsMGUncle. And we sot Nirain 10 for Adjacent 4-Connectivity, 6- E-Connectivity, 1- 1-Outdegree and 2- Outdegrree. Other hyperparameters, such as hyper- parameters for optimizer, remain the same for all tasks and consistent. with Payani et al's github code
30

---

Published in Transactions on Machine Learning Research (07/2023)
Table 8: Hyperparameters for defining and learning dNL-ILP rules each task.
Auxiliary
Target
Task
T
Narg
Near
Nterms
Fam
Narg
N var
N
Nterms
F Fam
HasFather
1
2
HasSister
1
eq
1
1
1
Isranndparent
2
1
4
eq
IsUncle
7
2
1
3
or
2
1
4
eq
Lncle
7
2
1
1
or
2
2
2
Adjacent ToRed
1
2
eq
4- +Connectivity
or
2
1
5
eq
6- G-Connectivity
or
2
7
eq
I-Outdegree
2
2
eq
2- 2-uudeeee
0
eq
1
3
2
09
Table 9: Hyperparameters for training dNL-ILP.
Napoch
Nitter
Niter
Mierms
Omean
Omax
B1
82
400
3
200
0.5
0.5
0.9
0.99
1c-6
For Family Tree tasks, we set Ir 0.01 when the loss from the last step is greater than 2, otherwise we set Ir 0.005. For Graph tasks, we set 0.01. Other hyperparameters are shown in Table
D.3.2 Hyperparameters for DLM
We have used ADAM with learning rate of 0.005, 5 trajectories, with a clip of 0.2 in the PPO loss, À = 0.9 in GAF and value function clipping of 0.2. For the softmax over the action distribution, we used a temperature of 0.01.
31

---

Published in Transactions on Machine Learning Research (07 (02)))
Table 10: Hyperparauneees the noise DLM.
Starting from
Exponential decay
Approximate final value
temperature T of Gumbel dist.
1
0.995
0.5
SL
scale 3 of Gumbel dist.
1
0.98
0.005
dropout probability
0.1
0.98
0.0005
lemperature t of Gumbel distr.
0.995
task-dependent task-dependent
RL
scale 3 of Gumbel dist.
0.1
0.98
dropout probability
0.01
0.98
task-dependent
Table 11: Architectures for DLM the different ILP and RL tasks.
Depth
Breadth
TO residual
HasFather
5
HasSister
5
3
2
Family Tree
IsGrandpavend
5
3
IsUncle
5
3
1sMGUncle
9
3
A AdjacentToRed
5
3
4 Connectivily
5
3
Graph Reasoning
6- Connectivity
9
3
1 1-OutDegree
5
3
2 OutDegree
7
4
Unslack
4
2
NLRL Tasks
Stack
4
2
On
4
2
Sorting
4
3
General Algorithm
Path
8
3
Path (DLM-iner)
6
3
Blocksworld (nIDLM)
8
2
Blocks World
Blocksworld (imitation)
8
2
Input-Output residual connections: As in NLM, all the input predicates of the DLM are given input of every module, Similarly, every output of each module is given to the final predicate of the DLM.
32


Reviews:
[{"review_id": "LLnt4PaQ9i", "reviewer": "Reviewer_VmLJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Disclaimer*: the reviewer is far from being an expert on neural logic architectures, or inductive logic programming more generally\n\nOverall, this well written paper provides novel contributions (the proposed neural logic architecture, the introduction of the critic for the RL part in this context), and provides a quite thorough empirical evaluation, both in SL and RL setting, with comparison to what seems to be the current SOTA, as well as an ablation of the Gumbel/temperature/dropout/critic components, and also study the computational and memory complexity. The appendix provides additional details, notably HPs for the experiments (open-sourcing the code would be welcomed).\n\nThe following questions are mainly clarifications requests (mostly related to the initial disclaimer, probably), and follows the structure of the paper.\n\n**Neural Logic Machine**\n\nThis part is a bit hard to follow (even if it’s not contributive, the proposed approach build upon it). If I understand well, a set of predicates are transformed into another set of predicates through an MLP, but there are additional operations (expansion, reduction, permutation), how does the gradient flow through them? And how are chosen the permutations (the set of all possible permutations? could be pretty huge)? What could help could be to provide a more detailed graph of what happens, and also the equations describing what a computational unit does (eg, for a vanilla MLP would be something like $Y = \\sigma(AX+b)$).\n\n**Differentiable Logic Machine: architecture**\n\nSame questions basically, and here also a more detailed graph of the computation unit could help, as well as Eqs describing what it does (ack it’s mostly done in Eqs (7-8). To sum up the difference between NLM and DLM are (please correct/complete if wrong):\n* adding negation and preservation operation (same question about gradient flow)\n* replacing the MLP of NLM by a soft-and and soft-or of a (learnt) convex combination of the input predicates\n\n**DLM: actor-critic training**\n* The RL modelling (state, action, next state) is not very clear. The state is a set of constants and predicates, but the network only takes predicates as inputs (and indirectly constants because predicates take constants as inputs)? The action is a predicate, but then what is the next state? A set of constants and predicates, but how are they obtained from the initial state-action couple?\n* It is stated that designing a critic is difficult, and the proposed architecture is quite complicated, relying on GRU (why do we need memory?). However, if one considers NLM, it transforms predicates (so states) into predicates (so actions) through an MLP. Why not just considering an MLP taking a predicate as input and outputing a scalar, what would not work with this approach?\n* It is stated that « Once an architecture for the critic is defined, different actor-critic algorithms could be applied ». However, the proposed architecture models a value function, while most AC requires a Q-function. Would the proposed architecture extends to Q-functions as well (maybe concatenating predicates corresponding to both the state and the action as input)?\n* footnote 2, what means converting states (so predicates?) into images?\n* Regarding the actor, there is another good reason for not seeking a deterministic policy: both policy gradient and PPO relies on having a policy with full support (otherwise one could rely on deterministic policy gradient)\n\n**Incremental Training**\n\nThe network size does not depend on the number of constants, but it does depend on the number of predicates. So, in incremental training, at each iteration the architecture of the network changes, correct?\n\n**Experiment**\nWhat about comparing also to non-differentiable methods if they can handle this kind of problems? Discussing also what are the pros and cons. Indeed, the related work part could be also extended (even if briefly) with non-differentiable methods (in contrast to differentiable ones). Also, the metric is a bit surprising (even if it seems to be used in other works). It seems a bit unfair to report the results of the best model over N seeds only (even though the PSS metrics provides partially the variability). Why not just providing the average results over seeds?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper introduces a neural logic architecture, called DLM (Differentiable Logic Machine). It is inspired by NLM (Neural Logic Machine), but differs from it by using interpretable modules instead of MLPs, and by considering two additional operations, negation and preservation, incurring a higher computational complexity tough. This architecture is considered both for supervised learning (SL) and reinforcement learning (RL). For SL, it performs a classic binary cross-entropy minimisation, with additional tricks to learn an interpretable solution (Gumble noise in the softmax, decreasing temperature, dropout, such that the learnt soft logic operators are as deterministic as possible). For RL, it adapts PPO, a novelty a neural-logic context being to introduce a critic (instead of relying on monte-carlo rollouts for a vanilla policy gradient). The proposed architecture is experimented in both SL and LR benchmarks, compared with state-of-the-art (SOTA) approaches, and overall is competitive with non-interpretable SOTA while providing an interpretable solution. An ablation study is also provided.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "It could make sense to address the above clarity questions to widen the audience of this paper. \n\nIn addition, below are a few typos/things to be corrected:\n* Sec. 3.2, « $d^{\\pi_\\theta}$, the stationary distribution of the Markov chain induced by the policy », this is wrong, it is the (unnormalised) discounted occupancy measure, not the stationary distribution (the best would be to define it formally)\n* Eq. (5), at least an expectation is missing\n* Sec 4.2.2, $r_t$ is used both for the reward and the reset gate vector (and arity in some places too)\n* Appx A.4, a few formating issues « Here is the pseudo-code for XX »\n* Alg. 3: I think $\\beta$ should be $\\beta_i$ and $\\rho$ should be $\\rho_i$ (both are decreased other time). Please also clarify what exactly how $\\hat{A}$ is estimated, and the loss for $v^\\psi$.\n* some Eqs are numbered, other not, it seems that not all numbered Eqs are referenced in the tex, please homogenise.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "GNP0Jv3bVf", "reviewer": "Reviewer_5Js5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors explain well how their approach relates to\nexisting neural ILP methods. The empirical comparisons (both RL and\nnon-RL) to these existing methods are quite thorough. The authors are\nadmirably up front about eg the difficulties of RL learning (with\nsparse rewards). The exploration of curriculum learning makes sense.\n\nThe paper is (mainly) clearly written and it is not hard work to\nunderstand what the authors have done (and potentially replicate\nit) and why. As can be seen below the problem with the paper is its narrow\nscope: the authors are basically only concerned with neural ILP\napproaches, rather than the ILP problem per se.\n\nLIMITATIONS OF DLM\n==================\n\nIn Appendix B the authors correctly note that \"the only FOL formulas\nnot covered by DLM are the ones containing function symbols\". But\nexcluding function symbols is a very significant restriction since one\nthen has only a finite number of ground atomic formulae and ends up\nwith, essentially, propositional logic (each ground atomic formula\nbeing a proposition). It is, of course, true when each proposition is\na particular grounding of some predicate, this can be exploited to\nallow compact formulas(*): in this setting, a universally quantified\nstatement is a very nice compact version of a very long conjunctive\nformula. So learning Datalog programs (and generalisations of Datalog,\nlike DLM) is a valuable goal, but since logic programs containing\nfunction symbols (including very simple list processing ones like\n\"append\") cannot be learned by DLM, it cannot be true (as claimed)\nthat DLM is a SOTA method for ILP - since many ILP systems are not so\nrestricted. The authors should be clear that they have a more modest\naim: doing ILP (and RL) in this particular restricted setting.\n\nNote that when function symbols are absent, the idea to\n\"propositionalize\" an ILP problem has a long history going back to\nthe early 90s.\n\n(*) DLM does not exploit this potential compaction. In DLM, each b-ary\npredicate P is represented by a tensor of order b with shape [m,...,m]\nwhere m is the number of constants.\n\nPERFORMANCE ON ILP TASKS\n========================\n\n\nIn the conclusion it is stated that the authors' approach (DLM)\n\"obtains state-of-the-art results for inductive logic programming\ntasks\". However when the reader inspects Appendix B in the hope of\nfinding empirical support for that statement we find this: \"Since DLM\nis a neural-logic architecture, we only compare with other\nneural-logic approaches dILP, NLM and dNL-ILP.\" Why only compare to\nother neural methods if the goal is to support the claim that DLM\n\"obtains SOTA results for ILP\"? There is no justification for the\n\"Since\" here. One should either also compare to non-neural ILP methods also\nor retract this claim.\n\nMoreover, the non-RL ILP tasks described in Appendices B and C look\neasy. We have no function symbols. Quite a few of these tasks do not\nrequire recursion. There is no \"background knowledge\" apart from the\ninitial ground atoms. Also from the description of Algorithm 2 it\nappears we have no noise (i.e. I assume the ground atoms P^O and P^T\n\"describing an ILP task\" do so correctly). It is true, on the other\nhand, that, in a number of cases, to get the desired logic program\nsome predicate invention is required which not all ILP systems deal\nwith well.\n\n\nSPECIFIC POINTS\n===============\n\n- We have the statement: \"Since traditional ILP systems can not handle\nnoisy, uncertain or ambiguous data, they have been extended and\nintegrated into neural and differentiable frameworks.\" Note first that\nDLM greatly restricts (not extends) which logic programs can be\nlearned (compared to trad systems). What exactly does \"can not handle\"\nmean here? Almost all ILP systems have ways of dealing with noisy\ndata. Is the claim here then that they do not do so very well? Perhaps\nthis is true, but it would be good to see some justification of this.\n\n- \"Variables refer to unspecified constrants.\" In FOL, variables refer\nto unspecified ground terms which may or may not be constants.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The learning architecture involves a \"continuous relaxation\" of logic\nprograms (actually only a very restricted type of logic program) where\none assigns \"weights to predicates instead of rules\". Essentially\nrather than assigning only 0 (false) or 1 (true) to a ground atom,\nthey can have values in the interval [0,1] much as in fuzzy logic\n(although these values are interpreted as probabilities not fuzzy\nvalues). So a binary variable is relaxed to a continuous one in the\nnormal way.\n\nThe authors present a neural architecture for learning with this\nrepresentation and present learning results which compare favourably\nto other neural ILP methods. Comparison is based not only on\ne.g. rewards for RL tasks, but also in terms of \"interpretrability\",\nwhich considers whether a logic program can be extracted from the\nneural learning.\n\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The authors need to extend their empirical evaluation beyond\nneural ILP methods to other ILP methods. This is a requirement. Since their system compares\nfavourably to some other neural systems, if they could (at least\nsometimes) out-perform some respectable non-neural ILP approaches that\nwould be interesting. Note that non-neural ILP systems simply output a\nlogic program, so they naturally score well for \"interpretability\".\n\nIt would be good to see comparisons on tasks using predicates with\nhigher arities. The authors have chosen tasks where the input\nand target predicates are unary or binary (which keeps the size of the\ntensor representation under control). And only occasionally do we get\narity-3 invented predicates. What happens when one attempts a task\nwith high-arity predicates?\n", "broader_impact_concerns": "I had no such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "xx4xspbpXJ", "reviewer": "Reviewer_mWf5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n\n+ The text is very well written and (surprisingly) mostly accessible to ILP non-experts.  All ideas are conveyed clearly.\n+ Taken individually, all methodological contributions are reasonable.\n+ Taken jointly, the proposed contributions bring improved interpretability (compared to NLMs) and scalability/success rate (compared to other differentiable ILP strategies)\n+ The experimental setup is quite extensive and looks sound.\n+ Results look very promising.\n\nWeaknesses\n\n- Taken individually, the methodological contributions are a bit incremental.  This is definitely not a problem for me.\n\nAll in all, this is a very solid piece of work, and I recommend acceptance.  As a matter of fact, I do not have any major changes to suggest!", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce Differentiable Logic Machines (DLMs), a new neuro-symbolic architecture for inductive logic programming-like tasks.  DLM build on a pre-existing architecture, namely Neural Logic Machines (NLMs), which feature a reduced number of parameters compared to other differentiable approaches to ILP.  SPecifically, DLMs take NLMs and a) Replace MLP layers with parameterized \"soft\" logic layers, b) Add more general \"pooling\" (or \"predicate scrambling\") operations between layers.  These additions are accompanied by improved training procedures for supervised learning and a new actor-critic approach for reinforcement learning problems.  These improvements are evaluated on an extensive set of experiments and ablation studies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A very minor change: the best results in the tables should be highlighted somehow (preferably in bold), if applicable.  This would help with readability.", "broader_impact_concerns": "None.  DLMs have the same potential negative impact as existing approaches (bar scaling to bigger problems).", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most of the reviewers were happy with the contributions although they agree they are not highly significant. Yet, the paper fits the TMLR requirements by providing a new method for solving ILPs with a neural approach that still provides explainability. The claims are supported by experiments and comparison to other neural methods. One reviewer regrets the lack of comparison to non-neural approach and insisted that this should appear in the paper. I think this is a valid point that the authors could easily address. Yet it is not preventing publication according to TMLR guidelines and other reviewers. Comparison to similar methods are convincing enough to them. 

Some modifications were requested to improve clarity and this was addressed by the authors, and acknowledged by the reviewers. 


Decision: Accept (poster)