Posted by Danny TarlowI'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: 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.