ÿþ W h e r e a r e w e ?
L e a s t S q u a r e s M e t h o d f o r r e g r e s s i o n E x a m p l e s
T h e L M S o b j e c t i v e
G r a d i e n t d e s c e n t
I n c r e m e n t a l / s t o c h a s t i c g r a d i e n t d e s c e n t E x e r c i s e s
W h a t s t h e m i l e a g e ?
S u p p o s e w e w a n t t o p r e d i c t t h e m i l e a g e o f a c a r f r o m i t s w e i g h t a n d a g e
( x 1 0 0 l b )
x 1 x 2
3 1 . 5 6 2 1 3 6 . 2 2 2 5 4 3 . 1 0 1 8 2 7 . 6 2 3 0
W h a t w e w a n t : A f u n c t i o n t h a t c a n p r e d i c t m i l e a g e u s i n g x 1 a n d x 2
( y e a r s )
L i n e a r r e g r e s s i o n : T h e s t r a t e g y P r e d i c t i n g c o n t i n u o u s v a l u e s u s i n g a l i n e a r m o d e l
A s s u m p t i o n : T h e o u t p u t i s a l i n e a r f u n c t i o n o f t h e i n p u t s M i l e a g e = w 0 + w 1 x 1 + w 2 x 2
L e a r n i n g : U s i n g t h e t r a i n i n g d a t a t o f i n d t h e b e s t p o s s i b l e v a l u e o f w
P r e d i c t i o n : G i v e n t h e v a l u e s f o r x 1 , x 2 f o r a n e w c a r , u s e t h e l e a r n e d w t o p r e d i c t t h e f o r t h e n e w c a r
L i n e a r r e g r e s s i o n : T h e s t r a t e g y P r e d i c t i n g c o n t i n u o u s v a l u e s u s i n g a l i n e a r m o d e l
A s s u m p t i o n : T h e o u t p u t i s a l i n e a r f u n c t i o n o f t h e i n p u t s M i l e a g e = w 0 + w 1 x 1 + w 2 x 2
P a r a m e t e r s o f t h e m o d e l A l s o c a l l e d w e i g h t s C o l l e c t i v e l y , a v e c t o r
L e a r n i n g : U s i n g t h e t r a i n i n g d a t a t o f i n d t h e b e s t p o s s i b l e v a l u e o f w
P r e d i c t i o n : G i v e n t h e v a l u e s f o r x 1 , x 2 f o r a n e w c a r , u s e t h e l e a r n e d w t o p r e d i c t t h e f o r t h e n e w c a r
L i n e a r r e g r e s s i o n : T h e s t r a t e g y
” I n p u t s a r e v e c t o r s : 5Ø ” R
” O u t p u t s a r e r e a l n u m b e r s : ” R
” W e h a v e a t r a i n i n g s e t
D = { 5Ø , , 5Ø , , ï”}
” W e w a n t t o a p p r o x i m a t e a s
= + + ï” +
F o r s i m p l i c i t y , w e w i l l a s s u m e t h a t t h e f i r s t f e a t u r e i s a l w a y s 1 .
1
= 5Ø
i s t h e l e a r n e d w e i g h t v e c t o r i n R
=
î”
T h i s l e t s m a k e s n o t a t i o n e a s i e r
E x a m p l e s y
O n e d i m e n s i o n a l i n p u t
x 1
E x a m p l e s y
O n e d i m e n s i o n a l i n p u t
P r e d i c t u s i n g y = w 1 + w 2 x 2
x 1
E x a m p l e s y
O n e d i m e n s i o n a l i n p u t
P r e d i c t u s i n g y = w 1 + w 2 x 2
T h e l i n e a r f u n c t i o n i s n o t o u r o n l y c h o i c e . W e c o u l d h a v e t r i e d t o f i t t h e d a t a a s a n o t h e r p o l y n o m i a l
x 1
E x a m p l e s y
O n e d i m e n s i o n a l i n p u t
P r e d i c t u s i n g y = w 1 + w 2 x 2
T h e l i n e a r f u n c t i o n i s n o t o u r o n l y c h o i c e . W e c o u l d h a v e t r i e d t o f i t t h e d a t a a s a n o t h e r p o l y n o m i a l
x 1
T w o d i m e n s i o n a l i n p u t P r e d i c t u s i n g y = w 1 + w 2 x 2 + w 3 x 3
W h a t i s t h e b e s t w e i g h t v e c t o r ?
Q u e s t i o n : H o w d o w e k n o w w h i c h w e i g h t v e c t o r i s t h e b e s t o n e f o r a t r a i n i n g s e t ?
F o r a n i n p u t ( , ) i n t h e t r a i n i n g s e t , t h e c o s t o f a m i s t a k e i s D e f i n e t h e c o s t ( o r l o s s ) f o r a p a r t i c u l a r w e i g h t v e c t o r w t o b e
S u m o f s q u a r e d c o s t s o v e r t h e t r a i n i n g s e t
O n e s t r a t e g y f o r l e a r n i n g : F i n d t h e w w i t h l e a s t c o s t o n t h i s d a t a
W h a t i s t h e b e s t w e i g h t v e c t o r ?
Q u e s t i o n : H o w d o w e k n o w w h i c h w e i g h t v e c t o r i s t h e b e s t o n e f o r a t r a i n i n g s e t ?
F o r a n i n p u t ( , ) i n t h e t r a i n i n g s e t , t h e c o s t o f a m i s t a k e i s
D e f i n e t h e c o s t ( o r l o s s ) f o r a p a r t i c u l a r w e i g h t v e c t o r w t o b e
S u m o f s q u a r e d c o s t s o v e r t h e t r a i n i n g s e t
O n e s t r a t e g y f o r l e a r n i n g : F i n d t h e w w i t h l e a s t c o s t o n t h i s d a t a
W h a t i s t h e b e s t w e i g h t v e c t o r ?
Q u e s t i o n : H o w d o w e k n o w w h i c h w e i g h t v e c t o r i s t h e b e s t o n e f o r a t r a i n i n g s e t ?
F o r a n i n p u t ( , ) i n t h e t r a i n i n g s e t , t h e c o s t o f a m i s t a k e i s D e f i n e t h e c o s t ( o r l o s s ) f o r a p a r t i c u l a r w e i g h t v e c t o r w t o b e
O n e s t r a t e g y f o r l e a r n i n g : F i n d t h e w w i t h l e a s t c o s t o n t h i s d a t a
W h a t i s t h e b e s t w e i g h t v e c t o r ?
Q u e s t i o n : H o w d o w e k n o w w h i c h w e i g h t v e c t o r i s t h e b e s t o n e f o r a t r a i n i n g s e t ?
F o r a n i n p u t ( , ) i n t h e t r a i n i n g s e t , t h e c o s t o f a m i s t a k e i s D e f i n e t h e c o s t ( o r l o s s ) f o r a p a r t i c u l a r w e i g h t v e c t o r w t o b e
S u m o f s q u a r e d c o s t s o v e r t h e t r a i n i n g s e t
O n e s t r a t e g y f o r l e a r n i n g : F i n d t h e w w i t h l e a s t c o s t o n t h i s d a t a
W h a t i s t h e b e s t w e i g h t v e c t o r ?
Q u e s t i o n : H o w d o w e k n o w w h i c h w e i g h t v e c t o r i s t h e b e s t o n e f o r a t r a i n i n g s e t ?
F o r a n i n p u t ( , ) i n t h e t r a i n i n g s e t , t h e c o s t o f a m i s t a k e i s D e f i n e t h e c o s t ( o r l o s s ) f o r a p a r t i c u l a r w e i g h t v e c t o r w t o b e
S u m o f s q u a r e d c o s t s o v e r t h e t r a i n i n g s e t
O n e s t r a t e g y f o r l e a r n i n g : F i n d t h e w w i t h l e a s t c o s t o n t h i s d a t a
L e a s t M e a n S q u a r e s ( L M S ) R e g r e s s i o n
L e a r n i n g : m i n i m i z i n g m e a n s q u a r e d e r r o r
L e a s t M e a n S q u a r e s ( L M S ) R e g r e s s i o n
L e a r n i n g : m i n i m i z i n g m e a n s q u a r e d e r r o r
D i f f e r e n t s t r a t e g i e s e x i s t f o r l e a r n i n g b y o p t i m i z a t i o n
” G r a d i e n t d e s c e n t i s a p o p u l a r a l g o r i t h m
( F o r t h i s p a r t i c u l a r m i n i m i z a t i o n o b j e c t i v e , t h e r e i s a l s o a n a n a l y t i c a l s o l u t i o n . N o n e e d f o r g r a d i e n t d e s c e n t )
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t G e n e r a l s t r a t e g y f o r m i n i m i z i n g
a f u n c t i o n J ( w )
” S t a r t w i t h a n i n i t i a l g u e s s f o r
w , s a y w 0
” I t e r a t e t i l l c o n v e r g e n c e :
C o m p u t e t h e g r a d i e n t o f t h e g r a d i e n t o f J a t w t
U p d a t e w t t o g e t w t + 1 b y t a k i n g a s t e p i n t h e o p p o s i t e d i r e c t i o n o f t h e g r a d i e n t
I n t u i t i o n : T h e g r a d i e n t i s t h e d i r e c t i o n o f s t e e p e s t i n c r e a s e i n t h e f u n c t i o n . T o g e t t o t h e m i n i m u m , g o i n t h e o p p o s i t e d i r e c t i o n
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t G e n e r a l s t r a t e g y f o r m i n i m i z i n g
a f u n c t i o n J ( w )
” S t a r t w i t h a n i n i t i a l g u e s s f o r
w , s a y w 0
” I t e r a t e t i l l c o n v e r g e n c e :
C o m p u t e t h e g r a d i e n t o f t h e g r a d i e n t o f J a t w t
U p d a t e w t t o g e t w t + 1 b y t a k i n g a s t e p i n t h e o p p o s i t e d i r e c t i o n o f t h e g r a d i e n t
I n t u i t i o n : T h e g r a d i e n t i s t h e d i r e c t i o n o f s t e e p e s t i n c r e a s e i n t h e f u n c t i o n . T o g e t t o t h e m i n i m u m , g o i n t h e o p p o s i t e d i r e c t i o n
G r a d i e n t d e s c e n t G e n e r a l s t r a t e g y f o r m i n i m i z i n g
a f u n c t i o n J ( w )
” S t a r t w i t h a n i n i t i a l g u e s s f o r
w , s a y w 0
” I t e r a t e t i l l c o n v e r g e n c e :
C o m p u t e t h e g r a d i e n t o f t h e g r a d i e n t o f J a t w t
U p d a t e w t t o g e t w t + 1 b y t a k i n g a s t e p i n t h e o p p o s i t e d i r e c t i o n o f t h e g r a d i e n t
W e a r e t r y i n g t o m i n i m i z e
I n t u i t i o n : T h e g r a d i e n t i s t h e d i r e c t i o n o f s t e e p e s t i n c r e a s e i n t h e f u n c t i o n . T o g e t t o t h e m i n i m u m , g o i n t h e o p p o s i t e d i r e c t i o n
G r a d i e n t d e s c e n t G e n e r a l s t r a t e g y f o r m i n i m i z i n g
a f u n c t i o n J ( w )
” S t a r t w i t h a n i n i t i a l g u e s s f o r
w , s a y w 0
” I t e r a t e t i l l c o n v e r g e n c e :
C o m p u t e t h e g r a d i e n t o f t h e g r a d i e n t o f J a t w t
U p d a t e w t t o g e t w t + 1 b y t a k i n g a s t e p i n t h e o p p o s i t e d i r e c t i o n o f t h e g r a d i e n t
W e a r e t r y i n g t o m i n i m i z e
I n t u i t i o n : T h e g r a d i e n t i s t h e d i r e c t i o n o f s t e e p e s t i n c r e a s e i n t h e f u n c t i o n . T o g e t t o t h e m i n i m u m , g o i n t h e o p p o s i t e d i r e c t i o n
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t G e n e r a l s t r a t e g y f o r m i n i m i z i n g
a f u n c t i o n J ( w )
” S t a r t w i t h a n i n i t i a l g u e s s f o r
w , s a y w 0
” I t e r a t e t i l l c o n v e r g e n c e :
C o m p u t e t h e g r a d i e n t o f t h e g r a d i e n t o f J a t w t
U p d a t e w t t o g e t w t + 1 b y t a k i n g a s t e p i n t h e o p p o s i t e d i r e c t i o n o f t h e g r a d i e n t
I n t u i t i o n : T h e g r a d i e n t i s t h e d i r e c t i o n o f s t e e p e s t i n c r e a s e i n t h e f u n c t i o n . T o g e t t o t h e m i n i m u m , g o i n t h e o p p o s i t e d i r e c t i o n
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t G e n e r a l s t r a t e g y f o r m i n i m i z i n g
a f u n c t i o n J ( w )
” S t a r t w i t h a n i n i t i a l g u e s s f o r
w , s a y w 0
” I t e r a t e t i l l c o n v e r g e n c e :
C o m p u t e t h e g r a d i e n t o f t h e g r a d i e n t o f J a t w t
U p d a t e w t t o g e t w t + 1 b y t a k i n g a s t e p i n t h e o p p o s i t e d i r e c t i o n o f t h e g r a d i e n t
I n t u i t i o n : T h e g r a d i e n t i s t h e d i r e c t i o n o f s t e e p e s t i n c r e a s e i n t h e f u n c t i o n . T o g e t t o t h e m i n i m u m , g o i n t h e o p p o s i t e d i r e c t i o n
G r a d i e n t d e s c e n t f o r L M S
1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . .
1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
2 . U p d a t e w a s f o l l o w s :
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
W e a r e t r y i n g t o m i n i m i z e
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t f o r L M S 1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . . 1 .
2 . U p d a t e w a s f o l l o w s :
W h a t i s t h e g r a d i e n t o f J ?
C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
” R e m e m b e r t h a t w i s a v e c t o r w i t h d e l e m e n t s w = [ w 1 , w 2 , w 3 , w j , , w d ]
W e a r e t r y i n g t o m i n i m i z e
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
O n e e l e m e n t o f t h e g r a d i e n t v e c t o r
G r a d i e n t o f t h e c o s t ” T h e g r a d i e n t i s o f t h e f o r m
W e a r e t r y i n g t o m i n i m i z e
O n e e l e m e n t o f t h e g r a d i e n t v e c t o r
S u m o f E r r o r £ I n p u t
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t f o r L M S
1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . .
1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
2 . U p d a t e w a s f o l l o w s :
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
G r a d i e n t d e s c e n t f o r L M S
1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . .
1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
W e a r e t r y i n g t o m i n i m i z e
O n e e l e m e n t o f r J
2 . U p d a t e w a s f o l l o w s :
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
G r a d i e n t d e s c e n t f o r L M S
1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . .
1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r
a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
2 . U p d a t e w a s f o l l o w s :
W e a r e t r y i n g t o m i n i m i z e
O n e e l e m e n t o f r J
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
G r a d i e n t d e s c e n t f o r L M S 1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l t o t a l e r r o r i s b e l o w a t h r e s h o l d ) 1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
2 . U p d a t e w a s f o l l o w s :
W e a r e t r y i n g t o m i n i m i z e
O n e e l e m e n t o f r J
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
G r a d i e n t d e s c e n t f o r L M S
1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l t o t a l e r r o r i s b e l o w a t h r e s h o l d )
1 .
C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r
a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
U p d a t e w a s f o l l o w s :
r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
W e a r e t r y i n g t o m i n i m i z e
O n e e l e m e n t o f r J
2 .
1 .
C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r
a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
U p d a t e w a s f o l l o w s : r : C a l l e d t h e l e a r n i n g r a t e
( F o r n o w , a s m a l l c o n s t a n t . W e w i l l g e t t o t h i s l a t e r )
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t f o r L M S
1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l t o t a l e r r o r i s b e l o w a t h r e s h o l d )
2 .
O n e e l e m e n t o f r J
T h i s a l g o r i t h m i s g u a r a n t e e d t o c o n v e r g e t o t h e m i n i m u m o f J i f r i s s m a l l e n o u g h . W h y ? T h e o b j e c t i v e J i s a c o n v e x f u n c t i o n
W e a r e t r y i n g t o m i n i m i z e
G r a d i e n t d e s c e n t f o r L M S 1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l t o t a l e r r o r i s b e l o w a t h r e s h o l d ) 1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
2 . U p d a t e w a s f o l l o w s :
G r a d i e n t d e s c e n t f o r L M S 1 . I n i t i a l i z e w 0
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l t o t a l e r r o r i s b e l o w a t h r e s h o l d ) 1 . C o m p u t e g r a d i e n t o f J ( w ) a t w t . C a l l i t r J ( w t )
E v a l u a t e t h e f u n c t i o n f o r e a c h t r a i n i n g e x a m p l e t o c o m p u t e t h e e r r o r a n d c o n s t r u c t t h e g r a d i e n t v e c t o r
2 . U p d a t e w a s f o l l o w s :
T h e w e i g h t v e c t o r i s n o t u p d a t e d u n t i l a l l e r r o r s a r e c a l c u l a t e d
W h y n o t m a k e e a r l y u p d a t e s t o t h e w e i g h t v e c t o r a s s o o n a s w e e n c o u n t e r e r r o r s i n s t e a d o f w a i t i n g f o r a f u l l p a s s o v e r t h e d a t a ?
W e a r e t r y i n g t o m i n i m i z e
I n c r e m e n t a l / S t o c h a s t i c g r a d i e n t d e s c e n t ” R e p e a t f o r e a c h e x a m p l e ( x i , y i )
P r e t e n d t h a t t h e e n t i r e t r a i n i n g s e t i s r e p r e s e n t e d b y t h i s s i n g l e e x a m p l e
U s e t h i s e x a m p l e t o c a l c u l a t e t h e g r a d i e n t a n d u p d a t e t h e m o d e l
” C o n t r a s t w i t h b a t c h g r a d i e n t d e s c e n t w h i c h m a k e s o n e u p d a t e t o t h e w e i g h t v e c t o r f o r e v e r y p a s s o v e r t h e d a t a
I n c r e m e n t a l / S t o c h a s t i c g r a d i e n t d e s c e n t
1 . I n i t i a l i z e
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l e r r o r b e l o w s o m e t h r e s h o l d )
F o r e a c h t r a i n i n g e x a m p l e ( , ) :
” U p d a t e w . F o r e a c h e l e m e n t o f t h e w e i g h t v e c t o r ( w j ) :
I n c r e m e n t a l / S t o c h a s t i c g r a d i e n t d e s c e n t
1 . I n i t i a l i z e
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l e r r o r b e l o w s o m e t h r e s h o l d )
F o r e a c h t r a i n i n g e x a m p l e ( , ) :
” U p d a t e w . F o r e a c h e l e m e n t o f t h e w e i g h t v e c t o r ( w j ) :
C o n t r a s t w i t h t h e p r e v i o u s m e t h o d , w h e r e t h e w e i g h t s a r e u p d a t e d o n l y a f t e r a l l e x a m p l e s a r e p r o c e s s e d o n c e
I n c r e m e n t a l / S t o c h a s t i c g r a d i e n t d e s c e n t
1 . I n i t i a l i z e
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l e r r o r b e l o w s o m e t h r e s h o l d )
F o r e a c h t r a i n i n g e x a m p l e ( , ) :
” U p d a t e w . F o r e a c h e l e m e n t o f t h e w e i g h t v e c t o r ( w j ) :
T h i s u p d a t e r u l e i s a l s o c a l l e d t h e W i d r o w - H o f f r u l e i n t h e n e u r a l n e t w o r k s l i t e r a t u r e
I n c r e m e n t a l / S t o c h a s t i c g r a d i e n t d e s c e n t
1 . I n i t i a l i z e
2 . F o r t = 0 , 1 , 2 , . . . . ( u n t i l e r r o r b e l o w s o m e t h r e s h o l d )
F o r e a c h t r a i n i n g e x a m p l e ( , ) :
” U p d a t e w . F o r e a c h e l e m e n t o f t h e w e i g h t v e c t o r ( w j ) :
O n l i n e / I n c r e m e n t a l a l g o r i t h m s a r e o f t e n p r e f e r r e d w h e n t h e t r a i n i n g s e t i s v e r y l a r g e
M a y g e t c l o s e t o o p t i m u m m u c h f a s t e r t h a n t h e b a t c h v e r s i o n
T h i s u p d a t e r u l e i s a l s o c a l l e d t h e W i d r o w - H o f f r u l e i n t h e n e u r a l n e t w o r k s l i t e r a t u r e
L e a r n i n g R a t e s a n d C o n v e r g e n c e
” I n t h e g e n e r a l ( n o n - s e p a r a b l e ) c a s e t h e l e a r n i n g r a t e r m u s t d e c r e a s e t o z e r o t o g u a r a n t e e c o n v e r g e n c e
” T h e l e a r n i n g r a t e i s c a l l e d t h e s t e p s i z e .
M o r e s o p h i s t i c a t e d a l g o r i t h m s c h o o s e t h e s t e p s i z e a u t o m a t i c a l l y a n d
c o n v e r g e f a s t e r
” C h o o s i n g a b e t t e r s t a r t i n g p o i n t c a n a l s o h a v e i m p a c t
” G r a d i e n t d e s c e n t a n d i t s s t o c h a s t i c v e r s i o n a r e v e r y s i m p l e a l g o r i t h m s
Y e t , a l m o s t a l l t h e a l g o r i t h m s w e w i l l l e a r n i n t h e c l a s s c a n b e t r a c e d b a c k t o g r a d i e n t d e c e n t a l g o r i t h m s f o r d i f f e r e n t l o s s f u n c t i o n s a n d d i f f e r e n t h y p o t h e s e s s p a c e s
L i n e a r r e g r e s s i o n : S u m m a r y
” W h a t w e w a n t : P r e d i c t a r e a l v a l u e d o u t p u t u s i n g a f e a t u r e r e p r e s e n t a t i o n o f t h e i n p u t
” A s s u m p t i o n : O u t p u t i s a l i n e a r f u n c t i o n o f t h e i n p u t s ” L e a r n i n g b y m i n i m i z i n g t o t a l c o s t
G r a d i e n t d e s c e n t a n d s t o c h a s t i c g r a d i e n t d e s c e n t t o f i n d t h e b e s t w e i g h t v e c t o r
T h i s p a r t i c u l a r o p t i m i z a t i o n c a n b e c o m p u t e d d i r e c t l y b y f r a m i n g t h e p r o b l e m a s a m a t r i x p r o b l e m