Factor Graph

In the propagation of information, we are usually dealing with such relations that some system (factor) $ f$ is related to some inputs (variable) $ x$.

Factor graph builds such networks of relations. In such a graph, we use boxes to represent factors, and circles to represent variables.

From Factor Graph @ Wikipedia

From Factor Graph @ Wikipedia

Suppose we need to find out the probability of factor $ f_4$, we have to take in the two variables $ X_2$ and $ X_3$.

One important question is that we can actually calculate the probability of a specific configuration of the variables, which is

$$ P \propto f_1(X_1) + f_2(X_1,X_2) + f_3(X_1,X_2) + f_4(X_2,X_3). $$

In general, we can assign weights $ w_i$ to each factors $ f_i$, so that the probability of each set of variables is

$$ P(X_1,X_2,X_3,X_4) \propto w_1 f_1(X_1) + w_2 f_2(X_1,X_2) + w_3 f_3(X_1,X_2) + w_4 f_4(X_2,X_3). $$

The normalization is the partition function, i.e., the summation of all the possible combinations of variables,

$$ Z = \sum_{\{X_1,X_2,X_3,X_4\}} P(X_1,X_2,X_3,X_4). $$

As an example, we consider $ X_i$ is 0 or 1. The combinations are (partially) listed below.

List of Possible Configurations of Variables

$ X_1$0111
$ X_2$0011
$ X_3$0001
$ X_4$0000

References and Notes

  1. Factor Graph @ Wikipedia
  2. DeepDive Docs

Planted: by ;

Lei Ma (2020). 'Factor Graph', Intelligence, 10 April. Available at: https://intelligence.leima.is/toolbox/random-thoughts/factor-graph/.