Neural Networks: Advanced

Dokuz Eylül University Computer Engineering Department

25 September 2000 – 12 January 2001

□ Contents:

• Introduction – What are Neural Networks?

– Why Neural Networks?

• Feed Forward Neural Networks

– Specification of the weight by ∗ Back Propagation Algorithm ∗ Genetic Algorithm

• Free Connected Neural Networks – Toy model with three neurons

(Neural Networks: Advanced) 3

□ What is Neural Network?

A system with neurons connected with synapses,

where

• synapse: transmits input state value (usually either one or zero) with its weight value being multiplied to the input; and

• neuron: takes the weighted sum of fan-in inputs, and outputs its function value of the specified transfer function f(x).

Typically categorized into two forms:

1. Layered (feed forward)

2. Fully-connected

Keywords:

• neuron, synapse, weight, transfer-function, layered, feed-forward, fully-connected

(Neural Networks: Advanced) 4

□ Perceptron:

An example of single-layered feed forward neural network.

Suppose:

• M inputs: x_{1}, ⋯ x_{M};

• N outputs: y_{1}, ⋯ y_{N};

• each N output neurons are connected with all M input neurons;

• weight values (of the synapse) from (input) neuron j to (output) neuron k is w_{jk};

then

y_{i} = f( N ; ∑ ; k=1 w_{ki}x_{k}),  (1)

where

f(x) = sgn(x) or f(x) = tan^{−1}(x).  (2)

Keywords:

• perceptron □ The simplest example.

1. AND with two inputs and one output e.g.,

∗ w_{00} = w_{01} = 0.7

2. How about OR?

e.g.,

∗ w_{00} = w_{01} = 1.4

3. How about XOR?

– Impossible by single layer perceptron.

Keywords:

• synaptic plasticity

(Neural Networks: Advanced) 6

□ Perceptron with hidden layers

Adding intermediate layer(s) called hidden layer(s) between input and output.

• Suppose K hidden layers.

• weight from neuron i of the k-th layer to neuron j of the next layer is denoted as w_{ij}^{k}.

• XOR revisited e.g.,

∗ w_{00}^{0} = w_{01}^{0} = 0.7, w_{10}^{0} = w_{11}^{0} = 1.4,

w_{10}^{1} = −1.4, w_{11}^{1} = 1.4.

• Separability

– If we can separate the solution space by hyperplane, (To be more specific, we can separate 2D solution space of 2-input AND/OR by a straight line, but not for XOR.)

then we can solve the problem by single perceptron.

– Multi-layer allows us to separate the space by more flexible surface, not necessarily the plane.

Keywords:

• hidden layer, separability, solution-space

(Neural Networks: Advanced) 7

□ Back Propagation Algorithm

Definition of variables:

• L layers of neurons.

• k_{r} neurons in the r-th layer. r = 1, 2, ⋯, L.

• l input neurons (k_{0} = l).

• w_{jk}^{r}: weight to the j-th neuron in the r-th layer from the k-th neuron in the previous layer.

• N training pairs: (x(i), y(i)), i = 1, 2, ⋯, N.

• y_{k}^{r}(i): the output of the k-th neuron in the r-th layer when the i-th training sample is given.

• fan-in’s to j-th neuron in the r-th layer when the i-th training sample is given.

h_{j}^{r}(i) ≡ k_{r−1} ; ∑ ; k=1 w_{jk}^{r}y_{k}^{r−1}(i) + w_{j0}^{r} = k_{r−1} ; ∑ ; k=0 w_{jk}^{r}y_{k}^{r−1}(i),

where y_{0}^{r−1} = 1 and

(y_{1}^{0}(i), ⋯, y_{l}^{0}(i)) = (x_{1}(i), ⋯, x_{l}(i)) = x(i).

• Each output neuron’s error:

e_{m}(i) ≡ y_{m}(i) − ŷ_{m}(i), i = 1, 2, ⋯, N. where (ŷ_{1}(i), ⋯, ŷ_{k_{L}}(i)) = y(i)

• Error function to be minimized:

D = \frac{1}{2} N ; ∑ ; i=1 k_{L} ; ∑ ; m=1 e_{m}(i)^{2}

(Neural Networks: Advanced) 8

The algorithm:

1. Initialization: Initialize all the weights with small random values.

2. Forward computations: For each of the training vectors

x(i), i = 1, 2, ⋯, N compute all the

y_{j}^{r}(i) = f(h_{j}^{r}(i)) for j = 1, 2, ⋯, k_{r} and r = 1, 2, ⋯, L.

3. Backward computations: For each i = 1, 2, ⋯, N, and

j = 1, 2, ⋯, k_{L} compute

δ_{j}^{L}(i) = e_{j}(i)f′(h_{j}^{L}(i)) then compute

δ_{j}^{r−1}(i) = e_{j}^{r−1}(i)f′(h_{j}^{r−1}(i)) for r = L, L − 1, ⋯, 2 and j = 1, 2, ⋯, k_{r} where

e_{j}^{r−1}(i) = k_{r} ; ∑ ; k=1 δ_{k}^{r}(i)w_{kj}^{r}

4. Update the weights for r = 1, 2, ⋯, L and j = 1, 2, ⋯, k_{r}

w_{jk}^{r} [new] = w_{jk}^{r} [old] + △w_{jk}^{r}, where

△w_{jk}^{r} = −ϵ N ; ∑ ; i=1 δ_{j}^{r}(i)y_{k}^{r−1}(i).

(Neural Networks: Advanced) 9

Rationale:

From the gradient descent’s principle,

△w_{jk}^{r} = −ϵ\frac{∂D}{∂w_{jk}^{r}}  (3)

where

D = N ; ∑ ; i=1 ε(i)  (4)

and

ε(i) = \frac{1}{2} N ; ∑ ; i=1 k_{L} ; ∑ ; m=1 e_{m}(i)^{2}  (5)
= \frac{1}{2} N ; ∑ ; i=1 k_{L} ; ∑ ; m=1(y_{m}(i) − ŷ_{m}(i))^{2}.  (6)

Hence

\frac{∂ε(i)}{∂w_{jk}^{r}} = \frac{∂ε(i)}{∂h_{j}^{r}} \frac{∂h_{j}^{r}}{∂w_{jk}^{r}}.  (7)

Here we define

\frac{∂ε(i)}{∂h_{j}^{r}} ≡ δ_{j}^{r}(i).  (8)

Then

△w_{jk}^{r} = −ϵ r ; ∑ ; i=1(i)δ_{j}^{r}(i)y_{k}^{r−1}(i).  (9)

□ Genetic Algorithm (GA)

An example:

• Neural network with 100 input neurons and 10 output neurons with no hidden layer:

– hand-written-characters of the figures from zero to nine drawn on the 10x10 pixels are to be recognized

– by activating only the i-th neuron of the output remaining other neurons not activated.

From a biological analogy, the followings are defined.

Chromosome: Each chromosome is comprised of 1000 genes, representing 1000 weights of one individual neural network.

Population:

A number of individuals, say 100, create a population.

Initialization: All genes of all chromosomes are initialized at random, taking a value ranging from zero to one. This construct the first generation.

(cont’d)

Fitness:

The ability of each individual is evaluated and assigned its fitness value. In our current problem, for example, each individual given a set of weights is evaluated by giving each output neuron 0.1 if the output is correct and 0 otherwise. Note that in the first generation, every individual performs rather badly but diferrently, since weights are determined at random.

Selection: Two parents are selected to produce one offspring. Individuals of better performance should be more likely to be selected. For example, (1) selection is always from upper half of the population in which individuals have been sorted with an order of their fitness, or (2) selection is made sot that the probability is proportional to the fitness value. The production of an offspring is by employing the following two operations: crossover and mutation

Crossover: A same position of the two parent chromosomes are determined at random (each time when they are selected), and cross them over.

Mutation: For each gene of the offspring chromosome, produce one integer random number from 0 to 99. If the value is zero, then the gene is replaced with the other weight value also created at random each time.

Algorithm:

1. Initialization: Initialize all the weight values of all the individuals in the first generation at random so that it lies on [0, 1].

2. Evaluation: Evaluate fitness of all the individuals of the population.

3. Reproduction:

(1) Select two parents from the population.

(2) Crossover the two parents and produce one offspring.

(3) Mutate the offspring.

(4) Repeat (1) to (3) above until new generation of same size is obtained.

4. Repeat 2. to 3. above until the perfect solution is obtained or prespecified generations is reached.

(Neural Networks: Advanced) 13

□ Associative Memory as a Dynamical System

(Neural Networks: Advanced) 14

□ A category of trajectories

(Neural Networks: Advanced) 15

□ State Transition

s_{i}(t + 1) = sgn ( N ; ∑ ; j≠i w_{ij} · s_{j}(t) ) .

Example 1

An example of state transition in the above toy example:

s_{1}(1) = sgn ( w_{11} · s_{1}(0) + w_{12} · s_{2}(0) + w_{13} · s_{3}(0) )
= sgn ( 0.14 · 1 + (−0.34) · 1 + (−0.52) · 1 )
= −1

Example 2

□ Example 3 □ Hebbian Weights

w_{ij} = \frac{1}{N} p ; ∑ ; ν=1 ξ_{i}^{ν}ξ_{j}^{ν} (i ≠ j), w_{ii} = 0.

• In the above toy example:

( \begin{matrix}0 & 0.11 & 0.11 \\ 0.11 & 0 & 0.11 \\ 0.11 & 0.11 & 0 \end{matrix} )

• An interpretation of Hebb’s rule:

– A strong weight affects neurons at both ends to be same states.

• Many other solutions of a weight configuration to store a same set of patterns exist.

– Each

∗ can recall from · partial information; · incorrect information

∗ but has a different · basin of attraction; · storage capacity.

(Neural Networks: Advanced) 19

□ The Other Topics of Associative Memory

• Memory of a set of Motion Pictures

w_{ij} = \frac{1}{N} p ; ∑ ; μ=1 ξ_{i}^{μ+1}ξ_{j}^{μ}.  (10)

• How to forget already stored patterns?

w_{ij} = w_{ij} − \frac{λ}{N} ξ_{i}ξ_{j}.  (11)

e.g., repeat equation(11) 1000 times with λ = 0.01.

• Storage capacity (How many patterns can be stored?)

· Under Hebb’s rule

p/N < 0.138  (12)

· E. Gardner asserts (1988).

p/N < 2  (13)

(Neural Networks: Advanced) 20

In order to obtain p/N ≈ 2: · ξ_{i}^{μ} and ∑_{j} w_{ij}ξ_{j}^{μ} should be a same sign for all μ = 1, ⋯, p (then all stored memories are stable.) · So,

ξ_{i}^{μ} · _{j}^{∑} w_{ij}ξ_{j}^{μ} > 0.  (14)

or more preferably

ξ_{i}^{μ} · _{j}^{∑} w_{ij}ξ_{j}^{μ} > (κ > 0).  (15)

(the bigger κ, the more stable)

· Algorithm for obtaining p/N ≈ 2:

IF ∑_{j} w_{ij}ξ_{j}^{μ} ≠ 1 for ∀μ (κ = 1)

THEN w_{ij} = w_{ij} + δw_{ij} where

δw_{ij} = \frac{1}{N} ξ_{i}^{μ}ξ_{j}^{μ}(1 − δ_{ij}) · θ(κ − γ_{i}^{μ})  (16)
γ_{i}^{μ} = \frac{∑_{j} w_{ij}ξ_{i}^{μ}ξ_{j}^{μ}}{∑_{j}(w_{ij})^{2}}  (17)

(Neural Networks: Advanced) 21

• How can we observe phenomena?

1) By displaying S_{i}(t) at every update time t = n△t (n = 1, 2, ⋯) on a PC screen.

2) By plotting Hamming distances from initial input.

3) By plotting a similarity measure of S_{i}(t) to the initial input.

m^{μ}(t) = \frac{1}{N} N ; ∑ ; i=1 ξ_{i}^{μ}S_{i}^{μ}(t).  (18)

Try each of the above three methods

· Fixed Points starting with one of stored patterns that is given some noises (1);

· Convergence to Stored Pattern

starting with non-noisy one of stored patterns (1)-(3); · Chaotic Trajectory

starting with random initial state under symmetric random weights (2) or (3);

· Trajectory to Spingrass Atractor same as above but under asymmetric random weights (2) or (3);

· Motion Picture

– observing equation (refeq:motion) (2) or (3).

• How appropriate a configuraition of weights is?

f = p ; ∑ ; μ=1 t_{0} ; ∑ ; t=1 m^{μ}(t)  (19)

□ Home work

• Using fully connected neural networks – with 200 neuronsl;

– with p random^{1} patterns stored by Hebb’s rule;

– with equal probability of 1 and –1 in patterns.^{2}

(1) Study capcity dependency on the number of patterns stored. e.g., f (y-axis) vs. p (x-axis)

(2) Study size of basin of attraction’s dependency on the number of patterns stored. e.g., f (y-axis) vs. #-of-noises (x-axis) with parameter p.

1To produce integer random number, e.g., my random number(int n)

{ r1=(double)rand(); r2=(double)n; r=(int)((r1/RAD MAX)*r2); return(r); }

2We use random binary patterns, but reproducibility of these random patterns is preferable. So, for example:

# define SEED ⋯ randomize()

{ srand(SEED); } ⋯ main()

{ ⋯ randomize(); generate pattenrs(); ⋯ }

(Neural Networks: Advanced) 23

Chapter 3 Solving Combinatorial Problem

by Neural Networks

□ Solving Combinatorial Problem

• The fully connected neural network model so far we’ve studied can also solve combinatorial problems.

e.g.

(1) Multiflop problem:

∗ Only one out of n neurons is on with all the others off at a moment.

∗ When all weight values are −2, · a unit that is set to 1 inhibits the other units; or · if the network is started with all neurons set to zero, then the excitation of every neuron is zero, which makes the first neuron to be asynchronously selected flip its state to 1 and no other neuron can change its state after this first neuron has been set to 1

(2) The eight rooks problem: ∗ A generalization of multiflop;

∗ If the connection of each neuron to other neurons in the same row or column have the weight −2, all others have a weight zero and all neurons have the threshold −1, then · Any neuron set to 1 inhibits any other neurons in the same row or column; or · if a row or column is all set to 0 when one of its neuron is selected it will immediately switch its state to 1

(Neural Networks: Advanced) 25

(3) The eight queens problem: ∗ A generalization of eight rooks problem,

∗ taking diagonal lines into consideration too.

∗ This, however, does not always work due to many local minima. surrounding the solution

⇓

using stocastic (probabilistic) neurons

(Neural Networks: Advanced) 26

□ A new scheme.

• Stochastic Neurons: Instead of using deterministic neurons where

S_{i}(t + 1) = sgn(N ; ∑ ; j w_{ij}S_{j}(t))  (20)

stochastic neurons where

P r(S_{i}(t + 1)) = f(N ; ∑ ; j w_{ij}S_{j}(t))  (21)

are employed, in which

f(x) = \frac{1}{1 + exp(−2\frac{x}{T})}  (22)

and T is called temperature.

• Energy: A quantity called energy is defined corresponding to a configuration of the states of neurons as

E(t) = −\frac{1}{2} i≠j ; ∑ ; ij w_{ij}S_{i}(t)S_{j}(t))  (23)

and network state changes so that E(t) minimizes.

Definition 1 (Boltzman machine) A Boltzman machine is a Hopfield network composed of n neurons with states x_{1} ⋯ x_{n}. The state of neuron i is updated asynchronously according to the rule

x_{i} = \{ \begin{matrix}1 & with probability & p_{i} \\ 0 & with probability & 1 − p_{i} \end{matrix}  (24)

where

p_{i} = \frac{1}{1 + exp\{(− n ; ∑ ; j=1 w_{ij}x_{j} − θ_{i})/T \}}  (25)

and T is a positive temperature constant and θ_{i} is the threshold of the neurons. Then the energy is defined as:

E = −1/2 _{i}^{∑} _{j}^{∑} w_{ij}x_{i}x_{j} + _{i}^{∑} θ_{i}x_{i}  (26)

Note that if T is very small p_{i} ≈ 1 for _{i}^{∑} w_{ij}x_{j} − θ_{i} is positive and p_{i} ≈ 0 for negative.

• Examples

– the smallest hopfield network — the flip-flop

two neurons with

w_{12} = w_{21} = −1, w_{11} = w_{22} = 0,

θ_{i} = −0.5
⇓
E_{00} = E_{11} = 0, E_{01} = E_{10} = −0.5

(Neural Networks: Advanced) 28

– the multi-flop

E = ( n ; ∑ ; i=1 x_{i} − 1)^{2}
= n ; ∑ ; i=1 x_{i}^{2} + _{i≠j}^{∑} x_{i}x_{j} − 2 n ; ∑ ; i=1 x_{i} + 1
= _{i≠j}^{∑} x_{i}x_{j} − n ; ∑ ; i=1 x_{i} + 1
= \frac{1}{2} _{i≠j}^{∑}(−2)x_{i}x_{j} + n ; ∑ ; i=1(−1)x_{i} + 1

– The eight rooks problem

E_{1} = _{j}^{∑}(_{i}^{∑} x_{ij−1})^{2}
E_{2} = _{i}^{∑}(_{j}^{∑} x_{ij−1})^{2}
E = E1 + E2

□ Traveler’s Salesman Problem (TSP)^{3}

– as an NP-complete^{4} combinatorial problem ∗ A salesman should visit every city once but only once such that his traveling route is the shortest^{5}.

• Representation of a rout by a N × N matrix

⋆ The rout 1-3-6-4-5-2 of 6-city TSP is represented as

( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \end{matrix} )  (28)

where “iα-element is one” means that the i-th city is in the α-th location in the tour.

• Implementation by a fully connected neural network with N neurons.

– S_{iα}(t) corresponds to the iα-element of the matrix.

– Starting with a random configuration of the network state, it is expected to converge to the matrix corresponding to the shortest route.

3We can apply the problem to “how we connect each device in LSI in which many, say 10^{5}, divices are included.”

4Nondeterministic polynomial 5With N cities, the number of all the possible route is

(N − 1)! = \sqrt{2πN} exp(N ln N − N)  (27)

i.e., not deterministic in polynomial time.

Then the energy of our neural network is

E = −\frac{1}{2} i≠k ; ∑ ; i,k α≠β ; ∑ ; α,β w_{iα,kβ}S_{iα}S_{kβ}  (29)

This can be expanded with appropriate A, B, and C as

E = − \frac{1}{2} i≠k ; ∑ ; i,k,α d_{ik}S_{iα}(S_{k(α−1)} + S_{k(α+1)})
− \frac{A}{2} α≠β ; ∑ ; i,α,β S_{iα}S_{iβ} − \frac{B}{2} i≠k ; ∑ ; i,k,α, S_{iα}S_{kα}
− \frac{C}{2} _{i,α}^{∑}(S_{iα}S_{N})^{2}  (30)

(31)

Then ⋆ 1st term means total length of the tour; ⋆ 2nd term vanishes iff the raw includes only one “1”; ⋆ 3rd term vanishes iff the column includes only one “1”; ⋆ 4th term takes its minimum when exactly N neurons are active.

□ Simmulated Annealing.

Annealing is a term from materials science which describes the process of eliminating lattice difects in crystals by heating a crystal to more than melting point and then slowly cooling it to room temperature.

If it is cooled too rapidly from the molten phase, some atoms are often captured an energetically infavarable locations in the lattice.

Hence, the thermal equilibrium distribution should be maintained at all times during the cooling process.

• Metropolis Algorithm

– Cost function (Objective function) E that we want to minimize is to be modified step by step as follows:

1. Start with randomly determined E.

2. IF △E = E^{old} − E^{new} < 0, then accept the modification. ELSE IF accept it with the probability exp(−△E/T), otherwise retain the E^{old}.

3. Repeat step 2.

• Traveling Salesman’s Problem

– E is set to the total length of a tour.

– Then how we modify E?

∗ Lin-Kernighan’s two procedures: · Transport: A segment of the tour is removed from its old position and insert it at a new position. · Reversal: A segment of the tour is selected and the order of cities in this segment is reversed.

– Run, for example, under the conditions:

1. Start with the temperature T = LN^{−3/2} wher L is the length of a initial tour.

2. At a temperature, repeat either of two modifications with equal probability, until · 100N modifications, or · 10N modifications are accepted

3. Reduce T by 5% and repeat Step 2.