Wednesday, May 19, 2010

Notes on Approximation Algorithms

Posted by Danny Tarlow
I'm enjoying reading notes from Shuchi Chawla's course at the University of Wisconsin, Madison on approximation algorithms for NP-hard optimization problems. There is a pdf available with scribe notes from all the courses, which makes for a very nice 170 page handbook:
http://pages.cs.wisc.edu/~shuchi/courses/880-S07/scribe-notes/all-in-one.pdf

Wednesday, May 5, 2010

Looking for Testers: Max-Product Belief Propagation Code

Posted by Danny Tarlow
I'm preparing to release some code associated with my upcoming paper on max-product belief propagation with high order potentials:
Tarlow, D., Givoni, I., & Zemel, R. (2010). HOP-MAP: Efficient message passing with high order potentials. In Artificial Intelligence and Statistics (AISTATS).
http://www.cs.toronto.edu/~dtarlow/TarlowGivoniZemel_AISTATS2010.pdf

If you're interested in trying to compile and play with a small example that I've put together, please let me know in the comments or by email: dtarlow cs toronto edu (but make sure to leave a way for me to contact you!)

The code is in C++. I have Makefiles that I can confirm work on my Apple machines (OS 10.5 with gcc 4.0.1) and the Toronto Ubuntu-based cluster computers (gcc 4.2.4). It'd be great to get people with different setups as well, though I won't be a ton of help with compilation specifics. I only ask that if you want to be a tester, you have some experience compiling C++ and a few hours sometime in the next few days to devote to this.

The code is written to only do max-product (max-sum) belief propagation, so it should be a bit simpler than existing alternatives. It should also have more functionality related to high order factors than any other existing library (this is the point of the paper). I should say that the library is similar in flavor to several other excellent libraries that are more mature: The first part I am releasing is a stripped down version of the code I use for my research. As I learn more about maintaining a reasonably-sized public code base, I will add in more pieces. Unless you are looking just to learn, or if you are specifically looking for simple high-order max-product code, you might be happier with the alternatives. At some point, I would like to add some of my factors to the other projects.

Having said that, by using my code, you'll be the first to get my implementations of my research, and I will provide a limited amount of support, especially to the earliest testers.