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.

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 0 1 1 1 ...
X_2 0 0 1 1 ...
X_3 0 0 0 1 ...
X_4 0 0 0 0 ...

References and Notes

  1. Factor Graph @ Wikipedia.
  2. DeepDive Docs.

© 2017, Lei Ma| GitHub| Page Source| changelog| Created with Sphinx