|
So i've been reading a few old statistical mechanics textbooks, and I've been intrigued by all that talk of "phase transitions" on the Ising model. Roughly speaking, a phase transition happens when certain parameters of the model (well, in the ising model, there is only one) exceed a certain value (physicists call this "temperature"), there is "spontaneous magnetization". What this means is that the "correlation length" increases and the whole system "solidifies". This is an interesting idea and I'm pretty certain most Markov Random Fields exhibit similar behavior, but I've never seen a true application of this in statistics. Thoughts? |
|
You don't get spontaneous magnetization in a finite size Ising model and positive temperature. Zero temperature would correspond to Markov field with fully deterministic edge potentials. Since statistics tends to deal with finite models and non-deterministic edge potentials, you don't get the same phase transition behaviors in practice. As to why people don't use Infinite Markov fields for real world inference, consider how differently they behave. For instance, in a finite Markov field, if your edge potentials are not fully deterministic, neither are nodes fully correlated. However, in an infinite Markov field, you could have non-deterministic edge potentials, and still end up with nodes deterministically related to each other (ie, knowing the state of one variable gives you the state of another with 100% certainty). Also, it's more mathematically involved...what does it mean exactly to marginalize out an infinite number of variables? Pedro Domingos' group is working on formalizing inference in infinite Markov fields, at last NIPS he mentioned that it was tricky and they didn't quite have all the details worked out back then One place phase transitions come up in statistics is with inference using Loopy Belief Propagation. The output of belief propagation iterated to fixed point is the same as the marginal of a tree of non-backtracking walks rooted at your node. This tree is infinite, and exhibits phase-transition behavior. "Spontaneous magnetization" in this case means belief propagation can produce confident beliefs (high mean magnetization) even when there's with no local evidence (zero local field), and "spontaneous symmetry breaking" here correspond to small numerical fluctuations ultimately deciding the output of belief propagation algorithm (which is bad!) See Tatikonda's Loopy Belief Propagation and Gibbs Measures As far as "correlation length", it's an idea that comes up in statistics and combinatorics. For certain temperature, correlations decay exponentially in distance in Ising model. For undirected graphical models, "temperature" corresponds to the informativeness of edge potential function. For low enough "informativeness", correlations in a graphical model also decay exponentially and you can accurately approximate the marginal of a given node by considering a fixed size window around your node, independent of the size of the graphical model. Since quickly computing marginals allows you to quickly compute the partition function, and counting various structures on graphs (independent sets, proper colorings) can be expressed as the problem of finding partition function of a properly defined Markov field, this "correlation decay" also characterizes situations when combinatoric counting becomes easy. See this presentation by David Gamarnik for examples Brilliant answer. Firstly, I believe you still get phase transition-ish behavior on finite models, though it becomes discontinuous in the limit, so I'm pretty sure infinite MRFs will lead to some very counter-intuitive behavior, perhaps something best left to the mathematicians to figure out for now. Your second and third points make sense, though I'm sure I'll need to put in the hours to fully grasp the richness of the theory you point at. There are obviously some deep connections in there which I need to look deeper into :) Out of curiosity, is your background in physics?
(Jul 21 '10 at 00:21)
dogy
1
Two relevant books are "Information, Physics and Computation" and "Phase Transitions in Combinatorial Optimization". I was able to find pre-prints of both books online. Especially Ch.13 Bridges in "Information, Physics and Computation" book, it gives examples of things becoming hard after phase transition, ie -- when the system enters glassy phase, accurate MCMC sampling and inference on corresponding graphical model becomes hard.
(Jul 21 '10 at 11:07)
Yaroslav Bulatov
|
|
Mackay's book talks about phase transitions on its chapter on Ising models (and other places as well, check the index at the back). I think one of the reasons you might not have seen any specific application of this is that models with phase transitions are very hard to work with, since they have wildly unpredictable behavior around the phase transition, and inference is harder, etc. I don't know of any specific examples off of the top of my head, but, for example, see Liang and Jordan's paper of type-based sampling for a method of avoiding some difficult phase transitions in graphical models. |
