# Using Inherent Structures to design
Lean 2-layer RBMs

Abhishek Bansal
IBM Research
<EMAIL_ADDRESS>Abhinav Anand
IISc Bengaluru
<EMAIL_ADDRESS>Chiranjib Bhattacharyya
IISc Bengaluru
<EMAIL_ADDRESS>
###### Abstract

Understanding the representational power of Restricted Boltzmann Machines
(RBMs) with multiple layers is an ill-understood problem and is an area of
active research. Motivated from the approach of _Inherent Structure formalism_
[21], extensively used in analysing Spin Glasses, we propose a novel measure
called _Inherent Structure Capacity_ (ISC), which characterizes the
representation capacity of a fixed architecture RBM by the expected number of
modes of distributions emanating from the RBM with parameters drawn from a
prior distribution. Though ISC is intractable, we show that for a single layer
RBM architecture ISC approaches a finite constant as number of hidden units
are increased and to further improve the ISC, one needs to add a second layer.
Furthermore, we introduce _Lean_ RBMs, which are multi-layer RBMs where each
layer can have at-most $O(n)$ units with the number of visible units being
$n$. We show that for every single layer RBM with $\Omega(n^{2+r}),r\geq 0$,
hidden units there exists a two-layered _lean_ RBM with $\Theta(n^{2})$
parameters with the same ISC, establishing that 2 layer RBMs can achieve the
same representational power as single-layer RBMs but using far fewer number of
parameters. To the best of our knowledge, this is the first result which
quantitatively establishes the need for layering.

##  1 Introduction

Deep Boltzmann Machines (DBMs111We shall use the terms RBM and DBM
interchangebly) are largely tuned using empirical methods based on trial and
error. Despite much effort, there is still very little theoretical
understanding about why a particular neural network architecture works better
than another for any given application. Furthermore there is no well defined
metric to compare different network architectures.

It is known that given any input distribution on the set of binary vectors of
length $n$, there exists an RBM with $\alpha 2^{n}-1$ ($\alpha<1$) hidden
units that can approximate that distribution to an arbitrary precision [13].
However with these many hidden units the number of parameters increase
exponentially. We call a network _lean_ if for each layer, the number of
hidden units $m=\mathcal{O}(n)$ where $n$ is the number of visible units. The
deep narrow Boltzmann Machines whose universal approximation properties were
studied in [11] are a special case of lean networks. In this paper we study
lean 2-layer deep RBMs.

We ask the questions, is there a measure that can relate DBM architectures to
their representational power? Once we have such a measure then can we gain
insights into the capabilities of different DBM architectures?

For example, given a _wide_ single layer RBM, an RBM with many hidden nodes,
can we find a _lean_ multilayer RBM with equivalent representational power but
with far lesser parameters? Despite much effort these questions are not
satisfactorily answered and may provide important insights to the area of Deep
Learning.

Our main contributions are as follows:

  1. 1.

We study the _Inherent structures_ formalism, first introduced in Statistical
Mechanics[21], to understand the configuration space of RBMs. We introduce a
capacity measure Inherent Structure Capacity (ISC) (Definition 5) and discuss
its relation with the expected number of perfectly reconstructible vectors
[14], one-flip stable states and the modes of the input distribution. We use
this as a measure of representation power of an RBM.

  2. 2.

Existing methods for computing expected number of inherent structures are
rooted in Statistical Mechanics. They use the replica approach [4] which does
not extend well to DBMs since it is not straightforward to incorporate the
bipartite nature and layering in the calculations. We use a first principles
approach to devise a method that yields upper and lower bounds for single
layered and two-layered DBMs (Theorems 1,2). We show that the bounds become
tight as we increase the number of hidden units.

  3. 3.

Previous results have shown that a sufficiently large single layer RBM can
represent any distribution on the $2^{n}$ input visible vectors. However we
show that if we continue adding units to hidden layer then the ISC tapers to
$0.585$ as opposed to the maximum limit of $1.0$ (Corollary 2). This implies
that although an RBM is a universal approximator, if the input distribution
contains large number of modes multi-layering should be considered. We have
empirically verified that when the number of units in a single hidden layer
RBM, $m\geq 20n$, the ISC saturates (Figure 3).

  4. 4.

By analyzing the ISC for two layer RBM we obtain an interesting result that
for any such RBM with $m=\Omega(n^{2})$ hidden units (number of parameters
$\Omega(n^{3})$) one can construct a two layered DBM with $1.6n$ units in
hidden layer 1 and $0.6n$ units in layer 2 (Corollary 4) and with number of
parameters $\Theta(n^{2})$, resulting in an order of magnitude saving in
parameters. To the best of our knowledge this is the first such result which
establishes the superiority of 2 layer DBMs over wide single layer RBMs in
terms of representational efficiency. We conduct extensive experiments on
synthetic datasets to verify our claim.

##  2 Model Definition and Notations

An RBM with $n$ visible and $m$ hidden units, denoted by
$\text{RBM}_{n,m}(\theta)$, is a probability distribution on $\\{0,1\\}^{n}$
of the form

$P(\textbf{v},\textbf{h}|\theta)=\frac{e^{-E(\textbf{v},\textbf{h}|\theta)}}{Z(\theta)}$
(1)
$E(\textbf{v},\textbf{h}|\theta)=-\textbf{a}^{T}\textbf{v}-\textbf{b}^{T}\textbf{h}-\textbf{v}^{T}\textbf{W}\textbf{h}$
(2)

where $\textbf{v}\in\\{0,1\\}^{n}$ denotes the visible vector, hidden vector
is denoted by $\textbf{h}\in\\{0,1\\}^{m}$, the parameter
$\theta=\\{\textbf{a},\textbf{b},\textbf{W}\\}$ denotes the set of biases
$\textbf{a}\in\mathbb{R}^{n},\textbf{b}\in\mathbb{R}^{m}$ and coupling matrix
$\textbf{W}\in\mathbb{R}^{n\times m}$ and
$Z(\theta)=\sum_{\textbf{v},\textbf{h}}e^{-E(\textbf{v},\textbf{h})}$ is the
normalization constant. The log-likelihood of a given visible vector v for an
$\text{RBM}_{n,m}(\theta)$ is given by

${\mathcal{L}}(\textbf{v}|\theta)=\ln
P(\textbf{v}|\theta)=\ln\sum_{\textbf{h}}e^{-E(\textbf{v},\textbf{h})}-\ln
Z(\theta)$ (3)

In the sequel $\textbf{\text{RBM}}_{n,m}$ will denote the family of
distributions parameterized by $\text{RBM}_{n,m}(\theta)$.

######  Definition 1 (Modes).

Given a distribution $p$ on vectors $\\{0,1\\}^{n}$, a vector v is said to be
a mode of that distribution if for all $\textbf{v}^{\prime}$ such that
$d_{H}(\textbf{v},\textbf{v}^{\prime})=1$,
$p(\textbf{v})>p(\textbf{v}^{\prime})$. Here
$d_{H}(\textbf{v},\textbf{v}^{\prime})=\sum_{i=1}^{N}[1-\delta(\textbf{v}_{i},\textbf{v}^{\prime}_{i})]$
is the Hamming distance222We shall use $d_{H}$ to denote Hamming distance
between two vectors. $\delta(x,y)$ is the kronecker distance and is defined as
$\delta(x,y)=1$ whenever $x=y$, and $0$ otherwise..

######  Definition 2 (Perfectly Reconstructible Vectors).

For an $\text{RBM}_{n,m}(\theta)$ we define the function
$\operatorname{up}:\\{0,1\\}^{n}\to\\{0,1\\}^{m}$ that takes a visible vector
v as input and outputs the most likely hidden units vector h conditioned on v,
i.e.,
$\operatorname{up}(\textbf{v})\triangleq\operatorname{arg\,max}_{\textbf{h}}P(\textbf{h}|\textbf{v},\theta)$.
Similarly
$\operatorname{down}(\textbf{h})\triangleq\operatorname{arg\,max}_{\textbf{v}}P(\textbf{v}|\textbf{h},\theta)$.
A visible units vector v is said to be _perfectly reconstructible_ (PR) if
$\operatorname{down}(\operatorname{up}(\textbf{v}))=\textbf{v}$.

For any set $C$ the cardinality will be denoted by $|C|$. For an
$\text{RBM}_{n,m}(\theta)$ we define

$\operatorname{prv}(n,m,\theta)\triangleq|\\{\textbf{v}:\textbf{v}\text{ is
{PR} for }\text{RBM}_{n,m}(\theta)\\}|$

##  3 Problem Statement

We consider fitting an $\text{RBM}_{n,m}(\theta)$ to a distribution
$p(\textbf{v})=\frac{1}{k}\sum_{i=1}^{k}\delta(\textbf{v}-\textbf{v}_{i})$
where $\delta$ denotes the Dirac Delta function and where for each pair of
vectors $\\{\textbf{v}_{i},\textbf{v}_{j}\\}$ in
$\\{\textbf{v}_{r}\\}_{r=1}^{k}$, $d_{H}(\textbf{v}_{i},\textbf{v}_{j})\geq
2$. We need to find the smallest $m^{*}\in\mathbb{N}$ such that the set
$\textbf{\text{RBM}}_{n,m^{*}}$ contains an $\text{RBM}_{n,m^{*}}(\theta)$
that represents $p$. We also study the case of a DBM with 2 hiddden layers. We
denote a DBM with $n$ visible units, $L$ hidden layers with $m_{k}$ hidden
units in layer $k$ by $\text{RBM}_{n,m_{1},\ldots,m_{L}}(\theta)$. We denote
the respective set of DBMs by $\textbf{RBM}_{n,m_{1},\ldots,m_{L}}$. We would
like to ask the following question. Are there _lean_ two layer architectures,
$\textbf{\text{RBM}}_{n,m_{1},m_{2}}$ which can model distributions with the
same number of modes as that of distributions generated by a one layer
architecture $\textbf{\text{RBM}}_{n,m}$ where $m\gg m_{1},m_{2}$.

###  3.1 Related Work

The representational power of Restricted Boltzmann Machines (RBMs) is an
ongoing area of study [9, 15, 23, 10, 5].It is well known that an RBM with one
hidden layer is a universal approximator [9, 12, 13]. [9] showed that the set
$\textbf{RBM}_{n,m}$ can approximate any input distribution with support set
size $k$ arbitrarily well if following inequality is satisfied.

$m\geq k+1$ (4)

If we know the number of modes of our input distribution, then we could design
our RBM as per Eqn (4). Unfortunately the number of modes could be large
resulting in a large RBM.

Figure 1: Number of modes attained for different choices of hidden units for
$n=15$. Can be seen that the current known result for the number of hidden
units required (red graph) is a large over-estimate. The green and purple
graphs are estimates given by Theorem 1. These are closer to the actual number
of enumerated modes, given by the blue graph.

To test the bound in Eqn (4), we conducted simulation experiments. We kept
$n=15$, $m\in\\{10,25,50,75,100,125\\}$ and generated random coupling weight
matrix whose entries were i.i.d. $\mathcal{N}(0,1)$ and enumerated all the
modes of the generated distribution. We averaged our readings over 100
different weight matrices. The results are shown in Figure 1. The results show
that the bound gives a highly conservative estimate for $k$. _For example on
average the set $\textbf{\text{RBM}}_{15,50}$ has the capability to represent
distributions with 170 modes, instead of only 49 modes_. Thus although the
number of modes is an important design criteria, a more practical metric is
desirable.

##  4 Inherent structures of RBM

To understand the complex structure in Spin glasses the notion of _Inherent
Structures_(IS) was introduced in [21]. The IS approach consists of
partitioning the configuration space into _valleys_ , where each valley
consists of configurations in the vicinity of a local minimum. The number of
such valleys can thus be indicative of _Complexity_ of the system.

In this section we recall the IS approach in a general setting to motivate a
suitable capacity measure. Consider a system governed by the probability model

$P(\textbf{s}|W)=\frac{e^{-\frac{1}{T}E(\textbf{s}|W)}}{Z(W)},Z(W)=\sum_{\textbf{s}}e^{-\frac{1}{T}E(\textbf{s})}$
(5)

where $E:\\{0,1\\}^{N}\rightarrow\mathds{R}$ is an energy function defined
over $N$ dimensional binary vectors with parameter $W$.

######  Definition 3 (One-flip Stable States).

[20] For an Energy function $E$ a configuration, ${\textbf{s}}^{*}$ is called
a local minimum, also called One flip stable state, if
$\forall\textbf{s}\in\\{s:d_{H}({\textbf{s}},{\textbf{s}}^{*})=1\\},E({\textbf{s}})-E({\textbf{s}}^{*})>0$
(equivalently $P({\textbf{s}})<P({\textbf{s}}^{*})$).

For every one-flip stable state ${\textbf{s}}^{*}$ we define the set
$OF({\textbf{s}}^{*})=\\{{\textbf{s}}|\quad
d_{H}({\textbf{s}},{\textbf{s}}^{*})\leq 1\\}$. Let
$\\{{\mathcal{P}}_{1},\ldots,{\mathcal{P}}_{K}\\}$ form a partition of the
configuration space where each ${\mathcal{P}}_{a}=OF({\textbf{s}}_{a})$
corresponds to the local minimum ${\textbf{s}}_{a}$ and $K$ is the total
number of valleys 333Here we assume that temperature parameter $T$ is small so
that all states with Hamming distance $>1$ from a one-flip stable state will
have negligible contribution to partition function.. The logarithm of the
partition function

$\log
Z(W)=\log\sum_{{\textbf{s}}}e^{-\frac{1}{T}E({\textbf{s}})}=\log\sum_{a=1}^{K}Z_{a}(W)$

where $Z_{a}(W)=\sum_{{\textbf{s}}\in P_{a}}e^{-\frac{1}{T}E({\textbf{s}})}$.
Now, for any $p$ in a $K$ dimensional probability simplex, using the non-
negativity of KL divergence, it is straightforward to show that

$H(p)+\sum_{a=1}^{K}p_{a}\log Z_{a}(W)\leq\log Z(W)$ (6)

where $H(p)=-\sum_{a=1}^{K}p_{a}\log p_{a}$ is the entropy of $p$. Equality
holds whenever $p_{a}^{*}=\frac{Z_{a}}{Z},\forall a\in\\{1,\ldots,K\\}$. One
could construct $\log Z$ from $\log Z_{a}$ if one had access to $p^{*}$, and
knew $K^{*}$ which is defined as $H(p^{*})=logK^{*}$.

$\log K^{*}+\sum_{a=1}^{K}p^{*}_{a}\log Z_{a}(W)=\log Z(W)$ (7)

From the properties of entropy function one could write

$1\leq K^{*}\leq K\leq 2^{N}$ (8)

where the lower bound on $K^{*}$ is attained at $H(p^{*})=0$ and is realized
when the Energy surface has only one local minimum, a very un-interesting
case. The upper bound on $K^{*}$ is attained at $p^{*}=\frac{1}{K}$, which
happens only when all valleys are considered similar. Since Number of states
can be at most $2^{N}$, the last upper bound holds and Thus
$\frac{1}{N}\log_{2}K$, can be viewed as a measure of Complexity, of the
energy surface. One could put a suitable prior distribution over the
parameters $W$ and evaluate the complexity averaged over the prior, motivating
the following definition.

######  Definition 4.

(Complexity) The _Complexity_ of the model described in Eqn (5) is given by

$\frac{1}{N}\mathds{E}_{W}\log_{2}K,\quad W\sim{\textbf{P}},$

where $K$ is the number of One-Flip stable states for Energy function defined
with parameter $W$ and P is a prior distribution over $W$.

For Ising models, _Complexity_ has been estimated in the large $N$ limit [4,
22] by methods such as _Replica technique_. However, extending their methods
to RBMs for a finite size $N$ is not straightforward.

It has been shown (see e.g. [16]) that IS decomposition gives a very accurate
picture of energy landscape of Ising models at Temperature, $T=0$. But, for
$T>0$, one needs to take into account both the Valley structure and the energy
landscape of the free energy [3]. Obtaining accurate estimates of Complexity
is an active area of study, for a recent review see [1].

Our goal is to apply the aforementioned IS decomposition to RBMs. We now show
the equivalence between these perfectly reconstructible vectors and one-flip
stable states for an RBM. The IS decomposition then allows us to define the
measure of capacity in terms of the modes of input distribution.

######  Lemma 1.

A vector v is perfectly reconstructible for an $\text{RBM}_{n,m}(\theta)$
$\iff$ the state $\\{\textbf{v},\operatorname{up}(\textbf{v})\\}$ is one-flip
stable.

###### Proof.

See Supplementary material. ∎

Thus we see that there is a one-one equivalence between perfectly
reconstructible vectors and the one-flip stable states for a single layer
$\text{RBM}_{n,m}(\theta)$.

Relationship between the modes of $p(\textbf{v})$ and
$p(\textbf{v},\textbf{h})$ In this section we discuss the relationship between
the modes of the marginal distribution, $p(\textbf{v})$ and the joint
distributuon $p(\textbf{v},\textbf{h})$. We make a mild assumption on one-flip
stable state.

  * A1

For a single layer RBM, given a visible vector v, vector
$\textbf{h}^{*}=\operatorname{up}(\textbf{v})$ is unique.

If the weights are given small random perturbation, then Assumption 1 holds
with probability one. However it does not hold true for an $L\geq 2$ layer
$\text{RBM}_{n,m_{1},...,m_{L}}(\theta)$. We denote
$\\{\textbf{h}_{l}\in\\{0,1\\}^{m_{l}}\\}_{l=1}^{L}$ to be hidden vectors,
$\textbf{v}\in\\{0,1\\}^{n}$ to be visible vector and define the set

$\mathcal{H}(\textbf{v})\triangleq\\{\\{\textbf{h}_{l}\\}_{l=1}^{L}|(\textbf{v},\\{\textbf{h}_{l}\\}_{l=1}^{L})\mbox{
is one-flip stable state}\\}$

It can be seen that $|\mathcal{H}(\textbf{v})|$ can be more than one. For
input distributions considered in Section 3, the modes of joint distribution
$p(\textbf{v},\textbf{h}_{1},\ldots,\textbf{h}_{L})$ with distinct v are
atleast as many as modes of marginal distribution p(v). A formal statement
with proof is given in supplementary material.

As discussed, for $L\geq 1$, the modes of the marginal distribution could be
smaller than modes of the joint distribution. However, [14] [Theorem 1.6] gave
precise conditions under which the number of modes for marginal and joint
distributions are same for a single layer network. We suspect that a similar
argument holds for $L>1$. For the rest of the paper we will assume that the
modes of joint distribution are same as those of $p(\textbf{v})$.

Armed with these observations we are now ready to define a measure which
relates the architecture of a DBM and the expected number of such modes under
a prior distribution on the model parameters. More formally,

######  Definition 5 (Inherent Structure Capacity).

For an $L$ layered DBM with $m_{1},\ldots,m_{L}$ hidden units and $n$ visible
units we define the _Inherent Structure Capacity_ (ISC), denoted by
$C(n,m_{1},\ldots,m_{L})$, to be the logarithm (divided by $n$) of the
expected number of modes of all possible distributions generated over the
visible units by the DBM.

$\mathcal{C}(n,m_{1},\ldots,m_{L})=\frac{1}{n}\log_{2}\mathds{E}_{\theta}\left[\left\lvert\\{\textbf{v}:|\mathcal{H}(\textbf{v})|\geq
1\\}\right\rvert\right]$

We note that for the single layer case this definition reduces to
$\frac{1}{n}\log_{2}\mathds{E}_{\theta}\left[\operatorname{prv}(n,m,\theta)\right]$.
ISC as a measure would be useful in identifying DBM architectures which can
model modes of an input distribution defined over the visible units.

This measure serves as a recipe for fitting DBMs. Suppose we know that the
input distribution has $k$ modes then one could find a suitable DBM
architecture, i.e. $m_{1},\ldots,m_{L}$ by the following criterion

$\frac{1}{n}\log_{2}k\leq\mathcal{C}(n,m_{1},\ldots,m_{L})$ (9)

Once the architecture has been identified one can then use a standard learning
algorithm to learn parameters to fit a given distribution.

In the following sections we investigate the computation of ISC and their
applications to single and two layer networks, i.e. $L=1$ and $L=2$. To keep
the exposition simple we assume the bias parameters to be zero 444Analysis can
be extended to non-zero biases in straightforward manner.. We also assume that
the coupling weights are distributed as per mean zero Gaussian, i.e., $\forall
i,j,w_{ij}\sim\mathcal{N}(0,\sigma^{2})$.

##  5 Computing capacity of $\text{RBM}_{n,m}$ and need for more layers

In this section we discuss the computation of ISC for a single layer RBM. In
absence of a definitive proof we conjecture that ISC is intractable just like
the Complexity measure in Spin glasses. The problem of computing Complexity
has been addressed in the Statistical Mechanics community using the Replica
method [17, 6] which yields reasonable estimates. However the applicability of
Replica trick to Multi-layer DBMs is not clear. In this section we develop an
alternative method for estimating ISC.

###  5.1 Computing ISC of $\text{RBM}_{n,m}$

For any arbitrary vector $\textbf{v}\in\\{0,1\\}^{n}$ we compute
$\mathds{E}\left[\mathds{1}_{[\textbf{v}\text{ is PR.}]}\right]$ where
$\mathds{1}$ is the indicator random variable and expectation is over the
model parameters $\theta$ with prior as stated in Section 4. We then sum this
over all $2^{n}$ vectors, i.e.,
$\sum_{\textbf{v}}\mathds{E}\left[\mathds{1}_{[\textbf{v}\text{ is
PR.}]}\right]$. Before stating our main theorem we state a few Lemmas.

######  Lemma 2.

For the set $\textbf{RBM}_{n,m}$, if a given vector v has $r(\geq 1)$ ones,
$\textbf{h}=\operatorname{up}(\textbf{v})$ has $l$ ones and $l\gg 1$,then
555Here $l\gg 1$ means $l$ is atleast 50 hidden units, which according to us
is a reasonable assumption. for $r>1$,

$\mathds{E}\left[\mathds{1}_{[\textbf{v}\text{ is
PR.}]}\right]\leq\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{l}{\pi
r-2}}\right)\right]^{r}\left(\frac{1}{2}\right)^{n-r}.$

For $r=1,$ the expression $\mathds{E}\left[\mathds{1}_{[\textbf{v}\text{ is
PR.}]}\right]$ equates to ${\left(\frac{1}{2}\right)}^{n-1}$. where
$\operatorname{erf}(x)=\frac{1}{\sqrt{\pi}}\int_{-x}^{x}e^{-t^{2}}dt$

###### Proof.

See Supplementary Material. ∎

For $r(>1)$ ones in v and $l$ ones in
$\textbf{h}=\operatorname{up}(\textbf{v})$ the problem of computing
$\left\\{P[[\operatorname{down}(\textbf{h})]_{i}=1]\right\\}_{i=1}^{r}$ can be
reformulated in terms of matrix row and column sums, viz, given
$W\in\mathds{R}^{r\times l}$ where all entries
$w_{ij}\sim\mathcal{N}(0,\sigma^{2})$ are i.i.d. and given that all the column
sums $\left\\{C_{j}=\sum_{i=1}^{r}w_{ij}>0\right\\}_{j=1}^{l}$, to compute the
probability that all the row sums are positive, i.e.,
$\left\\{R_{i}=\sum_{j=1}^{l}w_{ij}>0\right\\}_{i=1}^{r}$. Conditioned on the
fact $\left\\{C_{j}>0\right\\}_{j=1}^{l}$ the random variables
$\left\\{R_{i}\right\\}_{i=1}^{r}$ are negatively correlated. This gives us an
upper bound mentioned in Lemma 2. We now get a lower bound for the estimate.

######  Lemma 3.

For the set $\textbf{RBM}_{n,m}$, if v has $r(>1)$ ones,
$\textbf{h}=\operatorname{up}(\textbf{v})$ has $l$ ones, then
$\exists\mu_{c},\tilde{\mu}_{c},\sigma_{c},\tilde{\sigma}_{c}\in\mathds{R}_{+}$
such that conditioned on $\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0$, the moments of
posterior distribution of $w_{ij}$ is given by

$\displaystyle\mathds{E}\left[w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\right]$
$\displaystyle=$
$\displaystyle(\tilde{\mu}_{c}-\mu_{c})\frac{\sigma^{2}}{\sigma_{c}^{2}}$
$\displaystyle\text{Var}\left[w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\right]$
$\displaystyle=$
$\displaystyle\tilde{\sigma}_{c}^{2}\left(\frac{\sigma^{2}}{\sigma_{c}^{2}}\right)^{2}+\sigma^{2}\beta$

where $\beta=\left(1-\frac{\sigma^{2}}{\sigma_{c}^{2}}\right)$

###### Proof.

See Supplementary Material. ∎

Lemma 2 gives an upper bound $U(n,m)$ on expected number of _PR_ vectors while
Lemma 3 gives us a posterior distribution on $w_{ij}$ after taking into
account the conditional correlation between $\\{R_{i}\\}_{i=1}^{r}$. This
eventually results in a lower bound $L(n,m)$. Thus even though a closed-form
expression for ISC is difficult, we obtain bounds on it as the following
theorem states.

######  Theorem 1.

(ISC of $\text{RBM}_{n,m}$) There exist non-trivial functions
$L(n,m),U(n,m):\mathds{Z}\times\mathds{Z}\rightarrow\mathds{R}_{+}$ such that
ISC of the set $\textbf{\text{RBM}}_{n,m}$ obeys the following inequality.

$\frac{1}{n}\log_{2}(L(n,m))\leq{\mathcal{C}}(n,m)\leq\frac{1}{n}\log_{2}(U(n,m))$

###### Proof.

See Supplementary material. ∎

###  5.2 Need for more hidden layers

Theorem 1 establishes the lower and upper bounds for ISC. A direct corollary
of the theorem establishes that $C(n,m)$ approaches a limit as $m$ increases.

######  Corollary 1.

(Large $m$ limit) For the set $\textbf{\text{RBM}}_{n,m}$,
$\lim_{m\to\infty}{\mathcal{C}}(n,m)=\log_{2}1.5=0.585$ where $C(n,m)$ is
defined in Theorem 1.

###### Proof.

In the Supplementary material we show that
$\lim_{m\to\infty}\frac{1}{n}\log_{2}L(n,m)=\lim_{m\to\infty}\frac{1}{n}\log_{2}U(n,m)=\log_{2}1.5$.
Then claim follows from squeeze theorem666http://mathonline.wikidot.com/the-
squeeze-theorem-for-convergent-sequences. ∎

Empirically we observe that this saturation limit is achieved when $m>20n$
(see Figure 3). Here we discuss the implications of the results derived in the
previous subsection.

  1. 1.

We plotted the actual expected modes attained and the ISC estimates derived
from Theorem 1 for $n=15$ and varying number of hidden units (Figure 1). We
can see that even a small number of hidden units admits a large ISC and the
current known bound given in Equation 4 is not necessary. This shows that for
a large class of distributions we give a more practical estimate of number of
hidden units required than the current state of the art.

  2. 2.

The upper bound on the ISC estimated above seems surprising at first sight
since it seems to contradict the well established fact that RBMs are universal
approximators [7, 9]. However, one should note that the bound is in expected
sense which means that in the family $\textbf{\text{RBM}}_{n,(m\to\infty)}$
many RBMs shall have modes close to or less than $(1.5)^{n}$. For the class of
input distributions for which number of modes $k\gg(1.5)^{n}$ training an
$\text{RBM}_{n,m}(\theta)$ to represent these might be difficult. _The need
for multi-layering arises in such conditions_.

  3. 3.

Corollary 1 shows for a large enough $m$ the bounds become tight and the
expression is exact. We also show this through simulations in Section 7.

######  Remark.

When $n,m\to\infty$ we can approximate $U(n,m)$ by the following relatively
simple expression that we can use to conduct further analysis.

$\displaystyle\begin{split}U(n,m)&\approx\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{m}{\pi
n-4}}\right)\right]^{n}\end{split}$ (10)

##  6 ISC of two-layer RBM architecture

To study the effect of adding layers, we consider the family
$\textbf{\text{RBM}}_{n,m_{1},m_{2}}$. As stated in Section 4, adapting
analysis for single layer RBMs to multi-layer RBMs is not straightforward. In
this section we discuss the computation of ISC and study its application to
design RBMs.

###  6.1 Computing the capacity of 2 layer RBM

We observe that an $\textbf{\text{RBM}}_{n,m_{1},m_{2}}$ shares the same
bipartite structure as a single layer $\textbf{\text{RBM}}_{n+m_{2},m_{1}}$
(Figure 2). This enables us to extend our single layer result to two layers.
We introduce a threshold quantity $\gamma=0.05$. This value was obtained by
simulating the asymtotics of
$f(x)=1-0.5\operatorname{erf}(-\sqrt{\frac{x}{\pi}})$.

vvvh1h1h1h1h1h2h2h2vvvh2h2h2h1h1h1h1h1 Figure 2: Two Layer
$\text{RBM}_{n,m_{1},m_{2}}$ shares same bipartite graph structure as single
layer $\text{RBM}_{n+m_{2},m_{1}}$

######  Theorem 2.

(ISC of $\text{RBM}_{n,m_{1},m_{2}}$ ) For an
$\textbf{\text{RBM}}_{n,m_{1},m_{2}}$ ($n,m_{1}>0$ and $m_{2}\geq 0$), if we
denote $u=\max(m_{1},n+m_{2}),l=\min(m_{1},n+m_{2})$, then

${\mathcal{C}}(n,m_{1},m_{2})\leq\frac{1}{n}\log_{2}S$

whenever $S<\gamma
2^{n},\;S=\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{u}{\pi
l-4}}\right)\right]^{l}$

###### Proof.

See Supplementary material. ∎

Theorem 2 gives a general formula from which different regimes can be derived
by varying $m_{1},m_{2}$. We will use this theorem to understand the design of
multi-layer RBMs.

In the previous section we saw that in a single layer RBM, irrespective of
number of hidden units, ISC, achieves a limiting value of $0.585$. The theorem
will be useful to quantitatively show that ISC can indeed be improved if we
consider layering. For an $\textbf{\text{RBM}}_{n,m_{1},m_{2}}$ ($n,m_{1}>0$
and $m_{2}\geq 0$), we denote
$\alpha_{1}=\frac{m_{1}}{n},\alpha_{2}=\frac{m_{2}}{n}$. We say that a layer
with $m$ hidden units is _narrow_ if $m<\gamma$ and it is _wide_ if
$m>\frac{1}{\gamma}$.

Table 1: ISC Values for different $\alpha_{1}=\frac{m_{1}}{n},\alpha_{2}=\frac{m_{2}}{n}$. $\gamma=0.05$ (obtained by simulating the asymtotics of $f(x)=1-0.5\operatorname{erf}(-\sqrt{\frac{x}{\pi}})$). Regime |  ISC |  Implications
---|---|---
$\alpha_{1}>\frac{1}{\gamma},\alpha_{2}<\gamma$ |  $(1+\alpha_{2})\log_{2}(1.5)$ |  ISC determined only by $\alpha_{2}$. For a single layer RBM ($\alpha_{2}=0$), further increase in hidden units not effective, multi-layering recommended.
$\alpha_{1}(1+\alpha_{2})=c$, where $c\geq 1$ |  $\min[1,\sqrt{c}\log_{2}(1.29)]$ ($\alpha_{1}^{*}=\sqrt{c})$. |  Given a budget of $cn^{2}$ parameters, this is the maximum ISC achievable with optimal choice of $\alpha_{1}$.
$\alpha_{1}(1+\alpha_{2})=c$, where $c<1$ |  $c\log_{2}\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{1}{\pi c}}\right)\right]$ ($\alpha_{1}^{*}=c$). |  If total number of parameters $<n^{2}$, then multi-layering does not help.

######  Corollary 2.

(Layer 1 Wide, Layer 2 Narrow) For an $\textbf{\text{RBM}}_{n,m_{1},m_{2}}$
($n,m_{1}>0$ and $m_{2}\geq 0$), if
$\alpha_{1}=\frac{m_{1}}{n}>\frac{1}{\gamma}$ and
$\alpha_{2}=\frac{m_{2}}{n}<\gamma$ then

${\mathcal{C}}(n,m_{1},m_{2})\leq(1+\alpha_{2})\log_{2}(1.5)$

###### Proof.

See Supplementary material. ∎

The Corollary shows that for a RBM with a wide first layer and a narrow second
layer, the upper bound on ISC increases linearly with the number of units in
second layer.

###  6.2 $\text{RBM}_{n,m_{1},m_{2}}$ design under budget on parameters

We extend the result obtained in previous section to consider a real scenario
wherein we have a budget on the maximum number of parameters that we can use
and we have to design a two-layered DBM given this constraint. For a given
input distribution with $k$ modes, the DBM should have
$\mathcal{C}(n,m_{1},m_{2})>\frac{1}{n}\log_{2}k$.

######  Corollary 3.

(Fixed budget on parameters) For an $\textbf{\text{RBM}}_{n,m_{1},m_{2}}$
($n,m_{1}>0$ and $m_{2}\geq 0$), if there is a budget of $cn^{2}$ on the total
number of parameters, i.e, $\alpha_{1}(1+\alpha_{2})=c$ then the maximum
possible ISC,
$\max_{\alpha_{1},\alpha_{2}}{\mathcal{C}}(n,\alpha_{1},\alpha_{2})\leq\tilde{U}(n,\alpha_{1}^{*},\alpha_{2}^{*})$
where

$\tilde{U}(n,\alpha_{1}^{*},\alpha_{2}^{*})=\begin{cases}\min(1,\sqrt{c}\log_{2}(1.29))&\text{
if }c\geq 1\\\
c\log_{2}\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{1}{\pi
c}}\right)\right]&\text{ if }c<1\end{cases}$

###### Proof.

See Supplementary material. ∎

Corollary 3 can be used to determine the optimal allocation of hidden units to
the two layers if there is a budget on the number of parameters to be used due
to computational power or time constraints. It says that if $c\geq 1$, then
for optimality $\alpha_{1}=1+\alpha_{2}$ and if $c<1$, then $\alpha_{2}=0$
which means that all hidden units should be added to layer 1. The following
corollary highlights the existence of a two layer architecture
$\textbf{\text{RBM}}_{n,m_{1},m_{2}}$ that has ISC equal to $0.585$, the
saturation limit for single layer RBMs.

######  Corollary 4.

There exists a two layer architecture $\text{RBM}_{n,m_{1},m_{2}}$ with
$\Theta(n^{2})$ parameters such that

$\tilde{U}(n,\alpha_{1},\alpha_{2})=\log_{2}1.5$

where $m_{1}=\alpha_{1}n,m_{2}=\alpha_{2}n,\alpha_{1}=1.6$ and
$\alpha_{2}=0.6$

###### Proof.

In Corollary 3 if we put
$\tilde{U}(n,\alpha_{1}^{*},\alpha_{2}^{*})=\log_{2}(1.5)$, we get
$\alpha_{1}^{*}=\sqrt{c}=\frac{\log_{2}(1.5)}{\log_{2}(1.29)}=1.6,\alpha_{2}^{*}=\alpha_{1}^{*}-1=0.6$.
Number of parameters for such an RBM is
$\alpha_{1}(1+\alpha_{2})n^{2}=\Theta(n^{2})$. ∎

The number of parameters for any single layer RBM is $nm$ where $m$ is number
of hidden units. The above corollary gives an important insight: one can
construct a two layer RBM with $\Theta(n^{2})$ parameters that has the same
ISC as a single layer RBM with infinitely many hidden units. Ofcourse this is
true only if the upper-bound $\tilde{U}$ is close to ${\mathcal{C}}$. This
suggests that _lean_ 2 layer networks with _order of magnitude less number of
parameters can achieve the same ISC as that of a single layer RBM._

Table 1 summarises the ISC values for different regimes and their respective
implications for the two-hidden layered DBN. For example if
$\alpha_{1}>\frac{1}{\gamma}$ then the capacity is dictated only by the number
of hidden units in the second layer and increasing $\alpha_{1}$ has no effect.
Multi-layering should be considered to handle distributions with multiple
modes. Also, considering a practical scenario where there is a computational
and memory constraint that translates into a budget on the number of
parameters, i.e. $\alpha_{1}(1+\alpha_{2})=c$, we get the optimal distribution
of hidden units in the two layers that maximizes the capacity. In particular
if $c<1$ then it is recommended to allocate all hidden units to layer 1 itself
instead of adding more layers.

##  7 Experimental Results

Our main goals are to experimentally verify Theorems 1, 2 and Corollaries 3 4.
All experiments were run on CPU with 2 Xeon Quad-Core processors (2.60GHz 12MB
L2 Cache) and 16GB memory running Ubuntu 16.02 777The source code and
instructions to run is available at
http://mllab.csa.iisc.ernet.in/publications..

###  7.1 Validating estimate of Number of modes

To verify our theoretical claims of Theorems 1 and 2 a number of simulation
experiments for varied number of visible and hidden units were conducted. To
enable execution of exhaustive tests in reasonable time, the values of $n$ had
to be kept small. The entries $\\{w_{ij}\\}$ of the weight matrix were drawn
from an i.i.d. mean zero normal distribution. Each of the $2^{n}-1$ vectors
(leaving out the trivial all zero vector) was then tested for being _perfectly
reconstructible_. A comparison of the theoretical predictions and experimental
results is shown in Figures 3 and 5 for single layer and two layer RBMs
respectively. It can be seen that the theoretical predictions follow similar
trend as the experimental results.

Figure 3: Comparison chart of the upper and lower estimates with the actual simulation value of expected number of modes ($2^{n{\mathcal{C}}(n,m)}$) for $n=12$.  Table 2: Actual ISC for $\textbf{\text{RBM}}_{n,m}$ for $m=500$, obtained by averaging brute-force enumeration from 2000 independent instantiations of weight matrix, i.e., $\mathcal{C}(n,m)=\frac{1}{n}\log_{2}\left(\frac{1}{2000}\sum_{i=1}^{2000}k_{i}\right)$ where $k_{i}$ is the number of modes enumerated in $i$th instantiation. | $n=10$ | $n=11$ | $n=12$
---|---|---|---
$\mathcal{C}(n,m)$ | 0.585 | 0.585 | 0.588

Discussion. Figure 3 shows that the predicted bounds on the modes are close to
the actual modes enumerated. Table 2 validates the claim that for an
$\textbf{\text{RBM}}_{n,m}$ as $m\to\infty$, ${\textbf{ISC}}\to 0.585$
(Corollary 1). To enable bruteforce enumeration in reasonable time the values
for $n$ had to be kept small. Figure 5 in the supplementary section shows the
theoretical upper bound and actual simulated ISC values for a DBM with 2
hidden layers if we fix the total number of hidden units ($m_{1}+m_{2}=10$)
and vary the ratio $\beta=\frac{m_{2}}{m_{1}}$. It can be seen that both
theoretical prediction of ISC and actual simulation results are closely
aligned.

###  7.2 DBM design under budget on parameters

To validate the claim made in Corollary 3 we considered training a DBM with
two hidden layers on the MNIST dataset. For this dataset, the standard
architecture for a two hidden layer DBM uses $m_{1}=500,m_{2}=1000$ hidden
units (784x500x1000) [18, 19, 8]. In this case
$\alpha_{1}=0.64,\alpha_{2}=1.27$ and the number of parameters $=784\times
500+500\times 1000+(784+500+1000)=894284$. Under a budget of fixed number of
parameters Corollary 3 suggests a better split of the number of hidden units.
Accordingly we trained a DBM, with architecture of 784x945x161(_Recommended_),
with 894915 parameters. We note that the number of parameters are similar to
the standard architecture of 784x500x1000 (_Classical_), with 894284
parameters.

We used the standard metric average log-likelihood of test data [18, 19] as
the measure to compare. To estimate the model’s partition function we used
20,000 $\beta_{k}$ spaced uniformly from 0 to 1.0.

Discussion.  The classical _tuned_ architecture for training a DBM with 2
hidden layers for the original MNIST dataset gives a log-likelihood of
_-84.62_. Using our recommended architecture, we were able to get a matched
log-likelihood of _-84.29_ without significant tuning.

###  7.3 Wide single layer RBM vs _lean_ two-layered DBM

To verify our claim in Corollary 4 we chose single layer RBMs with $n=20$ and
$n=30$ and varying $\alpha=\frac{m}{n}\in\\{3,7,10,15\\}$. We initialized
weights and biases of each RBM architecture randomly and then performed gibbs
sampling for 5000 steps to generate a synthetic dataset of 60,000 points. The
same dataset was then used for training and evaluating corresponding
multilayer DBM architecture suggested by our formula. The resulting test-set
log likelihood are depicted in Figure 4.

Figure 4: Comparison of test set log-likelihood attained for single layer RBM
and two-layer DBM for $n=20$ and $n=30$. It can be seen that the DBM with much
less parameters gives atleast as good log-likelihood as RBM.

Discussion. We can see that optimal DBM architecture gives same or improved
log-likelihood despite the fact that it has less number of parameters than the
respective single layer RBM, thus justifying our claim.

##  8 Conclusion

We studied the IS formalism, first introduced to study Spin glasses, to
understand the energy landscape of one and two layer DBMs and proposed ISC, a
measure of representation power of RBMs. ISC makes practical suggestions such
as whenever number of hidden units $m>20n$, the ISC saturates and
multilayering should be considered. Also, ISC suggests alternative two layer
architectures to single layer RBMs which have equal or more representational
power with far fewer number of parameters.

## Acknowledgment

The authors would like to thank the referees for their insightful comments. CB
gratefully acknowledge partial support from a generous grant from Microsoft
Research India.

## References

  * [1] Antonio Auffinger, Gérard Ben Arous, and Jiří Černỳ.  Random matrices and complexity of spin glasses.  Communications on Pure and Applied Mathematics, 66(2):165–201, 2013\.
  * [2] Donald R Barr and E Todd Sherrill.  Mean and variance of truncated normal distributions.  The American Statistician, 53(4):357–361, 1999.
  * [3] Giulio Biroli and Rémi Monasson.  From inherent structures to pure states: Some simple remarks and examples.  EPL (Europhysics Letters), 50(2):155, 2000.
  * [4] AJ Bray and MA Moore.  Metastable states in spin glasses.  Journal of Physics C: Solid State Physics, 13(19):L469, 1980.
  * [5] María Angélica Cueto, Jason Morton, and Bernd Sturmfels.  Geometry of the restricted boltzmann machine.  Algebraic Methods in Statistics and Probability,(eds. M. Viana and H. Wynn), AMS, Contemporary Mathematics, 516:135–153, 2010.
  * [6] C De Dominicis, M Gabay, T Garel, and Henri Orland.  White and weighted averages over solutions of thouless anderson palmer equations for the sherrington kirkpatrick spin glass.  Journal de Physique, 41(9):923–930, 1980.
  * [7] Yoav Freund and David Haussler.  Unsupervised learning of distributions on binary vectors using two layer networks.  In Advances in neural information processing systems, pages 912–919, 1992.
  * [8] Geoffrey E Hinton and Ruslan R Salakhutdinov.  A better way to pretrain deep boltzmann machines.  In Advances in Neural Information Processing Systems, pages 2447–2455, 2012.
  * [9] Nicolas Le Roux and Yoshua Bengio.  Representational power of restricted boltzmann machines and deep belief networks.  Neural computation, 20(6):1631–1649, 2008.
  * [10] James Martens, Arkadev Chattopadhya, Toni Pitassi, and Richard Zemel.  On the representational efficiency of restricted boltzmann machines.  In Advances in Neural Information Processing Systems, pages 2877–2885, 2013.
  * [11] Guido Montúfar.  Deep narrow boltzmann machines are universal approximators.  arXiv preprint arXiv:1411.3784, 2014.
  * [12] Guido Montufar and Nihat Ay.  Refinements of universal approximation results for deep belief networks and restricted boltzmann machines.  Neural Computation, 23(5):1306–1319, 2011.
  * [13] Guido Montúfar and Johannes Rauh.  Hierarchical models as marginals of hierarchical models.  International Journal of Approximate Reasoning, 88:531–546, 2017\.
  * [14] Guido F Montúfar and Jason Morton.  When does a mixture of products contain a product of mixtures?  SIAM Journal on Discrete Mathematics, 29(1):321–347, 2015.
  * [15] Guido F Montúfar, Johannes Rauh, and Nihat Ay.  Expressive power and approximation errors of restricted boltzmann machines.  In Advances in neural information processing systems, pages 415–423, 2011.
  * [16] Giorgio Parisi and Marc Potters.  Mean-field equations for spin models with orthogonal interaction matrices.  Journal of Physics A: Mathematical and General, 28(18):5267, 1995\.
  * [17] SA Roberts.  Metastable states and innocent replica theory in an ising spin glass.  Journal of Physics C: Solid State Physics, 14(21):3015, 1981.
  * [18] Ruslan Salakhutdinov and Geoffrey Hinton.  Deep boltzmann machines.  In Artificial Intelligence and Statistics, pages 448–455, 2009\.
  * [19] Ruslan Salakhutdinov and Hugo Larochelle.  Efficient learning of deep boltzmann machines.  In AISTATs, volume 9, pages 693–700, 2010.
  * [20] Daniel L Stein and Charles M Newman.  Spin glasses and complexity.  Princeton University Press, 2013.
  * [21] Frank H Stillinger and Thomas A Weber.  Hidden structure in liquids.  Physical Review A, 25(2):978, 1982.
  * [22] F Tanaka and SF Edwards.  Analytic theory of the ground state properties of a spin glass. i. ising spin glass.  Journal of Physics F: Metal Physics, 10(12):2769, 1980.
  * [23] Laurens van der Maaten.  Discriminative restricted boltzmann machines are universal approximators for discrete data.  Technical report, Technical Report EWI-PRB TR 2011001, Delft University of Technology, 2011.

## Supplementary material

In the following sections we provide additional material (proofs and figures)
that supplement our main results. Section A outlines the preliminary facts and
notations that we use for the proofs. The subsequent sections provide the
detailed proofs for respective lemmas and theorems. Figure 5 compares the
theoretical upper bound estimate with the actual simulated values for modes of
two layer DBMs (${\mathcal{C}}(n,m_{1},m_{2})$).

##  Appendix A Preliminary Facts and Notations

In the proofs that follow we use the following facts and notations:

  1. 1.

The probability density function (pdf) of standard normal distribution
$\mathcal{N}(0,1)$

$\phi(x)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{x^{2}}{2}\right)$

  2. 2.

The cumulative distribution function (cdf) of standard normal distribution

$\Phi(x)=\int_{-\infty}^{x}\phi(x)dx=\frac{1}{2}\left[1+\operatorname{erf}\left(\frac{x}{\sqrt{2}}\right)\right]\text{
where }\operatorname{erf}(x)=\frac{1}{\sqrt{\pi}}\int_{-x}^{x}e^{-t^{2}}dt$

  3. 3.

The pdf of a skew normal distribution $\hat{\mathcal{N}}$ with skew parameter
$\alpha$

$f(x)=2\phi(x)\Phi(\alpha x)$

  4. 4.

If $X\sim\mathcal{N}(\mu,\sigma^{2})$,
$a\in\mathds{R},\alpha=\frac{a-\mu}{\sigma}$, then $X$ conditioned on $X>a$
follows a truncated normal distribution with moments

$\displaystyle\mathds{E}\left[X|X>a\right]$ $\displaystyle=$
$\displaystyle\mu+\sigma\frac{\phi(\alpha)}{Z}$ $\displaystyle Var(X|X>a)$
$\displaystyle=$
$\displaystyle\sigma^{2}\left[1+\alpha\frac{\phi(\alpha)}{Z}-\left(\frac{\phi(\alpha)}{Z}\right)^{2}\right]$

where $Z=1-\Phi(\alpha)$.

  5. 5.

_Squeeze Theorem_ 888http://mathonline.wikidot.com/the-squeeze-theorem-for-
convergent-sequences: Let, $\\{a_{m}\\},\\{b_{m}\\},\\{c_{m}\\}$ be sequences
such that $\forall m\geq m_{0}$ ($m_{0}\in\mathds{R}$)

$a_{m}\leq b_{m}\leq c_{m}$

Further, let $\lim_{m\to\infty}a_{m}=\lim_{m\to\infty}c_{m}=L$, then

$\lim_{m\to\infty}b_{m}=L$

##  Appendix B Proof of Lemma 1 (See page 1)

See 1

###### Proof.

Let $\textbf{h}^{*}=\operatorname{up}(\textbf{v})$ (conditioning on $\theta$
is implicit). If v is perfectly reconstructible
$\implies\textbf{v}=\operatorname{arg\,max}_{\textbf{v}}P(\textbf{v}|\textbf{h}^{*})\implies\forall\textbf{v}^{\prime}\neq\textbf{v},P(\textbf{v}^{\prime},\textbf{h}^{*})<P(\textbf{v},\textbf{h}^{*})$.
Similarly since
$\textbf{h}^{*}=\operatorname{arg\,max}_{\textbf{h}}P(\textbf{h}|\textbf{v}),\forall\textbf{h}^{\prime}\neq\textbf{h}^{*},P(\textbf{v},\textbf{h}^{\prime})<P(\textbf{v},\textbf{h}^{*})$.
Hence the state $\\{\textbf{v},\textbf{h}^{*}\\}$ is stable against any number
of flips of visible units and against any number of flips of hidden units,
$\implies\\{\textbf{v},\textbf{h}^{*}\\}$ is atleast one-flip stable.
Conversely let $\\{\textbf{v}^{*},\textbf{h}^{*}\\}$ be one-flip stable. We
shall prove by contradiction that
$\operatorname{up}(\textbf{v}^{*})=\textbf{h}^{*}$ and
$\operatorname{down}(\textbf{h}^{*})=\textbf{v}^{*}$. Assume
$\operatorname{up}(\textbf{v}^{*})=\textbf{h}^{\prime}\neq\textbf{h}^{*}$. We
use the fact that for an RBM the hidden units are conditionally independent of
each other given the visible units. Thus
$\textbf{h}^{\prime}=\operatorname{arg\,max}_{\textbf{h}}P(\textbf{h}|\textbf{v}^{*})=\\{\operatorname{arg\,max}_{h_{j}}P(h_{j}|\textbf{v}^{*})\\}_{j=1}^{m}$.
Further
$P(\textbf{h}^{*}|\textbf{v}^{*})=\prod_{j=1}^{m}P(h_{j}^{*}|\textbf{v}^{*})$.
Let $k$ be an index such that $h_{k}^{\prime}\neq h_{k}^{*}$. Since
$h_{k}^{\prime}=\operatorname{arg\,max}_{h_{k}}P(h_{k}|\textbf{v}^{*}),\implies
P(h_{k}^{\prime}|\textbf{v}^{*})>P(h_{k}^{*}|\textbf{v}^{*})$. Moreover,
$P(\textbf{v}^{*},\textbf{h}^{*})=P(\textbf{v}^{*})P(\textbf{h}^{*}|\textbf{v}^{*})=P(\textbf{v}^{*})\prod_{j=1}^{m}P(h_{j}^{*}|\textbf{v}^{*})$.
Thus just by flipping $h_{k}^{*}$ to $h_{k}^{\prime}$ we can increase the
probability of the state $\\{\textbf{v}^{*},\textbf{h}^{*}\\}$. This
contradicts the one-flip stability hypothesis. Similarly using the conditional
independence of visible units given the hidden units we can show that
$\operatorname{down}(\textbf{h}^{*})=\textbf{v}^{*}$. ∎

##  Appendix C Proof of Lemma 2 (See page 2)

See 2

###### Proof.

We first note that given a visible vector $\textbf{v}\in\\{0,1\\}^{n}$ the
most likely configuration of the hidden vector

$\left\\{h_{j}=\left[\operatorname{up}(\textbf{v})\right]_{j}=\mathds{1}_{\left[\sum_{i=1}^{n}w_{ij}v_{i}>0\right]}\right\\}_{j=1}^{m}$

Likewise given a hidden vector h, the most likely visible vector

$\left\\{v_{i}=\left[\operatorname{down}(\textbf{h})\right]_{i}=\mathds{1}_{\left[\sum_{j=1}^{m}w_{ij}h_{j}>0\right]}\right\\}_{i=1}^{n}$

Case 1: $r=1$
By symmetry it can be assumed $v_{1}=1$, and $v_{i}=0(\forall i>1)$. Then
$\left\\{h_{j}=\mathds{1}_{\left[w_{1j}>0\right]}\right\\}_{j=1}^{m}$ . Since
each of $w_{1j}$ is i.i.d. as per $\mathcal{N}(0,\sigma^{2})$, $h_{j}$ is a
Bernoulli random variable with $P(h_{j}=1)=\frac{1}{2}$. Again by symmetry it
is assumed the first $l$ units $\\{h_{j}\\}_{j=1}^{l}$ are one. Then the most
likely _reconstructed_ visible vector is given by
$\left\\{\hat{v}_{i}=\mathds{1}_{\left[X_{i}=\sum_{j=1}^{l}w_{ij}>0\right]}\right\\}_{i=1}^{n}$.
Since $w_{1j}>0$ for all $1\leq j\leq l\implies\hat{v}_{1}=1$. Also, for all
$i>1,w_{ij}\sim\mathcal{N}(0,\sigma^{2})\implies
X_{i}\sim\mathcal{N}(0,l\sigma^{2})\implies\\{\hat{v}_{i}\\}_{i>1}$ is a
Bernoulli random variable with
$\left\\{P[\hat{v}_{i}=1]=\frac{1}{2}\right\\}_{i=2}^{n}$. The result then
follows by mutual independence of $\hat{v}_{i}$.

Case 2: $r>1$
For $r(>1)$ ones in v and $l$ ones in
$\textbf{h}=\operatorname{up}(\textbf{v})$ the problem of computing
$\left\\{P[\hat{v}_{i}=1]\right\\}_{i=1}^{r}$ can be reformulated in terms of
matrix row and column sums, viz, given $W\in\mathds{R}^{r\times l}$ where all
entries $w_{ij}\sim\mathcal{N}(0,\sigma^{2})$ are i.i.d. and given that all
the column sums $\left\\{C_{j}=\sum_{i=1}^{r}w_{ij}>0\right\\}_{j=1}^{l}$, to
compute the probability that all the row sums are positive, i.e.,
$\left\\{R_{i}=\sum_{j=1}^{l}w_{ij}>0\right\\}_{i=1}^{r}$.

Using properties of normal distribution it can be shown that conditioned on
the fact that $C_{j}>0$, the posterior distribution of $w_{ij}$ shall be
_skew-normal_ with mean $\mu_{ij}=\sigma\sqrt{\frac{2}{\pi r}}$ and variance
$\sigma_{ij}^{2}=\sigma^{2}\left(1-\frac{2}{\pi r}\right)$. Since the random
variables $\left\\{w_{ij}|C_{j}>0\right\\}_{j=1}^{l}$ are independent the
posterior mean of $R_{i}$ shall be $\tilde{\mu}_{i}=l\sigma\sqrt{\frac{2}{\pi
r}}$ and the posterior variance
$\tilde{\sigma}_{i}^{2}=l\sigma^{2}\left(1-\frac{2}{\pi r}\right)$. Since
$l\gg 1$ by Central Limit Theorem $R_{i}$ follow a normal distribution. Since
the $R_{i}$ are negatively correlated (proof follows) and
$\left\\{P[\hat{v}_{i}=1]=\frac{1}{2}\right\\}_{i>r}$ by similar reasoning as
in Case 1 we get our desired upper bound.

Negatively Correlated $R_{i}$’s: Conditioned on the fact
$\left\\{C_{j}>0\right\\}_{j=1}^{l}$ the random variables
$\left\\{R_{i}\right\\}_{i=1}^{r}$ are not independent. They are negatively
correlated because for all $R_{i},R_{t}(t\neq i)$,

$P(R_{i}>0|\left\\{C_{j}>0\right\\}_{j=1}^{l},R_{t}>0)<P(R_{i}>0|\left\\{C_{j}>0\right\\}_{j=1}^{l})$

Hence the expression given in Lemma 2 is an upper bound since we have
neglected the negative correlation among the $R_{i}$ and in the process over-
estimated the probabilities.

∎

##  Appendix D Proof of Lemma 3 (See page 3)

See 3

###### Proof.

The conditional distribution for $R_{1}=\sum_{j=1}^{l}w_{1j}$ is obtained from
the proof of Lemma 2.

$\left(R_{1}|\\{C_{j}>0\\}_{j=1}^{l}\right)\sim\mathcal{N}\left(\tilde{\mu}_{1},\tilde{\sigma}_{1}^{2}\right)$

where $\tilde{\mu}_{1}=l\sigma\sqrt{\frac{2}{\pi r}}$,
$\tilde{\sigma}_{1}^{2}=l\sigma^{2}\left(1-\frac{2}{\pi r}\right)$. Using
similar arguments as in proof of Lemma 2, conditioned on $R_{t}>0$ the
posterior distribution of $w_{tj}$ shall be skew normal
$\hat{\mathcal{N}}\left[\sigma\sqrt{\frac{2}{\pi
l}},\sigma^{2}\left(1-\frac{2}{\pi l}\right)\right]$. Then conditioned on
$\\{R_{t}>0\\}_{t=1}^{i-1}$, $C_{j}$ shall be distributed as per skew normal

$\left(C_{j}|\\{R_{t}>0\\}_{t=1}^{i-1}\right)\sim\hat{\mathcal{N}}(\mu_{c},\sigma_{c}^{2})$

where

$\mu_{c}=(i-1)\sigma\sqrt{\frac{2}{\pi l}}\text{ and
}\sigma_{c}^{2}=(i-1)\sigma^{2}\left(1-\frac{2}{\pi
l}\right)+(r-i+1)\sigma^{2}$

Here we approximate the above distribution to be Normal since if $i$ is large
then _Central Limit Theorem_ would be applicable, otherwise the normally
distributed variables $\\{w_{kj}\\}_{k=i}^{r}$ would dominate the sum. Then
conditioned on $\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0$, $C_{j}$ shall be
distributed as per truncated normal distribution [2] with moments

$\displaystyle\mathds{E}\left[C_{j}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\right]$
$\displaystyle=\tilde{\mu}_{c}=$
$\displaystyle\mu_{c}+\sigma_{c}\frac{\phi}{Z}$
$\displaystyle\text{Var}\left[C_{j}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\right]$
$\displaystyle=\tilde{\sigma}_{c}^{2}=$
$\displaystyle\sigma_{c}^{2}\left[1-\frac{\mu_{c}\phi}{\sigma_{c}Z}-\frac{\phi^{2}}{Z^{2}}\right]$

where $\sigma_{c}^{2}=(i-1)\sigma^{2}\left(1-\frac{2}{\pi
l}\right)+(r-i+1)\sigma^{2},\\\ \mu_{c}=(i-1)\sigma\sqrt{\frac{2}{\pi
l}},Z=\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\frac{\mu_{c}}{\sigma_{c}\sqrt{2}}\right)$
and
$\phi=\frac{1}{\sqrt{2\pi}}e^{\left(-\frac{\mu_{c}^{2}}{2\sigma_{c}^{2}}\right)}$.
Then
$\mathds{E}\left[w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}=c\right]=(c-\mu_{c})\frac{\sigma^{2}}{\sigma_{c}^{2}}$
and
$\text{Var}\left[w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}=c\right]=\sigma^{2}\left(1-\frac{\sigma^{2}}{\sigma_{c}^{2}}\right)$.
The result then follows from Laws of total expectation and total variance
respectively. ∎

######  Remark.

The random variables
$\\{\tilde{w}_{ij}=w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\\}_{j=1}^{l}$
shall be negatively correlated with one another so we should subtract the
covariance terms while determining the effective variance of
$R_{i}=\sum_{j=1}^{l}\tilde{w}_{ij}$. Thus if we don’t subtract the covariance
terms from the variance we would get a lower bound on the posterior
probability of $R_{i}$ being positive. However it is close as can be seen in
Figure 3.

##  Appendix E Proof of Theorem 1 (See page 1)

See 1

###### Proof.

The upper bound follows from Lemma 2 and applying linearity of expectation.

$U_{n,m}=\sum_{r=1}^{n}\binom{n}{r}\sum_{l=1}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{l}{\pi
r-2}}\right)\right]^{r}\left(\frac{1}{2}\right)^{n-r}$

For lower bound, we use Lemma 3. We have
$\mathds{E}\left[w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\right]=\tilde{\mu}_{i}(r,l)$
and
$\text{Var}\left[w_{ij}|\\{R_{t}>0\\}_{t=1}^{i-1},C_{j}>0\right]=(\tilde{\sigma}_{i}(r,l))^{2}$.
Thus posterior mean and variance of $\\{R_{i}\\}_{i=1}^{r}$ shall be
$l\tilde{\mu}_{i}(r,l)$ and $l(\tilde{\sigma}_{i}(r,l))^{2}$ respectively.
Then summing over all possibilities of $l$ and applying linearity of
expectation we get the lower bound.

$L_{n,m}=\sum_{r=1}^{n}\binom{n}{r}\sum_{l=1}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left\\{\prod_{i=1}^{r}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\frac{\tilde{\mu}_{i}(r,l)\sqrt{\frac{l}{2}}}{\tilde{\sigma}_{i}(r,l)}\right)\right]\right\\}\left(\frac{1}{2}\right)^{n-r}$

∎

##  Appendix F Proof of Corollory 1 (See page 1)

See 1

###### Proof.

We shall show that $\lim_{m\to\infty}U_{n,m}\leq 1.5^{n}$ and
$\lim_{m\to\infty}L_{n,m}\geq 1.5^{n}$. Then using _Squeeze Theorem_ and the
fact that limits preserve inequalities the result shall hold.

$\lim_{m\to\infty}U_{n,m}=\lim_{m\to\infty}\left\\{\sum_{r=1}^{n}\binom{n}{r}\sum_{l=1}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{l}{\pi
r-2}}\right)\right]^{r}\left(\frac{1}{2}\right)^{n-r}\right\\}$

If we replace the $l$ inside the $\operatorname{erf}$ function by $m$ then we
would be increasing the value of the expression since $m\geq l$. Thus

$\displaystyle\lim_{m\to\infty}U_{n,m}$ $\displaystyle\leq$
$\displaystyle\lim_{m\to\infty}\left\\{\sum_{r=1}^{n}\binom{n}{r}\sum_{l=1}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left(\frac{1}{2}\right)^{r}\left[1-\operatorname{erf}\left(-\sqrt{\frac{m}{\pi
r-2}}\right)\right]^{r}\left(\frac{1}{2}\right)^{n-r}\right\\}$
$\displaystyle=$
$\displaystyle\lim_{m\to\infty}\sum_{r=1}^{n}\binom{n}{r}\sum_{l=1}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left(\frac{1}{2}\right)^{r}\left[2\right]^{r}\left(\frac{1}{2}\right)^{n-r}$
$\displaystyle=$ $\displaystyle 1.5^{n}$

To get a lower bound on $L_{n,m}$ we choose a small fixed constant
$\epsilon>0$. Then

$\displaystyle\lim_{m\to\infty}L_{n,m}$ $\displaystyle=$
$\displaystyle\lim_{m\to\infty}\sum_{r=1}^{n}\binom{n}{r}\sum_{l=1}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left\\{\prod_{i=1}^{r}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\frac{\tilde{\mu}_{i}(r,l)\sqrt{\frac{l}{2}}}{\tilde{\sigma}_{i}(r,l)}\right)\right]\right\\}\left(\frac{1}{2}\right)^{n-r}$
$\displaystyle\geq$
$\displaystyle\lim_{m\to\infty}\sum_{r=1}^{n}\binom{n}{r}\sum_{l=m\epsilon}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left\\{\prod_{i=1}^{r}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\frac{\tilde{\mu}_{i}(r,l)\sqrt{\frac{l}{2}}}{\tilde{\sigma}_{i}(r,l)}\right)\right]\right\\}\left(\frac{1}{2}\right)^{n-r}$
$\displaystyle\geq$
$\displaystyle\lim_{m\to\infty}\sum_{r=1}^{n}\binom{n}{r}\sum_{l=m\epsilon}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left\\{\prod_{i=1}^{r}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\left(-\frac{\tilde{\mu}_{i}(r,l)\sqrt{\frac{m\epsilon}{2}}}{\tilde{\sigma}_{i}(r,l)}\right)\right]\right\\}\left(\frac{1}{2}\right)^{n-r}$

Since $\tilde{\mu}_{i}(r,l)$ and $\tilde{\sigma}_{i}(r,l)$ are non-zero finite
quantities regardless of the value of $l$ amd $m$ and $\epsilon$ is a fixed
non-zero constant,

$\displaystyle\lim_{m\to\infty}L_{n,m}$ $\displaystyle\geq$
$\displaystyle\lim_{m\to\infty}\sum_{r=1}^{n}\binom{n}{r}\sum_{l=m\epsilon}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}\left\\{\prod_{i=1}^{r}\left[\frac{1}{2}-\frac{1}{2}\operatorname{erf}\underbrace{\left(-\frac{\tilde{\mu}_{i}(r,l)\sqrt{\frac{m\epsilon}{2}}}{\tilde{\sigma}_{i}(r,l)}\right)}_{\to-\infty}\right]\right\\}\left(\frac{1}{2}\right)^{n-r}$
$\displaystyle=$
$\displaystyle\lim_{m\to\infty}\sum_{r=1}^{n}\binom{n}{r}\underbrace{\sum_{l=m\epsilon}^{m}\binom{m}{l}\left(\frac{1}{2}\right)^{m}}_{\text{Prob}(l>m\epsilon)}\left\\{\left(\frac{1}{2}\right)^{r}\left[2\right]^{r}\right\\}\left(\frac{1}{2}\right)^{n-r}$

Since $\epsilon$ is an arbitrarily small number that we have chosen and $l$
denotes the number of successes in $m$ Bernoulli trials,
Prob$(l>m\epsilon)=1$.

$\implies\lim_{m\to\infty}L_{n,m}\geq 1.5^{n}$ $\implies
1.5^{n}\leq\lim_{m\to\infty}L_{n,m}\leq\lim_{m\to\infty}\mathcal{C}(n,m)\leq\lim_{m\to\infty}U_{n,m}\leq
1.5^{n}$

∎

##  Appendix G Proof of Theorem 2 (See page 2)

See 2

###### Proof.

As shown in Figure 2 we construct a single layer $\text{RBM}_{n+m_{2},m_{1}}$
that has the same bipartite connections as
$\textbf{\text{RBM}}_{n,m_{1},m_{2}}$. The expected number of perfectly
reconstructible vectors for the single layer RBM can then be obtained from
Equation 10.

$\displaystyle{\mathcal{C}}(n+m_{2},m_{1})$ $\displaystyle\leq$
$\displaystyle\frac{1}{n}\log_{2}U_{n+m_{2},m_{1}}=\frac{1}{n}\log_{2}S$
$\displaystyle=$
$\displaystyle\frac{1}{n}\log_{2}\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{u}{\pi
l-4}}\right)\right]^{l}$

However this quantity is an overestimate. This counts the number of pairs of
vectors $\\{\textbf{v},\textbf{h}_{2}\\}$ such that
$\begin{pmatrix}\textbf{v}\\\ \textbf{h}_{2}\end{pmatrix}$ is perfectly
reconstructible for $\text{RBM}_{n+m_{2},m_{1}}$. Among these, there can be
vectors like $\begin{pmatrix}\textbf{v}^{(1)}\\\
\textbf{h}_{2}^{(1)}\end{pmatrix}$ and $\begin{pmatrix}\textbf{v}^{(2)}\\\
\textbf{h}_{2}^{(2)}\end{pmatrix}$ where $\textbf{v}^{(1)}=\textbf{v}^{(2)}$
resulting in repetitions. Assuming such vectors $\textbf{v}^{(i)}$ are
uniformly distributed among the $2^{n}$ possibilities, we approximate the
problem to the following. Given $2^{n}$ distinct vectors, we make $S$ draws
from them uniformly randomly with replacement. The expected number of distinct
vectors that result is given by
$2^{n}\left[1-\left(1-\frac{1}{2^{n}}\right)^{S}\right]$. If $S<\gamma 2^{n}$
then binomial approximation an be applied and we get the desired result. ∎

##  Appendix H Proof of Corollary 2 (See page 2)

See 2

###### Proof.

For $\alpha_{1}>\frac{1}{\gamma}$,
$S=\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{n\alpha_{1}}{\pi
n(1+\alpha_{2})-4}}\right)\right]^{n(1+\alpha_{2})}=1.5^{n(1+\alpha_{2})}$.

Moreover for $\alpha_{2}<\gamma$, since
$S=1.5^{n(1+\alpha_{2})}<1.5^{n(1+\gamma)}=2^{n(1+\gamma)\log_{2}(1.5)}=2^{0.614n}$($<\gamma
2^{n}$ for reasonable choices of $n$), we can apply binomial approximation and
the result follows. ∎

##  Appendix I Proof of Corollary 3 (See page 3)

See 3

###### Proof.

We consider two regimes.

Regime 1 ($\alpha_{1}\leq 1+\alpha_{2}$)

In this regime using Theorem 2,
$\mathcal{C}(n,m_{1},m_{2})\leq\frac{1}{n}\log_{2}S$ where

$S=\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{u}{\pi
l-\underbrace{4}_{=\mathchoice{{\scriptstyle\mathcal{O}}}{{\scriptstyle\mathcal{O}}}{{\scriptscriptstyle\mathcal{O}}}{\scalebox{0.7}{$\scriptscriptstyle\mathcal{O}$}}(1)}}}\right)\right]^{l}=\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{\frac{nc}{\alpha_{1}}}{\pi
n\alpha_{1}}}\right)\right]^{n\alpha_{1}}=\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)\right]^{n\alpha_{1}}$

We will prove that $\frac{\partial S}{\partial\alpha_{1}}>0$. Taking natural
logarithm on both sides,

$\ln
S=n\alpha_{1}\ln\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)\right]$
$\displaystyle\frac{1}{S}\frac{\partial S}{\partial\alpha_{1}}$
$\displaystyle=$ $\displaystyle
n\ln\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)\right]+\frac{n\alpha_{1}}{1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)}\left[-\frac{1}{\sqrt{(\pi)}}\exp\left(-\frac{c}{\pi\alpha_{1}^{2}}\right)\right]\left(\frac{1}{\alpha_{1}^{2}}\sqrt{\frac{c}{\pi}}\right)$
$\displaystyle=$ $\displaystyle
n\ln\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)\right]-\frac{n\alpha_{1}}{1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)}\left[\frac{1}{\sqrt{(\pi)}}\exp\left(-\frac{c}{\pi\alpha_{1}^{2}}\right)\right]\left(\frac{1}{\alpha_{1}^{2}}\sqrt{\frac{c}{\pi}}\right)$

Now since $c=\alpha_{1}(1+\alpha_{2})$ and we are in the regime
$\alpha_{1}\leq 1+\alpha_{2},\implies\frac{c}{\alpha_{1}^{2}}\geq 1$. Hence

$\displaystyle\frac{1}{S}\frac{\partial S}{\partial\alpha_{1}}$
$\displaystyle\geq$ $\displaystyle
n\ln\left[1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{1}{\pi}}\right)\right]-\frac{\frac{n}{\sqrt{\pi}}}{1-\frac{1}{2}\operatorname{erf}\left(-\sqrt{\frac{1}{\pi}}\right)}\underbrace{\left[\left(\sqrt{\frac{c}{\pi\alpha_{1}^{2}}}\right)\exp\left(-\frac{c}{\pi\alpha_{1}^{2}}\right)\right]}_{x\exp(-x^{2})\leq
0.428}$ $\displaystyle=$ $\displaystyle 0.252n-0.187n$
$\displaystyle\implies\frac{\partial S}{\partial\alpha_{1}}$ $\displaystyle>$
$\displaystyle 0$

Similarly we can show that in the Regime $\alpha_{1}>1+\alpha_{2}$,
$\frac{\partial S}{\partial\alpha_{2}}>0$ which would imply $\frac{\partial
S}{\partial\alpha_{1}}<0$.

Hence the maximum occurs when either $\alpha_{1}=1+\alpha_{2}=\sqrt{c}$
($c\geq 1$) or $\alpha_{1}=c$ ($c<1$). ∎

##  Appendix J Relationship between modes of joint and marginal distribution

Proposition
Let $\\{\textbf{v}_{r}\\}_{r=1}^{k}$ be visible vectors such that for each
pair of vectors $\\{\textbf{v}_{i},\textbf{v}_{j}\\}$ in
$\\{\textbf{v}_{r}\\}_{r=1}^{k}$, $d_{H}(\textbf{v}_{i},\textbf{v}_{j})\geq
2$. For an $\text{RBM}_{n,m_{1},...,m_{L}}(\theta)$ that fits the input
distribution
$p(\textbf{v})=\frac{1}{k}\sum_{i=1}^{k}\delta(\textbf{v}-\textbf{v}_{i})$, if
a vector v is a mode of marginal distribution, then there exist vectors
$\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L}$ such that
$(\textbf{v},\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L})$ is a mode of joint
distribution $p(\textbf{v},\\{\textbf{h}_{l}\\}_{l=1}^{L})$.

###### Proof.

Since $v$ is a mode, $\implies p(\textbf{v})=\frac{1}{k}>0$.
Further, let
$\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L}=\operatorname{arg\,max}_{\\{\textbf{h}_{l}\\}}P(\textbf{v},\\{\textbf{h}_{l}\\}_{l=1}^{L})$,
that is, the state $(\textbf{v},\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L})$ is stable
against flip of any hidden unit999Here we assume that energy function values
of any two distinct configurations are different..
Moreover, since for all neighbours $\textbf{v}^{\prime}$ of v,
$p(\textbf{v}^{\prime})=0\implies
p(\textbf{v}^{\prime},\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L})=0$, it implies that
$(\textbf{v},\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L})$ is stable against flip of
any visible unit also.

Thus $(\textbf{v},\\{\textbf{h}^{*}_{l}\\}_{l=1}^{L})$ is one-flip stable and
hence a mode of the joint distribution. ∎

(a) $2^{n{\mathcal{C}}(n,m_{1},m_{2})}$ for $n=3$ (b)
$2^{n{\mathcal{C}}(n,m_{1},m_{2})}$ for $n=5$ (c)
$2^{n{\mathcal{C}}(n,m_{1},m_{2})}$ for $n=10$

Figure 5: Comparison chart of the upper estimates with the actual simulation
value for two layered RBM with $m_{1}+m_{2}=10$. The values are plotted for
various values of $\beta=\frac{m_{2}}{m_{1}}$.