Programmation logique inductive - Inductive logic programming

La programmation logique inductive ( ILP ) est un sous-domaine de l'intelligence artificielle symbolique qui utilise la programmation logique comme représentation uniforme d'exemples, de connaissances de base et d'hypothèses. Étant donné un codage des connaissances de base connues et un ensemble d'exemples représentés comme une base de données logique de faits, un système ILP dérivera un programme logique hypothétique qui implique tous les exemples positifs et aucun des exemples négatifs.

• Schéma : exemples positifs + exemples négatifs + connaissances de base ⇒ hypothèse .

La programmation logique inductive est particulièrement utile en bioinformatique et en traitement du langage naturel . Gordon Plotkin et Ehud Shapiro ont jeté les bases théoriques initiales de l'apprentissage automatique inductif dans un cadre logique. Shapiro a construit sa première implémentation (Model Inference System) en 1981 : un programme Prolog qui inférait par induction des programmes logiques à partir d'exemples positifs et négatifs. Le terme programmation logique inductive a été introduit pour la première fois dans un article de Stephen Muggleton en 1991. Muggleton a également fondé la conférence internationale annuelle sur la programmation logique inductive, a présenté les idées théoriques de l'invention de prédicat, de la résolution inverse et de l'implication inverse. Muggleton a d'abord mis en œuvre l'implication inverse dans le système PROGOL . Le terme « inductif » renvoie ici à une induction philosophique (c'est-à-dire suggérer une théorie pour expliquer les faits observés) plutôt que mathématique (c'est-à-dire prouver une propriété pour tous les membres d'un ensemble bien ordonné).

Définition formelle

Les connaissances de base sont données en tant que théorie logique B , généralement sous la forme de clauses de Horn utilisées dans la programmation logique . Les exemples positifs et négatifs sont donnés sous forme de conjonction et de littéraux au sol non niés et niés , respectivement. Une hypothèse correcte h est une proposition logique satisfaisant aux exigences suivantes. ${\style d'affichage E^{+}}$${\style d'affichage E^{-}}$

${\displaystyle {\begin{array}{llll}{\text{Nécessité :}}&B&\not \models &E^{+}\\{\text{Suffisance :}}&B\land h&\color {blue}{ \models }&E^{+}\\{\text{Faible cohérence :}}&B\land h&\not \models &{\textit {false}}\\{\text{Forte cohérence :}}&B\land h \land E^{-}&\not \models &{\textit {false}}\end{array}}}$

La " nécessité " n'impose pas de restriction sur h , mais interdit toute génération d'hypothèse tant que les faits positifs sont explicables sans elle. La « suffisance » requiert toute hypothèse h générée pour expliquer tous les exemples positifs . La " cohérence faible " interdit la génération de toute hypothèse h qui contredit les connaissances de base B . La « cohérence forte » interdit également la génération de toute hypothèse h qui serait incohérente avec les exemples négatifs , compte tenu des connaissances de base B ; il implique « Faible cohérence » ; si aucun exemple négatif n'est donné, les deux exigences coïncident. Džeroski n'exige que la « Suffisance » (appelée ici « Complétude ») et la « Consistance forte ». ${\style d'affichage E^{+}}$${\style d'affichage E^{-}}$

Exemple

Liens familiaux présumés dans la section « Exemple »

L'exemple bien connu suivant sur l'apprentissage des définitions des relations familiales utilise les abréviations

par : parent , fem : femelle , dau : fille , g : George , h : Helen , m : Mary , t : Tom , n : Nancy , et e : Eve .

Cela part des connaissances de base (cf. photo)

${\displaystyle {\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)}$,

les exemples positifs

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

et la proposition triviale vraie pour désigner l'absence d'exemples négatifs.

L' approche de la « généralisation la moins générale relative (rlgg) » de Plotkin à la programmation logique inductive sera utilisée pour obtenir une suggestion sur la façon de définir formellement la relation fille dau .

Cette approche utilise les étapes suivantes.

• Relativisez chaque exemple littéral positif avec les connaissances de base complètes :

  ${\displaystyle {\begin{aligned}{\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{aligned}}}$,

• Convertir en clause forme normale :

  ${\displaystyle {\begin{aligned}{\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{aligned}}}$,

• Anti-unifier chaque paire de littéraux compatible :
  • ${\displaystyle {\textit {dau}}(x_{me},x_{ht})}$de et ,${\displaystyle {\textit {dau}}(m,h)}$${\displaystyle {\textit {dau}}(e,t)}$
  • ${\displaystyle \lnot {\textit {par}}(x_{ht},x_{me})}$de et ,${\displaystyle \lnot {\textit {par}}(h,m)}$${\displaystyle \lnot {\textit {par}}(t,e)}$
  • ${\displaystyle \lnot {\textit {fem}}(x_{me})}$de et ,${\displaystyle \lnot {\textit {fem}}(m)}$${\displaystyle \lnot {\textit {fem}}(e)}$
  • ${\displaystyle \lnot {\textit {par}}(g,m)}$de et , similaire pour tous les autres littéraux de connaissances de base${\displaystyle \lnot {\textit {par}}(g,m)}$${\displaystyle \lnot {\textit {par}}(g,m)}$
  • ${\displaystyle \lnot {\textit {par}}(x_{gt},x_{me})}$de et , et bien d'autres littéraux niés${\displaystyle \lnot {\textit {par}}(g,m)}$${\displaystyle \lnot {\textit {par}}(t,e)}$
• Supprimez tous les littéraux niés contenant des variables qui n'apparaissent pas dans un littéral positif :
  • après avoir supprimé tous les littéraux niés contenant d'autres variables que , il ne reste plus que tous les littéraux de base de la connaissance de base${\displaystyle x_{me},x_{ht}}$${\displaystyle {\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{moi})}$
• Convertissez les clauses en forme Horn :
  • ${\displaystyle {\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}} (x_{moi})\land ({\text{tous les faits de connaissances de base}})}$

La clause de Horn résultante est l'hypothèse h obtenue par l'approche rlgg. Ignorant les faits de connaissance de base, la clause se lit de manière informelle " est appelée une fille de si est le parent de et est une femme ", qui est une définition communément acceptée. ${\displaystyle x_{moi}}$${\style d'affichage x_{ht}}$${\style d'affichage x_{ht}}$${\displaystyle x_{moi}}$${\displaystyle x_{moi}}$

Concernant les exigences ci - dessus , " Nécessité " a été satisfaite car le prédicat dau n'apparaît pas dans la connaissance de base, ce qui ne peut donc impliquer aucune propriété contenant ce prédicat, comme le sont les exemples positifs. « Suffisance » est satisfaite par l'hypothèse calculée h , car elle, avec la connaissance de base, implique le premier exemple positif , et de même h et à partir de la connaissance de base implique le deuxième exemple positif . La « cohérence faible » est satisfaite par h , puisque h tient dans la structure (finie) de Herbrand décrite par la connaissance de base ; similaire pour « Consistance forte ». ${\displaystyle {\textit {par}}(h,m)\land {\textit {fem}}(m)}$${\displaystyle {\textit {dau}}(m,h)}$${\displaystyle {\textit {par}}(t,e)\land {\textit {fem}}(e)}$${\displaystyle {\textit {dau}}(e,t)}$

La définition commune de la relation grand-mère, à savoir. , ne peut pas être appris en utilisant l'approche ci-dessus, car la variable y apparaît uniquement dans le corps de la clause ; les littéraux correspondants auraient été supprimés à la 4e étape de l'approche. Pour surmonter ce défaut, cette étape doit être modifiée de manière à pouvoir être paramétrée avec différentes heuristiques de post-sélection littérales . Historiquement, l'implémentation de GOLEM est basée sur l'approche rlgg. ${\displaystyle {\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}} (y,z)}$

Système de programmation logique inductive

Le système de programmation logique inductive est un programme qui prend en entrée des théories logiques et génère une hypothèse correcte H par rapport aux théories Un algorithme d'un système ILP se compose de deux parties : la recherche d'hypothèses et la sélection d'hypothèses. Tout d'abord, une hypothèse est recherchée avec une procédure de programmation logique inductive, puis un sous-ensemble des hypothèses trouvées (dans la plupart des systèmes une hypothèse) est choisi par un algorithme de sélection. Un algorithme de sélection note chacune des hypothèses trouvées et renvoie celles avec le score le plus élevé. Un exemple de fonction de score comprend une longueur de compression minimale où une hypothèse avec une complexité de Kolmogorov la plus faible a le score le plus élevé et est renvoyée. Un système ILP est complet ssi pour toutes les théories logiques d'entrée, toute hypothèse correcte H par rapport à ces théories d'entrée peut être trouvée avec sa procédure de recherche d'hypothèse. ${\style d'affichage B,E^{+},E^{-}}$${\style d'affichage B,E^{+},E^{-}}$${\style d'affichage B,E^{+},E^{-}}$

Recherche d'hypothèse

Les systèmes ILP modernes comme Progol, Hail et Imparo trouvent une hypothèse H en utilisant le principe de l'implication inverse pour les théories B , E , H : . Ils construisent d'abord une théorie intermédiaire F appelée théorie des ponts satisfaisant les conditions et . Puis comme , ils généralisent la négation de la théorie du pont F avec l'anti-implication. Cependant, le fonctionnement de l'anti-implication étant fortement non déterministe, est plus coûteux en calcul. Par conséquent, une recherche d'hypothèse alternative peut être menée en utilisant à la place l'opération de la subsomption inverse (anti-subsomption) qui est moins non déterministe que l'anti-implication. ${\displaystyle B\land H\models E\iff B\land \neg E\models \neg H}$${\displaystyle B\land \neg E\models F}$${\displaystyle F\modèles \neg H}$${\displaystyle H\models \neg F}$

Des questions sur l'exhaustivité d'une procédure de recherche d'hypothèse d'un système spécifique ILP se posent. Par exemple, la procédure de recherche d'hypothèse de Progol basée sur la règle d'inférence d'implication inverse n'est pas complète par l'exemple de Yamamoto . D'autre part, Imparo est complet à la fois par la procédure anti-implication et sa procédure de subsomption inverse étendue.

Implémentations

• 1BC et 1BC2 : classificateurs bayésiens naïfs du premier ordre :
• ACE (un moteur combiné)
• Aleph
• Atome
• Claudien
• DL-Apprenant
• DMax
• FastLAS (apprentissage rapide à partir d'ensembles de réponses)
• FOIL (Apprenant inductif du premier ordre)
• Golem
• ILASP (Programmes d'apprentissage inductif des ensembles de réponses)
• Imparo
• Inthelex (apprenant de théorie incrémentale à partir d'exemples)
• Chaux
• Métagol
• Mio
• MIS (Model Inference System) par Ehud Shapiro
• PROGOL
• RSD
• Warmr (maintenant inclus dans ACE)
• ProGolem

Voir également

• Raisonnement de bon sens
• Analyse de concept formelle
• Raisonnement inductif
• Programmation inductive
• Probabilité inductive
• Apprentissage statistique relationnel
• Apprentissage de l'espace des versions

Les références

Lectures complémentaires