Refinements of Universal Approximation Results for Deep Belief Networks and Restricted Boltzmann Machines

Guido Montúfar, Nihat Ay

Abstract

This paper improves upon existing theoretical bounds for the resources required by Restricted Boltzmann Machines (RBM) and Deep Belief Networks (DBN) to function as universal approximators. We demonstrate that any distribution $p$ on binary vectors of length $n$ can be approximated by an RBM with $k-1$ hidden units, where $k$ relates to the minimal number of neighboring pairs covering the support set of $p$. For Deep Belief Networks, we construct a model with $\frac{2^n}{2(n-b)}$ layers of width $n$ capable of approximating any distribution on $\{0,1\}^n$, thereby confirming a 2010 conjecture by Le Roux and Bengio.

Introduction

In machine learning theory, a "universal approximator" is an architecture capable of representing any distribution within a class, provided it is sufficiently large. For Restricted Boltzmann Machines (RBMs) and Deep Belief Networks (DBNs)—stochastic models central to early deep learning—the fundamental question is: how large must these networks be to approximate any distribution over binary vectors of length $n$?

Architectural comparison of a Restricted Boltzmann Machine (RBM) and a Deep Belief Network (DBN).

While previous work established initial bounds, they were suspected to be inefficient. This paper provides tighter mathematical proofs, showing these models can achieve universal representation with significantly fewer resources than previously estimated.

The Universal Approximation Challenge

The challenge lies in finding the most compact way to "construct" arbitrary distributions using network parameters. Previous bounds by Le Roux and Bengio (2008, 2010) were foundational but left room for optimization. This research aims to reduce the theoretical "hardware requirements" for universal representation, moving closer to the absolute parameter-counting lower bounds.

Refined Bounds for Restricted Boltzmann Machines

The authors introduce a refinement for RBMs based on a "sharing" mechanism. They prove that a single hidden unit can independently adjust the probability mass of a pair of visible states, provided those states differ by only one bit (Hamming distance of 1).

By pairing states across the $n$-dimensional hypercube, the number of hidden units needed is effectively halved. Specifically, any distribution on $\{0, 1\}^n$ can be approximated by an RBM with $2^{n-1} - 1$ hidden units, a significant improvement over the previous $s+1$ bound (where $s$ is the support size).

Refined Bounds for Deep Belief Networks

For DBNs, the authors utilize Gray codes—binary sequences where only one bit changes at a time—and cyclic permutations. This allows the DBN to "overlay" multiple sequences of probability transactions across its layers, moving probability mass more efficiently from a base distribution to the target.

The paper proves that for a DBN with layers of width $n$, a depth of $\frac{2^n}{2(n-b)}$ layers (where $b \sim \log n$) is sufficient. This result confirms a significant conjecture in the field regarding the efficiency of deep stochastic architectures.

Key Insights

  • The Power of Pairs: A single hidden unit in an RBM can influence two neighboring states independently due to the bipartite structure, halving the required units.
  • Gray Code Optimization: Organizing state transitions via Gray codes maximizes the efficiency of each layer in a DBN.
  • Confirming the Conjecture: The formal proof validates the 2010 Le Roux and Bengio conjecture on DBN layer requirements.
  • Parameter Efficiency: The total parameter count $O(n 2^n / 2)$ is tighter than previous estimates, showing DBNs are highly efficient at utilizing their capacity.

Conclusion

While these results tighten the theoretical bounds, they are constructive proofs. It remains to be seen if standard training algorithms like Contrastive Divergence can reliably find these optimal parameters. Additionally, the absolute minimum size for universal approximation remains an open question, with preliminary experiments suggesting even smaller RBMs might suffice.

Summary updated

Abstract

We improve recently published results about resources of Restricted Boltzmann Machines (RBM) and Deep Belief Networks (DBN) required to make them Universal Approximators. We show that any distribution p on the set of binary vectors of length n can be arbitrarily well approximated by an RBM with k-1 hidden units, where k is the minimal number of pairs of binary vectors differing in only one entry such that their union contains the support set of p. In important cases this number is half of the cardinality of the support set of p. We construct a DBN with 2^n/2(n-b), b ~ log(n), hidden layers of width n that is capable of approximating any distribution on {0,1}^n arbitrarily well. This confirms a conjecture presented by Le Roux and Bengio 2010.
BibTeX
@article{montufar2011refinements,
  author = {Guido Montúfar and Nihat Ay},
  title = {{Refinements of Universal Approximation Results for Deep Belief Networks and Restricted Boltzmann Machines}},
  journal = {Neural Computation},
  year = {2011},
  url = {https://openreview.net/forum?id=HKZZtE5_Le9},
}
Figure