better than its competitors across dense as well as sparse majority potentials.

The results on CoNLL dataset, whose W **matrix is 85% sparse, are displayed in Figure 5(c). ICM, modified**
α**-pass and LR return the true MAP in 87%, 95% and 99% of the cliques respectively, with the worst case MAP** ratio of LR being 0.97 as opposed to 0.94 and 0.74 for modified α**-pass and ICM respectively.**
Figure 5(d) displays runtime ratios on all CoNLL cliques for all three inexact algorithms. ICM and modified α**-pass are roughly 100-10000 times faster than the exact algorithm, while LR is roughly twice as expensive as** ICM and modified α-pass. Thus, for practical majority potentials, LR and modified α**-pass seem to quickly** provide highly accurate solutions.

From now on, while doing the top-level message passing on the cluster graph, we shall use the α**-pass and**
Lagrangian-relaxation based algorithms for computing messages from a clique, in the presence of Potts and majority **potentials respectively.**

## 7.2 Domain Adaptation

We now move on the generalized collective inference framework, and **show that a good set of properties can help** us in domain adaptation. We focus on the bibliographic task, where the aim is to adapt a sequential model across widely varying publications pages of authors. Our dataset consists **of 433 bibliographic entries from the webpages of 31 authors, hand-labeled with 14 labels such as Title, Author, Venue, Location and Year. Bibliographic**
entries across different authors differ in various aspects like label-ordering, missing labels, punctuation, HTML formatting and bibliographic style.

A fraction of 31 domains were used to train a baseline sequential model. The model was trained with the LARank algorithm of [3], using the BCE encoding for the labels. We used standard extraction features in a window around each token, along with label transition features [20].

For our collective framework, we use the following decomposable properties:

| p1 (x, y)   | =   | First non-Other label in y             |
|-------------|-----|----------------------------------------|
| p2 (x, y)   | =   | Token before the Title segment in y    |
| p3 (x, y)   | =   | First non-Other label after Title in y |
| p4 (x, y)   | =   | First non-Other label after Venue in y |

Inside a domain, any one of the above properties will predominantly favor one value, e.g. p3 **might favor the value**
'Author' in one domain, and 'Date' in another. Thus these properties encourage consistent labeling around the Title and Venue segments. We use Potts potential for each property, with λ **= 1.**
Some of these properties, e.g. p3**, operate on non-adjacent labels, and thus are not Markovian. This can be**
easily rectified by making 'Other' an extension of its predecessor label, e.g. an 'Other' segment after 'Title' can be relabeled as 'After-Title'.

The performance results of the collective model with the above properties versus the baseline model are presented in Table 3. For the test domains, we report token-F1 of **the important labels - Title, Author and**
Venue. The accuracies are averaged over five trials. The collective **model leads to upto 25% reduction in the test** error for Venue and Title, labels for which we had defined related properties. The gain is statistically significant
(p < 0.05). The improvement is more prominent when only a few domains are **available for training. Figure 6** shows the error reduction on individual test domains for one particular split when five domains were used for training and 26 for testing. The errors are computed from the combined token F1 scores of Title, Venue and Author. For some domains the errors are reduced by more than 50%. Collective inference increases errors in only two domains.

Finally, we mention that for this task, applying the classical collective **inference setup with cliques over**
repeated occurrences of words leads to very minor gains. In this context, the generalized collective inference framework is indeed a much more accurate mechanism for joint labeling.

## 7.3 Collective Labeling Of Repeated Words

We now establish that even for simple collective inference setups without any multi-clique properties, message passing on the cluster graph (abbreviated as CI) is a better option. We consider information extraction over