Neural Networks: Basic

Dokuz Eylül University Computer Engineering Department

24 October 2001 –

(Neural Networks: Basic) 2

□ What is Neural Network? □ A system with neurons connected with synapses,

where

• synapse:

transmits value with being multiplied by its weight; and • neuron:

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

□ Neural Networks What for?

• To model human brain;

• To make computers try thins that we are good at but they are not. ^{1} Foreword by □ Typically categorized into two forms:

1. Layered (feed forward)

2. Fully-connected

1 Terrence J. Sejnowski said in his foreword for the book “Face Image Analysis by Unsupervised Learning” by Marian Stewart Bartlett. Kluwer Academic Publishers (2001) that Computers are good at many things that we are not good at, like sorting a long list of numbers and calculating the trajectory of a rocket, but they are not at all good at things that we do easily and without much thought, like seeing and hearing.

0.1

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 □ Analogy from nature:

– from sensors at retina to sensori-motor-output in brain.

□ What can we do with this?

– prediction of sun-spots, stock market, etc

– character recognition

– ⋯

□ How can we specify weight values?

– Learning by themselves (a sort of Machine Learning). ∗ Supervised Learning (= Learning with Teacher)

∗ Unsupervised Learning (= Learning without Teacher)

Keywords:

– learning, supervised, unsupervised

0.1.1

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

0.1.2

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.

(Neural Networks: Basic) 7

– 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

0.2

Examples of Learning

– Perceptron Learning

– Gradient Learning

– Error Back Propagation

– Evolutionary computation (such as GA)

– etc

(Neural Networks: Basic) 9 0.2.1

Perceptron Learning

– Assume M input and N output neurons.

– Also assume that we have p examples

σ_{i}^{μ}, μ = 1, 2, ⋯, p, i = 1, 2, ⋯, M,  (3)

whose desired output are known, i.e.,

ζ_{j}^{μ}, i = 1, 2, ⋯, N.  (4)

while real output was

S_{i}^{μ}, i = 1, 2, ⋯, N.  (5)

– Then we modify w_{ij} by adding:

δw_{ik} = ϵ(ζ_{i}^{μ} − S_{i}^{μ})σ_{k}^{μ},  (6)

in each iteration of giving example, and we obtain

w_{ik}^{new} = w_{ik}^{old} + δw_{ik},  (7)

(implying if correct do nothing, otherwise modify.)

– Note that each of σ_{k}^{μ}, S_{i}^{μ}, and ζ_{k}^{μ} takes either 1 or −1.

□ Try to calculate the below by hand.

– Three binary inputs and two binary outputs.

– If the number of +1 is even then output should be −1+1 If the number of +1 is odd then output should be +1−1 (that is to say, y_{1} is odd-flag and y_{2} is even-flag.)

– Pick up 6 examples out of 8 possible input to give them for adjusting w_{ij}’s.

– Apply the Perceptron Learning Algorithm with ϵ = 0.05 f(x) = sgn(x − 1)

– Repeat giving the examples until w_{ij} won’t change any more. (You may use one example multiple time if needed.)

– Test the results with 2 remaining possible inputs.

□ Try to make program for the one with 10 inputs.

□Analog vs Binary Neurons

– Binary:

∗ Typical Transfer function: y_{i} = sgn(_{k}^{∑} w_{ik}x_{k} − θ)

∗ What does this imply?

∗ θ is called threshold.

– Analog: ∗ y_{i} = f(_{k}^{∑} w_{ik}x_{k} − θ)

∗ f(h) = tanh(βh)

From the definitions:

e^{jx} = cos x + j sin x;  (8)
e^{−jx} = cos x − j sin x,  (9)

we obtain

cos x = \frac{e^{jx} + e^{−jx}}{2};  (10)
sin x = \frac{e^{jx} − e^{−jx}}{2};  (11)

We extend them to

cosh x = \frac{e^{x} + e^{−x}}{2};  (12)
sinh x = \frac{e^{x} − e^{−x}}{2};  (13)

So,

tanh x = \frac{e^{x} − e^{−x}}{e^{x} + e^{−x}} = \frac{1 − e^{−2x}}{1 + e^{−2x}}  (14)

□ Gradient Learning (Learning for analog neurons.)

Squared Error of outputs:

D = _{μ}^{∑} _{i}^{∑}(S_{i}^{μ} − ζ_{i}^{μ}),  (15)

where

S_{i}^{μ} = f(_{k}^{∑} w_{ik}σ_{k}^{μ});  (16)
f(h) = tanh(βh)  (17)

defines an error surface of high dimensionality.

Then, the gradient of D w.r.t. w_{ij} modifies w_{ij} as:

δw_{ik} ≡ −ϵ\frac{∂D}{∂w_{ik}} = ⋯ = ϵ _{μ}^{∑}(ζ_{i}^{μ} − S_{i}^{μ})f′(_{k}^{∑} w_{ik}σ_{k}^{μ}), (18)

where

f′(x) = β{1 − f(x)^{2}}.  (19)

(Neural Networks: Basic) 13

Though there exist many alternatives to find minima of a non-linear function g(x), steepest descent

x_{n+1} = x_{n} − ϵ∇g(x_{n})  (20)

is sufficient in most cases.

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: Basic) 15

□ The algorithm:

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

2. Forward computations: For each of the training vec-

tors

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: Basic) 16

□ Rationale:

From the gradient descent’s principle,

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

where

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

and

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

Hence

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

Here we define

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

Then

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

Applications of Neural Networks

– Learning to steer a car simulator.

⋆ D. A. Pomerleau (1991) “Rapidly Adapting Artificial Neural Networks for Autonomous Navigation.” R. P. Lipman et al. (Eds.) Advances in Neural Information Processing Systems 3, Morgan Kaufmann, p429.

– Learning to pronounce English Text (NET-Talk) ⋆ T. J. Sejnowski, and C. R. Rosenberg (1987) “Parallel Networks that learn to Pronounce English Texts.” Complex Systems 1, p145.

– Stock Price Prediction ⋆ E. Schöneburg (1990) “Stock Price Prediction using Neural Networks: A Project Report.” Neurocomputing 2, p17.

– Learning to Play Backgammon ⋆ G. Tesauro, T. J. Sejnowski (1988) “A Neural Netwokr that Learns to play Backgammon.” D. Z. Anderson(Ed.) Neural Information Processing Systems. American Institute of Physics.

□ Chess (Satranç) by Neural Networks

• One possible implementation:

- 64 input neurons each of which takes a value from –6 to 6 representing a stone, plus one input binary neuron representing whose turn, which corresponds to one scene of a game.

- 2 output neurons: one takes a value from –6 to 6 and the other from 1 to 64, representing a possible best movement, that is, which stone should be moved to where? (e.g., output 1 and 48 means that the stone-1 should be moved to

(Neural Networks: Basic) 19

□ Backgammon (Tavla) by Neural Networks • One possible implementation:

- a total of 29 input neurons; ⋆ 26 input neurons^{2} each of which takes a value from −15 to 15, representing a number of stones at each cite, positive ones are mine and negative ones are opponent’s, plus two neurons with each indicating the figure of two dice, and one more neuron representing whose turn.

– 4 output neurons^{3} ⋆ each of which takes a value from 1 to 6 which indicates how many positions the corresponding stone proceeds.

or

– 24 output neurons ⋆ indicating the next scene as the 24 input neurons for the purpose above.

2 two of which are for the outside position of mine and opponent’s, respectively 3 Usually we need two but if the figures of two dice are identical, the number of movement is four.

□ Reward and Penalty Learning:

An example on perceptron with one hidden layer.

– N_{0} analog and deterministic output neurons:

y_{i}^{2} = f(_{j}^{∑} w_{ij}^{2}y_{j}^{1})  (28)

where

f(x) = \frac{1}{1 + exp(−x)}  (29)

– Binary and stochastic hidden neurons:

prob(y_{i}^{1} = 1) = f(_{j}^{∑} w_{ij}^{1}x_{j})  (30)
prob(y_{i}^{1} = 0) = 1 − f(_{j}^{∑} w_{ij}^{1}x_{j})  (31)

– Using

D = \frac{1}{N_{0}} _{i}^{∑}(ŷ_{i}^{2} − y_{i}^{2})^{2}  (32)

∗ modify weights to output layer by gradient method as

δwij^{out} = ϵ(ẑ_{i} − z_{i})f′(_{k}^{∑} wik^{out}y_{k})y_{j}  (33)

∗ and weights to hidden layer in a stochastic way as

δwij^{hidden} = rϵ(y_{i} − f(_{k}^{∑} wik^{hidden}x_{k})x_{j}
+ (1 − r)λϵ(1 − y_{i} − f(_{k}^{∑} wik^{hidden}x_{k})x_{j}(34)

(Neural Networks: Basic) 22

where r is signal meaning success/failure of the task, i.e., ⋆ r = 1 with probability 1 − D; ⋆ r = 0 with probability D.

IF rand() < 1 − D;

THEN r = 1;
ELSE r = 0;

• Note: Parameter notations of the previous few pages:

The i-th output neuron outputs z_{i} while desirerd output is ẑ_{i}.

⇑

The i-th output neuron takes

Nhidden ; ∑ ; k w_{ik}^{out}y_{k}

from all the hidden neurons.

⇑

Each of hidden neuron outputs y_{k},

⇑

The i-th hidden neuron takes

Ninput ; ∑ ; k w_{ik}^{hidden}x_{k}

from the input layer.

⇑

Each input neuron takes an input x_{k}, and send to all neurons in the hidden layer.

(Neural Networks: Basic) 24

– Apply this to a task of symmetry detection. ∗ n^{2} input, 12 hidden neurons, and 3 output.

∗ if the n × n pixels of the input are · horizontally symmetric · vertically symmetric · diagonally symmetric the 1st, 2nd and 3rd neuron should be acctivated.

– Interpretation of the reward and penalty learning.

□ Unsupervised Learning:

Unsupervised learning can only do anything useful when there is redundancy in the input data. In this sence redundancy provides knowledge.

– Learning by Competition.

– Kohonen’s Self-organizing Map.

– Reinforcement Learning.

(1) Unsupervised Learning through Competition:

Let x = (x_{1}, ..., x_{n}) be a normalized input vector, i.e.,

n ; ∑ ; i=1 x_{i} = 1,  (35)

in n-dimensional space which we want to classify in one of k different clasters.

– The network consitsts of n real-valued input neurons and k binary output neurons (with all neurons zerothreshold.)

– Each output neuron receives

h_{i} = n ; ∑ ; j=1 w_{ij}x_{j}  (36)

from all the neurons in the input layer.

(Neural Networks: Basic) 26

– Then the only neuron which recieves

h_{m} = max_{i}(h_{i})  (37)

will be on.

– Learning Algorithm:

1. Initialize all the weights w_{ij} at random, and normaliz them such that

n ; ∑ ; j=1 w_{ij} = 1 for ∀i = 1, ..., k  (38)

2. Selct a vector x^{μ} at random from the training sample, and compute

h_{i} = n ; ∑ ; j=1 w_{ij}x_{j} for ∀i = 1, ..., k  (39)

3. The Winner Takes All Procedure · Modify only the weight w_{mj} which recieves

h_{m} = max_{i} h_{i}  (40)

as

wmj^{new} = wmj^{old} + δw_{mj}  (41)

where

δw_{mj} = ϵ(x_{k} − w_{ik})  (42)

and normalize them again.

4. Repeat 2 and 3 until a predetermined number of steps is reached.

Note that · The difference between this algorithm and perceptron learning is that the input set cannot be classified a priori in a positive or a negative set or in any of several different clusters. · When we monitor the number of updates for each weight vector in order to make the process as balanced as possible, we call this learning with conscience.

– A numerical excersise: Assume three input neurons and three output neurons with w_{ij}

( \begin{matrix}0.23 & −0.72 & −0.51 \\ −0.49 & 0.33 & −0.16 \\ 0.23 & 0.68 & 0.84 \end{matrix} ) .  (43)

Then under an input (−1, 1, −1), · (1) obtain h_{m}; · (2) modify weights.

– How it works?

∗ When we take x and w as

x = (x_{1}, x_{2}, ⋯, x_{N_{i}},)
w = (w_{i1}, w_{i2}, ⋯, w_{iN_{i}},)

the equation (??) implies a vector such as: Therefore

w + δw makes w become closer to x, and

∗ the more w is closer to x, the larger the inner product h_{i} becomes.

∗ What will happen when multiple x^{μ} is repeatedly given?

(2) Kohonen’s Self-organizing Network:

Simulation of topology preserving maps in the brain.

– Kohonen Learning Algorithm The n-dimensional weight vectors w_{1}, .., w_{m} of the m computing neurons are selected at random. An initial radius r, a learning constant η, and a neighborhood funciton ϕ are selected.

1. Select an input vector ζ using the desired probability distribution over the input space.

2. The neuron k with the maximum excitation is selected, that is, for which the distabnce between w_{i} and ζ is minimal for i = 1, ⋯, m.

3. The weight vectors are updated using the nighborhood function and the update rule

w_{i} = w_{i} + ηϕ(i, k)(ζ − w_{i})fori = 1, ⋯, m (44)

4. Stop if the maximum number of iterations has been reached, otherwise modify η and ϕ as sceduled and continue with step 1.

(Neural Networks: Basic) 30

– Examples: (i) from 2D to 1D · points inside of a triangle in 2-dimensional space into 11 classes two inputs for x1,x2 representing coordinate eleven outputs corresponding to (wi1,wi2) which is closest to the (x1,x2) will be on · plot (w,w) (ii) from 2D to 2D