Search

MiS Preprint Repository

We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.

MiS Preprint
23/2010

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

Guido Montúfar and Nihat Ay

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 $\{0,1\}^n$ 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$ (given in Le Roux and Bengio, (2008)).

We construct a DBN with ${2^n}/{2(n-b)}$, $b\sim \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 in Le Roux and Bengio, (2010).

Received:
May 10, 2010
Published:
May 11, 2010

Related publications

inJournal
2011 Repository Open Access
Guido Montúfar and Nihat Ay

Refinements of universal approximation results for deep belief networks and restricted Boltzmann machines

In: Neural computation, 23 (2011) 5, pp. 1306-1319