Programmation logique inductive

La programmation logique inductive (ILP de l'anglais Inductive Logic Programming) est un sous-domaine de l'apprentissage automatique basée sur la programmation logique.

Introduction

À partir d'un ensemble de connaissances préalables et de résultats attendus, divisés en exemples positifs et négatifs, un système ILP déduit un programme logique hypothétique qui confirme les exemples positifs et infirme les exemples négatifs. On peut résumer le principe de fonctionnement d'un système ILP par le schéma suivant :

• exemples positifs + exemples négatifs + connaissances préalables ⇒ programme hypothétique.

La programmation logique inductive est particulièrement utile en bio-informatique et pour le traitement automatique du langage naturel.

Historique

Gordon Plotkin et Ehud Shapiro (en) ont posé les fondations théoriques de l'apprentissage automatique inductif dans un contexte logique^[1],[2],[3]. Shapiro créa une première implémentation (Model Inference System) en 1981^[4]: un programme Prolog capable d'inférer par induction un programme logique à partir d'exemples positifs et négatifs. Le terme programmation logique inductive (en anglais) fut utilisé pour la première fois^[5] dans un article de Stephen Muggleton (en) en 1991^[6]. Muggleton est aussi à l'origine de la création de la conférence internationale de programmation logique inductive, un événement annuel. Il a défini les notions théoriques d'invention de prédicat, de résolution inversée^[7] et d'implication inversée^[8]. Le système PROGOL (en) développé par Muggleton implémente l'implication inversée. Le terme inductive fait ici référence à la notion philosophique et logique d'induction (le fait de suggérer une théorie pour expliquer des faits observés) plutôt qu'à son pendant mathématique (le fait de prouver une propriété pour tous les membres d'un ensemble bien fondé).

Notes et références

Notes

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Inductive logic programming » (voir la liste des auteurs).

Références

1. (en) Gordon David Plotkin (sous la direction de Rodney Burstall (en)), Automatic methods of inductive inference [« Méthodes automatiques d'inférence inductive »] (thèse de doctorat en informatique à l'université d'Édimbourg en Écosse), Www.ed.ac.uk, 1971, 230 p. (lire en ligne [PDF]). .
2. (en) Shapiro, Ehud Y. Inductive inference of theories from facts[PDF], 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. (en) Shapiro, Ehud Y. (1983). Algorithmic program debugging. Cambridge, Mass: MIT Press. (ISBN 0-262-19218-7)
4. (en) 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. (en) 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. (en) S.H. Muggleton, « Inductive logic programming », New Generation Computing, vol. 8, n^o 4,‎ 1991, p. 295–318 (DOI 10.1007/BF03037089)
7. (en) S.H. Muggleton et W. Buntine, « Machine invention of first-order predicate by inverting resolution », Proceedings of the 5th International Conference on Machine Learning,‎ 1988
8. (en) S.H. Muggleton, « Inverting entailment and Progol », New Generation Computing, vol. 13,‎ 1995, p. 245–286 (DOI 10.1007/bf03037227)

Articles liés

• Unification
• Anti-unification

• Portail de l’informatique