Structured Prediction by Conditional Risk Minimization
This work addresses structured prediction tasks for machine learning practitioners, offering a general approach that is incremental in adapting to different loss functions.
The authors tackled the problem of supervised learning with structured output spaces by proposing a method based on conditional risk minimization, which enables efficient training and inference without convex surrogates for discontinuous loss functions, showing effectiveness in adapting to various loss functions in empirical evaluations.
We propose a general approach for supervised learning with structured output spaces, such as combinatorial and polyhedral sets, that is based on minimizing estimated conditional risk functions. Given a loss function defined over pairs of output labels, we first estimate the conditional risk function by solving a (possibly infinite) collection of regularized least squares problems. A prediction is made by solving an inference problem that minimizes the estimated conditional risk function over the output space. We show that this approach enables, in some cases, efficient training and inference without explicitly introducing a convex surrogate for the original loss function, even when it is discontinuous. Empirical evaluations on real-world and synthetic data sets demonstrate the effectiveness of our method in adapting to a variety of loss functions.