PHYSICAL REVIEW E 78, 021124 共2008兲

Statistical mechanics of lossy compression for nonmonotonic multilayer perceptrons
Florent Cousseau*
Graduate School of Frontier Sciences, University of Tokyo, Chiba 277-5861, Japan

Kazushi Mimura†
Faculty of Information Sciences, Hiroshima City University, Hiroshima 731-3194, Japan

Toshiaki Omori
Brain Science Institute, RIKEN, Saitama 351-0198, Japan

Masato Okada
Graduate School of Frontier Sciences, University of Tokyo, Chiba 277-5861, Japanand Brain Science Institute, RIKEN, Saitama 351-0198, Japan
共Received 20 March 2008; published 19 August 2008兲
A lossy data compression scheme for uniformly biased Boolean messages is investigated via statisticalmechanics techniques. We utilize a treelike committee machine 共committee tree兲 and a treelike parity machine
共parity tree兲 whose transfer functions are nonmonotonic. The scheme performance at the infinite code length
limit is analyzed using the replica method. Both committee and parity treelike networks are shown to saturate
the Shannon bound. The Almeida-Thouless stability of the replica symmetric solution is analyzed, and thetuning of the nonmonotonic transfer function is also discussed.
DOI: 10.1103/PhysRevE.78.021124

PACS number共s兲: 02.50.⫺r, 05.50.⫹q, 89.70.⫺aI. INTRODUCTION

The tools of statistical mechanics have been successfully
applied in several problems of information theory in recent
years. In particular, in the field of error correcting codes关1–4兴, spreading codes 关5,6兴, and compression codes 关7–11兴,
statistical mechanical techniques have shown great potential.
The present paper uses similar techniques to investigate alossy compression scheme. Lossless compression, which was
first pointed out in the pioneering paper of Shannon 关12兴, hasbeen widely studied for many years. After much effort, a setof very good codes have been designed and practical implementations have been proposed 关13–15兴. Lossy compression,on the other hand, was also first studied in another paper of
Shannon 关16兴. A lot of practical lossy compression schemes
have been developed over the years 共for example JPEG compression, MPEG compression, etc.兲 but at the present timenone of these schemes saturates the Shannon bound given by
the rate-distortion theorem. Nevertheless, several theoreticalschemes that reach this optimal bound have already been
proposed. Recently, Shannon optimal codes based on sparse
systems have been discovered 关7,17–19兴 and it is now thegeneral tendency to use such kinds of systems. These codes
saturate the Shannon bound asymptotically 共i.e., for an infinite codeword length兲, and in the dense generating matrix
limit 共but a low-connectivity sparse matrix already gives
near-Shannon performance兲. However, there is still a lot ofwork to be done for densely connected systems. One such
system is given by using a perceptron-based decoder. There
have been some recent studies on the encoding problem of*florent@mns.k.u-tokyo.ac.jp†

mimura@hiroshima-cu.ac.jp1539-3755/2008/78共2兲/021124共11兲

such schemes using the belief propagation 共BP兲 algorithm
and the results seems promising 关20兴. The foundations of thisencoding method for such lossy compression schemes wereoriginally put forward by Murayama using the ThoulessAnderson-Palmer equations applied to Sourlas-type codes关8兴. It is important to study a wide class of decoders to extract a pool of schemes that can give near-Shannon-boundperformance prior to fully investigate the encoding problem.
The study of such schemes could give interesting clues as to
how the lossy compression process works, and it might also
help to pinpoint some essential features a scheme should
possess in order to achieve Shannon optimal performance.
This paper extends the framework introduced in 关9–11兴
and studies three different decoders based on a nonmonotonic multilayer perceptron. Hosaka et al. studied a simple
perceptron network featuring a nonmonotonic transfer function in order to have a mirror symmetry property in theirmodel 关i.e., f共u兲 = f共−u兲兴. This was motivated by the belief
that the Edwards-Anderson order parameter should be zero
to reach the Shannon bound. Consequently, if one codewords is optimal 共note that here optimal denotes a codeword thatgives the minimum achievable distortion for the concerned
scheme兲, −s is also optimal. Then, they show that for an
infinite length codeword, their scheme effectively saturates
the Shannon bound. Next, one interesting feature of themodel proposed by Mimura et al. 关11兴 is to increase thenumber of optimal codewords by using a multilayer decoder
network. The number of optimal codewords is a function of
the number of hidden units K in the decoder network 共for
example, in their parity-tree model with an even number ofhidden units, there are at least 2K−1 optimal codewords兲.
Thus, one can expect that finding an optimal codeword becomes more and more easy as the number of hidden units
increases. Nevertheless, their model deals only with unbiased
messages. The main advantage of the model proposed in this021124-1©2008 The American Physical Society

PHYSICAL REVIEW E 78, 021124 共2008兲

COUSSEAU et al.

paper is to combine the benefits of the Hosaka et al. model
共mirror symmetry and ability to deal with biased messages兲
with the benefits of Mimura et al. model 共increasing numberof optimal codewords with the number of hidden units兲. By
studying three different schemes we would like to extract
some essential characteristics that a good lossy compression
framework should possess. Finally, the Almeida-Thouless
共AT兲 stability of the obtained solutions is also studied andpresents very good properties with almost no unstable part.
The paper is organized as follows. Section II introduces
the framework of lossy compression. Section III exposes ourmodel. Section IV presents the mathematical tools used toevaluate the performance of the present scheme. Section V
states some results concerning the validity of the obtained
solutions and Sec. VI is devoted to conclusion and discussion.
II. LOSSY COMPRESSION

Let us begin by introducing the framework of lossy datacompression 关21兴. Let y be a discrete random variable defined on a source alphabet Y. An original source message iscomposed of M random variables, y = 共y 1 , . . . , y M 兲 苸 Y M , andcompressed into a shorter expression. The encoder compresses the original message y into a codeword s, using thetransformation s = F共y兲 苸 SN, where N ⬍ M. The decoder
maps this codeword s onto the decoded message ŷ, using thetransformation ŷ = G共s兲 苸 Ŷ M . The encoding and decoding
scheme can be represented as in Fig. 1.
In this case, the code rate is defined by R = N / M. A distortion function d is defined as a mapping d : Y ⫻ Ŷ → R+.
With each possible pair of 共y , ŷ兲, it associates a positive real
number. In most cases, the reproduction alphabet Ŷ is thesame as the alphabet Y on which the original message y isdefined.
Hereafter, we set Ŷ = Y, and we use the Hamming distortion as the distortion function of the scheme. This distortionfunction is given by
d共y,ŷ兲 =再0, y = ŷ,1, y ⫽ ŷ,冎

if there exists a coding-decoding scheme such that, when
M → ⬁ and N → ⬁ 共note that the rate R is kept finite兲, wehave E关共1 / M兲d共y , ŷ兲兴 艋 D. In other words, a rate distortion
pair 共R , D兲 is said to be achievable if there exist a pair 共F , G兲such that E关共1 / M兲d共y , ŷ兲兴 艋 D in the limit M → ⬁ andN → ⬁.
The optimal compression performance that can be obtained in the framework of lossy compression is given by theso-called rate-distortion function R共D兲 which gives the best
achievable code rate R as a function of D 关21兴. However,despite the fact that the best achievable performance is
known, no clues are given about how to construct such an
optimal compression scheme. Moreover, finding explicitly
the expression of the rate-distortion function is, in generalcases, not possible.
Nonetheless, for the special case of uniformly biased
Boolean messages in which each component is generated
independently by the same probability distribution P关y = 0兴
= 1 − P关y = 1兴 = p, it is possible to calculate analytically therate distortion function R共D兲, which becomes
R共D兲 = H2共p兲 − H2共D兲,

where H2共x兲 = −xlog2 x − 共1 − x兲log2共1 − x兲. In the following,
we restrict ourselves to this particular case 共i.e., P关y = 0兴 = 1− P关y = 1兴 = p and Y = 兵0 , 1其兲.
III. COMPRESSION USING NONMONOTONICMULTILAYER PERCEPTRONSIn this section we introduce our compression scheme. To
make the calculations compatible with the statistical mechanics framework, let us map the Boolean representation 兵0,1其 to
the Ising representation 兵−1 , 1其 by means of the mapping␴ = 共−1兲␳, where ␴ is the Ising variable and ␳ is the Boolean
one. On top of that, we set Y = S = Ŷ = 兵−1 , 1其. Since we consider that all the y ␮ are generated independently by an identically biased binary source, we can easily write the corresponding probability distribution

共1兲

so that the quantity d共y , ŷ兲 = 兺␮M=1d共y ␮ , yˆ␮兲 measures how far

the decoded message ŷ is from the original message y. In
other words, it records the error made on the original message during the encoding and decoding process. The probability of error distortion can be written E关d共y , ŷ兲兴 = P关y⫽ ŷ兴 where E represents the expectation. Therefore, the distortion associated with the code is defined as D
= E关共1 / M兲d共y , ŷ兲兴, where the expectation is taken with respect to the probability distribution P关y , ŷ兴. D corresponds tothe average error per variable, ŷ ␮. Now we define a rate
distortion pair 共R , D兲 and we say that this pair is achievable
y

F

s

G

y

Original
message

Encoder

Codeword

Decoder

Decodedmessage

FIG. 1. Rate distortion encoder and decoder.

共2兲

P关y ␮兴 = p␦共1 − y ␮兲 + 共1 − p兲␦共1 + y ␮兲.

共3兲

Next we define the decoder of the compression scheme. We
use a nonlinear transformation G : SN → Ŷ M which associatesa codeword s 苸 SN with a sequence ŷ 苸 Ŷ M . For a given
original message y, the encoder is simply defined as follows:
F共y兲 ⬅ arg min d共y,G共ŝ兲兲.
ŝ

共4兲For the nonlinear transformation G, we utilize nonmonotonic multilayer perceptrons. The codeword s is split into
共N / K兲-dimensional K disjoint vectors s1 , . . . , sK 苸 SN/K sothat s can be written s = 共s1 , . . . , sK兲. In this paper, we will
focus on three different architectures for the nonmonotonic
multilayer perceptrons. There are the followings.
共I兲 A multilayer parity tree with nonmonotonic hidden
units. Its output is written

021124-2

STATISTICAL MECHANICS OF LOSSY COMPRESSION …

sK

u1

d共x,y兲 = 1 − ⌰共xy兲,

...

y^m

m

...

m

XK

sl

...

m

Xl

s1

...

X1

tion, the Hamming distance d takes a simple form:

m

...

m

PHYSICAL REVIEW E 78, 021124 共2008兲

ul

m

uK

FIG. 2. General architecture of a treelike multilayer perceptron
with N input units and K hidden units.
Kŷ ␮共s兲 ⬅ 兿 f k
l=1

冉冑

冊

K
sl · xl␮ .
N

共5兲

共II兲 A multilayer committee tree with nonmonotonic hidden
units. Its output is written冋 兺 冉冑 冊册
Kŷ ␮共s兲 ⬅ sgn

K
sl · xl␮
N

fk

l=1

共6兲

.

Note that in this case, if the number of hidden units K iseven, then there is a possibility to get 0 for the argument of
the sign function. We avoid this uncertainty by considering
only an odd number of hidden units for the committee treewith nonmonotonic hidden units in the following.
共III兲 A multilayer committee tree with a nonmonotonic
output unit. Its output is written冋冑 兺 冉冑
Kŷ ␮共s兲 ⬅ f k

1
sgn
K l=1

K
sl · xl␮
N

冊册

.

再

1

if 兩x兩 艋 k,

− 1 if 兩x兩 ⬎ k,

冎IV. ANALYTICAL EVALUATION

We analyze the performance of these three different compression schemes using the tools of statistical mechanics. We
first define the following partition function:
Z共␤,y,x兲 = 兺 exp关− ␤H„y,ŷ共s兲…兴,

共11兲

s

共8兲

and the vectors xl␮ are fixed 共N / K兲-dimensional independentvectors uniformly distributed on 兵−1 , 1其. “sgn” denotes thesign function, taking the value 1 for x 艌 0 and −1 for x ⬍ 0.
Each of these architectures applies a different transformation
to the codeword s. The general architecture of theseperceptron-based decoders is shown in Fig. 2.
Note that we can also consider a decoder based on a committee tree where both the hidden units and the output unit
are nonmonotonic. However, this introduces an extra parameter 共we will have one threshold parameter for the hidden
units, and one for the output unit兲 to tune and the performance should not change drastically. For simplicity, we restrict our study to the above three cases only.
Now let us introduce H, an energy function of the system,
H共y,ŷ„s兲兲 = d共y,ŷ共s兲….

where ⌰ denotes the unit step function which is 1 for x 艌 0
and 0 for x ⬍ 0.
The encoding phase can be viewed as a classical perceptron learning problem, where one tries to find the weightvector s that minimizes the energy function H for the original message y and the random input vector x. The vector swhich achieves this minimum gives us the codeword to besent to the decoder. Therefore, in the case of a lossless compression scheme 共i.e., D = 0兲, evaluating the rate-distortion
property of the present scheme is equivalent to finding thenumber of couplings s that satisfies the input-output relationx␮ 哫 y ␮. In other words, this is equivalent to the calculationof the storage capacity of the network 关22,23兴.
The choice of parity-tree- and committee-tree-based networks is motivated by the thorough literature available on
this kind of network. Parity and committee machines havebeen intensively studied 共see 关24兴 for an overview兲 by themachine-learning community over the years. The techniques
used to calculate the storage capacity of such networks give
us a starting point for our analytical evaluation of the typicalperformance of the above schemes.

共7兲

In each of these structures, f k is a nonmonotonic function ofa real parameter k of the formf k共x兲 =

共10兲

共9兲

This energy function H is clearly minimized for a codewords that satisfies Eq. 共4兲. Furthermore, in the Ising representa-

where the sum over s represents the sum over all the possible
states for the vector s. ␤ denotes the inverse temperatureparameter. Such a partition function can be identified withthe partition function of a spin glass system with dynamicalvariables s and quenched variables x. For a fixed Hamming
distortion MD = E关d共y , ŷ兲兴, the average of this partition function over y and x naturally contains all the interesting typical
properties of the scheme, such as the entropy. However,
evaluating this average is hard and we need some technique
to investigate it. In this paper we use the so-called replica
method in order to calculate the average of the partition
function. In the case of such a discrete system, the entropy
should not be negative, so that the zero-entropy criterion 共see
关23兴兲 gives us the best achievable code rate limit. The replica
method’s calculations to obtain the average of the partition
function 具Z共␤ , y , x兲典y,x are detailed in Appendix A.
A. Replica symmetric solution for the parity treewith nonmonotonic hidden units

In the lossy compression scheme using a parity tree withnonmonotonic hidden units 共5兲, the replica symmetric freeenergy is given by

021124-3

PHYSICAL REVIEW E 78, 021124 共2008兲

COUSSEAU et al.

f共␤,R,k兲 = −Finally, since we used the replica symmetric 共RS兲 ansatz,
we have to verify the Almeida-Thouless stability of the solution to confirm its validity. This is done in the next section.

1
兵p ln关e−␤ + 共1 − e−␤兲Ak兴␤

+ 共1 − p兲ln关e−␤ + 共1 − e−␤兲共1 − Ak兲兴 + R ln 2其,B. Replica symmetric solution for the committee treewith nonmonotonic hidden units

共12兲
where

In the lossy compression scheme using a committee treewith nonmonotonic hidden units 共6兲, the replica symmetricfree energy is given by

1 1
Ak = + 关1 − 4H共k兲兴K ,
2 2

冕 冑
+⬁

H共k兲 =

kef共␤,R,k兲 = −

−t2/2

2␲

dt.

共13兲

1
兵p ln关e−␤ + 共1 − e−␤兲Bk兴␤

+ 共1 − p兲ln关e−␤ + 共1 − e−␤兲共1 − Bk兲兴 + R ln 2其,共19兲

The internal free energy ise−␤共1 − Ak兲e −␤A k+共1−p兲.
u共␤,k兲 = p −␤
e + 共1 − e−␤兲Ake−␤ + 共1 − e−␤兲共1 − Ak兲

where
Bk = 兺

共14兲
Minimizing the free energy with respect to Ak, taking thezero-temperature limit ␤ → ⬁, and using the identity 共A6兲
gives
Ak =

p−D
,
1 − 2D

共15兲

D=

e −␤
.
1 + e −␤

共16兲Finally, using the zero-entropy criterion, one can get
R = H2共p兲 − H2共D兲,

冉 冑 冊

K
2p − 11
1−.
4
1 − 2D

␶l=⫾1

K

␶l

⌰

l=1

l=1

共18兲

In this paper we consider that 共p , D兲 苸 兵关0 , 21 兴其2; therefore,
one can easily show that for p ⫽ 21 then 共2p − 1兲 / 共1 − 2D兲 isnegative, which implies that there is no real solution for theabove equation if we have an even number of hidden units K
共because of the Kth root兲. However, we can also consider thecase where 共p , D兲 苸 兵关 21 , 1兴 ⫻ 关0 , 21 兴其 without any change 共theprobabilities of y = 1 and y = −1 are just inverted兲 and in thiscase 共2p − 1兲 / 共1 − 2D兲 is positive which implies that there isalways a solution for any value of K. The above problem isjust a consequence of the definition of p, but is not related tothe model. So, in the case of the parity tree, k̂ always exists
independently of the value of K.

1 + ␶l共1 − 4H关k兴兲2冊册. 共20兲

The sum over ␶l represents the sum over each possible state
for the dummy variable ␶l 共␶l = ⫾ 1兲. The internal free energyise−␤共1 − Bk兲e −␤B ku共␤,k兲 = p −␤
.
+
共1
−
p兲
e + 共1 − e−␤兲Bke−␤ + 共1 − e−␤兲共1 − Bk兲
共21兲
As in the parity tree case, after minimizing the free energy
with respect to Bk, taking the zero-temperature limit ␤ → ⬁,and using the identity 共A6兲, we obtain

共17兲

which is identical to the rate-distortion function 共2兲.
However, this minimum is reached under the conditions
given by Eqs. 共15兲 and 共16兲. Since D is fixed, the condition
given by Eq. 共16兲 is easily satisfied by choosing the proper
inverse temperature parameter ␤ = ln关共1 − D兲 / D兴. On theother hand, the condition given by Eq. 共15兲 is satisfied byproperly tuning the parameter k of the nonmonotonic function f k. Let us denote the optimal k that satisfies Eq. 共15兲 byk̂. In the case of the parity tree, this optimal k̂ is such that thefollowing equation becomes true:
H共k̂兲 =

冋 冉兺 冊兿 冉
K

Bk =

p−D
,
1 − 2D

共22兲

D=

e −␤
.
1 + e −␤

共23兲Finally, using the zero-entropy criterion, one can get
R = H2共p兲 − H2共D兲,共24兲

which is identical to the rate-distortion function 共2兲. However, here it is not easy to discuss the existence of an optimalk̂ that satisfies the condition given by Eq. 共22兲. Such an optimal k̂ satisfies the following equation:兺 冋 冉兺 冊兿 冉
K

␶l=⫾1

K

␶l

⌰

l=1

l=1

1 + ␶l共1 − 4H关k̂兴兲
2

冊册

=

p−D
.
1 − 2D
共25兲

We will discuss this existence problem a bit more in the next
section, when we check the AT stability of the RS solution.
C. Replica symmetric solution for the committee treewith a nonmonotonic output unit

In the lossy compression scheme using a committee treewith a nonmonotonic output unit 共7兲, the replica symmetricfree energy is given by

021124-4

STATISTICAL MECHANICS OF LOSSY COMPRESSION …

f共␤,R,k兲 = −PHYSICAL REVIEW E 78, 021124 共2008兲

1
兵p ln关e−␤ + 共1 − e−␤兲Ck兴␤

+ 共1 − p兲ln关e−␤ + 共1 − e−␤兲共1 − Ck兲兴 + R ln 2其,
共26兲
where
K

Ck = 2

−K

冉冊冉
K

冊

1

⌰ k2 − 共2l − K兲2 .
兺
K
l=0 l

共27兲

The term 共 nl 兲 denotes the binomial coefficient. The internal
free energy ise−␤共1 − Ck兲e −␤C ku共␤,k兲 = p −␤.
+ 共1 − p兲 −␤−␤e + 共1 − e 兲Ck
e + 共1 − e−␤兲共1 − Ck兲
共28兲
As in the parity tree case, after minimizing the free energy
with respect to Ck, taking the zero-temperature limit ␤ → ⬁,and using the identity 共A6兲, we obtain
p−D
,
Ck =
1 − 2D
D=

共29兲

FIG. 3. 共Color online兲 AT line and rate-distortion function forthe parity tree with three hidden units. The rate-distortion performance of the parity tree is given by the rate-distortion function. The
original message is biased with bias p = 0.2. The rate-distortionfunction is always above the AT line and thus the RS solution isalways stable.

Q = R = P⬘ = Q⬘ = R⬘ = 0.

Therefore, using Eq. 共B8兲, the RS stability criterion is given
by
R⬎

e −␤
.
1 + e −␤

共33兲

共30兲

8 2 −kˆ2 ␤Kk̂ e 共e − 1兲2␲⫻Finally, using the zero-entropy criterion, one can get

冓冉

冊冔
2

关1 − 4H共k̂兲兴K−1
共e␤ + 1兲 + 共e␤ − 1兲y关1 − 4H共k̂兲兴K

,
y

共31兲

共34兲

which is identical to the rate-distortion function 共2兲. However, here also it is not easy to discuss the existence of an
optimal k̂. Such an optimal k̂ satisfies the following equation:

where ␤ is given by 共16兲, and where k̂ satisfies Eq. 共18兲.
具¯典y denotes the expectation with respect to 共3兲.
For p = 21 , that is to say for an unbiased message y, k̂satisfies the equation H共k̂兲 = 41 , which implies 关1 − 4H共k̂兲兴 = 0,
and so the AT line is given by the line R = 0. Consequently,
for unbiased messages, the RS solution is always AT stable.
Figure 3 shows the rate-distortion function plotted with
the AT stability line for biased messages with p = 0.2. All theregion below the AT line is unstable.
Since no part of the rate-distortion function is under the
AT line, the RS solution is always stable. We did the same
experiment for higher values of K and never found any unstable part.
The lossy compression scheme using a parity tree withnonmonotonic hidden units presents good properties. It saturates the Shannon bound for any value of K 艌 2, and the RS
solution seems to be always AT stable.

R = H2共p兲 − H2共D兲,

K

2

−K

冉冊冉
K

1

冊

p−D

.
⌰ k̂2 − 共2l − K兲2 =兺
K
1 − 2D
l=0 l

共32兲This existence problem is discussed later, when checking the
AT stability of the RS solution.
V. ALMEIDA-THOULESS STABILITY OF THE REPLICA
SYMMETRIC SOLUTION

In this section we check the AT stability 共see 关25兴兲 of the
RS solution of each scheme. We use the same method as in关11,22兴. The main mathematical points of the AT stability
study are given in Appendix B.
A. AT stability for the parity tree with nonmonotonic hidden
units

B. AT stability for the committee tree with nonmonotonic
hidden units

In the case of a parity tree with nonmonotonic hidden
units, we findIn the case of a comittee tree with nonmonotonic hidden
units, we findP=

8 −1 2 −k2 ␤
R k e 共e − 1兲2
␲
⫻

冓冉

冊冔

2
关1 − 4H共k兲兴K−1
共e␤ + 1兲 + 共e␤ − 1兲y关1 − 4H共k兲兴K冋冉P = R−1 p,⫻y021124-5冉冊

共e␤ − 1兲共Bk − Bk*兲 2
1 + 共e␤ − 1兲Bk

共e␤ − 1兲共Bk* − Bk兲

1 + 共e␤ − 1兲共1 − Bk兲

冊册
2

,

+ 共1 − p兲PHYSICAL REVIEW E 78, 021124 共2008兲

COUSSEAU et al.

FIG. 4. 共Color online兲 AT line and rate-distortion function forthe committee tree with three nonmonotonic hidden units. The ratedistortion performance of the committee tree is given by the ratedistortion function. The original message is unbiased 共p = 0.5兲. The
rate-distortion function is always above the AT line, and thus the RS
solution is always stable.

Q = R = P⬘ = Q⬘ = R⬘ = 0,
where
B* =
k

冋 冉 兺 冊冉
K

兺

␶l=⫾1
K

⫻兿
l=2

␶l

⌰

冉

l=1

共35兲

1 + ␶1共1 − 4ke−k /2/冑2␲ − 4H关k兴兲22

1 + ␶l共1 − 4H关k兴兲
2

冊册

冊

共36兲

.

Therefore, using Eq. 共B8兲, the RS stability criterion is given
by

冋冉

R⬎K p

⫻

冉

冊
冊册

共e␤ − 1兲共Bkˆ − B*ˆ 兲k

1 + 共e␤ − 1兲Bkˆ共e␤ − 1兲共B*ˆ − Bkˆ兲k

1 + 共e␤ − 1兲共1 − Bkˆ兲2

+ 共1 − p兲

However as mentioned in the previous section, it is notclear if there exists a k̂ that makes Eq. 共25兲 true. Nevertheless, we did some numerical calculations for K = 3 and 5 共inthis case we consider only odd values of K as mentioned
earlier兲, and always found an optimal k 共⬅k̂兲 in those cases.
We present here the results obtain for K = 3. Figures 4 and5 show the rate-distortion function plotted with the AT stability line for unbiased 共p = 0.5兲 and biased 共p = 0.2兲 messages. Since no part of the rate-distortion function is underthe AT line, the RS solution is always stable. We tried also
for higher values of K and no unstable parts were found for
the RS solution.
The lossy compression scheme using a committee treewith nonmonotonic hidden units also presents good properties. If an optimal k̂ exists 共which seems to be always true兲, it
saturates the Shannon bound, and the RS solution seems tobe always AT stable.

2

R−1
共1 − e␤兲22−2共K−2兲
␲2

C. AT stability for the committee tree with a nonmonotonic
output unit

共37兲

,

where ␤ is given by 共23兲, and where k̂ satisfies Eq. 共25兲.

P⬘ =FIG. 5. 共Color online兲 AT line and rate-distortion function forthe committee tree with three nonmonotonic hidden units. The ratedistortion performance of the committee tree is given by the ratedistortion function. The original message is biased 共p = 0.2兲. The
rate-distortion function is always above the AT line, and thus the RS
solution is always stable.

冬冢冢In the case of a committee tree with a nonmonotonic output unit, we findK−2 冣 冢

K−2− K + y 冑K − 2k
K − y 冑K − 2k−122e−␤/2共y−1兲 − y共1 − e␤兲Ck

P = Q = R = Q⬘ = R⬘ = 0,

冣冭

冣

2

,
y

共38兲

where x denotes the ceiling function 共x = min兵n 苸 Z 兩 n 艋 x其兲 and x denotes the floor function 共x = max兵n 苸 Z 兩 n 艋 x其兲. Therefore, using Eq. 共B8兲, the RS stability criterion is given by
021124-6

STATISTICAL MECHANICS OF LOSSY COMPRESSION …

K共K − 1兲R⬎
共1 − e␤兲22−2共K−2兲
␲2

冬冢冢

PHYSICAL REVIEW E 78, 021124 共2008兲

K−2 冣 冢

K−2− K + y 冑K − 2k̂
K − y 冑K − 2k̂−122e−␤/2共y−1兲 − y共1 − e␤兲Ckˆ

where ␤ is given by 共30兲, and where k̂ satisfies Eq. 共32兲.
具¯典y denotes the same expectation as in the parity tree case.
However as mentioned in the previous section, here also it
is not clear if there exists k̂ such that Eq. 共32兲 is satisfied. On
top of that, the function Ck, which depends on k, is not continuous but discrete. Ck is a step function of k. Therefore, wemight have no k satisfying Eq. 共32兲. On the other hand, since
Ck is a step function of k, if we find a k that satisfies Eq. 共32兲,then it implies that k̂ is not given by a unique solution but by
an optimal interval where all the elements in this intervalsatisfy 共32兲. We did some numerical experiments for an unbiased message 共p = 0.5兲. For the special case of K = 2, Eq.
共32兲 is clearly satisfied for any k 苸 兴0 , 冑2关 so that in this casek̂ is given by any element of the interval 兴0 , 冑2关. But for K⬎ 2 共we checked up to K = 100兲, we did not found any optimal k. We did the same thing for a biased message 共p = 0.2兲with a fixed distortion D = 0.1, and for any K 艋 100 no optimal k exists. This implies that, in the general case, the committee tree with a nonmonotonic output unit does not saturate
the Shannon bound. However, if the number of hidden units
K becomes very large, we can apply the central limit theorem
to replace the scalar product sl · xl by a Gaussian variable.
Under these conditions, the expression of Ck becomes very
simple,

冣

冣冭
2

,

共39兲

y

In this case, Ck is no longer a step function, but a continuousfunction of k, and it is easy to see that there is always a k thatsatisfies the equation
1 − 2H共k兲 =p−D.
1 − 2D

共41兲

Let us denote it by k̂inf. So in the large-K limit k̂ = k̂inf exists
and is unique. The compression scheme with a committee
tree using a nonmonotonic output unit saturates the Shanonbound in this limit. It is, however, hard to check the AT
stability for an infinite number of hidden units K 共the binomial coefficient follows a factorial growth兲, but we claimthat the solution obtained by the RS ansatz is always AT
stable 共except for some very narrow region where D ⬇ p兲. We
show in Figs. 6 and 7 the rate distortion function plotted with
the AT line for K = 50 hidden units for unbiased 共p = 0.5兲 andbiased 共p = 0.2兲 messages.
To sum up this section, the lossy compression scheme
using a committee tree with a nonmonotonic output unit presents a quite complex structure which does not saturate theShannon bound in most cases. However, it does saturate it
when the number of hidden units becomes infinite. Concerning the AT stability, the committee tree with a nonmonotonic
output unit does not seem to exhibit any critical instability
for the RS solution.
VI. CONCLUSION AND DISCUSSION

共40兲

We investigated a lossy compression scheme for uniformly biased Boolean messages using nonmonotonic parity

FIG. 6. 共Color online兲 AT line and rate-distortion function forthe committee tree with a nonmonotonic output unit. The ratedistortion performance of the committee tree is given by the ratedistortion function. The original message is unbiased 共p = 0.5兲. The
AT line is calculated using K = 50. The rate-distortion function isalways above the AT line, and thus the RS solution is always stable.

FIG. 7. 共Color online兲 AT line and rate-distortion function forthe committee tree with a nonmonotonic output unit. The ratedistortion performance of the committee tree is given by the ratedistortion function. The original message is biased 共p = 0.2兲. The AT
line is calculated using K = 50. The rate distortion function is always
above the AT line except for a very narrow region where D ⬇ p.

Ck = 1 − 2H共k兲.

021124-7

COUSSEAU et al.

PHYSICAL REVIEW E 78, 021124 共2008兲

tree and nonmonotonic committee tree multilayer perceptrons. All the schemes were shown to saturate the Shannon
bound under some specific conditions. The replica symmetricsolution is always stable, which tends to confirm the validityof the replica symmetric ansatz.
The Edwards-Anderson order parameter q was always
found to be 0, meaning that codewords are uncorrelated in
the codeword space. As already mentioned in 关9,11兴, one
may conjecture that this is a necessary condition for a lossy
compression scheme to achieve the Shannon limit. The mirror symmetry seems then to be an essential feature to saturate
the Shannon bound. The committee tree with nonmonotonic
hidden units corresponds to the same committee tree model
as in the Mimura et al. paper 关11兴, with the exception of thehidden layer transfer function, which is given by the nonmonotonic transfer function f k in this paper. By enforcing
mirror symmetry in the hidden layer, we were able to get
Shannon optimal performance for an infinite length codeword independently of the number of hidden units, whereas
this was not possible using the Mimura et al. model, even for
an infinite number of hidden units. In the same way, keeping
the monotonic sgn function as the transfer function of thehidden layer and transforming only the output unit into a
nonmonotonic one by the use of f k 共i.e., the committee treewith a non monotonic output unit兲, we were able to reach the
Shannon limit with an infinite number of hidden units. Onceagain, enforcing mirror symmetry enabled us to get Shannon
optimal performance.
Next, one can easily derive a lower bound for the numberof optimal codewords 共here “optimal” means a codeword
that gives the minimum achievable distortion of the corresponding scheme兲 for each of the three schemes. In the caseof the parity tree and committee tree with nonmonotonic
hidden units, there are at least 2K optimal codewords in thecodeword space. Indeed, if s denotes an optimal codeword,
we can replace any of its components sl by −sl without altering the output of the hidden layer, and thus leave the output of the network unchanged. In the case of the committee
tree with a non-monotonic output unit, because of the more
complex structure of the hidden layer, we can guarantee only
the existence of two optimal codewords, which are given bys and −s.
However, a formal encoder for those schemes would require a computational cost which grows exponentially withthe original message length to perform its task. We needmore efficient algorithms to reduce the encoding time. A
preliminary study made by Hosaka et al. 关20兴 uses the BP
algorithm for this task. This could be a good solution toachieve the encoding phase in a polynomial time. Anotherpossibility is to use the survey propagation algorithm approach which was developed for satisfiability problems 关26兴.
Furthermore, as mentioned above, the parity tree and committee tree with nonmonotonic hidden units have a numberof optimal codewords that grows exponentially with thenumber of hidden units. This could make the search for one
optimal codeword easier to achieve using some proper heuristics. This issue will be studied in a future presentation.

ACKNOWLEDGMENTS

This work was partially supported by a Grant-in-Aid for
Encouragement of Young Scientists 共B兲 共Grant No.
18700230兲, Grants-in-Aid for Scientific Research on Priority
Areas 共Grants No. 18079003 and No. 18020007兲, a Grant-inAid for Scientific Research 共C兲 共Grant No. 16500093兲, and a
JSPS Grant-in-Aid 共Grant No. 06J06774兲 from the Ministryof Education, Culture, Sports, Science and Technology ofJapan. T.O. acknowledges support from the Japan Society for
the Promotion of Science.
APPENDIX A: ANALYTICAL EVALUATIONUSING THE REPLICA METHOD

The free energy can be evaluated by the replica method
共the parameter k is fixed here兲,f共␤,R兲 = −1
具Z共␤,y,x兲n典y,x − 1lim,␤N n→0n

共A1兲

where Z共␤ , y , x兲n denotes the n-times replicated partition
function,n

Z共␤,y,x兲n =兿 exp关− ␤H„y,ŷ共sa兲…兴.
兺 a=1

共A2兲

s1,. . .,sn

The vector sa is given by sa = 共sa1 , . . . , sKa兲 and the superscripta denotes the replica index.
By using the zero-entropy criterion 关23兴, we have
0 = ␤关U − F兴,
u = f,

共A3兲

where U denotes the internal energy and F the free energy. u
and f denote the same quantity per bit 共u = U / N, f = F / N兲. In
the zero-entropy limit, only one state of the dynamical variable s achieves a distortion per bit inferior or equal to D. The
free energy per bit,f共␤,R兲 = −1
ln 具Z共␤,y,x兲典y,x ,
␤N

共A4兲

is equal to the internal energy per bit,u共␤兲 =

⳵␤ f
.
⳵␤

共A5兲

This result f共␤ , R兲 = u共␤兲 gives us an explicit relation between the code rate R and the inverse temperature ␤.
Since this temperature was artificially introduced bymeans of the parameter ␤, we should get rid of it by taking
the zero-temperature limit 共␤ → + ⬁兲 where the dynamicalvariable freezes. At this limit, one can retrieve the codeword
that minimizes the free energy and gives the best achievable
code rate. However, since a distortion per bit D is tolerated,
at the zero-temperature limit the internal energy per bit
should be equal to this distortion. This motivates the introduction of the following identity:

021124-8

STATISTICAL MECHANICS OF LOSSY COMPRESSION …

lim u共␤兲 = D.

PHYSICAL REVIEW E 78, 021124 共2008兲

共A6兲

␤→+⬁

K

n

1= 兿 兿
a⬍b l=1

Finally, at this zero-temperature limit, one can get an explicit
relation which binds the best achievable code rate R with thedistortion D:

=

冉 冊

冕

冉

+⬁

a
b
dqab
l ␦ sl · sl −−⬁1 n共n−1兲K/2
2␲i冕 冉兿 兿

⫻ exp

q̂absal · sbl −l冋兺 兺 冉

共A7兲冕 冉兿 兿冋 冓冕 冉兿 冊兿冔 兺 冉兺 兺冊

ab⫻ exp N R−1 lndqab
l dq̂la⬍b lduldvll⫻ 兿 关e−␤ + 共1 − e−␤兲⌰共y,兵ual 其兲兴awhere Ql is an n ⫻ n matrix having elements 兵qabl 其 and where
具¯典y denotes the expectation with respect to 共3兲. The function ⌰共y , 兵ual 其兲 depends on the decoder and will be discussed
in the following sections. We analyze the scheme in the thermodynamic limit N , M → + ⬁, while the code rate R is kept
finite. In this limit, 共A9兲 can be evaluated using the saddleabpoint method with respect to qabl and q̂l . To continue thecalculation, we have to make some assumptions about thestructure of these order parameters. We use here the so-called
replica symmetric ansatz

共A8兲

+

y

1
ln
K

t

l

exp

兵sal 其冊a bq̂abl sl sl −a⬍b l

1f共␤,R,k,q,q̂兲 = − extr
␤ q,q̂册1
兺 兺 qabq̂ab ,K a⬍b l l l冋冓 冕 冉 兿 冊
+⬁

K

−⬁

l=1

Dtl

⫻ln关e−␤ + 共1 − e−␤兲⌸k共兵tl其,y兲兴

+R

冕

+⬁

冔

Du ln关2 cosh共冑q̂u兲兴 − R

−⬁

共A9兲

册

y

q̂共1 − q兲
,
2
共A12兲

2

q̂ab
l = 共1 − q̂兲␦ab + q̂,

共A10兲

where ␦ab denotes the Kronecker delta. This ansatz meansthat all the hidden units are equivalent after averaging overthe disorder.

冊

冑2␲ ,

冋 冉 冊 冉 冊册

.

共A13兲
Taking the derivative of 共A12兲 with respect to q and q̂ gives
the saddle point equations for the order parameters:冓冕 冉 冊+⬁q̂ = 2R

In the case of a parity tree with nonmonotonic hidden
units, the function ⌰共y , 兵ual 其兲 in 共A9兲 is given by⌰共y,兵ual 其兲 = ␪ y 兿 sgn关k2 − 共ual 兲2兴 .

e−x /2dx

1 y
k + 冑qtlk − 冑qtl− 2H+ 兿 1 − 2H
冑1 − q冑1 − q2 2 l=1
K⌸k共兵tl其,y兲 =1. Replica symmetric evaluation for the parity tree withnonmonotonic hidden units

l=1

冊册

共e−共1/2兲 vlQlvl+ivl·ul兲

Dx =

K

N ab
q
K l

冊

where extr denotes extremization and whereqabl = 共1 − q兲␦ab + q,

冉

ab
dqab
l dq̂linto 共A2兲 enables us to separate the relevant order parameter,
and to calculate the average moment 具Z共␤ , y , x兲n典y,x for natural numbers n as

We now proceed to the calculation of the replicated partition function 共A2兲. Inserting the identity
具Z共␤,y,x兲n典y,x ⯝

冊

a⬍b l

a⬍b l

f共D,R兲 = D.

N ab
q
K l

−1

K

− 共1 − e−␤兲⌸⬘共兵t 其,y兲lkDtl ⫻ −␤
兿
−␤
e
+
共1
−
e
兲⌸
共兵t
k l其,y兲
l=1
−⬁

q=

冕

+⬁

Du tanh2共冑q̂u兲,

冔

,
y

共A14兲

−⬁

共A11兲

We can then obtain the expression of the free energy as

where ⌸k⬘共兵tl其 , y兲 = ⳵⌸k共兵tl其 , y兲 / ⳵q.
We solved this saddle point equation numerically and findthat the solution is given for q = q̂ = 0. According to 关9,11兴 thisresult was expected and implies that all the codewords areuncorrelated and distributed all around SN. Substituting q

021124-9

PHYSICAL REVIEW E 78, 021124 共2008兲

COUSSEAU et al.

= q̂ = 0 into 共A12兲, one can finally find the free energy given
by 共12兲.

f共␤,R,k,q,q̂兲 = −2. Replica symmetric evaluation for the committee tree withnonmonotonic hidden units冉冊冋冓 冕 冉 兿 冊

⫻ln关e

冕

−␤

l=1

−⬁

−␤

+ 共1 − e 兲⌺k共兵tl其,y兲兴冔⌺k共兵tl其,y兲 = 兺␶l=⫾1

再冋 册 冋␪ y 兺 ␶l ⫻ 兿
l=1

冉

l=1

冊 冉

l=1

册

y

k + 冑qtlk − 冑qtl− ␶ lH− ␶ lH冑1 − q冑1 − q冓冕 冉 冊+⬁−⬁K

兿 Dtl ⫻
l=1

q=

冕

+⬁

冊册冎

− 共1 − e−␤兲⌺k⬘共兵tl其,y兲e−␤ + 共1 − e−␤兲⌺k共兵tl其,y兲

.
共A17兲

冔

,
y

共A18兲

where ⌺k⬘共兵tl其 , y兲 = ⳵⌺k共兵tl其 , y兲 / ⳵q.
We solved this saddle point equation numerically and here
also we find that the solution is given for q = q̂ = 0. Substituting q = q̂ = 0 into 共A16兲, one can finally find the free energy
given by 共19兲.
3. Replica symmetric evaluation for the committee treewith a nonmonotonic output unit

再冋 冉

兺
l=1

冊 册冎
2

K

sgn关ual 兴␪ yk2 −

冉 冊册

y
2
␶l
兺
K l

冉 冑 冊冎
q
1−q

−⬁

K

兿 Dtl ⫻

.

共A21兲

l=1

冕

+⬁

⬘ 共兵tl其,y兲− 共1 − e−␤兲F⌺,k−␤−␤
e + 共1 − e 兲F⌺,k共兵tl其,y兲Du tanh2共冑q̂u兲,

冔

,
y

共A22兲

where F⌺,k
⬘ 共兵tl其 , y兲 = ⳵F⌺,k共兵tl其 , y兲 / ⳵q.
We solved this saddle point equation numerically and here
also we find that the solution is given for q = q̂ = 0. Substituting q = q̂ = 0 into 共A20兲, one can finally find the free energy
given by 共26兲.
APPENDIX B: ALMEIDA-THOULESS STABILITY
CRITERION

The Hessian computed at the RS saddle point characterab
izes fluctuations in the order parameters qabl and q̂l aroundthe RS saddle point. Instability of the RS solution is signaled
by a change of sign of at least one of the eigenvalues of theabHessian. Let M共兵qabl 其 , 兵q̂l 其兲 be the exponent of the integrand of integral 共A9兲. Equation 共A9兲 can be represented as
具Z共␤,y,x兲n典y,x =abdqab
l dq̂l

a⬍b l

冊

ab
⫻ exp关NM共兵qabl 其,兵q̂l 其兲兴.

共B1兲

ab
We expand M around q and q̂ in ␦qabl and ␦q̂l and then find
up to the second order1t
vGv + O共储v储3兲,
2
共B2兲

where
ab
ab
ab
v = t共兵␦qab
1 其,兵␦q̂1 其, . . . ,兵␦qK 其,兵␦q̂K 其兲. 共A19兲

We can then obtain the expression of the free energy as冕 冉兿 兿

ab
M共兵q + ␦qabl 其,兵q̂ + ␦q̂l 其兲 = M共兵q其,兵q̂其兲 +In the case of a committee tree with a non-monotonic
output unit, the function ⌰共y , 兵ual 其兲 in 共A16兲 is given by
1
y k −
K

q̂共1 − q兲,2−⬁

Du tanh2共冑q̂u兲,2冓冕 冉 冊+⬁q̂ = 2R−1q=−⬁⌰共y,兵ual 其兲 = ␪册yTaking the derivative of 共A20兲 with respect to q and q̂ gives
the saddle point equations for the order parameters,

Taking the derivative of 共A16兲 with respect to q and q̂ gives
the saddle point equations for the order parameters,q̂ = 2R−1

再冋⫻ 兿 H − t l␶ l

1 + ␶l
2

冔

共A20兲

K

共A16兲
K

l=1

Du ln关2 cosh共冑q̂u兲兴 − R

␶l=⫾1

+⬁

K

冕

+⬁

F⌺,k共兵tl其,y兲 = 兺

Dtl

−⬁

Dtl

where

q̂共1 − q兲+R
Du ln关2 cosh共冑q̂u兲兴 − R
,
2
−⬁
where

+R

K

+⬁

K

共A15兲

We can then obtain the expression of the free energy as
1
f共␤,R,k,q,q̂兲 = − extr
␤ q,q̂

+⬁−⬁⌰共y,兵ual 其兲 = ␪ y 兺 sgn关k2 − 共ual 兲2兴 .
l=1

冋冓 冕 冉 兿 冊⫻ln关e−␤ + 共1 − e−␤兲F⌺,k共兵tl其,y兲兴In the case of a committee tree with nonmonotonic hidden
units, the function ⌰共y , 兵ual 其兲 in 共A9兲 is given by
K

1
extr
␤ q,q̂

共B3兲

is the perturbation to the RS saddle point. The Hessian G is
the following 关Kn共n − 1兲兴 ⫻ 关Kn共n − 1兲兴 matrix:
021124-10

STATISTICAL MECHANICS OF LOSSY COMPRESSION …

G=冢

U V ¯ VV U ¯ V]]]V V ¯ U冣PHYSICAL REVIEW E 78, 021124 共2008兲
cd

Ṽab,cd = ⳵2M/⳵qabl ⳵q̂l⬘共B4兲

,where n共n − 1兲 ⫻ n共n − 1兲 matrices U and V are
U=

V=

冉
冉

兵Uab,cd其 兵Ũab,cd其兵Ũab,cd其 兵Ũab,cd其兵Vab,cd其 兵Ṽab,cd其兵Ṽab,cd其 兵Ṽab,cd其

冊
冊

,

共B5兲

共l ⫽ l⬘兲.

共B7兲

For q , q̂ to be a local maximum of M, it is necessary for the
Hessian G to be negative definite 共i.e., all of its eigenvalues
must be negative兲.
To check these eigenvalues, we use the same method as in关11兴. We do not give the mathematical details here. Finally,using Gardner’s method 关22兴, we can derive the criterion for
the RS solution to be stable asK␥ ⬍ 1,

共B8兲

where
,

␥ ⬅ ␥0 + 共K − 1兲␥1 ,共B6兲

␥0 ⬅ P − 2Q + R,with

␥1 ⬅ P⬘ − 2Q⬘ + R⬘ ,
U

ab,cd

cd
= ⳵ M/⳵qabl ⳵ql ,
2P ⬅ Uab,ab ,Q ⬅ Uab,ac

cd
Ũab,cd = ⳵2M/⳵q̂abl ⳵q̂l ,R ⬅ Uab,cd
Ũ

ab,cd

cd
= ⳵ M/⳵qabl ⳵q̂l ,2

cd

Vab,cd = ⳵2M/⳵qabl ⳵ q l⬘
Ṽ

ab,cd

cd
= ⳵ M/⳵q̂abl ⳵q̂l⬘2

共b ⫽ c兲,

共a ⫽ c,b ⫽ d兲,P⬘ ⬅ Vab,ab ,Q⬘ ⬅ Vab,ac

共l ⫽ l⬘兲,R⬘ ⬅ Vab,cd

共l ⫽ l⬘兲,

共b ⫽ c兲,

共a ⫽ c,b ⫽ d兲.

共B9兲

The line K␥ = 1 defines the so-called AT line.

关1兴 N. Sourlas, Nature 共London兲 339, 693 共1989兲.
关2兴 Y. Kabashima, T. Murayama, and D. Saad, Phys. Rev. Lett.
84, 1355 共2000兲.
关3兴 H. Nishimori and K. Y. Michael Wong, Phys. Rev. E 60, 132
共1999兲.
关4兴 A. Montanari and N. Sourlas, Eur. Phys. J. B 18, 107 共2000兲.
关5兴 T. Tanaka, Europhys. Lett. 54, 540 共2001兲.
关6兴 T. Tanaka and M. Okada, IEEE Trans. Inf. Theory 51, 700
共2005兲.
关7兴 T. Murayama and M. Okada, J. Phys. A 36, 11123 共2003兲.
关8兴 T. Murayama, Phys. Rev. E 69, 035105共R兲 共2004兲.
关9兴 T. Hosaka, Y. Kabashima, and H. Nishimori, Phys. Rev. E 66,
066126 共2002兲.
关10兴 T. Hosaka and Y. Kabashima, J. Phys. Soc. Jpn. 74, 488
共2005兲.
关11兴 K. Mimura and M. Okada, Phys. Rev. E 74, 026108 共2006兲.
关12兴 C. E. Shannon, Bell Syst. Tech. J. 27, 379 共1948兲.
关13兴 R. Gallager, IEEE Trans. Inf. Theory IT-8, 21 共1968兲.
关14兴 D. J. C. MacKay and R. M. Neal, Electron. Lett. 33, 457
共1997兲.
关15兴 T. J. Richardson and R. L. Urbanke, IEEE Trans. Inf. Theory47, 638 共2001兲.
关16兴 C. E. Shannon, IRE Natl. Conv. Rec. 4, 142 共1959兲.
关17兴 Y. Matsunaga and H. Yamamoto, IEEE Trans. Inf. Theory 49,
2225 共2003兲.
关18兴 E. Martinian and M. J. Wainwright, in Proceedings of the Data
Compression Conference, 2006, edited by IEEE Computer Society 共unpublished兲.
关19兴 M. J. Wainwright, IEEE Signal Process. Mag. 24, 47 共2007兲.
关20兴 T. Hosaka and Y. Kabashima, Physica A 365, 113 共2006兲.
关21兴 T. M. Cover and J. A. Thomas, Elements of Information
Theory 共Wiley, New York, 1991兲.
关22兴 E. Gardner, J. Phys. A 21, 257 共1988兲.
关23兴 W. Krauth and M. Mézard, J. Phys. 共Paris兲 50, 3057 共1989兲.
关24兴 A. Engel and C. Van den Broeck, Statistical Mechanics ofLearning 共Cambridge University Press, Cambridge, U.K.,
2001兲.
关25兴 J. R. L. de Almeida and D. J. Thouless, J. Phys. A 11, 983
共1978兲.
关26兴 M. Mézard, G. Parisi, and R. Zecchina, Science 297, 812
共2002兲.

021124-11