Popper

Popper

Popper is an inductive logic programming system. Popper learns logical rules from examples and background knowledge.

Ask questions on Discord or email Andrew Cropper.

If you use Popper, please cite the paper learning programs by learning from failures (MLJ 2021).

Requirements

• SWI-Prolog (brew install swi-prolog)
• GNU Coreutils (brew install coreutils)
• uv package manager (brew install uv)

Install and run

git clone https://github.com/logic-and-learning-lab/Popper.git
cd Popper

Then run via uv run popper.py <input dir> such as uv run popper.py examples/iggp-rps-next-score

Example problem

Popper requires three input files:

• an examples file
• a background knowledge (BK) file
• a bias file

An examples file contains positive and negative examples of the relation you want to learn:

pos(grandparent(ann,amelia)).
pos(grandparent(steve,amelia)).
pos(grandparent(ann,spongebob)).
neg(grandparent(amy,amelia)).

A BK file contains other information about the problem:

mother(ann,amy).
mother(ann,andy).
mother(amy,amelia).
mother(linda,gavin).
father(steve,amy).
father(steve,andy).
father(gavin,amelia).
father(andy,spongebob).

A bias file defines the hypothesis space. The following statements tell Popper which predicate symbols it can use in the head (head_pred) or body (body_pred) of a rule:

head_pred(grandparent,2).
body_pred(mother,2).
body_pred(father,2).

These say that Popper can use the symbol grandparent with two arguments in the head of a rule and mother or father in the body, also each with two arguments.

Noise

Popper can learn from noisy data with the --noisy flag. Popper learns a minimal description length hypothesis.

Settings

• --noisy, -n learn from noisy data using an MDL cost function (default: false)
• --max-vars N maximum number of variables in a rule (default: 6)
• --max-body N maximum number of body literals in a rule (default: 10)
• --timeout N maximum learning time in seconds (default: 3600)
• -v, -vv, -vvv increase verbosity
• --nuwls use the NuWLS solver (default: false)

Solvers

Popper uses the CPSAT solver by default for its combine stage. Popper also supports the NuWLS anytime MaxSAT solver. You can download and compile this solver from the MaxSAT 2023 evaluation website. We strongly recommend using NuWLS as it greatly improves the performance of Popper. To use them, ensure that the solver is available on your path. See the install solvers file for help.

Recursion

Popper can learn recursive rules (where a predicate symbol appears in both the head and body), such as to find a duplicate element (uv run popper.py examples/synthesis-finddupl) in a list:

f(A,B):- tail(A,C),head(A,B),element(C,B).
f(A,B):- tail(A,C),f(C,B).

To enable recursion, add enable_recursion. to the bias file. However, recursion is expensive, so it is best to avoid it if possible.

Types

Popper supports type annotations in the bias file. A type annotation is of the form type(p,(t1,t2,...,tk) for a predicate symbol p with arity k, such as:

type(head,(list,element)).
type(tail,(list,list)).
type(length,(list,int,)).
type(empty,(list,)).
type(prepend,(element,list,list)).

Types are optional but can substantially reduce learning times.

Directions

Prolog often requires arguments to be ground. For instance, when asking Prolog to answer the query:

X is 3+K.

It throws an error:

ERROR: Arguments are not sufficiently instantiated

To avoid these issues, Popper supports optional direction annotations. A direction annotation is of the form direction(p,(d1,d2,...,dk) for a predicate symbol p with arity k, where each di is either in or out. An in variable must be ground when calling the relation. By contrast, an out variable need not be ground. Here are example directions:

direction(head,(in,out)).
direction(tail,(in,out)).
direction(length,(in,out)).
direction(prepend,(in,in,out)).
direction(geq,(in,in)).

Popper cannot learn with partial directions. If you provide them, you must provide them for all relations.

Performance tips

• Transform your BK to Datalog, which allows Popper to perform preprocessing on the BK
• Try the NuWLS anytime solver
• Use 7 variables or fewer
• Avoid recursion and predicate invention