MiS Preprint Repository

Delve into the future of research at MiS with our preprint repository. Our scientists are making groundbreaking discoveries and sharing their latest findings before they are published. Explore repository to stay up-to-date on the newest developments and breakthroughs.

MiS Preprint

Universal Approximation Depth and Errors of Narrow Belief Networks with Discrete Units

Guido Montúfar


We generalize recent theoretical work on the minimal number of layers of narrow deep belief networks that can approximate any probability distribution on the states of their visible units arbitrarily well. We relax the setting of binary units (Sutskever and Hinton, 2008; Le Roux and Bengio, 2008, 2010; Montufar and Ay, 2011) to units with arbitrary finite state spaces, and the vanishing approximation error to an arbitrary approximation error tolerance.

For example, we show that a $q$-ary deep belief network with $L\geq 2+\frac{q^{\lceil m- \delta \rceil}-1}{q-1}$ layers of width $n \leq m + \log_q(m) + 1$ for some $m\in\mathbb{N}$ can approximate any probability distribution on $\{0,1,\ldots,q-1\}^n$ without exceeding a Kullback-Leibler divergence of $\delta$.

Our analysis covers discrete restricted Boltzmann machines and na\"ive Bayes models as special cases.

Jul 29, 2014
Jul 30, 2014
MSC Codes:
82C32, 60C05, 68Q32
deep belief network, restricted Boltzmann machine, universal approximation, Representational Power, KL divergence

Related publications

2014 Repository Open Access
Guido Montúfar

Universal approximation depth and errors of narrow belief networks with discrete units

In: Neural computation, 26 (2014) 7, pp. 1386-1407