Tractable Semi-Supervised Learning of Complex Structured Prediction Models

Semi-supervised learning has been widely studied in the literature.
However, most previous works assume that the output structure is simple enough
to allow the direct use of tractable inference/learning algorithms (e.g., binary label
or linear chain). Therefore, these methods cannot be applied to problems with
complex structure. In this paper, we propose an approximate semi-supervised
learning method that uses piecewise training for estimating the model weights
and a dual decomposition approach for solving the inference problem of finding
the labels of unlabeled data subject to domain specific constraints. This allows us
to extend semi-supervised learning to general structured prediction problems. As
an example, we apply this approach to the problem of multi-label classification (a
fully connected pairwise Markov random field). Experimental results on benchmark
data show that, in spite of using approximations, the approach is effective
and yields good improvements in generalization performance over the plain supervised
method. In addition, we demonstrate that our inference engine can be
applied to other semi-supervised learning frameworks, and extends them to solve
problems with complex structure.