Homework 2 (Due: March 10, 2009)

Team : 2 members max.

The aim of this homework is to explore various non-junction tree based algorithms for solving MAP inference queries. As a first step, you will implement the alpha expansion algorithm for multi-arity labeling. The structure and potential of the graphical model will be provided as a file. Examples of the format are shown below. Each score denotes the log of potential. Input Format:
  1. The model is given in the form of a file containing the following fields: 
    [number of nodes] n
[number of edges] m
[node 1] [no of labels for node 1] [node potential values for each label]
  .
  .

[node 1] [node 2] [edge potential values for each pair of label for the nodes] (2-d matrix is converted to 1-d in row major way)
  .
  .
  .

Ex. :- An undirected graphical model with 3 nodes, 2 edges and 2 labels for each node.
3
2
0 2 0.1 1
1 2 1 0.9
2 2 1 0.7
0 1 0.8 0.2 0.2 0.8
1 2 0.8 0.2 0.2 0.8

API

API for graphical model is provided here. This jar contains some basic classes which can be used to represent graphical models. In this jar, implementation is provided only for undirected graphs. Automatic model loading is implemented for PairwiseGraphicalModel which is an undirected model with potential specified on the edges only. Some of the documentation of the classes is availabe here. Sample usage and other details will be updated/mailed soon.

Other necessary JARs

trove.jar with documentation.