Learning Explanatory Rules from Noisy Data

1. Introduction

• ILP learns explicit logic programs from positive and negative examples and offers inspectable rules, data efficiency through language bias, and continual and transfer learning.The introduction cautions that machine-generated programs can become less readable when large or reliant on invented predicates.Source: §1 · pp. 1–2
• Traditional ILP cannot learn intended rules from mislabeled examples and is not suited to noisy, erroneous, or ambiguous data.The introduction motivates connectionist learning as a way to bring robustness to symbolic relational learning.Source: §1 · p. 2
• Neural program induction tolerates noisy labels and ambiguous inputs such as raw pixels, but learns implicit, hard-to-inspect procedures that can falter on test inputs much larger than training examples.The introduction attributes overfitting risk to the high variance of general-purpose neural architectures.Source: §1 · pp. 2–3
• ∂ILP reimplements ILP as an end-to-end differentiable system, learning explicit symbolic rules through forward chaining and minimizing cross-entropy against Boolean labels.The introduction frames this as combining ILP’s data efficiency and human-readable rules with neural robustness to noise and ambiguous inputs.Source: §1 · p. 3
• ∂ILP learns recursive programs with predicate invention, generalizes beyond the training range on Fizz-Buzz, tolerates up to 20% mislabeled examples, and works with an MNIST convolutional net.The paper also notes that significant memory requirements limit the benchmark problems tested, including to predicates of arity at most two.Source: §1 · p. 3

2.1 Logic Programming

• Logic programs use if-then clauses whose body atoms imply a head atom, with this paper restricting clauses to definite Datalog without function symbols.Definite clauses exclude negation-as-failure; the restriction makes the language decidable and forward-chaining inference terminate.Source: §2.1 · p. 4
• Forward chaining tests entailment by deriving consequences, while extensional predicates are given as ground facts and intensional predicates are defined by clauses.The section also distinguishes backward chaining, which searches from a goal through rules whose heads unify with it.Source: §2.1 · pp. 5–6

2.2 Inductive Logic Programming (ILP)

• ILP takes background atoms B and positive and negative examples P and N, seeking definite clauses that entail positives but not negatives.The paper next transforms ILP into a satisfiability problem and presents a differentiable implementation of satisfiability solving.Source: §2.2 · pp. 6–7

3. ILP as a Satisfiability Problem

• A continuous relaxation of ILP-as-satisfiability lets gradient descent learn which generated clauses to enable, even with noisy or ambiguous data.The approach retains the top-down generate-and-test structure: generated clauses and background facts must entail positive examples and not entail negative examples.Source: §3 · p. 7

3.1 Basic Concepts

• An ILP instance combines a language frame, background assumptions, and positive and negative examples; its program template bounds programs and forward-chaining depth.The template includes auxiliary predicates and their arities.Source: §3.1 · p. 8

3.2 Generating Clauses

• Generated clauses are restricted to free variables, no constants, and exactly two body atoms; unsafe, circular, duplicate, and clauses violating the intensional flag are ruled out.Predicates whose meanings depend on particular constants are treated as extensional rather than intensional.Source: §3.2 · pp. 9–10

3.3 Reducing Induction to Satisfiability

• Boolean variables indicate which generated clauses are selected; a SAT solver assigns them truth values, and the true variables determine the induced rules.The candidate clauses are grouped by rule templates for intensional predicates.Source: §3.3 · p. 10

4. A Differentiable Implementation of ILP

• ∂ilp replaces Boolean atom semantics with values in the real unit interval and discrete clause selection with continuous weights defining a probability distribution over clauses, enabling differentiable deduction.The gradient of the loss with respect to rule weights implements a continuous form of induction.Source: §4 · p. 11

4.1 Valuations

• Given a set G of n ground atoms, a valuation maps each atom to a real value in [0, 1], and all valuations map ⊥ to 0.Source: §4.1 · p. 11

4.2 Induction by Gradient Descent

• Training samples atom-label pairs, predicts labels by T-step forward chaining, and updates clause weights with stochastic gradient descent on cross-entropy.The predicted label is extracted from the inferred valuation; the operations between the loss and clause weights are differentiable.Source: §4 · p. 11, §4.2 · p. 12

4.3 Rule Weights

• For each intensional predicate, ∂ilp softmaxes a matrix of clause-pair weights into probabilities; the lower-memory vector alternative was less effective on ILP tasks.Each matrix weight represents the system’s belief in a pair of clauses as the definition of the predicate.Source: §4.3 · p. 14

4.4 Inference

• Each clause becomes a differentiable valuation-to-valuation function for one forward-chaining step, with conclusions combined by probabilistic sum to preserve [0, 1] and gradient flow.The probabilistic sum is used instead of element-wise max, which adversely affected gradient flow.Source: §4.4 · pp. 14, 16

4.5 Computing the Fc Functions

• For rules with two body atoms, ∂ilp precomputes satisfying atom-index pairs, then uses gathered valuation values, element-wise products, and maxima to compute clause inference differentiably.The index calculation is discrete, but applying the resulting indices to valuations is differentiable.Source: §4.5 · pp. 16–18

4.5.1 Defining Fuzzy Conjunction

• Across 20 symbolic problems, the product t-norm consistently outperformed Gödel’s and Łukasiewicz’s, because its gradients flow through both conjuncts.The alternatives can block gradient information for one or both conjuncts under specified conditions.Source: §4.5.1 · p. 19

5.1 Hyperparameters

• RMSProp and Adam solved all 10 hyperparameter-search tasks in at least 5% of initialisations, and RMSProp succeeded across learning rates from 0.5 to 0.01.The experiments then used RMSProp at learning rate 0.5 with weights sampled from N(0, 1).Source: §5.1 · p. 20

5.3 ILP Benchmark Tasks

• The 20 symbolic benchmarks span arithmetic, lists, group theory, and family-tree relations; they use small training sets despite often requiring complex programs with recursion and invented predicates.Because ∂ilp is memory-expensive, the experiments exclude larger datasets such as Mutagenesis, WebKB, and IMDB.Source: §5.3 · pp. 20–21

5.3.1 Learning Even/1 on Natural Numbers

• For natural-number parity, ∂ilp reliably learned even/1, but the results depended on a program template that specifies two target clauses and an auxiliary predicate.The authors note the risk of templates baking in target knowledge and compare the template with Metagol’s metarules in an appendix.Source: §5.3.1 · pp. 21–22

5.3.2 Learning Graph Cyclicity

• ∂ilp solved graph cyclicity in 100% of runs, using an invented recursive predicate for the transitive closure of the edge relation.The test evaluates generalisation across alternative possible worlds and an unseen validation graph.Source: §5.3.2 · pp. 22–23

5.3.3 Learning Fizz-Buzz

• ∂ilp learned Fizz rules that generalised from training integers 0–6 to test integers of any size, while finding the correct Buzz solution in 30% of initialisations.The Fizz-Buzz approach first learns Fizz, then uses learned predicates as axioms when learning Buzz.Source: §5.3.3 · pp. 23–25

5.3.4 Results on All Symbolic Tasks

• On 20 symbolic tasks, Metagol sometimes timed out within the shared 24-hour limit, while ∂ilp’s memory use restricts it to nullary, unary, and binary predicates.The Metagol failures involved infinite loops from recursive metarules interacting with cycles; ternary-predicate tasks and the robot-waiter example exceed ∂ilp’s current scope.Source: §5.3.4 · p. 26, Table 2 · p. 27
• Across symbolic tasks, the reported success measure is the percentage of runs with validation mean squared error below 1e−4, based on 200 random initialisations per method.The methods include core ∂ilp and variants using Gödel’s t-norm, Łukasiewicz’s t-norm, or max for amalgamation; the supplied passages give no comparative values.Source: §5.3.4 · p. 26, Table 3 · p. 27

5.4 Dealing with Mislabelled Data

• Standard ILP cannot recover its intended program when examples are mislabelled, whereas ∂ilp’s loss-based training can handle mislabelling; experiments vary the mislabelled proportion ρ from 0 to 1.At each experiment’s start, a fixed proportion of positive and negative examples is transferred to the opposite group and remains consistently mislabelled during training.Source: §5.4 · p. 28
• At 10% mislabelled data, ∂ilp finds a perfect answer on 5 out of 6 tasks, and its error degrades gracefully as mislabelling increases.Traditional ILP test error increases sharply after even one piece of training data is mislabelled; ∂ilp also finds good answers on some tasks at 20% or 30% mislabelling.Source: Table 4 · p. 28, §5.4 · p. 28, Figure 3 · p. 29
• Rule entropy can fall even as mislabelling approaches 100%; with all even/odd labels switched, ∂ilp learns a zero-entropy odd-number rule.The paper notes that in some cases entropy is lower with all data mislabelled than with half mislabelled.Source: §5.4 · pp. 28–29, Figure 4 · p. 29

5.5 Dealing with Ambiguous Data

• ∂ilp’s continuous semantics assigns atoms values in [0, 1], and the experiments connect it to a pretrained MNIST convnet to test reasoning with ambiguous inputs.The image-recognition setup tests the connection rather than aiming to advance MNIST classification performance.Source: §5.5 · p. 30

5.5.1 Learning Even Numbers from Raw Pixel Images

• From raw digit images, ∂ilp learns the even predicate using mutually recursive invented predicates for even and odd numbers.The image is mapped by the pretrained convnet to a probability distribution over atoms, which is combined with background information to form the initial valuation.Source: §5.5.1 · pp. 30, 32

5.5.2 Learning if the Left Image is Exactly Two Less than the Right Image

• For paired images, ∂ilp learns to identify when the left-hand number is exactly two less than the right-hand number.Its learned solution uses a predicate for the right-hand number and an auxiliary predicate relating it to the left-hand number.Source: §5.5.2 · p. 32

5.5.3 Learning if the Right Image Equals 1

• For paired images labeled by whether the right digit is 1, ∂ilp learns to ignore the left image and makes its auxiliary predicate true exactly for 1.Source: §5.5.3 · p. 33

5.5.4 Learning the Less-Than Relation

• ∂ilp remains robust with 70% of integer pairs held out, while the MLP baseline performs increasingly poorly as hold-outs increase.The evaluation counts runs reaching at least 96% test accuracy; ∂ilp maintains a respectable mean test error even at 70% held out.Source: Figure 7 · p. 34, §5.5.4 · pp. 34–35

5.5.5 Discussion

• In further experiments, a learned mapping from convnet features to symbolic assignments adapts to each task, while the initial experiments froze the convnet and used a custom mapping.For example, the learned mapping blurs distinctions among nonzero digits for a zero-recognition task, and can map images of n to 9 − n for predecessor learning. The authors describe end-to-end joint learning of rules and classifiers as future work.Source: §5.5.5 · pp. 35–36

6.1 “Approximating the Semantics of Logic Programs by Recurrent Neural Networks”

• H¨olldobler, Kalinke, and St¨orr (1999) show that recurrent nets can approximate forward chaining for acyclic programs to any desired precision, but their real-number encoding is impractical.Their theoretical result does not provide a practical construction method and assumes arbitrary-precision floating-point numbers.Source: §6.1 · p. 37

6.2 “Connectionist Model Generation: A First-Order Approach”

• Bader, Hitzler, and H¨olldobler (2008) use vector representations to implement forward chaining, but their networks memorize particular atom sets, unlike ∂ilp’s reusable general rules.Their approach considers acyclic programs; the learned program is hidden in the weights, and extracting explicit symbolic rules remains an open question.Source: §6.2 · pp. 37–38

6.3 “Logic Tensor Networks: Deep Learning and Logical Reasoning from Data and Knowledge”

• Logic Tensor Networks use continuous semantics for full first-order logic, but perform abduction by completing fuzzy valuations rather than inducing rules (Serafini and Garcez, 2016).They are not restricted to Horn clauses or function-free Datalog clauses.Source: §6.3 · p. 38

6.4 “Computing First-Order Logic Programs by Fibring Artificial Neural Networks”

• Fibred neural networks represent recursive and mutually recursive programs but cannot represent programs with free variables (existential body variables absent from the head); Yang et al. (2016) learn individual, nonrecursive clauses.Source: §6.4 · p. 39, §6.10 · p. 42

6.5 “Logical Hidden Markov Models”

• Logical HMMs learn probabilistic first-order rules from atom sequences, but assume one atom is true at a time and use single-atom rule bodies, unlike ∂ilp’s multi-atom world states.Kersting, De Raedt, and Raiko (2006) learn rule probabilities with a modified Baum-Welch algorithm and report smaller models and better generalization than traditional HMMs.Source: §6.5 · p. 39

6.6 “Probabilistic Inductive Logic Programming”

• nFOIL learns individual clauses from noisy data and outperformed mFoil and Aleph on Mutagenesis, whereas ∂ilp learns multiple clauses, including recursive ones.De Raedt and Kersting (2008) frame probabilistic ILP by reinterpreting the covers relation as a conditional probability.Source: §6.6 · pp. 39–40

6.8 “Fast Relational Learning Using Bottom Clause Propositionalization with Artificial Neural Networks”

• ∂ilp learns more complex, sometimes mutually recursive programs, while CILP++ handles larger datasets but cannot learn recursive clauses (Franca et al., 2014).∂ilp is currently limited by memory requirements and cannot be tested on large datasets such as Mutagenesis, KRK, and UW-CSE.Source: §6.8 · p. 41

6.9 “Learning Knowledge Base Inference with Neural Theorem Provers”

• Neural Theorem Provers use backward chaining with learned clauses and embeddings, while Dyna uses forward chaining but learns background-assumption weights rather than rule weights.Neural Theorem Provers jointly learn clauses and vector embeddings; in ∂ilp, gradient descent learns rule weights given background rules, whereas Dyna fixes rules.Source: §6.9 · p. 41, §6.11 · p. 42

7.1 Program Templates and Language Bias

• Critics argue that ILP templates require careful human engineering and may predetermine much of the program; ∂ilp templates specify existential variables and intensional-predicate use, but not recursive-call form.The paper points to Appendices C and D for comparison with other forms of language bias.Source: §7.1 · p. 42
• Iterative deepening over enumerated templates can avoid hand-engineering them, but the brute-force search required massive computation across a large machine cluster.The authors used Cantor’s pairing function to enumerate templates and ran them in batch.Source: §7.1 · pp. 42–43

7. Discussion

• ∂ilp learns programs with multiple invented predicates and recursive clauses, tolerates mislabelled data, and extends ILP-style data efficiency and generalization to ambiguous domains.The authors envision an end-to-end differentiable system that learns perceptual and inferential rules simultaneously.Source: §7.2 · p. 43

7.2 Conclusion

• Across 20 symbolic ILP tasks, the model solved problems traditional ILP systems excel at, learned good models with 20% mislabelled examples, and generalized with ambiguous inputs from a pretrained convnet.The ambiguous-data experiments connected a pretrained convnet’s output to the induction system.Source: §7.2 · p. 43
• The framework still relies on program templates, and the attempted template-free search is hugely computationally expensive, motivating a less brute-force future solution.The authors identify templates as one of two main limitations.Source: §7.2 · p. 43
• Ambiguous-data experiments relied on pretrained classifiers and baked-in MNIST digit classes; preliminary joint learning after convolutional pretraining was satisfactory and interpretable, but full end-to-end training remains future work.Future work will explore pretraining strategies that do not bias networks toward the specific problems they will be integrated with.Source: §7.2 · p. 43

Appendix A. Notational Conventions

• The paper uses uppercase letters for ground-atom sets, lowercase letters for predicates and constants, and uppercase variables; boldface distinguishes vectors and matrices or tensors from scalars.Vector and matrix entries use indexed notation; tensor slices identify matrices, while ×, ⊙, and · denote scalar multiplication or cross-product, component-wise multiplication, and dot product, respectively.Source: Appendix A · p. 44

Appendix B. ILP as Satisfiability

• In the running example, no auxiliary predicates are needed, and the selected program defines q as the transitive closure of p.Source: Appendix B · pp. 46, 49
• Repeated atoms in generated clauses enforce a uniform two-atom body, a design that supports transfer to the matrix-based approach.Source: Appendix B · pp. 46–47
• ILP induction becomes a satisfiability problem by selecting generated clauses with Boolean flags; satisfying flags can be used to extract a logic program.The approach insists on exactly one flag for each rule template.Source: Appendix B · pp. 47–48

Appendix C. Comparing Language Bias in ∂ILP with Mode Declarations

• Unlike ∂ILP templates, mode declarations specify exact predicates allowed in rule bodies and can restrict where a new existential variable appears.Source: Appendix C · p. 50

Appendix D. Comparing Language Bias in ∂ILP and in Metagol

• Metagol metarules fix variable bindings and recursive forms, whereas ∂ILP templates specify only existential-variable counts and allow intensional predicates in rule bodies.The paper characterizes the Metagol template as more restrictive.Source: Appendix D · p. 50

Appendix E. Space Requirements

• ∂ILP is memory intensive, with major memory use coming from clause-application vectors and intermediate vectors Y1, Y2, and Z.Source: Appendix E · pp. 50–51

Appendix F. Why Not Use a Simpler, Smaller Model?

• The simpler model struggled to escape local minima on harder tasks and can overwrite same-predicate clause conclusions, losing information needed to learn multi-clause programs.The memory-intensive model keeps results from clauses with different predicate heads disjoint so they can be added without information loss.Source: Appendix F · pp. 51–52

Appendix G. The 20 Benchmark ILP Experiments

• Appendix G presents details of twenty benchmark experiments.Source: Appendix G · p. 52

G.1 Predecessor

• The predecessor task learns predecessor from zero and successor facts, with negatives defined as all target pairs over 0–9 not listed as positive.Source: §G.1 · p. 52

G.2 Even / Odd

• The even task uses auxiliary predicate pred1, and its learned solution makes target and pred1 mutually recursive, with pred1 true for odd numbers.Source: §G.2 · p. 52

G.3 Even / Succ2

• The Even / Succ2 experiment is described in Section 5.3.1.Source: §G.3 · p. 53

G.4 Less-Than

• The less-than task learns the relation over integers from 0 to 9 using the same language and background axioms as the preceding examples.Source: §G.4 · p. 53

G.5 Fizz

• The Fizz experiment is described in Section 5.3.3.Source: §G.5 · p. 53

G.6 Buzz

• The Buzz experiment is described in Section 5.3.3.Source: §G.6 · p. 53

G.7 Member

• The member task is to learn when an element X occurs in list Y, expressed by member(X, Y).List elements are represented with cons and value relations, and lists terminate at null node 0.Source: §G.7 · p. 53
• Member training uses two triples with lists [4, 3, 2, 1] and [2, 3, 2, 4], and treats all other target ground atoms as negatives.The supplied positive examples include target atoms for elements in both lists and their suffixes.Source: §G.7 · p. 53
• ∂ilp found one solution for the member task, though the supplied passage does not show the solution itself.The section introduces the solution but provides no rule or performance result in the supplied text.Source: §G.7 · p. 54

G.8 Length

• The length task learns whether list X has length Y and requires at least one auxiliary relation, pred1.It uses the same list representation as the member experiment.Source: §G.8 · p. 54
• Length training uses two triples with lists [1, 2, 3] and [3, 2, 1]; negatives are target ground atoms outside the positive set.The supplied text does not include the positive examples themselves.Source: §G.8 · p. 54
• ∂ilp found one solution for the length task, though the supplied passage does not show the solution itself.The section introduces the solution but provides no rule or performance result in the supplied text.Source: §G.8 · p. 54

G.9 Son

• ∂ilp’s son-of solution defines pred1 as male and makes X the son of Y when Y is X’s father and X is male.The learned male predicate holds when someone is the brother or father of another person.Source: §G.9 · pp. 54–55

G.10 Grandparent

• For grandparent, ∂ilp uses pred1 for parent-of, matching the solution reported by Muggleton et al. (2014).The task is learned from father-of and mother-of facts.Source: §G.10 · p. 55

G.11 Husband

• For husband-of, ∂ilp finds a solution from family facts involving father-of, daughter-of, and brother-of.The atomic facts come from the European family-tree dataset.Source: §G.11 · p. 55

G.12 Uncle

• For uncle-of, ∂ilp finds a solution using family facts involving father-of, mother-of, and brother-of, with pred1 defining parent-of.The background facts come from the European family-tree dataset.Source: §G.12 · p. 56

G.13 Relatedness

• For relatedness, target(X, Y) is true when an undirected path connects X and Y, and ∂ilp finds a solution to this task.The examples include target(a, a), target(f, a), and target(h, g) as positives, while target(g, a) and target(a, h) are negatives.Source: §G.13 · p. 56

• The task learns father-of from family-tree background and just two positives: Louis VII is father of Phillip II, and Henry VIII is father of Elizabeth I.Source: §G.14 · p. 56
• All other ground father-of atoms are negative, so ∂ilp must find a rule that entails the positives without entailing any negatives.Source: §G.14 · p. 57
• The available background predicates include husband, mother, brother, and aunt, but brother and aunt data are irrelevant and must be sifted out.Source: §G.14 · p. 57
• Validation uses fictitious family data and one positive example, George Donatus is father of Louis; all other target atoms are negative.Source: §G.14 · p. 57
• ∂ilp always finds the correct solution: X is father of Y when X is husband of Z and Z is mother of Y.Source: §G.14 · p. 57

G.15 Undirected Edge

• The target relation is true for X and Y when an edge connects them in either direction.Graphs are represented by edge(X, Y) atoms.Source: §G.15 · p. 58
• The first triple includes edge(a, b), edge(b, d), and edge(c, c), with positives in both directions for a-b and b-d and for c-c; the second gives positives for a-b and c-d in both directions.The passages identify two separate (B, P, N) triples, but do not provide the second triple’s background facts.Source: §G.15 · p. 58

G.16 Adjacent to Red

• The task is to infer whether a graph node is adjacent to red, using edge and node-colour predicates and at least one auxiliary monadic predicate.Source: §G.16 · p. 58
• ∂ilp found one solution for this task, which was trained using two separate (B, P, N) triples.Source: §G.16 · p. 58

G.17 Two Children

• The two-children task uses edge and neq relations plus an auxiliary relation to learn a predicate for nodes with at least two children.Source: §G.17 · p. 59
• Explicit neq is used in this setup; the authors say future negation-as-failure could make it unnecessary.Source: §G.17 · p. 59

G.18 Graph Colouring

• The graph-colouring task learns is-bad-node for a node adjacent to a node of the same colour, using edge and colour relations.Source: §G.18 · p. 59
• The invented pred1 relation holds for pairs of nodes of the same colour, and ∂ilp found one solution for the task.Source: §G.18 · pp. 59–60

G.19 Graph Connectedness

• The task is to learn connected(X, Y), true when some sequence of edge transitions connects X and Y.Source: §G.19 · p. 60
• The background facts are edge(a, b), edge(b, c), edge(c, d), and edge(b, a).Source: §G.19 · p. 60
• Positive examples include direct and multi-step connections, along with self-pairs target(a, a) and target(b, b).Source: §G.19 · p. 60
• ∂ilp finds the transitive closure of the edge relation as the solution to the connectedness task.Source: §G.19 · p. 60
• The transitive-closure relation is also synthesized as the recursive auxiliary predicate for Graph Cycles.Source: §G.19 · p. 60

G.20 Graph Cycles

• The detailed Graph Cycles experiment is described in Section 5.3.2.Source: §G.20 · p. 60