PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Explanatory Rules from Noisy Data

Richard Evans, Edward Grefenstette

arXiv:1711.04574v2cs.NEmath.LO

TL;DR

Neural systems handle noisy and ambiguous data but can overfit and lack inspectable symbolic rules, while ILP is data-efficient yet brittle and limited to symbolic inputs. The paper introduces ∂ILP, a differentiable ILP framework trained by gradient descent, and reports robust learning with mislabelled data and neural perceptual inputs while retaining ILP-style generalisation. Its main practical limitation is substantial memory demand.

  • Problem

    Neural networks face overfitting and require substantial data, whereas ILP is data-efficient but cannot robustly handle noise, mislabelling, or ambiguous non-symbolic inputs.

  • Method

    ∂ILP continuously relaxes ILP satisfiability and learns clause weights through backpropagation against cross-entropy loss.

  • Results

    Across 20 symbolic ILP tasks, ∂ILP consistently solved problems suited to traditional ILP, learned with 20% mislabelled examples, and learned effectively from pretrained convnet outputs while generalising consistently.

  • Takeaways & Limitations

    ∂ILP combines symbolic rule induction with robustness to noisy and ambiguous data, supporting end-to-end learning of perceptual and inferential rules.

  • Takeaways & Limitations

    Significant memory requirements limit the range of benchmark problems tested and require predicates of arity at most two.

Abstract

from arXiv · show

Artificial Neural Networks are powerful function approximators capable of modelling solutions to a wide variety of problems, both supervised and unsupervised. As their size and expressivity increases, so too does the variance of the model, yielding a nearly ubiquitous overfitting problem. Although mitigated by a variety of model regularisation methods, the common cure is to seek large amounts of training data---which is not necessarily easily obtained---that sufficiently approximates the data distribution of the domain we wish to test on. In contrast, logic programming methods such as Inductive Logic Programming offer an extremely data-efficient process by which models can be trained to reason on symbolic domains. However, these methods are unable to deal with the variety of domains neural networks can be applied to: they are not robust to noise in or mislabelling of inputs, and perhaps more importantly, cannot be applied to non-symbolic domains where the data is ambiguous, such as operating on raw pixels. In this paper, we propose a Differentiable Inductive Logic framework, which can not only solve tasks which traditional ILP systems are suited for, but shows a robustness to noise and error in the training data which ILP cannot cope with. Furthermore, as it is trained by backpropagation against a likelihood objective, it can be hybridised by connecting it with neural networks over ambiguous data in order to be applied to domains which ILP cannot address, while providing data efficiency and generalisation beyond what neural networks on their own can achieve.

1. Introduction

Traditional ILP is data-efficient and produces inspectable rules, but it is brittle to noise and ambiguity. ∂ILP combines differentiable neural processing with symbolic induction to retain explicit rules while handling noisy, ambiguous data and generalising beyond training examples.

  • ILP strengths: ILP constructs symbolic rules from positive and negative examples, entailing the positives while rejecting the negatives.It can be viewed as a rule-based binary classifier over examples.
  • ILP strengths: ILP is data-efficient because its language bias favors short, general programs over many ad-hoc special-case rules.Learned programs are explicit structures that can be inspected, understood, and verified.
  • Limitations and motivation: Traditional ILP cannot reliably handle mislabelled, noisy, erroneous, or ambiguous data, whereas neural systems tolerate such inputs and can process raw pixels.Neural program-induction systems trade symbolic inspectability and robust extrapolation for this flexibility.
  • Proposed framework: ∂ILP reimplements ILP as an end-to-end differentiable architecture intended to combine data-efficient, human-readable rule induction with robustness and generalisation.The system is trained through differentiable optimisation and is designed to connect with neural networks over ambiguous data.
  • Reported capabilities: ∂ILP learns moderately complex recursive programs with predicate invention, including Fizz-Buzz, and generalises robustly outside the training range.It also achieves reasonable performance with up to 20% mislabelled training data and learns effectively when connected to a convolutional network on MNIST.
  • Limitation: ∂ILP requires significant memory resources, limiting the range of benchmark problems tested.The paper notes that this restriction limits predicates to arity at most two.

2. Background

Logic programming represents computation with if-then clauses and derives consequences through repeated rule application. ILP learns such clauses from background facts and positive and negative examples under entailment-based criteria.

  • Logic programming: Logic programming uses if-then rules, or clauses, as its central computational component.Rules are read as deriving the head when all atoms in the body are true.
  • Representations: A ground atom contains no variables, and the set of all ground atoms is the Herbrand base.This paper restricts clauses to constants and variables, excluding function symbols.
  • Inference: Forward chaining repeatedly applies clauses to ground atoms until no further consequences can be derived.A ground atom is entailed when it belongs to the resulting consequence set.
  • Inductive logic programming: An ILP problem consists of background assumptions, positive examples, and negative examples.Background assumptions are ground atoms; positive and negative examples are formed from the target predicate and available constants.
  • Inductive logic programming: ILP seeks rules that entail the positive examples but do not entail the negative examples.The learned rules are applied deductively to the background assumptions to produce the desired conclusions.
  • Examples: The paper illustrates that ILP tasks can require recursion and predicate invention, such as an auxiliary successor predicate for a toy problem.These capabilities motivate the later differentiable implementation.

3. ILP as a Satisfiability Problem

The paper reformulates top-down ILP as satisfiability: generate candidate clauses from a program template, then select the subset whose consequences fit the examples. ∂ILP later relaxes these Boolean selections continuously.

  • Top-down induction: Top-down ILP generates clauses from a language definition and tests candidate programs against positive and negative examples.The paper adopts this generate-and-test strategy.
  • ILP as satisfiability: The satisfiability formulation assigns Boolean flags to generated clauses and seeks an assignment whose selected rules satisfy the examples.Selected clauses plus background facts must entail positives and avoid entailing negatives.
  • Program templates: A program template constrains the generated program space through auxiliary predicates, predicate arities, rule templates, and the inference-step limit T.The target predicate is an intensional predicate being learned.
  • Language construction: The language combines extensional predicates and constants with intensional predicates from the program template to define the ground atoms considered.The framework includes the always-false atom ⊥ in the ground-atom set.
  • Clause restrictions: Generated clauses exclude constants, support only predicate arities 0, 1, or 2, and impose structural restrictions such as safety and non-circularity.Clauses are also restricted to exactly two body atoms, with equivalent transformations available using auxiliary predicates.
  • Satisfiability encoding: Boolean variables indicate which candidate clauses are used, allowing a SAT solver to recover rules from the clauses assigned True.This converts rule induction into a satisfiability-solving problem.

4. A Differentiable Implementation of ILP

∂ILP replaces discrete ILP semantics and clause selection with continuous valuations and weights, then learns those weights by gradient descent. Differentiable forward chaining produces predicted labels from background facts and generated clauses.

  • Learning: ∂ILP minimises cross-entropy loss using stochastic gradient descent over differentiable replacements for the discrete induction process.The gradient with respect to rule weights implements continuous induction.
  • Continuous relaxation: The differentiable implementation replaces Boolean atom values with [0, 1] valuations and Boolean clause flags with continuous clause weights.The weights define a probability distribution over alternative clauses.
  • Differentiable inference: The finfer function performs T forward-chaining steps and combines clause conclusions using the learned clause weights.Each clause induces a differentiable valuation-to-valuation function for one inference step.
  • Architecture: The model predicts a sampled atom’s label by converting background facts into a valuation, generating clauses, running forward inference, and extracting the atom’s value.The conditional probability is computed through fextract, finfer, fconvert, and fgenerate.
  • Gradient path: The architecture permits non-differentiable preprocessing because the operations between the loss and clause weights remain differentiable.Clause indices can be computed discretely in advance while valuation operations remain differentiable.
  • Implementation trade-off: The matrix representation of clause weights requires substantial memory, while a less memory-intensive vector alternative performs worse on ILP tasks.The paper identifies this representation as a significant practical constraint.
  • Operator evaluation: Across 20 symbolic problems, the product t-norm consistently outperformed Gödel’s and Łukasiewicz’s t-norms.This comparison evaluates the alternative differentiable operators used in the system.

5. Experiments

Across symbolic, noisy, recursive, and perceptual tasks, ∂ILP learns rules that can generalise beyond training examples while retaining data-efficient symbolic structure. Its performance is nevertheless constrained by optimisation failures, memory demands, and the experimental setup.

  • 5.1 Hyperparameters: ∂ILP solved all 10 symbolic tasks for at least 5% of random weight initialisations using both RMSProp and Adam.RMSProp succeeded across learning rates from 0.5 to 0.01.
  • 5.3.2 Learning Graph Cyclicity: ∂ILP solved graph cyclicity 100% of the time, requiring an invented recursive predicate representing transitive closure.The result was independent of initial random weights.
  • 5.3.3 Learning Fizz-Buzz: ∂ILP learned Fizz-Buzz with invented predicates and generalised robustly to unseen test data, although it found the correct solution in only 30% of weight initialisations.The paper presents this as the first neural program induction system reported to learn Fizz-Buzz and generalise robustly.
  • 5.3.4 Results on All Symbolic Tasks: On 20 symbolic tasks, Metagol sometimes timed out on recursive cycles, while ∂ILP’s main limitation was memory consumption restricting it to nullary, unary, and binary predicates.The authors caution that direct comparison is difficult because the systems require different program templates.
  • 5.4 Dealing with Mislabelled Data: With mislabelled data, ∂ILP’s mean squared error degraded gradually; at 10% mislabelling it still found perfect answers on 5 of 6 tasks.Some tasks retained good answers with 20% or 30% mislabelled data.
  • 5.5 Learning from Raw Pixel Images: In raw-pixel experiments, ∂ILP was robust when 70% of the data was held out, while its perceptual front end was initially pretrained and frozen.The reported setup therefore did not yet train the convolutional network jointly with ∂ILP.

6. Related Work

The related work spans neural implementations of logic, differentiable semantics, probabilistic relational models, and methods for learning or executing first-order programs. The paper distinguishes its Datalog-focused, differentiable induction approach from prior systems in expressivity, practicality, and symbolic program extraction.

  • Neural execution of logic: Earlier theory showed that recurrent or multilayer neural networks can approximate forward-chaining consequences of acyclic logic programs.These constructions encode sets of ground atoms as real numbers and use continuous-function approximation.
  • Neural execution of logic: Theoretical neural encodings are impractical because representing an entire set of ground atoms with one real number assumes arbitrary-precision floating-point numbers.A later implementation replaces the single real with a distributed vector representation.
  • Comparison with prior systems: Bader et al. learn acyclic programs with differentiable forward chaining, whereas ∂ilp targets Datalog programs and supports mutual recursion.Their hidden units encode particular ground-atom models, while ∂ilp applies universally quantified clauses across atom pairs.
  • Comparison with prior systems: The prior acyclic-program approach hides the learned program in neural weights, making extraction of an explicit symbolic program non-obvious.This contrasts with the paper’s emphasis on differentiable induction of symbolic rules.
  • Continuous and probabilistic logic: Real Logic generalizes first-order semantics to real-valued truth degrees and supports full first-order logic, but performs continuous abduction rather than induction.Its objective extends a given atom assignment to minimize discrepancies with continuous truth values.
  • Continuous and probabilistic logic: Other related systems include fibred neural networks for recursive programs and Logical HMMs that assign probabilities to first-order state transitions.Fibred networks cannot represent rules with existentially quantified body variables absent from the head; LOHMM rules explicitly encode probabilistic transitions.
  • Comparison with prior systems: Compared with CILP++, ∂ilp can learn recursive clauses and mutual recursion, but its memory requirements currently restrict it to small datasets.CILP++ cannot learn recursive clauses because its bottom-clause bodies contain only extensional predicates.

7. Discussion

The discussion presents ∂ilp as a differentiable ILP system that retains symbolic learning strengths while extending robustness and applicability to noisy and ambiguous data. Experiments support performance on symbolic, mislabelled, and perceptual tasks, while program-template dependence and reliance on pretrained vision classifiers remain limitations.

  • 7.1 Program Templates and Language Bias: A key weakness is the continuing need for program templates, while avoiding hand-engineering through iterative deepening is hugely computationally expensive.The authors identify a less brute-force search strategy as future work.
  • 7.2 Conclusion: ∂ilp’s main contribution is a differentiable ILP implementation that learns recursive programs with multiple invented predicates.The framework is intended to combine perceptual and inferential rule learning in an end-to-end differentiable system.
  • 7.2 Conclusion: Unlike traditional symbolic ILP, the model is robust to mislabelled training data and can handle ambiguous inputs through neural connections.The paper positions this as extending ILP-style data efficiency and generalisation to domains involving neural-network processing.
  • 7.2 Conclusion: The model was evaluated on 20 symbolic ILP tasks, learned good models with 20% mislabelled training examples, and generalised consistently when connected to a pretrained convnet.The ambiguous-data experiments connected convnet outputs to the induction system.
  • 7.2 Conclusion: The ambiguous-data experiments relied on pretrained neural classifiers and incorporated prior knowledge that MNIST images form ten digit classes.Preliminary partial-training experiments were satisfactory and interpretable, but full end-to-end joint training remained unfinished in the supplied passage.
  • Notation: The paper’s notation distinguishes ground-atom sets, predicates, constants, variables, scalars, vectors, matrices, tensors, and vector elements.These conventions support the formal presentation of the differentiable logic framework.

Appendix B. ILP as Satisfiability

The appendix recasts ILP rule induction as a satisfiability problem by generating candidate clauses and selecting them with Boolean flags. The selected flags are then converted back into a logic program, illustrated by learning transitive closure.

  • Rule templates: Rule templates constrain generated clauses by specifying existential-variable counts and whether intensional predicates may appear in rule bodies.The example uses one template with no existential variables and another requiring one existential variable and an intensional body predicate.
  • Clause generation: Uniform two-atom clause bodies permit automatically generated clauses with repeated atoms and support the later matrix-based approach.Repeated atoms are retained because all clauses are required to have the same body size.
  • Satisfiability encoding: Exactly one flag is turned on for each rule template, defining which candidate clauses are included.A candidate ILP solution is represented as a subset of the Boolean variables.
  • Satisfiability encoding: The method transforms finding a set R of logic rules into finding a subset F of Boolean clause-selection atoms.Each Boolean indicates whether a generated clause is used in the program.
  • Program extraction: The selected flags can be decoded into a logic program whose learned target predicate is the transitive closure of p.This demonstrates that the satisfiability solution corresponds to an interpretable ILP program.
  • Relation to other ILP biases: Compared with mode declarations and Metagol metarules, ∂ilp templates specify less precise predicate, variable-binding, and recursion structure.This gives ∂ilp a less restrictive rule-template language than the cited alternatives.

Appendix G. The 20 Benchmark ILP Experiments

The benchmark section describes twenty ILP experiments covering arithmetic relations and related symbolic tasks. The supplied examples include predecessor, even, and less-than learning, with solutions produced by ∂ilp.

  • Benchmark scope: The paper evaluates ∂ilp across twenty benchmark experiments.The section introduces the experiments before detailing individual tasks.
  • Arithmetic tasks: The predecessor task learns the predecessor relation from zero and successor background knowledge and positive and negative examples.Negative examples are target atoms over integers 0 through 9 that are not positive examples.
  • Arithmetic tasks: The even task uses the same arithmetic background knowledge but requires an auxiliary predicate pred1.The reported solution makes target and pred1 mutually recursive, with pred1 true for odd numbers.
  • Arithmetic tasks: The less-than task uses the same language and background axioms with integers restricted to 0 through 9.The section reports a solution found by ∂ilp for this task.

G.7 Member

The member benchmark learns list membership from structural list relations across two training instances. Its reported solution is paired with a length task that requires an auxiliary relation.

  • Member: The member task defines list membership using cons links between nodes and value assignments to nodes.Lists terminate at the null node 0, and member(X, Y) means X is an element of list Y.
  • Member: Training uses two separate (B, P, N) triples, with lists [4, 3, 2, 1] and [2, 3, 2, 4].Positive examples enumerate members of the full and suffix lists, while negatives are the remaining target atoms.
  • Member: ∂ilp finds a solution for the member task.The supplied passage reports the solution without reproducing its clauses.
  • Length: The related length task represents lists identically and requires at least one auxiliary relation pred1.It is also trained on two separate background, positive, and negative example triples.
  • Length: One solution is reported for the length task.The supplied passage identifies the learned solution but does not state its clauses.

G.9 Son

The son benchmark learns a family relation from father, brother, and sister facts, using an auxiliary predicate. The reported solution defines maleness and combines it with the father relation to identify sons.

  • Son: The son task learns the son-of relation from family-tree facts involving father-of, brother-of, and sister-of relations.The task uses an auxiliary monadic predicate pred1 and constants representing people.
  • Son: The sister-of facts are irrelevant to the son task.The passage explicitly distinguishes them from the facts used for the target relation.
  • Son: ∂ilp reports a solution in which pred1 defines the is-male property from being someone’s brother or father.The auxiliary predicate is therefore an invented intermediate relation.
  • Son: The learned target rule identifies X as Y’s son when Y is X’s father and X is male.This clause combines the father relation with the invented male predicate.
  • Related family tasks: The supplied benchmark suite also includes grandparent, husband, uncle, and related-relation tasks drawn partly from family-tree data.These neighboring tasks use auxiliary predicates in several cases, including parent-of for the uncle task.

G.14 Father

The Father task learns the father-of relation from a family-tree background and two positive examples, treating other father-of atoms as negative. ∂ilp finds the correct rule despite irrelevant background relations.

  • The task learns father-of from fictitious family-tree data centered on Louis VII and Henry VIII, using two positive examples.
  • All other ground atoms involving father-of are treated as false and added to the negative examples.
  • The background includes husband, mother, brother, and aunt relations, although brother and aunt data are irrelevant to solving the task.
  • ∂ilp always finds the correct solution in this simple task.
  • The learned rule states that someone is father of Y when they are husband of Z and Z is mother of Y.

G.15 Undirected Edge

The Undirected Edge task learns a relation that holds when an edge connects two nodes in either direction. Training uses separate background, positive, and negative example triples, and ∂ilp produces a solution program.

  • The target relation is true for X and Y when an edge exists between them in either direction.
  • The system trains on two separate (B, P, N) triples containing graph backgrounds and positive target atoms.
  • The second training triple includes positive examples target(a, b), target(b, a), target(c, d), and target(d, c).
  • ∂ilp returns a solution for the Undirected Edge task.

G.16 Adjacent to Red

The graph experiments show ∂ilp learning relational predicates involving node colours, child counts, same-colour adjacency, and graph connectivity, often using auxiliary predicates.

  • G.16 Adjacent to Red: The Adjacent to Red task learns whether a node is adjacent to a red node from edge and colour relations.
  • G.16 Adjacent to Red: The Adjacent to Red task requires at least one auxiliary monadic predicate pred1, and ∂ilp finds one solution.
  • Has at Least Two Children: The Has at Least Two Children task uses edge and not-equals relations and requires an auxiliary relation pred1.
  • Has at Least Two Children: The paper plans to add negation-as-failure so the neq relation will not need to be included explicitly.
  • The paper also reports learned solutions for the Has at Least Two Children and Is-Bad-Node tasks.
  • Is-Bad-Node: The Is-Bad-Node task identifies nodes adjacent to nodes of the same colour and uses an auxiliary relation pred1 for shared colour.

G.19 Graph Connectedness

The Graph Connectedness task learns whether two nodes are connected by a sequence of edge transitions. ∂ilp synthesises the transitive closure of the edge relation, including recursive connectivity.

  • The target connected(X, Y) relation is true when some sequence of edge transitions connects X and Y.
  • The training positives include direct edges, multi-step connections, and self-connections such as target(a, a) and target(b, b).
  • ∂ilp finds a solution for the Graph Connectedness task.
  • The learned solution is the transitive closure of the edge relation and matches the recursive auxiliary predicate used for the Graph Cycles task.
Loading 1711.04574v2…