When Does a Mixture of Products Contain a Product of Mixtures?
Authors: Guido F. Montufar, Jason Morton
ICLR 2013

Abstract: We prove results on the relative representational power of mixtures of product distributions and restricted Boltzmann machines (products of mixtures of pairs of product distributions). Tools of independent interest are mode-based polyhedral approximations sensitive enough to compare full-dimensional models, and characterizations of possible modes and support sets of multivariate probability distributions that can be represented by both model classes. We find, in particular, that an exponentially larger mixture model, requiring an exponentially larger number of parameters, is required to represent probability distributions that can be represented by the restricted Boltzmann machines. The title question is intimately related to questions in coding theory and point configurations in hyperplane arrangements.

When Does a Mixture of Products
Contain a Product of Mixtures?
Guido F. Mont´ ufar∗1,2 and Jason Morton†2
1Max Planck Institute for Mathematics in the Sciences, Inselstrasse 22,
04103 Leipzig, Germany.
2Department of Mathematics, Pennsylvania State University, University
Park, PA 16802, USA.
September 22, 2014
Abstract
We derive relations between theoretical properties of restricted Boltzmann machines
(RBMs), popular machine learning models which form the building blocks of deep
learning models, and several natural notions from discrete mathematics and convex
geometry. We give implications and equivalences relating RBM-representable proba-
bility distributions, perfectly reconstructible inputs, Hamming modes, zonotopes and
zonosets, point conﬁgurations in hyperplane arrangements, linear threshold codes, and
multi-covering numbers of hypercubes. As a motivating application, we prove results
on the relative representational power of mixtures of product distributions and prod-
ucts of mixtures of pairs of product distributions (RBMs) that formally justify widely
held intuitions about distributed representations. In particular, we show that a mix-
ture of products requiring an exponentially larger number of parameters is needed to
represent the probability distributions which can be obtained as products of mixtures.
Keywords: linear threshold function, Hadamard product, zonotope, tensor rank, hy-
perplane arrangement
2000 MSC:51M20, 60C05, 68Q32, 14Q15
1 Introduction
Two basic ways of combining probability distributions are mixtures, i.e., convex combina-
tions, and Hadamard products, i.e., renormalized entry-wise products. Fixing the number
of parameters, we may ask: are Hadamard products of small mixtures better than mixtures
∗montufar@mis.mpg.de
†morton@math.psu.edu
arXiv:1206.0387v5  [stat.ML]  18 Sep 2014
k
Mixture of Products Product of Mixtures of
Products (RBM)
M6,k RBM6,4
Figure 1: Graphical representation of a mixture of products and a product
of mixtures. The dark nodes represent hidden units and the light nodes
represent visible units.
at approximating interesting or complex probability distributions? The general intuition
among practitioners is that using Hadamard products allows for more modeling power. We
compare two canonical representatives of these model classes: mixtures of product distribu-
tions, called na¨ ıve Bayes models, and Hadamard products of mixtures of pairs of product
distributions, called restricted Boltzmann machines (RBMs). The mixture of products model
Mn,k is the union of the convex hulls of all choices of k joint distributions for nindependent
binary variables (Deﬁnition 2.1). The restricted Boltzmann machine model RBM n,m is the
union of the Hadamard products of all choices of m mixtures of pairs of joint distributions
for n independent binary variables (Deﬁnition 2.2). Both are graphical probability mod-
els with hidden variables and bipartite graphs, see Figure 1. Besides deﬁning probability
distributions on their visible states, these graphical models deﬁne conditional distributions
between visible and hidden states, which makes them interesting in the context of learning
representations. This paper is the result of analyzing following problem.
Problem 1.1. When does the mixture of product distributions Mn,k contain the product
of mixtures of product distributions RBM n,m, and vice versa?
In answer to the title question, our results in Sections 3 and 4 imply the following.
Theorem 1.2. The number of parameters of the smallest mixture of products Mn,k con-
taining the product of mixtures RBMn,m grows exponentially in the number of parameters of
the latter for any ﬁxed ratio 0 < m/n <∞. More precisely, the smallest k such that Mn,k
contains RBMn,m is bounded by 3
4 n ≤log2(k) ≤n−1 when m ≥n, by 3
4 n ≤log2(k) ≤m
when 3
4 n≤m≤n, and satisﬁes log2(k) = m when m≤3
4 n.
The solution is of order log2(k) = Θ(min{m,n}). Hence the smallest mixture of products
model that contains a given RBM model is as large as one can possibly expect, having
near to one mixture component per joint state of the RBM hidden units, or otherwise
containing every possible probability distribution. See Figure 2 for an illustration of the
result. Theorem 1.2 is based on the more technical Theorem 4.2. In Theorem 4.5 we show a
complementary result stating that, although RBMs naturally contain small mixture models,
in general they do not contain mixture models that match their dimension.
To approach Problem 1.1, we study the sets of modes (Hamming-local maxima) of prob-
ability distributions that can be represented as mixtures of product distributions and as
2
(linear scale)dim(RBMn,m)=c
m
n
m
=n
m=
3
4
n
1
2
3 (1) 3
4 n≤ log2(k)≤n−1
(2) log 2(k) =m
(3) 3
4 n ≤ log2(k) ≤ m
Figure 2: Smallest mixtures of products that can represent an RBM. Shown
is the heat map of the logarithm of k(n,m) = min {k′ ∈ N: Mn,k′ ⊇
RBMn,m}, depending on n,m ∈N. The domain of this function has three
regions, each with approximately linear behavior (Theorems 1.2 and 4.2).
The model RBMn,m has nm+n+mparameters. Fixing nm+n+m= c(the
dashed hyperbola), the RBMs which are hardest to represent as mixtures
of product distributions are those with m/n≈1.
RBMs. We consider the following problems, showing in many cases that they are equivalent
or equivalent after adding some necessary conditions.
Problem 1.3. What sets of length- n binary vectors are
1. the modes or strong modes (Hamming-local maxima) of probability distributions rep-
resented by an RBM with m hidden units?
2. perfectly reconstructible (given a vector in the set, choosing the most likely hidden
state, then the most likely visible state, returns the given vector) by an RBM with m
hidden units?
3. the outputs of n linear threshold functions with m inputs?
We ﬁnd that probability distributions with many strong modes (for example, probability
distributions strictly supported on the binary vectors with even or odd number of ones),
can be represented far more compactly by RBMs than by mixtures of products. Modes
are described by linear inequalities of the form p(x) > p(x′) and can be used to derive
polyhedral approximations of probability models. As it turns out, the analysis of modes is
closely related to binary classiﬁcation problems (separation of vertex sets of hypercubes by
hyperplane arrangements), and leads to problems such as the following.
Problem 1.4. What is the smallest arrangement of hyperplanes, if one exists, that slices
each edge of a hypercube a given number of times?
We consider the following six properties of sets of binary vectors, and derive relations
between them, summarized below in Theorem 1.6.
3
SP
SM PR
LTC ZPHP
ℓ1
dH(C) ≥2dH(C) ≥2
Figure 3: Illustration of the implications in Theorem 1.6
Deﬁnition 1.5. Let nand mbe two non-negative integers and let Cbe a subset of {0,1}n.
•LTC(n,m, C): The set Cis an (n,m)-linear threshold code, i.e., the image of n linear
threshold functions with m inputs (Deﬁnition 3.23).
•HP(n,m, C): There exists an arrangement Aof nhyperplanes in Rm such that the ver-
tices of the m-dimensional unit cube intersect exactly the C-cells of A(Deﬁnition 3.18).
•ZP(n,m, C): There is an m-zonoset (i.e., the aﬃne image of the vertices of an m-cube)
in Rn which intersects exactly the C-orthants of Rn (Deﬁnition 3.15).
•SM(n,m, C): An RBM with nvisible and mhidden nodes can represent a distribution
with set of strong modes C(Deﬁnition 3.4).
•PR(n,m, C): The set Cis the set of perfectly reconstructible vectors of an RBM with
n visible and m hidden units (Deﬁnition 3.2).
•SP(n,m, C): An RBM with nvisible and mhidden units can represent a distribution
which is strictly positive on Cand zero elsewhere.
We derive implications among the properties LTC, PR, HP, ZP, SM, and SP in two
cases: the set Cis arbitrary, and Cconsists of vectors which are at least Hamming distance 2
apart.
Theorem 1.6. Let n and m be two non-negative integers and let Cbe a subset of {0,1}n.
1. The properties LTC, HP, and ZP are equivalent.
2. If Csatisﬁes PR or SM, then it is contained in an LTC set.
3. If the vectors in Care at least Hamming distance 2 apart, then SP implies both SM
and PR.
4. If the vectors in Care at least Hamming distance 2 apart and Csatisﬁes an ℓ1 property
(see Theorem 3.16), then LTC implies SP.
4
Figure 3 illustrates the result. The proof is given in Section 3.8 by combining results
from Section 3.
Section 2 contains basic deﬁnitions and background on mixtures of product distributions
and RBMs. Section 3 discusses geometric perspectives on statistical models and inference,
elaborated in various subsections. Section 3.1 discusses inference functions, distributed repre-
sentations, and reconstructability. Section 3.2 discusses the concept of modes and polyhedral
approximations of probability models. Section 3.3 covers the sets of modes of probability
distributions realizable as mixtures of product distributions (Theorem 3.7). Section 3.4
makes a few initial observations on the sets of modes of probability distributions realizable
by RBMs. In Section 3.5 these sets are related to zonosets and hyperplane arrangements
(Theorem 3.16), and in Section 3.6 to linear threshold codes. Section 3.7 discusses multi-
covering numbers; the smallest hyperplane arrangements slicing each edge of a hypercube
a given number of times. Section 3.8 contains the proof of Theorem 1.6. Turning to the
motivating questions, Section 4 contains our analysis of Problem 1.1, treating the inclusion
of RBMs in mixture models in Section 4.1, and the reverse inclusion in Section 4.2. Section 5
oﬀers a discussion.
2 Mixtures of products and products of mixtures
Let Pn denote the (2n−1)-dimensional simplex of joint probability distributions of nbinary
variables. This is the set of vectors p∈R2n
with entries p(x) ≥0, x= (x1,...,x n) ∈{0,1}n,
satisfying ∑
x∈{0,1}n p(x) = 1. For any given p ∈ Pn, the marginal distribution of the
i-th variable is the vector pi ∈ P1 with entries pi(xi) = ∑
(x1,...,xi−1,xi+1...xn)∈{0,1}n−1 p(x),
xi ∈{0,1}.
Let Mn,1 denote the n-dimensional set of joint probability distribution of n indepen-
dent binary variables. This is the set of distributions p ∈ Pn that factorize as p(x) =
p1(x1) ···pn(xn), x = (x1,...,x n) ∈{0,1}n, called product distributions. One can regard
these distributions as the n-way 2 ×···× 2 tables of the form p1 ⊗···⊗ pn, pi ∈P1, i∈[n],
where ⊗denotes the tensor product. We note that Mn,1 is the closure of the exponential
family pB(x) = 1
Z(B) exp(B⊤x), x∈{0,1}n, with natural parameter B ∈Rn and normaliza-
tion function Z(B) = ∑
y∈{0,1}n exp(B⊤y). Closure is needed in order to include probability
distributions with vanishing entries.
Deﬁnition 2.1. The k-mixture of product distributions of nbinary variables, denoted Mn,k,
is the set of distributions on {0,1}n expressible as convex combinations p = ∑
i∈[k] λiq(i),
where λi ≥0, ∑
i∈[k] λi = 1, and q(i) ∈Mn,1 for all i∈[k].
Up to positive scalar multiples, Mn,k corresponds to the set of n-way 2 ×···× 2 tables
with non-negative rank at most k. The Zariski closure of Mn,k in complex projective space
is the k-th secant variety of the n-th Segre product of P1s and has the same dimension as
Mn,k. As it turns out, this is the dimension expected from counting parameters, equal to
min{nk+ (k−1),2n −1}, except when ( n,k) = (4 ,3), in which case it has dimension 13
instead of 14. See [4], which answered this century-old question in algebraic geometry.
5
The set Mn,k is equal to the probability simplex Pn if and only if k ≥2n−1, see [18]. In
particular, the smallest Mn,k that equals Pn has 2n−1(n+ 1) −1 parameters.
Deﬁnition 2.2. The RBM model with nvisible and mhidden binary units, denoted RBMn,m,
is the closure of the set of distributions 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, (1)
where W ∈Rm×n is a matrix of interaction weights between hidden and visible units (with
state vectors hand x, respectively), B ∈Rn is a vector of biases of the visible units, C ∈Rm
is a vector of biases of the hidden units, and Z(W,B,C ) = ∑
x∈{0,1}n
∑
h∈{0,1}m exp(h⊤Wx+
B⊤x+ C⊤h) is a normalization function.
An RBM is a product of experts [13]; each hidden unit corresponds to an expert which
is a mixture of two product distributions [6]. For completeness we provide a proof of this
statement:
Proposition 2.3. Each RBM distribution of the form (1) is a renormalized entry-wise
product of positive mixtures of pairs of positive product distributions, and vice versa.
Proof. Each distribution p of the form (1) can be written as a renormalized entry-wise
product
p(x) = q(1)(x) ···q(m)(x)∑
y∈{0,1}n q(1)(y) ···q(m)(y) for all x∈{0,1}n,
where q(j) = λjpAj +(1−λj)pA′
j ∈Mn,2 is a positive mixture of positive product distributions,
with λj ∈(0,1), pAj = exp(A⊤
j x)/Z(Aj) and pA′
j = exp(A′
j
⊤x)/Z(A′
j), for all j ∈[m]. To
see this, note that
∑
h∈{0,1}m
exp(h⊤Wx + B⊤x+ C⊤h) =
∏
j∈[m]
∑
hj∈{0,1}
exp(hjWjx+ 1
mB⊤x+ Cjhj)
=
∏
j∈[m]
(
exp( 1
mB⊤x) + exp(Cj) exp((Wj + 1
mB⊤)x)
)
∝
∏
j∈[m]
(
λjpAj (x) + (1−λj)pA′
j (x)
)
,
where Wj is the j-th row of W, Aj = B/m, A′
j = W⊤
j + (B/m), and λj = Z(Aj)/(Z(Aj) +
Z(A′
j) exp(Cj)).
Conversely, each renormalized entry-wise product of positive mixtures of pairs of positive
product distributions is of the form (1). To see this, note that, for any choice of Aj,A′
j ∈Rn
6
and λj ∈(0,1),
∏
j∈[m]
(
λjpAj (x) + (1−λj)pA′
j (x)
)
=
∏
j∈[m]
( λj
Z(Aj) exp(A⊤
j x) + (1 −λj)
Z(A′
j) exp(A′
j
⊤x)
)
∝
∏
j∈[m]
exp(Aj
⊤x)
(
1 + Z(Aj)
λj
(1 −λj)
Z(A′
j) exp((A′
j −Aj)⊤x)
)
∝
∑
h∈{0,1}m
exp(h⊤Wx + B⊤x+ C⊤h),
where B = ∑
j∈[m] Aj, Wj = A′
j −Aj, and Cj = log
(
Z(Aj)(1 −λj)/λjZ(A′
j)
)
.
An RBM can also be seen as a set of restricted mixtures of product distributions; each
p∈RBMn,m is a mixture of 2 m product distributions, namely the conditionals
p(x|h) = exp((h⊤W + B⊤)x)∑
y∈{0,1}n exp((h⊤W + B⊤)y) = pW⊤h+B(x) for all h∈{0,1}m.
In general, the dimension of the mixture model Mn,2m is much larger than that of
RBMn,m. The set RBM n,m is known to have dimension nm+ n+ mwhen m< 2n−⌈log2(n+1)⌉,
and 2n −1 when m ≥2n−⌊log2(n+1)⌋, see [6]. In addition, it is known that RBM n,m equals
Pn whenever m ≥2n−1 −1, see [19]. It is not known if the latter bound is always tight,
but it shows that the smallest RBM n,m that equals Pn has not more than 2 n−1(n+ 1) −1
parameters, and hence not more than the smallest mixture of products model.
We will show that the sets of probability distributions representable by RBMs and mix-
tures of products are quite diﬀerent. The intersection of both model classes has been studied
in [22], where it is shown that RBM n,m contains any mixture of m+ 1 product distributions
with disjoint supports, and hence that the intersection RBM n,m∩Mn,m+1 has dimension of
order at least mn+ m+ 2n+ 1 −(m−1) log2(m+ 1). Typically RBMs have many binary
hidden variables and mixtures of products models have a single multivalued hidden vari-
able. The transition between these two limit cases has been studied in [20], focusing on the
Kullback-Leibler model approximation errors and the model dimension.
3 Geometric perspectives
In this section we present ﬁve points of view on the families of probability distributions
deﬁned in the previous section. We consider inference functions and hidden representations
deﬁned by these models (Section 3.1), modes and strong modes of their marginal distributions
(Sections 3.2, 3.3, and 3.4), zonosets, hyperplane arrangements, and linear threshold codes
that capture their combinatorial structure (Sections 3.5 and 3.6), and the resulting multi-
covering numbers of hypercubes (Section 3.7).
Each point of view comes with particular set of related tools and implications for the
capabilities of RBMs and competing models. We determine how these ﬁve concepts are
7
(00)
(01) (11)
(10)
1
23
4
(00)
(01) (11)
(10)
(111)
(100) (001)
(010)
(011)(110)
(101)
Figure 4: Inference regions of M2,4 (left) and RBM 2,3 (right), for a choice
of parameters.
related, which imply which, and how properties such as the number of strong modes in a
marginal distribution translate into each perspective. These observations are summarized
in Section 3.8, and in Section 4, where they are applied to distinguish mixtures of products
and products of mixtures.
3.1 Inference functions, distributed representations,
reconstructability
Hinton [13] discusses advantages of products of experts (Hadamard products of probabil-
ity models) over mixtures of experts (mixtures of probability models), for modeling “high-
dimensional data which simultaneously satisﬁes many low-dimensional constraints.” In prod-
ucts of experts models, each expert can individually ensure that one constraint is satisﬁed.
In the case of RBMs, each hidden unit linearly divides the input space according to its pre-
ferred state given the input, which results in a multi-clustering, or a partition of the input
space into cells where diﬀerent joint hidden states are most likely. Inference of the most likely
hidden state given an input produces a distributed encoding or distributed representation of
the input vector, as discussed by Bengio in [2, Section 5.3].
Deﬁnition 3.1. The inference function of a probability model pθ(v,h) with parameter
θ ∈RN ‘explains’ each value of v by the most likely value of h according to up θ: v ↦→
argmaxhpθ(h|v). This deﬁnes a partition of the input space into the preimages of all possi-
ble outputs, called inference regions.
Inference functions provide a combinatorial view on the corresponding probability models.
They appear naturally in the context of tropicalization, where they correspond to the linear
regions of certain piecewise linear approximations of algebraic varieties and serve to estimate
their dimension. This approach has been studied in [8] in the context of secants and in [6,
20, 21] in the context of RBMs.
For each choice of parameters W ∈Rm×n, B ∈Rn, C ∈Rm, the model RBM n,m deﬁnes
the inference function
upW,B,C: Rn ⊃{0,1}n →{0,1}m; v↦→argmaxh∈{0,1}m h⊤(Wv + C) .
8
The visible state vis explained by the hidden statehwhich satisﬁes sgn(Wv+C) = sgn(h⊤−
1
2 1), where 1 := (1 ,..., 1). There may be several explanations for a given observation,
but generically there is only one. Geometrically, the input space Rn is partitioned into the
preimages of the orthants of Rm by the aﬃne map ψ: Rn →Rm; v↦→Wv+C. This partition
corresponds to the intersection of an aﬃne space and the normal fan of an m-cube (the
orthants of Rm). The number of inference regions can be as large as Caﬀ(m,d) = ∑d
i=0
(m
i
)
,
which is the number of orthants ofRm intersected by a generic d-dimensional aﬃne subspace,
where d ≤min{n,m}is the rank of W. When the rank of W is less than m (for example,
when m > n), then the image of the map ψ does not intersect all orthants of Rm and
there are ‘empty’ inference regions, i.e., states hwhich are not the explanation of any input
vector v.
The mixture model Mn,k, on the other hand, deﬁnes, for any choice of the mixture
weights λi and the natural parameters of each mixture component Bi ∈Rn for i ∈[k], an
inference function
upλ,B: Rn ⊃{0,1}n →{1,...,k }; v↦→argmaxi∈[k](B⊤
i v−log(Z(Bi)) + log(λi)),
where Z(Bi) = ∑
v∈{0,1}n exp(B⊤
i v). In this case, the input space Rn is partitioned into the
at most k regions of linearity of the function v↦→max{B⊤
i v−log(Z(Bi)) + log(λi): i∈[k]}.
This partition corresponds to the intersection of an aﬃne space and the normal fan of a
(k−1)-simplex.
Figure 4 shows an example of inference regions in {0,1}2 ⊂R2 deﬁned by M2,4 (left
panel) and RBM 2,3 (right panel), for some speciﬁc parameter values. Both models have 7
parameters and are universal approximators of distributions on {0,1}2, but they deﬁne very
diﬀerent inference regions.
For a ﬁxed input space of dimension n, the number of inference regions in Rn that can
be realized by RBM n,m is of order Θ(
( m
min{n,m}
)
), which is exponential in the number of
parameters of the model, whereas the number of inference regions that can be realized by
Mn,k is linear in the number of parameters of the model. A function g: R+ →R+ is of order
Θ(f) if there exist positive constants C,C′ and n0 such that Cf(n) ≤g(n) ≤C′f(n) for all
n ≥n0 [16]. Distributed representations can, in principle, learn diﬀerent explanations to a
number of observations that is exponential in the number of model parameters, see [2].
Now we discuss reconstructability. Similarly to the up θ inference function, a model
pθ(v,h) deﬁnes a down θ inference function, which outputs the most likely visible state
argmaxv pθ(v|h) given a hidden state h.
Deﬁnition 3.2. Given a probability model pθ(v,h) on v ∈X and h ∈Y, a collection of
states C ⊆Xis perfectly reconstructible if there is a choice of the parameter θ for which
downθ(upθ(v)) = v for all v∈C.
The ability to reconstruct input vectors is sometimes used to evaluate the performance
of RBMs in practice, since it can be tested more cheaply than the probability distributions
they represent. The reconstructability of input vectors can also be used to deﬁne training
algorithms, like in the case of auto-encoders.
When writing the joint probabilities (pθ(v,h))v,h as a matrix with rows labeled by h∈Y
and columns by v ∈X, a set C⊆X is perfectly reconstructible iﬀ there is a choice of the
9
model parameter θ for which pθ(v,upθ(v)) is the unique maximal entry in the up θ(v)-row
(and in the v-column) for all v ∈C. For the model RBM n,m, this is the case exactly when
for each v ∈C⊆{ 0,1}n there is an hv ∈{0,1}m with sgn(Wv + C) = sgn( hv −1
2 1) and
sgn(h⊤
v W + B⊤) = sgn(v−1
2 1).
Example 3.3. If n,m ≥ k, all cylinder subsets of {0,1}n of dimension k are perfectly
reconstructible by RBMn,m. A k-dimensional cylinder subset of {0,1}n is a set of the form
{x ∈{0,1}n: xi = yi for all i ∈I}, where I is a subset of [ n] of cardinality |I|= n−k,
and yi ∈{0,1}, i ∈I are ﬁxed values. Without loss of generality let I = {k+ 1,...,n }.
Consider the following choice of parameters. Deﬁne Wi,j = δi,j for i,j ≤k and zero else,
deﬁne Bj = −1
2 for j ≤kand Bj = yj−1
2 else, and C = −1
2 1. Then sgn(Wv+C) = sgn(v1 −
1
2 ,...,v k−1
2 ,−1
2 ,..., −1
2 ), so that hv = (v1,...,v k,0,..., 0). Furthermore, sgn(h⊤
v W+B⊤) =
sgn(v1 −1
2 ,...,v k −1
2 ,yk+1 −1
2 ,...,y n −1
2 ).
Later we will study the ability of RBMs to reconstruct more complicated sets of binary in-
puts, and how the sets of reconstructible inputs relate to the visible probability distributions
represented by the model.
3.2 Modes
We will characterize the ability of RBMs and mixtures of product distributions to represent
distributions with many strong modes, in order to draw a distinction between them. As an
interesting side remark, note that similar questions, about the number of modes of mixtures
of multivariate normal distributions, have been posed in [28], and that the maximal number
of modes realizable by mixtures of k normal distributions on Rn is unknown.
Deﬁnition 3.4. Let pbe a probability distribution on a ﬁnite set Xof length-nvectors. A
vector x ∈X is a mode of p if p(x) > p(y) for all y ∈X with dH(y,x) = 1, and a strong
mode if p(x) > ∑
y∈X:dH(y,x)=1 p(y). Here dH(y,x) := |{i ∈[n]: yi ̸= xi}|is the Hamming
distance between y and x.
The modes of a distribution are the Hamming-locally most likely events in the space of
possible events. Modes are closely related to the support sets and boundaries of statistical
models, which have been studied especially for hierarchical and graphical models without
hidden variables [12, 15, 27].
We write Gn,m (and Hn,m) for the set of distributions in Pn which have at least mmodes
(strong modes). For any set C⊂{ 0,1}n of vectors with Hamming distance at least 2 from
each other, we writeGC(and HC) for the set of distributions which have modes (strong modes)
C. The closures GC (and HC) are convex polytopes inscribed in the probability simplex Pn.
The sets of modes that are not realizable by a probability model give a full dimensional
polyhedral approximation of the model’s complement. See Figure 5 for an example. We will
focus most of our consideration on strong modes. These are easier to study than modes,
because they are described by fewer inequalities.
The minimum Hamming distance of a setC⊆X is deﬁned asdH(C) := min{dH(x,y): x̸=
y and x,y ∈C}. Since any two modes have at least Hamming distance two from each other,
a distribution on {0,1}n has at most 2 n−1 modes. There are exactly two subsets of {0,1}n
10
G+
2
G−
2
M2,1
δ(00)
δ(11)
δ(01)
δ(10)
Figure 5: The 3-dimensional simplex of probability distributions on
{0,1}2 (a tetrahedron with vertices corresponding to the outcomes
(00),(01),(10),(11)), with three sets of probability distributions depicted.
The dark curved surface is the 2-dimensional manifold M2,1 of product dis-
tributions of two binary variables. The angular regions at the top and bot-
tom are the polyhedra G+
2 and G−
2 of distributions with two modes. An in-
teractive 3-D graphic object is available at http://personal-homepages.
mis.mpg.de/montufar/surface.pdf.
with cardinality 2n−1 and minimum distance two. These are the sets of binary strings with
an even, respectively odd, number of entries equal to one:
Z+,n :=
{
(x1,...,x n) ∈{0,1}n:
∑
i∈[n]
xi is even
}
;
Z−,n :=
{
(x1,...,x n) ∈{0,1}n:
∑
i∈[n]
xi is odd
}
.
We write Gn,2n−1 = GZ+,n ∪GZ−,n, or Gn = G+
n ∪G−
n for short, and similarly Hn = H+
n ∪H−
n.
Figure 5 illustrates the set G2 = G+
2 ∪G−
2 ⊂P2 (the set of distributions on {0,1}2 with
two modes), and the two-dimensional manifold M2,1 ⊂P2 (the set of product distributions
on {0,1}2). We see that P2 contains 6 disjoint sets congruent to G+
2 whose union’s closure
equals P2. Hence the Lebesgue volume satisﬁes vol( G+
2 )/vol(P2) = 1 /6. The case of three
bits is as follows.
Example 3.5. The subset G+
3 ⊂P3 of distributions on {0,1}3 with four modes Z+,3 is the
intersection of P3 and 12 open half-spaces deﬁned by p(x) >p(y) for all y with dH(x,y) = 1
for all x ∈Z+,3. The closure of this set is a convex polytope G+
3 with 19 vertices. The
vertices are uniform distributions on subsets of {0,1}3 that can be covered by three disjoint
cylinder subsets of {0,1}3. The list of vertices and vertex-facet incidences are provided in
Tables 1 and 2, in the appendix. The Lebesgue volume of this polytope can be computed
(e.g., using the software Polymake [11]): vol(G+
3 )/vol(P3) = 1/56 = 0.017857142.
11
The subset H+
3 ⊂G+
3 of distributions with four strong modes Z+,3 is the intersection of
P3 and the 4 open half-spaces deﬁned by p(x) >∑
y:dH(x,y)=1 p(y) for all x∈Z+,3. We will
discuss it in Section 3.5.1.
3.3 Modes of mixtures of products
In this section we characterize the sets of modes and strong modes that can appear in
mixtures of product distributions, and show how these can be used to obtain a polyhedral
approximation of the set of probability distributions representable in such models.
Problem 3.6. What is the smallest k ∈N for which Mn,k contains a distribution with l
(strong) modes?
A mixture of k unimodal discrete probability distributions has at most k strong modes.
For mixtures of products we have the following.
Theorem 3.7. Let X1,..., Xn be ﬁnite sets. Let Mbe the set of all possible mixtures of k
product distributions of n variables with state spaces Xi, i∈[n]. If p∈M has strong modes
C, then every c∈C is the mode of one mixture component of p. The sets of strong modes of
distributions within Mare exactly the sets of strings in X1 ×···×X n of minimum Hamming
distance at least two and cardinality at most k.
Proof. A product distribution q has at most one mode. This follows from the fact that the
value of q(x1,...,x n) = q1(x1) ···qn(xn) is either maximal, or can be increased by changing
only one entry of x. If q(j), j ∈[k], are product distributions and x is not a mode of any
q(j), then ∑
y:dH(y,x)=1
∑
j∈[k] αjq(j)(y) ≥∑
j∈[k] αjq(j)(x) for any αj ≥0. In turn, x is not a
strong mode of any mixture of the q(j). On the other hand, the set of product distributions
contains every point measure δy, since the latter can be written as δy(x) = q1(x1) ···qn(xn)
with qi(yi) = 1 for all i ∈[n]. Hence the mixture of products model Mcontains every
distribution of the form ∑
y∈C
1
|C|δy for any C⊆X with |C|≤ k.
By the previous theorem, a mixture of k product distributions can have at most k strong
modes. Nevertheless, a mixture of k product distributions can have more than k modes.
Here is an example:
Example 3.8. The mixture p= 1
2 p(1) + 1
2 p(2) of the following two product distributions of
four binary variables has three modes (0000), (1100), and (1111):
p(1) = 1
5 ( 3
2 ) ⊗1
5 ( 3
2 ) ⊗( 1
0 ) ⊗( 1
0 ) = 1
25
[9 6
6 4
0 0
0 0
0 0
0 0
0 0
0 0
]
;
p(2) = ( 0
1 ) ⊗( 0
1 ) ⊗1
5 ( 2
3 ) ⊗1
5 ( 2
3 ) = 1
25
[0 0
0 4
0 0
0 6
0 0
0 6
0 0
0 9
]
.
Theorem 3.7 shows that the set Hn,k+1 is in the complement of Mn,k for all k. We
can triangulate Hn,k+1 and thereby lower bound the (Lebesgue) volume of the complement
Pn \Mn,k ⊇Hn,k+1. A rough estimate is:
12
Proposition 3.9. Let k < 2n−1. The volume of Hn,k+1 satisﬁes vol(Hn,k+1)/vol(Pn) ≥
2−(k+1)nK(k+1), where K(k+1) = 2k+1 if k+1 ≤2s < 2n
n for some s∈N, and K(k+1) = 2
otherwise.
Proof. Let Y ⊆X:= {0,1}n. Let P(Y) be the simplex of probability distributions with
support in Y. This is a regular ( |Y|− 1)-simplex in R|X| with edge-length
√
2. Let H(Y)
denote the set of distributions on X with strong modes Y, such that H(Y) = ∩y∈YH(y).
Let B1(y) ⊆X denote the radius-1 Hamming ball centered at y. The set Py(B1(y)) := {p∈
P(B1(y)): p(y) ≥p(B1(y) \{y})}is a regular n-simplex with edge-length
√
2
2 and vertices
{1
2 (δy+ δˆy)}dH(ˆy,y)≤1. The volume of a regular N-simplex with edge-length lis
√N+1
N!
√
2
N lN. The
set H(y) is the convex hull of Py(B1(y)) and P(X\ B1(y)). Its volume satisﬁes
vol(H(y))/vol(Pn) = vol(Py(B1(y)))/vol(P(B1(y))) = 2−n.
If Yhas minimum distance 3 or more, then the radius-1 Hamming balls B1(y), y ∈Y,
are disjoint, and
vol(H(Y))/vol(Pn) =
∏
y∈Y
(vol(Py(B1(y)))/vol(P(B1(y)))) = 2−|Y|n.
If Yhas minimum distance 2 instead of 3, then the volume of H(Y) can only go up. To
see this, consider a pair y,y′ of Hamming distance 2 and let Py,y′(B1(y) ∪B1(y′)) := {p ∈
P(B1(y) ∪B1(y′)): p(y) ≥p(B1(y) \{y}),p(y′) ≥p(B1(y′) \{y′})}denote the closure of the
set of distributions with support in B1(y) ∪B1(y′) and strong modes y and y′. Then
vol(Py,y′(B1(y) ∪B1(y′)))/vol(P(B1(y) ∪B1(y′))) >2−2n.
This is because, for any z with Hamming distance one to both y and y′, the inequality
p(z) <1/2 implied by H(y) is also implied by H(y′) and hence not each pair of neighbors of
the form (y,x) or (y′,x) translates to a factor 1 /2 in the volume.
The number K(k+ 1) is a lower bound on the number of disjoint sets H(Y) with |Y|=
k+ 1. By the Gilbert-Varshamov bound, if k+ 1 ≤2s for some integer s with 2s < 2n
n ,
then there is a set Y⊂X of cardinality |Y|= k+ 1 and minimum distance 3. Let Y′ =
(Y\{y}) ∪{y⊕2 e1}(ﬂip one coordinate of one element of Y), such that H(Y) ∩H(Y′) = ∅.
Since Yhas (k+ 1) elements, there are 2k+1 disjoint sets of this form. For a general Y⊂X
of cardinality |Y|= k+1 ≤2n−1 and minimum distance 2, the set Y′⊕2 e1 also has minimum
distance 2 and cardinality |Y′|= k+ 1. These two sets satisfy H(Y) ∩H(Y′) = ∅.
3.3.1 Polyhedral approximation of the full-dimensional model M3,3
Theorem 3.7 shows that any p ∈M3,3 has at most three strong modes. We can show that
this is true for modes too.
Proposition 3.10. The mixture model of three product distributions on{0,1}3 cannot realize
distributions with four modes: M3,3 ∩G3 = ∅.
13
Proof. Assume that M3,3 ∩G+
3 ̸= ∅. By the Lemma 3.11 given below, there are factors
(pi
1,pi
2,pi
3) ∈(P1)3,i = 1,2,3 such that conv {qi := pi
2pi
3}i=1,2,3 intersects G+
2 and G−
2 . Hence
conv{q1,q2}intersects G+
2 and conv{q2,q3}intersects G−
2 (for some enumeration of q1,q2,q3).
The mixture of q2 and q3 intersects G−
2 only if (01) and (10) are the unique maxima of q2
and q3. Similarly, conv{q1,q2}intersects G+
2 only if (11) and (00) are the unique maxima of
q1 and q2; a contradiction.
The proof of Proposition 3.10 uses the following lemma, which relates the number of
modes realizable by Mn,k to the number of modes simultaneously realizable on subsets of
variables.
Lemma 3.11. Let n,k ∈N and n≥2. Let p= ∑
i∈[k] λi
∏
j∈[n] pi
j ∈Mn,k, with λi ≥0 and
pi
j ∈P1 for all (i,j) ∈[k]×[n]. If phas 2n−1 modes, then for any subset of variables I ⊊ [n],
|I|= m, the convex hull of the product distributions {∏
j∈I pi
j}i∈[k] ⊂Pm intersects both G+
m
and G−
m.
Proof. We show the special case with I = {1,...,n −1}. The proof of the general case is a
straightforward generalization. Any q∈Mn,k has the following form:
q(x1,x2,...,x n) =
k∑
i=1
λipi
1(x1)pi
2(x2) ···pi
n(xn),
for all ( x1,x2,...,x n) ∈{0,1}n, where ∑k
i=1 λi = 1, λi ≥0 and pi
j ∈P1. For the ﬁxed
value x1 = 0 this is a mixture of k products with ( n−1) variables, multiplied by a positive
constant:
q(x1 = 0,x2,...,x n) = c0
k∑
i=1
λ0,ipi
2(x2) ···pi
n(xn),
where ∑k
i=1 λ0,i = 1,λ0,i ≥0 with λ0,i = λipi
1(x1=0)
c0
and c0 = ∑k
i=1 λ0,ipi
1(x1 = 0). A similar
observation can be made for the ﬁxed value x1 = 1. If the distribution q is contained in G+
n,
then q(x1 = 0,x2,...,x n) ∈G+
n−1 and q(x1 = 1,x2,...,x n) ∈G−
n−1, since q ∈G+
n. These two
conditional distributions are mixtures of the same k product distributions {pi
2 ···pi
n}i∈[k],
even though they may have diﬀerent mixture weights.
Remark 3.12. The sets G+
3 and G−
3 are intersections of half-spaces that contain the uniform
distribution. Although M3,3 is full dimensional in P3, by Proposition 3.10 the complement
of M3,3 contains points arbitrarily close to the uniform distribution!
3.4 Modes of RBMs
In the following we characterize the sets of modes and strong modes that can appear in
RBM-distributions. In analogy to the problem posed in the last section, we ask:
Problem 3.13. What is the smallest m∈N for which RBMn,m contains a distribution with
l (strong) modes?
14
In particular, what is the smallest m for which the model RBM n,m can represent the
parity function? By Theorem 3.7 and RBM n,m ⊆Mn,2m, any p ∈RBMn,m has at most
min{2m,2n−1}strong modes. We will see that this bound is not always tight, but often.
In special cases, the analysis of mixtures of products (Section 3.3) is suﬃcient to make
statements about RBMs, for example: The model RBM 4,2 is contained in M4,4 and has co-
dimension one in P4. Its algebraic implicitization was studied in [7], i.e., its description as the
set of zeros of a collection of polynomials. It was found to be the zero locus of a polynomial
of degree 110 with as many as 5 .5 trillion monomials. By Theorem 3.7, M4,4 ∩H4 = ∅and
so RBM4,2 ∩H4 = ∅. Using Proposition 3.10 and Lemma 3.11 one can show:
Proposition 3.14. The models M4,4 and RBM4,2 cannot realize probability distributions
with 8 modes: M4,4 ∩G4 = ∅and RBM4,2 ∩G4 = ∅.
We note that the model RBM n,m contains any distribution with support of cardinality
min{m+ 1,2n}[19, Theorem 1]. Therefore, it contains some distributions with min {m+
1,2n−1}strong modes. For example, RBM n,m contains any uniform distribution on a set of
cardinality min{m+ 1,2n−1}and minimum Hamming distance 2. In particular, whenever
Mn,k+1 contains a distribution with strong modesC, then also RBMn,k contains a distribution
with strong modes C.
Note also that, since the model RBM n,m is symmetric under relabeling of any of its
variables, there is an RBM distribution with strong modes Ciﬀ there is one with strong
modes C⊕2 x= {c+ x mod (2): c∈C} for any x∈{0,1}n.
In general, characterizing the sets of modes realizable by RBMs is a more complex prob-
lem than it was for mixtures of product distributions, and will necessitate developing charac-
terizations in terms of point conﬁgurations called zonosets (Deﬁnition 3.15) and hyperplane
arrangements, or in terms of linear threshold functions. We elaborate these notions and
characterizations in the next 3 sections.
3.5 Zonosets and hyperplane arrangements
Deﬁnition 3.15. Let m ≥0, n >0, Wi ∈Rn for all i ∈[m], and B ∈Rn. The multiset
Z= {∑
i∈I Wi + B}I⊆[m] is called an m-zonoset.
The convex hull of a zonoset is a zonotope, a well known object in the literature of
polytopes. Zonotopes can be identiﬁed with hyperplane arrangements and oriented ma-
troids [3, 35].
Given a sign vector s∈{−,+}n, the s-orthant of Rn, denoted Rn
s, consists of all vectors
x∈Rn with sgn(x) = s. We say that an orthant has even (odd) parity if its sign vector has
an even (odd) number of +. The sets of strong modes of RBMs can be described in terms
of zonosets as follows.
Theorem 3.16. Let C⊂{ 0,1}n have minimum Hamming distance at least two.
•If the model RBMn,m contains a distribution with strong modes C(i.e., RBMn,m∩HC ̸=
∅), or Chas cardinality 2m and is perfectly reconstructible by RBMn,m, then there is
an m-zonoset with a point in each C-orthant of Rn.
15
•If there is an m-zonoset intersecting exactly the C-orthants of Rn at points of equal
ℓ1-norm, then RBMn,m∩HC ̸= ∅and, furthermore, Cis perfectly reconstructible.
Proof. Assuming that p ∈RBMn,m∩HC, for each x ∈C there is an h ∈{0,1}m for which
p(·|h) is uniquely maximized by x (Theorem 3.7 and RBM n,m ⊂Mn,2m). This is also true
if Cis perfectly reconstructible. In this case, ( h⊤W + B⊤)x >(h⊤W + B⊤)v for all v ̸= x,
and, equivalently, sgn(h⊤W + B⊤) = sgn(x−1
2 (1,..., 1)⊤). The existence of such W and B
is equivalent to the existence of a zonoset with a point in each C-orthant of Rn.
Assume now that W,B can be chosen such that all vectors h⊤W + B⊤ have the same
ℓ1 norm, equal to K. We have 1
2 K = 1
2 ∥h⊤W + B⊤∥1 = (h⊤W + B⊤)(xh −1
2 (1,..., 1)⊤) =
(h⊤W + B⊤)xh + h⊤C −1
2 B⊤(1,..., 1)⊤, where C = −1
2 W(1,..., 1)⊤, for some xh ∈ C
for all h ∈ {0,1}m. The RBM with parameters αW,αB, C = −αW1
2 (1,..., 1)⊤, and
α→∞ produces 1
2m
∑
h∈{0,1}m δxh ∈HC as its visible distribution. This also implies that C
is perfectly reconstructible.
Remark 3.17. The ﬁrst part of Theorem 3.16 remains true if HC is extended to the set of
distributions for which any Mn,2m-decomposition has a mixture component with mode c, for
every c∈C.
Deﬁnition 3.18. A hyperplane arrangement Ain Rn is a ﬁnite set of (aﬃne) hyperplanes
{Hi}i∈[k] in Rn. Choosing an orientation for each hyperplane, each vector x∈Rn receives a
sign vector sgnA(x) ∈{−,0,+}k, where (sgnA(x))i indicates whether x lies on the negative
side, inside, or on the positive side of Hi. The set of all vectors in Rn with the same sign
vector is called a cell of A.
A necessary condition for the existence of an m-zonoset intersecting all C-orthants of Rn
is that the number of orthants of Rn that are intersected by an m-dimensional aﬃne space is
at least |C|. The maximal number of orthants intersected by a d-dimensional linear subspace
of Rn, denoted C(n,d), was derived in [31]. It is not diﬃcult to derive the corresponding
number for a d-dimensional aﬃne subspace, denoted Caﬀ(n,d), as well:
C(n,d) = 2
d−1∑
i=0
(n−1
i
)
and Caﬀ(n,d) =
d∑
i=0
(n
i
)
. (2)
Cover [5] shows that C(n,d) is also the number of partitions of an n-point set in general
position in Rd by central hyperplanes (hyperplanes through the origin). A set of vectors in
Rd is in general position if any d or less are linearly independent. Dually, Caﬀ(n,d) can be
seen as the number of cells of a real d-dimensional arrangement of n hyperplanes in general
position [26, 30].
In particular, there are aﬃne hyperplanes ofRn intersecting all but one orthants. Figure 4
(right) is an example showing the intersection of a 2-dimensional aﬃne subspace of R3 and
7 orthants; four of odd parity and three of even parity. This does not imply, however,
that every collection of 2 m even, or odd, orthants can be intersected by an m-zonoset. For
example:
Proposition 3.19. If n is an odd natural number larger than one, then there is no (n−1)-
zonoset with a point in every even, or every odd, orthant of Rn.
16
Proof. Let Zbe a candidate zonoset; Zhas (n−1) generators, so it lies in an aﬃne hyper-
plane H of Rn. Let η be a normal vector to H. Assume ﬁrst that 0 ∈H. All vectors in
the orthants sgn(η) and −sgn(η) lie outside H (where we may assign arbitrary sign to zero
entries of η). This follows from Stiemke’s theorem, see, e.g., [10]. The two orthants have
opposite sign vectors and nis odd, so one orthant is even and the other odd. Hence at least
one even and one odd orthants do not intersect Z.
Consider now an aﬃne subspace H, and assume it intersects all even orthants. By
eq. (2) dim( H) ≥n−1, so H is a hyperplane. Assume without loss of generality that a
normal vector to H has only negative entries. Then H ∩Rn
(−···−) is an ( n−1)-dimensional
simplex containing a point of Z. This can be inferred from the number of bounded cells
in a d-dimensional arrangement of n hyperplanes in general position, b(n,d) =
(n−1
d
)
[32,
Proposition 2.4]. The orthant Rn
(−···−) is separated by (n−1) coordinate hyperplanes from the
orthant Rn
si with sign si = (+ ··· + −
i
+ ···+) for any i∈[n]. Since nis odd and larger than
one, (n−1) >0 is even. Since Zintersects H∩Rn
si for all i∈[n], also H∩Rn
(−···−) ⊂conv(Z)
(details in Lemma 3.20). On the other hand, the ( n−1)-generated zonotope of dimension
(n−1) is combinatorially equivalent to the ( n−1)-cube, and no point in its zonoset is
contained in the convex hull of any other points.
We used the following lemma in the proof of Proposition 3.19.
Lemma 3.20. Let P be a polytope with vertex set V. Let {Hi}r
i=1 the supporting hyperplanes
of the facets of P incident to a vertex v∈V, and assume P is contained in the intersection of
closed half-spaces ∩iH+
i . If v′ is any point in ∩iH−
i , then the polytope conv({v′}∪(V \{v}))
contains P.
Proof. The case v′= vis trivial, so let v′̸= v. It is suﬃcient to show that vis not a vertex of
Q:= conv({v′}∪V), from which v∈conv({v′}∪(V \{v})) and P ⊆conv({v′}∪(V \{v}))
follows. The point v′ is a vertex of Q, because v′̸∈P. Consider ﬁrst the case where v′ is in
the interior of ∩H−
i , which is to say that v′ is not contained in any H+
i . If v was a vertex
of Q, then one Hi would support a facet of Q (otherwise v′ would be incident to all facets
incident to v). This would contradict the fact that v′ ̸∈H+
i . The general case v′ ∈∩H−
i
results from continuity.
Proposition 3.19 allows us to describe some distributions that cannot be represented by
RBMs. A code C⊂{ 0,1}n extends another code C′⊂{0,1}r, r≤n, if restricting Cto some
r indices yields C′.
Corollary 3.21. If mis an even non-zero natural number and m<n , then RBMn,m∩HC =
∅for any code C⊂{ 0,1}n extending Z+,m+1 or Z−,m+1. In particular, when n is an odd
natural number larger than one, RBMn,n−1 cannot represent any distribution with 2n−1 strong
modes.
Proof. If there is an m-zonoset with points in every C-orthant of Rn and there is a restriction
of Cto Z+,m+1 or Z−,m+1, then there is an m-zonoset contradicting Proposition 3.19. By
Theorem 3.16, RBMn,m cannot represent distributions with strong modes C.
17
As a side remark, Corollary 3.21 implies, in particular, that the graphical probability
model on the bipartite graph Kn,m (a fully observable version of the RBM model) does not
contain in its closure any distribution supported on a set Y⊂{ 0,1}n+m with
{(xi1 ,...,x im+1 ) ∈{0,1}m+1 : (x1,...,x n,xn+1,...,x n+m) ∈Y} = Z±,m+1
for some 1 ≤i1 <··· <im+1 ≤n.
In Section 3.7 (Corollary 3.34) we extend the statement of Corollary 3.21 by showing
that RBM6,5 cannot represent distributions with 2 6−1 strong modes.
3.5.1 Polyhedral approximation of the full-dimensional model RBM3,2
The model RBM 3,2 is particularly interesting, because it is the smallest candidate of an
RBM universal approximator on {0,1}3 in terms of the number of mixture components of
the mixtures of products that it represents, but it has less than 2 n−1 −1 hidden units, the
upper bound for the number of hidden units of the smallest RBM universal approximator
given in [19]. Note that the model RBM 3,1 = M3,2 is readily full dimensional.
By Corollary 3.21, RBM 3,2 does not contain any distribution with four strong modes.
We illustrate this explicitly: By Theorem 3.16, if RBM 3,2 ∩H3 ̸= ∅, then
sgn


B
W1 + B
W2 + B
W1 + W2 + B

=


+ − −
− + −
− − +
+ + +

 (3)
up to permutations of rows. But it is quickly veriﬁed that this equation cannot be satisﬁed.
The set H3 is the disjoint union of H+
3 = HZ+,3 and H−
3 = HZ−,3 . The set H+
3 is
the 7-dimensional simplex deﬁned by the intersection of the 8 half-spaces with inequalities
p(z) ≥∑
y:dH(z,y)=1 p(y) for z ∈Z+,3 and p(y) ≥0 for all y ∈Z−,3. Its vertices are the
uniform distributions on the following sets:
{000,001,011,101},{011,101,110,111},{000,010,011,110},{000,100,101,110},
{000},{011},{101},{110}.
Denote these distributions by u1,...,u 8 ∈P3 ⊂R8. The volume of H+
3 satisﬁes
vol(H+
3 )/vol(P3) = det(u1,...,u 8) = 1
256 = 0.00390625.
Since H+
3 and H−
3 are congruent, we obtain vol( H3)/vol(P3) = 1
128 = 0.0078125. This is a
lower bound for vol(P3 \RBM3,2)/vol(P3).
Now let us brieﬂy discuss to what extent H3 exhausts the complement of RBM 3,2. The
ﬁrst four vertices of H+
3 , u1,...,u 4, are mixtures of two point measures and one uniform
distribution on a pair of Hamming distance one. The last four vertices, u5,...,u 8, are the
point measures on Z+,3. By [22, Theorem 1], all these distributions are contained in RBM 3,2
(by symmetry, the vertices of H−
3 are also in RBM 3,2). The distributions in the relative
interiors of the edges between the ﬁrst four vertices are not in RBM 3,2. The relative interior
18
of edges connecting one of the ﬁrst four and one of the last four vertices are in RBM 3,2 if
they have support of cardinality four and are not if they have support of cardinality ﬁve.
We conjecture that RBM3,2 ∩G3 = ∅.
3.6 Linear threshold codes
Deﬁnition 3.22. A linear threshold function (LTF) with m inputs is a function
f: {0,1}m →{−,+}; y↦→sgn((
∑
j∈[m]
wjyj) + b),
where w∈Rm is called weight vector and b∈R bias. A subset C⊂{ 0,1}m ⊂Rm is linearly
separable iﬀ there exists an LTF with f(C) = + and f({0,1}m\C) = −. For convenience we
identify −/+ and 0/1 vectors via −↔ 0 and + ↔1. The opposite xof a binary vector xis
the vector given by inverting all entries of x.
LTFs are also known as McCulloch-Pitts neurons and have been studied in the context of
feed-forward artiﬁcial neural networks. The problem of separating subsets of vertices of the
m-dimensional hypercube by hyperplane arrangements (multi-label classiﬁcation) has drawn
much attention, see, e.g., [33]. It is known that the logarithm of the number of LTFs with
minputs is asymptotically of order m2, see [37, 25], but the exact number is only known for
m ≤9, see [34, 23, 24]. The study of LTFs simpliﬁes when f(x1,...,x m) = f(x1,..., xm)
for all x∈{0,1}m, in which case they are called self-dual. If an LTF has an equal number of
positive and negative points, then it separates every input from its opposite and is self-dual.
Deﬁnition 3.23. A subset C⊆{ 0,1}n ∼= {−,+}n is an (n,m)-linear threshold code (LTC)
if there exist n linear threshold functions fi: {0,1}m →{0,1}, i∈[n] with
{(f1(y),f2(y),...,f n(y)) ∈{0,1}n: y∈{0,1}m}= C.
Equivalently,Cis an (n,m)-LTC if it is the image of the down inference function of RBMn,m
for some choice of the model parameters. If all fi can be chosen self-dual, then Cis called
homogeneous.
In the following examples, an LTF with m inputs is written as a list of the vertices of
the m-cube with a bar on inputs with negative output and no bar on inputs with positive
output. For notational convenience, each vertex x = (x1,...,x m) ∈{0,1}m is labeled by
1 + ∑
j∈[m] 2j−1xj, which is the decimal representation of the binary vector plus one. For
example, an LTF with two inputs, mapping (00) ,(01) to 0 and (10) ,(11) to 1, is written as
1234.
Example 3.24. Let n = 3 and m = 2. There are only two ways to linearly separate the
vertices of the unit square into sets of cardinality two: 12 34 and 1 234. These are the only
possible columns of a homogeneous LTC with two inputs (up to opposites). The code Z±,3
is not a (3,2)-LTC, because it has three non-equivalent columns. This shows that there does
not exist a 2-zonoset with vertices in the four even, or odd, orthants of R3, and that RBM3,2
does not contain any distributions with four strong modes.
19
Figure 6: The four slicings of the 3-cube discussed in Example 3.25.
An alternative way of proving this is as follows. The Hamming distance between any
two elements of Z±,n is even. If the distance of any two vertices of the square induced by
an arrangement of three lines is even and non-zero, then each edge of the square is sliced at
least twice, and in total at least 8 edges are sliced (repetitions allowed). On the other hand,
each line slices at most two edges of the square, and so three lines slice at most 6 edges
(repetitions allowed).
Example 3.25. Let n= 4 and m= 3. There are 104 ways to linearly separate the vertices
of the 3-cube, see [25]. A complete list appears in [3, Section 3.8]. The vertices of the 3-cube
are in the Z+,4-cells of an arrangement of four hyperplanes corresponding to the (4 ,3)-LTC
with following LTFs:
12345678, 12345678, 12345678, 12345678.
This arrangement corresponds to a 3-zonoset with points in the 8 even orthants of R4 (The-
orem 1.6). The zonoset can be realized as follows:
w=


−1 −1 −1 1
−1 −1 1 −1
−1 1 −1 −1

;
b=1
2
(
3 1 1 1
)
;
Z= 1
2


3 1 1 1
1 3 −1 −1
1 −1 3 −1
−1 1 1 −3
1 −1 −1 3
−1 1 −3 1
−1 −3 1 1
−3 −1 −1 −1


. (5)
This choice of wand bcorresponds to a central arrangement of four hyperplanes slicing each
edge of the 3-cube exactly twice, as shown in Figure 6.
20
Example 3.26. Let n = 5 and m = 4. There are three symmetry types of self-dual LTFs
with four inputs, see [23]. The following are representatives of the three types:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 ;
1 2 3 4 5 6 7 89 10 11 12 13 14 15 16 ;
1 2 3 4 5 6 7 89 10 11 12 13 14 15 16.
By Proposition 3.19, the code Z±,5 cannot be realized by any 5 LTFs, i.e., as a (5 ,4)-LTC,
and RBM5,4 does not contain any distribution with 16 strong modes.
The following example presents a kind of binary codeCof cardinality 2m with RBMn,m∩HC =
∅which is not covered by Corollary 3.21.
Example 3.27. Let n= 5 and m= 3. Let x′,x′′∈Z±,4 with dH(x′,x′′) = 4, and
C =
{
(x1,...,x 5): ( x1,...,x 4) ∈ Z±,4,x5 =
{
1 if ( x1,...,x 4) ∈{x′,x′′}
0 otherwise
}
.
If Cis an LTC, some hyperplane separates two vertices of the 3-cube from the other vertices
(corresponding to x5 = 1 only for two points). These two vertices must be connected by an
edge of the 3-cube. Since dH(x′,x′′) = 4, four hyperplanes pass through this edge. There
are only three diﬀerent central hyperplanes through an edge of the 3-cube, but four diﬀerent
central hyperplanes are required to produce Z±,4. Hence Cis not a (5 ,3)-LTC.
3.7 Multi-covering numbers of hypercubes
The previous section shows that the sets of strong modes realizable by RBM n,m are related
to the solution of the following problem:
Problem 3.28. Let m ≤n. Consider an m-zonoset Zin Rn which does not intersect any
two orthants separated by a single coordinate hyperplane. How many orthants of Rn does
Zintersect at most?
As we discuss in the following, this problem is related to the long standing problem of
computing the covering numbers of hypercubes.
Deﬁnition 3.29. The covering number of a hypercube is the smallest number of hyperplanes
that slice each edge of the hypercube at least once. An edge is sliced by a hyperplane if the
hyperplane intersects the relative interior of the edge and does not contain any vertices of
the hypercube. A cut is the collection of all edges sliced by a hyperplane and corresponds to
a linear threshold function.
The mhyperplanes with normal vectors equal to the standard basis ofRm passing through
the center of the m-dimensional hypercube slice all its edges. This arrangement is not always
optimal. Paterson found 5 hyperplanes slicing all edges of the 6-cube, see [29]. This shows
that covering numbers do not behave trivially. The covering numbers are known only for
hypercubes of dimension ≤6. Computing them in higher dimensions is challenging, even in
the cases where all cuts are known. Now:
21
Proposition 3.30. If Z+,n is an (n,n −1)-LTC, then there exists an arrangement of n
hyperplanes through the center of the (n−1)-cube slicing each edge an even non-zero number
of times.
Proof. Given the assumption, there exists an arrangement of n hyperplanes in Rn−1 such
that each vertex of the (n−1)-cube is in one of theZ+,n-cells of the arrangement. Each vertex
is separated by an even, positive number of hyperplanes from any other vertex, since any
two elements of Z+,n diﬀer in an even number of entries. Two vertices cannot be contained
in the same cell of the arrangement, since |Z+,n|= 2n−1 equals the total number of vertices
of the (n−1)-cube. The code Z+,n is homogeneous, as each coordinate i∈[n] has the same
number of zeros and ones, and hence each hyperplane in the arrangement can be chosen
through the center of the cube.
Proposition 3.30 motivates the following problem:
Problem 3.31 (Multi-covering number). What is the smallest arrangement of hyperplanes,
if one exists, that slices each edge of a hypercube a given number of times?
Of particular interest is the number of hyperplanes needed to slice each edge of the m-
cube an even non-zero number of times. The edges of the m-cube can be sliced exactly twice
by 2m hyperplanes with normal vectors equal to the standard basis vectors of Rm, counted
with multiplicity two. Proposition 3.19 shows that if mis even and larger than zero, there is
no arrangement of (m+1) hyperplanes for which each vertex of the m-cube lies in a diﬀerent
cell and any two vertices are separated by an even number of hyperplanes. This suggests
that when mis even, there is no arrangement of ( m+ 1) hyperplanes slicing all edges of the
m-cube exactly twice; at least not one for which each vertex lies in a diﬀerent cell.
There is exactly one way to slice all edges of the 3-cube an even non-zero number of times
by four hyperplanes, namely the way illustrated in Figure 6. To see that this is the only way,
note that the 3-cube has 12 edges and that there are only 4 diﬀerent cuts that slice 6 edges.
The 4-cube has 16 vertices, 32 edges, a total of 940 diﬀerent cuts, 3 symmetry classes
of central cuts, and 52 diﬀerent central cuts. The maximal number of edges sliced by a cut
is 12. Hence:
Proposition 3.32. There is no arrangement of ﬁve hyperplanes, or less, slicing each edge
of the four-dimensional cube at least twice.
The complexity of the next easiest example is considerable. We tested all combinations
of six cuts of the 5-cube and found:
Computation 3.33. There is no arrangement of six, or less, central hyperplanes slicing
each edge of the ﬁve-dimensional cube an even non-zero number of times.
In the following we explain some details of the computation. The 5-cube has 80 edges.
There are 47 285 diﬀerent ways of slicing them with aﬃne hyperplanes, see [9]. A cut is given
by the indicator function on the set of edges sliced. A list of the cuts can be found in [36].
An edge of the m-cube corresponds to a pair of binary vectors of length m which diﬀer in
exactly one entry. Each edge is parallel to one coordinate vector of Rm. The edges can
be organized in m groups, corresponding to their directions. Within each group, the edges
22
are naturally enumerated by the binary vectors of length ( m−1) containing the coordinate
values that are equal for the two vertices of each edge. The central cuts can be characterized
as the cuts which involve only pairs of opposite edges. The 5-cube allows 7 symmetry classes
of central cuts and 941 diﬀerent central cuts. For each choice of 6, or less, central cuts
we computed the entry-wise addition of the indicator functions and found that this never
produced an even non-zero value in each entry. On the other hand, 5 is the covering number
of the 5-cube, see [9], and hence at least 6 hyperplanes are needed to slice each edge twice.
As a consequence of Computation 3.33 we have:
Corollary 3.34. The model RBM6,5 cannot represent any probability distribution with 32
strong modes.
Indeed, we trained RBM 6,5 to approximate the uniform probability distribution on Z+,6
and found a Kullback-Leibler divergence minimum of 0 .6309 (with base-two logarithm),
which is a relatively large value. For this computation we used contrastive divergence [14]
and likelihood gradient with numerous parameter initializations.
3.8 Proof of Theorem 1.6
The equivalence theorem from the introduction (illustrated in Figure 3) is a summary of
observations from the previous subsections. For completeness we provide a proof. Recall the
deﬁnition of LTC, PR, HP, ZP, SM, and SP given in Deﬁnition 1.5. Let nand mbe two
integers and C⊆{ 0,1}n.
1. The properties LTC, HP, and ZP are equivalent.
Let W and Bbe parameters making Ca linear threshold code, so that C= {sgn(h⊤W+
B): h∈{0,1}m}. Let Wi, i= 1,...,n be the columns of W. The sign of h⊤Wi + Bi,
h∈{0,1}m indicates which side of hyperplane Hi in the arrangement AW,B this hlies
on. Dually, the sign of h⊤Wi+Bi indicates which side of the i-th coordinate hyperplane
in Rn the point h⊤W + B of the zonoset lies on.
2. If Csatisﬁes PR or SM, then it is contained in an LTC set.
For Cto be the perfectly reconstructible, in particular it must be a subset of the image
of a down inference function.
If C has the SM property, its vectors are at least Hamming distance 2 apart. By
Theorem 3.7, each point in Cis the unique maximizer of a conditional distribution
p(·|h) and an image point of the down inference function.
3. If the vectors in Care at least Hamming distance 2 apart, then SP implies both SM
and PR.
SP with Hamming distance two implies that there is a distribution p∈RBMn,m with
p(v) >0 for each v ∈C, and p(v′) = 0 for each neighbor v′ of each v ∈C. Therefore,
each element of Cis a strong mode of p, and SM. Writing pθ(v,h) as a matrix with
rows labeled by h, the Hamming distance two condition implies by Theorem 3.7 that
each row has a single non-zero entry, so downθ◦upθ is the identity on C, so PR holds.
23
4. If the vectors in Care at least Hamming distance 2 apart and Csatisﬁes an ℓ1 property,
then LTC implies SP.
This is by Theorem 3.16.
4 Relative representational power
4.1 When does a mixture of products contain an RBM?
Using the characterizations obtained in Sections 3.3 and 3.4, we now prove the result on
relative representational power discussed in the introduction and depicted in Figure 2. To
do this, we derive upper bounds for the smallest m such that RBMn,m contains probability
distributions with l strong modes, and show thereby that RBMs can represent many more
modes than mixtures of products with the same number of parameters.
Any representability result, as Example 3.25, combined with the following observation,
yields lower bounds on the smallest mixture of products which contains the RBM model.
Observation 4.1. Let k ∈N. Assume that for each i ∈[k] there is a matrix W(i) ∈Rmi×ni
and a vector B(i) ∈Rni which generate a zonoset {h⊤W(i) + B(i) : h∈{0,1}mi}intersecting
Ki even orthants of Rni. Then
W =


W(1)
...
W(k)

 and B = (B(1),...,B (k))
generate a zonoset {h⊤W + B: h ∈{0,1}m1+···+mk}intersecting ∏
i∈[k] Ki even orthants of
Rn1+···+nk.
The following theorem provides the justiﬁcation for the statement in the introduction
that “the number of parameters of the smallest mixture of products model containing an
RBM model grows exponentially in the number of parameters of the RBM for any ﬁxed ratio
0<m/n< ∞,” and for Figure 2.
Theorem 4.2. Let n,m ∈N.
•If 4⌈m/3⌉≤ n, then RBMn,m∩Hn,2m ̸= ∅and
Mn,k ⊇RBMn,m iﬀ k≥2m.
•If 4⌈m/3⌉>n, then RBMn,m∩Hn,L ̸= ∅and
Mn,k ⊇RBMn,m only if k≥L,
where L:= min{2l + m−l,2n−1}, l:= max{l∈N: 4⌈l/3⌉≤ n}.
Proof. Let 4⌈m/3⌉≤ n. The if direction follows from RBM n,m ⊆Mn,2m for all n and m.
For the only if direction we show that RBMn,m contains a probability distribution supported
on a set of cardinality 2m and minimum Hamming distance at least two (a distribution with
24
2m strong modes). By Theorem 3.7 such a distribution is in Mn,k only if k≥2m. Consider
the following parameters:
W = α


w
w
...
w
˜w
0


;
B = α(b,b,...,b, −1,..., −1) ;
b = 1
2 (3,1,1,1);
C = −W1
2 (1,..., 1)⊤= α(1,..., 1)⊤,
where α∈R is a constant, w is the 3 ×4-matrix deﬁned in eq. (5), ˜w consists of the ﬁrst or
the ﬁrst two rows of w, and B is α times ⌈m/3⌉copies of b followed by −1s. Let λi be the
set of indices {1,2,3,4}+ 4(i−1) ⊂[n]. For α →∞ the visible distribution generated by
RBMn,m with parameters W,B, and C is the uniform distribution on following subset ofZ+,n
of cardinality 2m: {v∈{0,1}n: ∑
j∈λi vj is even for all i, and vj = 0 for all j >4⌈m/3⌉}.
Now let 4 ⌈m/3⌉≥ n. By the ﬁrst part, RBM n,l contains some p with 2l strong modes
in Z+,n. Moreover, RBM n,l+1 contains µp+ (1 −µ)δx for any p ∈RBMn,l, x ∈{0,1}n and
µ∈[0,1] (see [17]), such that each additional hidden unit can be used to increase the number
of strong modes by one, until the set of strong modes is Z+,n.
Remark 4.3. The statement of the ﬁrst item of Theorem 4.2 remains true if m= 1 mod (3)
and 4⌊m/3⌋+ 2 ≤n. For n <3 we have Mn,k = RBMn,k−1 for any k ∈N. For n = 3 we
believe that M3,3 and RBM3,2 are very similar, if not equal.
4.2 When does an RBM contain a mixture of products?
Complementary to question of when a mixture of products contains a product of mixtures,
in this section we ask what is the smallest m for which RBM n,m contains Mn,k. We focus
on an instance which we ﬁnd particularly interesting:
Problem 4.4. Does RBMn,m contain the mixture of products Mn,m+1?
Both RBMn,m and Mn,m+1 have nm+n+mparameters and expected dimension min{nm+
n+ m,2n −1}. The expected dimension is also the true dimension of both models for most
choices of n and m [4, 6]. In the following we give a negative answer to Problem 4.4.
In the previous section we showed that the non-negative rank of probability distribu-
tions in the model RBM n,m is as large as 2 m; there are tables of probabilities (probability
distributions) represented by the RBM model, which cannot be represented as non-negative
sums of less than 2 m non-negative rank-one tables (product distributions). The rank of a
table p is the smallest number k such that p can be written as a sum of k rank-one tables.
Here, a multivariate probability distribution p = p(x1,...,x n) with xi ∈Xi, |Xi|= ri for
i = 1 ,...,n is expressed as an n-way r1 ×···× rn table with value p(x1,...,x n) at the
entry (x1,...,x n). A rank-one table is an outer-product of n vectors of lengths r1,...,r n.
A product distribution in Mn,1 is the outer-product of the marginal distributions on the
variables x1 through xn and is a non-negative rank-one table. By deﬁnition, the elements of
Mn,k have non-negative rank at most k, and therefore also rank at most k. Since RBM n,m
is contained in Mn,2m, any p∈RBMn,m has rank at most 2 m.
25
Two models Aand B are called generically distinguishable if A∩B has relative measure
zero in Aand in B. The restriction “generically” is useful, because in most cases of interest
the models do intersect (e.g., mixtures of products and RBMs contain the uniform distribu-
tion). A ﬂattening of a table of probabilities is a way of arranging its entries in a two-way
table (i.e., a matrix) by grouping the variables in two groups and considering the joint states
of the variables in each of the groups as the states of two variables. The following is an
example of a ﬂattening of a table p for four binary variables:
p=


p00,00 p00,01 p00,10 p00,11
p01,00 p01,01 p01,10 p01,11
p10,00 p10,01 p10,10 p10,11
p11,00 p11,01 p11,10 p11,11

.
The matrix rank of any ﬂattening of a table p is upper bounded by the outer-product rank
of p. In particular, the vanishing of the ( k+ 1) ×(k+ 1)-minors of ﬂattenings are algebraic
invariants of the model Mn,k.
Theorem 4.5. If m≤n/2, then the model RBMn,m contains points of rank 2m. If, further-
more, m+1 ̸= 3 or n̸= 4, then the models RBMn,m and Mn,m+1 have dimension nm+n+m
and intersect at a set of dimension strictly less than nm+ n+ m.
Proof. We show that if m ≤n/2, then RBM n,m contains a point p with a ﬂattening of
rank 2m, which implies that p has outer-product rank 2 m. The ﬂattenings of any q ∈Mn,k
have rank at most k. This gives an algebraic invariant of the mixture of products model
Mn,m+1 which is not satisﬁed by elements of RBMn,m. Hence, if both models have the same
dimension d, then they intersect at a set of dimension strictly less than d.
Consider the m-cube and the 2 m hyperplanes through its center consisting of translates
of the coordinate hyperplanes with multiplicity two. This hyperplane arrangement slices
each edge of the m-cube exactly twice and generates a (2 m,m)-LTC Cof minimum distance
two. The code Cconsists of the 2m binary vectors xin {0,1}2m with xi = xi+1 for all odd i,
and {(x1,x3,...,x 2m−1): x∈C} = {0,1}m. In the case m= 3, for example, the code is
C=


0 0 0 0 0 0
1 1 0 0 0 0
0 0 1 1 0 0
0 0 0 0 1 1
1 1 1 1 0 0
1 1 0 0 1 1
0 0 1 1 1 1
1 1 1 1 1 1


.
By Theorem 3.16, RBM2m,m contains the uniform distribution on C, uC. View uC as a linear
transformation from the 2 m-dimensional space of real valued functions of x1,x3,...,x 2m−1
to the space of functions of x2,x4,...,x 2m. Then
uC =


1/2m
1/2m
...
1/2m

,
26
which has rank 2m.
5 Discussion
RBMs create a multi-labeling of their input space by the most likely joint states of their
hidden units given the inputs. The number of inference regions that can be generated
in this way is of exponential order in the number of RBM parameters. The partitions
of Rn generated by an RBM with n visible and m hidden units can be identiﬁed with
the intersections of aﬃne spaces of dimension d ≤ min{n,m}with the orthants of Rm,
whereby each aﬃne space corresponds to a choice of the RBM parameters. We elaborated
on the combinatorics of the resulting hyperplane arrangements, and on the combinatorics of
point conﬁgurations in such hyperplane arrangements, in correspondence with the inference
functions on the set of binary input vectors {0,1}n ⊂Rn. Although the theory of hyperplane
arrangements and linear separation of points is well studied in the literature, it still poses
many questions (see examples below).
We analyzed the sets of strong modes of probability distributions represented by RBMs
and related them to the hyperplane arrangements and linear threshold codes (multi-labelings)
mentioned above. The products of mixtures represented by RBMs are compact representa-
tions of probability distributions with many strong modes; of order min {2m,2n−1}for the
RBM with nvisible and mhidden units (exponential in the number of parameters). At the
same time, Corollaries 3.21 and 3.34 show that the hard bound min {2m,2n−1}is not always
attained. Mixture models of product distributions (na¨ ıve Bayes models), on the other hand,
generate less restricted input space partitions but into at most as many regions as mixture
components, and can only represent probability distributions with a number of strong modes
of linear order in the number of model parameters.
These results imply that the smallest mixture model of product distributions that con-
tains an RBM model is, in most cases, as large as one can possibly expect, having one mixture
component per joint state of the RBM hidden units, and thus a number of parameters that
is exponential in the number of RBM parameters. RBMs can represent distributions with
many strong modes much more compactly than standard mixture models. This gives a con-
cise combinatorial way of diﬀerentiating the two models. Fixing dimension, the RBMs which
are hardest to represent as mixtures of product distributions are those with about the same
number of visible and hidden units. At the same time, we note that there may exist small
mixtures of product distributions which cannot be compactly represented by RBMs. For
instance, Theorem 4.5 shows that Mn,m+1 ̸⊆RBMn,m when 3 ≤m≤n/2.
These results aid our understanding of how models complement each other, and why
distributed representations in deep learning [2] can be expected to succeed, or when model
selection can be based on theory rather than trial-and-error. They conﬁrm the intuition
that distributed representations are exponentially more powerful than non-distributed ones,
in the case of binary RBMs and taking the number of strong modes, inference functions, and
non-trivial perfectly reconstructible input sets as a measure of complexity. Other measures
of complexity of probability distributions, such as multi-information, which is deﬁned as
the Kullback-Leibler divergence to the set of product distributions, are interesting but not
necessarily best for diﬀerentiating between mixtures of products and RBMs. In terms of
27
multi-information the most complex binary probability distributions have the form p =
1
2 (δx + δy) with xi + yi = 1 for all i, see [1], and are contained in any (non-trivial) mixtures
of products and RBM models.
Our approach has produced at least an order-of-magnitude or asymptotic understanding
of the models we discuss. We have also shown that to understand them fully would proba-
bly mean understanding as well some seemingly diﬃcult equivalent combinatorial problems
concerning linear threshold codes, hyperplane arrangements, multi-covering numbers, and so
on. On the other hand, we expect that our techniques can be used eﬀectively to study more
complex models in a similar fashion.
A number of problems is covered only partially by our analysis. Some interesting open
cases include:
•Computing multi-covering numbers for hypercubes of odd dimension larger than ﬁve.
•Characterizing the support sets of fully observable RBM models. This problem can
be seen to be equivalent to characterizing the face lattices of polytopes deﬁned as
Kronecker products of hypercubes.
•Computing the maximal cardinality of linear threshold codes of minimum Hamming
distance two. Are there cases where the ﬁrst item of Theorem 4.2 holds for 4⌈m/3⌉>n,
m≤n−1, assuming m̸= n−1 when n is odd?
•Can RBM8,7 represent probability distributions with 2 7 strong modes?
•Verifying the conjecture that RBM3,2 ∩G3 = ∅, and, in addition, proving or disproving
M3,3 = RBM3,2.
•For 2 <m< 2n−1 −1, does RBMn,m contain Mn,m?
Acknowledgments
The authors are grateful to Johannes Rauh for helpful discussions on algebraic invariants, to
Nihat Ay for comments on hyperplane arrangements, to Yoshua Bengio for helpful discussions
regarding distributed representations, and to Bernd Sturmfels for discussions motivating the
analysis of mixtures of products in RBMs. The authors acknowledge use of the RCC-ITS
computer cluster at the Pennsylvania State University. This work is supported in part by
DARPA grant FA8650-11-1-7145.
References
[1] N. Ay and A. Knauf. Maximizing multi-information. Kybernetika, 42:517–538, 2006.
[2] Y. Bengio. Learning deep architectures for AI. Foundations and Trends in Machine
Learning, 2(1):1–127, 2009.
[3] A. Bj¨ orner, M. L. Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented Ma-
troids, volume 46 of Encyclopedia of Mathematics and Its Applications . Cambridge
University Press, 1999.
28
[4] M. V. Catalisano, A. V. Geramita, and A. Gimigliano. Secant varieties of P1 ×···× P1
(n-times) are not defective for n≥5. J. Algebraic Geometry, 20:295–327, 2011.
[5] T. M. Cover. Geometrical and statistical properties of systems of linear inequalities
with applications in pattern recognition. IEEE Transactions on Electronic Computers ,
EC-14(3):326–334, 1965.
[6] M. A. Cueto, J. Morton, and B. Sturmfels. Geometry of the restricted Boltzmann
machine. In M. A. G. Viana and H. P. Wynn, editors, Algebraic methods in statistics
and probability II, AMS Special Session , volume 2. American Mathematical Society,
2010.
[7] M. A. Cueto, E. A. Tobis, and J. Yu. An implicitization challenge for binary factor
analysis. J. Symbolic Computation , 45:1296–1315, December 2010.
[8] J. Draisma. A tropical approach to secant dimensions. Journal of Pure Applied Algebra,
212(2):349–363, 2008.
[9] M. R. Emamy-Khansary and M. Ziegler. On the coverings of the d-cube for d ≤6.
Discrete Applied Mathematics, 156(17):3156–3165, 2008.
[10] L. Flatto. A new proof of the transposition theorem. Proceedings of the American
Mathematical Society, 24(1):29–31, 1970.
[11] E. Gawrilow and M. Joswig. Polymake: a framework for analyzing convex polytopes.
In Polytopes – Combinatorics and Computation , pages 43–74. Birkh¨ auser, 2000.
[12] D. Geiger, C. Meek, and B. Sturmfels. On the toric algebra of graphical models. Annals
of Statistics, 34:1463–1492, 2006.
[13] G. E. Hinton. Products of experts. In Proceedings of the 9-th ICANN, volume 1, pages
1–6, 1999.
[14] G. E. Hinton. Training products of experts by minimizing contrastive divergence.Neural
Computation, 14:1771–1800, 2002.
[15] T. Kahle, W. Wenzel, and N. Ay. Hierarchical models, marginal polytopes, and linear
codes. Kybernetika, 45:189–208, 2009.
[16] D. E. Knuth. Big omicron and big omega and big theta. SIGACT News, 8(2):18–24,
1976.
[17] N. Le Roux and Y. Bengio. Representational power of restricted Boltzmann machines
and deep belief networks. Neural Computation, 20(6):1631–1649, 2008.
[18] G. Mont´ ufar. Mixture decompositions of exponential families using a decomposition of
their sample spaces. Kybernetika, 49(1):23–39, 2013.
29
[19] 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.
[20] G. Mont´ ufar and J. Morton. Discrete restricted Boltzmann machines. In International
Conference on Learning Representations 2013 (ICLR 2013), Scottsdale, Arizona, USA ,
2013.
[21] G. Mont´ ufar and J. Morton. Dimension of hidden-visible products of exponential fam-
ilies. Unpublished manuscript, 2014.
[22] G. Mont´ ufar, J. Rauh, and N. Ay. Expressive power and approximation errors of
restricted Boltzmann machines. In NIPS 24, pages 415–423, 2011.
[23] S. Muroga, T. Tsuboi, and C. Baugh. Enumeration of threshold functions of eight
variables. IEEE Transactions on Computers , C-19(9):818–825, sept. 1970.
[24] OEIS. The on-line encyclopedia of integer sequences, A000609 Number of threshold
functions of n or fewer variables, 2010. Published electronically at http://oeis.org,
2010.
[25] P. C. Ojha. Enumeration of linear threshold functions from the lattice of hyperplane
intersections. IEEE Transactions on Neural Networks , 11(4):839–850, jul 2000.
[26] P. Orlik and H. Terao. Arrangements of Hyperplanes. Springer-Verlag, 1992.
[27] J. Rauh, T. Kahle, and N. Ay. Support sets of exponential families and oriented ma-
troids. International Journal of Approximate Reasoning , 52(5):613–626, 2011.
[28] S. Ray and B. G. Lindsay. The topography of multivariate normal mixtures. Annals of
Statistics, 33(5):2042–2065, 2005.
[29] M. E. Saks. Slicing the hypercube. In K. Walker, editor, Surveys in combinatorics ,
pages 211–255. Cambridge University Press, New York, NY, USA, 1993.
[30] L. Schl¨ aﬂi. Theorie der vielfachen Kontinuit¨ at. Cornell University Library historical
math monographs. George & Company, 1901.
[31] L. Schl¨ aﬂi. Gesammelte mathematische Abhandlungen . Number v. 2 in Gesammelte
mathematische Abhandlungen. Birkh¨ auser, 1953.
[32] R. Stanley. An introduction to hyperplane arrangements. In Lecture notes, IAS/Park
City Mathematics Institute , 2004.
[33] W. Wenzel, N. Ay, and F. Pasemann. Hyperplane arrangements separating arbitrary
vertex classes in n-cubes. Advances in Applied Mathematics , 25(3):284–306, 2000.
[34] R. O. Winder. Enumeration of seven-argument threshold functions. IEEE Transactions
on Electronic Computers, EC-14(3):315–325, 1965. See also correction in EC-16(2):231,
1967.
30
[35] G. M. Ziegler. Lectures on polytopes. Graduate texts in mathematics. Springer-Verlag,
1995.
[36] M. Ziegler. The cut number home page. http://www2.cs.uni-paderborn.de/cs/
ag-madh/WWW/CUBECUTS/.
[37] Y. A. Zuev. Asymptotics of the logarithm of the number of threshold functions of the
algebra of logic. Soviet Mathematics Doklady , 39(3):512–513, 1989.
1 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 0
0 1 /4 1 /4 1 /4 0 0 0 1 /4
1/4 0 1 /4 1 /4 0 0 1 /4 0
1/4 1 /4 0 1 /4 0 1 /4 0 0
1/4 1 /4 1 /4 0 1 /4 0 0 0
1/6 1 /6 1 /6 1 /6 0 1 /6 0 1 /6
1/6 1 /6 1 /6 1 /6 1 /6 0 0 1 /6
1/6 1 /6 1 /6 1 /6 0 0 1 /6 1 /6
1/6 1 /6 1 /6 1 /6 1 /6 1 /6 0 0
1/6 1 /6 1 /6 1 /6 1 /6 0 1 /6 0
1/6 1 /6 1 /6 1 /6 0 1 /6 1 /6 0
1/7 1 /7 1 /7 1 /7 0 1 /7 1 /7 1 /7
1/7 1 /7 1 /7 1 /7 1 /7 0 1 /7 1 /7
1/7 1 /7 1 /7 1 /7 1 /7 1 /7 0 1 /7
1/7 1 /7 1 /7 1 /7 1 /7 1 /7 1 /7 0
1/8 1 /8 1 /8 1 /8 1 /8 1 /8 1 /8 1 /8
(000) (011) (101) (110) (001) (010) (100) (111)
Table 1: Vertex-presentation of the polytope G+
3 ⊂ P3 ⊂ R8
(the set of probability distributions on {0,1}3 with modes Z+,3 =
{(000),(011),(101),(110)}). Each row is a probability distribution that is a
vertex of G+
3 . The vertices in the ﬁrst group are the point measures on Z+,3.
They have degree 18 (i.e., they are incident to 18 edges) and are connected
by edges to all other vertices. The vertices in the second and fourth groups
have degree 11. There are no edges between pairs of vertices in the second
group. The vertices in the third group have degree 8. The uniform distri-
bution has degree 12. The f-vector of the polytope, indicating the number
of faces in each dimension, is f(G
+
3 ) = (19 ,110,290,387,270,96,16). The
volume is vol(G+
3 )/vol(P3) = 1/56.
31
2 3 4 5 8 10 12 13 16 17 18 19
2 3 4 5 7 9 12 14 15 17 18 19
2 3 4 5 6 11 13 14 15 16 18 19
1 3 4 6 8 10 12 13 16 17 18 19
1 3 4 6 7 9 12 14 15 17 18 19
1 3 4 5 6 9 10 11 15 16 17 19
1 2 4 7 8 10 12 13 16 17 18 19
1 2 4 6 7 11 13 14 15 16 18 19
1 2 4 5 7 9 10 11 15 16 17 19
1 2 3 7 8 9 12 14 15 17 18 19
1 2 3 6 8 11 13 14 15 16 18 19
1 2 3 5 8 9 10 11 15 16 17 19
1 2 3 4 6 7 8 12 13 14 18
1 2 3 4 5 6 7 9 11 14 15
1 2 3 4 5 6 8 10 11 13 16
1 2 3 4 5 7 8 9 10 12 17
Table 2: Vertex-facet incidence table for the polytope G+
3 . Each row gives
the list of vertices incident to one facet of G+
3 (the index of each vertex
corresponds to the row in which it appears in Table 1). The set of vertices
in any face of the polytope is an intersection of some of the 16 sets listed
above.
32


Peer review:
[Review]:
We thank all three reviewers for the helpful comments, which enabled us to improve the paper.  We have uploaded a revision to the arxiv taking into account the comments, and respond to some specific concerns below.

We were unsure as to whether we should make the paper longer by providing more in-line intuition around the steps of the proof of our main results. This would address the concerns of Reviewers 6c04 and 51ff, who thought some additional intuition throughout would be helpful, while Reviewer 51ff felt that the paper was perhaps too long as it was.  We elected to balance these concerns by making significant changes to improve clarity without greatly expanding the exposition, making a net addition of about a page of text. However, by moving some material to the appendix, the main portion of the paper has been reduced in length to 14 pages.

Responding to specific comments:

Reviewer 6c04:

>> Things I did not understand: 
>>- Fig. 1 (as a whole) 

We have reworked this figure and improved the explanation in the caption; the intensity of the shading represents the value of log(k), that is the function $f(m,n) = min { log(k): mathcal{M}_{n,k}$ contains RBM_{n,m} }$. 

>>- Last paragraph of 1.1: why is this interesting? 

Since we are arguing that the sets of probability distributions representable by RBMs and MoPs are quite different, we thought it would be interesting to mention what is known about when these two sets do intersect.  We have added a comment about this.

>>- Fig. 5 (not clear why it is in some kind of pseudo-3D and what is the meaning of all these lines -- also some explanations come after it is referenced, which does not help) 

We have reworked the figure and added additional explanation in the text where the figure is referenced. This is a picture of the interior of a 3-dimensional simplex (a tetrahedron with vertices corresponding to the outcomes (0,0), (0,1), (1,0), (1,1)), with three sets of probability distributions depicted. The curved set is a 2-dimensional surface. The regions at the top and bottom are polyhedra, and the lines in the original figure were the edges of these polyhedra (the edges in back have now been removed to make the rendering clearer). Additionally, we linked to an interactive 3-d graphic object of Fig. 5.  Using Adobe Acrobat Reader 7 (or higher) the reader can rotate and slice this object in 3-d. 

>>- '(...) and therefore it contains distributions with (...)': I may be missing something obvious, but I did not follow the logical link ('therefore') 

We expanded and rephrased this to hopefully be more clear.

>>- I am unable to parse Remark 22, not sure if there is a typo (double 'iff') or I am just not getting it.  

We rewrote this remark, sorry for the confusion.  The meaning was that the three statements (X iff Y iff Z) are equivalent.

>>Typos or minor points: 
>> - It seems like Fig. 3 and 4 should be swapped to match the order in which they appear in the text 
>>- 'Figure 3 shows an example of the partitions (...) defined by the models M_2,4 and RBM_2,3' -> mention also 'for some specific parameter values' to be really clear 
>>- Deptartment (x2) 
>>- Lebsegue 
>>- I believe the notation H_n is not explicitly defined (although it can be inferred from the definition of G_n) 
>>- There is a missing reference with a '?' on p. 9 after 'm <= 9' 
>>- It seems to me that section 6 is also related to the title of section 5. Should it be a subsection? 
>>- 'The product of mixtures represented by RBMs are (...)': products 
>>- 'Mixture model (...) generate': models

Thank you, we fixed these.



Reviewer 51ff:

>>In conclusion, this paper tackles a problem which seems to be too contrived to be of general interest. Further, it is written in an unfriendly way which makes it more appropriate to a very technical crowd. 
>>- the fact that there are exponentially many inference regions for an RBM whereas there are only a linear number of them for a MoP seems quite obvious, merely by counting the number of hidden states configurations. I understand this is far from a proof but this is to me more representative of the fact that one does not want to use the hidden states as a new representation for a MoP, which we already knew.

In part this is simply a difference of philosophy.  Some place greater emphasis on an intuition or demonstration on a dataset, while others prefer to see a proof.  We recognize we may not have a lot to offer those comfortable relying upon their intuitive or empirical grasp of the situation, and instead aim to provide some mathematical proof to back up that intuition and satisfy the second group.

In trying to show that one class of models (RBMs or distributed representations) is better than another (here, non-distributed representations or naive Bayes models) at representing complex distributions, one must make a choice of criteria for comparison.  One can pick, inevitably arbitrarily, a dataset for comparison and produce an empirical comparison.  To provide a proof or theoretical comparison, one must choose a metric of complexity.  Of course, we always want larger and more natural datasets and broader metrics, but one must start somewhere.  We felt that in measuring the complexity of a distribution, the bumpiness of a probability distribution, or number of local maxima, modes, or strong modes in the Hamming topology was a reasonable place to start.  While we examined other metrics of distribution complexity, this was one that provided enough leverage to distinguish the models.  In the Discussion section, we talk about why multi-information, for example, is not suitable for making this distinction.  Making such a choice of metric is the unfortunate price of theoretical justifications.

Additionally, the number of inference regions was not claimed to be new, but part of the exposition about the widespread intuition regarding distributed representations.  We have added some exposition to clarify this.

Why we chose MoP: we wanted to compare distributed representations with non-distributed representations.  Since we are interested in learning representations, these should be two models with hidden variables that hold the representation.  For a non-distributed model with hidden variables and the same observables as an RBM, the na'ive Bayes or MoP model is canonical.  For example, a k-way interaction model might also be a good comparison, but it lacks hidden nodes.



>>Additionnally, the paper is very heavy on definitions and gives very little intuition about the meaning of the results. Theorem 29 is a prime example as it takes a very long time to parse the result and I could really have used some intuition about the meaning of the result. This feeling is reinforced by the length of the paper (18 when the guidelines mentioned 9) and the inclusion of propositions which seem anecdotal (Prop.7, section 2.1, Corollary 18).

Sorry for the confusion.  The introduction, as well as Figure 1 is devoted to explaining and interpreting Theorem 29. The statements therein such as 'We find that the number of parameters of the smallest MoP model containing an RBM model grows exponentially in the number of parameters of the RBM for any fixed ratio $0!<!m/n!<!infty$, see Figure 1' are hopefully more-intuitive corollaries of Theorem 29.  The structure of the paper is to try to put the intuitive explanation of the results first, then give the (necessarily technical) proof showing how the results were obtained.  We have added a pointer before Theorem 29 to indicate this.

In the revision we added explanations providing additional intuition as to why we are making certain definitions, and a road map of how the main results are proved.

>>Minor comments: 
>> - Definition 2, you have that C is included in {0, 1}^n. That makes C a vector, not a set. 

No, a subset as we write $mathcal{C} subset mathcal{X}$ of the set of (binary) strings $mathcal{X}$ of length n is again a set of (binary) strings.  One could of course interpret it in terms of a vector of indicator functions, but this is not the approach needed here.

>> - Proposition 8: I think that G_3 should be G_4.

Sorry for the confusion.  Again this is correct as is; G_4 would refer to binary strings of length 4, while the Proposition concerns strings of length 3.