FULL P APERS

Journal of the Physical Society of Japan 80 (2011) 034802
DOI: 10.1143/JPSJ.80.034802

Belief Propagation for Error Correcting Codes and Lossy Compression
Using Multilayer Perceptrons
Kazushi MIMURA, Florent COUSSEAU1 , and Masato OKADA1;2
Graduate School of Information Sciences, Hiroshima City University,
3-4-1 Ohtsuka-Higashi, Asaminami-ku, Hiroshima 731-3194, Japan
1
Division of Transdisciplinary Sciences, Graduate School of Frontier Sciences, The University of Tokyo,
5-1-5 Kashiwanoha, Kashiwa, Chiba 277-8561, Japan
2
RIKEN Brain Science Institute, 2-1 Hirosawa, Wako, Saitama 351-0198, Japan(Received May 12, 2010; accepted January 20, 2011; published online March 10, 2011)

The belief propagation (BP) based algorithm is investigated as a potential decoder for both of error correcting codes
and lossy compression, which are based on non-monotonic tree-like multilayer perceptron encoders. We discuss thatwhether the BP can give practical algorithms or not in these schemes. The BP implementations in those kind of fully
connected networks unfortunately shows strong limitation, while the theoretical results seems a bit promising. Instead,
it reveals it might have a rich and complex structure of the solution space via the BP-based algorithms.
KEYWORDS: belief propagation, lossy compression, error correcting code, committee machine, parity machine, replica
method, statistical mechanics

1.

Introduction

In today’s society, information processing is part of oureveryday life. As the pool of data available to us grows
exponentially within the years, it is vital to be able to store,
recover, and transmit those data in an eﬃcient way. With thebirth of information theory subsequently to the pioneering
work of Shannon,1) methods to eﬃciently process information start to become widely studied.
It has been shown that it is possible to ensure error freetransmission using a non zero code rate up to a maximum
value which cannot be exceeded without resulting in an
inevitable loss of information. This upper bound is known as
the Shannon bound. The design of eﬃcient and practicalcodes is still one of the main topics of information theory.
For example, the Sourlas’s code2) asymptotically attains
the Shannon bound, which is for channels with very small
capacity. A interesting feature of Sourlas’s paper is thatit showed the possibility to use methods from statisticalphysics to investigate error correcting code schemes.
Following this paper, the tools of statistical mechanics havebeen successfully applied in a wide range of problems of
information theory in recent years. For instance in the ﬁeldof error correcting codes itself,3–6) as well as spreading
codes.7–11)
On the other hand, lossy compression, which is thecounterpart of lossless compression which seeks error
free compression, has been also discussed.12) Its task is tocompress a given message allowing a certain amount ofdistortion between the original message and the reconstructed messages after compression. An eﬃcient lossy
compression scheme should be able to keep the compression
rate as large as possible while keeping the distortion as small
as possible. This is a typical trade-oﬀ optimization problem
between the desired ﬁdelity criterion and the compression
rate. As in ref. 1, Shannon derived an upper bound which
gives the optimal achievable compression rate for a ﬁxed
distortion, i.e., a ﬁxed ﬁdelity criterion. Recently, statisticalE-mail: mimura@hiroshima-cu.ac.jp

mechanical techniques were applied to these kind ofproblems with interesting results.13–18)
This paper focuses on error correcting code and lossy
compression where non-monotonic tree-like committee
machines or parity machines are used as encoder anddecoder respectively (for a thorough review on these kind ofneural networks, see ref. 19). It has been analytically shownthat in both error correcting code and lossy compression
cases, this kind of schemes can reach the Shannon boundunder some speciﬁc conditions.6,18) While these results areinteresting from a theoretical point of view, the complexityof a formal encoder/decoder prevents these schemes
from being practical. A formal way of encoding/decoding
information would require an amount of time which grows
exponentially with the size of the original message. One
possible solution is to use the popular belief propagation(BP) algorithm in order to approximate the marginalized
posterior probabilities of the appropriate Boltzmann factor
which describes the behavior of the scheme.
The BP algorithm is proved to be exact and is guaranteed
to converge only for probability distribution which can be
represented into a factor graph with no loop, i.e., a tree. This
is not the case for schemes based on the above kind of neuralnetworks as they are densely connected and necessarily
contains loops, i.e., their corresponding factor graph is not atree.
Nonetheless, the BP is known to give excellent approximating performance in the case of sparsely connected graphand have been successfully applied in decoding low density
parity check codes (LDPC) for example. On the other hand,
it is known that the approximation given by the BP in
the case of more densely connected graphs is sometimes
more mitigated. Several problems of sub-optimal solutions
or simply convergence failures arises.
However, despite those issues, it is considered thatinvestigating the BP algorithm on such kind of densely
connected schemes is still interesting from a statisticalphysical point of view and provides precious insight into thesolution space structure of such kind of systems. So far, only
the BP-based encoders of lossy compression, based on both

034802-1#2011 The Physical Society of Japan

J. Phys. Soc. Jpn. 80 (2011) 034802

FULL PAPERSof the low-density generator-matrix (LDGM) code13) and thesimple perceptron,20) have been discussed. Both BP-based
encoders for lossy compression based on the multilayer
perceptron (MLP) and BP-based decoders for error correcting codes based on the MLP have never investigated yet. In
this paper, we discuss that whether the BP can give practicalalgorithms or not in both error correcting codes and lossy
compression based on the MLP.
The paper is organized as follows. Section 2 introduces
non-monotonic tree-like multilayer perceptron networks
used throughout the paper. Section 3 exposes the frameworks of error correcting code and lossy compression.
Section 4 introduces the belief propagation algorithm andsection 5 states the results obtained by the algorithm in bothschemes. Section 6 is devoted to discussion and conclusion.
2.

K. MIMURA et al.

μ

X1

μ

Xl

μ

XK

s1

sl

sK

uμ1

μ

yμ

ul

uKμ

Fig. 1. General architecture of the treelike multilayer perceptron with N
input units and K hidden units.

Structure of Multilayer Perceptrons

In this section we introduce the kind of network we will
use throughout the paper. Tree like perceptrons were alreadystudied thoroughly by the machine learning community over
the years. It is known that a feed-forward network with asingle hidden layer made of suﬃciently many units is able toimplement any Boolean function between input layer andoutput.
The choice to use perceptron like networks for problem
of information theory was already proposed by Hosaka
et al.15) They used a simple perceptron to investigate a lossy
compression scheme. One of the most interesting feature of
their work was the use of the following non-monotonic
transfer function for the perceptron,1;jxj  k,fk ðxÞ ¼
ð1Þ
1; jxj > k,where k is a real parameter, controlling the bias of the output
sequence. This choice of a non-monotonic transfer function
was inspired by previous well known results within themachine learning community such as the improved storage
capacity achieved by non-monotonic networks. They choose
this modiﬁed version of a reversed wedge perceptron (seeref. 19 for a description of those networks) for several
reasons. The ﬁrst one was motivated by the need to be able
to control the bias of the output sequence easily (which isachieved by tuning the parameter k). The second reason was
motivated by the claim that a zero Edwards–Anderson (EA)
order parameter is needed, thus reﬂecting optimal compression within the codeword space (meaning that codewords areuncorrelated in the codeword space). The use of eq. (1)ensures mirror symmetry [ fk ðxÞ ¼ fk ðxÞ] and is likely togive rise to a zero EA order parameter (see ref. 15).
Subsequently, non-monotonic tree-like perceptrons weresuccessfully used in a lossy compression scheme and error
correcting code scheme using the same kind of nonmonotonic transfer function.6,18) This paper uses the same
networks, which are all derived from the general architecture
given by Fig. 1.
In each of these networks, the coupling vector s is split
into s ¼ ðs1 ; . . . ; sl ; . . . ; sK Þ where each sl ¼ ðs1l ; . . . ; sil ; . . . ;sN=K
Þ is a N=K-dimensional binary vector of Ising variables
l(i.e., 1 elements). In the same way, the input vector x ¼
ðx1 ; . . . ; xl ; . . . ; xK Þ,  2 f1; . . . ; Mg is also made of N=Kdimensional binary vector xl ¼ ðx1l ; . . . ; xil ; . . . ; xN=K;l Þ ofIsing variables. The output of the network is then given by
the scalar y which is also 1. The sgn function denotes thesign function taking 1 for x  0 and 1 for x < 0. We use
the Ising expression (bipolar expression) f1; 1; g insteadof the Boolean expression f0; 1; þ ðmod 2Þg to simplify
calculation. Consequently, the Boolean 0 is mapped onto 1
in the Ising framework while the Boolean 1 is mappedto 1. This mapping can be used without any loss ofgenerality. We investigate three diﬀerent networks which
are given by the followings:(I) Multilayer parity tree with non-monotonic hidden units(PTH).
!
rﬃﬃﬃﬃﬃ
KYKy ðsÞ s l xl :
fk
ð2Þ
N
l¼1
(II) Multilayer committee tree with non-monotonic hidden units (CTH).
"rﬃﬃﬃﬃﬃ#!
KXKs l xly ðsÞ  sgn
fk
:
ð3Þ
N
l¼1
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 non-monotonic hidden units in the sequel.
(III) Multilayer committee tree with a non-monotonic
output unit (CTO).
"rﬃﬃﬃﬃﬃ#!
rﬃﬃﬃﬃﬃ K
1X
Ky ðsÞ  fk
s l xl
sgn
:
ð4Þ
K l¼1
N
3.

Frameworks

3.1 Error correcting codes using multilayer perceptrons
In this section we show how non-monotonic tree-likeperceptron can be used in an error correcting code scheme.
In a general scheme, an original message s0 2 f1; 1gN of
size N is encoded into a codeword y0 2 f1; 1gM of size M
by some encoding device. The aim of this stage is too add
redundancy into the original data. Therefore, we necessarily
have M > N. Based on this redundancy, a proper decoder
device should be able to recover the original data even if itwere corrupted by some noise in the transmission channel.
The quantity R ¼ N=M is called the code rate and evaluates
the trade-oﬀ between redundancy and codeword size. The

034802-2#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

y0=-1

1-r

y=-1

r
p

y0=1

y=1

1-p

Fig. 2. The binary asymmetric channel (BAC).

Channel noise

s

0

y0

Original
message(size N)

Codeword(size M)ys

Receivedmessage(size M)

Estimatedmessage(size N)+

Fig. 3. Layout of the error correcting code scheme.

K. MIMURA et al.

ðx1 ; . . . ; x ; . . . ; xM Þ which are drawn independently anduniformly on f1; 1g. This will play the role of thecodebook. The original message s0 is used as the coupling
vector of the network. Then, each input vector x is fed
sequentially into the network generating a corresponding
scalar y0 at the output of the network ﬁnally resulting in a
M-dimensional vector y0 . This gives us the codeword to feed
into the channel.
The use of random input vectors is known to maximize
the storage capacity of perceptron’s network and since eachy0 is computed using the whole set of original bits s0 ,redundancy is added into the codeword. This makes suchkind of scheme promising for error correcting task. A formal
decoder should be able to decode the received corrupted
message y by maximizing the posterior probability pðs j yÞ,that iss^  argmax pðs j yÞ:
ð7Þ
s2f1;1gN

codeword y0 is then fed into a channel where the bits are
subject to some noise. The received corrupted message
y 2 f1; 1gM (which is also M dimensional) is then decodedusing its redundancy to infer the original N dimensional
message s0 . In other words, in a Bayesian framework, one
try to maximize the following posterior probability,Pðs j yÞ / Pð y j sÞPðsÞ:ð5Þ

As data transmission is costly, generally one wants to be able
to ensure error free transmission while transmitting the lesspossible bits. In other words, one wants to ensure error freetransmission keeping the code rate as close as possible to the
Shannon bound.
In this paper we assume that the original message s0 is
uniformly distributed on f1; 1gN and that all the bits are
independently generated so that we havePðs0 Þ ¼

1
:
2N

ð6Þ

The channel considered is the binary asymmetric channel(BAC) where each bit is ﬂipped independently of the otherswith asymmetric probabilities. If the original bit fed into thechannel is 1, then it is ﬂipped with probability r. Conversely,
if the original bit is 1, it is ﬂipped with probability p.
Figure 2 shows the BAC properties. The binary symmetricchannel (BSC) corresponds to the particular case wherer ¼ p.
Finally, the corrupted message y is received at the outputof the channel. The goal is then to ﬁnd back s0 using y. The
state of the estimated message is denoted by the vector s.
The general schematic outline of the scheme is shown in
Fig. 3. From Fig. 2 we can easily derived the following
conditional probability,Pð y j y0 Þ ¼

1 yþ ½ð1  r  pÞy0 þ ðr  pÞ ;22

where we make use of the notations y0 ¼ ð y10 ; . . . ; y0 ; . . . ;1MyM
0 Þ, y ¼ ð y ; . . . ; y ; . . . ; y Þ. Since we assume that thebits
independently, we deduce Pð y j y0 Þ ¼
QM are ﬂipped
0
¼1 Pð y j y0 Þ. To encode the original message s intoa codeword y0 , we make use of the non-monotonic treelike parity machine or committee machine neural networks
already introduced. We prepare a set of M input vectors

To keep notation as general as possible, as long as
explicit use of the encoder is not necessary in computations, we will denote the transformation perform on thevector s by therespective tree-like perceptrons using thepﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
notation F k ð K=N sl xl Þ. Here F k takes a diﬀerent
expression for the three diﬀerent types of network and thisnotation means all encoders depends on a real thresholdparameter k.
Since the relation between an arbitrary message s and thecodeword fed into the channel is deterministic, for any s, we
can write
(
"
M
Y
1 y
þ
Pð y j sÞ ¼
ð1  r  pÞ
2
2
¼1
!
#)
rﬃﬃﬃﬃﬃK
sl xl þ ðr  pÞ :
 Fk
N
We ﬁnally get the explicit expression of the joint probabilityof the model as
(
"
M
1 Y
1 y
þ
Pð y; sÞ ¼ N
ð1  r  pÞ
2 ¼1 2
2!
#)
rﬃﬃﬃﬃﬃK
sl xl þ ðr  pÞ :
ð8Þ
 Fk
N
The typical performance of this scheme was alreadystudied using the Replica Method (RM)6) and it was shownthat each of the three proposed network can reach the
optimal Shannon bound at the inﬁnite codeword length limit(when N ! 1 and M ! 1 while the code rate R is kept
ﬁnite) under some speciﬁc condition.
The PTH and the CTH were shown to reach the Shannon
bound for any number of hidden units K (any odd numberof hidden units in the case of the CTH) if the thresholdparameter k of the non-monotonic transfer function isproperly tuned. The CTO was shown to reach the Shannon
bound when its number of hidden units K becomes inﬁnite
and with a properly tuned threshold parameter k only.
3.2 Lossy compression using multilayer perceptrons
In this section we introduce the framework of lossy datacompression21) and how non-monotonic tree-like perceptrons can be used for this purpose.

034802-3#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

y

F

s

G

y

Original
message

Encoder

Codeword

Decoder

DecodedmessageFig. 4. Rate distortion encoder and decoder.

Let y be a discrete random variable deﬁned on a sourcealphabet Y. An original source message is composed of M
random variables, y ¼ ð y1 ; . . . ; yM Þ 2 Y M , and compressed
into a shorter expression. The encoder compresses theoriginal message y into a codeword s, using the transformation s ¼ F ð yÞ 2 S N , where N < M. The decoder maps
this codeword s onto the decoded message y^ , using thetransformation y^ ¼ GðsÞ 2 Y^ M . The encoding/decoding
scheme can be represented as in Fig. 4. In this case, thecode rate is deﬁned by R ¼ N=M. A distortion function d is
deﬁned as a mapping d: Y  Y^ ! Rþ . For each possible^ it associates a positive real number. In most ofpair of ð y; yÞ,the cases, the reproduction alphabet Y^ is the same as thealphabet Y on which the original message y is deﬁned.
Hereafter, we set Y^ ¼ Y, and we use the Hamming
distortion as the distortion function of the scheme. Thisdistortion function is given by^0; y ¼ y,^ ¼
dð y; yÞð9Þ^1; y 6¼ y,P ^so that the quantity dð y; y^ Þ ¼ M
¼1 dð 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/decoding process. The prob^ ¼ability of error distortion can be written E½dð y; yÞP½ y 6¼ y^ where E represents the expectation. Therefore,
the distortion associated with the code is deﬁned 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 deﬁned a rate
distortion pair ðR; DÞ and we said that this pair is achievable
if there exist a coding/decoding scheme such that whenM ! 1 and N ! 1 (note that the rate R is kept ﬁnite), we
have 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 ! 1 and
N ! 1.
The optimal compression performance that can beobtained in the framework of lossy compression is givenby the so-called rate distortion function RðDÞ which gives
the best achievable code rate R as a function of D (Shannon
bound for lossy compression). However, despite the fact thatthe best achievable performance is known, as in the error
correcting code case, no clues are given about how toconstruct such an optimal compression scheme.
In this paper we assume that the original message
y ¼ ð y1 ; . . . ; y ; . . . ; yM Þ is generated independently by an
identically biased binary source, so that we can easily write
the corresponding probability distribution,
P½ y ¼ pð y  1Þ þ ð1  pÞð y þ 1Þ;

ð10Þ

where p corresponds to the bias parameter. The encoder issimply deﬁned as follows:F ð yÞ  argmin dð y; Gð^sÞÞ:ð11Þ
s^ 2f1;1gN

K. MIMURA et al.

Next, to decode the compressed message s we make useof the already introduced tree-like perceptrons. As in theerror correcting code scheme, we prepare a set of M input
vectors ðx1 ; . . . ; x ; . . . ; xM Þ which are drawn independently
and uniformly on f1; 1g. This will play the role of thecodebook. The compressed message s is used as the coupling
vector of the network. Then, each input vector x is fed
sequentially into the network generating a corresponding
scalar y^ at the output of the network ﬁnally resulting in a
M-dimensional vector y^ . This gives us the reconstructedmessage which should satisﬁes E½ð1=MÞdð y; y^ Þ  D where
D is the desired ﬁdelity criterion which measure the amountof error between the reconstructed message y^ and theoriginal message y.
To keep notation as general as possible, as long as explicit
use of the decoder is not necessary in computations, we willagain denote the transformation perform on the vector s
by therespective tree-like perceptrons using the notationpﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
F k ð K=N sl xl Þ.
The encoding phase can be viewed as a classicalperceptron learning problem, where one tries to ﬁnd theweight vector s which minimizes the distortion function
dð y; y^ Þ for the original message y and the random input
vector x. The vector s which achieve this minimum gives
us the codeword to be send to the decoder. Therefore, inthe case of a lossless compression scheme (i.e., D ¼ 0),
evaluating the rate distortion property of the present scheme
is equivalent to ﬁnding the number of couplings s which
satisﬁes the input/output relation x 7 ! y . In other words,
this is equivalent to the calculation of the storage capacity of
the network.22,23)
The typical performance of this scheme was alreadystudied using the Replica Method (RM)18) and it was shownthat each of the three proposed network can reach the
optimal Shannon bound at the inﬁnite codeword length limit(when N ! 1 and M ! 1 while the code rate R is kept
ﬁnite) under some speciﬁc condition.
The PTH and the CTH were shown to reach the Shannon
bound for any number of hidden units K (any odd numberof hidden units in the case of the CTH) if the thresholdparameter k of the non-monotonic transfer function isproperly tuned. The CTO was shown to reach the Shannon
bound when its number of hidden units K becomes inﬁnite
and with a properly tuned threshold parameter k only.
4.

Belief-Propagation-Based Algorithms

In this section we brieﬂy introduce the BP algorithm
and how it can be used to infer an approximation of themarginalized posterior probabilities. The BP or sum-productalgorithm is originally designed to compute exact marginalization on a factor graph which is a tree. However it is
known to give very good performance even for non tree
factor graph in various cases. For a formal introduction of
the BP algorithm, see refs. 24 and 25.
So far, the BP algorithm was already applied by Hosaka
et al. in the case of lossy compression using the simple
perceptron,20) but not in the case of the MLP. We follow thefootsteps of their work to investigate both of the BP decoder
for error correcting code and the BP encoder for lossy
compression, which are based on multilayer perceptrons. It
should be noted that we can discuss a basic BP algorithm for

034802-4#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

t þ 1. At time t þ 1, the pseudo posterior marginals is givenasXptþ1 ðs j y; fxg; Þptþ1 ðsil j y; fxg; Þ ¼

M elements

y

1

y

2

y

3

y

Μ−1

y

Μ

mμl

K. MIMURA et al.

snfsil gmμl

Cil qtil ðsil Þ
s11

sΝ/Κ
1

s1Κ

N/K elementssΝ/ΚΚFig. 5. Factor graph of the Boltzmann distribution.

error correcting codes and lossy compression at a time. For the
BP to be used, we need to have a factorizable probability
distribution. Based on the statistical mechanical frameworkused in refs. 6 and 18, the posterior probability of each case(either in the error correcting code scheme and lossy compression scheme) can be represented by a Boltzmann distribution
ð12Þ

where the expression of the function Gk; depends on thescheme considered. In Appendix A, the derivaton of the
BP-based decoders for error correcting codes are given. In
Appendix B, the BP-based encoders for lossy compression
are derived. Following from this assumption, we can write
down the factor graph representation of the Boltzmann
distribution as a bipartite graph (Fig. 5).
In the BP, it is assumed that the secondary contribution ofa single variable sil or y is small and must be neglected.
Under this assumption, the factor graph shown in Fig. 5 isregarded as having a tree-like architecture. Now let us write
down the set of messages ﬂowing from the source sequence
to the codeword and vice versa. We then have the following
equations:(rﬃﬃﬃﬃﬃ
)!
X
K

t
i
s l xl^ il ðsl Þ ¼
Gk;
N
snfsil g
!
!
N=K
K N=K
Y
Y
Y
t
i0
t
i0

i0 l ðsl Þ
i0 l0 ðsl0 Þ ; ð14Þ
i
t i
tþ1
il ðsl Þ ¼ Cil qil ðsl Þ

l0 6¼l i0 ¼1

MY0 6¼

!

^ t0 il ðsil Þ

;

ð16Þ

ð17Þ
where we have inserted back the term depending on theprior and we put pt ðsil j y; fxg; Þ ¼ ð1=2Þð1 þ mtil sil Þ. Detailof calculation and deﬁnitions both tk;l and Gtk;l areavailable in Appendix A. The MPM estimator at time stept is given bysil ¼ sgnðmtil Þ:ð18ÞThis BP algorithm requires OðN Þ operations for each step.
2

where Hðs; y; fxgÞ denotes the relevant Hamiltonian andZð y; fxg; Þ the relevant partition function. The notation fxg
denotes the fact that the random vectors x are already ﬁxed
and known, which are random quenched variables.
In order to use the BP algorithm, this Boltzmann
distribution can be factorized such that the Boltzmann factor
can be decomposed into
(rﬃﬃﬃﬃﬃ)!
MYKs l xlexp½Hðs; y; fxgÞ ¼
Gk;
; ð13Þ
N
¼1

i0 6¼i;where Cil denotes the relevant normalization constant.
We obtain the BP-based algorithm as follows:"#
rﬃﬃﬃﬃﬃ
MX
K  t
1qtil ð1Þ
tþ1
t t
x  þ mil Gk;l þ ln t
mil ¼ tanh;
N il k;l
2 qil ð1Þ
¼1

N/K elements

exp½Hðs; y; fxgÞ;Zð y; fxg; Þ!
^ til ðsil Þ¼1

N elementspðs j y; fxg; Þ ¼

M
Y

ð15Þ

where Cil denotes the relevant normalization constantand qtil ðsil Þ denotes the prior. ^ til ðsil Þ denotes the message
received by the random variable sil from the source sequencei
bit y at time step t. tþ1
il ðsl Þ denotes the message sent by theirandom variable sl to the source sequence bit y at time step

5.

Empirical Performance

5.1 Error correcting code caseIn this section we show the results we obtain by using the
BP algorithm as a decoder of the scheme.
In the case of error correcting codes, the Edwards–
Anderson order parameter q is q ¼ 1 in the ferromagnetic
phase, implying that jhsl ij2 ¼ 1, where h i denotes theaverage with respect to y and x. This means that a simple
uniform prior can be used eﬃciently and there is no
uncertainty about the sign of sil . However, as it will be
discussed further with the lossy compression case, we
introduce a more reﬁne prior, so-called an inertia term, of thefollowing form
qtil ðsil Þ ¼ exp½sil tanh1 ðmtil Þ ;ð19Þ

where 0   < 1 denotes an amplitude of the inertia term.
Note that  is set by trial and error. This method was alreadysuccessfully applied by Murayama14) for a lossy compression scheme. In the sequel, if nothing is explicitly precised
about , then it means that we used  ¼ 0, corresponding to
the simple uniform prior.
The general procedure is as follows. In each case, thethreshold parameter k is set to the optimal theoretical value.
First, an original message s0 is generated from the uniform
distribution. Then the original message is turned into acodeword y0 using the relevant network. The codeword isthen fed into the binary asymmetric channel where it iscorrupted by noise according to the parameters p and r. The
decoder receives the corrupted codeword y at the output of
the channel. The BP is ﬁnally used to infer back the original
message s0 using the corrupted codeword y. The BP-based
decoders are shown in Appendix A.
We conducted two types of simulations. In the ﬁrst one,the number of hidden units K, the size of the original
message N, and the parameters ð p; rÞ of the BAC are kept
constant. The changing parameter is the size of the codeword
M which results in diﬀerent values for the code rate R ¼
N=M. For each value of R tested, we perform 100 runs. For
each run, we perform 100 BP iterations and the resulted

034802-5#2011 The Physical Society of Japan

J. Phys. Soc. Jpn. 80 (2011) 034802

FULL PAPERS

Fig. 6. Empirical performance of the BP-based decoder for error
correcting codes using the PTH with K ¼ 1 (solid) and K ¼ 3 (dashed).
We set p ¼ 0:1, r ¼ 0:2, and  ¼ 0 (set by trial and error) and used N ¼
1000 (for K ¼ 1) and N ¼ 999 (for K ¼ 3). The vertical line represents the
Shannon bound.

estimated message s is compared with the original one
s0 using the overlap value ð1=NÞs s0 . The code rate isplotted against the mean value of the overlap. The author are
well aware that in general, information theorists plot theperformance of an error correcting code scheme using error
probability plot in logarithmic scale. However, the present
BP calculations still requires a computational cost of orderOðN 2 Þ which prevent such drawing to be feasible. On top of
that, the author believes that the main interest of the present
schemes at the present state of research is from a theoreticalpoint of view rather than a practical point of view. The
performance plot intends to give an general idea about
the typical performance obtained using the BP with theseschemes but does not aim at discussing possible practicalimplementation of these schemes. We believe the performance exhibited by these schemes at the present time to be
too limited to be worth such discussion.
In the second type of experiment, we try to shed light on
the structure of the solution space. For this purpose, we ﬁx
the value of K; N; M; p; r and generate an original message
s0 . We let run the BP algorithm and get a estimated message
s after 100 iterations. Then we keep the same original
message and let run the BP again but with diﬀerent initialvalues. After 100 iterations we get another estimatedmessage s0 . We perform the same procedure 30 times andwe calculate the average overlap ð1=NÞs s0 between all theobtained estimated messages. Next we generate a new
original message s0 and do the same procedure for 50
diﬀerent original messages. We ﬁnally plot the obtained
overlap using histograms, thus reﬂecting the distribution of
the solution space.
5.1.1 Parity tree with non-monotonic hidden units (PTH)
We show the results obtained for the PTH with K ¼ 1
and 3 hidden units in Fig. 6. The vertical line represents
the Shannon bound, that is the theoretical limit for
which decoding is still successful (i.e., overlap is 1). The
average overlap for 100 trials is plotted. While the Shannon
bound gives a theoretical optimal code rate of R 0:4,
in this case for K ¼ 1, the performance of the BP starts
to deteriorates rapidly for R > 0:25. This shows limitationof the BP performance. We tested several conﬁguration

K. MIMURA et al.

with diﬀerent value for p and r (BSC case and Z channelcase), and the general tendency is always the same. Far
from the Shannon bound, the performance deteriorates
rapidly.
Next the same experiment with K ¼ 3 hidden units
shows that the BP fails completely to decode the corrupted
codeword. The average overlap is 0 even for low value of R.
We always got the same results for any value of p and r. In
fact, for any K > 1, it seems that the BP always fails toconverge to any relevant solution. This result is surprisingand might indicates that the number of suboptimal states is
so important that this prevent the BP to work.
Then we try to investigate the structure of the solution
space. We plot the histograms of the overlap of the solutions
obtained using the BP (when K ¼ 1) in Fig. 7(a). In thiscase, we see that the BP converges to two diﬀerent solutions
with opposite sign which corresponds to s0 . This is normal
and comes from the mirror symmetry of the function fk . In
this case the solution space is simple, with two dominant
attractor given by s0 and s0 .
Then we perform the same experiment but with K ¼ 3
and N ¼ 102. Results are plotted in Fig. 7(b). We obtain a
Gaussian like distribution centered on 0. This means that thesolution given by the BP are almost uncorrelated between
each others. They do not correspond to any relevant solution
and the empirical overlap is almost 0. We then conduct thesame experiment keeping the code rate unchanged but for
an original message of 1000 bits. Results are shown in
Fig. 7(c). The distribution becomes sharper, centered on 0,
meaning that the solutions given by the BP are completely
uncorrelated. The number of suboptimal states becomes verylarge and the BP completely fails to converge to a relevant
solution.
To conclude the case of the PTH, we can say that for
K ¼ 1, the BP converges but with performance far frombeing Shannon optimal. For K > 1, the BP completely fails.
This is probably due to a rise of suboptimal states whenusing more than 1 hidden unit.
5.1.2

Committee tree with non-monotonic hidden units(CTH)
We show the results obtained for the CTH with K ¼ 3
hidden units in Fig. 8(a). We do not show the result for
K ¼ 1 because in this case, the CTH is equivalent to thePTH. The vertical line represents the Shannon bound. The
average overlap for 100 trials is plotted.
In this case it is interesting to note that for  ¼ 0 and
R < 0:15, the BP fails to properly recover the original
message but still seems to converge to some meaningfulstate. The average overlap is around 0.75 but never reaches
1. This is probably due to local suboptimal attractors in thesolution space. Adding a perturbation by inserting a non zeroinertia term seems to be a good way to escape those
suboptimal states and the best performance are obtained for around 0.45. However, for R  0:15 whatever the value 
takes the performance quickly deteriorates. So the performance are very far from being optimal and suggest that thebigger the code rate is, the larger the number of suboptimal
states are.
We then conduct the exact same experiment but for
K ¼ 5. The results are shown in Fig. 8(b) and are almost

034802-6#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

K. MIMURA et al.

(a)

(a)

(b)

(b)

(c)

(c)

Fig. 7. Overlap of the solutions given by the BP-based decoder for error
correcting codes using the PTH with R ¼ 0:25, p ¼ 0:1, r ¼ 0:2 and  ¼ 0.
(a) K ¼ 1 and N ¼ 1000. The empirical overlap with the original message
is 0.97. (b) K ¼ 3 and N ¼ 102. The empirical overlap with the original
message is 0.08. (b) K ¼ 3 and N ¼ 1002. The empirical overlap with theoriginal message is 0.03.

identical to the results obtain for K ¼ 3. We then make acomparison of the best performance obtained using the CTH.
Results are shows in Fig. 8(c).
The best performance are obtain for K ¼ 1. Increasing thenumber of hidden units clearly yields poorer performance.
This is an interesting phenomenon and the only explanationis that the number of hidden units have a critical inﬂuenceand the solution space structure. While theoretically any
number of hidden units should be able to yield optimal
performance, the BP clearly gives bad results for K > 1. In asimilar way as the study we have introduced in the ﬁrst partof this paper. It is very likely that the intrinsic structure of

Fig. 8. Empirical performance of the BP-based decoder for error
correcting codes using the CTH with p ¼ 0:1 and r ¼ 0:2. The verticalline represents the Shannon bound. (a) K ¼ 3 and N ¼ 999. The dashed line
is for  ¼ 0, the dotted line is for  ¼ 0:45. (b) K ¼ 5 and N ¼ 1000. The
dashed line is for  ¼ 0, the dotted line is for  ¼ 0:45. (c) K ¼ 1 (solid),
K ¼ 3 (dashed) and K ¼ 5 (dotted) hidden units. We set N ¼ 1000 for
K ¼ 1; 5 and N ¼ 999 for K ¼ 3. We chose  ¼ 0 for K ¼ 1 and  ¼ 0:45
for K ¼ 3; 5, which are set by trial and error.

MLPs is at the origin of this ill behavior. The number ofhidden units seems to play a critical role in the organizationof the solution space, and probably give rise to somecomplex geometrical features.
Then we try to investigate the structure of the solution
space. First, we plot the histograms of the overlap of thesolutions obtained using the BP with K ¼ 3, N ¼ 999, and ¼ 0 in Fig. 9(a). Then we plot the histograms of theoverlap of the solutions obtained using the BP with K ¼ 3,
N ¼ 999, and  ¼ 0:45 in Fig. 9(b).

034802-7#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802(a)K. MIMURA et al.

Fig. 10. Empirical performance of the BP-based decoder for error
correcting codes using the CTO with K ¼ 2 (solid), K ¼ 3 (dashed), and
K ¼ 5 (dotted). We set p ¼ 0:1, r ¼ 0:2, and  ¼ 0 (set by trial and error)
and used N ¼ 1000 (for K ¼ 2 and 5), N ¼ 999 (for K ¼ 3). The verticalline represents the Shannon bound.

(b)
Fig. 9. Overlap of the solutions given by the BP-based decoder for error
correcting codes using the CTH with K ¼ 3, N ¼ 999, M ¼ 6660, R ¼
0:15,  ¼ 0, p ¼ 0:1, and r ¼ 0:2. (a)  ¼ 0. The empirical overlap withthe original message is 0.74. (b)  ¼ 0:45. The empirical overlap with theoriginal message is 0.99.

For  ¼ 0, we obtain seven peaks. Two tall peaks at1=3, one peak at 0, and four small peaks at 2=3 and 1.
The peaks located at 1 and 1=3 corresponds to successful
decoding and reﬂect the possible combination of decoded
messages when K ¼ 3. Indeed, because of the mirror
symmetry in the CTH network, any combination of s0l
gives the same output. We therefore have a inherent
indetermination on the original message, which can beeasily removed by adding some simple header to thecodeword.
The two small peaks around 2=3 corresponds to a partial
success in decoding. Indeed, further investigation showedthat those peaks correspond to codewords where two of thethree s0l vectors have been successfully retrieved but the lastvector was not. This means that the BP remained trapped insome local attractor, which probably depends on the initialvalues used by the BP. The interesting fact is that it aﬀects
only partially the BP performance in this case, showing thatfor the CTH the BP dynamics of each sl is independent to theothers to some extent. Finally, the peak around 0 reﬂect acompletely unsuccessful decoding. This explains the averageoverlap found of 0.74.
In the K ¼ 3 system, for a given original message s0 ,eight messages fðs01 , s02 , s03 Þ, ðs01 , s02 , s03 Þ, ðs01 , s02 , s03 Þ, ðs01 ,s02 , s03 Þ, ðs01 , s02 , s03 Þ, ðs01 , s02 , s03 Þ, ðs01 , s02 , s03 Þ,ðs01 ; s02 ; s03 Þg , Sðs0 Þ, which includes the original message s0 ¼ ðs01 ; s02 ; s03 Þ, are mapped into a same codeword. So

an additional K bit information is necessary to specify theoriginal message from the set Sðs0 Þ. For instance, it is oneof the additional information to add 1 to each block l as
s0l 7 ! ð1; s0l Þ to specify the original message (the length of
this information is negligible than the length of the original
message). If the BP decoder correctly estimates the original
message s0 , the estimated message is identical to one of theelement of the set Sðs0 Þ with equiprobability. Therefore,
when the BP decoder estimates correctly, the histgram
exhibits only four peaks located at 1 (probability 1/8) and1=3 (probability 3/8).
The case where  ¼ 0:45 on the other hand, exhibits only
four peaks located at 1 and 1=3. Therefore this meansthat decoding is always successful in this case as conﬁrmedby the average overlap of 0:99. This result shows that using
a non-zero inertia term can be an eﬃcient way of avoiding
sub-optimal states by adding a small perturbation to the BP
dynamics.
To conclude for the CTH, it is very clear that using a
number of hidden unit greater than 1 is at the origin of somestructural changes of the solution space, which provokes adramatic performance drop. For K ¼ 1, successful decoding
is ensured until R ¼ 0:25 while for K ¼ 3, successful
decoding is ensured until R ¼ 0:15 only. However, between
K ¼ 3 and K ¼ 5, we observe no substantial change. It
seems that as R increases, the suboptimal states’ basin of
attraction quickly becomes very large compared to the
optimal solution one. The inﬂuence of the number ofhidden units on the solution space geometry remains to beinvestigated in a future work.
5.1.3

Committee tree with a non-monotonic output unit
(CTO)
We show the results obtained for the CTO with K ¼ 2, 3,
and 5 hidden units in Fig. 10. We do not show the resultfor K ¼ 1 because the CTO cannot be deﬁned in thiscase. The vertical line represents the Shannon bound. The
average overlap for 100 trials is plotted. For K ¼ 2 the BP
successfully decodes the corrupted codeword until R ¼ 0:17
only and beyond this value the performance gradually
decreases. Compared to the PTH/CTH with K ¼ 1, the CTO
performance are poorer. However, this is not very surprisingbecause as mentioned during the analytical study of the CTO

034802-8#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

K. MIMURA et al.

indicates suboptimal states. However, here there is no
particular suboptimal states as in the case when K ¼ 2. Thisparticularity is interesting and remains to be investigated.
To conclude the case of the CTO, we can say that the BPreaches optimal performance for K ¼ 3 but decoding is still
far from being Shannon optimal. However, as the analytical
study already mentioned, the CTO is expected to yield
Shannon performance when using an inﬁnite number ofhidden units so it is a little bit hard to explain the results ofthis section. Nevertheless, one may expect the performanceto get better and better a K increases but this is not thecase as denoted by the case when K ¼ 5. As for the othernetworks, it is very likely that the solution space exhibits
strange geometrical features for K > 1 (explaining the riseof suboptimal states), preventing the BP to converge
properly for large values of K.

(a)

5.2 Lossy compression caseIn this section we show the results we obtained by using
the BP algorithm as an encoder of the scheme.
In the case of lossy compression, the Edwards–Andersonparameter q vanishes as discussed in the refs. 15 and 18,
implying that jhsl ij2 ¼ 0 (where h i denotes the averagewith respect to y and x). This means that it is not possible
to determine the most probable sign of sil . To avoid thisuncertainty we again introduce a particular prior of the form(b)Fig. 11. Overlap of the solutions given by the BP-based decoder for error
correcting codes using the CTO with K ¼ 2, N ¼ 1000, M ¼ 4000, R ¼
0:25,  ¼ 0, p ¼ 0:1, and r ¼ 0:2. (a) K ¼ 2 and N ¼ 1000. The empirical
overlap with the original message is 0.76. (b) K ¼ 3 and N ¼ 999. The
empirical overlap with the original message is 0.63.

case, the CTO is expected to reach the Shannon bound for
an inﬁnite number of hidden units only. The fact that we
get suboptimal performance for ﬁnite K is therefore notsurprising. For K ¼ 3, the average performance is better anddecoding is successful until R ¼ 0:2. In this case, it is worth
using an extra unit. However, for K ¼ 5, the performance
deteriorates and we get poorer performance than K ¼ 1.
Nonetheless, the overall performance is still better than the
CTH with the same number of hidden units.
Then we try to investigate the structure of the solution
space. We plot the histograms of the overlap of the solutions
obtained using the BP with K ¼ 2 and N ¼ 1000 in
Fig. 11(a). We obtain three sharp peaks at 1 and 0 andtwo small peaks around 2=3. The three sharp peaks
correspond to successful decoding. As in the CTH case,their positions correspond to the possible combination ofs0l . However, the other two small peaks corresponds tosuboptimal states (the average overlap is 0.76) and it isunclear what the value 2=3 denotes. It might corresponds
to some particular local attractor which should be investigated in the future.
Next we plot the histograms of the overlap of the solutions obtained using the BP with K ¼ 3 and N ¼ 999 in
Fig. 11(b). For K ¼ 3, we obtain two sharp peaks at 1 anda rather ﬂat distribution connecting them (with a small
concentration around 0). The two sharp peaks correspondto successful decoding, while the rest of the distribution

qtil ðsil Þ ¼ exp½sil tanh1 ðmtil Þ ;ð20Þ

where 0   < 1 denotes an amplitude of the inertia term.
Note that  is set by trial and error. This method was alreadysuccessfully applied by Murayama.14)
The general procedure is as follows (in each case, thethreshold parameter k is set to the optimal theoretical value,
see ref. 18). First, an original message y is generated fromthe distribution (10). Then the original message is turned
into a codeword s using the BP-based algorithms which
are shown in Appendix B. The codeword is subsequently
decoded into y^ using the proper tree-like multilayer
perceptron decoder network. The distortion between the
decoded message y^ and the original message y is thencomputed.
We conducted two types of simulations. In the ﬁrst one,the number of hidden units K, the size of the codeword N,
and the bias parameters p of the distribution (10) are kept
constant. The changing parameter is the size of the original
message M which results in diﬀerent values for the code rate
R ¼ N=M. For each value of R tested, we perform 100 runs.
For each run, we perform 35 BP iterations and the resulted
estimated codeword s is then decoded into y^ . The distortion
between y^ and y is then computed. The code rate is plottedagainst the mean value of the distortion.
The second type of experiment is exactly the same as in
the error correcting case. We ﬁx the value of K; N; M; p andgenerate an original message y. We let run the BP algorithm
and get a codeword s after 35 iterations. Then we keep thesame original message and let run the BP again but with
diﬀerent initial values. After 35 iterations we get anothercodeword s0 . We perform the same procedure 30 times
and we calculate the average overlap ð1=NÞs s0 between all
the obtained codewords. Next we generate a new original
message y and do the same procedure for 50 diﬀerent

034802-9#2011 The Physical Society of Japan

J. Phys. Soc. Jpn. 80 (2011) 034802

FULL PAPERS

K. MIMURA et al.

(a)Fig. 12. Empirical performance of the BP-based encoder for lossy
compression using the PTH with K ¼ 1 and K ¼ 3 for unbiased messages(p ¼ 0:5, on the top of the ﬁgure) and biased message (p ¼ 0:8, on thebottom). Dashed lines are for K ¼ 1 and dotted lines are for K ¼ 3. We
used N ¼ 1000 for K ¼ 1, and N ¼ 999 for K ¼ 3. The inertia term
 ¼ 0:45 was set by trial and error. The solid lines give the Shannon bound.
The top one is for p ¼ 0:5, the bottom one is for p ¼ 0:8.

original messages. We ﬁnally plot the obtained averageoverlap using histograms, thus reﬂecting the distribution of
the codeword space.
5.2.1 Parity tree with non-monotonic hidden units (PTH)
We show the results obtained for the PTH with K ¼ 1 and3 hidden units for unbiased message (i.e., p ¼ 0:5) an biased
message with p ¼ 0:8 in Fig. 12. The solid line represents
the rate distortion function corresponding to the Shannon
bound, that is the lowest achievable distortion for a given
code rate R. The average distortion for 100 trials is plotted.
For K ¼ 1, the results are quite far from the Shannon
bound for large code rate but approaches it for small ones
(for both p ¼ 0:5 and 0.8). We ﬁnd the same results asin Hosaka et al.20) Then, the same tendency can be shownfor biased messages with p < 0:5 but in those cases, forsymmetry reasons, we should use fk as a transfer function
which gives slightly diﬀerent BP equations (some signs
change). Hence, for simplicity we restrict the present study
to biased messages with p > 0:5.
The result for unbiased message and K ¼ 3 are extremely
bad and the BP does not seems to converge to any relevant
codeword. This is surprising. On top of that, while theperformance are also poorer than K ¼ 1 for biased
messages, it is not as extreme as for the unbiased case.
The reasons for such a behavior are not very clear. The
codeword space structure is again clearly aﬀected whenmore than one hidden unit is used and is likely to perturb
the BP dynamics. Bias in the original message seems to beanother factor to take into account.
Then we try to investigate the structure of the codeword
space. We plot the histograms of the overlap of thecodewords obtained using the BP for K ¼ 1, N ¼ 100,
R ¼ 0:4, and p ¼ 0:5 in Fig. 13(a). In this case, it isinteresting to note that despite one might believe, the BP
does not converge to two diﬀerent solutions. As discussed inref. 18, for K ¼ 1, we have at least two optimal codewords
s. Therefore, one might expect to see two peaks
concentrated around 1 but this is not the case. There are
two very small peaks around 1 and one large peak with its(b)Fig. 13. Overlap of the solutions given by the BP-based encoder for lossy
compression using the PTH with R ¼ 0:4 and  ¼ 0:45 which is set by trial
and error. The Shannon bound is 0.15 for p ¼ 0:5 and 0.057 for p ¼ 0:8.
(a) K ¼ 1, N ¼ 100, and p ¼ 0:5. The empirical distortion over the trial is0.21. (b) K ¼ 1, N ¼ 1000, and p ¼ 0:5. The empirical distortion is 0.19.

center around 0. This implies that there are many codewords
completely uncorrelated which share very similar distortion
properties. To conﬁrm this conjecture, we perform exactly
the same experiment but with a larger codeword size
N ¼ 1000. Results are shown in Fig. 13(b).
This time, the small peaks around 1 completely vanish
and we have a Gaussian like distribution centered on 0.
This conﬁrms the fact that there is a very large amount of
uncorrelated codewords sharing the same distortion properties. This is a surprising result.
We perform the same type of experiment but with K ¼ 3.
We ﬁrst consider unbiased messages (p ¼ 0:5). We show theresult for N ¼ 102 only because there is no major changewith larger value of N in this case. Results are plotted inFig. 14(a). We obtain a Gaussian like distribution centeredon 0. This means that the solution given by the BP arealmost uncorrelated between each others. This time they
do not correspond to any relevant solution as indicated by
the empirical distortion which is close to 0:5 meaning
completely random codewords. It seems that for K > 1 andfor unbiased messages (p ¼ 0:5), the number of suboptimal
states becomes very large and the BP fails to converge to any
relevant codeword.
Then we consider biased messages (p ¼ 0:8). Figure 14(b)shows the results for N ¼ 102. In this case we have two
peaks located at 1=3 linked by a rather high plateau andtwo small peaks at 1. The peaks location corresponds to034802-10#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

K. MIMURA et al.

(a)Fig. 15. Empirical performance of the BP-based encoder for lossy
compression using the CTH with K ¼ 1, 3, and 5 for unbiased messages(p ¼ 0:5, on the top of the ﬁgure) and biased message (p ¼ 0:8, on thebottom). Dashed lines are for K ¼ 1, dotted lines are for K ¼ 3 and dashdotted lines are for K ¼ 5. We used N ¼ 1000 for K ¼ 1 and 5, and
N ¼ 999 for K ¼ 3. The inertia term  ¼ 0:4 was set by trial and error. The
solid lines give the Shannon bound. The top one is for p ¼ 0:5, the bottom
one is for p ¼ 0:8.

(b)

(c)
Fig. 14. Overlap of the solutions given by the BP-based encoder for lossy
compression using the PTH with R ¼ 0:4 and  ¼ 0:45 which is set by trial
and error. The Shannon bound is 0.15 for p ¼ 0:5 and 0.057 for p ¼ 0:8.
(a) K ¼ 3, N ¼ 102, and p ¼ 0:5. The empirical distortion is 0.43. (b) K ¼ 3,
N ¼ 102, and p ¼ 0:8. The empirical distortion is 0.118. (c) K ¼ 3, N ¼ 999,
and p ¼ 0:8. The empirical distortion is 0.101.

the 2K possible combinations of codewords ensured by the
structure of the network (discussed in ref. 18). This meansthat in many cases the BP converge to one of this possible
2K combination. However the rather high plateau centeredon 0 shows that the BP converges many time to uncorrelated
codewords. This means that on top of the 2K codewords
sharing the same distortion properties, we have a large
number of uncorrelated codewords which share rather
similar distortion properties. We decide to investigate thesame case but with a larger value of N. Figure 14(c) shows
the result for N ¼ 999. This time, the peaks completely
vanish and we obtain a Gaussian like distribution centeredon 0. The empirical distortion obtained 0.101 shows that the
BP converges to a relevant solution (even if not optimal).
This shows that as N gets larger, the number of uncorrelated
codewords sharing similar distortion properties becomes
extremely large. This is an interesting feature. However, theresults are not Shannon optimal and as K increases, theresults for biased messages becomes smoothly worse andworse. Nevertheless, the reason why the BP fails to work forunbiased messages when K > 1 is still unclear.
To conclude the case of the PTH, we can say that for
K ¼ 1, the BP converges but with relatively poor performance. The codeword space exhibits an interesting structure,
showing that many uncorrelated codewords share very
similar properties. As the codeword length gets larger, thenumber of these codewords sharing very similar distortion
properties seem to increase dramatically. For K > 1, theperformance smoothly deteriorates for biased messages but
for near unbiased ones, the BP fails. This is probably due tothe rise of suboptimal states when using more than 1 hidden
unit. The geometrical structure of the codeword spaceremains to be investigated.
5.2.2

Committee tree with non-monotonic hidden units(CTH)
We show the results obtained for the CTH with K ¼ 1, 3,
and 5 hidden units for unbiased and biased messages inFig. 15. We remind that when K ¼ 1, the CTH is equivalent
to the PTH. The solid lines represent the rate distortionfunction corresponding to the Shannon bound. The average
distortion for 100 trials is plotted.
The results are quite far from the Shannon bound for large
code rate but approaches it for small ones. However, as K
increases, the performance smoothly decreases implying thatthe number of suboptimal states steadily increases with thenumber of hidden units. Nevertheless it should be noted thatfor unbiased messages, whereas the BP completely fails in
the PTH case for K > 1, this is not the case here. Anyway, in
the CTH case also, the reason for the deterioration of theperformance is clearly linked with the number of hidden units.

034802-11#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

K. MIMURA et al.

(a)

(a)

(b)

(b)
Fig. 16. Overlap of the solutions given by the BP-based encoder for lossy
compresion using the CTH with K ¼ 3, R ¼ 0:4, p ¼ 0:8, and  ¼ 0:4
which is set by trial and error. The Shannon bound is 0.14. (a) N ¼ 102. The
empirical distortion is 0.3. (b) N ¼ 1002. The empirical distortion is 0.22.

Then we try to investigate the structure of the codeword
space. We consider only K ¼ 3 because K ¼ 1 is equivalent
to the PTH. We plot the histograms of the overlap of thesolutions obtained using the BP in Fig. 16(a). In this case,for K ¼ 3, we have four peaks. Two small ones around 1
and two big ones linked by a plateau around 1=3. This is
the same situation as the PTH with K ¼ 3, p ¼ 0:8, and
N ¼ 102. The four peaks corresponds to the 2K possiblecombinations of codewords ensured by the structure of
the network (discussed in ref. 18). On the other hand, theplateau around 0 shows that there is also many codewords
completely uncorrelated which share very similar distortion
properties. To conﬁrm this conjecture, we perform exactly
the same experiment but with a larger codeword size
N ¼ 1002. Results are shown in Fig. 16(b). This time,
the peaks vanish and we have a Gaussian like distribution
centered on 0. This conﬁrm the fact that there is a verylarge amount of uncorrelated codewords sharing the same
distortion properties. We have the same surprising result as
in the PTH case.
To conclude the case of the CTH, we can say that the BP
converges but with quite poor performance. Furthermore,
as K increases, the performance smoothly deteriorates. The
codeword space exhibits an interesting structure, showingthat many uncorrelated codewords share very similar
distortion properties. As the codeword length gets larger,
the number of these codewords seems to increase dramatically. However the reasons of this performance deterioration

Fig. 17. Empirical performance of the BP-based encoder for lossy
compression using the CTO with K ¼ 2, 3, 4, and 5 for unbiased messages(p ¼ 0:5). Dashed line is for K ¼ 2, dotted line is for K ¼ 3, solid line is for
K ¼ 4 and dash dotted line is for K ¼ 5. We used N ¼ 1000 for K ¼ 2; 5,N ¼ 999 for K ¼ 3, and N ¼ 1004 for K ¼ 4. The inertia term  ¼ 0:4 was
set by trial and error. The continuous solid line (bottom) gives the Shannon
bound. (a) p ¼ 0:5. (b) p ¼ 0:8.

as K gets larger remains unclear. It is likely that the useof several hidden units induces structural change in thecodeword space and that these are responsible for the BP
bad behavior.
5.2.3

Committee tree with a non-monotonic output unit
(CTO)
We show the results obtained for the CTO with K ¼ 2, 3,
4, and 5 hidden units for unbiased messages in Fig. 17(a),where the CTO cannot be deﬁned for K ¼ 1. The continuous
solid line represents the rate distortion function corresponding to the Shannon bound. The average distortion for 100
trials is plotted. The results for unbiased messages (p ¼ 0:5)
are quite similar as in the CTH case. The best performanceis obtain for the smaller K and then smoothly deteriorates.
However, the results do not deteriorate steadily (for example
K ¼ 5 gives better performance compared to K ¼ 4).
This is probably due to the fact that the free energy is a
discontinuous function of K as shown in the ref. 18. Thisis then not surprising that the performance do not evolvesmoothly with K. On top of that, let us remind that the CTO
is expected to give the Shannon optimal performance only
for an inﬁnite number of hidden units K. So it is fair the
results are quite far from being Shannon optimal. However,as K increases, one may expect the performance to become
closer to the Shannon bound but this is not the case. This

034802-12#2011 The Physical Society of Japan

J. Phys. Soc. Jpn. 80 (2011) 034802

FULL PAPERS

shows again that a larger number of hidden units clearly
penalizes the BP performance.
Next we perform the same experiment but for biased
messages with p ¼ 0:8. The results are given in Fig. 17(b).
The results for biased messages with p ¼ 0:8 exhibits
strange behavior. The best performance for small rates
R < 0:2 is obtained for K ¼ 3 and for R > 0:2, the best
performance is given for K ¼ 4. We have some strange
jump in performance for K ¼ 2 between R ¼ 0:3 and 0.4
and for K ¼ 5 between R ¼ 0:5 and 0.6 for example. Thisis probably due to the fact that the tuning of the thresholdparameter k follows a discontinuous function of D which can
explain this kind of discontinuous jump. The results are hardto interpret but we observed that for K > 5, the generaltendency is to get worse performance. As mentioned earlier,
the CTO is expected to give Shannon optimal performance
only for an inﬁnite number of hidden units K so it is fair forthe results not to be Shannon optimal, especially for small K.
However, as K increases, one may expect the performance
to become closer to the Shannon bound but this is not thecase after K ¼ 4. This shows again that a larger number ofhidden units clearly penalizes the BP performance.
Then we try to investigate the structure of the codeword
space. We show the case when K ¼ 2 only here because theother ones are similar. We plot the histograms of the overlapof the solutions obtained using the BP for N ¼ 102 in
Fig. 18(a). In this case, we have almost the same picture asin the PTH/CTH case with K ¼ 1. Two small peaks around1 and one large plateau around 0. The small peaks
corresponds to the codewords which share exactly the same
distortion properties as ensured by the mirror symmetry of
the function fK (discussed in ref. 18). On the other hand, theplateau around 0 shows that there are also many codewords
completely uncorrelated which share very similar distortion
properties. To conﬁrm this conjecture, we perform exactly
the same experiment but with a larger codeword size
N ¼ 1000. Results are shown in Fig. 18(b). This time, thesmall peaks around 1 completely vanish and we have a
Gaussian like distribution centered on 0. This conﬁrm thefact that there is a very large amount of uncorrelated
codewords sharing the same distortion properties.
To conclude the case of the CTO, we can say that the
BP converges but with quite poor performance. On top of
that, because of the discontinuous free energy, we observe
some strange behavior like sudden jump in performance.
The CTO theoretically gives Shannon performance for an
inﬁnite number of hidden units K so one may expect theperformance given by the BP to get better and better as K
increases however this is not the case. For K > 4, we
generally get poorer and poorer performance showing one
more time that there is some intimate link between the BP
performance and the number of hidden units. Finally, as
already found for the PTH and CTH, as the codeword
length gets larger, the number of codewords sharing similar
distortion properties seems to increase dramatically. The
geometrical feature of the codeword space remains to beinvestigated.
6.

Conclusion and Discussion

We have investigated the BP algorithm as a decoder of anerror correcting code scheme based on tree-like multilayer

K. MIMURA et al.

(a)

(b)
Fig. 18. Overlap of the solutions given by the BP-based encoder for lossy
compression using the CTO with K ¼ 2, R ¼ 0:4, p ¼ 0:5, and  ¼ 0:4
which is set by trial and error. The Shannon bound is 0.15. (a) N ¼ 100. The
empirical distortion over the trial is 0.25. (b) N ¼ 1000. The empirical
distortion over the trial is 0.21.

perceptron encoder. In the same way, we have investigatedthe BP algorithm as a potential encoder of a lossy
compression scheme based on tree-like multilayer perceptron decoder. We have discussed that whether the BP cangive practical algorithms or not in these schemes. Unfortunately, the BP implementations in those kind of fully
connected networks shows strong limitation, while thetheoretical results seems a bit promising. Instead, it reveals
it might have a rich and complex structure of the solution
space via the BP-based algorithms.
While these two schemes have been shown to yield the
Shannon optimal performance theoretically (under somespeciﬁc conditions, cf. refs. 6 and 18), they lack a practicalformal decoder and encoder, respectively. The BP algorithm
has been proposed as a way to calculate the marginalized
posterior probabilities of the relevant Boltzmann factor but
exhibits poor performance preventing this kind of schemes
from being practical. The number of hidden units should be
kept as small as possible as no gain have been observed byusing several ones. While the precise reasons behind this bad
behavior are still unclear at the present time, there is no
doubt that the number of hidden units have some deep
impact onto the solution space of the considered network,
which is infered from behavior of the BP-based algorithms.
It is very probable that the existence of mirror symmetry in
the network is at the origin of the BP failure. It is also very
likely that a singular structure similar to the one studied

034802-13#2011 The Physical Society of Japan

J. Phys. Soc. Jpn. 80 (2011) 034802

FULL PAPERS

in the ﬁrst part of this paper, prevents the standard BP
algorithm to work eﬃciently. This underline the necessity toinvestigate the geometrical feature of the solution spaceof the PTH/CTH/CTO as well as the BP dynamics tounderstand why the BP does not work well when a large K isused. It would be interesting to investigate the informationgeometrical counterpart of the BP algorithm to see how wellit can performed. This remains a future topic of research.
On the other hand, as discussed in the ref. 15 and in theref. 18, the mirror symmetry seems to be a key factor toachieve Shannon performance while using perceptron likenetwork in the lossy compression case. Since we havefk ðsÞ ¼ fk ðsÞ, one would expect to get two optimal solutions(when K ¼ 1) or more (due to the possible combinations ofsl ) but this is not the case. Using a small value of N, theexpected peaks induced by the structure of the network areindeed observable but a large concentration of uncorrelated
codewords is also visible. Using a suﬃciently large N, thosepeaks completely vanish, and one will always get uncorrelated codewords, trial after trial, demonstrating that a verylarge amount of uncorrelated codewords share very similar
distortion properties. The origin of such particular spacestructure remains unclear. In the same way, the complete
failure of the BP in the case of the PTH with K > 1 remains
to be investigated. We might be able to investigate suchproblems by evaluating the complexity26) of the systems.
This is a part of our future works.

"#
qtil ð1Þ
tanh;
2 qtil ð1Þ
0 6¼
"#M
X
1
qtil ð1Þ
tþ1
1 ttanh m^ il þ ln t
mil ¼ tanh:
2 qil ð1Þ
¼1

mtþ1
il ¼ tanh

The authors would like to thank Tadaaki Hosaka for his
valuable discussions. This work was partially supported by
a Grant-in-Aid for Encouragement of Young Scientists B(No. 18700230), Grant-in-Aid for Scientiﬁc Research on
Priority Areas (Nos. 18079003, 18020007), Grant-in-Aid
for Scientiﬁc Research C (No. 16500093), and a Grant-inAid for JSPS Fellows (No. 06J06774) from the Ministryof Education, Culture, Sports, Science and Technology ofJapan.
Derivation of the BP Decoder for Error
Correcting Code Case

The sil are Ising variables, we can reparameterize theabove probabilities using their corresponding expectation
values for the random variable sil ,þ ðr  pÞ

11m^ t0 il þ ln

ðA 4Þ
ðA 5Þ

ðA 6Þ

:

Note that we put  ¼ 1.
A.1 Parity tree with non-monotonic hidden units (PTH)
In the case of the PTH F k is given by(rﬃﬃﬃﬃﬃ)!
!
rﬃﬃﬃﬃﬃ
KYKKs l xlsl xl : ðA 7Þ
fk
Fk
¼
N
N
l¼1
Applying the Taylor expansion, this can be rewritten as(rﬃﬃﬃﬃﬃ
)!
K
Y
K

sl xl
Fk
fk ð^il0 Þ;
ðA 8Þ
fk ð il þ ^il Þ
N
0
l 6¼l
 il ¼

rﬃﬃﬃﬃﬃ
K i sx ;N l il^il ¼

rﬃﬃﬃﬃﬃ
K i0 
s x0
N l ili0 6¼i

N=K
X

ðA 9Þ


0
and wepﬃﬃﬃﬃhave neglected the remaining f i;l0 j l 6¼ lg of orderOð1= N Þ. Note that this approximation is justiﬁed by thefact that we suppose N ! 1. For the same reason we apply
the central limit theorem on the ^il and ﬁnd,

^il
where
 til ¼^

rﬃﬃﬃﬃﬃ N=K
KX
N i0 6¼i

 til ; 1  qtil Þ;
N ð^
KX t 2
ðm 0 Þ :N i0 6¼i i l

ðA 10Þ

N=K

mti0 l xi0 l ;qtil ¼

ðA 11Þ

We ﬁnally get^ til ðsil Þ

1 þ m^ til sil
;
ðA 1Þ
2
1 þ mtil sil
til ðsil Þ ¼
;
ðA 2Þ
2
1 þ mtil sil
pt ðsil j y; fxg; Þ ¼
;
ðA 3Þ
2
where m^ til ; mtil ; mtil denotes the relevant expectation values
at time step t. Computing the expectation is easier thancomputing the message itself.
Using the following identity

where

1þx
¼ 2 tanh1 x;
1x

and

^ til ðsil Þ ¼

ln

M
X

In the error correcting code case, Gk; is given by(rﬃﬃﬃﬃﬃ)!
Ks l xlGk;
N((rﬃﬃﬃﬃﬃ)!
"yKN=M 1þs l xl¼2
ð1  r  pÞF k
2
N
2
#)

where

Acknowledgments

Appendix A:

K. MIMURA et al.

Ftk;il ð il Þ ¼

Z þ1 YK

2N=M Ftk;il ð il Þ

ðA 12Þ(1 yþ ð1  r  pÞ22
1 l¼1
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
  til þ zl 1  qtil
 fk  il þ ^K
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
Y t il0 þ zl0 1  qtil0

fk ^
Dzl 

l0 6¼l)yþ ðr  pÞ ;2

ðA 13Þ

expðx2 =2Þ dx
pﬃﬃﬃﬃﬃﬃ:
ðA 14Þ
2
p
ﬃﬃﬃﬃ
Using the fact that  il is of order Oð1= N Þ, we expand Ftk;ilaround 0 and get,Dx ¼

independently of the scheme and network considered,
one can already easily derived the following set of
equations,

034802-14#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

^ til ðsil Þ

2

N=M


@Ftk;il ð il Þ Ftk;il ð0Þ þ  il @ il il ¼0

K. MIMURA et al.

!
:ðA 15Þ
Finally, using (A 1) we get the expresion of m^ til as follows:@Ftk;il ð il Þ 
rﬃﬃﬃﬃﬃ @K il ¼0il
xil:
ðA 16Þ
m^ til ¼
tN
Fk;il ð0Þ
Evaluating Ftk;il ð0Þ and ½@Ftk;il ð il Þ=@ il j il ¼0 , we can
explicitly obtain m^ til .
So using (A 4), (A 5), and (A 16) iteratively until a ﬁxed
point is reached, one should be able to decode the received
corrupted codeword y and ﬁnd back the original message s0 .
However, this procedure still requires OðN 3 Þ operations so
one might want to reduce the complexity of the algorithm.
For simplicity, we suppose a uniform prior qtil hereafter.
However, the results can be easily generalized
pﬃﬃﬃﬃ for more
complex priors. Since m^ til is of order Oð1= N Þ, we have
"
#
M
X
tþ1
1 t
mil ¼ tanh
tanh m^ 0 il ;tð"til ÞU^ k;ilt
V^k;il
ð"til Þt
Uk;ilð"til Þ;ðA 27Þ

t
Vk;ilð"til Þ:Using this approximation, we getrﬃﬃﬃﬃﬃ
K  tt
x  ð"t Þ;m^ il
N il k;il ilwhere we put

ðA 28Þ

tk;il ð"til Þ ¼

KX t 2
ðm 0 Þ
N i0 6¼i i l

ðA 31Þ
For simplicity, we hereafter use the following abbreviations:

ðA 17Þ

N=K

qtl  q^ tl  ð"til Þ2 :ðA 18Þ

where
KX t 2ðm Þ ;
N i¼1 il
K=N

qtl ¼

ðA 19Þ

N=K
KX t
m ð1  ½mtil 2 Þm^ t1
ðA 20Þ
q^ tl ¼ 2
il ;N i¼1 ilrﬃﬃﬃﬃﬃ
K tm :"til ¼
ðA 21Þ
N ilP
We
P here insert the lacking term in the partial sum ( i0 6¼i
i¼1 ) of the cross term since this should be negligible forlarge N. In the same way we haverﬃﬃﬃﬃﬃ N=K
KX t t tl  ^^ tl  xil "til ;^il ¼m 0 x0^ðA 22Þ
N i0 6¼i i l i l
where
rﬃﬃﬃﬃﬃ K=N
KX t t l ¼^m x ;ðA 23Þ
N i¼1 il ilrﬃﬃﬃﬃﬃ N=K
KXt^ l ¼^
ð1  ½mtil 2 Þm^ t1
ðA 24Þ
il xil :N i¼1

Using these equations, we can rewrite Ftk;il and its
derivative as a function of "til ,@Ftk;il ð il Þ t^tðA 25Þ   Uk;il ð"il Þ;@ il il ¼0t
ð"til Þ;ðA 26Þ
Ftk;il ð0Þ  V^k;il
pﬃﬃﬃﬃ
tThen, because each "il is of order Oð1= N Þ, we approxtttt
imate fU^ k;il; V^k;ilg by fUk;il; Vk;ilg where we neglect allt
0
the terms f"il0 j l 6¼ lg, which givesðA 30Þ

il

We can then evaluate the following equations using theabove approximation,qtil ¼

t
Uk;ilð"til Þ:t
Vk;ilð"til Þpﬃﬃﬃﬃ
Then once again, because "til is of order Oð1= N Þ, we
perform the Taylor epxansion:#rﬃﬃﬃﬃﬃ "rﬃﬃﬃﬃﬃK  t
K t @tk;il ð"til Þ tx k;il ð0Þ þmm^ il
:
t
@"til
N il
N il
" ¼0

0 6¼

tþ1 2^ til :mtþ1il  ½1  ðmil Þ m

ðA 29Þtt
ð0Þ  Uk;l;
Uk;ilðA 32Þtt
ð0Þ  Vk;l;
Vk;iltk;il ð0Þ  tk;l ;t@Uk;il
ð"til Þ  ~t t  xil Uk;l ;@"til"il ¼0t@Vk;il
ð"til Þ  ~t t  xil Vk;l ;@"til"il ¼0ðA 33Þ
ðA 34Þ
ðA 35Þ
ðA 36Þ

which appear in ½@tk;il ð"til Þ=@"til j"til ¼0 . Note that because weneglect all the "til0 and use the value of the above functions
evaluated at 0 only, we can drop the index i.
So using all this results we have (we suppose a uniform
prior for simplicity),
"
#
M
X
tþ1
1
t
mil ¼ tanh
tanh ðm^ il Þ ;
"

¼1

#
rﬃﬃﬃﬃﬃ
K  t
t t
x  þ mil Gk;il ;¼ tanhN il k;l¼1
where we put

M
X

t
t 
M
X
 @k;il ð"il Þ xt :N ¼1 il
@"til
" ¼0

K
Gtk;il ðA 37Þ

ðA 38Þ

il

Neglecting small order terms, we obtain
t
t
t
M ~t
Uk;l Vk;l V~k;lUk;lKX
Gtk;il ¼
 Gtk;l :
t Þ2
N ¼1
ðVk;lðA 39Þ

We therefore obtain the approximated BP equation as
follows:"#
rﬃﬃﬃﬃﬃ
MX
K  t
1qtil ð1Þ
tþ1
t t
x  þ mil Gk;l þ ln t
mil ¼ tanh;
N il k;l
2 qil ð1Þ
¼1
ðA 40Þ
where we have inserted back the term depending on theprior. We then arrive at eq. (17). The BP algorithm is thus
ﬁnally reduced to eq. (A 40) and requires about OðN 2 Þ
operations for each step. The MPM estimator at time step t isgiven by sil ¼ sgnðmtil Þ.
In this case the BP reduces to a single recurrent equation given by (A 40), where in the case of the PTH, wehave

034802-15#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

K. MIMURA et al.

 


 K
y ð1  r  pÞ
1
1 t 2 Y
t
2
t
ðw
Uk;l
¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt ﬃ exp  ðwtþÞ
Þ½1  2Hðwtþ
exp

k;l0 Þ  2Hðwk;l0 Þ ;2 k;l2 k;l2ð1  ql Þ
l0 6¼l
K
Y
1 y
y
t
þ ðr  pÞ þ ð1  r  pÞ ½1  2Hðwtþ
k;l Þ  2Hðwk;l Þ ;
2
2
2
l¼1





1
1 t 2tþtþ 2tt
wk;l exp  ðwk;l Þ þ wk;l exp  ðwk;l Þ Uk;l
2
2
t



 
U~ k;l ¼;
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt
1 tþ 2
1 t 2
1  ql exp  ðwk;l Þ  exp  ðwk;l Þ
2
2
t
t
~
Vk;l ¼ Uk;l ;
t
Vk;l
¼

ðA 41Þ
ðA 42Þ

ðA 43Þ

ðA 44Þ

wherewtþ
k;l ¼

 tl  ^^ tl
kþ^pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt;
1  qlandwt
k;l ¼

 tl þ ^^ tlk^pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt
1  qlðA 45Þ

Z þ1HðuÞ ¼

ðA 46Þ

Dx:
u

t
t
t
t
In another schemes, we ﬁrst calculate Uk;l, Vk;l, U~ k;l, and V~k;lwhich are needed to obtain an iterative equation of(A 40).

A.2 Committee tree with non-monotonic hidden units (CTH)
In the case of the CTH, F k is given by(rﬃﬃﬃﬃﬃ)!
"!#
rﬃﬃﬃﬃﬃKXKKs l xls l xl
Fk
fk
¼ sgn
N
N
l¼1

"
sgn

fk ð il þ ^il Þ þKX
l0 6¼l#fk ð^il0 Þ:In the same way as the PTH, we ﬁnd"(
Z þ1 YK
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

1 y

t
 til þ zl 1  qtilþ ð1  r  pÞ sgn fk  il þ ^Dzl Fk;il ð il Þ ¼22
1 l¼1)#K
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
X
 ty il0 þ zl0 1  qtil0 þ ðr  pÞ :fk ^
þ2
l0 6¼l
Evaluating Ftk;il ð0Þ and ½@Ftk;il ð il Þ=@ il j il ¼0 , we obtain
(
"
#
 



K
X
y ð1  r  pÞ
1 tþ 2
1 t 2 Xt
Uk;l ¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt ﬃ exp  ðwk;l Þ  exp  ðwk;l Þ
l sgn
l
2
2
2 2ð1  ql Þ
l¼1
l
)

K 
Y
1 þ l0tþt
00 l Hðwk;l0 Þ  l Hðwk;l0 Þ ;2
l0 6¼l
( "
# 
)
K
K
Y
X
X
1 y
y
1þ l
t
tþ
t
 l Hðwk;l Þ  l Hðwk;l Þ ;Vk;l ¼ þ ðr  pÞ þ ð1  r  pÞ
sgn
l
2
2
2
2
l¼1
l¼1
l





1 tþ 2
1 t 2
t
t
ðw
ðw
exp

Þ
exp

Þ
wtþ
þ
w
Uk;l
k;l
k;l
k;l
k;l
2
2
t



 
U~ k;l¼;
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt
1
1 t 22
ðw
1  ql exp  ðwtþ
Þ
Þ

exp

2 k;l2 k;ltt¼ Uk;l;
V~k;lðA 47Þ

ðA 48Þ

ðA 49Þ
ðA 50Þ

ðA 51Þ

ðA 52Þ

where tl  ^^ tl
 tl þ ^
^ tl
kþ^
k^
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃtp
ﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
¼
; wt
:
ðA 53Þ
k;l1  ql1  qtlP
denotes the sum over all the possible state for the dummy binary variables f l g which can take the value 1.
and
l
wtþ
k;l ¼

A.3 Committee tree with a non-monotonic output unit (CTO)
In this case it should be noted that optimal performance are obtain only for a number of hidden unit K ! 1. However we
decide to investigate the performance given by the scheme even with a ﬁnite number of hidden units. In the case of the CTO
F k is given by
034802-16#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

Fk(rﬃﬃﬃﬃﬃ)!
"rﬃﬃﬃﬃﬃ!#
rﬃﬃﬃﬃﬃ
KK
1X
Ks l xls l xl
sgn
¼ fk
N
K l¼1
N

K. MIMURA et al.

"rﬃﬃﬃﬃﬃ#
rﬃﬃﬃﬃﬃ K
11Xsgnð^il0 Þ :fksgnð il þ ^il Þ þK
K l0 6¼l

In the same way as the PTH, we ﬁnd("rﬃﬃﬃﬃﬃ
Z þ1 YK
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ

1 y
1

t
 til þ zl 1  qtilþ ð1  r  pÞfkFk;il ð il Þ ¼
Dzl
sgn  il þ ^2
K2
1 l¼1)#
rﬃﬃﬃﬃﬃ K
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
 t
1X
y
t
 il0 þ zl0 1  qil0 þ ðr  pÞ ;þsgn ^K l0 6¼l
2and have

( "
)
#

K
K
Y
X
1 t 2 Xlt
pﬃﬃﬃﬃ
H½ l0 wk;l0 ; ðwk;l Þ
l fk
2
K l0 6¼l
l¼1
l
( "
)
#
K
K
Y
X
X
1 y
y
l
t
t
pﬃﬃﬃﬃ
Vk;l ¼ þ ðr  pÞ þ ð1  r  pÞfk
H½ l wk;l ;
2
2
2
K l¼1
l¼1
l

y ð1  r  pÞt
Uk;l
¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt ﬃ exp
2 2ð1  ql ÞðA 54Þ

ðA 55Þ



1
tt¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt wtk;l Uk;l;
U~ k;l1  qltt
V~k;l¼ Uk;l;ðA 56Þ
ðA 57Þ
ðA 58Þ
ðA 59Þ

where tl  ^^ tl^wtk;l ¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt :1  qlðA 60Þ

Appendix B: Derivation of the BP Encoder for Lossy Compression
In the lossy compression case, Gk; is given by(rﬃﬃﬃﬃﬃ)!
"(rﬃﬃﬃﬃﬃ
)! #
K
K





s l xls l xl¼ e þ ð1  e Þ y F k
;
Gk;
N
N

ðB 1Þ

according to the ref. 18. The method to derive the set of BP messages is exactly same as in the error correcting cases. Thus, the BP
equations are given by (A 4), (A 5), and (A 16) for the standard algorithm and by (A 40) for the more approximated version. Onlytttt
~ V and V~ change. Therefore, in lossy compression case, we ﬁrst calculate Uk;l
F, U, U,
, Vk;l, U~ k;l, and V~k;lfor each scheme.
B.1 Parity tree with non-monotonic hidden units (PTH)
In the case of the PTH, using the same method as the error correcting case, one can ﬁnd Fk ,()
Z þ1 Y
K
K
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ Y
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
 t
1 y  tttt il þ zl 1  qil
 il0 þ zl0 1  qil0 :þ fk  il þ ^Dzl
fk ^Fk;il ð il Þ ¼22
1 l¼1l0 6¼lðB 2Þ

In the same way, one can obtain

 


 K
1 tþ 2
1 t 2 Yt½1  2Hðwtþ
exp  ðwk;l Þ  exp  ðwk;l Þk;l0 Þ  2Hðwk;l0 Þ ;
2
2
0
l 6¼l
!
K
Y
1
y
t
t
þ
Vk;l
¼ e þ ð1  e Þ½1  2Hðwtþ
k;l Þ  2Hðwk;l Þ ;
2
2 l¼1





1 tþ 2
1 t 2
t
t
ðw
ðw
exp

Þ
exp

Þ
wtþ
þ
w
Uk;l
k;l
k;l
2 k;l2 k;lt 
U~ k;l ¼;
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt
1 tþ 2
1 t 2
1  ql exp  ðwk;l Þ  exp  ðwk;l Þ
22tt
V~k;l ¼ Uk;l ;y ð1  e Þt¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt ﬃ
Uk;l2ð1  ql Þ

ðB 3Þ
ðB 4Þ

ðB 5Þ

ðB 6Þ

where
wtþ
k;l ¼

 tl  ^^ tl
kþ^pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt;
1  qlwt
k;l ¼

 tl þ ^^ tlk^pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt:
1  qlðB 7Þ

B.2 Committee tree with non-monotonic hidden units
In the case of the CTH, one can ﬁnd034802-17#2011 The Physical Society of Japan

FULL PAPERS

J. Phys. Soc. Jpn. 80 (2011) 034802

Ftk;il ð il Þ ¼

Z þ1 YK
1 l¼1

K. MIMURA et al.

"#K
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
X
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
 til0 þ zl0 1  qtil0 ; til þ zl 1  qtil þ y
Dzl  y fk  il þ ^
fk ^

ðB 8Þ

l0 6¼lwhere  denotes the unit step function which takes 1 for x  0 and 0 for x < 0. Using the above equation, we have
 



ð1  e Þ
1 tþ 2
1 t 2tﬃ
ðwðw¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
Þ
Þ

exp

Uk;l
exp

2 k;l2 k;l2ð1  qtl Þ
(
"
# 
)
K
K
Y
X
X
0
1
þ
l

t
 l0 Hðwtþ

;
ðB 9Þ
l y
l
k;l0 Þ  l0 Hðwk;l0 Þ2
l¼1
l0 6¼l
l
( "
# 
)
K
K
Y
X
X
1þ l
t



tþ
t
 l Hðwk;l Þ  l Hðwk;l Þ ;Vk;l ¼ e þ ð1  e Þ ðB 10Þ
 y
l
2
l¼1
l¼1
l





1 tþ 2
1 t 2
t
t
ðw
ðw
exp

Þ
exp

Þ
wtþ
þ
w
Uk;l
k;l
k;l
k;l
k;l
2
2
t



 
U~ k;l¼;
ðB 11Þ
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt
1
1 t 22
ðw
1  ql exp  ðwtþ
Þ
Þ

exp

2 k;l2 k;ltt
V~k;l¼ Uk;l;ðB 12Þ
wherewtþ
k;l ¼

 tl  ^^ tl
kþ^pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt;
1  qlwt
k;l ¼

 tl þ ^^ tlk^pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt:
1  qlðB 13Þ

B.3 Committee tree with a non-monotonic output unit (CTO)
In this case it should be noted that optimal performance are obtain only for a number of hidden unit K ! 1. However we
decide to investigate the performance given by the scheme even with a ﬁnite number of hidden unit. We ﬁnd Fk as follows:#!
"rﬃﬃﬃﬃﬃ
rﬃﬃﬃﬃﬃ K
Z þ1 YK
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
 t
 
1
1X

t

t
t
t
 il0 þ zl0 1  qil0
 il þ zl 1  qil þ: ðB 14Þ
Dzl  y fk
sgn ^Fk;il ð il Þ ¼
sgn  il þ ^K
K l0 6¼l
1 l¼1We then have

)
(
"
!#


K
K
X
Y
1 t 2 Xltpﬃﬃﬃﬃ
H½ l0 wk;l0 ; ðwk;l Þl  y fk2
K
l¼1
l0 6¼l
l
)
( "
!#
K
K
Y
X
X
l
t



t
pﬃﬃﬃﬃ
Vk;l ¼ e þ ð1  e ÞH½ l wk;l ; y fkK
l¼1
l¼1
lð1  e Þt
ﬃ exp¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃ
Uk;l2ð1  qtl Þ1tt
U~ k;l¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt wtk;l Uk;l;
1  qltt
V~k;l¼ Uk;l;ðB 15Þ
ðB 16Þ
ðB 17Þ
ðB 18Þ

where tl  ^^ tl^wtk;l ¼ pﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃﬃt :1  ql1) C. E. Shannon: Bell Syst. Tech. J. 27 (1948) 379.
2) N. Sourlas: Nature 339 (1989) 693.
3) Y. Kabashima, T. Murayama, and D. Saad: Phys. Rev. Lett. 84 (2000)
1355.
4) H. Nishimori and K. Y. M. Wong: Phys. Rev. E 60 (1999) 132.
5) A. Montanari and N. Sourlas: Eur. Phys. J. B 18 (2000) 107.
6) F. Cousseau, K. Mimura, and M. Okada: Phys. Rev. E 78 (2010)
021124.
7) T. Tanaka: Europhys. Lett. 54 (2001) 540.
8) T. Tanaka and M. Okada: IEEE Trans. Inf. Theory 51 (2005) 700.
9) K. Mimura: J. Phys. A 38 (2005) 9917.
10) K. Mimura and M. Okada: Proc. 2007 IEEE Int. Symp. Information
Theory (ISIT2007), 2007, p. 2076.
11) K. Mimura and M. Okada: Proc. 2006 IEEE Int. Symp. Information
Theory (ISIT2006), 2006, p. 2373.
12) C. E. Shannon: IRE Natl. Conv. Rec. 4 (1959) 142.
13) T. Murayama and M. Okada: J. Phys. A 36 (2003) 11123.
14) T. Murayama: Phys. Rev. E 69 (2004) 035105(R).

ðB 19Þ

15) T. Hosaka, Y. Kabashima, and H. Nishimori: Phys. Rev. E 66 (2002)
066126.
16) T. Hosaka and Y. Kabashima: J. Phys. Soc. Jpn. 74 (2005) 488.
17) K. Mimura and M. Okada: Phys. Rev. E 74 (2006) 026108.
18) F. Cousseau, K. Mimura, T. Omori, and M. Okada: Phys. Rev. E 78
(2008) 021124.
19) A. Engel and C. Van den Broeck: Statistical Mechanics of Learning(Cambridge University Press, Cambridge, U.K., 2001).
20) T. Hosaka and Y. Kabashima: Physica A 365 (2006) 113.
21) T. M. Cover and J. A. Thomas: Elements of Information Theory(Wiley, New York, 1991).
22) E. Gardner: J. Phys. A 21 (1988) 257.
23) W. Krauth and M. Mézard: J. Phys. (France) 50 (1989) 3057.
24) Advanced Mean Field Methods, ed. M. Opper and D. Saad (MIT Press,
Cambridge, MA, 2000) Sect. 5.
25) D. J. C. MacKay: Information Theory, Inference, and Learning
Algorithms (Cambridge University Press, Cambridge, U.K., 2003).
26) T. Obuchi and Y. Kabashima: J. Stat. Mech. (2009) P12014.

034802-18#2011 The Physical Society of Japan