Source-linked AI summary
Deep belief networks are exact
Gleb Smirnov
TL;DR
The paper addresses whether strictly positive distributions can be represented exactly, rather than only approximated, by sigmoid belief networks. It replaces probability-sharing approximations with a topological construction using Brouwer’s fixed-point theorem, proving exact finite-parameter representation. The proof establishes existence but does not provide an algorithm for finding the parameters.
Problem
Earlier work established arbitrary approximation, but exact representation of every strictly positive distribution by a finite-parameter sigmoid belief network remained open.
Method
The proof composes probability-sharing sigmoid networks and uses uniform convergence together with Brouwer’s fixed-point theorem.
Results
Every strictly positive probability distribution on {−1,1}^n is exactly representable by a sigmoid belief network with finite parameters.
Takeaways & Limitations
The result upgrades probability-sharing approximation to exact representation for the strictly positive distributions covered by the theorem.
Takeaways & Limitations
The topological proof establishes that suitable finite parameters exist but does not provide an algorithm for finding them.
Abstract
from arXiv · showhide
We prove that every strictly positive probability distribution on \(\{-1,1\}^n\) is represented exactly by a sigmoid belief network with finite parameters. This answers a question of Sutskever and Hinton. The proof upgrades their probability-sharing approximation to exact representation using Brouwer's fixed-point theorem.
1. Main results. A sigmoid belief network consists of binary random vectors
Sigmoid belief networks generate visible distributions by sampling the top layer and proceeding downward, and prior work established arbitrary approximation but not exact representation. The paper answers the open question affirmatively for every strictly positive distribution, using finite parameters, while noting that its topological proof is nonconstructive.
- The network samples the top layer first and generates successive layers downward, with the visible layer V0 carrying the represented distribution.
- Prior work showed that deep and narrow sigmoid belief networks can approximate every distribution on {−1,1}^n arbitrarily well.
- The paper closes the gap between approximation and exactness by affirming that every strictly positive distribution can be exactly represented with finite parameters.
- The theorem permits maximal layer width n+1 and depth 3(2n −1)+1.
- Strict positivity is necessary because finite parameters give the top layer full support and strictly positive transition probabilities, making every visible configuration positive-probability.
- The proof is topological and uses Brouwer’s fixed-point theorem, establishing existence of finite parameters without providing an algorithm to find them.
2. Sharing.
The paper builds approximate probability-sharing modules and composes them to map sharing parameters to strictly positive distributions. Uniform convergence of the modules enables a Brouwer fixed-point argument that upgrades approximation to exact representation.
- Sharing: A sharing transfers a fraction p of the probability mass at x0 to xi while leaving all other probabilities unchanged.
- Sharing: Sequential sharings from x0 to x1,...,xM parameterize every strictly positive distribution through a one-to-one map Φ from (0,1)^M.
- Sharing: The five-step sigmoid construction copies the input, detects x0, passes the input forward, decides whether to share, and produces the output.
- Sharing: The construction’s sharing failure probability vanishes as w →∞, and convergence is uniform in p ∈(0,1) and the input X.
- Sharing: Replacing each sharing with a sigmoid network adds three layers, while initialization and sharing failures are bounded by terms involving εw.
- Sharing: The resulting network distributions converge uniformly in total variation to the ideal sharing distributions as w →∞, a property needed for exact representation.
3. Proof of Theorem 1.1. Let
The proof turns the continuous probability-sharing construction into exact representation by combining uniform approximation with Brouwer’s fixed-point theorem. A fixed point of the resulting map yields parameters whose sigmoid belief network distribution equals the target distribution.
- The successive probability-sharing operations define a continuous map from the interior of the probability simplex to network distributions.
- The finite-parameter network map Φw converges uniformly to the ideal map Φ in total variation as w →∞.
- For a fixed target distribution π, the proof selects a compact neighborhood S inside the simplex interior to control the approximation.
- The induced map T is continuous and maps the chosen compact convex set D into itself, so Brouwer’s fixed-point theorem supplies p ∈D with T(p)=p.
- At the fixed point, Φw(p)=π, completing the exact-representation proof.