3
$\begingroup$

I am just getting started on understanding Factor Graphs, by going through the excellent guide Factor Graph For Robot Perception by Dallaert and Kaess

While I am familiar with the SLAM problem, and have a fair understanding of the probability and statistics involved, I fail to understand why a Factor Graph is a better representation compared to a Bayes net.

To me, they seem to be the same thing. In the Bayes Net, you visualize functions (factors) by incoming and outgoing edges, while in a factor graph, you represent it by a bridge (node) between nodes. However, the underlying principle is the same, i.e. MAP and MLE, yielding the same computation.

Thus, fundamentally, what is the difference between a Bayes Net and a Factor Graph. (I understand what they are, but cannot really seem to point out the difference between them). And consequently, in what way does a Bayes Net fail to capture the SLAM problem, that a Factor Graph can?

Any explanation with examples would be appreciated!

$\endgroup$
2
  • 1
    $\begingroup$ I think this is a good question, but I had to edit the title to make it not opinion based. Questions that ask about the pros/cons or advantages/disadvantages are effectively opinion polls, which are discouraged on stack exchange. We prefer practical, answerable questions based on actual problems that you face. $\endgroup$
    – Ben
    Jan 31, 2021 at 14:51
  • $\begingroup$ Let me reiterate that I think asking the difference between a Bayes Net and a Factor Graph is valid and shout stay open. $\endgroup$
    – Ben
    Jan 31, 2021 at 14:52

1 Answer 1

1
$\begingroup$

I realize this answer is probably coming too late, but I think it is important, so I will try to give some exposition here.

At a high level, both Bayesian networks and factor graphs can be used to graphically represent probability distributions. This is the application we encounter in robot perception.

First, note that any distribution represented by a Bayesian network admits an equivalent representation as a factor graph. To see this, suppose we have a Bayesian network $\mathcal{N} \triangleq \{\mathcal{V}, \vec{\mathcal{E}}\}$ with variable nodes $\mathcal{V} \triangleq \{v_1, \ldots, v_N\}$ (the domain of each variable $v_i$ does not affect the equivalence) and directed edges $\vec{\mathcal{E}}$. Then the probability distribution $p(\mathcal{V})$ modeled by the network $\mathcal{N}$ is: \begin{equation} p(\mathcal{V}) = \prod_{i=1}^N p(v_i \mid \mathrm{Pa}(v_i)), \end{equation} where $\mathrm{Pa}(v_i)$ denotes the set of parents of the variable node $v_i$ (i.e. the set of nodes with outgoing edges in $\vec{\mathcal{E}}$ that are incident to $v_i$). Recall that a factor graph $\mathcal{G} = \{\mathcal{V}, \mathcal{F}, \mathcal{E}\}$ with variable nodes $\mathcal{V}$ (as before), factor nodes $\mathcal{F} \triangleq \{f_1, \ldots, f_M\}$ and undirected edges $\mathcal{E}$ encodes a factorization of a function $f$ as: \begin{equation} f(\mathcal{V}) = \prod_{j=1}^M f_j(\mathcal{V}_j), \quad \mathcal{V}_j \triangleq \mathrm{Neigh}(f_j) \subseteq \mathcal{V}, \end{equation} where $\mathrm{Neigh}(f_j)$ denotes the set of neighbors of $f_j$ (i.e. the variable nodes adjacent to $f_j$ in $\mathcal{G}$). As an aside, note that factor graph representations of functions are not unique; multiple distinct factor graphs can encode the same function. To see this, simply consider the trivial factor graph containing a single factor connected to all variables; this is always a valid factorization, but isn't necessarily the only valid factorization. We like to use specifically factor graph representations that explicate the conditional independence structure of $f$.

From this, we can see that a factor graph representation of $p(\mathcal{V})$ from the Bayesian network above can be immediately obtained as: \begin{equation} p(\mathcal{V}) = \prod_{i=1}^N f_i(v_i, \mathrm{Pa}(v_i)), \end{equation} where \begin{equation} f_i(v_i, \mathrm{Pa}(v_i)) \triangleq p(v_i \mid \mathrm{Pa}(v_i)). \end{equation} Going the other direction: we can obtain a Bayesian network from a factor graph representation of a probability distribution by eliminating variables in a particular order (as you may have encountered in the reference text, this is a key procedure for the tree construction steps that show up in iSAM2).

I suspect the fact that we can represent the same probabilistic model in different ways may be part of the confusion. At the end of the day, mathematical operations (like summation or maximization) can be performed on variables in the model whether you think about it as a factor graph or a Bayesian network. From a practical standpoint, however, it may be simpler to implement these operations with one representation than the other. In robot perception, Bayes nets most commonly appear as a tool for writing down probabilistic models. This is because they allow us to explicitly encode the direction of dependence relations (e.g. the probability of a measurement given the robot's state) that appear in the measurement models we specify.

When we want to perform computations with these models (like MAP inference or marginalization), we often encode them as factor graphs. One reason for this is that conditional independence relations are very easy to determine in factor graphs. Specifically, if we have a factor graph representation of $p(\mathcal{V})$ in which there exists a set $\mathcal{S} \subset \mathcal{V}$ of variable nodes such that all paths from one node $v_i \in \mathcal{V}\setminus\mathcal{S}$ to another node $v_j \in \mathcal{V}\setminus\mathcal{S}$ must go through some variable in $\mathcal{S}$, then we know immediately (it's a good exercise to verify this) that $v_i$ and $v_j$ are independent given $\mathcal{S}$. Formally: $p(v_i, v_j \mid \mathcal{S}) = p(v_i \mid \mathcal{S})p(v_j \mid \mathcal{S})$. It's possible to determine these sorts of conditional independence relations from a Bayesian network, too, but the procedure is a little bit more involved (see d-separation).

It turns out that since the models that show up in SLAM often admit representations as sparse factor graphs, the independence relations explicated by the factor graph structure can be quite useful in the construction of (approximate) inference algorithms (particularly since in robot perception and navigation we are often very concerned with computational efficiency). Practical applications of this property include "smart factors" [Carlone et al. 2014] and (my own work) discrete-continuous smoothing and mapping (DC-SAM) [Doherty et al. 2022].

There is much more that could be said on this topic, but hopefully this helps contextualize some of the ideas in Frank Dellaert and Michael Kaess' book :)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.