Ordered conditional approximation of Potts models

Anirban Chakraborty, Matthias Katzfuß, Joseph Guinness

TL;DR

This paper introduces the Ordered Conditional Approximation (OCA), a method that makes inference for Potts models—notoriously difficult spatial models for categorical data—computationally efficient. By approximating the joint probability as a product of local conditional distributions, the authors achieve linear-time complexity ($O(n)$) and enable rapid sampling and parameter estimation for both observed and hidden spatial fields.

What Problem Does This Paper Address?

Potts models are the "gold standard" for modeling categorical data on a grid (like pixels in an image or atoms in a crystal). However, they suffer from a massive computational bottleneck: the normalizing constant. To calculate the probability of a specific configuration, you technically need to sum over every possible state the grid could take. For a modest $100 \times 100$ grid with 3 categories, there are $3^{10,000}$ possible states—a number far larger than the atoms in the observable universe.

Existing workarounds like Besag’s "pseudo-likelihood" avoid this sum but often result in high statistical variance. Other methods like Markov Chain Monte Carlo (MCMC) are slow to converge (the "mixing" problem). The authors aim to provide a method that is both statistically accurate and fast enough for large-scale modern datasets.

Methods

The core innovation is the Ordered Conditional Approximation (OCA). It draws inspiration from "Vecchia approximations" used in Gaussian Processes.

  1. Ordering: The spatial locations are assigned a specific order (the authors found simple lexicographic/reading order works best).
  2. Conditional Product: The joint density is written as a product of conditional probabilities: $p(z_1) \cdot p(z_2|z_1) \cdot p(z_3|z_1, z_2) \dots$
  3. Local Truncation: Instead of conditioning a point on every previous point, OCA conditions it only on a small set of "nearest neighbors" from the past ($m_g$) and a small set of "look-ahead" points in the future ($m_f$).
  4. Modified Hamiltonian: By restricting the calculation to these small local windows, the intractable global sum is replaced by a tiny local sum that can be computed in milliseconds.

Crucially, this approach works for both observed Potts models (where we see the categories directly) and hidden Potts models (where we see noisy data, like a blurry satellite image, and must infer the underlying categories).

Datasets

The authors evaluated OCA using:

  • Simulated Ising and Potts Models: Grids of size $12 \times 12$ and $50 \times 50$ used to compare OCA against the exact likelihood and Besag’s pseudo-likelihood.
  • The Menteith Satellite Dataset: A classic $100 \times 100$ satellite image of the Lake of Menteith in Scotland. The goal was to classify pixels into six surface types (water, land, etc.) based on noisy spectral data.

Key Insights and Ideas

  • The "Future" Matters: Unlike some time-series models that only look backward, OCA's accuracy depends heavily on the "future" conditioning set ($m_f$). Including just a few look-ahead points significantly improves the approximation of the spatial dependence.
  • Lexicographic is King: In Gaussian Process literature, "maximin" ordering (picking points far apart) is usually better. Surprisingly, for Potts models, the authors found that simple row-by-row (lexicographic) ordering provided more accurate results.
  • One-Pass Sampling: Because OCA defines the field as a sequence of conditional distributions, you can generate a sample of the entire field in a single pass. This bypasses the "burn-in" and "mixing" issues that plague MCMC methods.
  • Parallel Potential: Since the conditional terms for different points can be calculated independently (given their neighbors), the method is naturally suited for parallel computing on GPUs or multi-core CPUs.

Key Results

  • Accuracy: In simulations, OCA consistently produced parameter estimates with lower Root Mean Squared Error (RMSE) than the standard pseudo-likelihood method.
  • Scalability: The computational cost scales linearly with the number of pixels ($n$). For the $100 \times 100$ satellite image, a single draw from the hidden Potts model took only 2 seconds on a standard laptop.
  • Robustness: On the Menteith satellite data, OCA successfully identified distinct geographical features. In contrast, a standard Gaussian Mixture Model (which ignores spatial correlation) failed completely, classifying all pixels into a single category.
  • Convergence: As the size of the local neighborhood ($m_f$) increases, the OCA likelihood converges toward the true, exact likelihood.

Limitations and Future Work

  • The Exponential Catch: While the complexity is linear in the number of pixels $n$, it is exponential in the size of the future conditioning set ($K^{m_f}$). If you have many categories ($K$) or need a very large look-ahead window, the method becomes slow.
  • Critical Temperature: The approximation is less accurate when the "inverse temperature" parameter $\beta$ is high (near the "critical temperature" where the model suddenly shifts from random noise to large solid blocks of color).
  • Theoretical Bounds: The authors note that while OCA works well in practice, formal theoretical bounds on the approximation error for Potts models (similar to those existing for Gaussian Processes) are still an open research question.
  • Non-Stationary Models: Future work could extend this to models where the spatial dependence ($\beta$) changes across the image (e.g., different textures in different parts of a photo).

Summary updated

Abstract

Potts models, which can be used to analyze dependent observations on a lattice, have seen widespread application in a variety of areas, including statistical mechanics, neuroscience, and quantum computing. To address the intractability of Potts likelihoods for large spatial fields, we propose fast ordered conditional approximations that enable rapid inference for observed and hidden Potts models. Our methods can be used to directly obtain samples from the approximate joint distribution of an entire Potts field. The computational complexity of our approximation methods is linear in the number of spatial locations; in addition, some of the necessary computations are naturally parallel. We illustrate the advantages of our approach using simulated data and a satellite image.
BibTeX
@inproceedings{chakraborty2022ordered,
  author = {Anirban Chakraborty and Matthias Katzfuß and Joseph Guinness},
  title = {{Ordered conditional approximation of Potts models}},
  booktitle = {Spatial},
  year = {2022},
  doi = {10.1016/j.spasta.2022.100708},
}
Figure