✳flâneur — a map of the web's best reading

Complexity of Inference in Bayesian Networks – Laboratory for Intelligent Probabilistic Systems – Princeton University Department of Computer Science

lips.cs.princeton.edu · 1,098 words · saved by 1 readers

Developing efficient (i.e. polynomial time) algorithms with guaranteed performance is a central goal in computer science (perhaps the central goal). In machine learning, inference algorithms meeting these requirements are much rarer than we would like: often, an algorithm is either efficient but doesn't perform optimally or vice versa. A number of results from the 1990's demonstrate the challenges of, but also the potential for, efficient Bayesian inference. These results were carried out in the context of Bayesian networks. Briefly, recall that a Bayesian network consists of a directed acyclic graph with a random variable $X_i$ at each vertex. Let $\pi_i$ be the parents of $X_i$. Then the Bayes net defines a distribution over $X = (X_1,\dots,X_n)$ of the form \begin{equation} \Pr[X] = \prod_{i=1}^n \Pr[X_i | \pi_i]. \end{equation} Inference in a Bayes net corresponds to calculating the conditional probability $\Pr[Y | Z = z]$, where $Y,Z \subset \{ X_1,\dots,X_n \}$ are sets of latent and observed variables, respectively. Cooper [1] showed that exact inference in Bayes nets is NP-hard. (Here and in other results mentioned, the size of the problem is given by the total size of the probability tables needed to represent the Bayes net.) The reason the Cooper result holds is essentially that Bayes nets can be used to encode boolean satisfiability (SAT) problems, so solving the generic Bayes net inference problem lets you solve any SAT problem. But SAT is NP-complete, so Bayes net inference must be NP-hard. A number of stronger and even more interesting results followed. First, Dagum and Luby [2] showed that even approximate inference is NP-hard. Specifically, let $\epsilon \in [0,1]$, define $Y$ and $Z$ as before, and define $p := \Pr[Y | Z = z]$. Then an absolute approximation $0 \le V \le 1$ satisfies \begin{equation} p - \epsilon \le V \le p + \epsilon \end{equation} while $0 \le V \le 1$ is a relative approximation if \begin{equation} p/(1+\epsilon) \le V \le p(1 + \epsilon). \end{equation} Dagum and Luby showed that finding either an absolute or relative approximation for $p$ deterministically is NP-hard. Furthermore, finding either type of approximation with high probability using a randomized, polynomial time algorithm is impossible unless NP $\subseteq$ RP (RP is a randomized version of P, where on negative inputs the algorithm must always be correct but can be correct on positive inputs with only probability $\ge 1/2$). There is good reason to believe this is not true because complexity theorists believe P = RP and P $\ne$ NP. Hence, we should not expect to be able to approximate conditional probabilities in arbitrary Bayes nets. Roth [4] strengthened portions Dagum and Luby's result by showing that relative approximation of Bayes nets is #P-complete. Recall that #P is the counting version of NP (instead of,

Complexity of Inference in Bayesian Networks Jonathan Huggins · January 24, 2013 Machine Learning Developing efficient (i.e. polynomial time) algorithms with guaranteed performance is a central goal in computer science (perhaps the central goal). In machine learning, inference algorithms meeting these requirements are much rarer than we would like: often, an algorithm is either efficient but doesn't perform optimally or vice versa. A number of results from the 1990's demonstrate the challenges of, but also the potential for, efficient Bayesian inference. These results were carried out in the c

Explore this link on the map →

related reading