Manifold Structured Prediction

Regression and classification are probably the most classical machine learning problems and correspond to estimating a function with scalar and binary values, respectively. In practice, it is often interesting to estimate functions with more structured outputs. When the output space can be assumed to be a vector space, many ideas from regression can be extended, think for example to multivariate [14] or functional regression [23]. However, a lack of a natural vector structure is a feature of many practically interesting problems, such as ranking [11], quantile estimation [19] or graph prediction [28]. In this latter case, the outputs are typically provided only with some distance or similarity function that can be used to design appropriate loss function. Knowledge of the loss is sufficient to analyze an abstract empirical risk minimization approach within the framework of statistical learning theory, but deriving approaches that are at the same time statistically sound and computationally feasible is a key challenge. While ad-hoc solutions are available for many specific problems [7, 9, 18, 27], structured prediction [5] provides a unifying framework where a variety of problems can be tackled as special cases.