Yuuji Ichisugi and Naoto Takahashi,
An Efficient Recognition Algorithm for Restricted Bayesian Networks,
In Proc. of 2015 International Joint Conference on Neural Networks (IJCNN 2015).
http://ieeexplore.ieee.org/document/7280330/© 2015 IEEE. Personal use of this material is permitted. Permission from IEEE must be
obtained for all other uses, in any current or future media, including reprinting/republishing
this material for advertising or promotional purposes, creating new collective works, forresale or redistribution to servers or lists, or reuse of any copyrighted component of thiswork in other works.

An Efficient Recognition Algorithm
for Restricted Bayesian Networks
Yuuji Ichisugi
and Naoto Takahashi
National Institute of Advanced Industrial Science and Technology (AIST)
Tsukuba Central 2, Tsukuba, Ibaraki 305-8568, Japane-mail: y-ichisugi@aist.go.jp
Abstract—We propose an optimization method for belief propagation. First we mathematically show that the belief propagation
algorithm can be optimized by imposing a reasonable restriction
on the conditional probability tables in a Bayesian network. Then
we demonstrate the efficiency of the proposed algorithm withexperiments. Compared to the previously derived approximate algorithm, the proposed algorithm has the following features: 1. theproposed algorithm calculates more accurate maximum posterior
marginal values, 2. similar to the approximate algorithm, its
execution time grows only linearly against the number of edges,
and 3. the proposed algorithm is slower than the approximate
algorithm, but the difference between their execution time is lessthan twice.

I.

I NTRODUCTION

According to the recent studies in computational neuroscience, Bayesian network [1] can be the underlying mechanism of the cerebral cortex. Various neuroscientific phenomena are successfully reproduced with models based on
Bayesian networks. The cerebral cortex shares many aspects,
not only in functions but also in structures, with Bayesian
networks [2][3][4][5][6][7].
On the other hand, the deep learning technology has been
receiving attention because of its high performance in recognition tasks that are easy for human but difficult for machines.
Systems that are based on deep learning have been breaking
records in many competitions. It is worth pointing out that the
deep learning technology is a descendant of Neocognitron [8],which is a neural circuit model that emulates the structure of
the ventral stream in the visual cortex.
Considering the above two facts, it is expected that we
obtain more human-like machine learning algorithms by combining Bayesian networks and the deep learning technology.
Such machine learning algorithms would show better performance and higher functionality compared to the current
machine learning algorithms used in recognition tasks.
There are also technical reasons for which we can expect
superior man-chine learning algorithms in the combination ofBayesian networks and the deep learning technology:•

Bayesian network is a knowledge representation
model that expresses causal relationship among multiple events, using probabilities. Under certain conditions, Bayesian networks can concisely express causal
relationships between the signal source and the observed data; various inferences can be performed
efficiently in these cases.

•

Bayesian networks use not only bottom-up input information but also top-down context information to
perform robust inference [2]. Which means Bayesian
networks can be applied to a wider range of tasks
compared to ordinary feed-forward neural networks.

•

Bayesian networks can straightforwardly represent
generative models with multiple layers. Therefore itis easy to design a Bayesian network that reflects
prior knowledge of the target domain. It is expectedthat learning performance improves by designing a
network so that its internal structure and the priordistribution of parameters reflect the prior knowledge. Prior knowledge can be obtained both fromengineering analysis of the target domain and fromneuroscientific studies, e.g. how multiple areas of thecerebral cortex are connected, etc.

There are, however, two potential problems in using
Bayesian networks with the deep learning technology: 1)
execution time and required memory grow rapidly as the sizeof the network becomes bigger, and 2) learning would converge
to a local minimum or overfitting would occur.
To overcome the first problem above (i.e. complexities),
we propose an algorithm that greatly accelerates the belief
propagation of a Bayesian network by imposing a restriction
on the conditional probability tables. We then demonstrate its
positive effect with experimental results.
Although we do not discuss the second problem (i.e. local
minimum/overfitting) in this paper, it can be mitigated by
specifying the prior distribution of parameters.
II.

P ROPOSED R ECOGNITION A LGORITHM

The main reason of the potential problems mentioned
above is that the size of a conditional probability table increases exponentially against the number of parent nodes.
We impose the following linear-sum restriction on the conditional probabilities to reduce the number of parameters of
the Bayesian network:m

P (x|u1 , · · · , um ) =1 X
w(x, uk )
m

(1)

k=1

where uk is the value of node X’s parent node Uk , and w is
an arbitrary function. One of the simplest form of w isw(x, uk ) = P (x|uk ).

(2)

BEL(x)π(x)u1 ,···,um

λ(x)

Y
X
1 XX
πX (ui )w(x, uk )πX (uk )mk uku1 ,···,um /uk i6=k
1 XX=
w(x, uk )πX (uk )
m
k uk
1 X
=
κUk (x)m== αλ(x)π(x)XY=
P (x|u1 , · · · , um )πX (uk )=YkλYl (x)lY

πYl (x)= β1 π(x)λYj (x)λX (uk )

X
= β2
λ(x)

k

j6=l
def

x


Y
P (x|u1 , · · · , um )πX (ui )X×With the definition of ρ(x) = π(x)λ(x), the equation ofπYl (x) in Fig. 1 is transformed as follows.

i6=ku1 ,···,um /uk

πYl (x)=β1 π(x)Y

λYj (x)j6=lFig. 1. Pearl’s original belief propagation algorithm. Here, α, β1 and β2 arenormalizing constants.

=

β1 (π(x)Y

λYj (x))/λYl (x)j=When the conditional probability tables are restricted as inEquation 1, we can transform Pearl’s original belief propagation algorithm [1], which is reproduced in Fig. 1, as follows.
First, we assume that the messages from the parent nodes
are normalized asXπX (uk ) = 1
(3)
uk

P
Q
The term u1 ,···,um /uk P (x|u1 , · · · , um ) i6=k πX (ui ) in
the equation of λX (uk ) in Fig. 1 is transformed as follows.
Here we use the same transformation technique that we use totransform π(x).

and therefore the equation
X

m
Y

X
πX (ui ) = 1(4)

P (x|u1 , · · · , um )X
u1 ,···,um /uk

holds.

1=m

Next, we define κUk (x) as follows:XdefκUk (x) =w(x, uk )πX (uk )

(5)

uk



Y

πX (ui )i6=ku1 ,···,um /uk=

u1 ,···,um i=1β1 ρ(x)/λYl (x)

X

Y
1 X
(
w(x, uj ) + w(x, uk ))πX (ui )
m
j6=k

X

i6=k

w(x, uj )

u1 ,···,um /uk j6=kX

+w(x, uk )YπX (ui )

i6=k

Y


πX (ui )u1 ,···,um /uk i6=k

Now the equation of π(x) in Fig. 1 is transformed asfollows. (Note that 1/m is a constant.)
XY
π(x) =
P (x|u1 , · · · , um )πX (ui )u1 ,···,um+··· +

w(x, um )πX (um )u1 ,···,um
1 X
w(x, u1 )πX (u1 )=m u1+··· +

Xum

Then we can calculate λX (uk ) as follows.

i6=1

m

X

k

1
= (mπ(x) − κUk (x) + w(x, uk ))
m

i

Y
1 X
w(x, uk ))πX (ui )=(m
u1 ,···,um
i
k
Y
1 X X
=
w(x, uk )πX (uk )πX (ui )m u ,···,u
i6=k
1
m k
 X
Y
1
=
w(x, u1 )πX (u1 )πX (ui )m u ,···,u
X

1

X
1
= (mπ(x) −w(x, uk )πX (uk ) + w(x, uk ))muY

λX (uk )
X
= β2
λ(x)

X

x

u1 ,···,um /uk=πX (ui )P (x|u1 , · · · , um )YπX (ui )

i6=k

β2 X
λ(x)(mπ(x) − κUk (x) + w(x, uk ))
m x

i6=m

X

Y

πX (ui )u1 ,···,um /u1 i6=1

w(x, um )πX (um )XY

u1 ,···,um /um i6=mπX (ui )Replacing mπ(x) with π(x) (as π(x) is rescalable), combining all the results above, reassigning normalizing constants
and adding the indices t and t + 1 so that the equations areapplicable to loopy networks, we get the following algorithm,
which we call Optimized Original Belief Propagation (OOBP).







....




PP
 
PP
)

?
)

q)
P
? 

? P
q
?
Hidden nodes


....



PP 

PP
 

? 
? 
q?
P
) 

? 
)

q)
P

....
Input nodes






Fig. 2. The generalized structure of the Bayesian networks used for theevaluation. All layers contain the same number of nodes. Edges exist only
between two adjacent layers. All nodes have two states. The conditional
probability tables are randomly set before each recognition trial.

λt+1
Yl (x)= β2X

λt (yl )(π t (yl ) − κtX (yl ) + w(yl , x))yl

λt+1 (x)

=

n
Y

λt+1
Yl (x)

hall is the total number of hidden nodes.
The convergence rate is defined as:
convergence rate =

tcon
tall

(8)

where tcon is the number of recognition trials in which all
hidden nodes converged within a predetermined iteration steps(set to 50 for this article) and tall is the total number ofrecognition trials.
The mean iteration steps is defined as:
mean iteration steps =

tcon
1 X

tcon i=1si(9)where si is the iteration steps at which the network convergedin the i-th converged recognition trial. Recognition trials that
did not converge are excluded. This measure is meaningful
only for network configurations that achieve high convergence
rates.

l=1

πYt+1
(x)
l
t+1
κUk (x)π t+1 (x)= β1 ρt+1 (x)/λt+1
Yl (x)
Xt=w(x, uk )πX
(uk )
=

uk
m
X

B. Accuracy for Small Networks
First we show the accuracy of the proposed algorithm.
Fig. 3 and Fig. 4 plot the mean measured values of 100
recognition trials. Only networks of small sizes were used forevaluation because calculation of strict MPM values requires
long execution time. (See footnote 2.)

κt+1
Uk (x)

k=1

ρt+1 (x) = λt+1 (x)π t+1 (x)BELt+1 (x) = αρt+1 (x)(6)

Note that, unlike done in [3], we do not use any approximation here.
III.

E VALUATION OF THE P ROPOSED A LGORITHM

A. Evaluation Method
We evaluated the algorithm proposed in this article bycomparing it with the approximate algorithm derived in [3]and with the original loopy belief propagation. All algorithms
were implemented in Java 1 and executed on a laptop computerwith an Intel Core 2 Duo P8600 (2.4GHz) CPU.
The Bayesian networks used for the evaluation have alayered structure as shown in Fig. 2. This structure is an
implementation of a cerebral cortex model called BESOM (BidirEctional Self-Organizing Map). [6]We used three measured values for evaluation: correct rate,
convergence rate and mean iteration steps.
The correct rate is defined as:
hcor(7)correct rate =hallwhere hcor is the number of hidden nodes that converged tothe correct maximum posterior marginal (MPM) values 2 and
1 The source code is available at:https://staff.aist.go.jp/y-ichisugi/besom/download.html
2 We implemented yet another algorithm to find the “correct” MPM values.
This algorithm calculates the strict MPM values based on naive full search andrequires long calculation time, which increases exponentially to the numberof nodes. This naive algorithm was used solely for strict MPM calculationand not a target for the current evaluation.

The proposed algorithm gives better correct rates comparedto the previously derived algorithm that uses approximation,
thanks to its more accurate calculation. Since the correct rateof the proposed algorithm and that of the original loopy belief
propagation are always almost the same, we can confirm thatthe proposed algorithm and the original loopy belief propagation are mathematically equivalent. (Fig. 3 A and Fig. 4 D)
All the convergence rates are close to 1.0, which means
both proposed and approximate algorithms have stable behaviour and seldom oscillate. When the number of layers
increases, however, the convergence rate of the approximate
algorithm decreases slightly. (Fig. 3 B and Fig. 4 E)
With shallow networks, the proposed algorithm requires
slightly greater mean iteration steps than the approximate
algorithm. The difference becomes clearer as the number ofnodes increases. (Fig. 3 C)
With narrow networks, both proposed and approximate
algorithms require almost the same mean iteration steps if thenumber of layers is less than or equal to 4. When the numberof layers reaches to 5, the approximate algorithm requires moremean iteration steps compared to the proposed algorithm. The
reason for this phenomenon remains to be elucidated. (Fig. 4 F)
C. Scalability
Next, we show the scalability of the proposed algorithm.
Fig. 5 plots execution time for networks that have 3 layers.
The number of nodes in a layer varies between 100 and
900. Both algorithms show execution time that grows almost
linearly against the number of nodes in a layer. Comparedto the approximate algorithm, the proposed algorithm requires

D

1

1

0.98

0.98
Correct rate

Correct rate

A

0.96
0.94
0.92

0.96
0.94
0.92

proposed
approximate
original

0.9
0.88
5

6

7
8
Number of nodes / layer

9

proposed
approximate
original

0.9
0.88
10

2

3

B

Convergence rate

Convergence rate

6

1

0.98
0.96
0.94
0.92

5

6

7
8
Number of nodes / layer

9

0.98
0.96
0.94
0.92

proposed
approximate
original

0.9

proposed
approximate
original

0.9
10

2

3

C
10

8

8

6

4

2

6

5

6

7
8
Number of nodes / layer

9

6

4

2

proposed
approximate
original

04
Number of layers
F

10

Mean iteration steps

Mean iteration steps

5

E

1

5

4
Number of layers

proposed
approximate
original

010Fig. 3.
Recognition results of shallow networks: (A) correct rates, (B)convergence rates and (C) mean iteration steps. The number of layers is fixed
to 3. The number of nodes in a layer varies between 5 and 10. Each hidden
node is connected to randomly selected 5 child nodes allowing duplication.

2

3

4
Number of layers

56Fig. 4.
Recognition results of narrow networks: (D) correct rates, (E)convergence rates and (F) mean iteration steps. The number of nodes in alayer is fixed to 5. The number of layers varies between 2 and 6. Each hidden
node is connected to every node in the layer below.

1200

1 node10 states

L3 (output)
Execution time (msec)

1000

800

L2

600

L1

3x3 nodes
100 states / node…

5x5 nodes
20 states / node400

L0 (input)

200

28x28 pixels

proposed
approximate

0
100

200

300

400
500
600
Number of nodes / layer

700

800

900

Fig. 5. Execution time of the proposed and the approximate algorithms forshallow and wide networks. The number of layers is fixed to 3. The number ofnodes in a layer varies between 100 and 900. Each hidden node is connected
to randomly selected 20 child nodes allowing duplication.
60

50
Execution time (msec)…

40

Fig. 7. The structure of the Bayesian network used for handwritten digit
recognition. The input layer consists of 28 by 28 pixels. The first hidden
layer contains 25 nodes with 20 states. The second hidden layer contains 9
nodes with 100 states.

consists of 28 by 28 pixels. The first hidden layer consistsof 5 by 5 nodes and the second 3 by 3. Each node has 20
states in the first hidden layer and 100 in the second. Eachhidden node is connected to nodes in the layer below to havea local receptive field as in general deep learning networks.
The output layer has only one node of 10 states; each statecorresponds to a label, i.e. one of the ten digits.
We first trained the network using the online version of
the EM algorithm, giving the label to the output node. Then
we tested its performance using the proposed algorithm. The
label that had the largest posterior probability in the output
node was selected as the output.

30

20

10
proposed
approximate

0
0

2

4

6
8
10
12
14
Number of children / node

16

18

20

Fig. 6. Execution time of the proposed and the approximate algorithms forshallow networks. The number of layers and the number of nodes in a layer are
fixed to 3 and 100, respectively. Each hidden node is connected to randomly
selected n child nodes allowing duplication, where n varies between 1 and20.

longer execution time, but the difference is suppressed lessthan twice.
Fig. 6 is another graph that indicates the scalability of the
proposed algorithm. For this time, the number of layers and thenumber of nodes in a layer are fixed, but the number of childnodes varies. Again, execution time of the proposed algorithm
grows almost linearly against the number of child nodes.
D. Digit Recognition
We also performed a preliminary experiment of handwritten digit recognition using MNIST [9] to estimate applicabilityof the proposed algorithm.
Fig. 7 shows the structure of the Bayesian network used
for this purpose. The network has a layered structure as the
networks used in the evaluation above, but the number of nodes
and the number of states differ with layers. The input layer

Its recognition accuracy was about 91% without pretraining. Although this result is not satisfactory as a practicalmachine learning algorithm, we should be able to increase theaccuracy by improving the model of conditional probability
tables and tuning hyper parameters.
IV.

R ELATED W ORK

Researchers often impose restrictions on the conditional
probability tables and/or the network structure of a Bayesian
network for the purpose of decreasing the number of parameters and increasing the accuracy of recognition.
The noisy-or model [1] not only concisely represents
causal relationships among binary variables but also reducescomputational cost by optimizing the algorithm. This modelstraightforwardly represents the situation in which one of thecausal events should have occurred when an event is observed.
Situations of this kind are common in the real world.
George and Hawkins’ cerebral cortex model [2] restricts
the network to tree structure to avoid explosion of memory
size and computational cost. However, tree structure looks
insufficient as a model of the cerebral cortex; the actual
cerebral cortex is definitely not of the form of tree structure.
Hosoya [4] successfully reproduces multiple phenomena
found in the visual cortex by using conditional probability
tables based on softmax. The used learning method is Markov
chain Monte Carlo (MCMC) and not the belief propagation
algorithm.

Dura-Bernal et al. [5] develop a visual perception modelusing two different optimization techniques. The first one isrestricting conditional probability tables, which is similar to theone proposed in this article. They optimize message calculation, which is also similar to our method, but their optimization
is done only partially. Their second optimization technique
is introducing approximation in messages calculation. Thissecond one is independent of the method proposed in thisarticle, therefore it should be possible to merge this second
technique with our method to accelerate calculation.
V.

C ONCLUSION

We first mathematically showed that the belief propagation
algorithm can be optimized by imposing a restriction on theconditional probability tables. Then we demonstrated the efficiency of the proposed algorithm with experiments. Comparedto the previously derived approximate algorithm, the proposed
algorithm has the following features:
1)
2)
3)

The proposed algorithm calculates more accurate
maximum posterior marginal values.
Similar to the approximate algorithm, its execution
time grows only linearly against the number of edges.
The proposed algorithm is slower than the approximate algorithm, but the difference between their
execution time is less than twice.

As already reported [6], our earlier version of cerebral
cortex model, which satisfies the same restriction on theconditional probability tables as in this article, resulted in having variables that correspond to the six-layers and columnarstructure in the cerebral cortex and relation among variables
that corresponds to connections between areas of the cortex.
Their resemblance is remarkable and unlikely to be a mere
coincidence. Therefore we believe that Equation 1 is a fairly
reasonable restriction.
However, it is also clear that the restriction limits the abilityof the Bayesian network to which it applies. We are now
investigating its theoretical limits and trying to find a looser
restriction for better performance.
R EFERENCES
[1]
[2]

[3]

[4]

[5]

[6]

J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks ofPlausible Inference, Morgan Kaufmann, 1988.
D. George and J. Hawkins, A hierarchical Bayesian model of invariant
pattern recognition in the visual cortex, In Proc. of International Joint
Conference on Neural Networks (IJCNN2005), Vol.3, pp.1812–1817,
2005.
Y. Ichisugi, Recognition Model of Cerebral Cortex based on Approximate Belief Revision Algorithm, In Proc. of International Joint
Conference on Neural Networks (IJCNN2011), pp.386–391, 2011.
H. Hosoya, Multinomial Bayesian Learning for Modeling Classical andNonclassical Receptive Field Properties, Neural Computation, Vol.24,
No.8, pp.2119–2150, 2012.
S. Dura-Bernal, T. Wennekers and S.L. Denham, Top-Down Feedbackin an HMAX-Like Cortical Model of Object Perception Based on
Hierarchical Bayesian Networks and Belief Propagation, PLOS ONE,
Vol.7, No.11, 2012.
Y. Ichisugi, The cerebral cortex model that self-organizes conditional
probability tables and executes belief propagation, In Proc. of International Joint Conference on Neural Networks (IJCNN2007), pp.1065–
1077, 2007.

[7]

F. Roehrbein, J. Eggert and E. Koemer, Bayesian Columnar Networks
for Grounded Cognitive System, In Proc. of the 30th Annual Conferenceof the Cognitive Science Society, pp.1423–1428, 2008.
[8] K. Fukushima, Neocognitron: A self-organizing neural network model
for a mechanism of pattern recognition unaffected by shift in position,
Biological Cybernetics, Vol.36, pp.193–202, 1980.
[9] Y. LeCun, L. Bottou, Y. Bengio and P. Haffner, Gradient-Based Learning Applied to Document Recognition, In Proc. of the IEEE, 86(11),2278–2324 1998.