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

object labeling in images. Due to its simplicity and appeal, relaxation labeling
was a topic of active research for some time and many researchers developed
different versions of the basic algorithm (20). Mean-field relaxation labeling
(39; 44), discussed in this article, is a simple instance of this general class
of algorithms. (4) also considered statistical analysis of images and proposed
a particularly simple approximate inference algorithm called iterated condi-
tional modes which is one of the earliest descriptions and a specific version
of the iterative classification algorithm presented in this article. Besides com-
puter vision, researchers working with an iterative decoding scheme known as
“Turbo Codes” (3) came up with the idea of applying Pearl's belief propaga-
tion algorithm (30) on networks with loops. This led to the development of
the approximate inference algorithm that we, in this article, refer to as loopy
belief propagation (LBP) (also known as sum product algorithm) (17; 25; 18).
Of course, the focus of this chapter is on collective classification techniques
for document classification. (7) was one of the first to apply collective clas-
sification to a corpora of patents linked via hyperlinks and reported that
considering attributes of neighboring documents actually hurts classification
performance. (33) also considered the problem of document classification by
constructing features from neighboring documents using an Inductive Logic
Programming rule learner. (42) conducted an in-depth investigation over mul-
tiple datasets commonly used for document classification experiments and
identified different patterns. Since then, collective classification has also been
applied to various other applications such as part-of-speech tagging (19), clas-
sification of hypertext documents using hyperlinks (34), link prediction in
friend-of-a-friend networks (37), optical character recognition (36), entity reso-
lution in sensor networks (8), predicting disulphide bonds in protein molecules
(35), segmentation of 3D scan data (2) and classification of email “speech acts”
(6).
Besides the four approximate inference algorithms discussed in this article,
there are other algorithms that we did not discuss such as graph-cuts based for-
mulations (5), formulations based on linear programming relaxations (16; 38)
and expectation propagation (26). Other examples of approximate inference
algorithms include algorithms developed to extend and improve loopy belief
propagation (LBP) to remove some of its shortcomings such as alternatives
with convergence guarantees (46) and alternatives that go beyond just using
edge and node marginals to compute more accurate marginal probability es-
timates such as the cluster variational method (45), junction graph method
(1) and region graph method (44).
More recently, there have been some attempts to extend collective classifi-
cation techniques to the semi-supervised learning scenario (41; 23).