  Motivated by Supervised Opinion Analysis, we propose a novel framework
devoted to Structured Output Learning with Abstention (SOLA). The structure
prediction model is able to abstain from predicting some labels in the
structured output at a cost chosen by the user in a flexible way. For that
purpose, we decompose the problem into the learning of a pair of predictors,
one devoted to structured abstention and the other, to structured output
prediction. To compare fully labeled training data with predictions potentially
containing abstentions, we define a wide class of asymmetric abstention-aware
losses. Learning is achieved by surrogate regression in an appropriate feature
space while prediction with abstention is performed by solving a new pre-image
problem. Thus, SOLA extends recent ideas about Structured Output Prediction via
surrogate problems and calibration theory and enjoys statistical guarantees on
the resulting excess risk. Instantiated on a hierarchical abstention-aware
loss, SOLA is shown to be relevant for fine-grained opinion mining and gives
state-of-the-art results on this task. Moreover, the abstention-aware
representations can be used to competitively predict user-review ratings based
on a sentence-level opinion predictor.
