PSD Representations for Effective Probability Models

Alessandro Rudi, Carlo Ciliberto

Abstract

Finding a good way to model probability densities is key to probabilistic inference. An ideal model should be able to concisely approximate any probability while being also compatible with two main operations: multiplications of two models (product rule) and marginalization with respect to a subset of the random variables (sum rule). In this work, we show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. In particular, we characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Moreover, we show that we can perform efficiently both sum and product rule in closed form via matrix operations, enjoying the same versatility of mixture models. Our results open the way to applications of PSD models to density estimation, decision theory and inference.

Introduction

In machine learning, choosing how to model a probability distribution usually forces a frustrating trade-off between computational tractability and expressiveness. If one desires easily performed core probabilistic operations—like the sum rule (marginalization) or the product rule (multiplying two distributions)—Mixture Models (e.g., Gaussian Mixture Models) are the standard choice. However, because mixture models only use positive weights, they suffer from the curse of dimensionality, requiring an exponentially large number of components to accurately approximate complex, high-dimensional distributions.

Conversely, Exponential Models or Implicit Generative Models (like GANs or Normalizing Flows) are highly expressive but make basic operations like marginalization computationally intractable. This work introduces Positive Semi-Definite (PSD) models, which bridge this gap by offering a class of models as flexible as exponential models but as mathematically convenient as mixture models.

Comparison of probability modeling frameworks across key properties.

Methodology: The PSD Model Framework

A PSD model is a generalization of a Gaussian Mixture Model. Instead of a simple weighted sum of positive Gaussians, a PSD model is defined by a positive semi-definite matrix $A$ and a set of base points. The model evaluates the density using a quadratic form: $f(x) = \phi(x)^\top A \phi(x)$, where $\phi(x)$ is a feature map associated with a Gaussian kernel.

This structure introduces two significant advantages:

  1. Negative Weights with Global Non-negativity: Because $A$ is a positive semi-definite matrix, the overall function is strictly guaranteed to be non-negative everywhere. However, the off-diagonal elements of $A$ can be negative. This allows the kernel components to destructively interfere, canceling out errors and fitting complex shapes far more efficiently than standard mixture models.
  2. Closed-Form Matrix Operations: Fundamental rules of probability map directly to matrix operations. Exact marginalization and multiplication of two PSD models can be performed entirely through standard linear algebra operations, such as Hadamard and Kronecker products.

To manage computational complexity during sequential inference (where multiplying two $m$-center models results in $m^2$ centers), the authors employ a Nyström-based projection method to "compress" the model back to a small number of points while bounding the approximation error.

Theoretical Guarantees

The paper provides strong theoretical support for PSD models, characterizing both their approximation and generalization capabilities:

  • Breaking the Curse of Dimensionality: By allowing "negative weights" while preserving global non-negativity, PSD models achieve optimal approximation rates. For a $\beta$-smooth density, a PSD model requires only $m = O(\varepsilon^{-d/\beta})$ base points to reach $\varepsilon$ precision.
  • Optimal Learning Rates: When learning from $n$ independent samples, PSD models achieve the minimax optimal learning rate of $O(n^{-\beta/(2\beta+d)})$.
  • Efficient Compression: A compressed model requires only $O(m \text{ polylog}(1/\varepsilon))$ centers to approximate the product of two $m$-center models, making sequential inference viable.

Conclusion and Future Work

PSD models offer a promising "best of both worlds" solution for probability density estimation, enabling exact, efficient inference via matrix math while maintaining optimal approximation rates. While this work is primarily theoretical, it opens doors for applications in continuous Hidden Markov Models (HMMs), decision theory, and complex inference tasks. Future research will focus on empirical validation, building software libraries, and addressing the challenges of efficient i.i.d. sampling from these models.

Summary updated

Abstract

Finding a good way to model probability densities is key to probabilistic inference. An ideal model should be able to concisely approximate any probability while being also compatible with two main operations: multiplications of two models (product rule) and marginalization with respect to a subset of the random variables (sum rule). In this work, we show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. In particular, we characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Moreover, we show that we can perform efficiently both sum and product rule in closed form via matrix operations, enjoying the same versatility of mixture models. Our results open the way to applications of PSD models to density estimation, decision theory and inference.
BibTeX
@inproceedings{rudi2021psd,
  author = {Alessandro Rudi and Carlo Ciliberto},
  title = {{PSD Representations for Effective Probability Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=HyQskgZwXO},
}
Figure