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

Guido Montúfar

Contact the author: Please use for correspondence this email.
Submission date: 29. Jul. 2014
Pages: 21
published in: Neural computation, 26 (2014) 7, p. 1386-1407 
DOI number (of the published article): 10.1162/NECO_a_00601
Bibtex
MSC-Numbers: 82C32, 60C05, 68Q32
Keywords and phrases: deep belief network, restricted Boltzmann machine, universal approximation, Representational Power, KL divergence
Download full preprint: PDF (433 kB)

Abstract:
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 ≥ 2 + layers of width n ≤ m + log _q(m) + 1 for some m ∈ ℕ can approximate any probability distribution on {0,1,…,q − 1}ⁿ without exceeding a Kullback-Leibler divergence of δ. Our analysis covers discrete restricted Boltzmann machines and naïve Bayes models as special cases.