  Mappings to structured output spaces (strings, trees, partitions, etc.) are
typically learned using extensions of classification algorithms to simple
graphical structures (eg., linear chains) in which search and parameter
estimation can be performed exactly. Unfortunately, in many complex problems,
it is rare that exact search or parameter estimation is tractable. Instead of
learning exact models and searching via heuristic means, we embrace this
difficulty and treat the structured output problem in terms of approximate
search. We present a framework for learning as search optimization, and two
parameter updates with convergence theorems and bounds. Empirical evidence
shows that our integrated approach to learning and decoding can outperform
exact models at smaller computational cost.
