Search-based Structured Prediction
  We present Searn, an algorithm for integrating search and learning to solve
complex structured prediction problems such as those that occur in natural
language, speech, computational biology, and vision. Searn is a meta-algorithm
that transforms these complex problems into simple classification problems to
which any binary classifier may be applied. Unlike current algorithms for
structured learning that require decomposition of both the loss function and
the feature functions over the predicted structure, Searn is able to learn
prediction functions for any loss function and any class of features. Moreover,
Searn comes with a strong, natural theoretical guarantee: good performance on
the derived classification problems implies good performance on the structured
prediction problem.
