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.

Abstract

Feature selection is a fundamental topic in data mining and machine learning. It addresses the issue of dimension reduction by removing non-relevant, or less relevant attributes in model building. For the task of classification, a major milestone for feature selection was achieved by Koller and Sahami [1]. Building upon the work of Pearl on Bayesian Networks (BN) [2], they proved that a Markov blanket (MB) of a variable is the optimal feature subset for class prediction. Deriving the MB of a class variable given a BN is a trivial problem. However, learning the structure of a BN from data is known to be NP hard. For large number of variables, learning the BN is impractical, not only because of the computational complexity, but also because of the data size requirement that is one of the curses of high dimensionality feature spaces. Hence, simpler topologies are often assumed, such as the Naive Bayes approach (NB) [5, 6], which is probably the best known one due its computational simplicity, requiring no structure learning, and also its surprising effectiveness in many applications despite its unrealistic assumptions. One of its extension, Tree-Augmented Naïve Bayes (TAN) [7] is shown to have a better performance than NB, by allowing limited additional dependencies among the features. However, because they make strong assumptions, these approaches may be flawed in general. By further relaxing the restriction on the dependencies, a BN is expected to show better performance in term of classification accuracy than NB and TAN [8]. The question is whether we can derive a MB without learning the full BN topology for the classification task. Let us refer to a MB for classification as a Markov Blanket Classifier, MBC. The MBC is expected to perform as well as the whole Bayesian network as a classifier, though it is generally much smaller in size than the whole network. This thesis addresses the problem of deriving the MBC effectively and efficiently from limited data. The goal is to outperform the simpler NB and TAN approaches that rely on potentially invalid assumptions, yet to allow MBC learning with limited data and low computational complexity. Our first contribution is to propose one novel algorithm to filter out non-relevant attributes of a MBC. From our review, it is known that there are at least nine existing published works on the learning of Markov blanket since 1996. However, there is no satisfactory tradeoff between correctness, data requirement and time efficiency. To address this tradeoff, we propose the IPC-MB algorithm [9-11]. IPC-MB performs an iterative search of the parents and children given a node of interest. We prove that the algorithm is sound in theory, and we compare it with the state of the art in MB learning, IAMB [12], PCMB [13] and PC [14]. Experiments are conducted using samples generated from known Bayesian networks, including small one like Asia with eight nodes, medium ones like Alarm and PolyAlarm (one polytree version of Alarm) with 37 nodes, and large ones like Hailfinder (56 nodes) and Test152 (152 nodes). The results demonstrate that, given the same amount of observations, (1) IPC-MB achieves much higher accuracy than IAMB, up to 80% reduction in distance (from the perfect result), (2) IPC-MB has slightly higher accuracy than PCMB and PC, (3) IPC-MB may require up to 98% fewer conditional independence (CI) tests than PC, and 95% fewer than PCMB. Given the output of IPC-MB, conventional structure learning algorithms can be applied to recover MBC without any modification since the feature selection procedure is transparent to them. In fact, the output of IPC-MB can be viewed as the output of general feature selection, and be employed further by all kinds of classifier. This algorithm was implemented by the author while working at SPSS and shipped with the software Clementine 12 in 2007. The second contribution is to extend IPC-MB to induce the MBC directly without having to depend on external structure learning algorithm, and the proposed algorithm is named IPC-MBC (or IPC-BNC in one of our early publication) [15]. Similar to IPC-MB, IPC-MBC conducts a series of local searches to filter out false negatives, including nodes and arcs. However, it is more complex and requires greater computing resource than IPC-MB. IPC-MBC is also proved sound in theory. In our empirical studies, we compare the accuracy and time cost between IPC-MBC, PC and IPC-MB plus PC (i.e. structure learning by PC on the features output by IPC-MB), with the same data as used in the study of IPC-MB. It is observed that both IPC-MBC and IPC-MB plus PC are much more time efficient than PC, with up to 95% saving of CI tests, but with no loss of accuracy. This reflects the advantage of local search and feature selection respectively.