Lab 2 : Moteur d’inférence à chaînage avant sans variables

Durée estimée : < 2 heures.

Objectifs de la série

Comment fonctionne un moteur d’inférence à chaînage avant sans variables ?

Exercice 1: Un moteur d’inférence à chaînage avant simple

Cette série veut introduire la notion d’inférence à chaînage avant sans variables. Cette technique simple est à la base de la plupart des systèmes experts utilisés à l’heure actuelle. La réalisation d’un tel système se fera en plusieurs étapes, cette première se limitant à des règles sans variables. La semaine prochaine, dans la serie 3, vous allez implementer un moteur de recherche avec variables.

L’idée de base d’un moteur d’inférence à chaînage avant est de déduire tout ce qu’il est possible à partir d’un ensemble de faits de départ et d’un ensemble de règles.

Les règles que nous considérerons seront des clauses de Horn. Une telle règle est composée de deux parties:

  • Un ensemble de conditions qui doivent toutes êtres satisfaites pour que la règle se déclenche.
  • Une seule conséquence, i.e., un nouveau fait, qui devra être inséré dans la base des faits.

A chaque fois qu’un nouveau fait est déduit, l’ensemble complet des règles doit être appliqué à nouveau à la base des faits : le nouveaufait peut permettre le déclenchement d’une règle qui avait déjà été essayée sans succès.

Le processus d’inférence se termine lorsque plus aucun nouveau fait ne peut être déduit.

Le fichier chainageAvantSansVariablesTemplate.py fournit le squelette du programme que l’on va développer. Dans le même répertoire se trouve le fichier impots.py qui contient des règles et des faits vous permettant de tester votre moteur d’inférence à chaînage avant sans variables. Commencez par copier chez vous ces deux fichiers.

Définition de faits et de règles

Les faits de départ seront stockés dans la liste faitsDepart. Tous les faits qui sont connus comme étant vrais (la base des faits) seront stockés dans la liste baseFaits. Les regles seront stockés dans la liste baseRegles. Ces trois listes seront initialement vides (i.e.: fixées à []).

Un fait sera un atome (pas-d-enfants par exemple) tandis qu’une règle sera une liste [[<condition1>, ..., <conditionn>], <consequence>].

Commencez par définir deux fonctions ajouteFait et ajouteRegle vous permettant d’ajouter des faits et des règles à listes des faits et des regles. Ajoutez ces fonctions dans chainageAvantSansVariablesTemplate.py.

Syntaxe: ajouteFait accepte deux paramètres, le fait (un atome) et la liste des faits. ajouteRegle a trois paramètres : la liste des conditions de la règle, la conclusion (un atome) de la règle, et la liste des regles.

Exemples: En admettant que faitsDepart et baseRegles soient vides, on aura:

ajouteFait('enfants', faitsDepart)
        # ajoute le fait enfants à faitsDepart.
        faitsDepart -> ['enfants']
ajouteFait('loyer', faitsDepart)
        # ajoute le fait loyer à faitsDepart.
        faitsDepart -> ['enfants','loyer']
ajouteRegle( ['bas-salaire', 'loyer'], 'reduc-loyer-200', baseRegles)
        # ajoute la règle  bas-salaire AND loyer => reduc-loyer-200 à baseRegles.
        baseRegles -> [ [['bas-salaire', 'loyer'], 'reduc-loyer-200'] ]

Définissez ensuite une fonction initDBs qui permet de réinitialiser les faits de départ, faitsDepart, la base des faits, baseFaits, et la base de regles, baseRegles, à [].

Grâce à ces trois fonctions, il est maintenant possible d’écrire des fichiers de données (règles et faits de départ) que l’on peut directement évaluer dans l’interpréteur Python par la commande exec(open("monFichier.py").read()), ou directement depuis le terminal en exécutant la commande python monFichier.py

Accès à la conséquence et aux conditions d’une règle

Ecrivez maintenant les deux fonctions suivantes:

  • conditionsRegle: retourne la liste des conditions de la règle passée en paramètre.
  • consequenceRegle: retourne la conséquence de la règle passée en paramètre.

Verification de la présence d’un fait dans une règle

Lors du chaînage avant, il va falloir vérifier si un fait q fait partie des conditions d’une règle (pas 10).

Ecrivez maintenant la fonction satisfaitUneCondition qui prend deux arguments en paramètre: un fait et une règle, et retourne True si un fait passé en paramètre fait partie des conditions de la règle, sinon elle retourne False.

Astuce

Utilisez l’opérateur in afin de vérifier si un élément est présent dans une liste.

Vérification qu’une règle peut être déclanchée

Définissez maintenant la fonction satisfaitConditions, qui prend deux paramètres: une règle et une liste des faits. Elle retournera:

  • True si toutes les conditions de la règle peuvent être satisfaites par les faits de la liste des faits, càd, (dans le cas présent) toutes les conditions sont présentes dans la liste des faits.
  • False sinon.

Astuce

Utilisez la fonction issubset afin de vérifier si un set est contenu dans un autre.

Chaînage avant

Vous êtes maintenant prêts pour la définition de la fonction principale: chainageAvantSimple. Elle prend en entrée les faits de départ, la base des faits et la base de règles, et affiche à l’écran tous les faits qui sont ajoutés à la base des faits.

Comme nous n’avons pas de variables dans cette première version, aucun filtrage n’est nécessaire; l’algorithme de chaînage avant est donc simple:

chainageAvantSimple(faitsDepart, faits, regles)
1. Q <- faitsDepart
2. WHILE Q n'est pas vide DO
3.     q <- premier(Q), Q <- reste(Q)
4.     IF q n'est pas dans faits THEN
5.         ajouter q à faits
6.         imprimer q
7.         FOR EACH règle r de regles DO
8.             IF q est une condition de r
9.               AND les conditions de r sont satisfaites par faits THEN
10.                 ajouter la conclusion de r à la queue de Q
11.             END IF
12.         END FOR
13.     END IF
14. END WHILE
END chainageAvantSimple

Les faits de départ et inférés sont gérés par la file d’attente Q (qui contient au début les faits de départ). S’il n’y est pas déjà, chaque fait de Q va être ajouté dans la base des faits et toutes les règles vont être essayées pour tenter d’inférer de nouveaux faits, qui seront ajoutés en queue de Q. Le processus s’arrête dès que Q est vide.

Note

La fonction copy.deepcopy(y) permet de faire une copie en profondeur de la liste y, car a=b signifie que a référence b. Pour plus d’informations, consultez ce lien.

Test du programme

Le fichier impots.py contient les règles et les faits pour le calcul très simple du montant de la réduction d’impôt. Après avoir écrit votre programme, chargez les données et testez votre programme en exécutant python impots.py dans le terminal, ou avec la commande exec(open("impots.py").read()) dans l’interpréteur python.

Vérifiez que le fait reduc-300 est déduit.

Modifiez la base des faits pour qu’elle contienne maintenant ['pas-d-enfants', 'pas-loyer', 'haut-salaire', 'long-trajet'].

Quelle devrait alors être la réduction d’impôts ? Vérifiez avec le programme.