GÉNÉRALITÉS DES RESEAUX BAYESIENS

INTRODUCTION ET GÉNÉRALITÉS DES RESEAUX BAYESIENS

lorsque les situations sont incertaines ou les données incomplètes la décomposition de la loi jointe permet d’avoir des algorithmes d’inférence puissants qui font des Réseaux Bayésiens des outils de modalisation et de raisonnement très pratique. Pour les problèmes de classification ils sont utiles lorsque les interactions entre les différents critères peuvent être modélisées par des relations de probabilité conditionnelles. Il est possible d’en faire l’apprentissage à partir d’une base de données lorsque la structure du Réseaux Bayésiens n’est pas fournie a priori par un expert. La recherche structure n’est pas simple d’un Réseaux Bayésiens à cause du fait que l’espace de recherche est de taille super-exponentielle en fonction du nombre de variables. Nous allons commencer par introduire quelque notions générales sur la structure des Réseaux Bayésiens, la façon de lui associer un score et les propriétés intéressantes de ces scores.

Ensuite nous détaillons des méthodes de recherche de structure les plus couramment utilisées, de la recherche de la causalité, au parcours heuristique de l’espace des Réseaux Bayésiens avec les différents problèmes d’initialisation que cela pose. Nous comparerons alors les méthodes grâce à deux séries de teste. La première série de tests permet d’évaluer l’efficacité de ces méthodes à trouver un bon Réseau Bayésien pour des problèmes de classification en utilisant éventuellement certaines connaissances a priori sur la tache à résoudre. Nous conclurons alors sur les avantages et inconvénients des différentes méthodes utilisées et évoquerons certaines techniques prometteuses pour l’apprentissage de structure des Réseaux Bayésien. Nous allons terminer notre chapitre par une problématique qui propose de la recherche de la causalité, au parcours heuristique de l’espace des Réseaux Bayésiens avec les différents problèmes d’initialisation que cela pose on se base sur des algorithmes génétique et précisément sur l’algorithme de recherche Coucou et l’algorithme de recherche Luciole.

Généralités

La première idée pour trouver la meilleure structure d’un Réseau Bayésien, est de parcourir tous les graphes possibles, de leur associer un score, puis de choisir le graphe ayant le score le plus élevé. Une premier approche, proposée initialement par Spirtes et al. D’un coté, et Pearl et Verma de l’autre, consiste à rechercher les différentes indépendances conditionnelles qui existent entre les variables. Les autres approches tentent de quantifier l’adéquation d’un Réseau Bayésien au problème à résoudre, c’est-à-dire d’associer un score à chaque Réseau Bayésien. Puis elles recherchent la structure qui donnera le meilleur score dans l’espace ? des graphes dirigés sans circuits. Une approche exhaustive est impossible en pratique en raison de la taille de l’espace de recherche. la Formule I-2[27] démontrée par [Robinson, 1977] prouve que le nombre de structures possibles à partir de ? noeuds est super-exponentiel (par exemple, ??(5)=29281 et ?? 10 =4.2×1018)

ALGORITHME COUCOU ET LUCIOLE

L’optimisation et l’intelligence artificielle sont des domaines de recherche actifs avec une littérature en pleine expansion. Pour la plupart des applications, le temps, l’argent et les ressources sont toujours limités, et leur utilisation optimale devient donc de plus en plus importante. Dans les applications de conception moderne, il faut un changement de paradigme dans la pensée et la conception pour trouver des solutions d’économie d’énergie et de conception plus écologique. Par exemple, il est bien connu que des problèmes d’optimisation combinatoire tels que Le problème du voyageur de commerce (en anglais : Travelling Salesman Problem « TSP ») sont NP-Difficiles [Garey and Johnson, 1979], ce qui signifie qu’il n’y a pas d’algorithmes efficaces en général. Même sans algorithmes efficaces, nous avons encore à résoudre ces problèmes difficiles dans la pratique. Cela conduit au développement des diverses techniques exotiques et des méthodes spécifiques aux problèmes afin que des connaissances spécifiques aux problèmes (comme les dégradés) puissent être utilisées pour guider des meilleures procédures de recherche.

En général, les algorithmes qui utilisent des connaissances liées à des problèmes devraient fonctionner mieux que les méthodes de type boîte noire qui n’utilisent pas du tout la connaissance du problème. Mais l’incorporation de connaissances spécifiques à un problème limite souvent l’utilisation d’une méthode ou d’un algorithme. En outre, il n’est pas facile ou trop informatisé d’intégrer ces connaissances. Parfois, il peut être impossible d’incorporer ces connaissances, soit parce que nous ne pouvons pas avoir un aperçu du problème ou parce que nous ne savons pas comment. Dans ce cas, la seule option est d’utiliser des algorithmes de type boîte noire qui n’assument aucune connaissance du problème d’intérêt.

Dans la plupart des cas, pour les problèmes NP-Difficiles, la seule alternative est d’utiliser des méthodes heuristiques et métaheuristiques par essais et erreurs. Les méthodes heuristiques sont la recherche de solutions par essais et faux, alors que les méthodes métaheuristiques peuvent être considérées comme des méthodes heuristiques de niveau supérieur qui utilisent l’information et la sélection des solutions pour guider le processus de recherche. Les algorithmes d’optimisation sont les outils et les techniques permettant de résoudre des problèmes d’optimisation dans le but de trouver son optimalité, même si cette optimalité n’est pas toujours accessible. Cette recherche de l’optimalité est encore compliquée par le fait que l’incertitude est presque toujours présente dans les systèmes réels. Par conséquent, nous recherchons non seulement la conception optimale mais aussi la conception robuste dans l’ingénierie et l’industrie. Des solutions optimales, qui ne sont pas assez robustes, ne sont pas pratiques en réalité. Des solutions suboptimales ou de bonnes solutions robustes sont souvent le choix dans de tels cas. Au cours des vingt dernières années, les algorithmes métaheuristiques inspirés de la nature ont gagné une grande popularité dans les domaines de l’optimisation, de l’intelligence artificielle, de l’apprentissage automatique, de l’intelligence computationnelle, de l’exploration des données et des applications d’ingénierie.

Pourquoi la recherche coucou est si efficace?

En plus de l’analyse précédente montrant que DE, PSO et SA sont particulièrement des cas de recherche de coucou, des études théoriques récentes indiquent aussi que la recherche de coucou a une convergence globale. Des études théoriques sur l’optimisation des essaims de particules ont suggéré que la PSO peut converger rapidement vers la meilleure solution actuelle, mais pas nécessairement les meilleures solutions globales. En fait, certains analystes suggèrent que les équations de mise à jour des PSO ne satisferont pas aux conditions de convergence globale, et donc il n’y a aucune garantie pour la convergence globale. D’autre part, il a prouvé que la recherche du coucou satisfait aux exigences de convergence globale et à ainsi garantit des propriétés.

Cela implique que pour l’optimisation multimodale, la PSO peut converger prématurément vers un optimum local, alors que la recherche de coucou peut généralement converger vers l’optimalité globale. En outre, la recherche de coucou a deux capacités de recherche: recherche locale et recherche globale, contrôlée par une probabilité de commutation / découverte. la recherche locale est très intensive avec environ 1/4 du temps de recherche (pour ??=0.25), tandis que la recherche globale prend environ 3/4 du temps de recherche total. Cela permet d’explorer l’espace de recherche de manière plus efficace à l’échelle globale et, par conséquent, l’optimalité globale peut être trouvée avec une probabilité plus élevée. Un autre avantage de la recherche de coucou est que sa recherche globale utilise des vols Lévy ou processus, plutôt que des randonnées aléatoires standard. Comme les vols de Lévy ont une moyenne et une variance infinies, CS peut explorer l’espace de recherche plus efficacement que les algorithmes utilisant des processus gaussiens standard. Cet avantage, conjugué à la fois aux capacités locales et de recherche et à la convergence globale garantie, rend la recherche de coucou très efficace. En effet, diverses études et applications ont démontré que la recherche du coucou est très efficace.

Complexité d’Algorithme :

Presque tous les algorithmes métaheuristiques sont simples en termes de complexité, et ils sont donc faciles à mettre en oeuvre. Algorithme Firefly a deux boucles intérieures en passant par la population?, et une boucle externe pour l’itérateur ?. La complexité dans le cas extrême est donc ?(?2?). Comme ? est petit (typiquement ? = 40) et ? est grand (par exemple, ? = 5000), le coût de calcul est relativement peu coûteux parce que la complexité de l’algorithme est linéaire en termes de ?. Le coût de calcul principal sera dans les évaluations de fonctions objectives, en particulier pour les objectifs de type boîte noire externe. Ce dernier cas est également vrai pour tous les algorithmes métaheuristiques. Après tout, les problèmes d’optimisation, la partie la plus coûteuse en termes de calcul est l’évaluation objective. Si ? est relativement grand, il est possible d’utiliser une boucle interne en classant l’attractivité ou la luminosité de toutes les lucioles en utilisant des algorithmes de tri. Dans ce cas, la complexité algorithmique de l’algorithme de luciole sera ?(??log ? ).

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction générale
CHAPITRE I: INTRODUCTION ET GÉNÉRALITÉS DES RESEAUX BAYESIENS
I- Introduction
I-1- Exemple
II- Généralités
III- les algorithmes
III-1- L’algorithme PC, recherche de causalité
III-2- restriction à l’espace des arbres
III-2- L’algorithme K2
III-4- Recherche Gloutonne
III-5- L’algorithme EM
IV- Apprentissage des paramètres
IV-1- A partir de données complètes
IV-1-1- Apprentissage statistique
IV-1-2- Apprentissage statistique
IV-1-3- Apprentissage bayésien
IV-2 A partir de données incomplètes
IV-2-1- Nature des données manquantes
IV-2-2- Traitement des données MCAR
IV-2-3- Traitement des données MAR
V- Problématique
CHAPITRE II: ALGORITHME COUCOU ET LUCIOLE
I- Introduction
I-1- Problèmes d’optimisation
I-2- Définition d’un Algorithme d’Optimisation
II- Recherche et analyse de coucou
II-1- La recherche coucou
II-2- Cas particuliers de la Recherche coucou
II-3- Pourquoi la recherche coucou est si efficace
III- Applications de la recherche coucou
III-1- Analyse théorique et mise en oeuvre
III-2- Améliorations et autres études
III-3- Implémentations
IV- Algorithme et analyse de Luciole (Firefly Algorithm )
IV-1- Algorithme de Luciole
IV-2- Les Paramètres
IV-3- Complexité d’Algorithme
IV-4- Cas particuliers de FA
IV-5- Variantes d’Algorithme Luciole « Firefly Algorithm
IV-6- Attraction et diffusion
IV-7- Pourquoi SA est efficace
V- Applications
VI- Conclusions
CHAPITRE III : CONCEPTION ET IMPLEMENTATION
1- Introduction
1-1- Algorithme de recherche coucou (AC)
1-2- Algorithme original luciole
II- Documents BNT_StructureLearning_v1.3
III- Méthode proposée
III-1- La formulation du problème
IV- Expérimentation et résultats
IV-1- Langage Matlab 07
IV-2- La base de teste HEART
V- Présentation de l’application
VI- Conclusion
Conclusion générale
Références Bibliographiques
Liste des figures
Liste des tableaux
Liste des algorithmes
Liste des abréviations