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$?
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