A Genetic Algorithm for Tuning Variable Orderings in Bayesian Network Structure Learning

Abstract

In the last two decades or so, Bayesian networks (BNs) [Pe88] have become a prevalent method for uncertain knowledge representation and reasoning. BNs are directed acyclic graphs (DAGs) where nodes represent random variables, and edges represent conditional dependence between random variables. Each node has a conditional probabilistic table (CPT) that contains probabilities of that node being a specific value given the values of its parents. The problem of learning a BN from data is important but hard. Finding the optimal structure of a BN from data has been shown to be NP-hard [HGC95], even without considering unobserved or irrelevant variables. In recent years, many Bayesian network learning algorithms have been developed. Generally these algorithms fall into two groups, score-based search and dependency analysis (conditional independence tests and constraint solving). Many previous approaches require that a node ordering is available before learning. Unfortunately, this is usually not the case in many real-world applications. To make greedy search usable when node orderings are unknown, we have developed a permutation genetic algorithm (GA) wrapper to tune the variable ordering given as input to K2 [CH92], a score-based BN learning algorithm. In our continuing project, we have used a probabilistic inference criterion as the GA’s fitness function and we are also trying some other criterion to evaluate the learning result such as the learning fixed-point property.