  In this paper, we study the problem of semi-supervised structured output
prediction, which aims to learn predictors for structured outputs, such as
sequences, tree nodes, vectors, etc., from a set of data points of both
input-output pairs and single inputs without outputs. The traditional methods
to solve this problem usually learns one single predictor for all the data
points, and ignores the variety of the different data points. Different parts
of the data set may have different local distributions, and requires different
optimal local predictors. To overcome this disadvantage of existing methods, we
propose to learn different local predictors for neighborhoods of different data
points, and the missing structured outputs simultaneously. In the neighborhood
of each data point, we proposed to learn a linear predictor by minimizing both
the complexity of the predictor and the upper bound of the structured
prediction loss. The minimization is conducted by gradient descent algorithms.
Experiments over four benchmark data sets, including DDSM mammography medical
images, SUN natural image data set, Cora research paper data set, and Spanish
news wire article sentence data set, show the advantages of the proposed
method.
