Manifold Structured Prediction

Alessandro Rudi, Carlo Ciliberto, Gian Maria Marconi, Lorenzo Rosasco

Introduction

In classical machine learning, predictive models typically output scalars (regression) or categories (classification). However, many real-world problems require predicting outputs that possess a rich, underlying structure that cannot be neatly mapped to a simple vector space. Examples include predicting the local orientation of a fingerprint (a point on a circle), a probability distribution (a point on a simplex), or a rotation matrix.

While "structured prediction" frameworks exist to handle complex outputs, they have traditionally focused on discrete spaces, such as sequences or graphs. When dealing with continuous, non-linear spaces—specifically Riemannian manifolds—researchers have historically relied on ad-hoc methods or ignored the geometry entirely. A common, flawed approach is predicting in a flat Euclidean space and "projecting" the result back onto the manifold. This often leads to poor performance because the model is unaware of the output space's true distance metric during training.

This paper extends the framework of structured prediction to continuous output spaces. By characterizing a broad class of "smooth" loss functions (including squared geodesic distance) as "Structure Encoding," the authors provide a learning algorithm that is both statistically consistent and computationally efficient via Riemannian optimization.

Methodology: The Structure Encoding Loss Function (SELF)

The authors build upon a framework called the Structure Encoding Loss Function (SELF). The core idea is to "bi-linearize" a loss function $\Delta(y, y')$. If a loss is SELF, it can be decomposed into a feature map $\psi$ and a linear operator $V$ such that the loss behaves like an inner product in a Hilbert space.

The proposed algorithm operates in two distinct phases:

  1. Training (The "Score" Step): The model learns a set of weights $\alpha_i(x)$ using standard Kernel Ridge Regression. This step determines how much each training example should influence the prediction for a new input $x$. Because it involves solving a linear system, this step is computationally efficient.
  2. Inference (The "Prediction" Step): To find the predicted value $\hat{f}(x)$, the model solves a minimization problem at test time: $\text{argmin}_{y \in \mathcal{M}} \sum \alpha_i(x) \Delta(y, y_i)$.

The major theoretical contribution of this work is proving that any smooth function on a manifold (under mild assumptions) is a SELF. This allows the use of the squared geodesic distance—the "natural" distance on a manifold—as a loss function. To solve the inference step, the authors employ Riemannian Gradient Descent (RGD), ensuring the prediction always remains on the manifold.

Key Insights

  • Smoothness is Enough: You do not need a specialized loss function for every manifold. As long as your loss is smooth and the manifold is well-behaved (geodesically convex), the SELF framework applies.
  • Decoupling Input and Output: The method elegantly separates the complexity of the input space (handled by the kernel) from the geometric structure of the output space (handled by the manifold optimization).
  • Universal Consistency: The authors prove that as the amount of data increases, this estimator is guaranteed to converge to the optimal predictor—a property many ad-hoc manifold regression methods lack.
  • Geometry Matters: By incorporating the manifold's curvature and distance directly into the loss, the model avoids the inconsistencies seen when flat Euclidean models attempt to predict on curved surfaces.

Experiments and Key Results

The authors evaluated their approach on three different types of manifolds, demonstrating strong empirical performance across the board.

1. Fingerprint Reconstruction

Using the FVC fingerprint verification challenge dataset, the goal was to predict the local orientation of contour lines (points on the circle $S_1$).

Fingerprint reconstruction comparison

The Structured Prediction (SP) model achieved an average error of 18.8°, significantly outperforming both a specialized Manifold Regression (MR) competitor (22°) and standard Kernel Regularized Least Squares (KRLS) (26.9°). Qualitatively, the SP reconstructions were visibly smoother and much closer to the ground truth original image than the ridge regression baseline.

2. Positive Definite (PD) Matrices

In synthetic experiments learning the inverse of a matrix, the SP approach significantly outperformed KRLS when measured by geodesic distance. While KRLS was slightly better at minimizing standard squared error, it frequently produced "illegal" matrices that required artificial projection back onto the manifold.

3. Multilabel Classification

Using the Emotions, CAL500, and Scene datasets, the output was treated as a probability distribution on a simplex, utilizing the Fisher information metric. The SP approach achieved higher Area Under the Curve (AUC) scores than the baseline, demonstrating that treating label sets as points on a statistical manifold is a highly viable strategy.

Limitations and Future Work

While theoretically sound and empirically strong, the method has a few limitations:

  • Inference Speed: Unlike standard regression where prediction is a simple matrix multiplication, this method requires solving an optimization problem (RGD) for every test point, which could be a bottleneck for real-time applications.
  • Kernel Bottleneck: The training phase scales at $O(n^3)$. This is standard for kernel methods but difficult for "big data" without using approximations like Nyström methods.
  • Optimization Convergence: The authors note that they haven't yet provided formal convergence rates for the Riemannian optimization part of the inference step.

For future work, the authors suggest exploring Hyperbolic spaces, which are increasingly popular for representing hierarchical or relational data, such as word embeddings or social networks.

Summary updated

Abstract

Structured prediction provides a general framework to deal with supervised problems where the outputs have semantically rich structure. While classical approaches consider finite, albeit potentially huge, output spaces, in this paper we discuss how structured prediction can be extended to a continuous scenario. Specifically, we study a structured prediction approach to manifold-valued regression. We characterize a class of problems for which the considered approach is statistically consistent and study how geometric optimization can be used to compute the corresponding estimator. Promising experimental results on both simulated and real data complete our study.
BibTeX
@inproceedings{rudi2018manifold,
  author = {Alessandro Rudi and Carlo Ciliberto and Gian Maria Marconi and Lorenzo Rosasco},
  title = {{Manifold Structured Prediction}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=Hy-ZNwbOWS},
}
Figure