Regression and

Classification with
Neural Networks
Note to other teachers and users of
these slides. Andrew would be
Andrew W. Moore
Professor
delighted if you found this source
material useful in giving your own
lectures. Feel free to use these
slides verbatim, or to modify them
to fit your own needs. PowerPoint School of Computer Science
originals are available. If you make

Carnegie Mellon University

use of a significant portion of these
slides in your own lecture, please
include this message, or the
following link to the source [Link]/~awm
repository of Andrew’s tutorials:
[Link] awm@[Link]
als
. Comments and corrections 412-268-7599
gratefully received.

Copyright © 2001, 2003, Andrew W. Moore Sep 25th, 2001

 Linear Regression
DATASET

inputs outputs
x1 = 1 y1 = 1
x2 = 3 y2 = 2.2

w x3 = 2 y3 = 2
 1 
x4 = 1.5 y4 = 1.9
x5 = 4 y5 = 3.1

Linear regression assumes that the expected

value of the output given an input, E[y|x], is linear.
Simplest case: Out(x) = wx for some unknown w.
Given the data, we can estimate w.
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 2
 regression
Assume that the data is formed by
yi = wxi + noisei

where…
• the noise signals are independent

• the noise has a normal distribution with mean

0 and unknown variance σ2

P(y|w,x) has a normal distribution with

• mean wx

• variance σ2

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 3

 Bayesian Linear Regression
P(y|w,x) = Normal (mean wx, var σ2)

We have a set of datapoints (x1,y1) (x2,y2) …

(xn,yn) which are EVIDENCE about w.

We want to infer w from the data.

P(w|x1, x2, x3,…xn, y1, y2…yn)
•You can use BAYES rule to work out a posterior
distribution for w given the data.
•Or you could do Maximum Likelihood

Estimation
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 4
 Maximum likelihood estimation
of w

Asks the question:

“For which value of w is this data most likely to
have happened?”
<=>
For what w is
P(y1, y2…yn |x1, x2, x3,…xn, w) maximized?
<=>
For what w is n

 P( y
i 1
i w, xi ) maximized?

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 5

For what w is
n

 P( y
i 1
i w, xi ) maximized?

For what w nis

1 yi  wxi 2

i 1
exp( (
2 
) ) maximized?

For what w is
2
n
1  yi  wxi 
i 1
 
2 
 maximized?

For what w is 2
n

 y
i 1
i  wxi  minimized?

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 6

 Linear Regression

The maximum
likelihood w is
the one that E(w)
w
minimizes
  yi  wxi 
2
sum-of-
squares of i
residuals  yi  2 xi yi w 
2
 x w i
2 2

i
We want to minimize a quadratic function of
w.
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 7
 Linear Regression
Easy to show the sum
of squares is
minimized when
w
 xy i i

x
2
i

The maximum likelihood

model is
Out x  wx
We can use it for
prediction
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 8
 Linear Regression
Easy to show the sum
of squares is
minimized when p(w)

w
 xy i i w

x
2
i Note: In Bayesian stats you’d

The maximum likelihood have ended up with a prob dist of

Out x  wx
w
model is
And predictions would have given a
prob dist of expected output
We can use it for
Often useful to know your
prediction
confidence. Max likelihood can

Copyright © 2001, 2003, Andrew W. Moore give some kindsNeural

of confidence
Networks: Slide 9
 Multivariate Regression
What if the inputs are vectors?
3 .

.4
6.
2-d input
.
5 example
.8
x2 .
10
x1
Dataset has form
x1 y1
x2 y2
x3 y3
.: :

Copyright © 2001, 2003, Andrew W. Moore xR yRNeural Networks: Slide 10

 Multivariate Regression
Write matrix X and Y
thus:
 .....x1 .....   x11 x12 ... x1m   y1 
 .....x .....   x x22 ... x2 m  y 
x  2   21 y  2 
       
     
 .....x R .....  xR1 xR 2 ... xRm   yR 

(there are R datapoints. Each input has m

components)
The linear regression model assumes a vector w
such that
Out(x) = wTx = w1x[1] + w2x[2] + ….wmx[D]
The max. likelihood w is w = (XTX) -1(XTY) Neural Networks: Slide 11
Copyright © 2001, 2003, Andrew W. Moore
 Multivariate Regression
Write matrix X and Y
thus:
 .....x1 .....   x11 x12 ... x1m   y1 
 .....x .....   x x22 ... x2 m  y 
x  2   21 y  2 
       
     
 .....x R .....  xR1 xR 2 ... xRm   yR 

IMPORTANT
(there are R datapoints. Each inputEXERCISE:
has m PROVE
components) IT !!!!!

The linear regression model assumes a vector w

such that
Out(x) = wTx = w1x[1] + w2x[2] + ….wmx[D]
The max. likelihood w is w = (XTX) -1(XTY) Neural Networks: Slide 12
Copyright © 2001, 2003, Andrew W. Moore
 (con’t)

The max. likelihood w is w = (XTX)-1(XTY)

R

XTX is an m x m matrix: i,j’th elt is x

k 1
x
ki kj

R
XTY is an m-element vector: i’th elt x
k 1
ki k y

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 13

What about a constant term?
We may expect
linear data that
does not go
through the origin.

Statisticians and
Neural Net Folks all
agree on a simple
obvious hack.

Can you guess??

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 14

 The constant term
• The trick is to create a fake input “X0”
that always takes the value 1
X1 X2 Y X0 X1 X2 Y
2 4 16 1 2 4 16
3 4 17 1 3 4 17
5 5 20 1 5 5 20
Before: After:
Y=w1X1+ w2X2 Y= w0X0+w1X1+ w2X2
In this example,
…has to be a You should be = w0+w1X1+ w2X2
poor model able to see the
MLE w0 , w1 and …has a fine constant
w2 by inspection term
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 15
 Regression with varying noise
• Suppose you know the variance of the noise
that was added to each datapoint.
y=
=
xi yi i 2 3
2

½ ½ 4 y=
2 =1/2
1 1 1
y= =
2 1 1/4 1 1
=1/2
=
2 3 4 y=
2
0x= x= x= x=
3 2 1/4 0 1 2 3

th e

Assume yi ~ N ( wxi ,  ) i
2
W h
ML ?
at’s timate
E es
of w
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 16
 MLE estimation with varying
noise
argmax log p ( y1 , y 2 ,..., y R | x 1 , x 2 ,..., x R ,  2
1 ,  2
2 ,..., 2
R , w) 

w Assuming i.i.d. and

2 then plugging in
R
( yi  wxi )
argmin   2  equation for
Gaussian and
i 1 i simplifying.
w
Setting
 xi ( yi  wxi )
R
 dLL/dw equal
 w such that  0   to zero
 i 1 i 2


 R xi yi  Trivial algebra
  2 
 i 1  i 
 R xi2 
  2 
 i 1  i 
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 17
 This is Weighted Regression
• We are asking to minimize the weighted
sum of squares
y=
3 =
R
( yi  wxi ) 2 2

argmin   2 y=
i 1 i 2 =1/2
w
y= =
1 1
=1/2
=
2
y=
0x= x= x= x=
0 1 2 3

1
where weight for i’th datapoint 2
i
is
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 18
 Regression

The max. likelihood w is w = (WXTWX)-1(WXTWY)

R xki xkj
(WXTWX) is an m x m matrix: i,j’th elt is k 1  2
i

R
(WXTWY) is an m-element vector: i’th elt xki yk

k 1  2
i

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 19

 Non-linear Regression
• Suppose you know that y is related to a function of
x in such a way that the predicted values have a
non-linear dependence on w, e.g:
y=
xi yi 3

½ ½ y=
2

1 2.5
y=
2 3 1

3 2 y=
0x= x= x= x=
3 3 0 1 2 3

h e
yi ~ N ( w  xi ,  ) 2 t
h at’s timate
Assume W es
E
ML ?
of w
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 20
 Non-linear MLE estimation
argmax log p( y , y ,..., y 1 2 R | x1 , x2 ,..., xR ,  , w) 
w Assuming i.i.d. and
then plugging in

argmin  y 
R 2
equation for
i  w  xi Gaussian and
i 1 simplifying.
w
Setting
 R
yi  w  xi  dLL/dw equal
 w such that  0   to zero
 w  x 
 i 1 i 

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 21

 Non-linear MLE estimation
argmax log p( y , y ,..., y 1 2 R | x1 , x2 ,..., xR ,  , w) 
w Assuming i.i.d. and
then plugging in

argmin  y 
R 2
equation for
i  w  xi Gaussian and
i 1 simplifying.
w
Setting
 R
yi  w  xi  dLL/dw equal
 w such that  0   to zero
 w  x 
 i 1 i 

We’re down
the algebraic
toilet
u e ss
g
So hat we
w
Copyright © 2001, 2003, Andrew W. Moore do
Neural
?
Networks: Slide 22
 Non-linear MLE estimation
argmax log p( y , y ,..., y 1 2 R | x1 , x2 ,..., xR ,  , w) 
w Assuming i.i.d. and
then plugging in

argmin   
R
Common (but not only) approach: 2
equation for
Numerical Solutions:
yi  w  xi  Gaussian and
i 1 simplifying.
• Line Search w
• Simulated Annealing R Setting
 yi  w  xi  dLL/dw equal


w such that
• Gradient Descent 
w  xi

0  to zero

• Conjugate Gradient i 1 
• Levenberg Marquart
• Newton’s Method We’re down
the algebraic
Also, special purpose statistical- toilet
optimization-specific tricks such ss
g u e
So hat we
as E.M. (See Gaussian Mixtures
lecture for introduction) w
Copyright © 2001, 2003, Andrew W. Moore do
Neural
?
Networks: Slide 23
 GRADIENT DESCENT
f(w) :   
Suppose we have a scalar function

We want to find a local minimum.

Assume our current weight is w

GRADIENT DESCENT RULE:w  w    f w

w

η is called the LEARNING RATE. A small

positive number, e.g. η = 0.05

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 24

 GRADIENT DESCENT
f(w) :   
Suppose we have a scalar function

We want to find a local minimum.

Assume our current weight is w

GRADIENT DESCENT RULE:w  w    f w

w
Recall Andrew’s favorite
default value for
anything
η is called the LEARNING RATE. A small
positive number, e.g. η = 0.05
QUESTION: Justify the Gradient Descent
Rule
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 25
 Gradient Descent in “m”
Dimensions
m
Given f(w ) :   
  
 f w  
 w1 
f w     points in direction of steepest
   ascent.
 w f w 
 m 
f w  is the gradient in that
direction
GRADIENT DESCENT w  w - f w 
RULE:

w
Equivalently j  w j - η f w  ….where wj is the jth weight
w j
“just like a linear feedback
Copyright © 2001, 2003, Andrew W. Moore
system” Neural Networks: Slide 26
 What’s all this got to do with
Neural Nets, then, eh??
For supervised learning, neural nets are also models with
vectors of w parameters in them. They are now called
weights.
As before, we want to compute the weights to minimize
sum-of-squared residuals.
Which turns out, under “Gaussian i.i.d noise”
assumption to be max. likelihood.
Instead of explicitly solving for max. likelihood weights,
we use GRADIENT DESCENT to SEARCH for them.
e s s ion in y o ur
u lo u s exp r
q u e r
h y ? ” y o u as k , a
“W
e ye s.
e ’ ll s e e later.”
h a ! ! ” I r e ply: “W
“A
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 27
 Linear Perceptrons
They are multivariate linear models:

Out(x) = wTx

And “training” consists of minimizing sum-of-squared

residuals by gradient descent.

  Outxk  yk 
2

 w xk  yk   2

QUESTION: Derive the perceptron training rule.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 28
 Rule
R
E  ( yk  w T x k ) 2
k 1

Gradient descent
tells us we should
update w thusly if we
wish to minimize E:
E
wj  wj - η
w j

E
So what’s ?
w j
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 29
 Rule
R
E R

E  ( yk  w T x k ) 2  ( yk  w T x k ) 2
k 1
w j k 1 w j
Gradient descent
R

 2( yk  w T x k ) ( yk  w T x k )
tells us we should k 1 w j
update w thusly if we  T
R
wish to minimize E:  2 δk w xk
k 1 w j
E …where…
wj  wj - η δk  y k  w T x k
w j R
 m
 2 δk w x i ki
k 1 w j i 1
E
So what’s ? R
w j  2 δk xkj
k 1

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 30

 Rule
R
E  ( yk  w T x k ) 2
k 1

Gradient descent
tells us we should
update w thusly if we
wish to minimize E:
E R
wj  wj - η
…where…
w j w j  w j  2η δk xkj
k 1
E R
 2 δk xkj
w j k 1
We frequently neglect the 2
(meaning we halve the learning
rate)
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 31
 algorithm
1) Randomly initialize weights w1 w2 … wm

2) Get your dataset (append 1’s to the inputs

if you don’t want to go through the origin).

3) for i = 1 to R  i : yi  w  xi
for j = 1 to m w  w   R  x
4)
j j  i ij i 1

5) if   i 2 stops improving then stop. Else

loop back to 3.
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 32
 
 i  yi  w x i A RULE KNOWN BY

w j  w j   i xij MANY NAMES

ru le
ule H off
MS
R
i d row
L e W
The T h
The delta
rule
Th
ea
da
lin
er
Classical ule

conditioning

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 33

If data is voluminous and arrives
fast

Input-output pairs (x,y) come streaming in

very quickly. THEN
Don’t bother remembering old ones.
Just keep using new ones.

observe (x,y)

  y w x
j w j  w j  η δ x j

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 34

 Gradient Descent vs Matrix
Inversion for Linear Perceptrons
GD Advantages (MI disadvantages):
• Biologically plausible
• With very very many attributes each iteration costs only O(mR).
If fewer than m iterations needed we’ve beaten Matrix Inversion
• More easily parallelizable (or implementable in wetware)?

GD Disadvantages (MI advantages):

• It’s moronic
• It’s essentially a slow implementation of a way to build the XTX
matrix and then solve a set of linear equations
• If m is small it’s especially outageous. If m is large then the
direct matrix inversion method gets fiddly but not impossible if
you want to be efficient.
• Hard to choose a good learning rate
• Matrix inversion takes predictable time. You can’t be sure when
gradient descent will stop.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 35

 Gradient Descent vs Matrix
Inversion for Linear Perceptrons
GD Advantages (MI disadvantages):
• Biologically plausible
• With very very many attributes each iteration costs only O(mR).
If fewer than m iterations needed we’ve beaten Matrix Inversion
• More easily parallelizable (or implementable in wetware)?

GD Disadvantages (MI advantages):

• It’s moronic
• It’s essentially a slow implementation of a way to build the XTX
matrix and then solve a set of linear equations
• If m is small it’s especially outageous. If m is large then the
direct matrix inversion method gets fiddly but not impossible if
you want to be efficient.
• Hard to choose a good learning rate
• Matrix inversion takes predictable time. You can’t be sure when
gradient descent will stop.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 36

 Gradient Descent vs Matrix
Inversion for Linear Perceptrons
GD Advantages (MI disadvantages):
• Biologically plausible
• With very very many attributes each iteration costs only O(mR).
If fewer than m iterations needed we’ve beaten Matrix Inversion
• But we’ll in wetware)?
More easily parallelizable (or implementable
soonadvantages):
GD Disadvantages (MI see that
• It’s moronic GD
• It’s essentially a slow implementation
has an important of a way to build the XTX
extra
matrix and then solve a set of linear equations
• If m is small it’s especiallytrick up its Ifsleeve
outageous. m is large then the
direct matrix inversion method gets fiddly but not impossible if
you want to be efficient.
• Hard to choose a good learning rate
• Matrix inversion takes predictable time. You can’t be sure when
gradient descent will stop.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 37

 Perceptrons for Classification
What if all outputs are 0’s or 1’s ?

or

We can do a linear fit.

Our prediction is 0 if out(x)≤1/2
1 if out(x)>1/2
WHAT’S THE BIG PROBLEM WITH THIS???

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 38

 Perceptrons for Classification
What if all outputs are 0’s or 1’s ?

or

Blue =
We can do a linear fit. Out(x)
Our prediction is 0 if out(x)≤½
1 if out(x)>½
WHAT’S THE BIG PROBLEM WITH THIS???

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 39

 Perceptrons for Classification
What if all outputs are 0’s or 1’s ?

or

Blue =
We can do a linear fit. Out(x)
Green =
Our prediction is 0 if out(x)≤½
Classification
1 if out(x)>½

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 40

 Perceptrons I
 y 
 2
Don’t minimize i  w xi .
Minimize number of misclassifications instead. [Assume outputs are
+1 & -1, not +1 & 0]
 y i  
 Round w x i 
where Round(x) = -1 if x<0 NOTE: CUTE &
NON OBVIOUS WHY

1 if x≥0 THIS WORKS!!

The gradient descent rule can be changed to:

if (xi,yi) correctly classed, don’t change
if wrongly predicted as 1 w  w - xi
if wrongly predicted as -1 w  w + xi

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 41

 II:
Sigmoid Functions

Least squares fit useless

This fit would classify much
better. But not a least
squares fit.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 42

 II:
Sigmoid Functions

Least squares fit useless

This fit would classify much
SOLUTION: better. But not a least
squares fit.
Instead of Out(x) = wTx
We’ll use Out(x) = g(wTx)
where g x :   0,1 is a
squashing function
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 43
 The Sigmoid
1
g ( h) 
1  exp( h)

Note that if you rotate

this curve through 180o
centered on (0,1/2) you
get the same curve.

i.e. g(h)=1-g(-h)

Can you prove

this?
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 44
 The Sigmoid
1
g ( h) 
1  exp( h)

Now we choose w to minimize

 
R R

 y  Out ( x i )  yi  g ( w x i )
2  2
i
i 1 i 1

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 45

 Linear Perceptron Classification
Regions
0 0
0
1
X2 1
1
X1

We’ll use the model Out(x) = g(wT(x,1))

= g(w1x1 + w2x2 + w0)
Which region of above diagram classified with +1, and
which with 0 ??
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 46
 perceptron
First, notice g ' x   g x 1  g x 
1  e x
Because : g x   so g ' x  
1 e  x 2
 1  e  x 
 
1  1  e x 1 1 1  1 
    1    g x 1  g x 
2 2  x  x   x 
 1  e  x   1  e  x  1 e 1 e  1 e 
   
 
Out(x)  g   wk xk 
 k  The sigmoid perceptron
2
  
   yi  g   wk xik   update rule:
i   k 
R
      
 2 yi  g   wk xik    

g   wk xik   w j  w j     i gi 1  gi xij
w j i   k    w j  k   i 1
     
  2 yi  g   wk xik   g '   wk xik  w x  m 
i   k   k  w j k
k ik
where gi  g   w j xij 
  2 i g net i 1  g net i xij  j 1 
i

where  i  yi  Out(x i ) net i  wk xk  i  yi  gi

k
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 47
 Perceptrons
• Invented and popularized by Rosenblatt (1962)

• Even with sigmoid nonlinearity, correct

convergence is guaranteed

• Stable behavior for overconstrained and

underconstrained problems

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 48

 Perceptrons and Boolean
Functions
If inputs are all 0’s and 1’s and outputs are all 0’s and 1’s…

• Can learn the function x1  x2 X2

X1

X2
• Can learn the function x1  x2 .
X1
• Can learn any conjunction of literals, e.g.
x1  ~x2  ~x3  x4  x5

QUESTION: WHY?

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 49

 Perceptrons and Boolean
Functions
• Can learn any disjunction of literals
e.g. x1  ~x2  ~x3  x4  x5

• Can learn majority function

f(x1,x2 … xn) = 1 if n/2 xi’s or more are = 1
0 if less than n/2 xi’s are = 1

• What about the exclusive or function?

f(x1,x2) = x1  x2 =
(x1  ~x2)  (~ x1  x2)

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 50

 Multilayer Networks
The class of functions representable by perceptrons
is limited  
Out(x) g w  x g   w j x j 
 j 

Use a wider
representation !

  
Out(x) g   W j g   w jk x jk   This is a nonlinear function
 j  k 
Of a linear combination
Of non linear functions
Of linear combinations of inputs
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 51
 A 1-HIDDEN LAYER NET
NINPUTS = 2 NHIDDEN = 3

 N INS 
w11
v1  g   w1k xk 
 k 1  w1
x1 w21

w31
 N INS 
v2  g   w2 k xk  w2  N HID 
Out  g   Wk vk 
w12  k 1   k 1 
w22
x2 w3

w32
 N INS 
v3  g   w3k xk 
 k 1 
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 52
 OTHER NEURAL NETS
1

x1

x2

x3
2-Hidden layers + Constant Term

“JUMP” CONNECTIONS

x1

x2  N INS N HID

Out g   w0 k xk   Wk vk 
 k 1 k 1 
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 53
 Backpropagation
  
Out(x)  g   W j g   w jk xk  
 j  k 
Find a set of weights {W j },{w jk }
to minimize

 y  Outx 
2
i i
i

by gradient descent.
That’s
That’s it!
it!
That’s
That’s the
the
backpropagation
backpropagation
algorithm.
algorithm.
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 54
 Convergence
Convergence to a global minimum is not
guaranteed.
•In practice, this is not a problem, apparently.

Tweaking to find the right number of hidden

units, or a useful learning rate η, is more
hassle, apparently.

IMPLEMENTING BACKPROP:  Differentiate Monster sum-square residual

 Write down the Gradient Descent Rule  It turns out to be easier &
computationally efficient to use lots of local variables with names like h j
ok vj neti etc…

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 55

 Choosing the learning rate
• This is a subtle art.
• Too small: can take days instead of
minutes to converge
• Too large: diverges (MSE gets larger
and larger while the weights increase
and usually oscillate)
• Sometimes the “just right” value is
hard to find.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 56

 Learning-rate problems

From J. Hertz, A. Krogh, and

R. G. Palmer. Introduction to
the Theory of Neural
Computation. Addison-
Wesley, 1994.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 57

 Improving Simple Gradient
Descent
Momentum
Don’t just change weights according to the current datapoint.
Re-use changes from earlier iterations.
Let ∆w(t) = weight changes at time t.
Let  be the change we would make with

w regular gradient descent.
Instead we use

Δw t 1    Δw t 
w
w t 1 w t  Δw t 
Momentum damps oscillations. momentum
parameter
A hack? Well, maybe.
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 58
 Momentum illustration

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 59

 Improving Simple Gradient
Descent
Newton’s method
2
T E 1 T  E 3
E ( w  h) E ( w )  h  h 2
h  O (| h | )
w 2 w

If we neglect the O(h3) terms, this is a quadratic

form
Quadratic form fun facts:
If y = c + bT x - 1/2 xT A x
And if A is SPD
Then
xopt = A-1b is the value of x that maximizes y
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 60
 Improving Simple Gradient
Descent
Newton’s method
2
T E 1 T  E 3
E ( w  h) E ( w )  h  h 2
h  O (| h | )
w 2 w

If we neglect the O(h3) terms, this is a quadratic

form
1
 E
2
E
w w  2
 w  w

This should send us directly to the global minimum

if the function is truly quadratic.
And it might get us close if it’s locally quadraticish
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 61
 Improving Simple Gradient
Descent
Newton’s method
2
T E 1 T  E 3
E ( w  h) E ( w )  h  h 2
h  O (| h | )
w 2 w

IfBwe neglect
UT (a the O(h 3
) terms, this is a quadratic
form nd it’s
That a bi g
seco but)…  2 E   1 E
expe nd d
nsive erivwa  w   2
and t i ve m   w  w
If w e fiddl atrix
’re n y to co can b
boThis o
wl, wshouldt alrsend e
mputo the global
e’ll g e a us
dy i n directly t e. minimum
o nu is trulythquadratic.
if the function e qu
ts. adra
tic
And it might get us close if it’s locally quadraticish
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 62
 Improving Simple Gradient
Descent
Conjugate Gradient
Another method which attempts to exploit the
“local quadratic bowl” assumption
E
But does so while only needing to use
w
2

and not E
w 2

It is also more stable than Newton’s method if the

local quadratic bowl assumption is violated.
It’s complicated, outside our scope, but it often
works well. More details in Numerical Recipes in C.
Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 63
 BEST GENERALIZATION
Intuitively, you want to use the smallest,
simplest net that seems to fit the data.

HOW TO FORMALIZE THIS INTUITION?

1. Don’t. Just use intuition

2. Bayesian Methods Get it Right
3. Statistical Analysis explains what’s going on
4. Cross-validation
Discussed in the
next lecture

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 64

 What You Should Know
• How to implement multivariate Least-
squares linear regression.
• Derivation of least squares as max.
likelihood estimator of linear
coefficients
• The general gradient descent rule

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 65

 What You Should Know
• Perceptrons
 Linear output, least squares
 Sigmoid output, least squares

• Multilayer nets
 The idea behind back prop
 Awareness of better minimization methods

• Generalization. What it means.

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 66

 APPLICATIONS
To Discuss:

• What can non-linear regression be useful

for?

• What can neural nets (used as non-linear

regressors) be useful for?

• What are the advantages of N. Nets for

nonlinear regression?

• What are the disadvantages?

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 67

 Other Uses of Neural Nets…
• Time series with recurrent nets
• Unsupervised learning (clustering
principal components and non-linear
versions thereof)
• Combinatorial optimization with
Hopfield nets, Boltzmann Machines
• Evaluation function learning (in
reinforcement learning)

Copyright © 2001, 2003, Andrew W. Moore Neural Networks: Slide 68