Efficient Learning of Markov Blanket and Markov Blanket Classifier

La sélection de variables est un problème de première importance dans le domaine de l'apprentissage machine et le forage de données. Pour une tâche de classification, un jalon important du développement de stratégies sélection de variables a été atteint par Koller et Shamai [1]. Sur la base des travaux de Pearl dans le domaine des réseaux bayésiens (RB) [2], ils ont démontré que la couverture de Markov (CM) d'une variable nominale représente le sous-ensemble optimal pour prédire sa valeur (classe). Différents algorithmes ont été développés pour d'induire la CM d'une variable cible à partir de données, sans pour autant nécessiter l'induction du RB qui inclue toutes les variables potentielles depuis 1996, mais ils affichent tous des problèmes de performance, soit au plan de la complexité calculatoire, soit au plan de la reconnaissance. La première contribution de cette thèse est le développement d'un nouvel algorithme pour cette tâche. L'algorithme IPC-MB [9-11] permet d'induire la CM d'une variable avec une performance qui combine les meilleures performances en terme de complexité calculatoire et de reconnaissance. IPC-MB effectue une recherche itérative des parents et enfants du noeud cible en minimisant le nombre de variables conditionnnelles des tests d'indépendance. Nous prouvons que l'algorithme est théoriquement correct et comparons sa performance avec les algorithmes les mieux connus, IAMB [12], PCMB [13] et PC [14]. Des expériences de simulations en utilisant des données générées de réseaux bayésiens connus, à savoir un réseau de petite envergure, Asia, contenant huit noeuds; deux réseaus de moyenne envergure, Alarm et PolyAlarm de 37 noeuds, et deux réseaux de plus grande envergure, Hailfinder contenant 56 noeuds et Test152 contenant 152 noeuds. Les résultats démontrent qu'avec un nombre comparable d'observations, (1) IPC-MB obtient une reconnaissance nettement plus élevée que IAMB, jusqu'à 80% de réduction de distance (par rapport à un résultat parfait), (2) IPC-MB a une reconnaissance légèrement supérieure que PCMB et PC, et (3) IPC-MB nécessite jusqu'à 98% moins de tests conditionnels que PC et 95% de moins que PCMB (le nombre de tests conditionnels représente la mesure de complexité calculatoire ici). La seconde contribution de la thèse est un algorithme pour induire la topologie du RB constitué des variables de la CM. Lorsqu'une CM d'une variable cible forme un RB, ce réseau est alors considéré comme un classificateur, nommé une Couverture de Markov de Classification (MBC). L'algorithme a été nommé IPC-MBC sur la base du premier algorithme, IPC-MB. À l'instar de IPC-MB, l'algorithme IPC-MBC effectue une série de recherches locales pour éliminer les faux-négatifs, incluant les noeuds et les arcs. Cependant, sa complexité est supérieure et requiert des ressources calculatoires plus importantes que IPC-MB. Nous prouvons que IPC-MB est théoriquement et effectuons des études empiriques pour comparer sa performance calculatoire et de reconnaissance par rapport à PC seul et PC combiné à IPC-MB (c.-à-d. l'induction de la structure du RB avec l'algorithme PC seul et avec PC appliqué sur le résultat de IPC-MB). Les mêmes données que pour les expériences de simulation de IPC-MB sont utilisées. Les résultats démontrent que IPC-MBC combiné à IPC-MB et que PC combiné à IPC-MB sont tous deux plus efficaces que PC seul en termes de temps de complexité calculatoires, fournissant jusqu'à 95% de réduction du nombre de tests conditionnels, sans pour autant avoir d'impact au plan du taux de reconnaissance.