of labels, and n **is the clique size. This algorithm is exact for max-like potentials, and is** 13 15 **-approximate for Potts**
potentials. We show that this algorithm can be generalized to an O(m2n log n**) algorithm while improving the**
approximation bound to 89
. For majority-like potentials, we present an LP-based exact algorithm with polynomial but expensive runtime. We present an alternative approximate algorithm based on Lagrangian relaxation that is two orders of magnitude faster and and provides close to optimal **quality solutions in practice.**
Finally, we show that our suite of algorithms can be plugged into the properties-based framework to achieve a highly expressive way for capturing associativity. We illustrate this **on a bibliographic information task where** we use properties to deploy our collective framework over unseen bibliographic domains, and achieve significant error reductions.

## Outline

In Section 2, we give some real-life scenarios where collective inference can be used to exploit associativity amongst isolated MRF instances. We model associativity using symmetric potentials. In Section 3, we describe three families of symmetric potentials, that subsume the Potts and linear majority **potentials. Section 4 discusses our**
properties-based collective inference framework in formal detail. **Our framework ensures tractability of inference**
as long as the properties are *decomposable***, a notion that we cover in Section 4.1. In Section 5, we discuss the** cluster message passing algorithm to compute the MAP in our framework. Section 5.1 presents our approach for exactly computing property-aware messages from an MRF instance to a clique, and Section 5.1.2 contains practical approximations of this exact computation. In Section 5.2, we show that computing the reverse message - from a clique to a MRF instance, is the same as the *clique inference problem***. Then in Section 6, we present** algorithms for solving the clique inference problem under a variety of **symmetric clique potentials. The two**
key algorithms presented are the α**-pass algorithm and a Lagrangian-relaxation based algorithm for** majority potentials, in Sections 6.1 and 6.3.3 respectively. Section 7 contains experimental results of three types - (a) Establishing that our properties based framework leads to significant gains in a domain adaptation task. (b) Our clique inference algorithms are better than applicable alternatives and (c) The cluster message passing framework is a better way of doing inference. Finally, Section 8 contains conclusions and a discussion of future work.

## 2 Applications Of Collective Inference

We review a few practical applications of collective inference in real-life tasks. Both the tasks benefit when we introduce associative dependencies between labelings of isolated instances.

## 2.1 Information Extraction

Recall Figure 1(d) for the task of named-entity extraction. Let the potential function for an edge between adjacent word positions j − 1 and j in document i be φij (y, y′**) and for non-adjacent positions that share a word**
w be fw(y, y′). The goal during inference is to find a labeling y where yij is the label of word xij **in position** j of doc i**, so as to maximize:**

$$\sum_{i,j}\phi_{i j}(y_{i j},y_{i(j-1)})+\sum_{w}\sum_{\mathbf{x}_{i j}=x_{i^{\prime}j^{\prime}}=w}f_{w}(y_{i j},y_{i^{\prime}j^{\prime}})$$
′ **) (1)**
The above inference problem gets intractable very soon with the addition of non-adjacent edges beyond the highly tractable collection of chain models of classical IE. Consequently, all prior work on collective extraction for IE relied on generic approximation techniques including belief propagation [22, 6] , Gibbs sampling [9] or stacking [15].

We present a different view of the above inference problem using cardinality-based clique potential functions Cw**() defined over label subsets** y w of positions where word w **occurs. We rewrite the second term in Equation 1**
as

$$\frac{1}{2}\sum_{w}(\sum_{y,y^{\prime}}f_{w}(y,y^{\prime})n_{y}({\bf y}^{w})n_{y^{\prime}}({\bf y}^{w})-\sum_{y}n_{y}({\bf y}^{w})f_{w}(y,y))$$ $$=\sum_{w}{\rm C}_{w}(n_{1}({\bf y}^{w}),\ldots n_{m}({\bf y}^{w}))$$
$$\left(1\right)$$
