Collective Classification for Text Classification - Text Mining: Classification, Clustering, and Applications - page 58

y j m i→j ( y j )=1and y i b i ( y i ) = 1. The algorithm proceeds by making
each Y i ∈Y

N i ∩Y

until the
messages stabilize (Eq. (3.1)). After the messages stabilize, we can calculate
the marginal probability of assigning Y i with label y i by computing b i ( y i )
using Eq. (3.2). The algorithm is described more precisely in Algorithm 3 .
LBP has been shown to be an instance of a variational method. Let b i ( y i )
denote the marginal probability associated with assigning unobserved variable
Y i the value y i and let b ij ( y i ,y j ) denote the marginal probability associated
with labeling the edge ( Y i ,Y j )withvalues( y i ,y j ). Then (44) showed that the
following choice of trial distribution,

communicate messages with its neighbors in

b ( y )= ( Y i ,Y j ) ∈E b ij ( y i ,y j )

Y i ∈Y

b i ( y i ) |Y∩N i |− 1

and subsequently minimizing the Kullback-Leibler divergence between the
trial distribution from the distribution associated with a pairwise MRF gives
us the LBP message passing algorithm with some qualifications. Note that
the trial distribution explicitly contains marginal probabilities as variables.
Thus, once we fit the distribution, extracting the marginal probabilities is as
easy as reading them off.

3.4.2 Relaxation Labeling via Mean-Field Approach
Another approximate inference algorithm that can be applied to pairwise
MRFs is mean-field relaxation labeling (MF). The basic algorithm can be
described by the following fixed point equation:

b j ( y j )= αφ j ( y j )
Y i ∈N j ∩Y

ψ b i ( y i )
ij

( y i ,y j ) , j ∈L

y i ∈L

where b j ( y j ) denotes the marginal probability of assigning Y j ∈Y with label y j

and α is a normalization constant that ensures y j b j ( y j ) = 1. The algorithm
simply computes the fixed point equation for every node Y j and keeps doing
so until the marginal probabilities b j ( y j ) stabilize. When they do, we simply
return b j ( y j ) as the computed marginals. The pseudo-code for MF is shown
in Algorithm 4 .
MF can also be justified as a variational method in almost exactly the same
way as LBP. In this case, however, we choose a simpler trial distribution:

b ( y )=
Y i ∈Y

b i ( y i )

We refer the interested reader to (40; 44) for more details.