I don't understand why converting a Bayesian network into a factor graph is good for Bayesian inference?
My questions are:
Any concrete examples will be appreciated!
I will try to answer my own question.
A very important notion of factor graph is message, which can be understood as A tells something about B, if the message is passed from A to B.
In the probabilistic model context, message from factor $f$ to variable $x$ can be denoted as $\mu_{f \to x}$, which can be understood as $f$ knows something(probability distribution in this case) and tells it to $x$.
In the "factor" context, to know the probability distribution of some variable, one needs to have all the messages ready from its neighboring factors and then summarize all the messages to derive the distribution.
For example, in the following graph, the edges, $x_i$, are variables and nodes, $f_i$, are factors connected by edges.
To know $P(x_4)$, we need to know the $\mu_{f_3 \to x_4}$ and $\mu_{f_4 \to x_4}$ and summarize them together.
Then how to know these two messages? For example, $\mu_{f_4 \to x_4}$. It can be seen as the message after summarizing two messages, $\mu_{x_5 \to f_4}$ and $\mu_{x_6 \to f_4}$. And $\mu_{x_6 \to f_4}$ is essentially $\mu_{f_6 \to x_6}$, which can be calculated from some other messages.
This is the recursive structure of messages, messages can be defined by messages.
Recursion is a good thing, one for better understanding, one for easier implementation of computer program.
The benefit of factors are:
A Bayesian Network, by definition, is a collection of random variables $\{X_n: P \rightarrow \mathbb{R}\}$ and a graph $G$ such that the probability function $P(X_1,...,X_n)$ factors as conditional probabilities in a way determined by $G$. See http://en.wikipedia.org/wiki/Factor_graph.
Most importantly the factors in the Bayesian Network are of the form $P(X_i| X_{j_1},..,X_{j_n})$.
A factor graph, even though it is more general, is the same in that it is a graphical way to keep information about the factorization of $P(X_1,...,X_n)$ or any other function.
The difference is that when a Bayesian network is converted to a factor graph the factors in the factor graph are grouped. For example, one factor in the factor graph may be $P(X_i| X_{j_1},..,X_{j_n})P(X_{j_n})P(X_{j_1}) = P(X_i| X_{j_2},..,X_{j_{n-1}})$. The original Bayesian network stored this as three factors but the factor graph stores it only as one factor. In general, the factor graph of a Bayesian network keeps tracks of fewer factorizations than the original Bayesian network did.
A factor graph is just yet another representation of a Bayesian model. If you had an exact algorithm for inference in a particular Bayesian network, and another exact algorithm for inference in the corresponding factor graph, the two results would be the same. Factor graphs just happen to be a useful representation for deriving efficient (exact and approximate) inference algorithms by exploiting conditional independence between variables in the model, thereby mitigating the curse of dimensionality.
To give an analogy: the Fourier transform contains the exact same information as the time representation of a signal, yet some tasks are easier accomplished in the frequency domain, and some are easier accomplished in the time domain. In the same sense, a factor graph is just a reformulation of the same information (the probabilistic model), which is helpful for deriving clever algorithms but doesn't really "add" anything.
To be more specific, assume that you are interested in deriving the marginal $p(x_i)$ of some quantity in a model, which requires integrating over all other variables:
$$ p(x_i) = \int p(x_1, x_2, \ldots, x_i,\ldots, x_N) dx_1x_2\ldots x_{i-1}x_{i+1}\ldots x_N $$
In a high-dimensional model, this is an integration over a high-dimensional space, which is very hard to calculate. (This marginalization/integration problem is what makes inference in high dimensions hard/intractable. One approach is to find clever ways to evaluate this integral efficiently, which is what Markov chain Monte Carlo (MCMC) methods do. Those are known to suffer from notoriously long computation times.)
Without going into too many details, a factor graph encodes the fact that many of these variables are conditionally independent of one another. This enables replacing the above, high-dimensional integration by a series of integration problems of much lower dimension, namely, the computations of the different messages. By exploiting the structure of the problem in this way, inference becomes feasible. This is the core benefit of formulating inference in terms of factor graphs.
