

![0_image_0.png](0_image_0.png)

setting λ = 0.9/n, where n is the clique size. Such a λ **allowed us to balance the vertex and clique potentials for** each clique. A majority version was also created by learning W **discriminatively in the training phase.**
All our algorithms were written in Java. We compared these with C++ implementations of the TRW-S2, and graph-cut based expansion algorithms3**[5, 23, 14, 4]. All experiments were performed on a Pentium-IV 3.0**
GHz machine with four processors and 2 GB of RAM.

## 7.1.1 Edge Decomposable Potentials

Figures 4(a) and 4(b) compare the performance of TRW-S vs α**-pass on the two datasets. In Figure 4(a), we** varied λ uniformly in [0.8, 1.2] with increments of 0.05. This range of λ **is of special interest, because it allows** maximal contention between the clique and vertex potentials. For λ **outside this range, the MAP is almost always** a trivial assignment, viz. one which individually assigns each vertex to **its best value, or assigns all vertices to a** single value.

We compare two metrics - (a) the quality of the MAP score, captured by the ratio of the TRW-S MAP score with the α**-pass MAP score, and (b) the runtime required to report that MAP, again as a ratio. Figure 4(a) shows** that while both the approaches report almost similar MAP scores, the TRW-S algorithm is more than 10 times slower in more than 80% of the cases, and is never faster. This is expected because each iteration of TRW-S costs O(n 2), and multiple iterations must be undertaken. In terms of absolute **run times, a single iteration of TRW-S**
took an average of 193ms across all cliques in potts, whereas our algorithm returned the MAP in 27.6 ± 8.**7ms.**
Similar behavior can be observed on CoNLL dataset in Figure 4(b). Though the degradation is not as much as before, mainly because of the smaller average clique size, TRW-S is more than 5 times slower on more than half the cliques.

Figure 4(c) shows the comparison with Graph-cut based expansion. The MAP ratio is even more in favor of α**-pass, while the blowup in running time is of the same order of magnitude as TRW-S. This is surprising**
2http://www.adastral.ucl.ac.uk/~vladkolm/papers/TRW-S.html 3http://vision.middlebury.edu/MRF/