On the Expressive Power of Restricted Boltzmann Machines

James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard S. ZemelNeurIPS 2013 · OpenReview

Introduction

This paper provides a rigorous theoretical look at the "brain power" of Restricted Boltzmann Machines (RBMs). The authors prove that while RBMs are surprisingly good at representing any distribution based on counting (like the PARITY function), they fail miserably at representing more complex logical structures like the "inner product mod 2" function without using an astronomical number of hidden units. This result provides one of the first formal mathematical justifications for why we need "deep" models instead of just making shallow models wider.

The Efficiency Gap in RBMs

Restricted Boltzmann Machines were a cornerstone of the early deep learning renaissance, used extensively for generative modeling and pre-training deep networks. It was already known that RBMs are "universal approximators"—meaning they can represent any distribution if you give them enough hidden units.

However, "enough" often meant an exponential number of units relative to the input size, which is computationally impossible in the real world. The gap in our knowledge was efficiency: What kinds of distributions can an RBM represent using only a reasonable (polynomial) number of hidden units? And more importantly, can we prove that certain simple-looking distributions are actually "hard" for an RBM to learn?

Bridging Physics and Complexity Theory

The authors bridge the gap between statistical physics (where RBMs originate) and computational complexity theory through several key methodological steps:

  1. RBM as a Neural Network: They demonstrate that the unnormalized log-likelihood of an RBM can be viewed as a standard feed-forward neural network with one hidden layer using softplus activation functions ($log(1 + e^y)$).
  2. The "Hardplus" Approximation: To make the mathematics tractable, they approximate the smooth softplus function with a "hardplus" function (essentially a ReLU). They prove that a network using one can simulate the other with high accuracy.
RBM Network and Hardplus Approximation
  1. Complexity Mapping: By relating these "RBM networks" to well-studied threshold circuits (networks of neurons that output 0 or 1), they can apply established lower bounds from the field of circuit complexity.
  2. Constructive Proofs: For the "easy" cases, they provide a specific recipe (a construction) for how to set RBM weights to represent symmetric distributions.

Evaluation Approach

As a theoretical paper, this work does not use empirical datasets like ImageNet or CIFAR-10. Instead, it evaluates RBMs against mathematical distribution families:

  • Symmetric Distributions: Distributions where the probability depends only on the number of 1s in the input (e.g., the PARITY function).
  • Inner Product mod 2 (IP): A distribution where the probability depends on a specific logical combination of input bits. This serves as the "hard" benchmark.

Key Insights and Results

Symmetry is Surprisingly Easy

The most surprising finding is that RBMs are incredibly efficient at representing symmetric distributions. The authors demonstrate that any symmetric distribution over $n$ bits can be represented to arbitrary accuracy by an RBM with only $m = n^2 + 1$ hidden units. Even the "PARITY" function—notoriously difficult for simple perceptrons—can be represented efficiently.

Constructing Symmetric Distributions

The "Feature Detector" Constraint

In an RBM, each hidden unit acts as a "feature detector" that can only add to the log-probability. This lack of "subtractive" logic in the output layer makes it very difficult for the model to perform multi-stage logical operations.

The Exponential Wall and the Need for Depth

The paper successfully draws a line in the sand: "Counting" tasks are easy for RBMs, but "multi-stage logic" tasks are hard. They prove that for the "Inner Product mod 2" function, the number of hidden units $m$ must grow exponentially with the input size $n$ (assuming the weights stay within a realistic range).

By proving that a relatively simple logical function requires an exponential number of units in a shallow RBM, the authors provide a "no-free-lunch" theorem. It suggests that increasing the width of a model is a poor substitute for increasing its depth.

Limitations and Future Work

  • Bounded Weights: The proof for the "hard" distributions assumes that the weights of the RBM are bounded (i.e., they don't grow to infinity). While this is realistic for practical training (where we use weight decay), a purely mathematical proof for the unbounded case remains an open challenge.
  • Deep Boltzmann Machines (DBMs): While this paper justifies the need for deeper models, it doesn't provide a corresponding efficiency proof for DBMs. The authors suggest that characterizing the expressive power of multi-layer Boltzmann machines is the natural next step.
  • Approximation vs. Exactness: The results focus on representing distributions to high accuracy. Exploring the limits of "rough" approximations might yield different efficiency bounds.

Summary updated

Abstract

This paper examines the question: What kinds of distributions can be efficiently represented by Restricted Boltzmann Machines (RBMs)? We characterize the RBM's unnormalized log-likelihood function as a type of neural network (called an RBM network), and through a series of simulation results relate these networks to types that are better understood. We show the surprising result that RBM networks can efficiently compute any function that depends on the number of 1's in the input, such as parity. We also provide the first known example of a particular type of distribution which provably cannot be efficiently represented by an RBM (or equivalently, cannot be efficiently computed by an RBM network), assuming a realistic exponential upper bound on the size of the weights. By formally demonstrating that a relatively simple distribution cannot be represented efficiently by an RBM our results provide a new rigorous justification for the use of potentially more expressive generative models, such as deeper ones.
BibTeX
@inproceedings{martens2013expressive,
  author = {James Martens and Arkadev Chattopadhyay and Toniann Pitassi and Richard S. Zemel},
  title = {{On the Expressive Power of Restricted Boltzmann Machines}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2013},
  url = {https://openreview.net/forum?id=BkZpJvZd-H},
}
Figure