Inductive logic programming

Inductive logic programming (ILP) is a subfield of machine learning which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples.

• Schema: positive examples + negative examples + background knowledge ⇒ hypothesis.

Inductive logic programming is particularly useful in bioinformatics and natural language processing. Gordon Plotkin and Ehud Shapiro laid the initial theoretical foundation for inductive machine learning in a logical setting.^[1][2][3] Shapiro built its first implementation (Model Inference System) in 1981:^[4] a Prolog program that inductively inferred logic programs from positive and negative examples. The term Inductive Logic Programming was first introduced^[5] in a paper by Stephen Muggleton in 1991.^[6] Muggleton also founded the annual international conference on Inductive Logic Programming, introduced the theoretical ideas of Predicate Invention, Inverse resolution,^[7] and Inverse entailment,.^[8] Muggleton implemented Inverse entailment first in the PROGOL system. The term "inductive" here refers to philosophical (i.e. suggesting a theory to explain observed facts) rather than mathematical (i.e. proving a property for all members of a well-ordered set) induction.

Formal definition

The background knowledge is given as a logic theory B, commonly in the form of Horn clauses used in logic programming. The positive and negative examples are given as a conjunction $E^+$ and $E^-$ of unnegated and negated ground literals, respectively. A correct hypothesis h is a logic proposition satisfying the following requirements.^[9]

$\begin{array}{llll} \text{Necessity:} & B & \not\models & E^+ \\ \text{Sufficiency:} & B \land h & \color{blue}{\models} & E^+ \\ \text{Weak consistency:} & B \land h & \not\models & \textit{false} \\ \text{Strong consistency:} & B \land h \land E^- & \not\models & \textit{false} \end{array}$

"Necessity" does not impose a restriction on h, but forbids any generation of a hypothesis as long as the positive facts are explainable without it. "Sufficiency" requires any generated hypothesis h to explain all positive examples $E^+$. "Weak consistency" forbids generation of any hypothesis h that contradicts the background knowledge B. "Strong consistency" also forbids generation of any hypothesis h that is inconsistent with the negative examples $E^-$, given the background knowledge B; it implies "Weak consistency"; if no negative examples are given, both requirements coincide. Džeroski ^[10] requires only "Sufficiency" (called "Completeness" there) and "Strong consistency".

Example

Assumed family relations in section "Example"

The following well-known example about learning definitions of family relations uses the abbreviations

$\textit{par}: \textit{parent}$, $\textit{fem}: \textit{female}$, $\textit{dau}: \textit{daughter}$,

$g:\textit{George}$, $h:\textit{Helen}$, $m:\textit{Mary}$, $t:\textit{Tom}$, $n:\textit{Nancy}$, and $e:\textit{Eve}$.

It starts from the background knowledge (cf. picture)

$\textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e)$,

the positive examples

$\textit{dau}(m,h) \land \textit{dau}(e,t)$,

and the trivial proposition $\textit{true}$ to denote the absence of negative examples.

Plotkin's ^[11][12] "relative least general generalization (rlgg)" approach to inductive logic programming shall be used to obtain a suggestion about how to formally define the daughter relation $\textit{dau}$.

This approach uses the following steps.

• Relativize each positive example literal with the complete background knowledge:

  $\begin{align} \textit{dau}(m,h) \leftarrow \textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e) \\ \textit{dau}(e,t) \leftarrow \textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e) \end{align}$,

• Convert into clause normal form:

  $\begin{align} \textit{dau}(m,h) \lor \lnot \textit{par}(h,m) \lor \lnot \textit{par}(h,t) \lor \lnot \textit{par}(g,m) \lor \lnot \textit{par}(t,e) \lor \lnot \textit{par}(n,e) \lor \lnot \textit{fem}(h) \lor \lnot \textit{fem}(m) \lor \lnot \textit{fem}(n) \lor \lnot \textit{fem}(e) \\ \textit{dau}(e,t) \lor \lnot \textit{par}(h,m) \lor \lnot \textit{par}(h,t) \lor \lnot \textit{par}(g,m) \lor \lnot \textit{par}(t,e) \lor \lnot \textit{par}(n,e) \lor \lnot \textit{fem}(h) \lor \lnot \textit{fem}(m) \lor \lnot \textit{fem}(n) \lor \lnot \textit{fem}(e) \end{align}$,

• Anti-unify each compatible ^[13] pair ^[14] of literals:
  • $\textit{dau}(x_{me},x_{ht})$ from $\textit{dau}(m,h)$ and $\textit{dau}(e,t)$,
  • $\lnot \textit{par}(x_{ht},x_{me})$ from $\lnot \textit{par}(h,m)$ and $\lnot \textit{par}(t,e)$,
  • $\lnot \textit{fem}(x_{me})$ from $\lnot \textit{fem}(m)$ and $\lnot \textit{fem}(e)$,
  • $\lnot \textit{par}(g,m)$ from $\lnot \textit{par}(g,m)$ and $\lnot \textit{par}(g,m)$, similar for all other background-knowledge literals
  • $\lnot \textit{par}(x_{gt},x_{me})$ from $\lnot \textit{par}(g,m)$ and $\lnot \textit{par}(t,e)$, and many more negated literals
• Delete all negated literals containing variables that don't occur in a positive literal:
  • after deleting all negated literals containing other variables than $x_{me},x_{ht}$, only $\textit{dau}(x_{me},x_{ht}) \lor \lnot \textit{par}(x_{ht},x_{me}) \lor \lnot \textit{fem}(x_{me})$ remains, together with all ground literals from the background knowledge
• Convert clauses back to Horn form:
  • $\textit{dau}(x_{me},x_{ht}) \leftarrow \textit{par}(x_{ht},x_{me}) \land \textit{fem}(x_{me}) \land (\text{all background knowledge facts})$

The resulting Horn clause is the hypothesis h obtained by the rlgg approach. Ignoring the background knowledge facts, the clause informally reads "$x_{me}$ is called a daughter of $x_{ht}$ if $x_{ht}$ is the parent of $x_{me}$ and $x_{me}$ is female", which is a commonly accepted definition.

Concerning the above requirements, "Necessity" was satisfied because the predicate $\textit{dau}$ doesn't appear in the background knowledge, which hence cannot imply any property containing this predicate, such as the positive examples are. "Sufficiency" is satisfied by the computed hypothesis h, since it, together with $\textit{par}(h,m) \land \textit{fem}(m)$ from the background knowledge, implies the first positive example $\textit{dau}(m,h)$, and similarly h and $\textit{par}(t,e) \land \textit{fem}(e)$ from the background knowledge implies the second positive example $\textit{dau}(e,t)$. "Weak consistency" is satisfied by h, since h holds in the (finite) Herbrand structure described by the background knowledge; similar for "Strong consistency".

The common definition of the grandmother relation, viz. $\textit{gra}(x,z) \leftarrow \textit{fem}(x) \land \textit{par}(x,y) \land \textit{par}(y,z)$, cannot be learned using the above approach, since the variable y occurs in the clause body only; the corresponding literals would have been deleted in the 4th step of the approach. To overcome this flaw, that step has to be modified such that it can be parametrized with different literal post-selection heuristics. Historically, the GOLEM implementation is based on the rlgg approach.

Inductive Logic Programming system

Inductive Logic Programming system is a program that takes as an input logic theories $B, E^+, E^-$ and outputs a correct hypothesis H wrt theories $B, E^+, E^-$ An algorithm of an ILP system consists of two parts: hypothesis search and hypothesis selection. First a hypothesis is searched with an inductive logic programming procedure, then a subset of the found hypotheses (in most systems one hypothesis) is chosen by a selection algorithm. A selection algorithm scores each of the found hypotheses and returns the ones with the highest score. An example of score function include minimal compression length where a hypothesis with a lowest Kolmogorov complexity has the highest score and is returned. An ILP system is complete iff for any input logic theories $B, E^+, E^-$ any correct hypothesis H wrt to these input theories can be found with its hypothesis search procedure.

Hypothesis search

Modern ILP systems like Progol,^[6] Hail ^[15] and Imparo ^[16] find a hypothesis H using the principle of the inverse entailment^[6] for theories B, E, H: $B \land H \models E \iff B \land \neg E \models \neg H$. First they construct an intermediate theory F called a bridge theory satisfying the conditions $B \land \neg E \models F$ and $F \models \neg H$. Then as $H \models \neg F$, they generalize the negation of the bridge theory F with the anti-entailment.^[17] However, the operation of the anti-entailment since being highly non-deterministic is computationally more expensive. Therefore, an alternative hypothesis search can be conducted using the operation of the inverse subsumption (anti-subsumption) instead which is less non-deterministic than anti-entailment.

Questions of completeness of a hypothesis search procedure of specific ILP system arise. For example, Progol's hypothesis search procedure based on the inverse entailment inference rule is not complete by Yamamoto's example.^[18] On the other hand, Imparo is complete by both anti-entailment procedure ^[19] and its extended inverse subsumption ^[20] procedure.

Implementations

• 1BC and 1BC2: first-order naive Bayesian classifiers: (http://www.cs.bris.ac.uk/Research/MachineLearning/1BC/)
• ACE (A Combined Engine) (http://dtai.cs.kuleuven.be/ACE/)
• Aleph (http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/)
• Atom (http://www.ahlgren.info/research/atom/)
• Claudien (http://dtai.cs.kuleuven.be/claudien/)
• DL-Learner (http://dl-learner.org)
• DMax (http://dtai.cs.kuleuven.be/dmax/)
• FOIL (ftp://ftp.cs.su.oz.au/pub/foil6.sh)
• Golem (ILP) (http://www.doc.ic.ac.uk/~shm/Software/golem)
• Imparo^[19]
• Inthelex (INcremental THEory Learner from EXamples) (http://lacam.di.uniba.it:8000/systems/inthelex/)
• Lime (http://cs.anu.edu.au/people/Eric.McCreath/lime.html)
• Mio (http://libra.msra.cn/Publication/3392493/mio-user-s-manual)
• MIS (Model Inference System) by Ehud Shapiro
• PROGOL (http://www.doc.ic.ac.uk/~shm/Software/progol5.0)
• RSD (http://labe.felk.cvut.cz/~zelezny/rsd/)
• Tertius (http://www.cs.bris.ac.uk/publications/Papers/1000545.pdf)
• Warmr (now included in ACE)
• ProGolem (http://ilp.doc.ic.ac.uk/ProGolem/) ^[21][22]

See also

• Commonsense reasoning
• Formal concept analysis
• Inductive inference
• Inductive reasoning
• Inductive programming
• Inductive probability
• Statistical relational learning
• Version space learning

References

1. Plotkin G.D. Automatic Methods of Inductive Inference, PhD thesis, University of Edinburgh, 1970.
2. Shapiro, Ehud Y. Inductive inference of theories from facts, Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press, Cambridge, MA, 1991, pp. 199–254.
3. Shapiro, Ehud Y. (1983). Algorithmic program debugging. Cambridge, Mass: MIT Press. ISBN 0-262-19218-7
4. Shapiro, Ehud Y. "The model inference system." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.
5. Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. CiteSeerX: 10.1.1.56.1790
6. Muggleton, S.H. (1991). "Inductive logic programming". New Generation Computing 8 (4): 295–318. doi:10.1007/BF03037089.
7. Muggleton S.H. and Buntine W. "Machine invention of first-order predicate by inverting resolution","Proceedings of the 5th International Conference on Machine Learning, 1988.
8. Muggleton S.H., "Inverting entailment and Progol", New Generation Computing, 13:245-286, 1995.
9. Muggleton, Stephen (1999). "Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic". Artificial Intelligence 114: 283–296. doi:10.1016/s0004-3702(99)00067-3.; here: Sect.2.1
10. Džeroski, Sašo (1996), "Inductive Logic Programming and Knowledge Discovery in Databases", in Fayyad, U.M.; Piatetsky-Shapiro, G.; Smith, P.; Uthurusamy, R., Advances in Knowledge Discovery and Data Mining, MIT Press, pp. 117–152; here: Sect.5.2.4
11. Plotkin, Gordon D. (1970). Meltzer, B.; Michie, D., eds. "A Note on Inductive Generalization". Machine Intelligence (Edinburgh University Press) 5: 153–163.
12. Plotkin, Gordon D. (1971). Meltzer, B.; Michie, D., eds. "A Further Note on Inductive Generalization". Machine Intelligence (Edinburgh University Press) 6: 101–124.
13. i.e. sharing the same predicate symbol and negated/unnegated status
14. in general: n-tuple when n positive example literals are given
15. Ray, O., Broda, K., & Russo, A. M. (2003). Hybrid abductive inductive learning. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.
16. Kimber, T., Broda, K., & Russo, A. (2009). Induction on failure: learning connected Horn theories. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.
17. Yoshitaka Yamamoto, Katsumi Inoue, and Koji Iwanuma. Inverse subsumption for complete explanatory induction. Machine learning, 86(1):115–139, 2012.
18. Akihiro Yamamoto. Which hypotheses can be found with inverse entailment? In Inductive Logic Programming, pages 296–308. Springer, 1997.
19. Timothy Kimber. Learning definite and normal logic programs by induction on failure. PhD thesis, Imperial College London, 2012.
20. David Toth (2014). Imparo is complete by inverse subsumption. arXiv:1407.3836
21. Muggleton, Stephen; Santos, Jose; Tamaddoni-Nezhad, Alireza (2009). "ProGolem: a system based on relative minimal generalization" (PDF). ILP.
22. Santos, Jose; Nassif, Houssam; Page, David; Muggleton, Stephen; Sternberg, Mike (2012). "Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study" (PDF). BMC Bioinformatics 13: 162. doi:10.1186/1471-2105-13-162.

Further reading

• Muggleton, S.; De Raedt, L. (1994). "Inductive Logic Programming: Theory and methods". The Journal of Logic Programming. 19-20: 629–679. doi:10.1016/0743-1066(94)90035-3.
• Lavrac, N.; Dzeroski, S. (1994). Inductive Logic Programming: Techniques and Applications. New York: Ellis Horwood. ISBN 0-13-457870-8.
• Visual example of inducing the grandparenthood relation by the Atom system. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html