3
$\begingroup$

This question is about graphical modeling of joint probability functions, Markovian property and Markov random fields.

Suppose we have an undirected graph G where each node represents a random variable and an edge between two nodes says that there is a probabilistic relation in between them. I want to model the joint probability of these variables and to simplify things I assume that the graph/nodes have Markovian property. This should let me write the joint as a factorization over ``local" clique potentials.

In C. Bishop's Pattern Recog. and Machine Learning book, Chapter 8, pp. 386 (pdf of the chapter), it is said that the joint distribution is written as a product of potential functions over the maximal cliques of the graph:

$p(x) = \frac{1}{Z} \prod_C \psi_C(x_C)$ (eq. 8.39)

However, in Stan Li's book on MRFs, he says this factorization is done over all possible cliques of the graph: see equation (1.26) and (1.27) in http://www.nlpr.ia.ac.cn/users/szli/MRF_Book/Chapter_1/node12.html#SECTION00323000000000000000.

Stan Li's explanation makes more sense to me. Which one do you think is correct? Or, might they be just different wording of the same fact? Any help would be appreciated.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Same fact, since you can absorb potential over each non-maximal clique into potential of corresponding maximal clique $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 26, 2010 at 2:50

1 Answer 1

Reset to default
2
$\begingroup$

As I read it, Bishop is asserting that for each maximal clique $C$ we may define the potential as $\psi_C(x_C) = \prod_S U_S(x_S)$ where $S$ denotes cliques which are subsets of $C$ (and $U$ is the energy, as in the link from Li). This is how I interpret "[if $C$] is a maximum clique, and we define an arbitrary function over this clique, then including another factor defined over a subset of these variables would be redundant." It is potentially confusing because, as typical in statistics, the symbol $\psi$ is overloaded to allow different functional form for any clique. In any case, Bishop defines each maximal clique potential in terms of a factorization over all subset cliques. Substitution gives back the other definition.

Improve this answer
$\endgroup$
4
  • $\begingroup$ for god's sake what are $x_c$ or $x_s$?? I'm stuck at understanding what they refer to!! $\endgroup$
    – Jack Twain
    Commented Apr 18, 2014 at 10:01
  • $\begingroup$ @AlexTwain c and s refer to cliques of the graph. I think $x_c$ represents the value that clique c takes. $\endgroup$
    – eakbas
    Commented Apr 18, 2014 at 14:39
  • $\begingroup$ @eakbas but how can the clique take a value? As I know every node/vertex has a corresponding random value. Then what does the value of a clique mean? what does it represent? $\endgroup$
    – Jack Twain
    Commented Apr 18, 2014 at 21:17
  • $\begingroup$ @eakbas I added this question here mathoverflow.net/questions/163730/clique-factorization $\endgroup$
    – Jack Twain
    Commented Apr 18, 2014 at 21:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .