Intelligence Artificielle AI - Prolog : Chapitre1 Prolog introduction
Télécharger PDFIntroduction à l’Intelligence Artificielle
Mélanie COURTINE
Plan
- Logique des propositions et des prédicats
- Langage Prolog
- Histoire de l’Intelligence Artificielle
- Des mythes à la réalité
- Résolution de problèmes : exploration intelligente des solutions
- Modélisation sous forme de graphes d’états
- Recherche de solutions optimales
- Définition d’heuristiques
- Systèmes formels, experts et à base de connaissances
- Représentation des connaissances
- De la logique aux langages complexes
- Extraction des connaissances
- Induction d’arbres de décision et de règles
- Classification automatique
- Fouille de données
Évaluation : un examen et un travail en Prolog
Un travail pratique à rendre en utilisant le langage Prolog.
Prolog : une introduction
Styles de programmation
Programmation impérative (et programmation objet)
Ce style repose sur l’exécution de blocs d’instructions séquentiellement. Il offre un contrôle total du flux d’exécution.
Exemples : Pascal, C.
Programmation objet
Basée sur l’utilisation d’entités-messages.
Exemples : Smalltalk, C++, Java.
Programmation fonctionnelle
Tout est fonction. La syntaxe est épurée et repose sur une base mathématique solide (λ-calcul). Le contrôle est délégué à l’interpréteur, avec une utilisation intensive de la récursivité.
Exemples : LISP, Scheme.
Programmation logique
Tout est logique. La syntaxe est simple et épurée, avec une base théorique : le calcul des prédicats. La logique sert de cadre formel pour formaliser, représenter et raisonner.
Ce style donne encore plus de contrôle à la machine et repose sur la récurrence et le non-déterminisme.
Exemple : Prolog.
Histoire de la programmation logique
- 1930 : Calcul des prédicats (J. Herbrand)
- 1945 : Principe de résolution (J.A. Robinson)
- 1969 : Kowalski montre que la logique peut être utilisée comme langage de programmation
- 1972 : Premier interprète Prolog (A. Colmerauer et P. Roussel)
- 1977 : Premier compilateur Prolog (D.H.D. Warren)
- 1980 : Prolog devient le langage de l’Intelligence Artificielle
- 1990 : Prolog s’étend à la programmation par contraintes
Domaines d’application
- Logique mathématique
- Traitement des langages naturels
- Conception assistée par ordinateur
- Résolution symbolique d’équations
- Analyse de structures biochimiques
- Planification et allocation de ressources
- Systèmes experts
- Aide à la décision
- Aide au dépannage
La logique
Syntaxe et sémantique
En logique, les formules possèdent une syntaxe et une sémantique.
- La syntaxe définit la structure des formules, c’est-à-dire la manière dont elles doivent être écrites pour former le langage logique.
- La sémantique associe un sens aux formules, souvent une valeur de vérité (vrai ou faux).
La logique permet de représenter des connaissances et de raisonner sur ces connaissances.
Logique des propositions
Comment écrire les formules ?
Le calcul des propositions manipule des formules composées d’atomes (ou variables propositionnelles) et de connecteurs booléens.
- Les atomes sont représentés par des lettres minuscules.
- Exemples de formules élémentaires :
- p = il fait beau
- q = Strasbourg est en France
- r = les poules ont des dents
Définition d’un atome
Un atome est un énoncé élémentaire qui ne peut pas être décomposé.
Connecteurs logiques
Les connecteurs booléens utilisés en logique des propositions sont :
- ¬ (non) : négation
- ∧ (et) : conjonction
- ∨ (ou) : disjonction
- → (implique ou si...alors...) : implication
- ↔ (équivalent ou si et seulement si) : équivalence
Définition des propositions
Les propositions (ou formules propositionnelles) sont définies comme suit :
- Un atome est une proposition.
- Si A est une proposition, alors (¬A) est une proposition.
- Si A et B sont des propositions, alors (A ∧ B), (A ∨ B), (A → B) et (A ↔ B) sont des propositions.
- La proposition vide est notée ☐ et définie par (a ∧ ¬a).
- Par convention, les propositions sont notées avec des majuscules ou des lettres grecques.
- Ordre de dominance des connecteurs : ↔, →, ∧, ∨, ¬.
Limites du calcul propositionnel
Le calcul propositionnel ne permet pas d’exprimer des nuances ou de gérer des informations manquantes, contrairement aux raisonnements humains.
Exemple :
- Les chandelles sont faites pour éclairer.
- Quelques chandelles éclairent très mal.
- Quelques objets qui sont faits pour éclairer le font très mal.
Logique des prédicats
Modélisation
La logique des prédicats permet de formaliser des énoncés plus complexes.
Exemple :
- ∃x (éclaireMal(x) ∧ chandelle(x)) : quelques chandelles éclairent très mal.
- ∀x (chandelle(x) → éclaire(x)) : les chandelles sont faites pour éclairer.
- ∃x (éclaireMal(x) ∧ éclaire(x)) : quelques objets qui sont faits pour éclairer le font très mal.
Syntaxe
La logique des prédicats du premier ordre (LP1) utilise :
- Des variables (x, y, ...)
- Des constantes (a, b, ...)
- Des fonctions (f, g, ...)
- Des relations (prédicats) (R, S, éclaire, ...)
- Des connecteurs logiques (¬, ∧, ∨, → et ↔)
- Des quantificateurs (∀ et ∃)
Formules
Les formules en logique des prédicats sont construites comme suit :
- Un atome est une formule.
- Si F et G sont des formules et x une variable, alors les expressions suivantes sont des formules :
- ¬(F) : négation
- (F) ∧ (G) et (F) ∨ (G) : conjonction et disjonction
- (F) → (G) et (F) ↔ (G) : implication et équivalence
- ∀x (F) et ∃x (G) : quantificateurs universel et existentiel
Inconvénients de la LP1
La logique du premier ordre ne permet pas d’exprimer des nuances ou de gérer des informations manquantes, comme le font les humains.
Pour pallier ces limites, d’autres logiques sont utilisées : logiques multivaluées, modales, non monotones, temporelles, floues, etc.
Les fondamentaux de Prolog
Environnements Prolog
Les environnements Prolog sont des systèmes interactifs qui incluent :
- Un environnement de travail (ex : Quintus Prolog, BIM Prolog, SWI-Prolog, Turbo-Prolog)
- Une session de travail
- Une fenêtre de l’environnement Prolog
- Une fenêtre d’édition (ex : Xemacs)
- Une fenêtre de shell
SWI-Prolog
SWI-Prolog est un environnement de programmation logique.
Les clauses de base
Voici quelques commandes de base pour naviguer dans un environnement Prolog :
- Afficher le répertoire de travail et ses fichiers : pwd.
- Changer de répertoire de travail : chdir(‘~/prolog/tp1’).
- Charger un fichier : consult(menu). ou consult(‘menu.pl’).
- Affichage des clauses : listing. ou listing(plat).
- Quitter : halt.
Communication homme-machine
Exemple de communication :
- Tout psychiatre est une personne.
- Chaque personne qu’il analyse est malade.
- Jacques est un psychiatre à Paris.
Questions posées au système :
- Est-ce que Jacques est une personne ?
- Où est Jacques ?
- Est-ce que Jacques est malade ?
Réponses du système :
- Oui.
- À Paris.
- Je ne sais pas.
Prolog : langage déclaratif
Prolog est un langage de programmation déclaratif, ce qui signifie qu’il permet de représenter et manipuler des connaissances sur un domaine particulier.
- Les faits décrivent des relations ou des propriétés d’objets spécifiques.
- Les règles expriment des relations entre catégories d’objets, permettant de déduire de nouveaux faits.
- Les questions permettent de vérifier si un fait est établi ou peut l’être.
Programme Prolog
Un programme Prolog est composé de trois types de connaissances :
- Les faits : P(...). où P est un prédicat.
- Les clauses de Horn réduites à un littéral positif : règles de la forme P(...) :- Q(...), ..., R(...).
- Les questions : S(...), ..., T(...).
Les faits
Les faits sont des affirmations qui décrivent des relations ou des propriétés.
Forme : predicat(arg1, arg2, ..., argn).
Un prédicat est identifié par son nom et son arité (nombre d’arguments).
Exemples :
- homme(sartre).
- mange(vache, herbe).
- eleve(albert, 1982, maths, 8).
Les règles
Les règles permettent d’exprimer des conjonctions de buts.
Forme : tete :- C1, C2, ..., Cn.
Si C1, C2, ..., Cn sont vraies, alors la tête est vraie.
Exemples :
- Tous les herbivores mangent de l’herbe.
- Tous les animaux qui volent sont des oiseaux.
Les termes
Les termes en Prolog incluent :
- Les constantes : chaînes de caractères commençant par une majuscule ou des symboles comme +, -, *, /, \.
- Les nombres : valeurs numériques.
- Les atomes :
- Atomes standards : chaînes de caractères commençant par une minuscule.
- Atomes protégés : chaînes de caractères entre ’ ’.
- Atomes symboliques : symboles comme +, -, *, /, \.
- Les variables : chaînes de caractères commençant par une majuscule ou _.
- La variable indéterminée (singleton) : _.
- Les structures/relations/prédicats d’arité n : nom(arg1, arg2, ..., argn).
Exemple de programme Prolog : un menu
Voici un exemple de programme Prolog pour modéliser un menu simple :
/* La carte est donnée ("clauses faits") */
/* les entrées */
entree(crudites).
entree(terrine).
entree(melon).
/* les viandes (avec légumes associés) */
viande(steack).
viande(poulet).
viande(gigot).
/* les poissons (avec légumes associés) */
poisson(bar).
poisson(saumon).
/* les desserts */
dessert(sorbet).
dessert(creme).
dessert(tarte).
/* Composition d’un menu simple (sans boisson) : une entrée, un plat, un dessert */
menu_simple(E, P, D) :- entree(E), plat(P), dessert(D).
/* le plat (de résistance) : viande OU poisson */
plat(P) :- viande(P).
plat(P) :- poisson(P).
Les questions et les requêtes
Une question en Prolog a la forme d’une formule atomique pouvant contenir des variables.
- Les questions fermées : sans variables.
- Les questions ouvertes : avec variables.
- Le point-virgule (;) permet d’obtenir la solution suivante.
La stratégie de résolution
Exécution et résolution
Résoudre un problème en Prolog revient à poser une question et à demander une preuve d’une expression. Le moteur de Prolog trouve toutes les valeurs des variables qui mènent à une contradiction.
La règle de résolution utilise la technique de backtracking (recherche en profondeur avec retour arrière).
Avantages et inconvénients
Les avantages de Prolog sont :
- Souplesse et pouvoir d’expression du langage.
- Rapidité de développement d’un système.
- Simplification de la maintenance.
Les inconvénients sont :
- Bonne maîtrise des stratégies de résolution de Prolog.
- Expertise dans l’ordre des faits et règles à introduire dans le système.
Exemple : grand-père
Programme :
pere(charlie, david). pere(henri, charlie). grand_pere(X,Y) :- pere(X,Z), pere(Z,Y).
Question : grand_pere(X,Y).
Réponse : X=henri, Y=david.
Prolog n’est pas équivalent à la logique
L’ordre des clauses a de l’importance en Prolog.
Exemple :
ancetre(X,X). ancetre(X,Y) :- pere(X,Z), ancetre(Z,Y).
Recommandation : commencer toujours par les prédicats les plus simples à résoudre.
Exemple : carnivores et herbivores
Formalisation :
- La chèvre est un animal herbivore.
- Le loup est un animal carnivore.
- Un animal cruel est carnivore.
- Un animal carnivore mange de la viande.
- Un animal herbivore mange de l’herbe.
- Un animal carnivore mange des animaux herbivores.
- Les herbivores et les carnivores boivent de l’eau.
- Un animal consomme ce qu’il boit ou ce qu’il mange.
Question : Y a-t-il un animal cruel et que consomme-t-il ?
Modèle d’exécution
SWI-Prolog propose des outils pour activer ou désactiver la traçabilité des exécutions :
- Activation : trace.
- Désactivation : notrace.
Paquets de clauses : call, fail, redo, exit.