Progress Report

Continuing from my previous post on being able to understand the gist of the culmination of the 3 papers, I think I have some ideas now. Not 100% still. Being reading the papers and so much of mathematics related to it, I thought giving in to write code side by side will be good.

This is so because too much of theory makes me feel handicapped. I mean, writing code along helps me grasp the mathematical formulations nicely. This always doesn’t come along well though as there are many cases where I have no idea how to implement certain section of the paper and I move on by working out the implementation from the author’s code in the hope that I get it after that section is completed. And it works, I do really understand that part. The only thing is that it is not the right way! It is cumbersome.

Moreover, the implemented code written by Sontag lacks proper documentation adding up my worries. Anyways, I am treading forward. Slowly but steadily. I have started writing the 1st paper in python following the C++ code and my understandings of the paper.

The part that now that i have to deal is the message updating method. This forms the crux of the paper.


This goes in the following manner. I have to read the Markov Model from the UAI file and take it in for the MAP query. Then run the update message method until we reach some convergence. For reading the model from the UAI file, I am thankful to Ankur who gladly helped me in writing a smple UAI reader so that I could focus more on the algorithm than on the other nuances. (check it out here: pull 411 ).

For the other part where I wrote a sample MPLP code, check out the other PR: pull 420 . I really wanted to get my mentor’s comments so I pushed this PR. Getting to know how much you are in water sooner or later is always helpful. I intend to grow this PR and write keep on implementing the left part.


Community bonding experience.

Hi all!

The community bonding period is over. I tried to start with understanding those source codes which have implemented the same class of algorithms that I am hoping to implement over the GSoC timeline.

For me, it is Approximate inference of Probabilistic Graphic Models. OpenGM is one of the best C++ template library for discrete factor graph models and distributive operations on these models. It includes state-of-the-art optimization and inference algorithms beyond message passing.

The method that I intend to implement is basically a message passing algorithm. It is called Max-product Linear Programming(MPLP) approx. inference. It was first proposed by Amir Globerson and Tommi Jaakkola in the paper “Fixing max-product: Convergent message passing algorithms for MAP LP-Relaxation” in the year 2007.

I figured it out that this is going to be the 1st phase of my implementation.

The whole of my timeline consists of implementing 2 more subsequent papers which are very much written in hierarchy to this one. So, I have been thinking that if this one is implemented correctly and efficiently, then extending the code for the other 2 papers will be easy.

The other 2 subsequent papers are:

So as far as the community bonding period is concerned, my learning curve was right up. I read all the 3 papers and tried to grasp the concepts of PGM’s. It came out to be not so easy and I had to fall back.

I started understanding PGM’s from the basics by skimming past the introductory videos on PGM from Coursera by Daphne Koller. After going over them, I tried for another read of the papers. I am now able to figure the objective quite well than the last time.

From the last GSoC experience, I am very much sure that understanding is very much important before coding. I just hope I get to understand the gist of the papers and implement them well.