  Structured output prediction aims to learn a predictor to predict a
structured output from a input data vector. The structured outputs include
vector, tree, sequence, etc. We usually assume that we have a training set of
input-output pairs to train the predictor. However, in many real-world appli-
cations, it is difficult to obtain the output for a input, thus for many
training input data points, the structured outputs are missing. In this paper,
we dis- cuss how to learn from a training set composed of some input-output
pairs, and some input data points without outputs. This problem is called semi-
supervised structured output prediction. We propose a novel method for this
problem by constructing a nearest neighbor graph from the input space to
present the manifold structure, and using it to regularize the structured out-
put space directly. We define a slack structured output for each training data
point, and proposed to predict it by learning a structured output predictor.
The learning of both slack structured outputs and the predictor are unified
within one single minimization problem. In this problem, we propose to mini-
mize the structured loss between the slack structured outputs of neighboring
data points, and the prediction error measured by the structured loss. The
problem is optimized by an iterative algorithm. Experiment results over three
benchmark data sets show its advantage.
