*Posted by Danny Tarlow*

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.

ftp://cmp.felk.cvut.cz/pub/cmp/articles/werner/Werner-PAMI-2007.pdf

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: http://vision.middlebury.edu/MRF/code/).

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.

## 4 comments:

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" http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=intv&paperid=68&option_lang=rus

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.

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:

http://cmp.felk.cvut.cz/cmp/software/maxsum/

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

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

Post a Comment