
## 4 Generalized Collective Inference Framework

We now discuss our framework for generalized collective inference. **Recall that we wish to encourage the labelings** of various isolated MRFs to agree on a set of properties. Our generalized collective inference framework consists of three parts:

1. A collection of structured instance-labeling pairs {(xi, yi)}
N
i=1 where each yi**is probabilistically modeled**
using a corresponding Markov Random Field (MRF). Let φ(xi, yi**) be a scoring function for assigning** labeling yi to xi using the MRF. The scoring function decomposes over the parts c **of the MRF as** φ(xi P , y) =
c φc(xi, yc).

2. A set P of properties where each property p ∈ P includes in its domain a subset Dp **of MRFs and maps**
each labeling y of an input x ∈ Dp to a discrete value from its range R′p**. Each property decomposes over**
cliques of the MRF. We discuss decomposable properties in Section 4.1 3. A clique potential Cp({p(xi, yi)}xi∈Dp) for each property p**. This potential is a symmetric function of its**
input. We elaborated on various symmetric potential functions in Section 3. These potentials encourage conformity of properties across labelings of multiple MRFs.
The collective inference task is to label the N **instances so as to maximize the sum of the individual MRF**
specific scores and the clique potentials coupling many MRFs via the property functions. This is given by:

$$\operatorname*{max}_{(\mathbf{y}_{1},...,\mathbf{y}_{N})}\sum_{i=1}^{N}\phi(\mathbf{x}_{i},\mathbf{y}_{i})+\sum_{p\in P}\operatorname{C}_{p}(\{p(\mathbf{x}_{i},\mathbf{y}_{i})\}_{i\in\mathcal{D}_{p}})$$
Cp({p(xi, yi)}i∈Dp**) (6)**
Even for symmetric Cp **and binary labels, Equation 6 is NP-hard to optimize. One well-known hard case is the** Ising model, where each Cp is a Potts potential. Thus we look at an approximate approach based **on message**
passing that we elaborate in Section 5.

## 4.1 Decomposable Properties

A property maps a (x, y) pair to a discrete value in its range. Typically, since y **is exponentially large in the size** of x**, we cannot solve Equation 6 tractably without constructing the value of a property from smaller components**
of y**. We define** *decomposable* properties as those which can be broken over the parts c **of the MRF of labeling** y, just like φ**. Such properties can be folded into the message computation steps at each of the MRFs, as we shall** see in Section 5. We now formally describe decomposable properties:
Definition 4.1. A decomposable property p(x, y) *is composed out of component level properties* p(x, yc, c) defined over parts c of y. p : (x, yc, c) 7→ Rp **∪ {⊥}** where the special symbol ⊥ means that the property is not applicable to (x, yc, c). p(x, y) *is composed as:*

$$p(\mathbf{x},\mathbf{y})\triangleq{\left\{\begin{array}{l l}{\varnothing}&{{\mathit{i f}}\ \ \forall c:p(\mathbf{x},\mathbf{y}_{c},c)=\ \ \bot}\\ {v}&{{\mathit{i f}}\ \ \forall c:p(\mathbf{x},\mathbf{y}_{c},c)\in\{v,\bot\}}\\ {\bot}&{{\mathit{o t h e r w i s e.}}}\end{array}\right.}$$
$$(6)$$
$$\left(7\right)$$

The first case occurs when the property does not fire over any of the parts. The last case occurs when y has more than one parts where the property has a valid value but the values are different. The new range R′p now consists of Rp and the two special symbols ⊥ and ∅.

We show that even with decomposable properties we can express many useful types of regularities in labeling multiple MRFs arising in applications like domain adaptation.

Example 1 **We start with an example from the simple collective inference task of [22, 6, 9] of favoring the same** label for repeated words. Let x be a sentence and y be a labeling of all the tokens of x**. Consider a property**