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

摘要

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 & Hinton, 2008; Le Roux & Bengio, 2008, 2010; Montúfar & 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 src="/ielx7/6720226/6855468/6855489/abstract_images/NECO_a_00601inline1.gif" /> layers of width src="/ielx7/6720226/6855468/6855489/abstract_images/NECO_a_00601inline2.gif" /> for some src="/ielx7/6720226/6855468/6855489/abstract_images/NECO_a_00601inline3.gif" /> can approximate any probability distribution on src="/ielx7/6720226/6855468/6855489/abstract_images/NECO_a_00601inline4.gif" /> without exceeding a Kullback-Leibler divergence of src="/ielx7/6720226/6855468/6855489/abstract_images/NECO_a_00601inline5.gif" />. Our analysis covers discrete restricted Boltzmann machines and naive Bayes models as special cases.