Lecture Notes in Computer Science

bet	36/88
Sana	16.12.2017
Hajmi	12.42 Mb.
	#22381

1 ... 32 33 34 35 36 37 38 39 ... 88

Stop learning

Virtual Environment

Environmental

data

CPG

Robot

Fig. 1. Virtual learning system for a biped robot

with representative data, it can generate desired CPG input at unknown envi-

ronment and then a biped robot achieves a task. It takes much time to train

NN, but NN is fast to generate output. CPG input is ﬁrst generated by NN

and then checked in virtual environment. When the CPG input generated by

NN achieve a task, it is sent to a CPG. Otherwise, CPG input obtained by ex-

ploring, which takes time, is used for controlling a robot. And NN learns with

CPG input obtained by exploring to correct its error. Combination of NN and

exploring realizes autonomous learning and covers their shortcomings each other.

Neural Networks for Incremental Learning

A key of our virtual learning system is NN. A virtual learning system should

develop with experience in various environments and tasks. However, multi-

layer perceptron (MLP) with back-propagation (BP) learning algorithm, which

is widely used in many applications, has a problem that it forgets prior learning

through training with a new dataset because its connection weights are over-

written. If all training datasets are stored in a memory, prior learning can be

reﬂected in a MLP by training with all the datasets, but training with a large

volume of dataset takes huge amount of time and memory. Of course humans

can learn something new with keeping old experiences. A virtual learning system

needs to accumulate virtual experiences step by step.

3.1

Perturbational Neural Networks

The basic idea of PNN is that a NN learns a new dataset by adding new pa-

rameters to constant weights and thresholds after training without overwriting

them. PNN consists of main NN and sub NN as shown in Fig.2. Main NN learns

with representative datasets and is constant after this learning. Sub NN learns

with new datasets and generates new terms in weights and thresholds of main

398

E. Inohira, H. Oonishi, and H. Yokoi

Main NN

Sub NN

Δw, Δh

Input

Output

Fig. 2. A perturbational neural network

1

w

Δ

−

h

x

1

h

Δ

f

z

From Sub NN

Neuron

Input

Output

Fig. 3. A neuron in main NN

NN, i.e., Δw and Δh. A neuron of PNN is shown in Fig.3. Input-output relation

of a conventional neuron is given by the following equation.

z = f

i

w

− h

(1)

where z denotes output, w

weight, x

input, and f (

·) activation function.

A neuron of PNN is given as follows.

z = f

i

(w

+ Δw

− (h + Δh)

(2)

where Δw

and Δh are outputs of sub NN.

Training of PNN is divided into two phases. First, main NN learns a main

NN with representative dataset. For instance, it is assumed that representa-

tive datasets consists of environmental data (E

, E

) and CPG parameters

PNNs for Incremental Learning in Virtual Learning System

399

Main NN

Sub NN

Δw, Δh

E

A

E

B

E

C

,

,

P

A

P

B

P

C

,

,

0

Fig. 4. Training of NN with representative dataset

Main NN

Sub NN

Δw, Δh

E

D

P

D

Stop learning

Fig. 5. Training of NN with new dataset

A

, P

, P

) as shown in Fig.4. Training of main NN is the same as NN with BP.

At this time, sub NN learn as Δw and Δh equal zero. Then, for representative

dataset, sub NN has no eﬀect on main NN. Next, PNN learns with new dataset.

For instance, it is assumed that new dataset consists of environmental data E

and CPG parameters P

as shown in Fig.5. Main NN does not learn with the

new dataset, but reinforcement signals are passed to sub NN through main NN.

Output error of main NN for E

exists because it is unknown for main NN. Sub

NN learns with new dataset as such error is canceled.

3.2

Related Work

Some authors [6,7,8] have proposed other methods in which Mixture of Experts

(MoE) architecture is applied to incremental learning of neural networks. The

MoE architecture is based on divide-and-conquer approach. It means that a com-

plex mapping which a signal neural network should learn is divided into simple

mappings which a neural network can learn easily in such architecture. On the

other hand, a PNN learns a complex mapping by connecting sub NNs with a main

NN. A PNN is expected to have global generalization capability because it does

not divided a mapping to local mappings. In the MoE architecture, a expert neu-

ral network is expected to have local generalization capability. However, a system

would not have global generalization capability because it is not concerned. There-

fore, when generalization capability is focused on, a PNN should be used.

400

E. Inohira, H. Oonishi, and H. Yokoi

A PNN have a problem that it needs large number of connections from sub NNs

to a main NN. It means that a PNN is very ineﬃcient in resources. Although we

have not yet study eﬃciency in a PNN, we guess that a PNN has room to reduce

the connections, and it would be our future work.

Numerical Experiments

4.1

Setup

We evaluate generalization capability of proposed NN for incremental learning

through numerical experiments of a robot climbing stairs. Simpliﬁed experiments

are performed because we focus on a NN for virtual learning.

Fig. 6. A two-dimensional ﬁve-link biped robot model

Neural oscillator

Fig. 7. A CPG for a biped robot

A two-dimensional ﬁve-link model of a bipedal robot is used as shown in

Fig. 6. Five joint angles deﬁned in Fig. 6 are controlled by ﬁve neural oscillators

corresponding to each joint angle. Length of all link is 100 cm. A task of a

bipedal robot is to climb ﬁve stairs. Height and depth of stairs are used for

PNNs for Incremental Learning in Virtual Learning System

401

Table 1. Dimension of representative stairs

Stairs Height [cm] Depth [cm]

30

60

100

Main NN

Sub NN

for hidden layer

Sub NN

for output layer

Δw , Δh

o

o

Δw , Δh

h

h

Sub NN

Input

Output

Fig. 8. A PNN used for experiments

environmental data. A robot concerns only kinematics in virtual environment

and ignores dynamics.

A CPG shown in Fig. 7 is used for controlling of a bipedal robot. We used

Matsuoka’s neural oscillator model [9] in a CPG. In this study, 16 connection

weights w and ﬁve constant external inputs u

are deﬁned as CPG input for

controlling a bipedal robot. CPG input for climbing stairs are given through

exploring their parameter space by GA and are optimized for each environment.

Internal parameters of CPG are also given by GA and are constant in all envi-

ronments because it takes much time to explore all CPG parameters including

internal parameters. Internal parameters of CPG are optimized for walking on

a horizontal plane.

The four pairs shown in Table 1 are deﬁned as representative data for NN

training. Then inputs and outputs of the NNs numbers 2 and 21 respectively.

The following targets are compared to evaluating their generalization

capability.

– CPG whose parameters are optimized from each of the three representative

environmental data, i.e., stairs A, B, and C

– MLP trained for stairs A, B, and C (MLP-I)

– MLP trained for stairs D after trained for stairs A, B, and C (MLP-II)

– PNN trained in the same way as the above MLP

These targets are optimized and trained for one to four kinds of stairs. General-

ization capability of each targets is calculated by the number of conditions which

is diﬀerent from the representative stairs and where a biped robot can climb ﬁve

402

E. Inohira, H. Oonishi, and H. Yokoi

stairs successfully. Stairs’ height ranges from 4 cm to 46 cm and width from 40

cm to 110 cm. MLPs has 30 neurons in a hidden layer. Initial weights of MLPs

are given by uniform random numbers ranging between

±0.3. PNN used in this

paper has two sub NNs as shown in Fig.8. Main NN in PNN is the same as the

above MLP. Sub NN for hidden layer has 100 neurons and 90 outputs. Sub NN

for output layer has 600 neurons and 561 outputs. All initial weights in PNN are

given in the same way as the MLPs.

One learning cycle is deﬁned as stairs A, B, and C are given to MLP or PNN

sequentially. MLP-I is trained for the three kinds of stairs until 10000 learning

cycles where sum of squared error is much less than 10

−7

. MLP-II is trained for

stairs D until 1000 learning cycles after trained for the three kinds of stairs. As

mentioned below, although the number of learning cycles for stairs D is small,

MLP-II forgets stair A, B, and C. Training condition for Main NN in PNN is

the same as MLP-I. Incremental learning of PNN for stairs D means that the

two sub NNs are trained for stairs D while the main NN is constant. These sub

NNs are trained until 700 learning cycles.

Learning rate of NNs is optimized through preliminary experiments because

their performance heavily depends on it. We used learning rate minimizing sum

of squared error under a certain number of learning cycles for each of NNs.

Learning rate used in MLP-I and sub NN of PNN is 0.30 and 0.12 respectively.

4.2

Experimental Results

In Fig. 9, mark x denotes successful condition in climbing ﬁve stairs and a

circle a given condition as representative dataset. Fig. 9 (a) to (c) show that

successful conditions spreads around representative stairs to some degree. It

means that CPG has a certain generalization capability by itself as already

known. However, generalization capability of CPG is not as much as stairs A,

B, and C are covered simultaneously. On the other hand, Fig. 9 (d) shows that

MLP-I covers intermediate conditions in stairs A, B, and C. Eﬀect of virtual

learning with NNs is clear. Fig. 9 (e) and (f) are involved in incremental learning.

Fig. 9 (e) shows that PNN is successful in incremental learning. Moreover, when

conditions near stairs C are focused on, generalization capability of PNN is larger

than MLP-I. Fig. 9 (f) shows that MLP-II forgot the precedent learning on stairs

A, B, and C and fails in incremental learning.

It is known that incremental learning of MLP with BP fails because connec-

tion weights are overwritten by training with new dataset. In PNN, main NN

is constant after training with initial dataset. Then main NN does not forget

initial dataset. Incremental learning is realized by sub NNs in PNN. The prob-

lems of sub NNs are eﬀects on adjusting of connection weights, i.e., whether it

is successful in incremental learning or not, and whether performance for ini-

tial dataset decreases or not. From the experimental results, we showed that

PNN realized incremental learning and increased generalization capability by

incremental learning.

PNNs for Incremental Learning in Virtual Learning System

403

100

Depth [cm]

Height [cm]

(a) CPG without NN for data A

100

Depth [cm]

Height [cm]

(b) CPG without NN for data B

100

Depth [cm]

Height [cm]

100

Depth [cm]

Height [cm]

(d) Trained NN with data A, B, and C

60

80

100

Depth [cm]

Height [cm]

(e) Trained proposed NN with data D

after the three data

100

Depth [cm]

Height [cm]

B

C

(f) Trained conventional NN with data D

after the three data

Fig. 9. A comparison of generalization capability of CPG and MLP and PNN in stair

climbing

404

E. Inohira, H. Oonishi, and H. Yokoi

Conclusions

We proposed a new type of NNs for incremental learning in a virtual learning

system. Our proposed NNs features adjusting weights and thresholds externally

to slightly change a mapping of a trained NN. This paper demonstrated numeri-

cal experiments with a two-dimensional ﬁve-link biped robot and climbing-stairs

task. We showed that PNN is successful in incremental learning and has gener-

alization capability to some degree.

This study is very limited to focus on only verifying our approach. In future

work, we will study PNN with as much data as an actual robot needs and

compare with related work quantitatively.

References

1. Hirai, K., Hirose, M., Haikawa, Y., Takenaka, T.: The development of honda hu-

manoid robot. In: Proc. IEEE ICRA, vol. 2, pp. 1321–1326 (1998)

2. Mahadevan, S., Connell, J.: Automatic programming of behavior-based robots using

reinforcement learning. Artiﬁcial Intelligence 55, 311–365 (1992)

3. Kuniyoshi, Y., Sangawa, S.: Early motor development from partially ordered neural-

body dynamics: experiments with a cortico-spinal-musculo-skeletal model. Biologi-

cal Cybernetics 95, 589–605 (2006)

4. Yamashita, I., Yokoi, H.: Control of a biped robot by using several virtual environ-

ments. In: Proceedings of the 22nd Annual Conference of the Robotics Society of

Japan 1K25 (in Japanese) (2004)

5. Kawano, T., Yamashita, I., Yokoi, H.: Control of the bipedal robot generating the

target by the simulation in virtual space (in Japanese). IEICE Technical Report 104,

65–69 (2004)

6. Haruno, M., Wolpert, D.M., Kawato, M.: MOSAIC model for sensorimotor learning

and control. Neural Computation 13, 2201–2220 (2001)

7. Schaal, S., Atkeson, C.G.: Constructive incremental learning from only local infor-

mation. Neural Computation 10, 2047–2084 (1998)

8. Yamauchi, K., Hayami, J.: Incremental learning and model selection for radial ba-

sis function network through sleep. IEICE TRANSACTIONS on Information and

Systems E90-D, 722–735 (2007)

9. Matsuoka, K.: Sustained oscillations generated by mutually inhibiting neurons with

adaptation. Biological Cybernetics 52, 367–376 (1985)

Bifurcations of Renormalization Dynamics in

Self-organizing Neural Networks

Peter Tiˇ

University of Birmingham, Birmingham, UK

p.tino@cs.bham.ac.uk

Abstract. Self-organizing neural networks (SONN) driven by softmax

weight renormalization are capable of ﬁnding high quality solutions of dif-

ﬁcult assignment optimization problems. The renormalization is shaped

by a temperature parameter - as the system cools down the assignment

weights become increasingly crisp. It has been reported that SONN

search process can exhibit complex adaptation patterns as the system

cools down. Moreover, there exists a critical temperature setting at which

SONN is capable of powerful intermittent search through a multitude of

high quality solutions represented as meta-stable states. To shed light

on such observed phenomena, we present a detailed bifurcation study of

the renormalization process. As SONN cools down, new renormalization

equilibria emerge in a strong structure leading to a complex skeleton of

saddle type equilibria surrounding an unstable maximum entropy point,

with decision enforcing “one-hot” stable equilibria. This, in synergy with

the SONN input driving process, can lead to sensitivity to annealing

schedules and adaptation dynamics exhibiting signatures of complex dy-

namical behavior. We also show that (as hypothesized in earlier studies)

the intermittent search by SONN can occur only at temperatures close

to the ﬁrst (symmetry breaking) bifurcation temperature.

Introduction

For almost three decades there has been an energetic research activity on ap-

plication of neural computation techniques in solving diﬃcult combinatorial

optimization problems. Self-organizing neural network (SONN) [1] constitutes

an example of a successful neural-based methodology for solving 0-1 assign-

ment problems. SONN has been successfully applied in a wide variety of ap-

plications, from assembly line sequencing to frequency assignment in mobile

communications.

As in most self-organizing systems, dynamics of SONN adaptation is driven

by a synergy of cooperation and competition. In the competition phase, for each

item to be assigned, the best candidate for the assignment is selected and the

corresponding assignment weight is increased. In the cooperation phase, the as-

signment weights of other candidates that were likely to be selected, but were

not quite as strong as the selected one, get increased as well, albeit to a lesser

M. Ishikawa et al. (Eds.): ICONIP 2007, Part I, LNCS 4984, pp. 405–414, 2008.

c Springer-Verlag Berlin Heidelberg 2008

406

P. Tiˇ

degree. The assignment weights need to be positive and sum to 1. Therefore,

after each SONN adaptation phase, the assignment weights need to be renor-

malized back onto the standard simplex e.g via the softmax function [2]. When

endowed with a physics-based Boltzmann distribution interpretation, the soft-

max function contains a temperature parameter

T > 0. As the system cools

down, the assignments become increasingly crisp. In the original setting SONN

is annealed so that a single high quality solution to an assignment problem is

found. Yet, renormalization onto the standard simplex is a double edged sword.

On one hand, SONN with assignment weight renormalization have empirically

shown sensitivity to annealing schedules, on the other hand, the quality of solu-

tions could be greatly improved [3].

Interestingly enough, it has been reported recently [4] that there exists a

critical temperature

∗

at which SONN is capable of powerful intermittent search

through a multitude of high quality solutions represented as meta-stable states of

the adaptation SONN dynamics. It is hypothesised that the critical temperature

may be closely related to the symmetry breaking bifurcation of equilibria in the

autonomous softmax dynamics.

At present there is still no theory regarding the dynamics of SONN adap-

tation driven by the softmax renormalization. Consequently, the processes of

crystallising a solution in an annealed version of SONN, or of sampling the so-

lution space in the intermittent search regime are far from being understood.

The ﬁrst steps towards theoretical underpinning of SONN adaptation driven

by softmax renormalization were taken in [5,4,6]. For example, in [5] SONN

is treated as a dynamical system with a bifurcation parameter

T . The co-

operation phase was not included in the model, The renormalization process

was empirically shown to result in complicated bifurcation patterns revealing

a complex nature of the search process inside SONN as the systems gets an-

nealed. More recently, Kwok and Smith [4] suggested to study SONN adapta-

tion dynamics by concentrating on the autonomous renormalization process,

since it is this process that underpins the search dynamics in the SONN. In

[6] we initiated a rigorous study of equilibria of the autonomous renormaliza-

tion process. Based on dynamical properties of the autonomous renormaliza-

tion, we found analytical approximations to the critical temperature

∗

as a

function of SONN size.

In this paper we complement [6] by reporting a detailed bifurcation study

of the renormalization process and give precise characterization and stability

types of equilibria, as they emerge during the annealing process. Interesting

and intricate equilibria structure emerges as the system cools down, explaining

empirically observed complexity of SONN adaptation during intermediate stages

of the annealing process. The analysis also clariﬁes why the intermittent search

by SONN occurs near the ﬁrst (symmetry breaking) bifurcation temperature of

the renormalization step, as was experimentally veriﬁed in [4,6]. Due to space

limitations, we cannot fully prove statements presented in this study. Detailed

proofs can be found in [7] and will be published elsewhere.

Bifurcations of Renormalization Dynamics in SONNs

407

Self-organizing Neural Network and Iterative Softmax

First, we brieﬂy introduce Self-Organizing Neural Network (SONN) endowed

with weight renormalization for solving assignment optimization problems (see

e.g. [4]). Consider a ﬁnite set of input elements (neurons)

i ∈ I = {1, 2, ..., M}

that need to be assigned to outputs (output neurons)

j ∈ J = {1, 2, ..., N}, so

that some global cost of an assignment

A : I → J is minimized. Partial cost of

assigning

i ∈ I to j ∈ J is denoted by V (i, j). The “strength” of assigning i to

j is represented by the “assignment weight” w

i,j

∈ (0, 1).

The SONN algorithm can be summarized as follows: The connection weights

i,j

i ∈ I, j ∈ J , are ﬁrst initialized to small random values. Then, repeatedly,

an output item

∈ J is chosen and the partial costs V (i, j

) incurred by

assigning all possible input elements

i ∈ I to j

are calculated in order to

select the “winner” input element (neuron)

i(j

)

∈ I that minimizes V (i, j

The “neighborhood”

(

i(j

)) of size

L of the winner node i(j

) consists of

nodes

i = i(j

) that yield the smallest partial costs

V (i, j

). Weights from nodes

i ∈ B

(

i(j

)) to

get strengthened:

i,j

← w

i,j

η(i)(1 − w

i,j

)

, i ∈ B

(

i(j

))

(1)

where

η(i) is proportional to the quality of assignment i → j

, as measured by

V (i, j

). Weights

= (

i,1

, w

i,2

, ..., w

i,N

) for each input node

i ∈ I are then

renormalized using softmax

i,j

←

exp(

i,j

)

k=1

exp(

i,k

)

(2)

We will refer to SONN for solving an (

M, N)-assignment problem as (M, N)-

SONN. As mentioned earlier, following [4,6] we strive to understand the search

dynamics inside SONN by analyzing the autonomous dynamics of the renormal-

ization update step (2) of the SONN algorithm.

The weight vector

of each of

M neurons in an (M, N)-SONN lives in the

standard (

N − 1)-simplex,

N−1

{w = (w

, w

, ..., w

)

∈ R

| w

≥ 0, i = 1, 2, ..., N, and

i=1

= 1

Given a value of the temperature parameter

T > 0, the softmax renormalization

step in SONN adaptation transforms the weight vector of each unit as follows:

w → F(w; T ) = (F

(

w; T ), F

(

w; T ), ..., F

(

w; T )) ,

(3)

where

(

w; T ) =

exp(

)

Z(w; T )

, i = 1, 2, ..., N,

(4)

Here

denotes the transpose operator.

408

P. Tiˇ

and

Z(w; T ) =

k=1

exp(

) is the normalization factor. Formally,

F maps R

N−1

, the interior of

N−1

Linearization of

F around w ∈ S

N−1

is given by the Jacobian

J(w; T ):

J(w; T )

i,j

[

i,j

(

w; T ) − F

(

w; T )F

(

w; T )], i, j = 1, 2, ..., N,

(5)

where

i,j

= 1 iﬀ

i = j and δ

i,j

= 0 otherwise.

The softmax map

F induces on S

N−1

a discrete time dynamics known as

Iterative Softmax (ISM):

w(t + 1) = F(w(t); T ).

(6)

The renormalization step in an (

M, N)-SONN adaptation involves M sepa-

rate renormalizations of weight vectors of all of the

M SONN units. For each

temperature setting

T , the structure of equilibria in the i-th system, w

(

t + 1) =

F(w

(

t); T ), gets copied in all the other M − 1 systems. Using this symmetry, it

is suﬃcient to concentrate on a single ISM (6). Note that the weights of diﬀer-

ent units are coupled by the SONN adaptation step (1). We will study systems

for

N ≥ 2.

Equilibria of SONN Renormalization Step

We ﬁrst introduce basic concepts and notation that will be used throughout the

paper. An (

r − 1)-simplex is the convex hull of a set of r aﬃnely independent

points in

m

,

m ≥ r−1. A special case is the standard (N−1)-simplex S

N−1

. The

convex hull of any nonempty subset of

n vertices of an (r − 1)-simplex Δ, n ≤ r,

is called an (

n − 1)-face of Δ. There are

distinct (

n − 1)-faces of Δ and each

(

n − 1)-face is an (n − 1)-simplex. Given a set of n vertices w

, w

, ..., w

∈ R

deﬁning an (

n − 1)-simplex Δ in R

, the central point,

w(Δ) =

i=1

(7)

is called the maximum entropy point of

Δ.

We will denote the set of all (

n − 1)-faces of the standard (N − 1)-simplex

N−1

N,n

. The set of their maximum entropy points is denoted by

N,n

, i.e.

N,n

{w(Δ)| Δ ∈ P

N,n

}.

(8)

The

n-dimensional column vectors of 1’s and 0’s are denoted by 1

and

respectively. Note that

N,n

(

, 0

N−n

)

∈ Q

N,n

. In addition, all the other

elements of

N,n

can be obtained by simply permuting coordinates of

N,n

. Due

to this symmetry, we will be able to develop most of the material using

N,n

only

and then transfer the results to permutations of

N,n

. The maximum entropy

point

N,N

−1

of the standard (

N − 1)-simplex S

N−1

will be denoted

Bifurcations of Renormalization Dynamics in SONNs

409

simply by

w. To simplify the notation we will use w to denote both the maximum

entropy point of

N−1

and the vector

w − 0

We showed in [6] that

w is a ﬁxed point of ISM (6) for any temperature setting

T and all the other ﬁxed points w = (w

, w

, ..., w

) of ISM have exactly two

diﬀerent coordinate values:

∈ {γ

, γ

}, such that N

−1

< γ

1

< N

−1

1

and

0

< γ

2

< N

−1

, where

is the number of coordinates

larger than

−1

. Since

w ∈ S

N−1

, we have

− N

N − N

(9)

The number of coordinates

2

smaller than

−1

is denoted by

. Obviously,

N − N

. If

w = (γ

, γ

) is a ﬁxed point of ISM (6), so are all

N

1

distinct permutations of it. We collect

w and its permutations in a set

N,N

(

) =

v| v is a permutation of γ

− N

N − N

N−N

. (10)

The ﬁxed points in

N,N

(

) exist if and only if the temperature parameter

is set to [6]

N,N

(

) = (

Nγ

− 1) −(N − N

)

· ln 1 −

Nγ

− 1

(

N − N

)

−1

(11)

We will show that as the system cools down, increasing number of equilibria

emerge in a strong structure. Let

w, v ∈ S

N−1

be two points on the standard

simplex. The line from

w to v is parametrized as

(

τ; w, v) = w + τ · (v − w), τ ∈ [0, 1].

(12)

Theorem 1. All equilibria of ISM (6) lie on lines connecting the maximum

entropy point

w of S

N−1

with the maximum entropy points of its faces. In par-

ticular, for 0

< N

1

< N and γ

∈ (N

−1

, N

−1

), all ﬁxed points from

N,N

(

)

lie on lines (

τ; w, w), where w ∈ Q

N,N

Sketch of the Proof:

Consider the maximum entropy point

N,N

(

, 0

) of an (

−1)-face

N−1

. Then

w(γ

) = (

, γ

) lies on the line (

τ; w, w

N,N

) for the

parameter setting

τ = 1 − Nγ

.

Q.E.D.

The result is illustrated in ﬁgure 1. As the (

M, N)-SONN cools down, the ISM

equilibria emerge on lines connecting

w with the maximum entropy points of

faces of

N−1

of increasing dimensionality. Moreover, on each such line there

can be at most two ISM equilibria.

Theorem 2. For N

1

< N/2, there exists a temperature T

(

N, N

)

> N

−1

such

that for

T ∈ (0, T

(

N, N

)], ISM ﬁxed points in

N,N

(

) exist for some

1

∈

410

P. Tiˇ

Fig. 1. Positions of equilibria of SONN renormalization illustrated for the case of

4-dimensional weight vectors w. ISM is operating on the standard 3-simplex

and

its equilibria can only be found on the lines connecting the maximum entropy point

w (ﬁlled circle) with maximum entropy points of its faces. Triangles, squares and

diamonds represent maximum entropy points of 0-faces (vertices), 1-faces (edges) and

2-faces (facets), respectively.

(

−1

, N

−1

), and no ISM ﬁxed points in

N,N

(

), for any

1

∈ (N

−1

, N

−1

can exist at temperatures

T > T

(

N, N

For each temperature

T ∈ (N

−1

, T

(

N, N

)), there are two coordinate val-

ues

γ

−

(

T ) and γ

(

T ), N

−1

< γ

−

1

(

T ) < γ

(

T ) < N

−1

, such that ISM ﬁxed

points in both

N,N

(

−

(

T )) and E

N,N

(

T )) exist at temperature T . Further-

more, as the temperature decreases,

−

1

(

T ) decreases towards N

−1

, while

(

T )

increases towards

−1

. For temperatures

T ∈ (0, N

−1

], there is exactly one

(

T ) ∈ (N

−1

, N

−1

) such that ISM equilibria in

N,N

(

T )) exist at tempera-

ture

T .

Sketch of the Proof:

The temperature function

N,N

(

) (11) is concave and can be continuously

extended to [

−1

, N

−1

) with

N,N

(

−1

) =

−1

and lim

→N

−1

N,N

(

) =

0

< N

−1

. The slope of

N,N

(

) at

−1

is positive for

1

< N/2.

Q.E.D.

Theorem 3. The bifurcation temperature T

(

N, N

) is decreasing with increas-

ing number

of equilibrium coordinates larger than

−1

Sketch of the Proof:

It can be shown that for any feasible value of

> N

−1

, if there are two

ﬁxed points

w ∈ E

N,N

(

) and

w ∈ E

N,N

(

) of ISM, such that

1

<

, then

w exists at a higher temperature than w does. For a given N

1

<

N/2, the bifurcation temperature T

(

N, N

) corresponds to the maximum of

N,N

(

) on

∈ (N

−1

, N

−1

). It follows that

1

< N

implies

(

N, N

)

(

N, N

Q.E.D.

Bifurcations of Renormalization Dynamics in SONNs

411

Theorem 4. If N/2 ≤ N

1

< N, for each temperature T ∈ (0, N

−1

), there is

exactly one coordinate value

(

T ) ∈ (N

−1

, N

−1

), such that ISM ﬁxed points

N,N

(

T )) exist at temperature T . No ISM ﬁxed points in E

N,N

(

), for

any

∈ (N

−1

, N

−1

) can exist for temperatures

T > N

−1

. As the temperature

decreases,

(

T ) increases towards N

−1

1

.

Sketch of the Proof:

Similar to the proof of theorem 2, but this time the slope of

N,N

(

) at

−1

is not positive.

Q.E.D.

Let us now summarize the process of creation of new ISM equilibria, as the

(

M, N)-SONN cools down. For temperatures T > 1/2, the ISM has exactly one

equilibrium - the maximum entropy point

w of S

N−1

[6]. As the temperature is

lowered and hits the ﬁrst bifurcation point,

(

N, 1), new ﬁxed points of ISM

emerge on the lines (

τ; w, w), w ∈ Q

N,1

, one on each line. The lines connect

with the vertices

w of S

N−1

. As the temperature decreases further, on each line,

the single ﬁxed point splits into two ﬁxed points, one moves towards

w, the other

moves towards the corresponding high entropy point

w in Q

N,1

(vertex of

N−1

When the temperature reaches the second bifurcation point,

E

(

N, 2), new ﬁxed

points of ISM emerge on the lines (

τ; w, w), w ∈ Q

N,2

, one on each line. This

time the lines connect

w with the maximum entropy points (midpoints) w of the

edges of

N−1

. Again, as the temperature continues decreasing, on each line, the

single ﬁxed point splits into two ﬁxed points, one moves towards

w, the other

moves towards the corresponding maximum entropy point

w in Q

N,2

(midpoint

of an edge of

N−1

). The process continues until the last bifurcation temperature

(

N, N

) is reached, where

1

is the largest natural number smaller than

N/2. At T

(

N, N

), new ﬁxed points of ISM emerge on the lines (

τ; w, w),

w ∈ Q

N,N

, connecting

w with maximum entropy points w of (N

− 1)-faces

N−1

. As the temperature continues decreasing, on each line, the single ﬁxed

point splits into two ﬁxed points, one moves towards

w, the other moves towards

the corresponding maximum entropy point

w in Q

N,N

. At temperatures below

−1

, only the ﬁxed points moving towards the maximum entropy points of faces

N−1

exist.

In the low temperature regime, 0

< T < N

−1

, a ﬁxed point occurs on every

line (

τ; w, w), w ∈ Q

N,N

1

,

N/2 , N/2 + 1, ..., N − 1. Here, x denotes

the smallest integer

y, such that y ≥ x. As the temperature decreases, the ﬁxed

points

w move towards the corresponding maximum entropy points w ∈ Q

N,N

of (

− 1)-faces of S

N−1

The process of creation of new ﬁxed points and their ﬂow as the temperature

cools down is demonstrated in ﬁgure 2 for an ISM operating on 9-simplex

(

N = 10). We plot against each temperature setting T the values of the larger

coordinate

> N

−1

= 0

.1 of the ﬁxed points existing at T .

The behavior of ISM in the neighborhood of its equilibrium

w is given by the

structure of stable and unstable manifolds of the linearized system at

w outlined

in the next section.

412

P. Tiˇ

0.05

0.1

0.15

0.2

0.25

0.2

0.4

0.6

0.8

gamma

temperature T

Bifurcation structure of ISM equilibria (N=10)

(10,2)

(10,1)

(10,4)

(10,3)

Fig. 2. Demonstration of the process of creation of new ISM ﬁxed points and their

ﬂow as the system temperature cools down. Here

N = 10, i.e. the ISM operates on the

standard 9-simplex

. Against each temperature setting

T , the values of the larger

coordinate

> N

−1

of the ﬁxed points existing at

T are plotted. The horizontal bold

line corresponds to the maximum entropy point w = 10

−1

1

10

Stability Analysis of Renormalization Equilibria

The maximum entropy point

w is not only a ﬁxed point of ISM (6), but also,

regarded as a vector

w − 0

, it is an eigenvector of the Jacobian

J(w; T )

at any

w ∈ S

N−1

, with eigenvalue

λ = 0. This simply reﬂects the fact that

ISM renormalization acts on the standard simplex

N−1

, which is a subset of a

(

N − 1)-dimensional hyperplane with normal vector 1

. We have already seen

that

w plays a special role in the ISM equilibria structure: all equilibria lie on

lines going from

w towards maximum entropy points of faces of S

N−1

. The lines

themselves are of special interest, since we will show that these lines are in-

variant manifolds of the ISM renormalization and their directional vectors are

eigenvectors of ISM Jacobians at the ﬁxed points located on them.

Theorem 5. Consider ISM (6) and 1 ≤ N

1

< N. Then for each maximum

entropy point

w ∈ Q

N,N

of an (

− 1)-face of S

N−1

, the line

(

τ; w, w),

τ ∈ [0, 1) connecting the maximum entropy point w with w is an invariant set

under the ISM dynamics.

Sketch of the Proof:

The result follows from plugging parametrization (

τ; w, w) into (3) and realizing

(after some manipulation) that for each

τ ∈ [0, 1), there exists a parameter

setting

∈ [0, 1) such that F( (τ; w, w)) = (τ

;

w, w).

Q.E.D.

Bifurcations of Renormalization Dynamics in SONNs

413

The proofs of the next two theorems are rather involved and we refer the

interested reader to [7].

Theorem 6. Let w ∈ E

N,N

(

) be a ﬁxed point of ISM (6). Then,

∗

=

w−w

is an eigenvector of the Jacobian

J(w; T

N,N

(

)) with the corresponding eigen-

value

λ

∗

, where

1. if

N/2 ≤ N

≤ N − 1, then 0 < λ

∗

< 1.

2. if 1

≤ N

1

< N/2 and N

−1

< γ

1

< (2N

)

−1

, then

∗

> 1.

3. if 1

≤ N

1

< N/2 , then there exists ¯γ

∈ ((2N

)

−1

, N

−1

), such that for all

ISM ﬁxed points

w ∈ E

N,N

(

) with

∈ (¯γ

, N

−1

), 0

< λ

∗

< 1.

We have established that for an ISM equilibrium

w, both w and w

∗

=

w−w are

eigenvectors of the ISM Jacobian at

w. Stability types of the remaining N − 2

eigendirections are characterized in the next theorem.

Theorem 7. Consider an ISM ﬁxed point w ∈ E

N,N

1

(

) for some 1

≤ N

1

< N

and

N

−1

< γ

1

< N

−1

1

. Then, there are

N − N

− 1 and N

− 1 eigenvectors

of Jacobian

J(w; T

N,N

(

)) of ISM at

w with the same associated eigenvalue

0

< λ

−

< 1 and λ

> 1, respectively.

Discussion – SONN Adaptation Dynamics

In the intermittent search regime by SONN [4], the search is driven by pulling

promising solutions temporarily to the vicinity of the 0-1 “one-hot” assignment

values - vertices of

N−1

(0-dimensional faces of the standard simplex

N−1

The critical temperature for intermittent search should correspond to the case

where the attractive forces already exist in the form of attractive equilibria near

the “one-hot” assignment suggestions (vertices of

N−1

), but the convergence

rates towards such equilibria should be suﬃciently weak so that the intermittent

character of the search is not destroyed. This occurs at temperatures lower than,

but close to the ﬁrst bifurcation temperature

E

(

N, 1) (for more details, see [7]).

In [4] it is hypothesised that there is a strong link between the critical tem-

perature for intermittent search by SONN and bifurcation temperatures of the

autonomous ISM. In [6] we hypothesised (in accordance with [4]) that even

though there are many potential ISM equilibria, the critical bifurcation points

are related only to equilibria near the vertices of

N−1

, as only those could be

guaranteed by the theory of [6] (stability bounds) to be stable, even though the

theory did not prevent the other equilibria from being stable. In this study, we

have rigorously shown that the stable equilibria can in fact exist only near the

vertices of

N−1

, on the lines connecting

w with the vertices. Only when N

= 1,

there are no expansive eigendirections of the local Jacobian with

> 1.

As the SONN system cools down, more and more ISM equilibria emerge on the

lines connecting the maximum entropy point

w of the standard simplex S

N−1

with the maximum entropy points of its faces of increasing dimensionality. With

decreasing temperature, the dimensionality of stable and unstable manifolds

414

P. Tiˇ

of linearized ISM at emerging equilibria decreases and increases, respectively.

At lower temperatures, this creates a peculiar pattern of saddle type equilibria

surrounding the unstable maximum entropy point

w, with decision enforcing

“one-hot” stable equilibria located near vertices of

N−1

. Trajectory towards

the solution as the SONN system anneals is shaped by the complex skeleton of

saddle type equilibria with stable/unstable manifolds of varying dimensionalities

and can therefore, in synergy with the input driving process, exhibit signatures of

a very complex dynamical behavior, as reported e.g. in [5]. Once the temperature

is suﬃciently low, the attraction rates of stable equilibria near the vertices of

N−1

are so high that the found solution is virtually pinned down by the system.

Even though the present study clariﬁes the prominent role of the ﬁrst (sym-

metry breaking) bifurcation temperature

(

N, 1) in obtaining the SONN in-

termittent search regime and helps to understand the origin of complex SONN

adaptation patterns in the annealing regime, many interesting open questions

remain. For example, no theory as yet exists of the role of abstract neighborhood

(

i(j

)) of the winner node

i(j

c

) in the cooperative phase of SONN adaptation.

We conclude by noting that it may be possible to apply the theory of ISM in

other assignment optimization systems that incorporate the softmax assignment

weight renormalization e.g. [8,9].

References

1. Smith, K., Palaniswami, M., Krishnamoorthy, M.: Neural techniques for combina-

torial optimization with applications. IEEE Transactions on Neural Networks 9,

1301–1318 (1998)

2. Guerrero, F., Lozano, S., Smith, K., Canca, D., Kwok, T.: Manufacturing cell

formation using a new self-organizing neural network. Computers & Industrial

Engineering 42, 377–382 (2002)

3. Kwok, T., Smith, K.: Improving the optimisation properties of a self-organising

neural network with weight normalisation. In: Proceedings of the ICSC Symposia

on Intelligent Systems and Applications (ISA 2000), Paper No.1513-285 (2000)

4. Kwok, T., Smith, K.: Optimization via intermittency with a self-organizing neural

network. Neural Computation 17, 2454–2481 (2005)

5. Kwok, T., Smith, K.: A noisy self-organizing neural network with bifurcation dy-

namics for combinatorial optimization. IEEE Transactions on Neural Networks 15,

84–88 (2004)

6. Tiˇ

no, P.: Equilibria of iterative softmax and critical temperatures for intermit-

tent search in self-organizing neural networks. Neural Computation 19, 1056–1081

(2007)

7. Tiˇ

no, P.: Bifurcation structure of equilibria of adaptation dynamics in self-

organizing neural networks. Technical Report CSRP-07-12, University of Birm-

ingham, School of Computer Science (2007),

http://www.cs.bham.ac.uk/

∼

pxt/PAPERS/ism.bifurc.tr.pdf

8. Gold, S., Rangarajan, A.: Softmax to softassign: Neural network algorithms for

combinatorial optimization. Journal of Artiﬁcial Neural Networks 2, 381–399

(1996)

9. Rangarajan, A.: Self-annealing and self-annihilation: unifying deterministic anneal-

ing and relaxation labeling. Pattern Recognition 33, 635–649 (2000)

M. Ishikawa et al. (Eds.): ICONIP 2007, Part I, LNCS 4984, pp. 415–425, 2008.

Download 12.42 Mb.

Do'stlaringiz bilan baham:

1 ... 32 33 34 35 36 37 38 39 ... 88