Input: ψ, W, α**,maxIters,tolerance** Output**: approximately best assignment** vˆ
γ ← 0; iter ← 0; ˆz ← **Assignment with all vertices assigned** α; while iter < *maxIters* do Compute L(γ) (Equation 30), let z **be the solution;**
if F(z) > F(ˆz) **then**
ˆz ← z; end
(v, ∆) ← **Worst violator and violation (Equations 34 and 35);**
if ∆ < *tolerance* **then**
We are done, L∗ = L(γ);
break *break*;
else if *using subgradient optimization* **then**
Compute the new direction d iter **and step-size** η iter; Modify γ **using Equation 36;**
else Modify γv **using golden search or conservative descent;**
end iter ← **iter+1;**
end Construct value assignment vˆ **from** zˆ;
return vˆAlgorithm 2**: Compute** L∗
Second, in Section 7.2 we demonstrate the application of the generalized collective framework on domain adaptation and show that using a good set of properties can bring down the test error significantly. Finally, in Section 7.3 we show that message passing on the cluster graph is a more effective way to perform inference compared to alternatives such as ordinary belief propagation, and enjoys better convergence speeds.

## 7.1 Clique Inference Experiments

In this section, we compare our algorithms against sequential tree **re-weighted message passing (TRW-S) and** graph-cut based inference for clique potentials that are decomposable over clique edges; and with ICM when the clique potentials are not edge decomposable. We compare them on running time and quality of the MAP. Our experiments were performed on both synthetic and real data.

Synthetic Dataset: We generated cliques with 100 vertices and R **= 24 values by choosing vertex potentials at**
random from [0, **2] for all values. A Potts version (**potts) was created by gradually varying λ **, and generating** 25 cliques for every value of λ**. We also created analogous** entropy, makespan and makespan2 **versions of the**
dataset by choosing entropy, linear makespan (λ maxv nv) and square makespan (λ maxv n 2v
) clique potentials respectively.

For majority potentials we generated two kinds of datasets (parameterized by λ**): (a)** maj-dense **obtained**
by generating a random symmetric W for each clique, where Wvv = λ was the same for all v and Wvv′ ∈
[0, 2λ] (v 6= v′**), and (b)** maj-sparse from symmetric W with Wij ∈ [0, 2λ] for all i, j**, roughly 70% of whose**
entries were zeroed.

Of these, only potts **is decomposable over clique edges.**
CoNLL Dataset: The CoNLL 2003 dataset1**is a popular choice for demonstrating the benefit of collective**
labeling in named entity recognition tasks. We used the BIOU encoding **of the entities, that resulted in 20 labels.** We took a subset of 1460 records from the test set of CoNLL, and **selected all 233 cliques of size 10 and above.** The median and largest clique sizes were 16 and 259 respectively. The **vertex potentials of the cliques were set**
by a sequential Conditional Random Field trained on a separate training set. We created a Potts version by 1http://cnts.uia.ac.be/conll2003/ner/