User:Felix QW/Inductive logic programming

Approaches to ILP

Bottom-up search

• Sketches of Golem and the Model Inference System
• Inverse resolution
• Least general generalisations

Top-down search

• Sketch of Progol/Aleph
• Beam search

Metainterpretative learning

• Metarules
• Constraint-based learning

Common issues

• Language bias
• Scoring functions
• Predicate invention
• Learning recursive programs

Probabilistic inductive logic programming

Probabilistic inductive logic programming adapts the setting of inductive logic programming to learning probabilistic logic programs. It can be considered as statistical relational learning within the formalism of probabilistic logic programming.

Given

1. background knowledge as a probabilistic logic program B, and
2. a set of positive and negative examples ${\textstyle E^{+}}$ and ${\textstyle E^{-}}$

the goal of probabilistic inductive logic programming is to find a probabilistic logic program ${\textstyle H}$ such that the probability of positive examples according to ${\textstyle {H\cup B}}$ is maximized and the probability of negative examples is minimized.

This problem has two variants: parameter learning and structure learning. In the first, one is given the structure (the clauses) of H and the goal is to infer the probabilities annotations of the given clauses, while in the second the goal was to infer both the structure and the probability parameters of H. Just as in classical inductive logic programming, the examples can be given as examples or as (partial) interpretations.

Parameter Learning

Parameter learning for languages following the distribution semantics has been performed by using an expectation-maximisation algorithm or by gradient descent. An expectation-maximisation algorithm consists of a cycle in which the steps of expectation and maximization are repeatedly performed. In the expectation step, the distribution of the hidden variables is computed according to the current values of the probability parameters, while in the maximisation step, the new values of the parameters are computed. Gradient descent methods compute the gradient of the target function and iteratively modify the parameters moving in the direction of the gradient.

Structure Learning

Structure learning was pioneered by Daphne Koller and Avi Pfeffer in 1997, where the authors learn the structure of first-order rules with associated probabilistic uncertainty parameters. Their approach involves generating the underlying graphical model in a preliminary step and then applying expectation-maximisation.

In 2008, De Raedt et al. presented an algorithm for performing theory compression on ProbLog programs, where theory compression means removing as many clauses as possible from the theory in order to maximize the probability. No new clause can be added to the theory.

In the same year, Meert, W. et al. introduced a method for learning parameters and structure of ground probabilistic logic programs by considering the Bayesian networks equivalent to them and applying techniques for learning Bayesian networks.

ProbFOIL, introduced by De Raedt and Ingo Thon in 2010, combined the inductive logic programming system FOIL with ProbLog. Logical rules are learned from probabilistic data in the sense that both the examples themselves and their classifications can be probabilistic. The set of rules has to allow to predict the probability of the examples from their description. In this setting, the parameters (the probability values) are fixed and the structure has to be learned.

In 2011, Elena Bellodi and Fabrizio Riguzzi introduced SLIPCASE, which performs a beam search among probabilistic logic programs by iteratively refining probabilistic theories and optimizing the parameters of each theory using expectation-maximisation. Its extension SLIPCOVER, proposed in 2014, uses bottom clauses generated as in Progol to guide the refinement process, thus reducing the number of revisions and exploring more effectively the search space. Moreover, SLIPCOVER separates the search for promising clauses from that of the theory: the space of clauses is explored with a beam search, while the space of theories is searched greedily.

 This article incorporates text from a free content work. Licensed under CC-BY 4.0 (license statement/permission). Text taken from A History of Probabilistic Inductive Logic Programming​, Fabrizio Riguzzi, Elena Bellodi and Riccardo Zese, Frontiers Media.