Deep Stochastic Processes via Functional Markov Transition Operators

Jin Xu, Emilien Dupont, Kaspar Märtens, Tom Rainforth, Yee Whye Teh

Executive Summary

Markov Neural Processes (MNPs) are a new class of stochastic processes that build complex distributions by stacking sequences of neural-parameterized Markov transition operators. Unlike many recent extensions to Neural Processes, MNPs significantly boost expressivity and performance while strictly maintaining the mathematical "gold standard" of consistency and exchangeability.

The Consistency Problem in Neural Processes

Stochastic Processes (SPs)—like the famous Gaussian Process—are the workhorses of uncertainty modeling. They allow us to define distributions over functions rather than just numbers. In the deep learning era, Neural Processes (NPs) were introduced to combine the flexibility of neural networks with the principled uncertainty of SPs.

However, the original NPs often underfit data. To fix this, researchers created "predictive" versions (like Attentive NPs or Convolutional NPs) that perform better but at a hidden cost: they lose conditional consistency. In plain English, this means their predictions don't actually correspond to a single underlying "prior" model. If you update the model with new data points sequentially, the uncertainties can become miscalibrated or even contradictory. This makes them risky for high-stakes sequential tasks like Bayesian optimization or medical decision-making.

Markov Neural Processes (MNPs)

The authors introduce MNPs to solve this dilemma. Instead of trying to map a context set to a prediction in one giant leap, MNPs treat the construction of a stochastic process as an iterative refinement.

Iterative refinement of a stochastic process from a trivial prior to a complex final state.
  1. Functional Markov Transition Operators (FMTOs): The core innovation is a mathematical proof showing that you can "stack" transformations in function space. If you start with a simple, valid SP (like white noise) and apply these operators, the resulting complex process is guaranteed to remain a valid SP (satisfying Kolmogorov’s Consistency Theorem).
  2. Invertible Transformations: To make this work, they use Normalizing Flows (specifically rational quadratic splines). These allow the model to warp a simple distribution into a highly complex one while remaining mathematically tractable.
  3. Latent Markov Chain: The model uses a sequence of latent variables $z^{(1:T)}$. The generative process moves from a "trivial" SP to a "final" expressive SP.
  4. Reverse-Path Inference: Because the model is a sequence, standard inference doesn't work. The authors designed a novel inference model that works in reverse, starting from the observed data and "undoing" the transformations to find the latent states.

Experimental Domains

The authors evaluated MNPs across three distinct domains:

  • 1D Synthetic Regression: They tested on standard Gaussian Process kernels (RBF, Matern) and more difficult non-Gaussian data, including monotonic functions, convex functions, and trajectories from Stochastic Differential Equations (SDEs).
  • Wheel Contextual Bandit: A classic reinforcement learning benchmark that requires a model to manage the exploration-exploitation trade-off based on its uncertainty.
  • GeoFluvial Dataset: A newly generated dataset for this paper consisting of 25,000 simulations of river (fluvial) patterns. These are represented as $128 \times 128$ grayscale images, simulating complex geological structures that are notoriously hard for traditional Gaussian Processes to model.

Why MNPs Work

  • Generative > Predictive: The paper argues forcefully for "generative" SPs. By ensuring the model is a valid SP, it becomes "safe" for sequential updates. It won't fall foul of "Dutch Book" scenarios where a sequence of bets (or predictions) leads to a guaranteed loss or inconsistency.
  • Complexity through Stacking: Much like how Deep Neural Networks gain power by stacking layers, MNPs gain expressivity by stacking functional transitions. A single transition might only slightly warp the function space, but multiple steps can model highly non-linear, non-Gaussian patterns.
  • Uncertainty that "Makes Sense": In the geological tasks, MNPs didn't just predict the most likely river path; they provided uncertainty maps that correctly identified where data was missing or where the river's direction was ambiguous.

Performance Highlights

MNPs demonstrate clear advantages over baseline models, particularly on complex, non-Gaussian datasets.

Quantitative results comparing MNPs against baselines on 1D regression tasks.
  • Superior Expressivity: On 1D non-GP data (like convex functions), MNPs achieved a marginal log-likelihood of 5.582, dwarfing the original NP's 1.956.
  • Closing the Gap: On data actually sampled from GPs, MNPs performed nearly as well as "Oracle" models (GPs with perfectly known parameters), whereas standard NPs lagged far behind.
  • Contextual Bandits: MNPs outperformed both NPs and MAML (a popular meta-learning algorithm) in the "Wheel" bandit task, achieving significantly lower "regret" (a measure of how many mistakes the agent makes).
  • Geological Modeling: In the GeoFluvial task, MNPs achieved a log-likelihood of 1.12 compared to the NP's -0.25. Qualitatively, MNPs produced much sharper, more realistic geological features.

Limitations and Future Directions

  • Computational Cost: Because MNPs stack transitions, the memory and time requirements scale linearly with the number of steps. Training a 7-step MNP on 1D functions took about a day on a GTX 1080 GPU.
  • Discrete vs. Continuous: Currently, the model uses a finite number of steps. The authors suggest that moving to continuous-time Markov transitions (essentially defining the process via a Differential Equation in function space) could be more memory-efficient using "adjoint methods."
  • Symmetries: The current model is general-purpose. The authors note that adding specific symmetries (like translation invariance for images) via convolutions could further boost performance on spatial data.

Summary updated

Abstract

We introduce Markov Neural Processes (MNPs), a new class of Stochastic Processes (SPs) which are constructed by stacking sequences of neural parameterised Markov transition operators in function space. We prove that these Markov transition operators can preserve the exchangeability and consistency of SPs. Therefore, the proposed iterative construction adds substantial flexibility and expressivity to the original framework of Neural Processes (NPs) without compromising consistency or adding restrictions. Our experiments demonstrate clear advantages of MNPs over baseline models on a variety of tasks.
BibTeX
@inproceedings{xu2023deep,
  author = {Jin Xu and Emilien Dupont and Kaspar Märtens and Tom Rainforth and Yee Whye Teh},
  title = {{Deep Stochastic Processes via Functional Markov Transition Operators}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=Lg1ODJGGiI},
}
Figure