Error Correction Learning(I) Ch 2.

Learning Processes
Error signal, ek(n) ek(n) = dk(n) - yk(n)
where n denotes time step

Error signal activates a control mechanism for corrective adjustment of synaptic weights Mininizing a cost function, E(n), or index of performance
E (n) 1 2 ( n) 2 ek

Also called instantaneous value of error energy step-by-step adjustment until

system reaches steady state; synaptic weights are stabilized

Learning
Learning is a process by which free parameters of NN are adapted thru stimulation from environment Sequence of Events
stimulated by an environment undergoes changes in its free parameters responds in a new way to the environment

Error Correction Learning(II)

Deltra rule, Widrow-Hoff rule wkj(n) = ek(n)xj(n). What is more general rule of delta rule? : rate of learning; learning-rate parameter wkj(n+1) = wkj(n) + wkj(n) wkj(n) = Z-1[wkj(n+1)] Z-1 is unit-delay operator adjustment is proportioned to the product of error signal and input signal error-correction learning is local The learning rate determines the stability or convergence

Learning Algorithm
prescribed steps of process to make a system learn ways to adjust synaptic weight of a neuron No unique learning algorithms - kit of tools

The Chapter covers

five learning rules, learning paradigms, issues of learning task probabilistic and statistical aspect of learning

Memory-based Learning
Past experiences are stored in memory of correctly classified input-output examples
retrieve and analyze local neighborhood

Hebbian Learning
If two neurons of a connection are activated
simultaneously (synchronously), then its strength is increased asynchronously, then the strength is weakened or eliminated

Essential Ingredient
Criterion used for defining local neighbor Learning rule applied to the training examples

Hebbian synapse
time dependent depend on exact time of occurrence of two signals local locally available information is used interactive mechanism learning is done by two signal interaction conjunctional or correlational mechanism cooccurrence of two signals

Nearest Neighbor Rule (NNR)

the vector Xn { X1, X2, ,XN } is the nearest neighbor of Xtest (not seen before) if

min d ( X , X
i i

tes t

d(X

' N

tes t

Xn is the class of Xtest d: Euclidian distance

Hebbian learning is found in Hippocampus

presynaptic & postsynaptic signals

Nearest Neighbor Rule

Cover and Hart
Examples are independent and identically distributed The sample size N is infinitely large then, error(NNR) < 2 * error(Bayesian rule) Half of the information is contained in the Nearest Neighbor

Math Model of Hebbian Modification

wkj(n) = F(yk(n), xj(n)) Hebbs hypothesis wkj(n) = yk(n)xj(n) where is rate of learning
also called activity product rule repeated application of xj leads to exponential growth

K-nearest Neighbor rule

variant of NNR Select k-nearest neighbors of Xtest and use a majority vote act like averaging device discriminate against outlier

Radial-basis function network is a memory-based classifier

Covariance hypothesis wkj(n) = (xj - x)(yk - y) 1. wkj is enhanced if xj > x and yk > y 2. wkj is depressed if (xj > x and yk < y ) or (xj < x and yk > y ) where x and y are time-average

Competitive Learning
Output neurons of NN compete to became active Only single neuron is active at any one time
salient feature for pattern classification

Competitive Learning
Output signal
yk 1 if v k > v j for all j, j 0 otherwise

Basic Elements
A set of neurons that are all same except synaptic weight distribution responds differently to a given set of input pattern A limit on the strength of each neuron A mechanism to compete to respond to a given input winner-takes-all

Wkj denotes the synaptic weight

j

kj

1 for all k

Competitive Learning Rule

wkj (xj 0 wkj ) if neuron k is the winner if neuron k is the loser

Neurons learn to respond specialized conditions

become feature detectors

If neuron does not respond to a particular input, no learning takes place

Competitive NN
Feedforward connection is excitatory

Competitive Learning
x has some constant Euclidean length and
j

w2 kj

1 for all k

Lateral connection ( ) is inhibitory - lateral inhibition layer of source Input Single layer of output neurons

perform clustering thru competitive learning

Boltzman Learning
Rooted from statistical mechanics Boltzman Machine : NN on the basis of Boltzman learning The neurons constitute a recurrent structure
operate in binary manner: on: +1 and off: -1 Visible neurons and hidden neurons energy function 1 E wkj xk x j 2 j k
j k

Boltzman Learning Rule

Let kj denote the correlation between the states of neurons j and k with its clamped condition
kj x x

p( X

x |X

x ) x j xi

Let kj denote the correlation between the states of neurons j and k with its free-running condition
kj x x

p( X

x) x j xi

k means no self feedback

Boltzman Learning Rule (Hinton and Sejnowski 86)

Goal of Boltzman Learning is to maximize likelihood function

set of synaptic weights is called a model of the environment if it leads the same probability distribution of the states of visible units

wkj
where

kj

kj

),

is a learning-rate

Boltzman Machine Operation

choosing a neuron at random, k, then flip the state of the neuron from state xk to state -xk with probability
P ( xk xk ) 1 exp( 1 Ek T )

Credit-Assignment Problem
Problems of assigning credit or blame for overall outcomes to each of internal decisions Two sub-problems
assignment of credit to actions temporal credit assignment problem : time instance of action many actions are taken; which action is responsible the outcome assignment of credit to internal decisions structural credit assignment problem : internal structure of action multiple components are contributed; which one do best

where Ek is energy change resulting from such a flip If this rule applied repeatedly, the machine reaches thermal equilibrium. Two modes of operation
Clamped condition : visible neurons are clamped onto specific states Free-running condition: all neurons are allowed to operate freely

CAP occurs in Error-correction learning

in multiple layer feed-forward NN How do we credit or blame for the actions of hidden neurons ?

Learning with a Teacher

Supervised learning Teacher has knowledge of environment to learn Input and desired output pairs are given as a training set Parameters are adjusted based on error signal step-by-step System performance measure
mean-square-error sum of squared errors over the training sample visualized as error surface with parameter as coordinates Move toward to a minimum point of error surface may not be a global minimum use gradient of error surface - direction of steepest descent

Unsupervised Learning
Self-organized learning
No external teacher or critics Task-independent measure of quality is required to learn Network parameters are optimized with respect to the measure Competitive learning rule is a case of unsupervised learning

Good for pattern recognition and function approximation

Learning without a Teacher

Reinforcement learning
No teacher to provide direct (desired) response at each step example : good/bad, win/lose must solve temporal credit assignment problem since critics may be given at the time of final output
Primary reinforcement

Learning Tasks
Pattern Association Pattern Recognition Function Approximation Control Filtering Beamforming

Environment

Critics Heuristic reinforcement Learning Systems

Pattern Association
Associative memory is distributed memory that learns by association
predominant features of human memory

Function Approximation
(x i , d i ) i 1 Given set of labeled examples drawn from d f ( x) , find F ( x) which approximates unknown function f ( x) s.t. || F ( x ) f ( x) || for all x
Supervised learning is good for this task System identification Unknown construct an inverse system
system input NN model yi
N

xk yk, k=1, 2,, q Storage capacity, q Storage phase and Recall phase
NN is required to store a set of patterns by repeatedly presenting partial description or distorted pattern is used to retrieve the particular pattern
xk is act as a stimulus that determines location of memorized pattern

di ei

Autoassociation : when xk = yk, (unsupervised) Hetroassociation : when xk yk(supervised), Have q as large as possible yet recall correctly

Pattern Recognition
Process whereby a received pattern is assigned to one of prescribed classes (categories) Pattern recognition by NN is statistical in nature
pattern is a point in a multidimensional decision space decision boundaries - region associated with a class decision boundaries are determined by training

Control
Feedback control system
Reference signal d e Controller u Plant y

search of Jacobian matrix

Input pattern

Feature Extraction Feature vector q-D

Classification

Outout class

unsupervised m-D

supervised r-D

for error correction learning uj indirect learning using input-output measurement on the plant, construct NN model the NN model is used to estimate Jacobian direct learning

yk

Filtering
Extract information from a set of noisy data information processing tasks
filtering using data measured up to and including time n smoothing using data measured up to and after time n prediction predict at n+n0 ( n0 > 0) using data measured up to time n

Memory
Relatively enduring neural alterations induced by interaction with environment - neurobiological definition accessible to influence future behavior activity pattern is stored by learning process
memory and learning are connected

Short-term memory
compilation of knowledge representing current state of environment

Cocktail party problem

focus on a speaker in the noisy environment believed that preattentive, preconscious analysis involved

Long-term memory
knowledge stored for a long time or permanently

Blind source separation

Associative memory
Memory is distributed stimulus pattern and response pattern consist of data vectors information is stored as spatial patterns of neural activities information of stimulus pattern determines not only stage location but also address for its retrieval although neurons is not reliable, memory is there may be interaction between patterns stored. (not a simple storage of patterns) There is possibility of error in recall process

x1(n) u1(n)
...

um(n)

Unknown mixer A

y1(n) Demixer W
... ...

ym(n)

xm (n) Unknown environment

Correlation Matrix Memory

Association of key vector xk with memorized vector yk
yk = W(k)xk, k = 1, 2, 3, , q

Recall
^

y
y

Mxj
m m

Total experience
q

y k xT x j k
k 1 k 1 m

(x T x j ) y k k (xT x j )y k k
k 1, k j

M
k 1

W (k )
Normalize to have unit matrix

( xT x j ) y j j
m

Mk

M k -1

W(k), k 1, 2, ..., q
defined as

Vj

yj
k 1, k

(xT x j )y k k
j

Adding W(k) to Mk-1 loses distinct identity of mixture of contributions that form Mk but information about stimuli is not lost

Noise Vector

cos(x k , x j )
normalized to have unit matrix

xT x j k || x k || || x k || xT x j k

Correlation Matrix Memory

Learning : Estimate of memory ^ matrix M M
called Outer Product Rule generalization of Hebbs postulate of learning
^ q T y k xk k 1

Orthogonal set
m

vj
orthogonal set

cos(x k , x j )y k
k 1, k 1

cos( x k , x j )

0,

y1 ,

y 2 , ...,

yq

T x1 xT 2

xT x j k YX T
Storage Capacity
rank : # of independent columns limited by dimensionality of input

1, k 0, k

j j

xT q
^ ^

Mk

Mk

y k xT , k 1, 2, ..., q k

Error of Associative Memory

Real-life is Neither orthogonal nor highly separated Lower bound

Statistical Nature of Learning Process

Training sample denoted by

(xi , d i ) i 1 functional relationship between X and D : D

deterministic function of random variable X expectation error random variable

f (X)

x xj

T k

for k

if is large, the memory may fail to distinguish

memory act as having patterns of never seen before termed animal logic

called regressive model

E [ | x] f ( x)

0 E[ D | x ]

Mean value is zero

f ( x) E ( D | X x ) error is uncorrelated (principles of orthogonality) E[ f ( x)] 0

Adaptation
Space and time : fundamental dimension
spatiotemporal nature of learning

Minimizing Cost Function

1 N (w ) (d i F (x i , w )) 2 2 i1 1 ( w) E [( d F (x, )) 2 ] 2 (w )
natural measure of the effectiveness

Stationary system
learned parameters are frozen to be used later

E is averaging
operator

Nonstationary system
continually adapt its parameters to variations in the incoming signal in a real-time fashion continuous learning; learning-on-the-fly

1 E [ 2

1 E [( f (x) 2 E [( f (x)

F ( x, )) 2 ] F ( x, )) 2 ] x] F (x, )) 2 ]

Psudostationary
consider stationary for a short time window speech signal : 10~30 msec weather forcasting : period of minutes

Lav ( f (x), F ( x, w ))

Lav ( f (x), F (x, w ))

since f (x)

E [( E ( D | X
E(D | X x)

Bias/Variance Dilemma
E[ D | X
Bias: variance:

Vapnik-Chervonenkis Dimension
Measure the capacity or expressive power of the family of classification functions realized by the learning machine VC dimension, VCdim( ), of an ensemble of dichotomies is the cardinality of the largest set L that is shattered by
maximum number of training examples that can be shattered by the machine( ) without error example : 4 points in general position in 2D space # of dichotomies ( (L)): 16 Vcdim( ), max N where (L) = 2N : 4

x] F (x, ) B (w ) V (w )

E[ D | X

x] E [ F ( x, )] F ( x, ) x]

E [ F ( x, )] E [( F (x, )

E [ F (x, )] E[ D | X

E [ F (x, )]) 2 ]

Bias (approximation error)

represents inability of the NN to approximate the regression function

Variance (estimation error)

inadequacy of the information contained in the training set

we can reduce both of bias and variance only with Large training samples purposely introduce harmless bias to reduce variance
designed bias - constrained network takes prior knowledge

Evaluation of VCdim(.) is difficult task, but its bounds are often tractable
feedforward network with a threshold function : O(W logW) feedforward network with the sigmoid function : O(W2) feedforward network with pure linear function : O(W)

Statistical Learning Theory

Address fundamental issue of controlling generalization ability
Risk functional
w

Confidence Interval
Pr(sup | P( w ) v (w ) | ) 2eN h
h

exp(

N)

R (w )

L ( d , F ( x, w )) dFX , D ( x, d )

Pr(sup | P (w )
w

v (w) |

Principles of empirical risk minimization

empirical risk function for i.i.d examples (xi, di) Remp ( w) uniform convergence 1 N
N

( N, h, ) ( N, h, ) 2

h 2N log N h
2 0

1 1

1 log N
2 0

For large P(w)

L (d i , F (x i , w ))
i 1

( N, h, ) 1

v(w ) ( N, h, )

For small P(w)

P (sup | R (w )
w W

Remp ( w) |

0 as N
1

holds iif

( N, h, )

2 0

( N, h, )

for v (w )

R (w emp )

min R( w) holds as N

As training progress, likelihood of those approximate functions F(xi, w), consistent with training data is increased

A finite VCdim is a necessary and sufficient condition for the uniform convergence of the principle of empirical risk minimization Training Error v(w) vs. Generalization Error

Guaranteed risk
v guaranteed (w)
error

v train (w)

( N, h,

v train )

Guranteed risk (bound on generation error)

1

( N, h,

v train )

Training error

VC dimension, h overdetermined underdetermined

Probably Approximately Correct Learning Model

Goal of PAC learning is to ensure that vtrain is usually small v train P(x : g ( x ) c ( x)
prob. of difference btn trained hypothesis and concept to learn

Parameters
size of training sample, N error parameter, , allowed in approximation of the target concept confidence parameters, , likelihood of approximation

How many random example is needed to learn unknown concept within given VCdim h, and with constant K
N K h log
N

1
1

log

1
1

For H hypothesis

ln | H |

log