## 3 Common Distributional Assumptions for Bayesian Networks
### Inference  
For BNs, _inference_ broadly denotes obtaining the conditional distribution of a subset of variables conditional on a second subset of variables. Following older terminology from expert systems [2], this is called formulating a _query_ in which we ask the BN about the probability of an _event_ of interest after observing some _evidence_. In conditional probability queries, the event of interest is the probability of one or more events in (or the whole distribution of) some variables of interest conditional on the values assumed by the evidence variables. In maximum a posteriori (\"most probable explanation\") queries, we condition the values of the evidence variables to predict those of the event variables.  
All inference computations on BNs are completely automated by _exact_ and _approximate_ algorithms, which we will briefly describe here. We refer the interested reader to the more detailed treatment in [PERSON] et al. [2] and [PERSON] and [PERSON] [5]. Exact inference algorithms use local computations to compute the value of the query. The seminal works of [PERSON] and [PERSON] [39], [PERSON] and [PERSON] [37] and [PERSON] and [PERSON] [40] describe how to transform a discrete BN or a (CL)GBN into a _junction tree_ as a preliminary step before using belief propagation. [PERSON] [41] uses elimination trees for the same purpose in CLGBNs. (A junction tree is an undirected tree whose nodes are the cliques in the moral graph constructed from the BN and their intersections. A clique is the maximal subset of nodes such that every two nodes in the subset are adjacent).  
[PERSON] et al. [42] give the computational complexity of constructing the junction tree from a discrete BN as \(O(Nw+wl^{w}N)\) where \(w\) is the maximum number of nodes in a clique and, as before, \(l\) is the maximum number of values that a variable can take. We take the complexity of belief propagation to be \(O(Nwl^{w}+|\Theta|)\), as stated in [PERSON] and [PERSON] [39] (\"The global propagation is no worse than the initialisation [of the junction tree]\"). This is confirmed by [PERSON] [43] and [PERSON] and [PERSON] [44].  
As for GBNs, we can also perform exact inference through their global distribution because the latter has only \(O\big{(}N^{2}+N\big{)}\) parameters. The computational complexity of this approach is \(O\big{(}N^{3}\big{)}\) because of the cost of composing the global distribution, which we derived in Section 3.2. However, all the operations involved are linear, making it possible to leverage specialised hardware such as GPUs and TPUs to the best effect. [PERSON] and [PERSON] [5] (Section 14.2.1) note that \"inference in linear Gaussian networks is linear in the number of cliques, and at most cubic in the size of the largest clique\" when using junction trees and belief propagation. Therefore, junction trees may be significantly faster for GBNs when \(w\ll N\). However, the correctness and convergence of belief propagation in GBNs require a set of sufficient conditions that have been studied comprehensively by [PERSON] et al. [45]. Using the global distribution directly always produces correct results.  
Approximate inference algorithms use Monte Carlo simulations to sample from the global distribution of **X** through the local distributions and estimate the answer queries by computing the appropriate summary statistics on the particles they generate. Therefore, they mirror the Monte Carlo and Markov chain Monte Carlo approaches in the literature: rejection sampling, importance sampling, and sequential Monte Carlo among others. Two state-of-the-art examples are the _adaptive importance sampling_ (AIS-BN) scheme [46] and the _evidence pre-propagation importance sampling_ (EPIS-BN) [47].