Transcript Document

Energy function:
E(S1,…,SN) = - ½ i Σ= j Wij Si Sj + C (Wii = P/N)
(Lyapunov function)
• Attractors= local minima of energy
function.
• Inverse states
• Mixture states
Spurious minima
• Spin glass states
Magnetic Systems
• Ising Model: Si
spins
• Field acting on spin i:
hi = wij Sj + hext where wij is exchange
interaction strength and wij = wji
At low temperature Sj = sgn(hi)
Effect of temperature:
Glauler :
+1, with probability g( hi)
Si =
-1, with probability 1- g( hi)
Where g(h) =
1
1 + e –2bh
b= 1/ ( K * T)
K = Boltzman’s constant
T = temperature
Stochastic hopfield nets
Prob ( Si = + 1) =
1
1 + e +–2bhi
b = 1/T
Optimization with HNN
Weighted Matching Problem
N points, dij distance between i & j
Link in pairs : each point linked to exactly one
other point and total length MINIMUM.
1. Encoding:
N x N neurons, (nij )
•
1<= i <= N
1<=j<= N
activation of neuron ij:
1, if Ξ link from i to j
nij = 0, otherwise.
2. Quantity to minimize:
total length L= i<j
Σ dij nij
3. Constraints: n = 1, V i
4. Energy function:
Quantity to minimize + constraint penalty
E ([nij ]) = Σ dij nij + (γ /2) Σ (1- Σj nij)2
i<j
i
5. Reduce energy function to summation of
quadratic and linear terms.
1. Coefficients of linear terms are thresholds of
units.
2. Coefficients of quadratic terms are the
weights between neurons.
E ( n ) = …= (Nγ)/2 + Σ
(d -γ )nij + γ Σ nij nik
I<j ij
i,j,k
So, weightij, kl =
- γ, if i,j & k,l have index in common
φ, otherwise.
Thresholds of node nij : dij-γ
Traveling salesman problem (TSP)
• NP- Complete
• N x N nodes : nij = 1 iff city I is visited at j –th stop in tour.
• Minimize:
– L = ½ Σ dij nia (nj,a+1 + nj,a-1 )
i,j,a
• Constraints:
Σa nia = 1, V city i
Σ nia = 1, V city a
i
• Energy:
e=½Σ
d
n
(n
+
n
)
+
(γ
/2)
[
Σ (1- Σ
ij
ia
j,a+1
j,a-1
a
i
i,j,a
2
2
nia) + Σ (1- Σ nia) ]
i
a
=…= ½ i,j,a
Σ dij nia nj,a+1 +½ i,j,a
Σ dij nia nj,a-1 + γ Σ
i!=j
nia nja + γ Σ nia njb - γ Σ nia + γ N
a!=b
i,a
So, threshold : - γ for each unit.
weights : γ , between units on same row or
column
dij , between units on different columns
Reinforcement Learning ( Learn with critic,
not teacher)
• Associative Reward – penalty algo ( ARP)
• Stochastic units:
1
Prob( Si = + 1) =
1 + e +–2bhi
hi = Σ wij vj
vj = activation of hidden unit or net
inputs ξj themselves.
• ξiμ = Siμ , if γμ = +1 (reward)
-Siμ , if γμ = -1 (penalty)