Repository files navigation

Popper is aninductive logic programming system. Popper combines logical reasoning with machine learning to induce rules from examples and background knowledge.

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

If you have any questions, ask us onDiscord or emailAndrew Cropper.

• SWI-Prolog (9.2.0 or above)
• Clingo (5.6.2 or above)
• Janus-swi
• pysat
• bitarray

Install Popper with the commandpip install git+https://github.com/logic-and-learning-lab/Popper@main

Run Popper with the commandpython popper.py <input dir>. For instance,python popper.py examples/zendo1 produces:

********** SOLUTION **********Precision:1.00Recall:1.00TP:20FN:0TN:20FP:0Size:6zendo(V0):- small(V2),piece(V0,V1),red(V1),contact(V1,V3),size(V3,V2).******************************

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 search space of Popper. Predicate declarations tell Popper which predicate symbols it can use in the head (head_pred) or body (body_pred) of a rule, such as:

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

These declarations say that Popper can use the symbolgrandparent with two arguments in the head of a rule andmother orfather in the body, also each with two arguments.

Popper can learn fromnoisy data with the--noisy flag. Popper learns the minimal description length program.

Popper can learn recursive programs where a predicate symbol appears in both the head and body of a rule, such as to find a duplicate element (python popper.py examples/find-dupl) 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, addenable_recursion. to the bias file. However, recursion is expensive, so it is best to avoid it if possible.

Popper supports type annotations in the bias file. A type annotation is of the formtype(p,(t1,t2,...,tk) for a predicate symbolp with arityk, such as:

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

Types areoptional but can substantially reduce learning times.

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

Xis3+K.

It throws an error:

ERROR:Argumentsarenotsufficientlyinstantiated

To avoid these issues, Popper supportsoptional direction annotations. A direction annotation is of the formdirection(p,(d1,d2,...,dk) for a predicate symbolp with arityk, where eachdi is eitherin orout.Anin variable must be ground when calling the relation. By contrast, anout 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.

Popper has two important bias settings:

• max_vars(N) sets the maximum number of variables in a rule toN (default: 6)
• max_body(N) sets the maximum number of body literals in a rule toN (default: 6)

These settings greatly influence performance. If the values are too high, Popper might struggle to find a solution. If the settings are too low, the search space might be too small to contain a good solution.

Popper supportsautomatic predicate invention (PI). With PI enabled, Popper (python popper.py examples/kinship-pi) learns the program:

grandparent(A,B):-inv1(C,B),inv1(A,C).inv1(A,B):-mother(A,B).inv1(A,B):-father(A,B).% Precision:1.00, Recall:1.00, TP:5, FN:0, TN:1, FP:0

To enable PI, add the settingenable_pi. to the bias file. However, predicate invention is currentlyvery expensive so it is best to avoid it if possible.

• --noisy (default: false) learn fromnoisy (misclassified examples)
• --stats (default: false) shows runtime statistics
• --debug (default: false) runs in debug mode
• --quiet (default: False) runs in quiet mode
• --timeout (default: 1200 seconds) sets a maximum learning time
• --eval-timeout (default: 0.001 seconds) sets a maximum example testing time. This flag only applies when learning recursive programs.
• --solver {rc2,uwr,wmaxcdcl}(default:rc2) which exact solver to use
• --anytime-solver {wmaxcdcl,nuwls}(default:None) which anytime solver to use
• --anytime-timeout (default: 10 seconds) sets the maximum time allowed by the anytime solver

Popper uses various MaxSAT solvers. By default, Popper uses theRC2 exact solver provided by PySAT. Popper also supports these solvers:

• UWrMaxSat (exact)
• WMaxCDCL (exact)
• NuWLS (anytime)

You can download and compile these solvers from theMaxSAT 2023 evaluation website.We strongly recommend using the anytime NuWLS solver as it greatly improves the performance of Popper. To use them, ensure that the solver is available on your path. See theinstall solvers file for help.

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

You can import Popper and use it in your Python code like so:

frompopper.utilimportSettings,print_prog_scorefrompopper.loopimportlearn_solutionsettings=Settings(kbpath='input_dir')prog,score,stats=learn_solution(settings)ifprog!=None:print_prog_score(prog,score)

If you want to make Popper better, look at thediscussion page for open problems or emailAndrew Cropper.