An overview of structured prediction

Structured prediction is an important area of application for machine learning problems in a variety of domains. Considering an input x and an output y in areas such as a labeling of time steps, a collection of attributes for an image, a parsing of a sentence, or a segmentation of an image into objects, problems are challenging because the y's are exponential in the number of output variables that comprise it. These are computationally challenging because prediction requires searching an enormous space, and also statistical considerations, since learning accurate models from limited data requires reasoning about commonalities between distinct structured outputs. Structured prediction is fundamentally a problem of representation, where the representation must capture both the discriminative interactions between x and y and also allow for efficient combinatorial optimization over y.

Structured prediction is about predicting structured outputs from input data in contrast to predicting just a single number, like in classification or regression. For example:

• Natural language processing--automatic translation (output: sentences) or sentence parsing (output: parse trees)
• Bioinformatics--secondary structure prediction (output: bipartite graphs) or enzyme function prediction (output: path in a tree)
• Speech processing--automatic transcription (output: sentences) or text to speech (output: audio signal)
• Robotics--planning (output: sequence of actions)