PSD Representations for Effective Probability Models

Alessandro Rudi, Carlo Ciliberto

Introduction

Finding a robust way to model probability densities is a cornerstone of probabilistic inference. An ideal model must be able to concisely approximate any probability distribution while remaining compatible with two fundamental operations: the product rule (multiplying two models, essential for Bayes' inference) and the sum rule (marginalization with respect to a subset of random variables).

This paper introduces Positive Semi-Definite (PSD) models as a powerful "best-of-both-worlds" framework for probability density estimation. They provide the computational ease of mixture models while achieving the optimal learning rates and "conciseness" of kernel methods, effectively overcoming the curse of dimensionality without ever producing invalid negative probability values.

The Challenge: Expressiveness vs. Tractability

Researchers usually face a frustrating trade-off between expressiveness and tractability when choosing a model class.

  • Mixture models (like Gaussian Mixture Models) are easy to integrate and multiply, but they require a massive number of components to approximate complex shapes. This leads to slow learning rates that suffer heavily from the "curse of dimensionality."
  • Exponential or Implicit models are highly expressive, but they make operations like marginalization computationally intractable.
  • Linear models and RBF networks can learn quickly and concisely, but they often output negative values, making them mathematically invalid as true probability distributions.
Comparison of probability models across key properties. PSD models uniquely satisfy all desired criteria.

The authors tackle the challenge of creating a single model class that satisfies all these requirements simultaneously, as summarized in the table above.

The Solution: Gaussian PSD Models

The authors propose using Gaussian PSD models. In this framework, a probability density function $f(x)$ is represented in the form:

$$f(x) = \phi(x)^\top M \phi(x)$$

where $\phi(x)$ is a feature map (specifically for a Gaussian kernel) and $M$ is a positive semi-definite matrix.

Key Technical Innovations

  1. The PSD Constraint: Because $M$ is positive semi-definite, the function is guaranteed to be non-negative everywhere. However, unlike standard mixtures where every individual weight must be strictly positive, the matrix $M$ can have negative off-diagonal entries. This "flexibility to cancel out" allows the model to approximate complex, smooth functions much more efficiently.
  2. Closed-form Inference: The authors derive exact matrix algebra identities for both the Sum Rule (marginalization) and the Product Rule. This means complex probabilistic inference can be reduced entirely to efficient matrix multiplications and trace operations.
  3. Nyström Compression: Multiplying two models with $m$ components naturally results in a model with $m^2$ components. To prevent this computational "inflation" during sequential operations, the authors introduce a compression technique based on Nyström projection. This keeps the model size manageable without sacrificing significant accuracy.

Key Theoretical Insights and Results

This work is a rigorous theoretical foundation rather than an empirical benchmark study. The authors prove that their model class achieves optimal theoretical bounds for both approximation (how well it can represent a function) and learning (how fast it improves with more data).

  • Breaking the Curse of Dimensionality (Optimal Learning): Traditional non-negative mixtures learn very slowly in high dimensions. By allowing "negative weights" within the PSD matrix structure, these models achieve the minimax optimal learning rate of $n^{-\beta/(2\beta+d)}$ (Theorem 7). This means they are statistically as efficient as theoretically possible for smooth densities.
  • Conciseness: The paper proves (Theorem 6) that PSD models are inherently "concise." For a $\beta$-smooth density, a PSD model only needs $O(\epsilon^{-d/\beta})$ components to achieve an error of $\epsilon$, requiring significantly fewer components than traditional mixtures to achieve the same accuracy.
  • Unified Inference Engine: Because the models are closed under sum and product rules, they are perfectly suited for Graphical Models. The authors demonstrate this by providing a complete, exact algorithm for Hidden Markov Models (HMMs) using only PSD matrix operations.
  • Effective Compression: Theorem 8 shows that a model can be compressed to $O(m \text{ poly log}(1/\epsilon))$ centers while maintaining high accuracy, effectively solving the problem of component explosion during inference.

Limitations and Future Directions

While theoretically optimal, the framework has practical considerations to address in future work:

  • Inflation of Base Points: Even with Nyström compression, performing many sequential operations (like in a very long HMM or a large graphical model) requires frequent re-compression, adding computational overhead.
  • High-Dimensional Scaling: The statistical rate is optimal, but the computational cost involves handling matrices that scale with the number of base points. In very high dimensions with highly complex data, matrix operations could still be demanding.
  • Empirical Validation: As a purely theoretical paper, the natural next step is to develop a robust software library. Testing these models on real-world density estimation and decision theory tasks will be crucial to see how they perform against modern deep learning-based density estimators.

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