Abstract
In a structured prediction problem, one needs to
learn a predictor that, given a structured input, produces a structured object, such as a sequence, tree,
or clustering output. Prototypical structured prediction tasks include part-of-speech tagging (predicting POS tag sequence for an input sentence) and semantic segmentation of images (predicting semantic labels for pixels of an input image). Unlike simple classification problems, here there is a need to
assign values to multiple output variables accounting for the dependencies between them. Consequently, the prediction step itself (aka “inference”
or “decoding”) is computationally-expensive, and
so is the learning process, that typically requires
making predictions as part of it. The key learning
and inference challenge is due to the exponential
size of the structured output space and depend on
its complexity. In this paper, we present a unifying perspective of the different frameworks that address structured prediction problems and compare
them in terms of their strengths and weaknesses.
We also discuss important research directions including integration of deep learning advances into
structured prediction methods, and learning from
weakly supervised signals and active querying to
overcome the challenges of building structured predictors from small amount of labeled data