Approximate Learning for Structured Prediction Problems
Alex Kulesza · 2009
Prediction problems such as image segmentation, sentence parsing, and gene prediction involve complex output spaces for which multiple decisions must be coordinated to achieve optimal results. Unfortunately, this means that there are generally an exponential number of possible predictions for every input. Markov random fields can be used to express structure in these output spaces, reducing the number of model parameters to a manageable size; however, the problem of learning those parameters from a training sample remains NP-hard in general. We review some recent results on approximate learning of structured prediction problems. There are two distinct approaches. In the first, results from the well-studied field of approximate inference are adapted to the learning setting. In the second, learning performance is characterized directly, producing bounds even when the underlying inference method does not offer formal approximation guarantees. While the literature on this topic is still sparse, we review the strengths and weaknesses of current results, and discuss issues