  We consider a framework for structured prediction based on search in the
space of complete structured outputs. Given a structured input, an output is
produced by running a time-bounded search procedure guided by a learned cost
function, and then returning the least cost output uncovered during the search.
This framework can be instantiated for a wide range of search spaces and search
procedures, and easily incorporates arbitrary structured-prediction loss
functions. In this paper, we make two main technical contributions. First, we
define the limited-discrepancy search space over structured outputs, which is
able to leverage powerful classification learning algorithms to improve the
search space quality. Second, we give a generic cost function learning
approach, where the key idea is to learn a cost function that attempts to mimic
the behavior of conducting searches guided by the true loss function. Our
experiments on six benchmark domains demonstrate that using our framework with
only a small amount of search is sufficient for significantly improving on
state-of-the-art structured-prediction performance.
