Inference against the causal direction of a BN is more difficult. Several types of algorithms have been developed for exact inference in networks that have discrete variables or multivariate Gaussian distributions. These involve either reversing the direction of the edges using Bayes's theorem, eliminating variables through summation, performing symbolic manipulation to achieve optimal factoring, or transforming the network into a tree structure of cliques (called a junction tree) and employing a message passing scheme. However, exact inference in an arbitrary
BN is NP-hard, meaning that algorithms do not exist that can perform the inference in polynomial time. Instead, calculation time is exponential in the number ofvariables. Therefore, network size quickly becomes a limiting factor.
For large BNs or those with continuous, non-Gaussian distributions, several different approximation algorithms are available. Stochastic simulation, including importance sampling and Markov Chain Monte Carlo-type algorithms, is the most popular. Other methods include: systematic simplification with the goal of finding a network with an exact solution, and search-based methods that concentrate on the areas ofthe joint probability space containing most ofthe probability mass.
Unfortunately, all of the approximate inference techniques are also NP-hard, and there does not seem to be a single technique that works well for all situations. Therefore, recent research has focused on developing algorithms that can give imprecise solutions quickly and be refined iteratively over time. Another option is to link multiple algorithms that are more or less appropriate for different problems and select or combine them in an automated and intelligent way for specific applications.
Was this article helpful?