#### Date of Award

Spring 2018

#### Document Type

Thesis

#### Degree Name

Master of Science (MS)

#### Department

Applied Mathematics

#### First Advisor

Jem Corcoran

#### Abstract

Bayesian networks are widely considered as powerful tools for modeling risk assessment, uncertainty, and decision making. They have been extensively employed to develop decision support systems in a variety of domains including medical diagnosis, risk assessment and management, human cognition, industrial process and procurement, pavement and bridge management, and system reliability. Bayesian networks are convenient graphical expressions for high dimensional probability distributions which are used to represent complex relationships between a large number of random variables. A Bayesian network is a directed acyclic graph consisting of nodes which represent random variables and arrows which correspond to probabilistic dependencies between them. The ability to recover Bayesian network structures from data is critical to enhance their application in modeling real-world phenomena.

Many research efforts have been done on this topic to identify the specific network structure. Friedman and Koller suggest an approach based on the assumption that every Bayesian network has a corresponding ordering of its vertices. An order associated with a Bayesian network can be thought of as a logical ordering of causality, with random variables earlier in the order causing random variables later in the order.

The Friedman and Koller (FK) algorithm itself is comprised of two steps: (1) Use Markov Chain Monte Carlo (MCMC) methods to sample the order of a Bayesian network and then (2) sample the parent set for each vertex independently using Bayesian methods. However, since some Bayesian networks are compatible with more orders than others, the FK algorithm is biased towards these networks. The algorithm presented in this thesis corrects this bias while adding minimal algorithmic complexity to the FK algorithm by uniformly drawing linear extensions of the partial ordering of vertices implied by any Bayesian network.

#### Recommended Citation

Sidrow, Evan, "Network Structure Sampling in Bayesian Networks via Perfect Sampling from Linear Extensions" (2018). *Applied Mathematics Graduate Theses & Dissertations*. 98.

https://scholar.colorado.edu/appm_gradetds/98