The log likelihood of the agreement set is then:

$$\operatorname{LL}(\mathcal{Y}_{\mathcal{A}},\mathbf{W})\triangleq\log\operatorname*{Pr}(\mathcal{Y}_{\mathcal{A}})=\log\sum_{\mathbf{Y}\in\mathcal{Y}_{\mathcal{A}}}\prod_{s,i\in s}\operatorname{P}(\mathbf{Y}_{s i}|\mathbf{X}_{s i},\mathbf{w}_{s})$$
P(Ysi|Xsi, ws) (5)
In the rest of the paper we use the short form (*s, i*) to denote the instance i in source s. Our goal now is to jointly train w1*, . . . ,* wS so as to maximize a weighted combination of the likelihoods of the labeled and agreement sets:

$$\left({\bar{5}}\right)$$
$$\operatorname*{max}_{\mathbf{w}_{1},\dots,\mathbf{w}_{S}}\sum_{s}\mathrm{LL}(L_{s},\mathbf{w}_{s})+\lambda\mathrm{LL}({\mathcal{Y}}_{\mathcal{A}},\mathbf{W})$$
$$\left(7\right)$$
* [16] A. A. K.  

LL(Ls, ws) + λLL(YA,W) (6)

## 2.1 Computing Ll(Ya,W)

Using Equations 1, 3, and 5, we rewrite LL(YA,W) as

$$\operatorname{LL}(\mathcal{Y}_{\mathcal{A}},\mathbf{W})=\log\sum_{\mathbf{Y}\in\mathcal{Y}_{\mathcal{A}}}\exp(\sum_{s,i}\mathbf{w}_{s}\mathbf{f}_{s}(\mathbf{Y}_{s i},\mathbf{w}_{s}))-\sum_{s,i}\log Z(\mathbf{X}_{s i},\mathbf{w}_{s})$$

The second part in this equation is the sum of the log partition function over individual instances which can be computed efficiently as long as the base models are tractable.

The first part is equal to the log partition function of a fused graphical model GA constructed as follows:
Initially, each instance (*s, i*) creates a graph Gsi corresponding to its model Ps(.). For text tasks, this would typically be a chain model with a node for each token position. Next, for each clique C ∈ A, and for each pair of triples (*s, i, r*),(s 0, i0, r0) ∈ C, we collapse the nodes of r in Gsi with the corresponding nodes of r 0in Gs 0i 0 . In Figure 1(b) we show an example of such a fused graph created from the three instances of Figure 1(a) with four cliques in their agreement set.

Let K be the number of nodes in the final fused graph and z1*, . . . , z*K denote the node variables. Every node j in the initial graph Gsi is now mapped to some final node k ∈ 1, · · · , K, and we denote this mapping by π(*s, i, j*). The log-potential for a component c in the fused graph is simply an aggregate of the log-potentials of the members c 0that collapsed onto it.

$$\theta_{\mathbf{c}}(\mathbf{z_{c}})\triangleq\sum_{(s,i,\mathbf{c^{\prime}}):\pi(s,i,\mathbf{c^{\prime}})=\mathbf{c}}\mathbf{w}_{s}\mathbf{f}_{s}(\mathbf{z_{c^{\prime}}},\mathbf{X}_{s i},\mathbf{c^{\prime}})$$
0) (8)
where we extend π to operate on node-sets as well. The above θ parameters now define a distribution over the fused variables z1*, . . . , z*K as follows:

$$({\boldsymbol{\delta}})$$
$$\mathrm{P}_{\mathcal{A}}(\mathbf{z}|\theta)={\frac{1}{Z_{\mathcal{A}}(\theta)}}\exp(\sum_{\mathbf{c}}\theta_{\mathbf{c}}(\mathbf{z_{c}}))$$
$$(9)$$
θc(zc)) (9)
It is easy to see that the log partition function of this distribution is the same as the first term of Equation 7, so we can work with GA instead. If the set of cliques in A is such that the fused graph GA has a small tree width, we can compute the log partition function log ZA(θ) efficiently. In other cases, we need to approximate the term in various ways. We discuss several such approximations in Section 2.3.

## 2.2 Training Algorithm

The overall training objective of Equation 6 is not necessarily concave in ws because of the agreement term with sums within a log. As in [17, 11] it is easy to derive a variational approximation with extra variables to be solved using an EM algorithm. EM will give a local optima if the marginals of the PA distribution can be computed exactly. Since this cannot be guaranteed for general fused graphs, we also explore the simpler approach of gradient ascent. In Section 5 we show that gradient ascent achieves better accuracy than EM while being faster. The gradient of LL(YA,W) is

$$\nabla\mathrm{LL}(\mathbf{Y}_{\mathcal{A}},\mathbf{W})=\sum_{s,i,c}\sum_{\mathbf{y}_{c}}(\mu_{\mathcal{A},\pi(s,i,c)}(\mathbf{y}_{c})-\mu_{s,c}(\mathbf{y}_{c}|\mathbf{X}_{s i}))\mathbf{f}_{s}(\mathbf{X}_{s i},\mathbf{y}_{c},c)$$

where we use the notation µs,c, µA,c0 to denote the marginal probability at c of Ps and c 0 of PA respectively. Note that the E-step of EM requires the computation of the same kind of marginal variables. These are computed using the same inference algorithms as used to compute the log partition function and we discuss the various options next.