PHYSICAL REVIEW E 94, 062310 (2016)

Unsupervised feature learning from finite data by message passing:
Discontinuous versus continuous phase transition
Haiping Huang* and Taro Toyoizumi†
RIKEN Brain Science Institute, Wako-shi, Saitama 351-0198, Japan(Received 25 August 2016; revised manuscript received 1 December 2016; published 21 December 2016)
Unsupervised neural network learning extracts hidden features from unlabeled training data. This is used
as a pretraining step for further supervised learning in deep networks. Hence, understanding unsupervised
learning is of fundamental importance. Here, we study the unsupervised learning from a finite number of data,
based on the restricted Boltzmann machine where only one hidden neuron is considered. Our study inspires anefficient message-passing algorithm to infer the hidden feature and estimate the entropy of candidate featuresconsistent with the data. Our analysis reveals that the learning requires only a few data if the feature is salient andextensively many if the feature is weak. Moreover, the entropy of candidate features monotonically decreases withdata size and becomes negative (i.e., entropy crisis) before the message passing becomes unstable, suggesting a
discontinuous phase transition. In terms of convergence time of the message-passing algorithm, the unsupervised
learning exhibits an easy-hard-easy phenomenon as the training data size increases. All these properties are
reproduced in an approximate Hopfield model, with an exception that the entropy crisis is absent, and only
continuous phase transition is observed. This key difference is also confirmed in a handwritten digits dataset.
This study deepens our understanding of unsupervised learning from a finite number of data and may provide
insights into its role in training deep networks.
DOI: 10.1103/PhysRevE.94.062310
I. INTRODUCTION

Humans and other animals can learn new concepts fromonly a handful of training data but standard machine-learningalgorithms require huge data to uncover hidden features[1]. Learning hidden features in unlabeled data is called
unsupervised learning. How many data are required to learna feature? What key factors determine the success of unsupervised learning? These fundamental questions are largely
unsolved so far, and rarely explained by a physics model.
Understanding how data size confines learning process is a
topic of interest not only in machine learning [2] but also in
cognitive neuroscience [3]. The underlying neural mechanism
or inspired algorithms are still elusive, but recent progress inmean-field theory of restricted Boltzmann machine [4] allows
us to develop a statistical mechanics model to understand how
learning improves with data size.
Restricted Boltzmann machine (RBM) is a basic block
widely used in building a deep belief network [5,6]. It
consists of two layers of neurons. The visible layer receives
data, and based on this, the hidden layer builds an internal
representation. No lateral connections exist within each layer
for computational efficiency. The symmetric connections
between visible and hidden neurons represent hidden featuresin the data that the network learns. A common strategy to traina RBM is to apply a gradient-descent update algorithm of theconnections based on stochastically sampled neural activities[6]. However, no theory was proposed to address how learning
improves and how the number of candidate features decreases
with data size.
Here we tackle this problem by taking a different perspective. We propose a Bayesian inference framework to uncover

the connections, i.e., a feature vector, from data by explicitly
modeling its posterior distribution. Based on this framework,
we develop a message-passing algorithm for inferring an
optimal feature vector, while monitoring its entropy to quantify
how many candidate feature vectors are consistent with given
data.
II. MODEL DEFINITIONIn this study, we consider a RBM [4,7] with a single hidden
neuron, whose
activity is generated according to P (σ ,h) ∝√−βE(σ ,h)/ N, where σ = {σi |σi = ±1,i = 1, . . . ,N} repree
sents binary activity of N visible√ neurons, h = ±1 is theactivity of the hidden neuron, β/ N is the system-size andinverse-temperature dependent scaling factor, and E(σ ,h) =−hξ T σ is the energy function characterized by a feature
vector ξ (T indicates vector transpose). We assume that eachelement of the feature vector takes a binary value ξi = ±1.
While generalization to a case with multiple hidden neurons
is possible, we do not explore it here as the analysis becomes
more involved.
To perform unsupervised learning, we generate M independent samples as training data {σ a }M
a=1 from a RBM
with randomly generated true feature vector ξ true , where eachelement is drawn from ±1 with equal probability. Another
RBM learns this feature vector from the data. We formulate
the learning process as Bayesian inference. Given the training
data, the posterior distribution of the feature vector is


M
M

 
1 
β T a
a
,
P ξ |{σ a }M
∝
P
(σ
|ξ
)
=
cosh
σ
ξ
√
a=1
Z a=1
N
a=1
(1)

*

physhuang@gmail.com†
taro.toyoizumi@brain.riken.jp
2470-0045/2016/94(6)/062310(8)where Z is the partition function of the model and weassume a uniform prior about ξ . Here, the data {σ a }M
a=1
serves as the quenched disorder (data constraints), and the062310-1©2016 American Physical Society

HAIPING HUANG AND TARO TOYOIZUMIPHYSICAL REVIEW E 94, 062310 (2016)

inverse-temperature parameter β characterizes the learning
difficulty on a network of dimension N . If M > 1, themodel becomes nontrivial as the partition function cannot becomputed exactly for a large N . This M can be proportional
to the system size, and in this case we define a data density as
α = M/N. Hereafter, we omit the conditional dependence ofa M
P (ξ |{σ a }Ma=1 ) on {σ }a=1 .
III. MEAN-FIELD THEORYIn the following, we compute the maximizer of theposterior marginals (MPM) estimator ξ̂i = arg maxξi Pi (ξi )
true[8], which maximizes the overlap q = N1 N
i=1 ξi ξ̂i between
the true and estimated feature vectors. If q = 0, the data do
not give any information about the feature vector. If q = 1,
the feature vector is perfectly estimated. Hence, the task now
is to compute marginal probabilities, e.g., Pi (ξi ), which is stilla hard problem due to the interaction among data constraints.
However, by mapping the model [Eq. (1)] onto a factor graph[4,9], the marginal probability can be estimated by message
passing (Fig. 1) as we explain below. We first assume thatelements of the feature vector on the factor graph are weakly
correlated (also named Bethe approximation [10]), then byusing the cavity method [9], we define a cavity probability
Pi→a (ξi ) of ξi on a modified factor graph with data node aremoved. Under the weak correlation assumption, Pi→a (ξi )satisfies a recursive equation (namely belief propagation (BP)in computer science [11]):
Pi→a (ξi ) ∝μb→i (ξi ),(2a)b∈∂i\aμb→i (ξi ) = βcosh √ ξ T σ b
Pj →b (ξj ),N{ξj |j ∈∂b\i}
j ∈∂b\i(2b)where the proportionality symbol ∝ omits a normalization
constant, ∂i\a defines the neighbors of feature node i except

FIG. 1. Schematic illustration of factor graph representation andmessage passing. Left panel: circle nodes indicate features to beinferred. Square nodes indicate data constraints. A connection σia
indicates how the feature ξi is related to ath data. Right panel: thetop panel shows data node a collects messages from its neighboring
features other than node i and produces an output message to nodei. The bottom panel shows feature node i collects messages fromits neighboring data nodes other than b and produces an output
message to data node b. Iteration of these messages gives a coherent
understanding of the feature learning process.

data node a, ∂b\i defines the neighbors of data node b except
feature node i, and the auxiliary quantity μb→i (ξi ) represents
the contribution from data node b to feature node i given thevalue of ξi [9]. An equation similar to Eq. (2) was recently
derived to compute activity statistics of a RBM [4].
In the thermodynamic limit, the sum inside the hyperbolic cosine function excluding the i-dependent term in
Eq. (2b) is a random variable following a normal distribution with mean Gb→i and variance 2b→i [4], where
Gb→i = √1N j ∈∂b\i σjb mj →b and 2b→i  N1 j ∈∂b\i (1 −m2 ). The cavity magnetization is defined as mj →b =j →b
ξj ξj Pj →b (ξj ). Thus, the intractable sum over all ξj (j = i)
can be replaced by an integral over the normal distribution.
Furthermore, because ξi is a binary variable, Pi→a (ξi ) andμb→i (ξi ) are completely characterized [4] by the cavity magb→i (ξi =1)
netization mi→a and cavity bias ub→i = 12 ln μμb→i, re(ξi =−1)spectively. Using these expressions, the BP equation [Eq. (2)]could be reduced to the following practical recursive equations:⎞⎛
mi→a = tanh ⎝(3a)ub→i ⎠,b∈∂i\a√ ub→i = tanh−1 tanh(βGb→i ) tanh βσib / N ,(3b)where mi→a can be interpreted as the message passing fromfeature i to the data constraint a, while ub→i can be interpreted
as the message passing from data constraint b to feature i(Fig. 1). If the weak correlation assumption is self-consistent,
the BP would converge to a fixed point corresponding to astationary point of the Bethe free-energy function with respect
to the cavity messages {mi→a ,ua→i } [9].
By initializing the message on each link of the factor graph(Fig. 1), we run the BP equation [Eq. (3)] until it converges
within a prefixed precision. From this fixed point, one canextract useful information about the true feature vector byi ξicalculating 
the marginal probability as Pi (ξi ) = 1+m
where2
mi = tanh ( b∈∂i ub→i ). An alternative strategy to use passing
messages to infer the true feature vector is called reinforced
BP (rBP). This strategy is a kind of soft-decimation [12],which progressively
enhances or weakens the current local
field (hti = b∈∂i ub→i ) each feature component feels by thewith a probability 1 − γ t ,reinforcement rule hti ← hti + ht−1iuntil a solution ({ξ̂i = sgn(mi )}) is stable over iterations. γ
usually takes a value close to 1.
Another important quantity is the number of candidatefeature vectors consistent with the data, characterized by theentropy per neuron s = − N1 ξ P (ξ ) ln P (ξ ). Under the Bethe
approximation, s is evaluated as summing up contributions
from single feature nodes and data nodes (Appendix A).
IV. RESULTS

We use the above mean-field theory to study unsupervised
learning of the feature vector in single random realizationsof the true feature vector and analyze how its performance
depends on model parameters. We first explore effects of β
(N = 100). Note that β scales the energy and hence tunes thedifficulty of the learning. As shown in Fig. 2(a), it requires
an extensive number of data to learn a weak feature vector

062310-2

UNSUPERVISED FEATURE LEARNING FROM FINITE . . .

PHYSICAL REVIEW E 94, 062310 (2016)

FIG. 2. Bayesian learning in the RBM model [Eq. (1)]. Thirty random realizations of the model are considered. The error bars characterize
the standard deviation; N = 100. (a) Inference overlap q versus data density α with different values of feature saliency β. Results obtained byrBP (γ = 0.95) are also shown for comparison (β = 1). The inset shows the entropy per neuron. Arrows in the inset indicate thresholds forcontinuous transitions. (b) Median of convergence (learning) time defined by the number of iterations at which BP converges to a fixed point.
Two different values of β are considered. For β = 1, results for a larger N are also shown. The inset shows that the peak learning time scales
linearly with N (β = 1).

(β = 0.5). However, as β increases, the inference becomesmuch better. The overlap grows more rapidly at β = 1.0. When
α is above 10, one can get a nearly perfect inference of thefeature vector. We also use the reinforcement strategy to infer
the true feature vector, and it has nearly the same performancewith reduced computer time, because the estimation of the true
feature need not be carried out at the fixed point.
Remarkably, the overlap improves at some α, revealing that
the RBM could extract the hidden feature vector only aftersufficient data are shown. This critical α decreases with thesaliency β of the hidden feature. A statistical analysis of Eq. (3)reveals that αc = β14 (Appendix C). Next, we show the entropy
per neuron in the inset of Fig. 2(a). This quantity that describes
how many feature vectors are consistent with the data becomes
negative (i.e., entropy crisis [13,14]) at a zero-entropy αZE .
However, the BP equation is still stable (convergent), and thus
the instability occurs after the entropy crisis. This suggests theexistence of a discontinuous glass transition at a value of α lessthan or equal to αZE , as commonly observed in some spin glassmodels of combinatorial satisfaction problems [14–17]. As
shown in the inset of Fig. 2(a), αc can be either larger or smaller
than αZE , depending on β. If αc < αZE , a continuous transition
is followed by a discontinuous transition, where intrastateand interstate overlaps [18] bifurcate discontinuously. If
αc > αZE , the predicted continuous transition is inaccurate
at least under the replica symmetric assumption. Detailed
discussions about this novel property will be provided in aforthcoming extended work [19]. Interestingly, despite thelikely glass transition and entropy crisis, the fixed point of BP
still yields good inference of the feature vector, which may berelated to the Nishimori condition (Bayes-optimal inference)[19,20], since the temperature parameter used in inference isthe same as that used to generate the data.
Next, we study the median of learning time. The learning
time is measured as the number of iterations when the message
passing converges. Figure 2(b) shows that learning is fast at
small α, slow around the critical α, and becomes fast again atlarge α. This easy-hard-easy phenomenon can be understoodas follows. When a few data are presented, the inference is lessconstrained, and thus there exist many candidate feature vectors consistent with the data, the BP converges fast to estimate
the marginals. Once relatively many data are presented, thenumber of candidate feature vectors reduces [Fig. 2(a)], and the
BP requires more iterations to find a candidate feature vector.
We also observe that the peak learning time at αc scales linearlywith N within the measured range [the inset of Fig. 2(b)]. This
intermediate region is thus termed hard phase. Large β moves
the hard phase to the small α region. Once the number of data
is sufficiently large, the inference becomes easy once again
as the number of necessary iterations drops drastically. Thismay be because the feature space around the true feature vector
dominates the posterior probability in the presence of sufficient
data.
V. CONNECTION TO AN APPROXIMATE
HOPFIELD MODEL

It is interesting to show that one can also perform thesame unsupervised learning by using an associative memory(Hopfield) model defined byP̃ (ξ ) ∝β̃e 2N (ξ σ ) ,
T

a 2

(4)

a

where β̃ = β 2 . This posterior distribution about a feature
vector ξ given data {σ a }M
a=1 can be obtained by a small-β
expansion of Eq. (1) [21]. This relationship indicates that one
can infer the feature vector of a RBM using this Hopfieldmodel if β is small enough. In this case, the true feature vector
is also interpreted as a unique memory pattern in the Hopfieldmodel. By a small-β expansion, we interpret the unsupervised
learning in a RBM model as recovering stored pattern in a
Hopfield model from noisy data [22]. In the following, we
generate data by a RBM with true feature ξ true and compute

062310-3

HAIPING HUANG AND TARO TOYOIZUMIPHYSICAL REVIEW E 94, 062310 (2016)

FIG. 3. Bayesian learning in the approximate Hopfield model [Eq. (4)]. Thirty random realizations of the model are considered. The error
bars characterize the standard deviation; N = 100. (a) Entropy per neuron versus the data density α. (b) Overlap versus the data density. Resultsfor RBM (solid symbols) are shown for comparison.

the MPM estimator ξ̂ of the memory pattern in Eq. (4) basedon the given data.
Analogous to the derivation of Eq. (3), we can derive
the practical BP corresponding to the posterior probability[Eq. (4)]:
⎛

⎞

β̃
σib G̃b→i Fb→i ⎠,mi→a = tanh ⎝ √N b∈∂i\a(5)
where G̃b→i = √1N k∈∂b\i σkb mk→b , Fb→i = 1 + 1−β̃Cβ̃Cb→i inb→i
which Cb→i = N1 k∈∂b\i (1 − m2k→b ). The entropy of candidate feature vectors can also be evaluated from the fixed pointof this iterative equation (Appendix B).
Bayesian learning performance of the Hopfield model isshown in Fig. 3. This model does not show an entropy crisis in
the explored range of α. As α increases, the entropy decreases
much more slowly for weak features than for strong ones. For
β = 0.5, the overlap stays slightly above zero for a wide rangeof α. At a sufficiently large α (∼8), the overlap starts to increase
continuously. It is impossible to predict underlying structures if
the number of data is insufficient. This phenomenon is named
retarded learning first observed in unsupervised learning basedon Gaussian or mixture-of-Gaussian data [23,24]. At large
α where the entropy value approaches zero, the overlap
approaches one. All the properties except the entropy crisis
are qualitatively similar in both the approximate Hopfield andRBM model. The absence of entropy crisis may be related tothe absence of p-spin (p > 2) interanctions in the approximate
model, which has thus only the continuous glass transition at2αc = ( β̃1 − 1) , predicted by a statistical analysis of Eq. (5)(Appendix C). Note that the spin glass transition in a standard
Hopfield model where many random patterns are stored isof second order [25]. The current analysis sheds light onunderstanding the relationship between RBM and associative
memory networks [21,26] within an unsupervised learning
framework.

VI. APPLICATIONS OF OUR THEORYON MNIST DATASET

Finally, we test our theory on the MNIST handwritten digit
dataset [27]. For simplicity, we consider some combinationsof two different digits (e.g., 0 and 1, 3 and 7). Each digit
is represented by a 28 × 28 gray-scale image. Results showthat the real dataset shares common properties with our model(Fig. 4), which does not change qualitatively when different
combinations even the whole dataset are used. Importantly,
the presence and absence of the entropy crisis in a RBM anda Hopfield model, respectively, are also confirmed in this real
dataset.
Given the dataset [e.g., a set of digit 0 and 1 images (seeFig. 5)], our theory could estimate the corresponding hiddenfeature vector consistent with these images. The feature vector
is also called the receptive field of the hidden neuron, because
it determines the firing response of the hidden neuron. We
organize the inferred feature vector into a 28 × 28 matrix(the same size as the input image), and plot the matrix as
the gray-scale image (black indicates ξi = −1, and white
indicates ξi = 1). As shown in Fig. 6, the inferred feature

FIG. 4. Entropy per neuron versus α for MNIST dataset [handwritten digits (0, 1) and (3, 7)] at β = 1.

062310-4

UNSUPERVISED FEATURE LEARNING FROM FINITE . . .

PHYSICAL REVIEW E 94, 062310 (2016)

FIG. 5. Two examples of digits (0 and 1) from the MNIST dataset
are shown.

vector gets much better as the number of input images grows,
serving as a local structure detector. This is indicated by a
few active synaptic weights in the center of the image, where
local characteristics of handwritten digits are approximately
captured when sufficient data samples are shown to themachine. In a deep network composed of many layers ofstacked RBM, the low-level features (e.g., edges or contours)
detected by the hidden neuron could be passed to deeper layers,
where high-level information (e.g., object identity) could be
extracted [29].
The effect of the data size on the feature learning performance can be quantitatively measured by the precision-recall
curve. First, we computed the weighted sum (local field H )of the hidden neuron given the input image. These fields arethen ranked. Digits 1 and 0 are discriminated by introducing athreshold Hth for corresponding local fields. The true positive(TP) event is identified when digit 1 is predicted by a local
field above the threshold. The false-positive (FP) event is
identified when digit 0 is wrongly predicted by a local field
above the threshold. The false-negative event (FN) is identified
when digit 1 is wrongly predicted by a local field below theTPthreshold. The recall (RC) is defined as RC = PTPP+P
, and
FN
PTP
the precision (PR) is defined as PR = PTP +PFP , where PTP is
defined as the number of TP events in all presented samples.
Thus the precision-recall curve is the parametric curve of
PR(Hth ) and RC(Hth ). The closer we can get to (1,1) in theplot, the better the unsupervised feature learning understands
the embedded feature structure of the data. As shown in
Fig. 7, as the data size increases, the performance improves,

FIG. 6. Inferred features evolve with the number of input images (M) on the MNIST dataset. The top panel displays the result for the RBM
model, and the bottom panel displays the result for the approximate Hopfield model.
062310-5

HAIPING HUANG AND TARO TOYOIZUMIPHYSICAL REVIEW E 94, 062310 (2016)

FIG. 7. The precision-recall curve corresponding to Fig. 6. The unsupervised learning performance is also compared with the random guess(RG) case.

and it behaves much better than a random guess of synaptic
weights.
VII. CONCLUSION

In conclusion, we build a physics model of unsupervised
learning based on the RBM and propose a Bayesian inference
framework to extract a hidden feature vector from a finite
number of data. The mean-field theory inspires an efficientmessage passing procedure to infer the hidden feature. Unlike
previous approaches, each data in this work is treated asa constraint on the factor graph, and the message passing
carries out a probabilistic inference of the hidden feature
without sampling activities of neurons. We show that salientfeatures can be recovered by even a few data. Conversely, it is
impossible to recover the weak features by a finite amount ofdata. Interestingly, the entropy of candidate feature vectors becomes negative before the message passing algorithm becomes
unstable, suggesting a discontinuous glass transition to resolve
the entropy crisis, a typical statistical mechanics phenomenon
revealed in studies of spin glass models [14–17]. In terms of theconvergence time of the message passing algorithm, we reveal
the easy-hard-easy phenomenon for the current unsupervised
learning, which is explained by our theory. All these properties
except the entropy crisis are also observed in an approximate
Hopfield model, where we infer from data a hidden featureof a RBM. Remarkably, these phenomena are also confirmed
in a real dataset (Fig. 4). This work provides a theoreticalbasis to understand efficient neuromorphic implementationof RBM with simple binary feature elements [28]. We
also hope our study will provide important insights into aphysics understanding of unsupervised learning, especially its
important role in pretraining deep neural networks for superior
performances [6].
ACKNOWLEDGMENTS

H.H. thanks Pan Zhang for useful discussions. This work
was supported by the program for Brain Mapping by Integrated
Neurotechnologies for Disease Studies (Brain/MINDS) fromJapan Agency for Medical Research and development, AMED,and by RIKEN Brain Science Institute.

APPENDIX A: THE NUMBER OF CANDIDATE FEATURE VECTORS IN THE RBM MODEL

For the unsupervised learning in the RBM model, one important quantity is
the number of candidate feature vectors consistent
with the input noisy data, characterized by the entropy per neuron s = − N1 ξ P (ξ ) ln P (ξ ). Under the Bethe approximation[10], s is evaluated as summing up contributions from single feature nodes and data nodes:Ns =Si − (N − 1)
Sa ,
(A1)
a

i

√
a
where single feature nodeas Si = a∈∂i [β 2 2a→i
 contribution isexpressed  /2 + ln cosh(βGa→i + βσi / N )] +andsingledata
nodeln(1 + a∈∂i Ga→i ) − [ a∈∂i Ha→i (+1) + a∈∂i Ga→i a∈∂i Ha→i (−1)]/(1 + a∈∂i Ga→i ),

062310-6

UNSUPERVISED FEATURE LEARNING FROM FINITE . . .

PHYSICAL REVIEW E 94, 062310 (2016)

contribution
Sa = ln cosh(βGa ) −√β 2 2a /2 − βGa tanh(βGa ). We define Ga→i = e−2ua→i , Ha→i (ξi ) = β 2 2a→i + (βGa→i +√aβσi ξi / N ) tanh(βGa→i + βσia ξi / N ), Ga = √1N i∈∂a σia mi→a , and 2a = N1 i∈∂a (1 − m2i→a ).
APPENDIX B: THE NUMBER OF CANDIDATE FEATURE VECTORS IN THE APPROXIMATE HOPFIELD MODEL
For the approximate Hopfield model, the entropy can be evaluated as N s = i Si − (N − 1) a Sa , where single
β̃Ca→i+ β̃2 (1/N + G̃2a→i )Fa→i ] + ln (2 cosh(β̃Hi )) −feature node contribution reads Si = − a∈∂i [ 12 ln(1 − β̃Ca→i ) + 2(1−
β̃C
)
a→i

β̃Ca
(β̃Hi + β̃Hi ) tanh(β̃Hi ), and single data node contribution
Sa = − 12 ln(1 − β̃Ca ) − 2(1−− β̃2 G̃2a Fa , where G̃a =β̃Ca )



a→i
a
√1
σ am
, Fa→i = (1−β̃C, Fa = (1−β̃C, Ca = N1 k∈∂a (1 − m2k→a ), Hi = √1N b∈∂i σib G̃b→i Fb→i , and Hi =β̃Ca→i )2β̃Ca )2N k∈∂a k k→ab√1b∈∂i σi G̃b→i Fb→i .
N−z2 /2APPENDIX C: A STATISTICAL ANALYSIS
OF PRACTICAL BP EQUATIONS

where Dz = dze√2π . Note that Q = 0 is a stable solutionof Eq. (C1) only when α  αc = β14 . The threshold can beobtained by a Taylor expansion of Eq. (C1) around Q = 0.
Next, we perform a statistical analysis of the practical BP equation [Eq. (5) in the main text] for the approximate Hopfield model.
Similarly, a cavity field de
fined by hi→a = √1N b∈∂i\a σib G̃b→i Fb→i can be approximated by a random variable following a normal distribuαQ
tion with mean zero and variance (1−β̃(1−Q))
2 , where Q ≡
1 
2
m
.
Consequently,
weobtainthe
final
thermodynamici iNequation as

We first statistically analyze the practical BP equations[Eq. (3) in the main text] for the RBM. In a large N limit, theβσ bcavity bias can be approximated as ub→i  √Ni tanh βGb→i .
We then define a cavity field as hi→a = b∈∂i\a ub→i . The
sum in the cavity field involves an order of O(N ) terms,
which are assumed to be nearly independent under the replica
symmetric assumption. Therefore, the cavity field follows anormal distribution with mean zero and variance αβ 2 Q̂, whereQ̂ ≡ tanh2 βGb→i . Note that Gb→i is also a random variable
subject to a normal distribution
 with zero mean and variance
Q. Q is defined by Q = N1 i m2i . To derive the variance of
Gb→i , we used N1 k∈∂b\i m2k→b  Q, which is reasonable in
the large N limit (thermodynamics limit). Finally, we arrive at
the following thermodynamic recursive equation:


(C1a)
Q = Dz tanh2 β α Q̂z,Q̂ = Dz tanh2 β Qz,(C1b)

Obviously, Q = 0 is a solution of Eq. (C2), which is stable up
2
to αc = ( β̃1 − 1) . The threshold can be analogously derived
by a linear stability analysis.

[1] B. M. Lake, R. Salakhutdinov, and J. B. Tenenbaum, Science
350, 1332 (2015).
[2] G. E. Hinton, Trends Cogn. Sci. 11, 428 (2007).
[3] D. Kersten, P. Mamassian, and A. Yuille, Annu. Rev. Psychol.
55, 271 (2004).
[4] H. Huang and T. Toyoizumi, Phys. Rev. E 91, 050101 (2015).
[5] G. E. Hinton and R. R. Salakhutdinov, Science 313, 504(2006).
[6] Y. Bengio, A. Courville, and P. Vincent, IEEE Trans. PatternAnal. Machine Intell. 35, 1798 (2013).
[7] G. Hinton, S. Osindero, and Y. Teh, Neural Comput. 18, 1527
(2006).
[8] H. Nishimori, Statistical Physics of Spin Glasses and Information Processing: An Introduction (Oxford University Press,
Oxford, 2001).
[9] M. Mézard and A. Montanari, Information, Physics, andComputation (Oxford University Press, Oxford, 2009).
[10] M. Mézard and G. Parisi, Eur. Phys. J. B 20, 217 (2001).
[11] J. S. Yedidia, W. T. Freeman, and Y. Weiss, IEEE Trans. Inf.
Theory 51, 2282 (2005).

[12] A. Braunstein and R. Zecchina, Phys. Rev. Lett. 96, 030201(2006).
[13] B. Derrida, Phys. Rev. Lett. 45, 79 (1980).
[14] O. C. Martin, M. Mézard, and O. Rivoire, Phys. Rev. Lett. 93,
217205 (2004).
[15] A. Montanari, Eur. Phys. J. B 23, 121 (2001).
[16] H. Hai-Ping, Commun. Theor. Phys. 63, 115 (2015).
[17] H. Huang and Y. Kabashima, Phys. Rev. E 90, 052813(2014).
[18] E. Barkai, D. Hansel, and I. Kanter, Phys. Rev. Lett. 65, 2312
(1990).
[19] H. Huang, arXiv:1612.01717.
[20] Y. Iba, J. Phys. A: Math. Gen. 32, 3875 (1999).
[21] E. Agliari, A. Barra, A. Galluzzi, F. Guerra,and F. Moauro, Phys. Rev. Lett. 109, 268101(2012).
[22] S. Cocco, R. Monasson, and V. Sessak, Phys. Rev. E 83, 051123(2011).
[23] M. Biehl and A. Mietzner, J. Phys. A: Math. Gen. 27, 1885
(1994).


Q=

062310-7

Dz tanh

2



β̃
αQz .
1 − β̃(1 − Q)

(C2)

HAIPING HUANG AND TARO TOYOIZUMIPHYSICAL REVIEW E 94, 062310 (2016)[24] T. L. H. Watkin and J. P. Nadal, J. Phys. A: Math. Gen. 27, 1899(1994).
[25] D. J. Amit, H. Gutfreund, and H. Sompolinsky, Phys. Rev. Lett.
55, 1530 (1985).
[26] M. Mézard, arXiv:1608.01558.
[27] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, Proc. IEEE 86,
2278 (1998).

[28] M. Courbariaux, Y. Bengio, and J.-P. David, Advances in
Neural Information Processing Systems 28, edited by C.
Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and
R. Garnett (Curran Associates, Inc., Red Hook, NY, 2015),
pp. 3105–3113.
[29] James J. DiCarlo, D. Zoccolan, and N. C. Rust, Neuron 73, 415(2012).

062310-8