Algorithmic Implications of Bayesian Networks

Bayesian networks are useful for both inferential exploration of previously undetermined relationships among variables as well as descriptions of these relationships upon discovery. In the former case, raw computational power can be brought to bear upon a problem. In the case of determining the likelihood of rain the next day following a rainy day, raw meteorological data can be input into the computer and the computer can determine the resultant probability network. This process of network discovery is discussed by Friedman & Goldszmidt[14]. Such a process is computationally intensive and NP-hard in its algorithmic implications. The benefit of such a process is evident in the ability to describe the discovered network in the future. The calculation of any probability branch of the network can then be computed in linear time.