Wednesday, October 13, 2010

Max-Product Belief Propagation and Constraint Satisfaction Problems

Posted by Danny Tarlow
I'm giving the machine learning tea talk today on the Augmenting DAG (directed acyclic graph) algorithm, which is an algorithm with some interesting history. It seems that there was a line of work starting in the mid seventies in the USSR about relating the discrete maximum a posteriori (MAP) inference problem (in English: find the most likely explanation of variables under some probabilistic model) in pairwise graphical models to: (a) constraint satisfaction problems, and (b) linear program relaxations. The work went unnoticed for 30 years (it was published in Russian), but it was recently discovered and reviewed by Tomas Werner in the 2007 journal paper available here:
T. Werner. A Linear Programming Approach to Max-sum Problem: A Review. IEEE Trans. on Pattern Recognition and Machine Intelligence (PAMI) 29(7), July 2007.

It's interesting, because even today, the best known general algorithms for the MAP inference problem are based on linear program relaxations (though we solve the relaxation using algorithms that are more efficient than general purpose solvers). The most notable modern versions are variants on max-product belief propagation: the tree-reweighted belief propagation (TRW) of Martin Wainwright et al. and the sequential TRW (TRW-S) algorithm of Vladimir Kolmogorov (code here:

The other interesting bit is the connection between MAP and constraint satisfaction. It turns out that the inner loop of the Augmenting DAG algorithm is to run an arc-consistency algorithm. If you find an arc-consistency violation in an appropriately constructed graph, then you have also discovered a step that you can take in the dual of the MAP linear program relaxation that will improve your upper bound.

In practice, the prevailing wisdom is that you're better off using max-product or TRW-S to solve a general problem, but in my opinion, the Augmenting DAG algorithm is a very nice algorithm, and the paper makes a lot of interesting connections to work in other fields. It's definitely worth a read if you're interested in this sort of thing.


Yaroslav said...

I couldn't find Schlesinger's original paper after about 50 mins of searching. I did find a few recent papers (post 2008) citing them. I wonder how many of those authors actually read the original...

Russian Academy of Sciences recently digitized and put online some of it's proceedings going back to 1968. "Kibernetika" and "Automatics and Telemechanics" where Schlesinger published, are not there. However, some related journals are. Some quick searching finds this gem -- "minimization of boolean functions in DNF form, summary of results from 1953 to 1989"

Schlesinger's university ended up on the Ukranian side of the border after USSR split. I found a recent PhD thesis following up on his work, written 100% in Ukranian. This is kind of ironic, given that Ukranian had no machine learning terminology before 1989, so people publishing on ML in Ukranian have to invent words for technical terms. This is done for political reasons.

Danny Tarlow said...

Cool, thanks for the additional info. Have you looked at Werner's page on the subject? I believe he's posted the original papers here:

Yaroslav said...

Wow, you are right, original papers are indeed on that page

B. Tarlow said...

I love this blog. Thanks for sharing such interesting ideas. And it's been a while, so welcome back.

Please visit OHSUBOOKS.COM for all you book needs