Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have a Markov Random Field P(X1,...,Xn) on graph G. Suppose we know P(Xi,Xj) for every edge (i,j). Can we recover P(X1,...,Xn)?

If G is a tree, then there's a formula for joint (product of edge marginals divided by product of node marginals). Is there a nice formula that works for some non-tree graphs?

Edit: this is essentially equivalent to the following problem - given an exponential family, how do you write the joint in terms of mean parameters? There's a closed form solution when sufficient statistics are 2 variable functions defined on (Xi,Xj) pairs where (i,j) are edges in some tree graph, is there a closed form solution for other graphs?

Motivation: given an approximate marginalization method, can you fit parameters of a distribution by maximizing joint likelihood of the data under the model "implied" by this marginalization method?

share|improve this question
    
could you clarify what you mean by 'markov with respect to graph G' ? –  Suresh Venkat Jul 23 '10 at 22:48
add comment

3 Answers

up vote 2 down vote accepted

No, a counter-example can be constructed as follows:

Let G be the complete graph on 3 vertices, where each vertex is a binary random variable. Let the joint distribution for each pair of vertices be independent Bernoulli with probability 1/2.

There are multiple joint distributions which satisfy such edge marginals. For example:

  • Independent Bernoulli for each vertex, with probability 1/2 (complete mutual independence)
  • Each variable could be the XOR (sum modulo 2) of the other two variables (i.e. functionally dependent)
  • The probability of each outcome could be 3/16 if 3 or 1 vertices are 1's, and 1/16 if 2 or 0 are 1's.

So what do you require to be able to uniquely determine the joint distribution? If the graph is decomposable (aka chordal or triangulated), you require the joint distribution for each clique (maximal complete subset) of the graph. Then the joint density is then:

$p(X) = \frac{\prod_{\text{cliques }C} p(X_C)}{\prod_{\text{separators }S} p(X_S)}$

(see Dawid and Lauritzen (1993), Lemma 2.5)

If the graph is not decomposable, then the problem is a bit trickier: the only result I know of is Lauritzen (1996), Lemma 3.14. Basically, given the clique marginal distributions, uniqueness is determined when the sample space is finite, and each clique marginal density is the limit of a sequence of positive densities. I suspect this result could be made stronger in some way, but I am not aware of any efforts to do so.

share|improve this answer
    
Right, distr. over 3 binary variables has 7 degrees of freedom, while fixing edge/node marginals only constrains 6. So I'm looking for a formula of a joint, any joint, that's consistent with given marginals, in terms of those marginals. One choice might be to take the highest entropy distr consistent with marginals, but even for 3 variable distr, formula for such joint in terms of marginal parameters is quite large (mathurl.com/324o4a3) Testing if given set of marginals is consistent can takes exp time, so a formula must not provide an easy way to check that to be short – Yaroslav –  Yaroslav Bulatov Jul 29 '10 at 18:15
2  
Yeah, this stuff gets hard very quickly, even for seemingly trivial problems, hence the development of variational methods. If you're interested in that stuff, the standard reference is the paper by Wainwright and Jordan: nowpublishers.com/product.aspx?product=MAL&doi=2200000001 –  simon Jul 29 '10 at 19:13
add comment

the method for trees should generalize to graphs of bounded treewidth, where the formula might get exponentially long in the treewidth itself. Also, do you care how (algorithmically) complicated the formula is, because it's probably possible to write the general formula as some kind of sum over spanning trees of the graph.

share|improve this answer
    
I can see how it generalizes if you are given distributions over maximal cliques and separators, but how do you go from edge marginals to distributions over maximal cliques? –  Yaroslav Bulatov Jul 24 '10 at 3:41
add comment

I was able to derive some closed form expressions using Mathematica for a binary loop Ising model, but they are unwieldy even for 3-loop and get complicated very fast with increasing loop size.

The basic idea is to use the fact that gradient of log Z gives marginal probabilities, so you invert that mapping algebraically, plug into the original equation of the joint and simplify.

For example, here's probability of 3-loop ising taking configuration {x1,x2,x3} where m1,m2,m3 are probabilities P(X1=X2),P(X2=X3),P(X3=X1) respectively, after simplification (Mathematica's FullSimplify) http://mathurl.com/324o4a3

For uniform potentials, it doesn't get a lot nicer. For instance take Ising model with uniform potentials on a loop of size n, then probability of all spins being +1 can be written in terms of marginal m = P(x1=x2) as

$exp(n j)/Z$ where Z=$\lambda_1^n + \lambda_2^n$, $\lambda_1=e^j+e^{-j}$, $\lambda_2=e^j-e^{-j}$ and j is the solution of

$\frac{\lambda_1^n(e^{2j}-1)+\lambda_2^n(e^{2j}+1)}{2 \lambda_1 \lambda_2}/Z=m$

Mathematica can solve the above equation for various values of n, but the expression becomes large very fast.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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