Deep Generative Models

CS504 - Fall 2020

Narayanan C Krishnan
ckn@[Link]
Story so far
• Neural networks for computation
• All feedforward structures

• But what about..

Deep Generative Models CS504 - Artificial Neural Networks 2

Consider this loopy network
+1 𝑖𝑓 𝑧 > 0 𝑦! = Θ $ 𝑤"! 𝑦" + 𝑏!
Θ 𝑧 =)
−1 𝑖𝑓 𝑧 ≤ 0 "#!

The output of a neuron

affects the input to the
neuron

• Each neuron is a perceptron with +1/-1 output

• Every neuron receives input from every other neuron
• Every neuron outputs signals to every other neuron
Deep Generative Models CS504 - Artificial Neural Networks 3
Hopfield Net
+1 𝑖𝑓 𝑧 > 0 𝑦! = Θ $ 𝑤"! 𝑦" + 𝑏!
Θ 𝑧 =)
−1 𝑖𝑓 𝑧 ≤ 0 "#!

A symmetric network:
𝑤!" = 𝑤"!

• Each neuron is a perceptron with +1/-1 output

• Every neuron receives input from every other neuron
• Every neuron outputs signals to every other neuron
Deep Generative Models CS504 - Artificial Neural Networks 4
Loopy network
𝑦! = Θ $ 𝑤"! 𝑦" + 𝑏!
𝑦! → −𝑦! "#!
if 𝑦! ∑"#! 𝑤"! 𝑦" + 𝑏! < 0
+1 𝑖𝑓 𝑧 > 0
Θ 𝑧 =)
−1 𝑖𝑓 𝑧 ≤ 0
• At each time each neuron receives a “field” ∑"#! 𝑤"! 𝑦" + 𝑏!
• If the sign of the field matches its own sign, it does not respond
• If the sign of the field opposes its own sign, it “flips” to match the
sign of the field

Deep Generative Models CS504 - Artificial Neural Networks 5

Loopy network
𝑦! = Θ $ 𝑤"! 𝑦" + 𝑏!
𝑦! → −𝑦! "#!
if 𝑦! ∑"#! 𝑤"! 𝑦" + 𝑏! < 0
+1 𝑖𝑓 𝑧 > 0
Θ 𝑧 =)
−1 𝑖𝑓 𝑧 ≤ 0
• At each time each neuron receives a “field” ∑"#! 𝑤"! 𝑦" + 𝑏!
• If the sign of the field matches its own sign, it does not respond
• If the sign of the field opposes its own sign, it “flips” to match the
A neuron “flips” if weighted sum of other
sign of the field neurons’ outputs is of the opposite sign
But this may cause other neurons to flip!

Deep Generative Models CS504 - Artificial Neural Networks 6

Example

• Red edges are +1, blue edges are -1

• Yellow nodes are -1, black nodes are +1
Deep Generative Models CS504 - Artificial Neural Networks 7
Example

• Red edges are +1, blue edges are -1

• Yellow nodes are -1, black nodes are +1
Deep Generative Models CS504 - Artificial Neural Networks 8
Example

• Red edges are +1, blue edges are -1

• Yellow nodes are -1, black nodes are +1
Deep Generative Models CS504 - Artificial Neural Networks 9
Loopy network

• If the sign of the field at any neuron opposes its own sign, it
“flips” to match the field
• Which will change the field at other nodes
• Which may then flip
• Which may cause other neurons including the first one to flip…
• And so on…

Deep Generative Models CS504 - Artificial Neural Networks 10

Loopy network

• If the sign of the field at any neuron opposes its own sign, it
“flips” to match the field
• Which will change the field at other nodes
• Which may then flip
• Which may cause other neurons including the first one to flip…

• Will this behavior continue for ever??

Deep Generative Models CS504 - Artificial Neural Networks 11

Loopy network
𝑦! = Θ % 𝑤"! 𝑦" + 𝑏!
"#!

+1 𝑖𝑓 𝑧 > 0
Θ 𝑧 =)
−1 𝑖𝑓 𝑧 ≤ 0
• Let 𝑦!" be the output of the i-th neuron just before it responds to the current field
• Let 𝑦!# be the output of the i-th neuron just after it responds to the current field
• If 𝑦!" = 𝑠𝑖𝑔𝑛 ∑$%! 𝑤$! 𝑦$ + 𝑏! , then 𝑦!# = 𝑦!"
• If the sign of the field matches its own sign, it does not flip

𝑦!# + 𝑤$! 𝑦$ + 𝑏! − 𝑦!" + 𝑤$! 𝑦$ + 𝑏! = 0

$%! $%!

Deep Generative Models CS504 - Artificial Neural Networks 12

Loopy network
𝑦! = Θ $ 𝑤"! 𝑦" + 𝑏!
"#!

+1 𝑖𝑓 𝑧 > 0
Θ 𝑧 =)
−1 𝑖𝑓 𝑧 ≤ 0
• If 𝑦!" ≠ 𝑠𝑖𝑔𝑛 ∑#$! 𝑤#! 𝑦# + 𝑏! , then 𝑦!% = −𝑦!"

𝑦!% 0 𝑤#! 𝑦# + 𝑏! − 𝑦!" 0 𝑤#! 𝑦# + 𝑏! = 2𝑦!% 0 𝑤#! 𝑦# + 𝑏!

#$! #$! #$!
• This term is always positive!

• Every flip of a neuron is guaranteed to locally increase

𝑦! 0 𝑤#! 𝑦# + 𝑏!
#$!

Deep Generative Models CS504 - Artificial Neural Networks 13

Globally
• Consider the following sum across all nodes

𝐷 𝑦2, 𝑦3, … , 𝑦4 = % 𝑦! % 𝑤"! 𝑦" + 𝑏!

! "#!

= % 𝑤!" 𝑦! 𝑦" + % 𝑏! 𝑦!
!,"#! !
• Assume 𝑤!! = 0

• For any unit 𝑘 that “flips” because of the local field

∆𝐷 𝑦6 = 𝐷 𝑦2, … , 𝑦67, … , 𝑦4 − 𝐷 𝑦2, … , 𝑦68, … , 𝑦4
Deep Generative Models CS504 - Artificial Neural Networks 14
Upon flipping a single unit
∆𝐷 𝑦$ = 𝐷 𝑦% , … , 𝑦$& , … , 𝑦' − 𝐷 𝑦% , … , 𝑦$( , … , 𝑦'
• Expanding
∆𝐷 𝑦$ = 𝑦$& − 𝑦$( $ 𝑤"$ 𝑦" + 𝑏$
"#$
• All other terms that do not include 𝑦6 cancel out

• This is always positive!

• Every flip of a unit results in an increase in 𝐷

Deep Generative Models CS504 - Artificial Neural Networks 15

Hopfield Net

• Flipping a unit will result in an increase (non-decrease) of

𝐷 = 0 𝑤!# 𝑦! 𝑦# + 0 𝑏! 𝑦!
!,#$! !

• 𝐷 is bounded

𝐷'() = 0 𝑤!# + 0 𝑏!
!,#$! !

• The minimum increment of 𝐷 in a flip is

∆𝐷'!* = min 2 0 𝑤#! 𝑦# + 𝑏!

!, {,! , !-...0}
#$!

• Any sequence of flips must converge in a finite number of steps

Deep Generative Models CS504 - Artificial Neural Networks 16

The Energy of a Hopfield Net
• Define the Energy of the network as

𝐸 = − $ 𝑤!" 𝑦! 𝑦" − $ 𝑏! 𝑦!
!,"#! !
• Just the negative of 𝐷

• The evolution of a Hopfield network constantly decreases its

energy

Deep Generative Models CS504 - Artificial Neural Networks 17

Evolution
𝐸 = − $ 𝑤!" 𝑦! 𝑦"
!,"*!

PE
state

• The network will evolve until it arrives at a local minimum in the

energy contour

Deep Generative Models CS504 - Artificial Neural Networks 18

Content-addressable memory

PE
state
• Each of the minima is a “stored” pattern
• If the network is initialized close to a stored pattern, it will inevitably evolve to
the pattern
• This is a content addressable memory
• Recall memory content from partial or corrupt values
• Also called associative memory
Deep Generative Models CS504 - Artificial Neural Networks 19
Evolution
𝐸 = − $ 𝑤!" 𝑦! 𝑦"
!,"*!

• The network will evolve until it arrives at a local minimum in the

energy contour
• We proved that every change in the network will result in decrease in
energy
• So path to energy minimum is monotonic
Deep Generative Models CS504 - Artificial Neural Networks 20
Evolution
1 +
𝐸 = − 𝐲 𝐖𝐲
2

𝑦! = Θ 0 𝑤#! 𝑦# + 𝑏!
#$!

• For threshold activations the energy contour is only defined on

a lattice
• Corners of a unit cube on [-1,1]N
• For tanh activations it will be a continuous function
Deep Generative Models CS504 - Artificial Neural Networks 21
Examples: Content addressable memory

• [Link]
Deep Generative Models CS504 - Artificial Neural Networks 22
Computational algorithm
1. Initialize network with initial pattern

𝑦! 0 = 𝑥! , 0≤𝑖 ≤𝑁−1

2. Iterate until convergence

𝑦! 𝑡 + 1 = Θ 8 𝑤"! 𝑦" , 0≤𝑖 ≤𝑁−1

"#!
• Very simple
• Updates can be done sequentially, or all at once
• Convergence
𝐸 = − $ $ 𝑤"! 𝑦" 𝑦!
! "#!
does not change significantly any more
Deep Generative Models CS504 - Artificial Neural Networks 23
Issues
• How do we make the network store a specific pattern or set of
patterns?

• How many patterns can we store?

• How to “retrieve” patterns better..

Deep Generative Models CS504 - Artificial Neural Networks 24

How do we remember a specific pattern?
• How do we teach a network
to “remember” this image

• For an image with 𝑁 pixels we need a network with 𝑁 neurons

• Every neuron connects to every other neuron
• Weights are symmetric (not mandatory)
'('(%)
• weights in all
<

Deep Generative Models CS504 - Artificial Neural Networks 25

Storing patterns: Training a network
1 -1

-1 1 1 -1

1 -1 -1 1

• A network that stores pattern 𝑃 also naturally stores – 𝑃

• Symmetry 𝐸(𝑃) = 𝐸(−𝑃) since 𝐸 is a function of yiyj

𝐸 = − 8 8 𝑤"! 𝑦" 𝑦!
! "$!
Deep Generative Models CS504 - Artificial Neural Networks 26
A network can store multiple patterns
-1

1 -1

PE
-1 1

state 1 -1

• Every stable point is a stored pattern

1 -1

• So we could design the net to store multiple patterns

• Remember that every stored pattern 𝑃 is actually two stored patterns, 𝑃
and −𝑃
Deep Generative Models CS504 - Artificial Neural Networks 27
Storing a pattern
-1 1

1 -1 1 -1
𝐸 = − $ $ 𝑤"! 𝑦" 𝑦!
! "*!
-1 1 1 -1

• Design {𝑤𝑖𝑗} such that the energy is a local minimum at the

desired 𝑃 = {𝑦𝑖}

Deep Generative Models CS504 - Artificial Neural Networks 28

Storing specific patterns
-1

1 -1

-1 1

• Storing 1 pattern: We want

𝑠𝑖𝑔𝑛 $ 𝑤"! 𝑦" = 𝑦! ∀𝑖
"#!
• This is a stationary pattern

Deep Generative Models CS504 - Artificial Neural Networks 29

Storing specific patterns
-1

1 -1
HEBBIAN LEARNING:
𝑤'( = 𝑦' 𝑦(
-1 1

• Storing 1 pattern: We want

𝑠𝑖𝑔𝑛 $ 𝑤"! 𝑦" = 𝑦! ∀𝑖
"#!
• This is a stationary pattern
• 𝑠𝑖𝑔𝑛 ∑"#! 𝑤"! 𝑦" = 𝑠𝑖𝑔𝑛 ∑"#! 𝑦" 𝑦! 𝑦" = 𝑠𝑖𝑔𝑛 ∑"#! 𝑦"< 𝑦! =
𝑠𝑖𝑔𝑛 𝑦! = 𝑦!
Deep Generative Models CS504 - Artificial Neural Networks 30
Storing specific patterns
-1

1 -1
HEBBIAN LEARNING:
𝑤'( = 𝑦' 𝑦(
-1 1

𝐸 = − $ $ 𝑤"! 𝑦" 𝑦! = − $ $ 𝑦!< 𝑦"<

! "*! ! "*!

= − $ $ 1 = −0.5𝑁(𝑁 − 1)
! "*!
• This is the lowest possible energy value for the network
Deep Generative Models CS504 - Artificial Neural Networks 31
Hebbian learning: Storing a 4-bit pattern

• Left: Pattern stored. Right: Energy map

• Stored pattern has lowest energy
• Gradation of energy ensures stored pattern (or its ghost) is recalled from everywhere
Deep Generative Models CS504 - Artificial Neural Networks 32
Storing multiple patterns
-1 1

1 -1 1 -1

-1 1 1 -1

• To store more than one pattern

B B
𝑤"! = $ 𝑦! 𝑦"
𝐲! ∈{𝐲! }
• {𝐲B } is the set of patterns to store
• Super/subscript 𝑝 represents the specific pattern
Deep Generative Models CS504 - Artificial Neural Networks 33
How many patterns can we store?

• Hopfield: For a network of 𝑁 neurons can store up to ~0.15𝑁

patterns through Hebbian learning
• Provided they are “far” enough

Deep Generative Models CS504 - Artificial Neural Networks 34

Parasitic Patterns
Target patterns Parasites

Energy

state
• Parasitic patterns can occur because sums of odd numbers of stored
patterns are also stable for Hebbian learning:
• 𝐲&'(')!*+ = 𝑠𝑖𝑔𝑛 𝐲' + 𝐲, + 𝐲-
• They are also from other random local energy minima from the
weights matrices themselves
Deep Generative Models CS504 - Artificial Neural Networks 35
Alternate Approach to Estimating the
Network
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 − 𝐛+ 𝐲
2

• Estimate 𝐖 (and 𝐛) such that

• 𝐸 is minimized for 𝐲2, 𝐲3, … , 𝐲?
• 𝐸 is maximized for all other 𝐲
• Caveat: Unrealistic to expect to store more than 𝑁 patterns, but
can we make those 𝑁 patterns memorable
Deep Generative Models CS504 - Artificial Neural Networks 36
Optimizing W (and b)
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 I = argmin $ 𝐸(𝐲)
𝐖
2 𝐖
𝐲∈𝐘"
The bias can be captured by
another fixed-value component

• Minimize total energy of target patterns

• Problem with this?

Deep Generative Models CS504 - Artificial Neural Networks 37

Optimizing W
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲
2

I = argmin $ 𝐸(𝐲) − $ 𝐸(𝐲)

𝐖
𝐖
𝐲∈𝐘" 𝐲∉𝐘"

• Minimize total energy of target patterns

• Maximize the total energy of all non-target patterns

Deep Generative Models CS504 - Artificial Neural Networks 38

Optimizing W
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 I = argmin $ 𝐸(𝐲) − $ 𝐸(𝐲)
𝐖
2 𝐖
𝐲∈𝐘" 𝐲∉𝐘"

• Simple gradient descent:

𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

Deep Generative Models CS504 - Artificial Neural Networks 39

Optimizing W

𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

• Can “emphasize” the importance of a pattern by repeating

• More repetitions à greater emphasis

Deep Generative Models CS504 - Artificial Neural Networks 40

Optimizing W

𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

• Can “emphasize” the importance of a pattern by repeating

• More repetitions à greater emphasis
• How many of these?
• Do we need to include all of them?
• Are all equally important?

Deep Generative Models CS504 - Artificial Neural Networks 41

The training again
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

• The first term tries to minimize the energy at target patterns

• Make them local minima
• Emphasize more “important” memories by repeating them more
frequently
Target patterns

Energy

Deep Generative Models CS504 - Artificial Neural Networks 42

state
The negative class
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

• The second term tries to “raise” all non-target patterns

• Do we need to raise everything?

Energy

Deep Generative Models CS504 - Artificial Neural Networks 43

state
Option 1: Focus on the valleys
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘" &𝐲GHIJJKL

• Focus on raising the valleys

• If you raise every valley, eventually they’ll all move up above the target
patterns, and many will even vanish

Energy

Deep Generative Models CS504 - Artificial Neural Networks 44

state
Identifying the valleys..
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘" &𝐲GHIJJKL

• Problem: How do you identify the valleys for the current 𝐖?

Energy

Deep Generative Models CS504 - Artificial Neural Networks 45

state
Identifying the valleys..

• Initialize the network randomly and let it evolve

• It will settle in a valley

Energy

Deep Generative Models CS504 - Artificial Neural Networks 46

state
Training the Hopfield network
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘" &𝐲GHIJJKL

• Initialize 𝐖
• Compute the total outer product of all target patterns
• More important patterns presented more frequently
• Randomly initialize the network several times and let it evolve
• And settle at a valley
• Compute the total outer product of valley patterns
• Update weights

Deep Generative Models CS504 - Artificial Neural Networks 47

Training the Hopfield network: SGD
version
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘" &𝐲GHIJJKL
• Initialize 𝐖
• Do until convergence, satisfaction, or death from boredom:
• Sample a target pattern 𝐲@
• Sampling frequency of pattern must reflect importance of pattern
• Randomly initialize the network and let it evolve
• And settle at a valley 𝐲%
• Update weights
• 𝐖 = 𝐖 + 𝜂 𝐲& 𝐲&' − 𝐲% 𝐲%'

Deep Generative Models CS504 - Artificial Neural Networks 48

Which valleys?
• Should we randomly sample valleys?
• Are all valleys equally important?

• Major requirement: memories must be stable

• They must be broad valleys

• Spurious valleys in the neighborhood of memories are more

important to eliminate

Energy

Deep Generative Models CS504 - Artificial Neural Networks 49

state
Identifying the valleys..

• Initialize the network at valid memories and let it evolve

• It will settle in a valley. If this is not the target pattern, raise it

Energy

Deep Generative Models CS504 - Artificial Neural Networks 50

state
Training the Hopfield network
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘" &𝐲GHIJJKL

• Initialize 𝐖
• Compute the total outer product of all target patterns
• More important patterns presented more frequently
• Initialize the network with each target pattern and let it evolve
• And settle at a valley
• Compute the total outer product of valley patterns
• Update weights

Deep Generative Models CS504 - Artificial Neural Networks 51

Training the Hopfield network: SGD
version
𝐖 = 𝐖 + 𝜂 $ 𝐲𝐲 + − $ 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘" &𝐲GHIJJKL
• Initialize 𝐖
• Do until convergence, satisfaction, or death from boredom:
• Sample a target pattern 𝐲@
• Sampling frequency of pattern must reflect importance of pattern
• Initialize the network at 𝐲@ and let it evolve
• And settle at a valley 𝐲%
• Update weights
• 𝐖 = 𝐖 + 𝜂 𝐲& 𝐲&' − 𝐲% 𝐲%'

Deep Generative Models CS504 - Artificial Neural Networks 52

A probabilistic interpretation of Hopfield
Nets
• For binary y the energy of a pattern is the analog of the
negative log likelihood of a Boltzmann distribution
• Minimizing energy maximizes log likelihood

1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 𝑃(𝐲) = 𝐶𝑒𝑥𝑝 −𝐸(𝐲)
2

Deep Generative Models CS504 - Artificial Neural Networks 53

Hopfield nets: Optimizing W
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 I = argmin $ 𝐸(𝐲) − $ 𝐸(𝐲)
𝐖
2 𝐖
𝐲∈𝐘" 𝐲∉𝐘"

• Simple gradient descent:

𝐖 = 𝐖 + 𝜂 $ 𝛼𝐲 𝐲𝐲 + − $ 𝛽 𝐸(𝐲) 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

More importance to more frequently More importance to more attractive

presented memories spurious memories

Deep Generative Models CS504 - Artificial Neural Networks 54

Hopfield nets: Optimizing W
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 I = argmin $ 𝐸(𝐲) − $ 𝐸(𝐲)
𝐖
2 𝐖
𝐲∈𝐘" 𝐲∉𝐘"

• Simple gradient descent:

𝐖 = 𝐖 + 𝜂 $ 𝛼𝐲 𝐲𝐲 + − $ 𝛽 𝐸(𝐲) 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

More importance to more frequently More importance to more attractive

presented memories spurious memories

Deep Generative Models

THIS LOOKS LIKE AN EXPECTATION!
CS504 - Artificial Neural Networks 55
Hopfield nets: Optimizing W
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲 I = argmin $ 𝐸(𝐲) − $ 𝐸(𝐲)
𝐖
2 𝐖
𝐲∈𝐘" 𝐲∉𝐘"
• Update rule

𝐖 = 𝐖 + 𝜂 $ 𝛼𝐲 𝐲𝐲 + − $ 𝛽 𝐸(𝐲) 𝐲𝐲 +
𝐲∈𝐘" 𝐲∉𝐘"

𝐖 = 𝐖 + 𝜂 𝐸𝐲~𝐘" 𝐲𝐲 + − 𝐸𝐲~O 𝐲𝐲 +
Natural distribution for variables: The Boltzmann Distribution

Deep Generative Models CS504 - Artificial Neural Networks 56

The Energy of the Network
Visible 𝐸 𝑆 = − % 𝑤!" 𝑠! 𝑠" − 𝑏! 𝑠!
Neurons !A"

𝑒𝑥𝑝 −𝐸(𝑆)
𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 −𝐸(𝑆′)

• We can define the energy of the system as before

• Since neurons are stochastic, there is disorder or entropy (with T = 1)
• The equilibrium probability distribution over states is the Boltzmann
distribution at T=1
• This is the probability of different states that the network will wander over at
equilibrium
Deep Generative Models CS504 - Artificial Neural Networks 57
The Hopfield net is a distribution
Visible 𝐸 𝑆 = − % 𝑤!" 𝑠! 𝑠" − 𝑏! 𝑠!
Neurons !A"

𝑒𝑥𝑝 −𝐸(𝑆)
𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 −𝐸(𝑆′)

• The stochastic Hopfield network models a probability distribution over states

• Where a state is a binary string
• Specifically, it models a Boltzmann distribution
• The parameters of the model are the weights of the network
• The probability that (at equilibrium) the network will be in any state is 𝑃 𝑆
• It is a generative model: generates states according to 𝑃 𝑆
Deep Generative Models CS504 - Artificial Neural Networks 58
The field at a single node
• Let 𝑆 and 𝑆 ′ be otherwise identical states that only differ in the i-th bit
• S has i-th bit = +1 and S’ has i-th bit = −1

𝑃 𝑆 = 𝑃 𝑠! = 1 𝑠"#! 𝑃(𝑠"#! )
𝑃 𝑆′ = 𝑃 𝑠! = −1 𝑠"#! 𝑃(𝑠"#! )

log 𝑃 𝑆 − log 𝑃 𝑆 ( = log 𝑃 𝑠! = 1 𝑠"#! − log 𝑃 𝑠! = −1 𝑠"#!

𝑃 𝑠! = 1 𝑠"#!
log 𝑃 𝑆 − log 𝑃 𝑆( = log
1 − 𝑃 𝑠! = 1 𝑠"#!

Deep Generative Models CS504 - Artificial Neural Networks 59

The field at a single node
• Let 𝑆 and 𝑆 ′ be the states with the ith bit in the +1 and −1 states
log 𝑃(𝑆) = −𝐸 𝑆 + 𝐶
1
𝐸 𝑆 = − 𝐸()* ! + $ 𝑤" 𝑠" + 𝑏!
2
"+!
1
𝐸 𝑆′ = − 𝐸()* ! − $ 𝑤" 𝑠" − 𝑏!
2
"+!

• log𝑃 𝑆 − log𝑃 𝑆 , = 𝐸 𝑆 , − 𝐸 𝑆 = ∑"+! 𝑤" 𝑠" + 𝑏!

Deep Generative Models CS504 - Artificial Neural Networks 60

The field at a single node
𝑃 𝑠! = 1 𝑠"#!
log = $ 𝑤" 𝑠" + 𝑏!
1 − 𝑃 𝑠! = 1 𝑠"#!
"#!
• Giving us
1
𝑃 𝑠! = 1 𝑠"#! =
( ∑&'( X& Y& &Z(
1+ 𝑒
• The probability of any node taking value 1 given other node
values is a logistic

Deep Generative Models CS504 - Artificial Neural Networks 61

The Hopfield net is a distribution
Visible 𝑧! = % 𝑤"! 𝑠" + 𝑏!
Neurons "

1
𝑃(𝑠! = 1|𝑠"#! ) =
1 + 𝑒 8D!

• The Hopfield net is a probability distribution over binary sequences

• The Boltzmann distribution

• The conditional distribution of individual bits in the sequence is a

logistic
Deep Generative Models CS504 - Artificial Neural Networks 62
 Running the network
Visible 𝑧! = % 𝑤"! 𝑠" + 𝑏!
Neurons "

1
𝑃(𝑠! = 1|𝑠"#! ) =
1 + 𝑒 8D!

• Initialize the neurons

• Cycle through the neurons and randomly set the neuron to 1 or -1 according to
the probability given above
• Gibbs sampling: Fix N-1 variables and sample the remaining variable
• After many many iterations (until “convergence”), sample the individual neurons

Deep Generative Models CS504 - Artificial Neural Networks 63

The Boltzmann Machine
1
𝑧! = % 𝑤"! 𝑠"
𝑇
"

1
𝑃(𝑠! = 1|𝑠"#! ) =
1 + 𝑒 8D!

• The entire model can be viewed as a generative model

• Has a probability of producing any binary vector 𝐲:
1 +
𝐸(𝐲) = − 𝐲 𝐖𝐲
2
𝐸(𝐲)
𝑃 𝐲 = 𝐶𝑒𝑥𝑝 −
𝑇
Deep Generative Models CS504 - Artificial Neural Networks 64
 Training the network 𝐸 𝑆 = − % 𝑤!" 𝑠! 𝑠"
!A"
𝑒𝑥𝑝 −𝐸(𝑆)
𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 −𝐸(𝑆′)

𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠! 𝑠"

𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠!C 𝑠"C
• Training a Hopfield net: Must learn weights to “remember” target states and
“dislike” other states
• “State” == binary pattern of all the neurons
• Training Boltzmann machine: Must learn weights to assign a desired probability
distribution to states
• This should assign more probability to patterns we “like” (or try to memorize) and less to
other patterns
Deep Generative Models CS504 - Artificial Neural Networks 65
Training the network 𝐸 𝑆 = − % 𝑤!" 𝑠! 𝑠"
Visible
!A"
Neurons
𝑒𝑥𝑝 −𝐸(𝑆)
𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 −𝐸(𝑆′)

𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠! 𝑠"

𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠!C 𝑠"C
• Must train the network to assign a desired probability distribution to states
• Given a set of “training” inputs 𝑆2, … , 𝑆?
• Assign higher probability to patterns seen more frequently
• Assign lower probability to patterns that are not seen at all

• Alternately viewed: maximize likelihood of stored states

Deep Generative Models CS504 - Artificial Neural Networks 66
Maximum Likelihood Training
log 𝑃 𝑆 = 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
!$" )( !$"

Average log likelihood of training vectors

1
ℒ = 8 log 𝑃 𝑆 (to be maximized)
𝑁
)∈𝐒

1
= 8 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
𝑁
) !$" )( !$"

• Maximize the average log likelihood of all “training” vectors 𝐒 =

{𝑆1, 𝑆2, … , 𝑆𝑁}
• In the first summation, si and sj are bits of S
• In the second, si’ and sj’ are bits of S’
Deep Generative Models CS504 - Artificial Neural Networks 67
Maximum Likelihood Training
1
ℒ= 8 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
𝑁
) !$" )( !$"

𝑑ℒ 1
= 8 𝑠! 𝑠" −? ? ?
𝑑𝑤!" 𝑁
)

• We will use gradient ascent, but we run into a problem..

• The first term is just the average sisj over all training patterns
• But the second term is summed over all states
• Of which there can be an exponential number!

Deep Generative Models CS504 - Artificial Neural Networks 68

The second term
𝑑log ∑)( 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠!( 𝑠"( 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠!( 𝑠"(
=8 𝑠!( 𝑠"(
𝑑𝑤!" ∑)" 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠!" 𝑠""
)(

𝑑log ∑)( 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠!( 𝑠"(

= 8 𝑃(𝑆 ( )𝑠!( 𝑠"(
𝑑𝑤!"
)(

• The second term is simply the expected value of sisj, over all
possible values of the state
• We cannot compute it exhaustively, but we can compute it by
sampling!

Deep Generative Models CS504 - Artificial Neural Networks 69

Estimating the second term
𝑑log ∑)( 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠!( 𝑠"(
= 8 𝑃(𝑆 ( )𝑠!( 𝑠"(
𝑑𝑤!"
)(

1
% 𝑃(𝑆 C )𝑠!C 𝑠"C ≈ % 𝑠!C 𝑠"C
𝑀
BC BC∈𝐒"#$%&'"

• The expectation can be estimated as the average of samples

drawn from the distribution

Deep Generative Models CS504 - Artificial Neural Networks 70

Maximum Likelihood Training
Sampled estimate
1
log 𝑃 𝐒 = 8 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
𝑁
) !$" )(∈𝐒!"#$% !$"

𝑑 log 𝑃 𝐒 1 1
= 8 𝑠! 𝑠" − 8 𝑠!( 𝑠"(
𝑑𝑤!" 𝑁 𝑀
) )(∈𝐒!"#$%

𝑑 log 𝑃 𝐒
𝑤!" = 𝑤!" + 𝜂
𝑑𝑤!"

• The overall gradient ascent rule

Deep Generative Models CS504 - Artificial Neural Networks 71

Adding Capacity to the Hopfield Network
/ Boltzmann Machine
• The network can store up to 𝑁 𝑁-bit patterns
• How do we increase the capacity

Deep Generative Models CS504 - Artificial Neural Networks 72

Expanded Network K Neurons
N Neurons

• New capacity: ~(𝑁 + 𝐾) patterns

• Although we only care about the pattern of the first N neurons
• We’re interested in N-bit patterns
Deep Generative Models CS504 - Artificial Neural Networks 73
Terminology Hidden
Visible
Neurons
Neurons

• Terminology:
• The neurons that store the actual patterns of interest: Visible neurons
• The neurons that only serve to increase the capacity but whose actual values
are not important: Hidden neurons
• These can be set to anything in order to store a visible pattern

Deep Generative Models CS504 - Artificial Neural Networks 74

Training the network Hidden
Visible
Neurons
Neurons

• For a given pattern of visible neurons, there are any number of hidden
patterns (2K)
• Which of these do we choose?
• Ideally choose the one that results in the lowest energy
• But that’s an exponential search space!
Deep Generative Models CS504 - Artificial Neural Networks 75
The patterns
• In fact we could have multiple hidden patterns coupled with any
visible pattern
• These would be multiple stored patterns that all give the same visible
output
• How many do we permit

• Do we need to specify one or more particular hidden patterns?

• How about all of them?

Deep Generative Models CS504 - Artificial Neural Networks 76

With hidden neurons Hidden
Visible
Neurons
Neurons

• Now, with hidden neurons the complete state pattern for even
the training patterns is unknown
• Since they are only defined over visible neurons

Deep Generative Models CS504 - Artificial Neural Networks 77

 With hidden neurons
Hidden
Visible
Neurons
Neurons
𝑒𝑥𝑝 −𝐸(𝑆)
𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 −𝐸(𝑆′)

𝑃 𝑆 = 𝑃(𝑉, 𝐻)

𝑃 𝑉 = % 𝑃(𝑆)
G
• We are interested in the marginal probabilities over visible bits
• We want to learn to represent the visible bits
• The hidden bits are the “latent” representation learned by the network

• 𝑆 = (𝑉, 𝐻)
• 𝑉 = visible bits
• 𝐻 = hidden bits
Deep Generative Models CS504 - Artificial Neural Networks 78
Training the network 𝐸 𝑆 = − % 𝑤!" 𝑠! 𝑠"
Visible
!A"
Neurons
𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠! 𝑠"
𝑃 𝑆 =
∑BC 𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠!C 𝑠"C

∑G 𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠! 𝑠"

𝑃 𝑉 =
∑BC 𝑒𝑥𝑝 ∑!A" 𝑤!" 𝑠!C 𝑠"C

• Must train the network to assign a desired probability

distribution to visible states
• Probability of visible state sums over all hidden states

Deep Generative Models CS504 - Artificial Neural Networks 79

Maximum Likelihood Training
log 𝑃 𝑉 = log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
0 !$" )( !$"

1 Average log likelihood of training vectors

ℒ = 8 log 𝑃 𝑉 (to be maximized)
𝑁
1∈𝐕

1
= 8 log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
𝑁
1∈𝐕 0 !$" )( !$"
• Maximize the average log likelihood of all visible bits of “training” vectors 𝐕 =
{𝑉1, 𝑉2, … , 𝑉𝑁}
• The first term also has the same format as the second term
• Log of a sum
• Derivatives of the first term will have the same form as for the second term

Deep Generative Models CS504 - Artificial Neural Networks 80

Maximum Likelihood Training
1
ℒ = 8 log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠! 𝑠" − log 8 𝑒𝑥𝑝 8 𝑤!" 𝑠!( 𝑠"(
𝑁
1∈𝐕 0 !$" )( !$"

( (
𝑑ℒ 1 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠! 𝑠" ( (
𝑒𝑥𝑝 ∑ !$" 𝑤!" 𝑠! 𝑠" ( (
= 88 " "
𝑠! 𝑠" − 8 " "
𝑠! 𝑠"
𝑑𝑤!" 𝑁 ∑0" 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠! 𝑠" ∑)" 𝑒𝑥𝑝 ∑!$" 𝑤!" 𝑠! 𝑠"
1∈𝐕 0 )(

𝑑ℒ 1
= 8 8 𝑃 𝑆|𝑉 𝑠! 𝑠" − 8 𝑃(𝑆 ( )𝑠!( 𝑠"(
𝑑𝑤!" 𝑁
1∈𝐕 0 )(
• We’ve derived this math earlier
• But now both terms require summing over an exponential number of states
• The first term fixes visible bits, and sums over all configurations of hidden states for each visible
configuration in our training set
• But the second term is summed over all states

Deep Generative Models CS504 - Artificial Neural Networks 81

Step 1 Hidden
Visible
Neurons
Neurons

• For each training pattern 𝑉!

• Fix the visible units to 𝑉!
• Let the hidden neurons evolve from a random initial point to generate 𝐻!
• Generate 𝑆! = [𝑉! , 𝐻! ]
• Repeat K times to generate synthetic training
𝐒 = {𝑆/,/ , 𝑆/,1 , … , 𝑆/2 , 𝑆1,/ , … , 𝑆3,2 }

Deep Generative Models CS504 - Artificial Neural Networks 82

Step 2 Hidden
Visible
Neurons
Neurons

• Now unclamp the visible units and let the entire network evolve
several times to generate
𝐒Y!deJ = {𝑆Y!deJ,% , 𝑆Y!deJ,%G< , … , 𝑆Y!deJ,f }

Deep Generative Models CS504 - Artificial Neural Networks 83

Overall Training 𝑑 log 𝑃 𝐒 1 1
= 8 𝑠! 𝑠" − 8 𝑠!( 𝑠"(
𝑑𝑤!" 𝑁𝐾 𝑀
𝑺 )(∈𝐒!"#$%

𝑑 log 𝑃 𝐒
𝑤!" = 𝑤!" − 𝜂
𝑑𝑤!"

• Initialize weights
• Run simulations to get clamped and unclamped training samples
• Compute gradient and update weights
• Iterate

Deep Generative Models CS504 - Artificial Neural Networks 84

Boltzmann machines
• Stochastic extension of Hopfield nets
• Enables storage of many more patterns than Hopfield nets
• But also enables computation of probabilities of patterns, and
completion of pattern
• Issues
• Training takes for ever
• Doesn’t really work for large problems
• A small number of training instances over a small number of bits

Deep Generative Models CS504 - Artificial Neural Networks 85

Solution: Restricted Boltzmann Machines
HIDDEN

VISIBLE
• Partition visible and hidden units
• Visible units ONLY talk to hidden units
• Hidden units ONLY talk to visible units
• Restricted Boltzmann machine..
• Originally proposed as “Harmonium Models” by Paul Smolensky

Deep Generative Models CS504 - Artificial Neural Networks 86

Solution: Restricted Boltzmann Machines
HIDDEN

VISIBLE

𝑧! = % 𝑤"! 𝑠! + 𝑏! 1
𝑃(𝑠! = 1) =
" 1 + 𝑒 8D!
• Still obeys the same rules as a regular Boltzmann machine
• But the modified structure adds a big benefit..
Deep Generative Models CS504 - Artificial Neural Networks 87
Solution: Restricted Boltzmann Machines
HIDDEN

VISIBLE

𝑧! = % 𝑤"! 𝑣! + 𝑏! 1
HIDDEN 𝑃(ℎ! = 1) =
" 1 + 𝑒 8D!

𝑦! = % 𝑤"! ℎ! + 𝑏! 1
VISIBLE 𝑃(𝑣! = 1) =
" 1 + 𝑒 8H!
Deep Generative Models CS504 - Artificial Neural Networks 88
Sampling: Restricted Boltzmann machine
𝑧! = 8 𝑤"! 𝑣! + 𝑏!
HIDDEN "
1
𝑃(ℎ! = 1) =
1 + 𝑒 45"

VISIBLE

• For each sample:

• Anchor visible units
• Sample from hidden units
• No looping!!

Deep Generative Models CS504 - Artificial Neural Networks 89

Sampling: Restricted Boltzmann machine
HIDDEN

VISIBLE

𝑧! = % 𝑤"! 𝑣! + 𝑏! 𝑦! = % 𝑤"! ℎ! + 𝑏!
" "
1 1
𝑃(ℎ! = 1) = 𝑃(𝑣! = 1) =
1 + 𝑒 8D! 1 + 𝑒 8H!
• For each sample:
• Iteratively sample hidden and visible units for a long time
• Draw final sample of both hidden and visible units
Deep Generative Models CS504 - Artificial Neural Networks 90
Pictorial hrepresentation
h h
of RBM training
h
0 1 2 ∞

v0 v1 v2 v∞
• For each sample:
• Initialize 𝑉I (visible) to training instance value
• Iteratively generate hidden and visible units
• For a very long time

Deep Generative Models CS504 - Artificial Neural Networks 91

Pictorial hrepresentation
h h
of RBM training
h
0 j 1 j 2 j ∞ j

i v0 i v1 i v2 i v∞
• Gradient (showing only one edge from visible node i to hidden node
j)
¶ log p(v) 0 ¥
= <vi h j > - <vi h j >
¶wij
• <vi, hj> represents average over many generated training samples

Deep Generative Models CS504 - Artificial Neural Networks 92

A Shortcut: Contrastive
h h
Divergence
0 j 1 j

i v0 i v1
• Sufficient to run one iteration!
¶ log p (v)
= <vi h j > 0 - <vi h j >1
¶wij

• This is sufficient to give you a good estimate of the gradient

Deep Generative Models CS504 - Artificial Neural Networks 93

Restricted Boltzmann Machines
• Excellent generative models for binary (or binarized) data
• Can also be extended to continuous-valued data
• “Exponential Family Harmoniums with an Application to Information
Retrieval”, Welling et al., 2004
• Useful for classification and regression
• How?
• More commonly used to pretrain models

Deep Generative Models CS504 - Artificial Neural Networks 94

Continuous-values RBMs
HIDDEN

VISIBLE

𝑧! = % 𝑤"! 𝑣! + 𝑏! 1
HIDDEN 𝑃(ℎ! = 1) =
" 1 + 𝑒 8D!

VISIBLE 𝑦! = % 𝑤"! ℎ! + 𝑏! 𝑃(𝑣! ) = 𝑟(𝑦! )𝑒𝑥𝑝 𝑦!

"

Hidden units may also be continuous values

Deep Generative Models CS504 - Artificial Neural Networks 95
Other variants

• Left: “Deep” Boltzmann machines

• Right: Helmholtz machine
• Trained by the “wake-sleep” algorithm

Deep Generative Models CS504 - Artificial Neural Networks 96