Universal Approximation Depth and Errors of Narrow Belief Networks with Discrete Units
This provides theoretical guarantees for discrete deep belief networks, which is incremental as it extends prior binary-unit results to more general settings.
The paper generalizes theoretical bounds on the minimal depth of narrow deep belief networks to handle arbitrary finite-state discrete units and non-zero approximation error tolerances, showing that a network with L layers of width n can approximate any distribution on q-ary states within a Kullback-Leibler divergence of δ.
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; Montúfar 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-δ\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 $δ$. Our analysis covers discrete restricted Boltzmann machines and naïve Bayes models as special cases.