Résumé: Les réseaux de neurones artificiels sont toujours considérés comme des boites noires, qui permettent après un apprentissage à partir d'une base d'exemples incomplète, de classifier de nouveaux exemples, mais sans donner aucune explication sur les résultats. Leurs connaissances sont codées de manière interne par les poids synaptiques, et ne sont pas donc exprimées de manière compréhensible. Les algorithmes génétiques très performants dans les problèmes d'exploration semblent être en mesure de rechercher dans l'espace des ensembles de règles, celui qui représentera le mieux les connaissances d'un RNA. En revanche, ils sont inefficaces lorsqu'il s'agit de trouver la valeur exacte de l'optimum dans cet espace or, c'est précisément ce que les algorithmes exacts d'optimisation réalisent le mieux. Nous présentons dans cet article une nouvelle approche d'extraction de règles à partir d'un réseau de neurones permettant de combiner les deux méthodes métaheuristiques et exactes au sein d'un même système.
La figure1 présente l’architecture de notre système MC-RULEGEN, il est décomposé en 04 modules: le module perceptron multicouches, le module génétique, le module simplification de règles, et enfin le module system à base de règles. 2.1. Module Apprentissage du réseau de neurones
Règles Initiales
System à base de règles
Règles finales
Les connaissances du réseau de neurones sont difficilement interprétables par un être humain. Pour remédier à cela, il convient d’expliciter ces connaissances, c’est-à-dire les traduire sous une forme intelligible, une approche pédagogique basé sur les algorithmes génétiques est utilisée. La règle extraite doit avoir la forme suivante
if [not]x1 and [not]x2 . . . then C [.] est facultatif
Les règles extraites doivent être précises et compréhensibles [4], [6]. La précision (2) mesure la proportion des exemples correctement classés par la règle parmi tous les exemples d'apprentissage précision = nombre des exemples correcteme nt classés nombre total des exemples
nombre de règles Generalisa tion = 1 - nombre des exemples (2) (3)
La fidélité se calcule de la manière suivante: chaque individu est passé dans le réseau de neurone pour classification, le pourcentage des bonnes réponses est la valeur de la fidélité associé à l'individu. La compréhensibilité calcule le nombre de règles ainsi que le nombre de prémisses dans chaque règle. Enfin la généralisation est définit par (3) Algorithme génétique pour l'extraction de règles
Les algorithmes génétiques (AG) sont des algorithmes d'optimisation s'appuyant sur des techniques dérivées de la génétique et de l'évolution naturelle. ils utilisent la selection, le croisement et la mutation.
Générer aléatoirement une population initiale P(0), Calculer la fonction fitness fi(m) pour chaque individu m de la population P(t), Définir des probabilités de selection pour chaque individu m dans P(t), Générer la nouvelle population P(t+1) en appliquant les opérateurs génétiques de croisement et de mutation, Repéter l'étape 2 jusqu'à ce que le résultat final est le meilleur individu généré durant la recherche ou bien si le nombre maximal de générations soit atteint.
Dans cet article, l'approche génétique est utilisée pour générer les règles symboliques interprétant le résultat du réseau de neurones, c'est pourquoi ces règles doivent être représentées sous forme de chromosomes.
Le chromosome est composé d'un ensemble de gènes, chaque gène correspond à une règle, cela dit que le chromosome code un ensemble de règles (figure2)
R1
R2
R3
R4
R5 1(-1)010 00010 10011 10110
1110(-1)
Class0 Class1 Class1 Class0 Class0 Fig. 2 - Forme du chromosome dans MC-RULEGEN
Prémisses Conclusions -1 veux dure que l'attribut n'est pas activé. 0 veux dire que l'attribut x s'ecrit not (x) dans la règle générée 1 veux dire que l'attribut x s'ecrit (x) dans la règle générée on suppose que les attributs se lisent de la gauche vers la droite alors le dernier gène devient : if x1 and x2 and x3 and not(x4) then class0 , x1, x2 et x3 sont dits attributs positifs et x4 un attribut négatif, x5 un attribut inactif
La population initiale de règles est choisie à partir de la table de vérité, qui doit contenir toutes les combinaisons possibles de valeurs d'entrées (attributs), les valeurs de sorties sont générées aléatoirement.
La fonction fitness permet d'évaluer les individus (chromosomes), et donc de déterminer la qualité de la solution. Les meilleurs individus sont mutés et croisés pour produire une nouvelle génération. Dans cet article deux mesures de fitness sont utilisées: la fidélité et la compréhensibilité.
Les trois opérateurs de base utilisés dans les AG sont: la selection, le croisement et la mutation. La méthode de la selection utilisée est celle de la roulette (roulette wheel selection).
Croisement: permet de combiner deux chromosomes (parents) afin de produire un nouveau chromosome (offspring). La figure 3 explique le croisement ( | est le point de croisement):
C’est au cours de l’évaluation des règles que vont se réaliser les interactions entre le module génétique et le RNA. nous
avons modifié l'algorithme de la rétropropagation (developed by Rumelhart hinton, wiliams [
Couche Sortie
Couche Cachée 1 2 3 4 5
Couche d'entrée
L'ensemble de règles générée par AG (supposé optimal) est exprimé sous forme de chaînes de "un", de "zéro" ou de
"-1". On applique l'algorithme de Quine-McCluskey sur cet ensemble afin d'arriver à la solution exacte et simplifiée. La
méthode de Quine consiste, en partant de la décomposition canonique disjonctive de f, à utiliser systématiquement la
formule de simplification x + ¯ x = 1 plusieurs fois jusqu'à ce que aucune paire de termes ne peut être combinées [
Considérrons l’exemple suivant : f(a, b, c) = a.b + b.c + a.c La décomposition canonique disjonctive de f est : f(a, b, c, d) = a.b.c + a.b.c + a.b.c + abc + abc +a b c
La méthode de quine MC-Cluskey permet de simplifier une fonction en partant de sa forme canonique, nous avons modifié l'algorithme pour qu'il commence avec n'importe quels termes, cela permet de réduire la complexité de l'algorithme.
Comment utiliser l'algorithme de Quine McCluskey dans notre approche: 1. Initialement RNM =, RFIN= 2. Regrouper les règles générées par le module génétique dans des classes, chaque classe englobe tous les règles ayant le même nombre des attributs inactifs (valeur=-1),
3. Numéroter chaque classe, ex: class0 contient les règles avec zéro (0) attribut négatif, class1 contient les règles avec un seul (1) attribut négatif, etc … (si le nombre des sous classes de la classe0=n nbre maximum de classes (nbrclass)=n)
4. Trier chaque classe suivant le nombre des attributs positifs (valeur=1), construire alors des sous classes, chacune d'elles contient les règles ayant le même nombre de 1, deux sous classes de la classe i sont dites adjacentes si la première contient m attributs positifs et la 2ème contient m+1 attributs positifs, 5. Commencer par la classe0, (i 0) 6. Apparier les sous classes adjacentes de la classei deux à deux, appliquer la règle x + ¯x (voir figure 6) ,
7. Les règles qui ont participé à la génération des nouvelles règles sont
marquées,
8. Les règles non marquées sont insérées dans RNM
9. Les nouvelles règles sont insérées dans la classe i+1,
10. i i+1
11. si i< n alors aller à l'étape 5 sinon RFIN= RNM fsi
12. Déterminer quels sont les implicants premiers essentiels à partir de RFIN
[
Règles du module
Les règles obtenues à partir des deux modules précédents (génétique et simplification) sont utilisées par le module "système à base règle" dans le but d'obtenir un ensemble final et réduit de règles pertinentes qui couvre le maximum des exemples de test.
On suppose que E= l'ensemble de règles finale, initialement E=, pour chaque règle, la précision est calculée en comptant le nombre des exemples correctement classés par cette règle, les règles sont triées dans l'ordre décroissant, selon leurs valeurs de précision, choisir les règles dont la précision est supérieur à la valeur maxaccuracy définie par l'utilisateur, si cette règle existe alors: - calculer NB le nombre de prémisses dans chaque règle de l'étape 3, - Choisir uniquement les règles dont la valeur NB<prem, (prem est une valeur définie par l'utilisateur) - Déplacer la règle dans E Sinon, l'algorithme fait des combinaisons des deux meilleurs règles au sens de précision, ce processus continu jusqu'à ce qu'on trouve un ensemble de règles vérifiant le critère précision >=maxaccuracy et NB<prem, cet ensemble de règles est déplacé dans E.
Notre système MC-RULEGEN est testé sur la base de données cancer du sein, nous avons utilisé le modèle PMC avec une seule couche cachée. Les résultats sont comparés avec d'autres approches.
Base de données cancer du sein [
Le meilleur résultat est obtenu en utilisant (table 1): 9 neurones dans la couche d’entrée, 03 neurones dans la couche cachée et deux neurones dans la couche de sortie, nous avons utilisé la fonction logistique entre les couches, le momentum = 0.95 et la fréquence d’apprentissage=0.4. Après 500 époques, le taux de classification est égale à 98%. 3.2. Extraction de règles par l’algorithme génétique
Fonction Fitness:MC-RULEGEN cherche des règles avec:
Une meilleure précision, Un nombre minimal de prémisses.
Entrées 9
Cachées 3 2
Sorties
Training
La taille de la population est initialisée à la valeur "popsize", celle du chromosome ( l'individu) est égale "indiv_length", le nombre de gènes (règles) dans le chromosome est égale à "rulesize". Chaque règle contient "sizeinput" attributs. La méthode de la roulette est utilisée dans la selection des individus. La prochaine génération est créee à partir de la population courante en utilisant les opérateurs de croisement (avec une probabilité pCross) et de mutation (avec une probabilité pMut). Les meilleurs chromosomes au sens de fitness survivent et participent à la création de la nouvelle population. La population continue à évoluer vers les meilleurs valeurs de fitness. Après plusieurs générations, l'algorithme converge vers le meilleur chromosome. La figure7 montre l'évolution des valeurs de la fonction fitness des meilleurs individus de chaque génération. La compréhensibilité dans chaque individu est calculée en comptant le nombre des attributs inactifs, si ce nombre augumente alors la compréhensibilité augmente. Nous avons utilisé dans notre travail les valeurs suivante: popsize=30, rulesize=15, sizeinput=9; indiv_length = sizeinput*rulesize; pMut=0.2; pCross=0.8; nombre de génération égale à 10000;
En appliquant la procédure d'optimisation, deux règles sont éliminées.
La table 2 montre les 03 meilleurs règles obtenues pour chaque classe. Pour la classe bénigne, en se basant sur la première règle, uniquement 5 parmi 229 d'exemples de test sont malclassées, si on rajoute à cette règle la deuxième, la précision saute à 100% (voir table 3), les autres règles sont alors omises.
500 GENERATION 1000
500 GENERATION
1000 Règles Malignes Précision (Test %) Précision (Train %) Nombre prémisses / Nombre de règles
Règles Bégnine Précision (Test %) Précision (Train %) Nombre prémisses / Nombre de règles
RM1 80 81.2 1/1
RM2 100 98.66 2/2 RM1 + RM2
RM1+RM2 +RM3 Les règles finaux obtenues sont données par: Règles de la classe Bénigne if (v(8) Normal Nucleoli <2.77) then benin if (v(6) Bare Nuclei <3.45) then benin Règles de la classe Maligne if (v(8) Normal Nucleoli if (v(6 Bare Nuclei if (v(4) Marginal Adhesion ≥2.77) then malignant ≥3.45) then malignant ≥ 3) then malignant
Notre base de règles est comparée avec le réseau de neurones (NN), les résultats des table 4 et table 5 montrent que les cinq règles extraites par l'approche MC-RULEGEN permet de couvrir tous les exemples de test, le nombre maximal d'attributs dans chaque règle est égale à "1". Notre système utilise seulement 03 attributs v(8), v(6) et v(4) qui sont suffisants pour représenter toutes les connaissances du NN.
NN (Exemples) MC-RULEGEN (Règles) 229 2
98% 100%
attributs (prémisses) 9 1 La précision est passée de 98% à 100% en utilisant seulement 05 règles et 03 attributs. 120 3 Apprentissage
de neurones
Ratio 336/341 342/349 678/690
% 4. Comparaisons avec d'autres travaux
Dans cette section, nous avons comparé notre approche avec d'autres travaux soit qu'ils utilisent l'approche globale (BioRe, GEX, CGA) ou locale (Partial-Re, Full-RE, NeuroRule, C4.5rules). Les résultats de classification des règles obtenues, le nombre de règles trouvé ainsi que le nombre maximale de prémisses par règle sont illustrés dans la table 6. les résultats montrent que les règles extraites par Mc-RULEGEN sont plus performantes et plus compréhensibles par rapport à celles extraites par les autres techniques. MC-RULEGEN est capable d'extraire un ensemble de règles d'une meilleur performance.
Ce papier présente une nouvelle approche d'extraction de règles à partir d'un réseau de neurones. Notre approche combine les deux approches métaheuristiques (algorithme génétique) et les exactes (Quine Mc-cluskey) au sein d'un même système afin d'extraire les règles binaires de la forme if-then, les règles obtenues sont passées dans un système à base de règles pour raffinage. Les résultats expérimentaux montrent que notre approche MC-RULEGEN génère des règles de très haute performance. REFERENCES Markowska-Kaczmar, Evolutionary approaches to rule extraction from neural networks, studies in computational intelligence (SCI) 82, 117-209, 2008.
Markowska-Kaczmar U, Mularczyk K (2006) GA-based pareto optimization, Vol. 16 of Studies in computational intelligence. Springer, Berlin Heidelberg, Newyork Markowska-Kaczmar, Pawel Wnuk-Lipinski: Rule Extraction from Neural Network by Genetic Algorithm with Pareto Optimization. ICAISC 2004: 450-455 McMillan C, Mozer M.C, and P.smolensky. the Connectionist Scientist Game: Rule Extraction and Refinement in a Neural Network. In: Proceedings of the Thirteenth Annual Conference of the Cognitive Science Society, Hillsdale, NJ, 1991.