Discrete Restricted Boltzmann Machines
Authors: Guido F. Montufar, Jason Morton
ICLR 2013

Abstract: In this paper we describe discrete restricted Boltzmann machines: graphical probability models with bipartite interactions between discrete visible and hidden variables. These models generalize standard binary restricted Boltzmann machines and discrete na'ive Bayes models. For a given number of visible variables and cardinalities of their state spaces, we bound the number of hidden variables, depending on the cardinalities of their state spaces, for which the model is a universal approximator of probability distributions. More generally, we describe tractable exponential subfamilies and use them to bound the maximal and expected Kullback-Leibler approximation errors of these models from above. We discuss inference functions, mixtures of product distributions with shared parameters, and patterns of strong modes of probability distributions represented by discrete restricted Boltzmann machines in terms of configurations of projected products of simplices in normal fans of products of simplices. Finally, we use tropicalization and coding theory to study the geometry of these models, and show that in many cases they have the expected dimension but in some cases they do not. Keywords: expected dimension, tropical statistical model, distributed representation, q-ary variable, Kullback-Leibler divergence, hierarchical model, mixture model, Hadamard product, universal approximation, covering code

Discrete Restricted Boltzmann Machines
Guido Mont´ufar GFM 10@ PSU .EDU
Jason Morton MORTON @MATH .PSU .EDU
Department of Mathematics
Pennsylvania State University
University Park, PA 16802, USA
Abstract
We describe discrete restricted Boltzmann machines: probabilistic graphical models with bipar-
tite interactions between visible and hidden discrete variables. Examples are binary restricted
Boltzmann machines and discrete na ¨ıve Bayes models. We detail the inference functions and
distributed representations arising in these models in terms of conﬁgurations of projected prod-
ucts of simplices and normal fans of products of simplices. We bound the number of hidden
variables, depending on the cardinalities of their state spaces, for which these models can ap-
proximate any probability distribution on their visible states to any given accuracy. In addition,
we use algebraic methods and coding theory to compute their dimension.
Keywords: Restricted Boltzmann Machine, Na¨ıve Bayes Model, Representational Power, Dis-
tributed Representation, Expected Dimension
1 Introduction
A restricted Boltzmann machine (RBM) is a probabilistic graphical model with bipartite interactions
between an observed set and a hidden set of units [see Smolensky, 1986, Freund and Haussler,
1991, Hinton, 2002, 2010]. A characterizing property of these models is that the observed units
are independent given the states of the hidden units and vice versa. This is a consequence of the
bipartiteness of the interaction graph and does not depend on the units’ state spaces. Typically
RBMs are deﬁned with binary units, but other types of units have also been considered, including
continuous, discrete, and mixed type units [see Welling et al., 2005, Marks and Movellan, 2001,
Salakhutdinov et al., 2007, Dahl et al., 2012, Tran et al., 2011]. We study discrete RBMs, also called
multinomial or softmax RBMs, which are special types of exponential family harmoniums [Welling
et al., 2005]. While each unit Xi of a binary RBM has the state space {0,1}, the state space of
each unit Xi of a discrete RBM is a ﬁnite set Xi = {0,1,...,r i −1}. Like binary RBMs, discrete
RBMs can be trained using contrastive divergence (CD) [Hinton, 1999, 2002, Carreira-Perpi˜nan and
Hinton, 2005] or expectation-maximization (EM) [Dempster et al., 1977] and can be used to train
the parameters of deep systems layer by layer [Hinton et al., 2006, Bengio et al., 2007].
Non-binary visible units are natural because they can directly encode non-binary features. The
situation with hidden units is more subtle. States that appear in different hidden units can be acti-
1
arXiv:1301.3529v4  [stat.ML]  22 Apr 2014
MONT ´UFAR AND MORTON
2 2 2 2
2 2 2 2
⊆
2 2 2 2
2 2 2 2
⊆
8 2
2 2 2 2
⊆
16
2 2 2 2
2 2 2 2
2 2 2 2
⊆
2 2 2 2
2 2 2 2
⊆
8 2
2 2 2 2
⊆
16
2 2 2 2
24 40 79
Figure 1: Examples of probability models treated in this paper, in the special case of binary visible
variables. The light (dark) nodes represent visible (hidden) variables with the indicated number of
states. The total parameter count of each model is indicated at the top. From left to right: a binary
RBM; a discrete RBM with one 8-valued and one binary hidden units; and a binary na ¨ıve Bayes
model with 16 hidden classes.
vated by the same visible vector, but states that appear in the same hidden unit are mutually exclu-
sive. Non-binary hidden units thus allow one to explicitly represent complex exclusive relationships.
For example, a discrete RBM topic model would allow some topics to be mutually exclusive and
other topics to be mixed together freely. This provides a better match to the semantics of several
learning problems, although the learnability of such representations is mostly open. The practical
need to represent mutually exclusive properties is evidenced by the common approach of adding
activation sparsity parameters to binary RBM hidden states, which artiﬁcially create mutually ex-
clusive non-binary states by penalizing models which have more than a certain percentage of hidden
units active.
A discrete RBM is a product of experts [Hinton, 1999]; each hidden unit represents an expert
which is a mixture model of product distributions, or na¨ıve Bayes model. Hence discrete RBMs cap-
ture both na¨ıve Bayes models and binary RBMs, and interpolate between non-distributed mixture
representations and distributed mixture representations [Bengio, 2009, Mont´ufar and Morton, 2012].
See Figure 1. Na¨ıve Bayes models have been studied across many disciplines. In machine learning
they are most commonly used for classiﬁcation and clustering, but have also been considered for
probabilistic modelling [Lowd and Domingos, 2005, Mont ´ufar, 2013]. Theoretical work on binary
RBM models includes results on universal approximation [Freund and Haussler, 1991, Le Roux
and Bengio, 2008, Mont ´ufar and Ay, 2011], dimension and parameter identiﬁability [Cueto et al.,
2010], Bayesian learning coefﬁcients [Aoyagi, 2010], complexity [Long and Servedio, 2010], and
approximation errors [Mont´ufar et al., 2011]. In this paper we generalize some of these theoretical
results to discrete RBMs.
Probability models with more general interactions than strictly bipartite have also been consid-
ered, including semi-restricted Boltzmann machines and higher-order interaction Boltzmann ma-
chines [see Sejnowski, 1986, Memisevic and Hinton, 2010, Osindero and Hinton, 2008, Ranzato
et al., 2010]. The techniques that we develop in this paper also serve to treat a general class of
RBM-like models allowing within-layer interactions, a generalization that will be carried out in a
forthcoming work [Mont´ufar and Morton, 2013].
Section 2 collects basic facts about independence models, na ¨ıve Bayes models, and binary
RBMs, including an overview on the aforementioned theoretical results. Section 3 deﬁnes discrete
RBMs formally and describes them as (i) products of mixtures of product distributions (Proposi-
tion 7) and (ii) as restricted mixtures of product distributions. Section 4 elaborates on distributed
representations and inference functions represented by discrete RBMs (Proposition 11, Lemma 12,
2
DISCRETE RESTRICTED BOLTZMANN MACHINES
ex1=1
ex2=1
ex3=1
ex1=1
ex1=2
ex2=1
Figure 2: The convex support of the independence model of three binary variables (left) and of a
binary-ternary pair of variables (right) discussed in Example 1.
and Proposition 14). Section 5 addresses the expressive power of discrete RBMs by describing
explicit submodels (Theorem 15) and provides results on their maximal approximation errors and
universal approximation properties (Theorem 16). Section 6 treats the dimension of discrete RBM
models (Proposition 17 and Theorem 19). Section 7 contains an algebraic-combinatorial discussion
of tropical discrete RBM models (Theorem 21) with consequences for their dimension collected in
Propositions 24, 25, and 26.
2 Preliminaries
2.1 Independence models
Consider a system of n <∞random variables X1,...,X n. Assume that Xi takes states xi in a
ﬁnite set Xi = {0,1,...,r i −1}for all i ∈{1,...,n }=: [n]. The state space of this system is
X:= X1 ×···×X n. We write xλ = (xi)i∈λ for a joint state of the variables with index i∈λfor
any λ⊆[n], and x= (x1,...,x n) for a joint state of all variables. We denote by ∆(X) the set of
all probability distributions on X. We write ⟨a,b⟩for the inner product a⊤b.
The independence model of the variables X1,...,X n is the set of product distributions p(x) =∏
i∈[n] pi(xi) for all x∈X, where pi is a probability distribution with state space Xi for all i∈[n].
This model is the closure EX (in the Euclidean topology) of the exponential family
EX :=
{ 1
Z(θ) exp(⟨θ,A(X)⟩): θ∈RdX
}
, (1)
where A(X) ∈RdX×X is a matrix of sufﬁcient statistics; with rows equal to the indicator functions
1X and 1{x: xi=yi}for all yi ∈Xi \{0}for all i ∈[n]. The partition function Z(θ) normalizes
the distributions. The convex support of EX is the convex hull QX := conv({A(X)
x }x∈X) of the
columns of A(X), which is a Cartesian product of simplices with QX ∼= ∆(X1) ×···× ∆(Xn).
Example 1. The sufﬁcient statistics of the independence models EX and EX′ with state spaces
3
MONT ´UFAR AND MORTON
X= {0,1}3 and X′= {0,1,2}×{0,1}are, with rows labeled by indicator functions,
A(X) =
[1
1
1
] [1
1
0
] [1
0
1
] [1
0
0
] [0
1
1
] [0
1
0
] [0
0
1
] [0
0
0
]


1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 0
1 1 0 0 1 1 0 0
1 0 1 0 1 0 1 0

x3 = 1
x2 = 1
x1 = 1
A(X′) =
[1
2
] [1
1
] [1
0
] [0
2
] [0
1
] [0
0
]


1 1 1 1 1 1
1 1 1 0 0 0
1 0 0 1 0 0
0 1 0 0 1 0


x2 = 1
x1 = 2
x1 = 1
.
In the ﬁrst case the convex support is a cube and in the second it is a prism. Both convex supports
are three-dimensional polytopes, but the prism has fewer vertices and is more similar to a simplex,
meaning that its vertex set is afﬁnely more independent than that of the cube. See Figure 2.
2.2 Na ¨ıve Bayes models
Let k∈N. The k-mixture of the independence model, or na¨ıve Bayes modelwith khidden classes,
with visible variables X1,...,X n is the set of all probability distributions expressible as convex
combinations of kpoints in EX:
MX,k :=
{∑
i∈[k]
λip(i) : p(i) ∈EX, λi ≥0, for all i∈[k], and
∑
i∈[k]
λi = 1
}
. (2)
We write Mn,k for the k-mixture of the independence model of nbinary variables. The dimen-
sions of mixtures of binary independence models are known:
Theorem 2 (Catalisano et al. [2011]). The mixtures of binary independence models Mn,k have the
dimension expected from counting parameters,min{nk+ (k−1),2n−1}, except for M4,3, which
has dimension 13 instead of 14.
Let AX(d) denote the maximal cardinality of a subset X′⊆X of minimum Hamming distance
at least d, i.e., the maximal cardinality of a subset X′⊆X with dH(x,y) ≥dfor all distinct points
x,y ∈X′, where dH(x,y) := |{i∈[n]: xi ̸= yi}|denotes the Hamming distance betweenxand y.
The function AXis familiar in coding theory. Thek-mixtures of independence models are universal
approximators when kis large enough. This can be made precise in terms of AX(2):
Theorem 3 (Mont´ufar [2013]). The mixture model MX,k can approximate any probability distri-
bution on Xarbitrarily well if k≥|X|/maxi∈[n] |Xi|and only if k≥AX(2).
By results from [Gilbert, 1952, Varshamov, 1957], when q is a power of a prime number and
X= {0,1,...,q −1}n, then AX = qn−1. In these cases the previous theorem shows that MX,k
is a universal approximator of distributions on Xif and only if k ≥qn−1. In particular, the small-
est na¨ıve Bayes model universal approximator of distributions on {0,1}n has 2n−1(n+ 1) −1
parameters.
Some of the distributions not representable by a given na¨ıve Bayes model can be characterized
in terms of their modes. A state x∈X is a mode of a distribution p∈∆(X) if p(x) >p(y) for all
ywith dH(x,y) = 1 and it is a strong mode if p(x) >∑
y: dH(x,y)=1 p(y).
Lemma 4 (Mont´ufar and Morton [2012]). If a mixture of product distributions p = ∑
iλip(i) has
strong modes C⊆X , then there is a mixture component p(i) with mode xfor each x∈C.
4
DISCRETE RESTRICTED BOLTZMANN MACHINES
2.3 Binary restricted Boltzmann machines
The binary RBM model with nvisible and mhidden units, denoted RBMn,m, is the set of distribu-
tions on {0,1}n of the form
p(x) = 1
Z(W,B,C )
∑
h∈{0,1}m
exp(h⊤Wx + B⊤x+ C⊤h) for all x∈{0,1}n, (3)
where xdenotes states of the visible units, hdenotes states of the hidden units, W = (Wji)ji ∈
Rm×n is a matrix of interaction weights, B ∈Rn and C ∈Rm are vectors of bias weights, and
Z(W,B,C ) = ∑
x∈{0,1}n
∑
h∈{0,1}m exp(h⊤Wx + B⊤x+ C⊤h) is the normalizing partition
function.
It is known that these models have the expected dimension for many choices of nand m:
Theorem 5 (Cueto et al. [2010]). The dimension of the model RBMn,m is equal to nm+ n+ m
when m+ 1 ≤2n−⌈log2(n+1)⌉and it is equal to 2n −1 when m≥2n−⌊log2(n+1)⌋.
It is also known that with enough hidden units, binary RBMs are universal approximators:
Theorem 6 (Mont´ufar and Ay [2011]). The model RBMn,m can approximate any distribution on
{0,1}n arbitrarily well whenever m≥2n−1 −1.
A previous result by Le Roux and Bengio [2008, Theorem 2] shows thatRBMn,m is a universal
approximator wheneverm≥2n+1. It is not known whether the bounds from Theorem 6 are always
tight, but they show that for any given n, the smallest RBM universal approximator of distributions
on {0,1}n has at most 2n−1(n+ 1) −1 parameters and hence not more than the smallest na ¨ıve
Bayes model universal approximator (Theorem 3).
3 Discrete restricted Boltzmann machines
Let Xi = {0,1,...,r i−1}for all i∈[n] and Yj = {0,1,...,s j−1}for all j ∈[m]. The graphical
model with full bipartite interactions {{i,j}: i∈[n],j ∈[m]}on X×Y is the exponential family
EX,Y:=
{ 1
Z(θ) exp(⟨θ,A(X,Y)⟩): θ∈RdXdY
}
, (4)
with sufﬁcient statistics matrix equal to the Kronecker product A(X,Y) = A(X) ⊗A(Y) of the
sufﬁcient statistics matrices A(X) and A(Y) of the independence models EX and EY. The matrix
A(X,Y) has dXdY =
(∑
i∈[n](|Xi|−1) + 1
)(∑
j∈[m](|Yi|−1) + 1
)
linearly independent rows
and |X×Y| columns, each column corresponding to a joint state (x,y) of all variables. Disregard-
ing the entry of θ that is multiplied with the constant row of A(X,Y), which cancels out with the
normalization function Z(θ), this parametrization of EX,Y is one-to-one. In particular, this model
has dimension dim(EX,Y) = dXdY−1.
The discrete RBM model RBMX,Yis the following set of marginal distributions:
RBMX,Y:=
{
q(x) =
∑
y∈Y
p(x,y) for all x∈X : p∈EX,Y
}
. (5)
5
MONT ´UFAR AND MORTON
In the case of one single hidden unit, this model is the na¨ıve Bayes model onXwith |Y1|hidden
classes. When all units are binary, X = {0,1}n and Y= {0,1}m, this model is RBMn,m. Note
that the exponent in eq. (3) can be written as (h⊤Wx + B⊤x+ C⊤h) = ⟨θ,A(X,Y)
(x,h) ⟩, taking for θ
the column-by-column vectorization of the matrix
(0 B⊤
C W
)
.
Conditional distributions
The conditional distributions of discrete RBMs can be described in the following way. Consider a
vector θ ∈RdXdY parametrizing EX,Y, and the matrix Θ ∈RdY×dX with column-by-column vec-
torization equal toθ. A lemma by Roth [1934] shows thatθ⊤(A(X)⊗A(Y))(x,y) = (A(X)
x )⊤Θ⊤A(Y)
y
for all x∈X, y∈Y, and hence
⣨
θ,A(X,Y)
(x,y)
⟩
=
⣨
ΘA(X)
x ,A(Y)
y
⟩
=
⣨
Θ⊤A(Y)
y ,A(X)
x
⟩
∀x∈X,y ∈Y. (6)
The inner product in eq. (6) describes following probability distributions:
pθ(·,·) = 1
Z(θ) exp
(⟨
θ,A(X,Y)⟩)
, (7)
pθ(·|x) = 1
Z
(
ΘA(X)
x
)exp
(⟨
ΘA(X)
x ,A(Y)⟩)
, and (8)
pθ(·|y) = 1
Z
(
Θ⊤A(Y)
y
)exp
(⟨
Θ⊤A(Y)
y ,A(X)⟩)
. (9)
Geometrically, ΘA(X) is a linear projection of the columns of the sufﬁcient statistics matrix A(X)
into the parameter space of EY, and similarly, Θ⊤A(Y) is a linear projection of the columns of A(Y)
into the parameter space of EX.
Polynomial parametrization
Discrete RBMs can be parametrized not only in the exponential way discussed above, but also by
simple polynomials. The exponential family EX,Ycan be parametrized by square free monomials:
p(v,h) = 1
Z
∏
{j,i}∈ [m] ×[n],
(y′
j,x′
i) ∈Yj ×Xi
(γ{j,i},(y′
j,x′
i))
δy′
j
(hj)δx′
i
(vi)
for all (v,h) ∈Y×X , (10)
where γ{j,i},(y′
j,x′
i) are positive reals. The probability distributions in RBMX,Ycan be written as
p(v) = 1
Z
∏
j∈[m]
( ∑
hj∈Yj
γ{j,1},(hj,v1) ···γ{j,n},(hj,vn)
)
for all v∈X. (11)
The parameters γ{j,i},(y′
j,x′
i) correspond to exp(θ{j,i},(y′
j,x′
i)) in the parametrization given in eq. (4).
6
DISCRETE RESTRICTED BOLTZMANN MACHINES
Products of mixtures and mixtures of products
In the following we describe discrete RBMs from two complementary perspectives: (i) as products
of experts, where each expert is a mixture of products, and (ii) as restricted mixtures of product
distributions. The renormalized entry-wise (Hadamard) product of two probability distributions p
and qon Xis deﬁned as p◦q := (p(x)q(x))x∈X/∑
y∈Xp(y)q(y). Here we assume that pand q
have overlapping supports, such that the deﬁnition makes sense.
Proposition 7. The model RBMX,Yis a Hadamard product of mixtures of product distributions:
RBMX,Y= MX,|Y1|◦···◦M X,|Ym|.
Proof. The statement can be seen directly by considering the parametrization from eq. (11). To
make this explicit, one can use a homogeneous version of the matrix A(X,Y) which we denote by
Aand which deﬁnes the same model. Each row of Ais indexed by an edge {i,j}of the bipartite
graph and a joint state (xi,hj) of the visible and hidden units connected by this edge. Such a row
has a one in any column when these states agree with the global state, and zero otherwise. For any
j ∈[m] let Aj,: denote the matrix containing the rows of Awith indices ({i,j},(xi,hj)) for all
xi ∈Xi for all i∈[n] for all hj ∈Yj, and let A(x,h) denote the (x,h)-column of A. We have
p(x) = 1
Z
∑
h
exp(⟨θ,A(x,h)⟩)
= 1
Z
∑
h
exp(⟨θ1,:,A1,:(x,h)⟩) exp(⟨θ2,:,A2,:(x,h)⟩) ···exp(⟨θm,:,Am,:(x,h)⟩)
= 1
Z
(∑
h1
exp(⟨θ1,:,A1,:(x,h1)⟩)
)
···
(∑
hm
exp(⟨θm,:,Am,:(x,hm)⟩)
)
= 1
Z(Z1p(1)(x)) ···(Zmp(m)(x)) = 1
Z′p(1)(x) ···p(m)(x),
where p(j) ∈MX,|Yj|and Zj = ∑
x∈X
∑
hj∈Yj exp(⟨θj,:,Aj,:(x,hj)⟩) for all j ∈[m]. Since the
vectors θj,: can be chosen arbitrarily, the factors p(j) can be made arbitrary within MX,|Yj|.
Of course, every distribution in RBMX,Y is a mixture distribution p(x) = ∑
h∈Yp(x|h)q(h).
The mixture weights are given by the marginals q(h) on Yof distributions from EX,Y, and the
mixture components can be described as follows.
Proposition 8. The set of conditional distributions p(·|h), h∈Y of a distribution in EX,Yis the set
of product distributions in EX with parameters θh = Θ⊤A(Y)
h , h ∈Y equal to a linear projection
of the vertices {A(Y)
h : h∈Y} of the Cartesian product of simplices QY∼= ∆(Y1) ×···× ∆(Ym).
Proof. This is by eq. (6).
4 Products of simplices and their normal fans
Binary RBMs have been analyzed by considering each of the mhidden units as deﬁning a hyper-
plane Hj slicing the n-cube into two regions. To generalize the results provided by this analysis, in
7
MONT ´UFAR AND MORTON
/Bullet /Bullet 
/Bullet /Bullet 
/Bullet /Bullet 
/Bullet /Bullet 
/Bullet /Bullet 
/Bullet /Bullet 
/Bullet /Bullet 
/Bullet 
R0
R1
R2
0
1
2(0,0) (0,1)
(1,0) (1 ,1)
Θ−1(R2)
Θ−1(R1)
Θ−1(R0)
Figure 3: Three slicings of a square by the normal fan of a triangle with maximal conesR0, R1, and
R2, corresponding to three possible inference functions of RBM{0,1}2,{0,1,2}.
this section we replace the n-cube with a general product of simplices QX, and replace the two re-
gions deﬁned by the hyperplane Hj by the |Yj|regions deﬁned by the maximal cones of the normal
fan of the simplex ∆(Yj).
Subdivisions of independence models
The normal cone of a polytope Q ⊂Rd at a point x ∈Q is the set of all vectors v ∈Rd with
⟨v,(x−y)⟩≥ 0 for all y ∈Q. We denote by Rx the normal cone of the product of simplices
QX = conv{A(X)
x }x∈X at the vertex A(X)
x . The normal fan FX is the set of all normal cones of
QX. The product distributions pθ = 1
Z(θ) exp(⟨θ,A(X)⟩) ∈EX strictly maximized at x∈X, with
pθ(x) >pθ(y) for all y∈X\{ x}, are those with parameter vector θin the relative interior of Rx.
Hence the normal fan FX partitions the parameter space of the independence model into regions of
distributions with maxima at different inputs.
Inference functions and slicings
For any choice of parameters of the model RBMX,Y, there is an inference function π: X →Y,
(or more generally π: X→ 2Y), which computes the most likely hidden state given a visible state.
These functions are not necessarily injective nor surjective. For a visible state x, the conditional
distribution on the hidden states is a product distribution p(y|X = x) = 1
Z exp(⟨ΘA(X)
x ,A(Y)
y ⟩)
which is maximized at the state yfor which ΘA(X)
x ∈Ry. The preimages of the cones Ry by the
map Θ partition the input spaceRdX and are called inference regions. See Figure 3 and Example 10.
Deﬁnition 9. A Y-slicing of a ﬁnite set Z⊂ RdX is a partition of Zinto the preimages of the cones
Ry, y ∈Y by a linear map Θ: RdX →RdY. We assume that Θ is generic, such that it maps each
element of Zinto the interior of some Ry.
For example, when Y= {0,1}, the fan FY consists of a hyperplane and the two closed half-
spaces deﬁned by that hyperplane. A Y-slicing is in this case a standard slicing by a hyperplane.
Example 10. Let X = {0,1,2}×{ 0,1}and Y = {0,1}4. The maximal cones Ry, y ∈Y of
the normal fan of the 4-cube with vertices {0,1}4 are the closed orthants of R4. The 6 vertices
{A(X)
x : x ∈ X}of the prism ∆({0,1,2}) ×∆({0,1}) can be mapped into 6 distinct orthants
8
DISCRETE RESTRICTED BOLTZMANN MACHINES
of R4, each orthant with an even number of positive coordinates:


3 −2 −2 −2
1 2 −2 −2
1 −2 −2 2
1 −2 2 −2


Θ


1 1 1 1 1 1
1 1 1 0 0 0
1 0 0 1 0 0
0 1 0 0 1 0


A(X)
=


−1 −1 1 1 1 3
1 1 3 −1 −1 1
−3 1 −1 −1 3 1
1 −3 −1 3 −1 1

. (12)
Even in the case of one single hidden unit the slicings can be complex, but the following simple
type of slicing is always available.
Proposition 11. Any slicing by k−1 parallel hyperplanes is a {1,2,...,k }-slicing.
Proof. We show that there is a line L= {λr−b: λ ∈R}, r,b ∈Rk intersecting all cells of FY,
Y= {1,...,k }. We need to show that there is a choice of rand bsuch that for every y∈Y the set
Iy ⊆R of all λwith ⟨λr−b,(ey −ez)⟩>0 for all z∈Y\{ y}has a non-empty interior. Now, Iy
is the set of λwith
λ(ry −rz) >by −bz for all z̸= y. (13)
Choosing b1 < ··· < bk and ry = f(by), where f is a strictly increasing and strictly concave
function, we get I1 = (−∞,b2−b1
r2−r1
), Iy = ( by−by−1
ry−ry−1
,by+1−by
ry+1−ry ) for y = 2,3,...,k −1, and Ik =
(bk−bk−1
rk−rk−1
,∞). The lengths ∞,l2,...,l k−1,∞of the intervals I1,...,I k can be adjusted arbitrarily
by choosing suitable differences rj+1 −rj for all j = 1,...,k −1.
Strong modes
Recall the deﬁnition of strong modes given in page 4.
Lemma 12. Let C⊆X be a set of arrays which are pairwise different in at least two entries (a
code of minimum distance two).
•If RBMX,Y contains a probability distribution with strong modes C, then there is a linear
map Θ of {A(Y)
y : y ∈Y} into the C-cells of FX (the cones Rx above the codewords x∈C)
sending at least one vertex into each cell.
•If there is a linear mapΘ of {A(Y)
y : y∈Y} into the C-cells of FX, with maxx{⟨Θ⊤A(Y)
y ,A(X)
x ⟩}=
cfor all y∈Y, then RBMX,Ycontains a probability distribution with strong modes C.
Proof. This is by Proposition 8 and Lemma 4.
A simple consequence of the previous lemma is that if the model RBMX,Y is a universal ap-
proximator of distributions on X, then necessarily the number of hidden states is at least as large as
the maximum code of visible states of minimum distance two,|Y|≥ AX(2). Hence discrete RBMs
may not be universal approximators even when their parameter count surpasses the dimension of
the ambient probability simplex.
Example 13. Let X= {0,1,2}nand Y= {0,1,..., 4}m. In this case AX(2) = 3n−1. If RBMX,Y
is a universal approximator with n= 3 and n= 4, then m≥2 and m≥3, respectively, although
the smallest mfor which RBMX,Yhas 3n −1 parameters is m= 1 and m= 2, respectively.
Using Lemma 12 and the analysis of [Mont´ufar and Morton, 2012] gives the following.
Proposition 14. If 4⌈m/3⌉≤ n, then RBMX,Ycontains distributions with 2m strong modes.
9
MONT ´UFAR AND MORTON
5 Representational power and approximation errors
In this section we describe submodels of discrete RBMs and use them to provide bounds on the
model approximation errors depending on the number of units and their state spaces. Universal
approximation results follow as special cases with vanishing approximation error.
Theorem 15. The model RBMX,Ycan approximate the following arbitrarily well:
•Any mixture of dY= 1 + ∑m
j=1(|Yj|−1) product distributions with disjoint supports.
•When dY ≥(∏
i∈[k] |Xi|)/maxj∈[k] |Xj|for some k ≤n, any distribution from the model P
of distributions with constant value on each block {x1}×···×{ xk}×Xk+1 ×···×X n for
all xi ∈Xi, for all i∈[k].
•Any probability distribution with support contained in the union ofdYsets of the form {x1}×
···×{ xk−1}×Xk ×{xk+1}×···×{ xn}.
Proof. By Proposition 7 the model RBMX,Y contains any Hadamard product p(1) ◦···◦ p(m)
with mixtures of products as factors, p(j) ∈ MX,|Yj| for all j ∈[m]. In particular, it contains
p= p(0) ◦(1 + ˜λ1 ˜p(1)) ◦···◦ (1 + ˜λm˜p(m)), where p(0) ∈EX, ˜p(j) ∈MX,|Yj|−1, and ˜λj ∈R+.
Choosing the factors ˜p(j) with pairwise disjoint supports shows thatp= ∑m
j=0 λjp(j), whereby p(0)
can be any product distribution and p(j) can be any distribution from MX,|Yj|−1 for all j ∈[m], as
long as supp(p(j)) ∩supp(p(j′)) for all j ̸= j′. This proves the ﬁrst item.
For the second item: Any point in the set Pis a mixture of uniform distributions supported
on the disjoint blocks {x1}×···×{ xk}×X k+1 ×···×X n for all (x1,...,x k) ∈X1 ×···×
Xk. Each of these uniform distributions is a product distribution, since it factorizes as px1,...,xk =∏
i∈[k] δxi
∏
i∈[n]\[k] ui, where ui denotes the uniform distribution on Xi. For any j ∈ [k] any
mixture ∑
xj∈Xj λxj px1,...,xk is also a product distribution, since it factorizes as
( ∑
xj∈Xj
λxj δxj
) ∏
i∈[k]\{j}
δxi
∏
i∈[n]\[k]
ui. (14)
Hence any distribution from the set Pis a mixture of (∏
i∈[k] |Xi|)/maxj∈[k] |Xj|product distribu-
tions with disjoint supports. The claim now follows from the ﬁrst item.
For the third item: The modelEXcontains any distribution with support of the form{x1}×···×
{xk−1}×Xk ×{xk+1}×···×{ xn}. Hence, by the ﬁrst item, the RBM model can approximate
any distribution arbitrarily well whose support can be covered by dYsets of that form.
We now analyse the RBM model approximation errors. Let pand qbe two probability distribu-
tions on X. The Kullback-Leibler divergence frompto qis deﬁned as D(p∥q) := ∑
x∈Xp(x) log p(x)
q(x)
when supp(p) ⊆ supp(q) and D(p∥q) := ∞otherwise. The divergence from p to a model
M ⊆∆(X) is deﬁned as D(p∥M) := inf q∈MD(p∥q) and the maximal approximation error
of Mis supp∈∆(X) D(p∥M).
The maximal approximation error of the independence modelEXsatisﬁes supp∈∆(X) D(p∥EX) ≤
|X|/maxi∈[n] |Xi|, with equality when all units have the same number of states [see Ay and Knauf,
2006, Corollary 4.10].
10
DISCRETE RESTRICTED BOLTZMANN MACHINES
 
 
0 100 200 300 400 500
100
200
300
400
500
 
 
0 100 200 300 400 500
100
200
300
400
500
0.5
1
1.5
2
2.5
x 10
7
82
84
86
88
90
92
94
96
98
k
m
Maximal-error bound
k
m
Nr. parameters
Figure 4: Illustration of Theorem 16. The left panel shows a heat map of the upper bound on the
Kullback-Leibler approximation errors of discrete RBMs with 100 visible binary units and the right
panel shows a map of the total number of model parameters, both depending on the number of
hidden units mand their possible states k= |Yj|for all j ∈[m].
Theorem 16. If ∏
i∈[n]\Λ |Xi|≤ 1 +∑
j∈[m](|Yj|−1) = dYfor some Λ ⊆[n], then the Kullback-
Leibler divergence from any distribution pon Xto the model RBMX,Yis bounded by
D(p∥RBMX,Y) ≤log
∏
i∈Λ |Xi|
maxi∈Λ |Xi|.
In particular, the model RBMX,Yis a universal approximator whenever dY≥|X|/maxi∈[n] |Xi|.
Proof. The submodel Pof RBMX,Y described in the second item of Theorem 15 is a partition
model. The maximal divergence from such a model is equal to the logarithm of the cardinality of
the largest block with constant values [see Mat ´uˇs and Ay, 2003]. Thus maxpD(p∥RBMX,Y) ≤
maxpD(p∥P) = log
(
(∏
i∈Λ |Xi|)/maxi∈Λ |Xi|
)
, as was claimed.
Theorem 16 shows that, on a large scale, the maximal model approximation error ofRBMX,Yis
smaller than that of the independence model EXby at least log(1 +∑
j∈[m](|Yj|−1)), or vanishes.
The theorem is illustrated in Figure 4. The line k = 2 shows bounds on the approximation error of
binary RBMs with mhidden units, previously treated in [Mont ´ufar et al., 2011, Theorem 5.1], and
the line m= 1 shows bounds for na¨ıve Bayes models withkhidden classes.
6 Dimension
In this section we study the dimension of the model RBMX,Y. One reason RBMs are attractive is
that they have a large learning capacity, e.g. may be built with millions of parameters. Dimension
calculations show whether those parameters are wasted, or translate into higher-dimensional spaces
of representable distributions. Our analysis builds on previous work by Cueto, Morton, and Sturm-
fels [2010], where binary RBMs are treated. The idea is to bound the dimension from below by
the dimension of a related max-plus model, called the tropical RBM model [Pachter and Sturmfels,
2004], and from above by the dimension expected from counting parameters.
11
MONT ´UFAR AND MORTON
The dimension of a discrete RBM model can be bounded from above not only by its expected
dimension, but also by a function of the dimension of its Hadamard factors:
Proposition 17. The dimension of RBMX,Yis bounded as
dim(RBMX,Y) ≤dim(MX,|Yi|) +
∑
j∈[m]\{i}
dim(MX,|Yj|−1) + (m−1) for all i∈[m]. (15)
Proof. Let udenote the uniform distribution. Note thatEX◦EX = EXand also EX◦MX,k = MX,k.
This observation, together with Proposition 7, shows that the RBM model can be factorized as
RBMX,Y= (MX,|Y1|) ◦(λ1u+ (1 −λ1)MX,|Y1|) ◦···◦ (λmu+ (1 −λm)MX,|Ym|−1),
from which the claim follows.
By the previous proposition, the model RBMX,Y can have the expected dimension only if (i)
the right hand side of eq. (15) equals |X|− 1, or (ii) each mixture model MX,k has the expected
dimension for allk≤maxj∈[m] |Yj|. Sometimes none of both conditions is satisﬁed and the models
‘waste’ parameters:
Example 18. The k-mixture of the independence model on X1 ×X2 is a subset of the set of
|X1|×|X 2|matrices with non-negative entries and rank at most k. It is known that the set of
M ×N matrices of rank at most k has dimension k(M + N −k) for all 1 ≤k <min{M,N }.
Hence the model MX1×X2,k has dimension smaller than its parameter count whenever 1 < k <
min{|X1|,|X2|}. By Proposition 17 if (∑
j∈[m](|Yj|−1) + 1)(|X1|+ |X2|−1) ≤|X1 ×X2|and
1 < |Yj|≤ min{|X1|,|X2|}for some j ∈[m], then RBMX1×X2,Y does not have the expected
dimension.
The next theorem indicates choices of Xand Yfor which the model RBMX,Yhas the expected
dimension. Given a sufﬁcient statistics matrix A(X), we say that a set Z⊆X has full rank when
the matrix with columns {A(X)
x : x∈Z} has full rank.
Theorem 19. When Xcontains mdisjoint Hamming balls of radii 2(|Yj|−1) −1, j ∈[m] and
the subset of Xnot intersected by these balls has full rank, then the model RBMX,Yhas dimension
equal to the number of model parameters,
dim(RBMX,Y) = (1 +
∑
i∈[n]
(|Xi|−1))(1 +
∑
j∈[m]
(|Yj|−1)) −1.
On the other hand, if mHamming balls of radius one cover X, then
dim(RBMX,Y) = |X|− 1.
In order to prove this theorem we will need two main tools: slicings by normal fans of simplices,
described in Section 4, and the tropical RBM model, described in Section 7. The theorem will follow
from the analysis contained in Section 7.
12
DISCRETE RESTRICTED BOLTZMANN MACHINES
7 Tropical model
Deﬁnition 20. The tropical model RBMtropical
X,Y is the image of the tropical morphism
RdXdY ∋θ ↦→ Φ(v; θ) = max{⟨θ,A(X,Y)
(v,h) ⟩: h∈Y} for all v∈X, (16)
which evaluates log( 1
Z(θ)
∑
h∈Yexp(⟨θ,A(X,Y)
(v,h) ⟩)) for all v ∈X for each θ within the max-plus
algebra (addition becomes a+ b = max {a,b}) up to additive constants independent of v (i.e.,
disregarding the normalization factor Z(θ)).
The idea behind this deﬁnition is thatlog(exp(a)+exp(b)) ≈max{a,b}when aand bhave dif-
ferent order of magnitude. The tropical model captures important properties of the original model.
Of particular interest is following consequence of the Bieri-Groves theorem [see Draisma, 2008],
which gives us a tool to estimate the dimension of RBMX,Y:
dim(RBMtropical
X,Y ) ≤dim(RBMX,Y) ≤min{dim(EX,Y),|X|− 1}. (17)
The following Theorem 21 describes the regions of linearity of the map Φ. Each of these
regions corresponds to a collection of Yj-slicings (see Deﬁnition 9) of the set {A(X)
x : x ∈X} for
all j ∈[m]. This result allows us to express the dimension of RBMtropical
X,Y as the maximum rank of
a class of matrices deﬁned by collections of slicings.
For each j ∈[m] let Cj = {Cj,1,...,C j,|Yj|}be a Yj-slicing of {A(X)
x : x∈X} and let ACj,k
be the |X|× dX-matrix with x-th row equal to (A(X)
x )⊤when x∈Cj,k and equal to a row of zeros
otherwise. Let ACj = (ACj,1 |···| ACj,|Yj|) ∈R|X|×|Yj|dX and d= ∑
j∈[m] |Yj|dX.
Theorem 21. On each region of linearity, the tropical morphism Φ is the linear map Rd →
RBMtropical
X,Y represented by the |X|× d-matrix
A= (AC1 |···| ACm),
modulo constant functions. In particular, dim(RBMtropical
X,Y ) + 1 is the maximum rank of Aover all
possible collections of slicings C1,...,C m.
Proof. Again use the homogeneous version of the matrix A(X,Y) as in the proof of Proposition
7; this will not affect the rank of A. Let θhj = ( θ{j,i},(hj,xi))i∈[n],xi∈Xi and let Ahj denote the
submatrix of A(X,Y) containing the rows with indices {{j,i},(hj,xi): i∈[n],xi ∈Xi}. For any
given v∈X we have
max
{⟨
θ,A(X,Y)
(v,h)
⟩
: h∈Y
}
=
∑
j∈[m]
max
{⟨
θhj ,Ahj (v,hj)
⟩
: hj ∈Yj
}
,
from which the claim follows.
In the following we evaluate the maximum rank of the matrixAfor various choices of Xand Y
by examining good slicings. We focus on slicings by parallel hyperplanes.
Lemma 22. For any x∗∈X and 0 <k <n the afﬁne hull of the set {A(X)
x : dH(x,x∗) = k}has
dimension ∑
i∈[n](|Xi|−1) −1.
13
MONT ´UFAR AND MORTON
Proof. Without loss of generality let x∗ = (0,..., 0). The set Zk := {A(X)
x : dH(x,x∗) = k}is
the intersection of {A(X)
x : x ∈X} with the hyperplane Hk := {z: ⟨1,z⟩= k+ 1}. Now note
that the two vertices of an edge of QX either lie in the same hyperplane Hl, or in two adjacent
parallel hyperplanes Hl and Hl+1, with l ∈N. Hence the hyperplane Hk does not slice any edges
of QX and conv(Zk) = QX ∩Hk. The set Zk is not contained in any proper face of QX and
hence conv(Zk) intersects the interior of QX. Thus dim(conv(Zk)) = dim( QX) −1, as was
claimed.
Lemma 22 implies the following.
Corollary 23. Let x ∈X , and 2k−3 ≤n. There is a slicing C1 = {C1,1,...,C 1,k}of Xby
k−1 parallel hyperplanes such that ∪k−1
l=1 C1,l = Bx(2k−3) is the Hamming ball of radius 2k−3
centered at xand the matrix AC1 = (AC1,1 |···| AC1,k−1 ) has full rank.
Recall that AX(d) denotes the maximal cardinality of a subset of X of minimum Hamming
distance at least d. When X= {0,1,...,q −1}n we write Aq(n,d). Let KX(d) denote the minimal
cardinality of a subset of Xwith covering radius d.
Proposition 24 (Binary visible units) . Let X = {0,1}n and |Yj|= sj for all j ∈[m]. If X
contains mdisjoint Hamming balls of radii 2sj −3, j ∈[m] whose complement has full rank, then
RBMtropical
X,Y has the expected dimension, min{∑
j∈[m](sj −1)(n+ 1) +n,2n −1}.
In particular, ifX= {0,1}nand Y= {0,1,...,s −1}mwith m< A2(n,d) and d= 4(s−1)−
1, then RBMX,Yhas the expected dimension. It is known that A2(n,d) ≥2n−⌈log2(∑d−2
j=0 (n−1
j ))⌉.
Proposition 25 (Binary hidden units). Let Y= {0,1}m and Xbe arbitrary.
•If m+ 1 ≤AX(3), then RBMtropical
X,{0,1}m has dimension (1 + m)(1 + ∑
i∈[n](|Xi|−1)) −1.
•If m+ 1 ≥KX(1), then RBMtropical
X,{0,1}m has dimension |X|− 1.
Let Y= {0,1}m and X= {0,1,...,q −1}n, where qis a prime power.
•If m+ 1 ≤qn−⌈logq(1+(n−1)(q−1)+1)⌉, then RBMtropical
X,Y has dimension
(1 + m)(1 + ∑
i∈[n](|Xi|−1)) −1.
•If n = ( qr −1)/(q−1) for some r ≥2, then AX(3) = KX(1), and RBMtropical
X,Y has the
expected dimension for any m.
In particular, when all units are binary andm< 2n−⌈log2(n+1)⌉, then RBMX,Yhas the expected
dimension; this was shown in [Cueto et al., 2010].
Proposition 26 (Arbitrary sized units). If Xcontains mdisjoint Hamming balls of radii 2|Y1|−
3,..., 2|Ym|−3, and the complement of their union has full rank, thenRBMtropical
X,Y has the expected
dimension.
14
DISCRETE RESTRICTED BOLTZMANN MACHINES
Proof. Propositions 24, 25, and 26 follow from Theorem 21 and Corollary 23 together with the
following explicit bounds on A by [Gilbert, 1952, Varshamov, 1957]:
Aq(n,d) ≥ qn
∑d−1
j=0
(n
j
)
(q−1)j.
If qis a prime power, thenAq(n,d) ≥qk, where kis the largest integer withqk < qn
∑d−2
j=0 (n−1
j )(q−1)j .
In particular, A2(n,3) ≥2k, where k is the largest integer with 2k < 2n
(n−1)+1 = 2n−log2(n), i.e.,
k= n−⌈log2(n+ 1)⌉.
Example 27. Many results in coding theory can now be translated directly to statements about
the dimension of discrete RBMs. Here is an example. Let X = {1,2,...,s }×{ 1,2,...,s }×
{1,2,...,t }, s ≤t. The minimum cardinality of a code C ⊆X with covering-radius one equals
KX(1) = s2 −
⌊
(3s−t)2
8
⌋
if t ≤3s, and KX(1) = s2 otherwise [see Cohen et al., 2005, Theo-
rem 3.7.4]. Hence RBMtropical
X,{0,1}m has dimension |X|−1 when m+ 1 ≥s2 −
⌊
(3s−t)2
8
⌋
and t≤3s,
and when m+ 1 ≥s2 and t> 3s.
8 Discussion
In this note we study the representational power of RBMs with discrete units. Our results generalize
a diversity of previously known results for standard binary RBMs and na ¨ıve Bayes models. They
help contrasting the geometric-combinatorial properties of distributed products of experts versus
non-distributed mixtures of experts.
We estimate the number of hidden units for which discrete RBM models can approximate any
distribution to any desired accuracy, depending on the cardinalities of their units’ state spaces. This
analysis shows that the maximal approximation error increases at most logarithmically with the
total number of visible states and decreases at least logarithmically with the sum of the number of
states of the hidden units. This observation could be helpful, for example, in designing a penalty
term to allow comparison of models with differing numbers of units. It is worth mentioning that the
submodels of discrete RBMs described in Theorem 15 can be used not only to estimate the maximal
model approximation errors, but also the expected model approximation errors given a prior of target
distributions on the probability simplex. See [Mont ´ufar and Rauh, 2012] for an exact analysis of
Dirichlet priors. In future work it would be interesting to study the statistical approximation errors
of discrete RBMs and to complement the theory by an empirical evaluation.
The combinatorics of tropical discrete RBMs allows us to relate the dimension of discrete RBM
models to the solutions of linear optimization problems and slicings of convex support polytopes by
normal fans of simplices. We use this to show that the modelRBMX,Yhas the expected dimension
for many choices of Xand Y, but not for all choices. We based our explicit computations of the
dimension of RBMs on slicings by collections of parallel hyperplanes, but more general classes of
slicings may be considered. The same tools presented in this paper can be used to estimate the
dimension of a general class of models involving interactions within layers, deﬁned as Kronecker
products of hierarchical models [see Mont ´ufar and Morton, 2013]. We think that the geometric-
combinatorial picture of discrete RBMs developed in this paper may be helpful in solving various
long standing theoretical problems in the future, for example: What is the exact dimension of na¨ıve
15
MONT ´UFAR AND MORTON
Bayes models with general discrete variables? What is the smallest number of hidden variables that
make an RBM a universal approximator? Do binary RBMs always have the expected dimension?
Acknowledgments
We are grateful to the ICLR 2013 community for very valuable comments. This work was accom-
plished in part at the Max Planck Institute for Mathematics in the Sciences. This work is supported
in part by DARPA grant FA8650-11-1-7145.
References
M. Aoyagi. Stochastic complexity and generalization error of a Restricted Boltzmann Machine in
Bayesian estimation. J. Mach. Learn. Res., 99:1243–1272, August 2010.
N. Ay and A. Knauf. Maximizing multi-information. Kybernetika, 42(5):517–538, 2006.
Y . Bengio. Learning deep architectures for AI.Found. Trends Mach. Learn., 2(1):1–127, 2009.
Y . Bengio, P. Lamblin, D. Popovici, and H. Larochelle. Greedy layer-wise training of deep networks.
In B. Sch ¨olkopf, J. Platt, and T. Hoffman, editors, Advances in Neural Information Processing
Systems 19, pages 153–160. MIT Press, Cambridge, MA, 2007.
M. A. Carreira-Perpi ˜nan and G. E. Hinton. On contrastive divergence learning. In Proceedings of
the 10-th Interantional Workshop on Artiﬁcial Intelligence and Statistics, 2005.
M. V . Catalisano, A. V . Geramita, and A. Gimigliano. Secant varieties ofP1 ×···× P1 (n-times)
are not defective for n≥5. J. Algebraic Geometry, 20:295–327, 2011.
G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein. Covering Codes. North-Holland Mathematical
Library. Elsevier Science, 2005.
M. A. Cueto, J. Morton, and B. Sturmfels. Geometry of the restricted Boltzmann machine. In
M. Viana and H. Wynn, editors, Algebraic methods in statistics and probability II, AMS Special
Session, volume 2. American Mathematical Society, 2010.
G. E. Dahl, R. P. Adams, and H. Larochelle. Training restricted Boltzmann machines on word
observations. arXiv:1202.5695, 2012.
A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the
EM algorithm. Journal of the Royal Statistical Society. Series B (Methodological) , 39(1):1–38,
1977.
J. Draisma. A tropical approach to secant dimensions. J. Pure Appl. Algebra , 212(2):349–363,
2008.
Y . Freund and D. Haussler. Unsupervised learning of distributions of binary vectors using 2-layer
networks. In J. E. Moody, S. J. Hanson, and R. Lippmann, editors, Advances in Neural Informa-
tion Processing Systems 4, pages 912–919. Morgan Kaufmann, 1991.
16
DISCRETE RESTRICTED BOLTZMANN MACHINES
E. N. Gilbert. A comparison of signalling alphabets. Bell System Technical Journal, 31:504–522,
1952.
G. E. Hinton. Products of experts. In Proceedings 9-th ICANN, volume 1, pages 1–6, 1999.
G. E. Hinton. Training products of experts by minimizing contrastive divergence. Neural Compu-
tation, 14:1771–1800, 2002.
G. E. Hinton. A practical guide to training restricted Boltzmann machines, version 1. Technical
report, UTML2010-003, University of Toronto, 2010.
G. E. Hinton, S. Osindero, and Y . Teh. A fast learning algorithm for deep belief nets. Neural
Computation, 18:1527–1554, 2006.
N. Le Roux and Y . Bengio. Representational power of restricted Boltzmann machines and deep
belief networks. Neural Computation, 20(6):1631–1649, 2008.
P. M. Long and R. A. Servedio. Restricted Boltzmann machines are hard to approximately evaluate
or simulate. In J. F ¨urnkranz and T. Joachims, editors, Proceedings of the 27th International
Conference on Machine Learning (ICML-10), pages 703–710. Omnipress, 2010.
D. Lowd and P. Domingos. Naive Bayes models for probability estimation. In Proceedings of the
22nd International Conference on Machine Learning, pages 529–536. ACM Press, 2005.
T. K. Marks and J. R. Movellan. Diffusion networks, products of experts, and factor analysis. In
Proc. 3rd Int. Conf. Independent Component Anal. Signal Separation, pages 481–485, 2001.
F. Mat´uˇs and N. Ay. On maximization of the information divergence from an exponential family. In
Proceedings of the WUPES’03, pages 199–204. University of Economics, Prague, 2003.
R. Memisevic and G. E. Hinton. Learning to represent spatial transformations with factored higher-
order Boltzmann machines. Neural Computation, 22(6):1473–1492, June 2010.
G. Mont´ufar. Mixture decompositions of exponential families using a decomposition of their sample
spaces. Kybernetika, 49(1), 2013.
G. Mont ´ufar and N. Ay. Reﬁnements of universal approximation results for deep belief networks
and restricted Boltzmann machines. Neural Computation, 23(5):1306–1319, 2011.
G. Mont ´ufar and J. Morton. When does a mixture of products contain a product of mixtures?
http://arxiv.org/abs/1206.0387, 2012.
G. Mont´ufar and J. Morton. Geometry of hierarchical models on hidden-visible products of simpli-
cial complexes. 2013. In preparation.
G. Mont´ufar and J. Rauh. Scaling of model approximation errors and expected entropy distances.
In Proc. of the 9th Workshop on Uncertainty Processing (WUPES 2012), pages 137–148, 2012.
Preprint available at http://arxiv.org/abs/1207.3399.
G. Mont ´ufar, J. Rauh, and N. Ay. Expressive power and approximation errors of restricted Boltz-
mann machines. In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. C. N. Pereira, and K. Q. Weinberger,
editors, Advances in Neural Information Processing Systems 24, pages 415–423, 2011.
17
MONT ´UFAR AND MORTON
S. Osindero and G. E. Hinton. Modeling image patches with a directed hierarchy of Markov random
ﬁelds. In J. C. Platt, D. Koller, Y . Singer, and S. Roweis, editors,Advances in Neural Information
Processing Systems 20, pages 1121–1128. MIT Press, Cambridge, MA, 2008.
L. Pachter and B. Sturmfels. Tropical geometry of statistical models. Proceedings of the National
Academy of Sciences of the United States of America, 101(46):16132–16137, Nov. 2004.
M. Ranzato, A. Krizhevsky, and G. E. Hinton. Factored 3-Way Restricted Boltzmann Machines For
Modeling Natural Images. In Proc. Thirteenth International Conference on Artiﬁcial Intelligence
and Statistics (AISTATS), pages 621–628, 2010.
W. E. Roth. On direct product matrices. Bulletin of the American Mathematical Society , 40:461–
468, 1934.
R. Salakhutdinov, A. Mnih, and G. E. Hinton. Restricted Boltzmann machines for collaborative
ﬁltering. In Proceedings of the 24th International Conference on Machine Learning, pages 791–
798, 2007.
T. J. Sejnowski. Higher-order Boltzmann machines. In Neural Networks for Computing , pages
398–403. American Institute of Physics, 1986.
P. Smolensky. Information processing in dynamical systems: foundations of harmony theory. In
Symposium on Parallel and Distributed Processing, 1986.
T. Tran, D. Phung, and S. Venkatesh. Mixed-variate restricted Boltzmann machines. InProc. of 3rd
Asian Conference on Machine Learning (ACML), pages 213–229, 2011.
R. R. Varshamov. Estimate of the number of signals in error correcting codes.Doklady Akad. Nauk
SSSR, 117:739–741, 1957.
M. Welling, M. Rosen-Zvi, and G. E. Hinton. Exponential family harmoniums with an application
to information retrieval. In L. K. Saul, Y . Weiss, and L. Bottou, editors, Advances in Neural
Information Processing Systems 17, pages 1481–1488. MIT Press, Cambridge, MA, 2005.
18


Peer review:
[Review]:
This paper presents a comprehensive theoretical discussion on the approximation properties of discrete restricted Boltzmann machines. The paper is clearly written. It provides a contextual introduction to the theoretical results by reviewing approximation results for Naive Bayes models and binary restricted Boltzmann machines. Section 4 of the paper lists the theoretical contributions, while proofs are are delayed to the appendix.

Notably, the first result gives conditions, based on the number of hidden and visible units together with their cardinalities, for the joint RBM to be a universal approximator of distributions over the visible units. The theorem provides an extension to previous results for binary RBMs. The second result shows that discrete RBMs can represent distributions with a number of strong modes that is exponential in the number of hidden units, but not necessarily exponential in the number of parameters. The third result shows that discrete RBMs can approximate any mixture of product distributions, with disjoint supports, arbitrarily well.

Proposition 10 is a nice result showing that a discrete RBM is a Hadamard product of mixtures of product distributions. These decompositions often help with the design of inference algorithms. Lemma 25 provides useful connections between RBMs and mixtures. Subsequently theorem 27 discusses the relation to exponential families.
Theorem 29 provides a very nice approximation bound for the KL divergence between the RBM and a distribution in the set of all distributions over the discrete state space, and so on. The paper also presents a geometry analysis but I did not follow all the appendix details about these.

Finally the appendices discuss interactions within layers and training. With regard to the first issue, I think the authors should consult

H. J. Kappen. Deterministic learning rules for Boltzmann machines. Neural Networks, 8(4):537-548, 1995

which discusses these lateral connections and approximation properties. With regard to training,  I recommend the following expositions to the authors. The last one considers a different aspect of the theory of RBMS, namely statistical efficiency of the estimators:

Marlin, Benjamin, Kevin Swersky, Bo Chen, and Nando de Freitas. 'Inductive principles for restricted boltzmann machine learning.' In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, pp. 509-516. 2010.

Tieleman, Tijmen, and Geoffrey Hinton. 'Using fast weights to improve persistent contrastive divergence.' In Proceedings of the 26th Annual International Conference on Machine Learning, pp. 1033-1040. ACM, 2009.

Marlin, Benjamin, and Nando de Freitas. 'Asymptotic Efficiency of Deterministic Estimators for Discrete Energy-Based Models'. UAI 2011. 

The above provide a more clear picture of stochastic maximum likelihood as well as deterministic estimators.

Minor: Why does your paper end with a b?

In remark 5. It might be easier to simply use x throughout instead of v.