Low rank continuous-space graphical models

Carl Smith, Frank D. Wood, Liam PaninskiAISTATS 2012 · OpenReview

Presented at AISTATS 2012, this research introduces a novel framework for performing exact inference in a specific class of continuous-space graphical models. By identifying and exploiting a "low-rank" structure within the model's potentials, the authors bridge the long-standing gap between simple, tractable discrete models and complex, often intractable, continuous ones.

The Challenge of Continuous Inference

Graphical models are essential for representing complex probability distributions, yet exact inference—calculating true marginals or conditionals—is typically limited to two scenarios: discrete state spaces, where summation is feasible, and linear-Gaussian models, where distributions remain closed under standard operations.

When dealing with non-Gaussian continuous variables, such as probabilities constrained to $[0, 1]$ or circular data (angles), researchers often rely on approximations like Gibbs sampling or Laplace approximations. These methods can be computationally expensive or inaccurate. This paper proposes a third way: continuous-space models that are both expressive and exactly solvable through a discrete auxiliary structure.

The Low-Rank Framework

The core innovation is the introduction of a "low-rank" structure using discrete auxiliary variables. Rather than defining a direct, complex dependency between continuous variables $x_t$ and $x_{t+1}$, the authors insert a discrete auxiliary variable $z_t$ between them. This variable $z_t$ has a finite state space of size $R$, which defines the rank of the potential.

Comparison of standard state-space models (left) with the proposed auxiliary variable model (middle) and its factor graph representation (right).

This structure allows the continuous variables $x_t$ to be analytically marginalized out in many cases. This transformation leaves a standard Markov chain consisting solely of the discrete $z_t$ variables. Consequently, the classic forward-backward algorithm can be employed to perform exact inference in $O(R^2 T)$ time, where $T$ is the sequence length. This adapts a standard Hidden Markov Model (HMM) technique to solve continuous-space problems exactly.

Model Selection and Rank Estimation

A significant advantage of this approach is that the "rank" $R$ serves as a natural smoothing parameter. Because the marginal likelihood is computed as a byproduct of the forward pass, it can be used to automatically estimate the optimal rank from the data, balancing model complexity with fit.

The marginal likelihood as a function of rank R, used for automatic model selection.

Key to the mathematical tractability is the use of conjugacy. By choosing the conditional distribution $p(z|x)$ to be conjugate to the prior $G_0(x)$, the authors ensure that the resulting distributions remain within the same family (e.g., Beta-Binomial or Dirichlet-Multinomial), keeping the integration manageable.

Empirical Evaluation

The method was evaluated on two distinct datasets:

  1. Neural Spike Trains: Inferring underlying firing rates (probabilities between 0 and 1) from binary spike observations.
  2. CMU Motion Capture Database: Analyzing joint articulation data (angles) using von Mises distributions to handle circular phase data.

Results demonstrated that the exact method significantly outperforms Gibbs sampling, which required thousands of iterations to match the accuracy of the low-rank approach, particularly in sparse data regimes. The model also showed robust smoothing capabilities, correctly increasing uncertainty in regions with missing data by reverting toward a uniform distribution.

Limitations and Future Directions

The primary constraint of the model is its computational scaling: the $O(R^2 T)$ complexity means that if a problem requires a very high rank $R$ for accuracy, the method may become less efficient than approximate alternatives. Furthermore, the current framework assumes non-negative potentials to maintain a Markov chain interpretation; while mathematically flexible, negative values can introduce numerical instability.

Future work may explore connections to Reproducing Kernel Hilbert Spaces (RKHS) and the application of these exact techniques to more complex structures, such as time-dependent Dirichlet process mixtures.

Summary updated

BibTeX
@inproceedings{smith2012low,
  author = {Carl Smith and Frank D. Wood and Liam Paninski},
  title = {{Low rank continuous-space graphical models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=TvYykIn3D1B},
}
Figure