On Sparse, Spectral and Other Parameterizations of Binary Probabilistic Models

David Buchman, Mark Schmidt, Shakir Mohamed, David Poole, Nando de Freitas

Abstract: This paper studies issues relating to the parameterization of probability distributions over binary data sets. Several such parameterizations of models for binary data are known, including the Ising, generalized Ising, canonical and full parameterizations. We also discuss a parameterization that we call the “spectral parameterization”, which has received significantly less coverage in existing literature. We provide this parameterization with a spectral interpretation by casting log-linear models in terms of orthogonal Walsh-Hadamard harmonic expansions. Using various standard and group sparse regularizers for structural learning, we provide a comprehensive theoretical and empirical comparison of these parameterizations. We show that the spectral parameterization, along with the canonical, has the best performance and sparsity levels, while the spectral does not depend on any particular reference state. The spectral interpretation also provides a new starting point for analyzing the statistics of binary data sets; we measure the magnitude of higher order interactions in the underlying distributions for several data sets.

Introduction

Modeling distributions over binary data is a cornerstone of probabilistic machine learning, yet the choice of mathematical representation—the parameterization—is often treated as a secondary concern. This paper demonstrates that the choice of parameterization significantly impacts how models learn structure and generalize to new data. While pairwise models like the Ising model are common, they often fail to capture essential higher-order interactions. The authors introduce a "spectral parameterization" based on Walsh-Hadamard transforms, offering a symmetric, complete, and mathematically elegant alternative to traditional methods.

Parameterization and Sparsity

A critical challenge in binary modeling is structure learning: identifying which interactions among variables are significant. Typically, $\ell_1$-regularization is employed to induce sparsity. However, $\ell_1$-regularization is not re-parameterization invariant; different mathematical forms of the same distribution will be penalized differently. The authors compare several frameworks:

  • Full: Redundant and over-parameterized.
  • Ising: Limited to pairwise interactions, making it "incomplete" for general distributions.
  • Canonical: Requires an arbitrary "reference state" (e.g., the all-zeros vector), which can introduce bias.
  • Spectral: Decomposes the log-probability signal into orthogonal Walsh-Hadamard harmonics. This approach is minimal, complete, and symmetric, avoiding the need for a reference state.

Empirical Performance and Sparsity

The frameworks were evaluated on several well-known datasets, including NLTCS (disability surveys), Yeast (protein localization), and USPS (handwritten digits). The Spectral and Canonical parameterizations consistently outperformed others, achieving the lowest test-set negative log-likelihood and discovering the simplest underlying structures.

Test set negative log-likelihood across parameterizations for NLTCS, Yeast, and USPS datasets.

The results indicate that the standard Ising model's incompleteness prevents it from capturing subtle but necessary higher-order logic, leading to inferior predictive power compared to the Spectral and Canonical models. Furthermore, the spectral approach effectively places a prior on the "frequency" of interactions, which aligns well with the natural statistics of binary data.

The Spectral Signature of Binary Data

A key insight of this work is that real-world binary data exhibits a specific "spectral signature." Similar to how natural images have a characteristic power spectrum, binary datasets show a sharp decay in interaction magnitude as the order of interaction (the number of variables involved) increases.

Magnitude and sparsity of interactions as a function of interaction order |A|.

As shown in the figure above, both the average magnitude of parameters ($E|w_A|$) and the percentage of non-zero parameters plummet as the interaction size $|A|$ grows. This empirical evidence provides a strong justification for the historical success of pairwise models: while higher-order interactions exist, they are often negligible in magnitude for real-world datasets.

Conclusion and Future Directions

The spectral parameterization provides a robust, symmetric foundation for learning sparse binary models. While currently limited by the $2^n$ dimensionality of the transform (feasible for $n < 20$), the use of the Fast Walsh-Hadamard Transform (FWHT) mitigates computational costs. Future work may explore extensions to categorical data and deeper theoretical connections to compressed sensing, potentially enabling the learning of complex models from significantly fewer samples.

Summary updated

Abstract

This paper studies issues relating to the parameterization of probability distributions over binary data sets. Several such parameterizations of models for binary data are known, including the Ising, generalized Ising, canonical and full parameterizations. We also discuss a parameterization that we call the “spectral parameterization”, which has received significantly less coverage in existing literature. We provide this parameterization with a spectral interpretation by casting log-linear models in terms of orthogonal Walsh-Hadamard harmonic expansions. Using various standard and group sparse regularizers for structural learning, we provide a comprehensive theoretical and empirical comparison of these parameterizations. We show that the spectral parameterization, along with the canonical, has the best performance and sparsity levels, while the spectral does not depend on any particular reference state. The spectral interpretation also provides a new starting point for analyzing the statistics of binary data sets; we measure the magnitude of higher order interactions in the underlying distributions for several data sets.
BibTeX
@inproceedings{buchman2012sparse,
  author = {David Buchman and Mark Schmidt and Shakir Mohamed and David Poole and Nando de Freitas},
  title = {{On Sparse, Spectral and Other Parameterizations of Binary Probabilistic Models}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=OcaHpgTZqk0},
}

Loading related content...

Figure