Logique des prédicats
Introduction
Avec la logique des prédicats (ou d'ordre 1) - FOL - on passe un cran au dessus en terme d'expressivité des phrases, puisqu'il est possible d'exprimer, entre autre, la notion de variabilité dans une proposition, qui se nomme alors un prédicat (smullyan1995first). Incidemment, elle devient plus difficilement satisfiable.
Avec cette logique, on peut totalement modéliser des systèmes complexes, capables d'exploiter une base de connaissances et de faits pour raisonner efficacement et produire de l'information.
Formellement, un prédicat se définit comme :
une expression linguistique qui peut être reliée à un ou plusieurs éléments du domaine pour former une phrase [source].
Syntaxe
Alphabet
Un ensemble de termes variables, toujours infini mais dénombrables :
un ensemble de termes constants, qui peut être soit , soit
Un ensemble de prédicats (ou relations) :
Un un ensemble de connecteurs : , , ,
Deux quantificateurs : (pour tous) et (il existe)
L'ordre des quantificateurs est important !
!! Jamais vrai
Arité
, possède une arité (i.e. le nombre de variables et de constantes qui interviennent).
Par exemple :
le prédicat
pere
est dit dyadique puisque pour être le père de quelqu’un, deux entités sont concernés. On note celale prédicat
grand
est dit monoadique puisqu'un seul individu est concerné. Il s'exprime comme
Formule
Une formule du calcul des prédicats (i.e. mot) se définit par induction.
Soit un poids associé à chaque prédicat . est une formule ssi est de poids .
Exemple :
pere(x,y)
est un mot ;
grand(x,y)
n'est pas un mot puisqu'il est monadique.
De plus, une formule qui ne possède que des variables liées est appelée un enoncé.
Lorsqu'une variable est associée à un quantificateur (e.g. ), on dit qu'elle est liée ;
Inversement, lorsqu'une variable n'est pas associée à un quantificateur, on dit qu'elle est libre.
L'exemple ci-après illustre le célèbre syllogisme de Socrate, que l'on ne peut pas exprimer en ZOL.
Modèle
Un modèle du langage permet son interprétation en y décrivant les valeurs prises par les éléments du premier ordre (variables, constantes...) et les formules associées. Chaque énoncé se voit attribué une valeur de vérité. Un modèle donne donc un sens aux symboles du langage : l’on parle alors de sémantique.
Un modèle donne une valeur de vérité (vrai ou faux) à toute formule close du langage. Les conditions de vérité sont définis par induction structurelle sur les formules. Par exemple, dans le modèle ci-contre :
FAUX (le "pellet" ne mange persone)
VRAI (il y a toujours quelque chose qui est mangé)
Raisonnement
Règles
Dans la logique des prédicats, il est possible de dynamiquement augmenter la base de faits disponibles en s'appuyant sur des raisonnements adossés à des règles.
Exemples :
Aussi, si on sait que grandmere(Anna,Bob)
(i.e. que Anna est la grand mère de Bob), on peut en déduire que Anna est une femme grâce à femme(y)
, sans même l'avoir spécifié dans la base de fait. Autrement dit, on a inféré cette connaissance !
Cette information peut venir enrichir la base de faits, et ensuite être utilisée dans des raisonnements a postériori.
Quelques pièges
Quand ont définit des règles/formules/énoncés il faut être prudent avec les implications qu'elles peuvent avoir. Autrement, l'on cours à des incohérences dans les faits.
Disons que ... et les pingouins dans cette histoire ?
Parmi les pièges les plus courants :
Créer des chemins de règles qui amène à être vrai quoi qu'il arrive (i.e. x est "tout") ;
Règles trop génériques, ou à l'inverse trop exclusives ;
Des règles insolubles nécessitant de d'être à la fois vrai et faux, afin que le prédicat soit vrai.
Inférence
On l'a vu dans la section précédente, il est possible de créer de l'information à partir de la base de faits et de règles. Ce mécanisme, communément appelé inférence, repose sur différents ressorts d'interprétation des connaissances à disposition du moteur d'inférence (induction, déduction, chaînage...).
Le chaînage est un procédé puissant permettant d'exploiter au maximum les énoncés du modèle. À partir d'un ensemble d'énoncés initiaux et de faits, le moteur va faire croître sa base de faits en fonction des résultats, et recommencer l'application des règles jusqu'à ce qu'il n'y ait plus de changement entre deux itérations.
Exemple 1 (chaînage avant) :
Soit les règles suivantes :
Et le fait suivants :
grandmere(Anna,Bob)
homme(Bob)
Avec un chaînage avant, on en déduit que Anna est une femme (
femme(y)
) puis que Anna est probablement plus petite que Bob.
Exemple 2 (chaînage mixte):
De telles inférences peuvent rapidement devenir utiles en situation réelle. Admettons que vous avez, sur une chaîne de production, cinq machines différentes (i.e. qui font des actions différentes) :
pli(b,c)
cut(c,b)
transform(a,b)
livrable(c,b,d)
livrable(e,d)
Admettons aussi que votre produit final est
d
, et que, pour une raison ou pour une autre, une pénurie de ressources se manifeste et ne vous laisse plus quea
comme matière première. En utilisant un chaînage mixte, vous savez que pour qued
soit vrai, il vous faut . Avec un chaînage avant, vous savez qu'aveca
vous pouvez produireb
, et avecb
produirec
. Le process de production final déduit est alors :transform pli livrable
Conclusion
La FOL est utilisé dans des algorithmes d'intelligence artificielle, pour résoudre des problèmes d'optimisation, de jeux...
Elle donne aussi un cadre intéressant aux mécanismes d'inférences et de déduction pour produire de l'informations supplémentaires et du DM. C'est par exemple le cas avec les chaînages, comme on l'a vu juste avant.
C'est sur ces principes que la notion de systèmes experts est apparues (~1963). Il s'agit d'une implémentation informatique capable de simuler les mécanismes cognitifs d'un expert, dans un domaine particulier, pour répondre à des questions.
Il y a des avantages et des désavantages à ces systèmes. Une petite liste
Pros
Cons
Explicabilité des résultats
Recueil des connaissances complexe et fastidieux
Complet
Semi-décidable
Maintenance et évolution
Un modèle volumineux peut devenir complexe à maintenir
Humainement compréhensible
Dernière mise à jour
Cet article vous a-t-il été utile ?