A two-step approach Bayesian network model selection

It is often desirable to show relationships between unstructured, potentially related data elements, or features, composing a knowledge database (KD). By understanding the interaction between these elements, we may gain insight into the underlying process from which the KD is derived, and as a result, we can often model the process. Bayesian Belief Networks (BBN) in particular, are adept at modeling knowledge databases for two reasons. The first is that BBNs give a structural representation of data elements through a directed acyclic graph (DAG). This ability may make BBNs invaluable in areas such as data mining, where statistical relationships between the features of a traditional database are not apparent. An accurate BBN will clearly show features exerting influences on each other. The second strength of the BBN model is its ability to encode conditional expectations between knowledge database features. This ability facilitates using BBNs as inference engines. Given a set of instantiated elements, BBNs allow us to derive the most statistically likely instantiation of states for elements whose state is unknown. These qualities lend themselves to BBNs being proficient in applications ranging from computer vision to risk-assessment. In this thesis, two frameworks for BBN structure learning, or model selection, will be compared. The first is the asymptotically correct structure learning algorithm which shows efficient search space exploration characteristics. The second takes permutations of global structures in an elitist elimination heuristic search and shows precise search space exploitation characteristics. Comparisons between techniques will be presented, paying particular attention to computational complexity versus model precision. In the elitist elimination technique, comparisons between the Minimum Description Length (MDL) scoring heuristic and the Database probability given Model (DGM) scoring heuristic, will be provided. A comparison between naïve and non-naïve structure learning will be made along with an analysis of the infeasibility of naïve BBN model selection. Finally, an efficient and precise algorithm tor learning BBNs, which utilizes both frameworks, will be proposed