État de l’art dans le domaine du diagnostic des réseaux de télécommunication

Système expert à base de règles

Un système expert de diagnostic est une suite d’applications informatiques qui intègrent une grande base de connaissances ou de raisonnements d’experts sur des tâches de diagnostic bien précises et qui infèrent de façon automatique les causes racines des anomalies observées. Pour constituer une base de raisonnements valides, les connaissances d’experts en matière de diagnostic peuvent être formalisées sous forme de règles, d’arbre de décisions, de logique propositionnelle, etc. Une évaluation de différents schémas de représentation des connaissances est faite dans PAU [1986]. La complexité des systèmes experts se situe principalement au niveau de la représentation formelle des connaissances spécialisées HOUNKONNOU [2013]. Un système expert se distingue d’un logiciel classique. En effet, un logiciel classique est développé autour d’un ensemble de procédures algorithmiques. La résolution d’un problème suit une séquence d’étapes bien définie par le programmeur qui doit de ce fait connaître toutes les combinaisons possibles des données d’entrée du logiciel et les traitements associés à ces états. Un système expert quant à lui n’est pas construit autour d’un ensemble de procédures prédéfini. En effet, un système expert peut intégrer la capacité à déterminer lui même les traitements adaptés à un état donné des paramètres d’entrée, c’est-à-dire une séquence d’étapes non prédéfinie par le programmeur pour cet état. Cette différence entre un logiciel classique et un système expert est essentiellement due à la méthode d’organisation et d’utilisation des connaissances spécialisées.

Un programme traditionnel est organisé en deux niveaux : les données et le contrôle CRONK et collab. [1998], c’est-à-dire le code qui résout le problème. La reconnaissance des tâches et la méthode de résolution du problème sont explicitement codées par le programmeur. Il est donc très difficile d’ajouter une nouvelle connaissance sur une tâche donnée ou de changer la méthode de résolution d’un problème complexe. Un système expert quant à lui effectue une séparation entre la reconnaissance des tâches et la résolution du problème. Cette séparation lui confère une architecture logicielle en trois niveaux : les données ou faits en mémoire (working memory), les connaissances sur les tâches (task knowledge ou knowledge base) et le moteur d’inférence (control) CRONK et collab. [1998]. Une inférence est une conclusion déduite sur la base de faits ou d’hypothèses. Cette architecture réduit considérablement les difficultés relatives à la construction et à la modification des programmes informatiques complexes.

Au niveau « control », le moteur d’inférence est un programme qui détermine comment appliquer les connaissances contenues dans la « knowledge base » aux faits et hypothèses courants décrits dans la « working memory » afin d’inférer de nouvelles données qui pourront être utilisées pour de prochaines inférences. Une donnée est un ensemble d’attributs et de valeurs associées qui décrivent explicitement un fait. Pour des faits correspondant à une situation donnée, le moteur d’inférence détermine dans un premier temps les règles potentielles applicables. Dans un second temps, le moteur d’inférence détermine parmi ces règles candidates la règle la plus appropriée à la situation courante. Une règle experte est exprimée sous la forme IF < cond i t i on > THEN < ac t i on >.

La condition peut être évaluée directement si les données ou les hypothèses requises sont disponibles. Certains systèmes experts automatisent des tests sur le domaine expertisé tel qu’un réseau de télécommunication par exemple, et les résultats servent à enrichir les faits et donc mieux évaluer les conditions. L’action peut être une décision définitive ou la création de nouveaux attributs de données, la modification ou la suppression de certaines données dans la mémoire de travail (working memory). Le mécanisme de contrôle implémenté par le moteur d’inférence est un cycle de reconnaissance de faits et d’activation de règles. Ce cycle exécute les trois étapes suivantes CRONK et collab. [1998] :
— Le « matching » ou la recherche de toutes les règles applicables au contenu courant de la mémoire de travail (working memory). Cet ensemble de règles candidates est appelé « conflict set ».
— La sélection ou la résolution du conflit détermine parmi les règles concurrentes, laquelle est la plus appropriée pour être invoquée à ce moment, c’est-à-dire la règle qui correspond au mieux aux données dans la mémoire de travail.
— L’invocation ou l’exécution de la règle précédemment choisie qui consiste à appliquer les actions spécifiées par cette règle. Ces actions changent typiquement les données dans la « working memory ». Dans certains systèmes experts, des règles elles-mêmes sont ajoutées dans la « knowledge base », supprimées ou modifiées.

Le cycle est répété jusqu’à ce qu’aucune règle correspondant au contenu de la mémoire de travail ne soit trouvée (ou une interruption externe du système). Par conséquent, le mécanisme de contrôle est la répétition de l’évaluation des conditions des règles basée sur des données changeantes et non pas sur une structure statique du programme. Ce mécanisme qui n’est pas utilisé dans les logiciels traditionnels est appelé « data-driven control » ou « forward-chaining ».

Le raisonnement d’un système expert repose essentiellement sur la procédure d’inférence qui peut varier d’un système à l’autre. Avec l’algorithme de chaînage avant (forward chaining), le système essaye de faire correspondre les faits disponibles dans la mémoire de travail, avec la portion IF des règles dans la base des connaissances (knowledge base) PHAM [1988]. Lorsque de telles règles sont trouvées (l’ensemble des règles concurrentes), l’une d’entre elles est sélectionnée sur la base d’un critère discriminant approprié, et exécutée. L’exécution génère de nouveaux attributs de données qui enrichissent les faits en mémoire dont le contenu sera utilisé à la prochaine itération pour de nouveau déterminer un ensemble de règles concurrentes et sélectionner celle d’entre elles qui sera exécutée. Les itérations se terminent lorsqu’aucune règle ne peut plus être exécutée, c’est-à-dire qu’aucune règle ne correspond au contenu courant de la mémoire ou lorsqu’il est impossible de discriminer entre les règles concurrentes .

Notons aussi qu’il existe d’autres procédures d’inférence comme alternative au chaînage avant. On peut noter par exemple le chaînage arrière (backward chaining ou goaldriven inferencing) qui consiste à prouver une assertion appellée « objectif » PHAM [1988]. Si l’assertion ne peut être directement prouvée par les faits disponibles dans la base des connaissances, le système examine les règles pour lesquelles la portion THEN contient l’assertion. En effet, pour chacune de ces règles, le système vérifie s’il existe un fait dans la base correspondant à la portion IF. Si un tel fait est disponible, alors la règle est exécutée. Dans le cas contraire, le fait dérivant de la portion IF de la règle est considéré comme une autre assertion (appelée « sous-objectif ») à prouver. Le processus se poursuit récursivement jusqu’à ce que tous les faits requis pour prouver l’assertion initiale sont trouvés, ou qu’une assertion correspondant à un « sous-objectif » ne peut être prouvée. Dans ce dernier cas, l’assertion initiale est elle même désapprouvée.

L’efficacité de la procédure d’inférence d’un système expert est étroitement liée à la pertinence des connaissances acquises et à leur représentation. Les difficultés relatives à la conception des systèmes experts sont justement l’acquisition et la représentation des connaissances. En effet, il est difficile de formaliser le problème à résoudre lors de la conception d’un système expert DAVID et KRIVINE [1987]. Pourtant il faut que le problème soit bien formalisé afin de faciliter l’extraction des connaissances pertinentes de l’énorme quantité d’informations ou de données collectées durant la période d’expertise. L’extraction des connaissances peut s’avérer très complexe si les informations et les données collectées contiennent beaucoup d’incohérences ou de redondances qu’il faut pouvoir identifier et supprimer, mais aussi beaucoup d’insuffisances ou d’absences d’informations qu’il faut pouvoir compléter. Enfin, nous noterons comme conséquence des difficultés précitées qu’il est très difficile de valider un système expert. Néanmoins, malgré ces difficultés, des systèmes experts ont été conçus dans le passé avec plus ou moins de succès.

DENDRAL est le tout premier système expert développé en 1965, par les informaticiens Edward Feigenbaum, Bruce Buchanan, le médecin Joshua Lederberg et le chimiste Carl Djerassi, à l’université de Stanford, pour permettre à la NASA (National Aeronautics and Space Administration) d’effectuer des analyses chimiques du sol de la planète MARS durant les missions spatiales. L’objectif principal de DENTRAL était d’aider les chimistes organiques à l’identification des molécules organiques inconnues, par analyse de leurs spectres de masse et en utilisant les connaissances en chimie.

Le programme DENDRAL est constitué de deux sous-programmes : Heuristic Dendral et Meta Dendral.
— Heuristic Dendral est un programme qui utilise des spectres de masse ou d’autres données expérimentales conjointement avec une base de connaissances en chimie, pour produire un ensemble de structures chimiques possibles. Le spectre de masse d’un composé est produit par un spectromètre de masse, et est utilisé pour déterminer son poids moléculaire, c’est-à-dire la somme des masses de ses constituants atomiques. Par exemple, le composé eau (H2O), a une masse moléculaire de 18 puisque l’hydrogène a une masse de 1,01 et de l’oxygène 16,00, et son spectre de masse présente un pic à 18 unités. Heuristic Dendral utilise cette masse d’entrée et la connaissance du tableau périodique des éléments chimiques ainsi que des règles de valence, pour déterminer les combinaisons possibles des constituants atomiques dont la somme des masses atomiques serait 18. Lorsque la masse moléculaire augmente et que les molécules deviennent plus complexes, le nombre de composés possibles augmente de manière drastique. Ainsi, un programme qui est en mesure de réduire ce nombre de solutions candidates au moyen d’un processus de formation d’hypothèses est essentiel, d’ou le rôle de Meta Dendral.
— Meta Dendral est un système d’acquisition de connaissances qui reçoit en entrée, l’ensemble des structures chimiques possibles (produites par Heuristic Dendral) et les spectres de masse correspondants, et propose un ensemble d’hypothèses pour expliquer la corrélation entre certaines des structures proposées et le spectre de masse de la molécule inconnue à identifier. Ces hypothèses sont ensuite renvoyées à Heuristic Dendral pour tester leur applicabilité. Ainsi, Heuristic Dendral est un système de performance et Meta Dendral est un système d’apprentissage.

Lor et collab. LOR et KAR-WING [1993] ont développé un système de diagnostic des réseaux de multiplexeurs. Les connaissances expertes de diagnostic sont classifiées en deux catégories : les connaissances expertes génériques et les connaissances expertes spécialisées sur des tâches de diagnostic bien précises. Le système expert utilise une base de données contenant des informations statiques et des informations dynamiques nécessaires durant le processus de diagnostic. Ces informations concernent les relations entre les entités logiques (groupes de canaux) et les entités physiques (équipements et liens) telles que les informations de routage, les attributs des entités physiques et les relations d’incidences entre les noeuds du réseau et les liens, etc. Le diagnostic est un processus interactif entre l’expertise générique et l’expertise spécialisée. La survenance d’une panne spécifique invoque une règle spécialisée, qui à son tour, invoque une règle générique. Les règles génériques produisent un diagnostic général et un plan de réparation pour cette panne. Les règles spécialisées sont invoquées pour appliquer ce plan. Plusieurs échanges entre la base de connaissances expertes génériques et celle des connaissances expertes spécialisées sont nécessaires dans une session de diagnostic d’une anomalie survenue sur le réseau.

Table des matières

1 Introduction
1.1 Énoncé du problème
1.2 Contribution
1.3 Structure de la dissertation
2 État de l’art dans le domaine du diagnostic des réseaux de télécommunication
2.1 Introduction
2.2 Système expert à base de règles
2.3 Système expert à base de modèles
2.4 Le diagnostic comme système d’apprentissage artificiel
2.5 Réseau de Petri
2.6 Graphe de dépendances
2.7 Réseaux bayésiens
2.8 Discussions et conclusion
3 Algorithmes d’inférence exacte sur un réseau bayésien
3.1 Introduction
3.2 Quelques bases en théorie des probabilités
3.3 Opération de marginalisation
3.4 Algorithme de somme-produit
3.5 Algorithme d’inférence sur un arbre de jonction
3.6 Discussion et conclusion
4 Apprentissage artificiel des paramètres d’un réseau bayésien
4.1 Introduction
4.2 Estimation paramétrique au sens du Maximum de vraisemblance (MLE)
4.3 L’algorithme MLE avec des données incomplètes
4.4 L’algorithme EM sur un réseau bayésien
4.5 Discussion et conclusion
5 Modèle générique pour le diagnostic automatique d’un réseau de télécommunication
5.1 Introduction
5.2 Propagation de pannes dans un réseau
5.3 Description du modèle générique
5.4 Formalisme du modèle générique
5.5 Calcul de diagnostic du modèle générique
5.6 Capacité de reconfiguration du modèle générique
5.7 Conclusion et perspectives
6 Modélisation probabiliste du réseau FTTH (Fiber To The Home) de type GPON (Gigabit Passive Optical Network)
6.1 Introduction
6.2 Modèle du réseau GPON-FTTH
6.3 Paramètres experts du modèle initial d’un PON
6.4 Validation du modèle initial d’un PON
6.5 Comparaison entre système expert et modèle probabiliste de diagnostic
6.6 Discussion et conclusion
7 Conclusion

Télécharger le rapport complet