PhD Seminar • Artificial Intelligence • Improved Scalability and Accuracy of Bayesian Network Structure Learning within Score-and-Search

Please note: This PhD seminar will take place online.

Charupriya Sharma, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Peter van Beek

A Bayesian network is a probabilistic graphical model that consists of a directed acyclic graph (DAG), where each node is a random variable and attached to each node is a conditional probability distribution (CPD). A Bayesian network (BN) can either be constructed by a domain expert or learned automatically from data using the well-known score-and-search approach. Previous work has shown that the accuracy of a data analysis can be improved by incorporating structured representations of the CPDs into the DAG algorithms and by learning a set of DAGs from a dataset, and then performing model averaging to obtain a representative DAG.

In this talk, we focus on improving the accuracy of the score-and-search approach for learning a BN and in scaling the approach to datasets with larger numbers of random variables. We introduce a novel model averaging approach to learning a BN motivated by performance guarantees in approximation algorithms. Our approach considers all optimal and all near-optimal networks for model averaging and provides pruning rules that retain optimality while enabling our approach to scale to BNs significantly larger than the current state of the art. We extend our model averaging approach to simultaneously learn the DAG and the local structure of the CPDs in the form of a noisy-OR representation. We provide an effective gradient descent algorithm to score a candidate noisy-OR using the widely used BIC score.

Our empirical results provide evidence for the success of our approach to learning Bayesian networks that incorporate noisy-OR relations and we provide pruning rules that allow the search to successfully scale to medium sized networks. We also extend our model averaging approach to simultaneously learn the DAG and the local structure of the CPD using neural networks representations. Our approach compares favourably with approaches like decision trees and performs well in instances with low amounts of data. Finally, we introduce a score-and-search approach to simultaneously learn a DAG and model linear and non-linear local probabilistic relationships between variables using multivariate adaptive regression splines (MARS). MARS are polynomial regression models represented as piecewise spline functions. We show on a set of discrete and continuous benchmark instances that our proposed approach can improve the accuracy of the learned graph while scaling to instances with over 1,000 variables.

To join this PhD seminar on MS Teams, please go to https://teams.microsoft.com/l/meetup-join/19%3ameeting_MzhjYmU2OGEtODI2MC00NjdiLTljNmMtZDVjZDA0NzhjNjU5%40thread.v2/0?context=%7b%22Tid%22%3a%22723a5a87-f39a-4a22-9247-3fc240c01396%22%2c%22Oid%22%3a%220e1e0a54-770d-42a2-9a9c-3db7942a1407%22%7d.