neurwnika diktua, suneirmikec mnhmec kai beltistopoihsh j ...€¦ · geniko tmhma, poluteqnikh...
TRANSCRIPT
Neurwnika Diktua, Suneirmikec Mnhmec kai Beltistopoihsh
J. KeqagiacGeniko Tmhma, Poluteqnikh Sqolh, APJ
1
O Stoqoc
H sqediash enoc dunamikou susthmatoc pou apojhkeuei kai anakalei protupa
Upologistiko Paradeigma
2
Biologiko Upobajro
• O egkefaloc apoteleitai apo 1011 neurwnec (neurika kuttara).
• Enac neurwnac apoteleitai apo to swma kai touc dendritec.
• Oi dendritec sundeoun touc neurwnec metaxu touc.
• Mesw qhmikwn antidrasewn to hlektriko fortio enoc neurwna auxanetai meqri na xeperasei enakatwfli, opote o neurwnac apofortizetai.
3
Istorikh Anadromh
• Oi McCulloch & Pitts to 1943 proteinan ena aplopoihmeno montelo tou neurwna:
xn (t + 1) =12Sgn
[∑m
wnmxm (t)
]+
12.
• Auto to montelo qrhsimopoihjhke wc basiko domiko stoiqeio diaforwn neurwnikwn diktuwn, toopoia kapoioi ereunhtec qrhsimopoihsan gia na montelopoihsoun to anjrwpino neuriko susthmakai alloi gia na dhmiourghsoun teqnhta susthmata me nohmona sumperifora (teqnhtaneurwnika diktua).
• Ena tupoc neurwnikou diktuou pou melethjhke se megalh ektash einai to neurwniko diktuo touHopfield kai oi parallagec tou. Ta neurwnika diktua autou tou tupou onomazontai kai suneir-mikec mnhmec.
4
To Diktuo Hopfield
Dhl. gia t = 0, 1, ... kai n = 1, 2, ..., N :
Parallhlh Leitourgia: xn (t + 1) = Sgn
[N∑
m=1
wnmxm (t)− un
](1)
Seiriakh Leitourgia: xn (t + 1) = Sgn
[n−1∑m=1
wnmxm (t + 1) +N∑
m=n
wnmxm (t)− un
](2)
5
Basikec Arqec
Ta (1) kai (2) einai dunamika susthmata:
• diakritou qronou (t = 0, 1, 2, ...),
• me dianusma katastashc x (t) = [x1 (t) , x2 (t) , ..., xN (t)]T ∈ {−1, 1}N .
Parametroi tou susthmatoc einai:
• o sunaptikoc pinakac W opou Wmn = wmn (m, n = 1, 2, ..., N),
• to dianusma katwfliwn u opou un = un (n = 1, 2, ..., N).
Ta (1) kai (2) qarakthrizontai apo:
• Parallhlh / Katanemhmenh Leitourgia (Parallel Distributed Processing )
• Stoiqeiwdeic Epexergastec (Neurwnec)
6
Orismoc 1 Leme oti to dunamiko susthma me dianusma katastashc x (t) eqei
1. stajero shmeio x0 an uparqei τ tetoio wste
∀t ≥ τ : x (t + 1) = x (t) ;
2. kuklo an uparqoun τ, T tetoia wste
∀t ≥ τ : x (t + T ) = x (t) .
O arijmoc τ legetai mhkoc metabashc.
Parathrhsh. Pollec forec sta parakatw ja leme (kataqrhstika!) oti to dunamiko susthma eqeistajero shmeio an uparqei kapoia sunarthsh J (·) tetoia wste J (x (t + 1)) =J (x (t)) (kai oti eqeikuklo an uparqei kapoia sunarthsh J (·) tetoia wste J (x (t + T )) =J (x (t))).
7
Energeia / Sunarthsh Lyapunov
Orizoume wc energeia enoc diktuou Hopfield (W,u) thn tetragwnikh sunarthsh
E (x) = −12
N∑m=1
N∑n=1
wmnxmxn +N∑
n=1
unxn = −12xTWx + xTu
8
Sugklish se Seiriakh Leitourgia
Protash 2 Estw oti o sunaptikoc pinakac W einai summetrikoc kai ta diagwnia stoiqeia einai mharnhtika. Tote, gia to seiriako diktuo (2) kai gia t = 0, 1, ... eqoume :
x (t + 1) 6= x (t)⇒ E (x (t + 1)) < E (x (t)) .
Porisma 3 Estw oti o sunaptikoc pinakac W einai summetrikoc kai ta diagwnia stoiqeia einai mharnhtika. Tote, to seiriako diktuo (2) den eqei kuklouc kai eqei toulaqiston ena stajero shmeio. Gia tomhkoc metabashc τ isquoun ta exhc fragmata.
1. An ola ta stoiqeia sthn diagwnio tou W einai jetika, tote
τ ≤M +
∑Nn=1 |un|
w.
2. An wmn ∈ {0,±1,±2, ...} tote
τ ≤2(M +
∑Nn=1 |un|
)1 + 2w
.
3. An |wmn| ∈ {0, 1} toteτ ≤ 5
2N2.
Sta parapanw M einai to ajroisma twn⌊n2/4
⌋megaluterwn stoiqeiwn |wmn| (me m 6= n) kai w =
min1≤n≤N wnn.
9
Sugklish se Parallhlh Leitourgia
Protash 4 Estw oti o sunaptikoc pinakac W einai jetikoc orismenoc. Tote, gia to parallhlo diktuo(1) kai gia t = 0, 1, ... eqoume :
x (t + 1) 6= x (t)⇒ E (x (t + 1)) < E (x (t)) .
Porisma 5 Estw oti o sunaptikoc pinakac W einai jetikoc orismenoc kai ta diagwnia stoiqeia einai mharnhtika. Tote, to parallhlo diktuo (1) den eqei kuklouc kai eqei toulaqiston ena stajero shmeio. Giato mhkoc metabashc τ isquoun ta exhc fragmata.
1. Se kaje periptwsh
τ ≤M +
∑Nn=1 |un|
λmin.
2. An o W einai summetrikoc kai wmn ∈ {0,±1,±2, ...} tote
τ ≤ 4N∑
n=1
∑m>n
|wmn|+ 2N∑
n=1
|wnn|+ 4N∑
n=1
|un| .
3. An o W einai summetrikoc kai |wmn| ∈ {0, 1} tote
τ ≤ 6N2.
Sta parapanw M einai to ajroisma twn⌊N2/4
⌋megaluterwn stoiqeiwn |wmn| (me m 6= n) kai λmin
einai h elaqisth idiotimh tou W.
10
Problhmata Analushc kai Sunjeshc
• Estw oti dinontai ta protupa dianusmata x(1),x(2), ...,x(P ). Mporoume na sqediasoume ena diktuotou tupou (1) h (2) (dhl. na epilexoume W kai u) gia to opoio ta x(1),x(2), ...,x(P ) einai stajerashmeia?
• An h apanthsh sto parapanw erwthma einai katafatikh, einai ta x(1),x(2), ...,x(P ) eustajh sta-jera shmeia? Poia einai h aktina sugklishc autwn?
• An h apanthsh sta prohgoumena erwthmata enai katafatikh gia kapoia mejodo epiloghc twn Wkai u, einai dunaton h mejodoc auth na dhmiourgei kai alla, “parasitika” stajera shmeia h́ kuklikhsumperifora?
11
Sunjesh: O Kanonac tou Hebb
Estw oti jeloume na apojhkeusoume ta protupa dianusmata x(1),x(2), ...,x(P ). Ac orisoume ton pinakaprotupwn
X =[x(1),x(2), ...,x(P )
].
Enac jemeliwdhc kanonac sqediashc einai o
Kanonac touHebb
W=1P
P∑p=1
x(p)(x(p)
)T=
1P
XXT .
12
Estw oti ta protupa dianusmata einai orjogwnia:(x(p)
)Tx(q) = N · δpq =
{N gia p = q0 gia p 6= q.
Tote gia p = 1, 2, ..., P eqoume
Wx(p) =N
Px(p) (3)
opote
Sgn(Wx(p)
)= Sgn
(N
Px(p)
)= Sgn
(x(p)
)(4)
kai ara ta x(1),x(2), ...,x(P ), einai stajera shmeia tou diktuou (me mhdeniko dianusma katwfliwn).
Se pollec praktikec periptwseic (eidika otan P � N) ta protupa dianusmata einai kata proseggishorjogwnia kai mporoume na elpizoume oti h (3) isquei kata proseggish kai h (4) akribwc (opote tax(1),x(2), ...,x(P ), einai stajera shmeia).
13
Uparqoun diaforec parallagec tou kanona tou Hebb , p.q.:
�����������������������������������Kanonac touHebb me Mhdenikh Diagwnio
W=1P
XXT − I,
(Tote, an N > P eqoume Wx(p) =(
NP − 1
)x(p) ⇒ Sgn
(Wx(p)
)= Sgn
(x(p)
)).
�����������������������������������Stajmismenoc Kanonac touHebb
W= XΛXT
(me Λ = diag (λ1, ..., λP ), λp ≥ 0 kai∑P
p=1 λp = 1)
14
Sunjesh: O Kanonac Probolhc
Eidame oti mia ikanh sunjhkh wste ta x(1),x(2), ...,x(P ) na einai stajera shmeia tou diktuou (me mhdenikodianusma katwfliwn) einai h
Sgn(Wx(p)
)= Sgn
(x(p)
).
Enac aploc tropoc gia na isquei auto einai na eqoume Wx(p) = x(p) gia kaje p = 1, 2, .., P , dhl.
WX = X (5)
Otan P < N h (5) eqei apeirec luseic, kai h pio gnwsth ex autwn einai h probolh
Kanonac Probolhc:
W = X(XTX
)−1XT .
15
Protash 6 Estw oti o sunaptikoc pinakac W proerqetai apo
1. Ton kanona tou Hebb (me h qwric mhdenikh diagwnio)
2. Ton stajmismeno kanona tou Hebb
3. Ton kanona probolhc
Tote o W einai summetrikoc, jetikoc orismenoc kai eqei mh arnhtika diagwnia stoiqeia.
16
Porisma 7 Estw oti o sunaptikoc pinakac W proerqetai apo
1. Ton kanona tou Hebb (me h qwric mhdenikh diagwnio)
2. Ton stajmismeno kanona tou Hebb
3. Ton kanona probolhc
Tote to seiriako diktuo (1) den eqei kuklouc kai ta x(1), x(2), ..., x(P ) einai stajera shmeia.
Porisma 8 Estw oti o sunaptikoc pinakac W proerqetai apo
1. Ton kanona tou Hebb (me h qwric mhdenikh diagwnio)
2. Ton stajmismeno kanona tou Hebb
3. Ton kanona probolhc
Tote to parallhlo diktuo (2) den eqei kuklouc kai ta x(1), x(2), ..., x(P ) einai stajera shmeia.
17
Arijmoc kai Fush twn Stajerwn ShmeiwnAktina Sugklishc
Parathrhsh. An to x = [x1, ..., xN ]T einai stajero shmeio enoc diktuou, tote to y = −x einai epishc
stajero shmeio.
Erwthma. Poia einai h aktina sugklishc enoc stajerou shmeiou?
18
Orismoc 9 Apostash (Hamming ) twn x kai y: d (x,y) = 12
∑Nn=1 |xn − yn|.
Orismoc 10 Geitonia tou x me aktina r: Nr (x) = {y :d (x,y) ≤ r}.
Orismoc 11 H aktina sugklishc-se-1-bhma enoc stajerou shmeiou x einai:
r1 (x) = max {r : x (0) ∈ Nr (x)⇒ x (1) = x)}
kai h geitonia sugklishc-se-1-bhma enoc stajerou shmeiou x einai:
B1 (x) = Nr1(x) (x) .
An to diktuo leitourgei seiriaka, ta parapanw prepei na isquoun gia opoiadhpote seira enhmerwshc twnneurwnwn.
Parathrhsh. Antistoiqa orizetai h aktina kai geitonia sugklishc-se-k-bhmata.Parathrhsh. H perioqh sugklishc-se-1-bhma tou x einai genika upersunolo thc geitoniac sugklishc-se-1-bhma.
Protash 12 H geitonia sugklishc-se-1-bhma enoc diktuou einai anexarthth apo to an h leitourgia toudiktuou einai parallhlh h́ seiriakh.
19
Orismoc 13 To sunaptiko dunamiko sumbolizetai me h (x) = [h1 (x) , ..., hN (x)]T kai orizetai wc exhc(gia n = 1, 2, ..., N):
hn (x) =N∑
m=1
wnmxm + un.
Protash 14 Estw oti ena diktuo eqei stajero shmeio x. Qwric blabh thc genikothtac, ac upojesoumeoti
|h1 (x)| ≤ |h2 (x)| ≤ ... ≤ |hN (x)| .
Orizoume tic posothtec
R1 =⌊
12|h1 (x)|
⌋, R2 =
⌊12|hR1+1 (x)|
⌋, R3 =
⌊12|hR2+1 (x)|
⌋, ...
H akoloujia R1, R2, ... termatizei se peperasmeno arijmo bhmatwn, estw K. Eqoume K ≤ bN/2c kai
R1 ≤ R2 ≤ ... ≤ RK .
An oi parapanw anisothtec isquoun austhra, tote Rk einai h aktina sugklishc se k bhmata tou x.
20
Qwrhtikothta
Poioc einai o megistoc arijmoc anaklhsimwn stajerwn shmeiwn pou mporei na eqei ena diktuo N neur-wnwn? Isquoun ta exhc.
Protash 15 Estw oti ta P protupa x(1), x(2), ..., x(P ) einai stajera shmeia tou diktuou (W,u). Anuparqei ρ ∈ [0, 1
2) tetoio wste
P < (1− 2ρ)2N
2 log N,
tote gia p = 1, ..., P eqoume
limN→∞
Pr(r1
(x(p)
)≥ ρN
)= 1.
Protash 16 Estw oti ta P protupa x(1), x(2), ..., x(P ) einai stajera shmeia tou diktuou (W,u). Anuparqei ρ ∈ [0, 1
2) tetoio wste
P < (1− 2ρ)2N
4 log N,
tote
limN→∞
Pr(
minp=1,...,P
[r1
(x(p)
)]≥ ρN
)= 1.
21
Parallagec tou Diktuou Hopfield
1. Suneqeic Katastaseic:
xn (t + 1) = g
(N∑
m=1
wnmxm (t) + un
)
opou (p.q.)
g (z) =ez/T − e−z/T
ez/T + e−z/T.
H sunarthsh g (z) einai h uperbolikh efaptomenh kai (gia diaforec timec tou T ) eqei thn morfh:
22
2. Suneqhc Qronoc:
dxn
dt= −xn (t) + g
(N∑
m=1
wnmxm (t) + un
).
Auth h diaforikh exiswsh eqei shmeia isorropiac tic luseic thc
0 = −xn + g
(N∑
m=1
wnmxm + un
).
23
3. Stoqastikoi Neurwnec:
xn (t + 1) ={
+1 me pijan. p−1 me pijan. q = 1− p
(6)
opou
p =ehn(x(t))/T
ehn(x(t))/T + e−hn(x(t))/T
q =e−hn(x(t))/T
ehn(x(t))/T + e−hn(x(t))/T
Parathroume oti
E (xn (t + 1) |x (t)) = (+1) · p + (−1) · q
=ehn(x(t))/T
ehn(x(t))/T + e−hn(x(t))/T− e−hn(x(t))/T
ehn(x(t))/T + e−hn(x(t))/T
=ehn(x(t))/T − e−hn(x(t))/T
ehn(x(t))/T + e−hn(x(t))/T.
Dhladh
E (xn (t + 1) |x (t)) = g
(N∑
m=1
wnmxm (t) + un
).
24
Beltistopoihsh
• Eqoume parathrhsei oti to diktuo Hopfield teinei se topiko elaqisto thc sunarthshc
E (x) = −12xT Wx + xTu.
• Ara mporoume na qrhsimopoihsoume to diktuo Hopfield gia na elaqistopoihsoume thn E (x) .
• PROSOQH: E : {−1, 1}N → R
• An eiqame E : R→ R ja mporousame na qrhsimopoihsoume allouc tropouc elaqistopoihshc.
• P.q. elaqistopoihsh megisthc klishc:
x(i+1) = x(i) − a · ∂E
∂x(7)
• Sthn pragmatikothta h (7), opwc kai kaje epanalhptikoc algorijmoc beltistopoihshc (gia sunarth-seic me suneqec pedio orismou), mporei na tejei se morfh PDP (Tsitsiklhc). Kai malista autoisquei oqi mono gia tetragwnikec, alla gia sunarthseic genikhc morfhc.
25
Sunduastikh Beltistopoihsh
• Edw eqoume mia tetragwnikh sunarthsh me pedio orismou to {−1,+1}N . Jumizei integer program-ming, 0/1 programming.
• Parathrhsh. Olh h prohgoumenh analush isquei kai otan eqoume pedio orismou to {0, 1}Nqrhsimopoiwntac ton metasqhmatismo
x← x + 12
.
• To shmantiko einai oti:
– Uparqoun tetragwnika 0/1 problhmata pou epiluontai apo diktuo Hopfield .
– Gia ta problhmata auta isquei h analush sugklishc (se topiko elaqisto).
– H analush sugklishc eqei ginei gia nteterministika diktua, eqei endiaferon na exetasoume seleptomereia thn sumperifora twn stoqastikwn diktuwn.
26
Problhma Weighted Matching
Weighted Matching: Dinontai N = 2M shmeia A1, A2, ..., AN ston qwro kai o pinakac apostasewnmetaxu duo opoiwndhpote zeugwn: Dmn = d (Am, An). Zhteitai na brejoun M zeugh shmeiwn (Ai1 , Aj1),..., (AiM , AjM ) (opou i1, j1, ...., iM , jM einai mia metajesh twn 1, 2, ..., N) tetoia wste to ajroisma
d (Ai1 , Aj1) + d (Ai2 , Aj2) + ... + d (AiM , AjM )
na ginetai elaqisto.Weighted Bipartite Matching: dinontai shmeia A1, A2, ..., AM kai B1, B2, ..., BM kai zhteitai nabrejoun M zeugh shmeiwn (Ai1 , Bj1), ..., (BiM , BjM ) (opou i1, ...., iM kai j1, ...., jM einai duo metajeseictwn 1, 2, ..., N) tetoia wste to ajroisma
d (Ai1 , Bj1) + d (Ai2 , Bj2) + ... + d (AiM , BjM )
na ginetai elaqisto.
27
Morfopoihsh tou problhmatoc Weighted Matching:Na brejei N ×N pinakac Q tetoioc wste
∀m,n : Qmn ∈ {0, 1}∀m,n : Qmn = Qnm
∀n :M∑
m=1
Qnm = 1
Elaqistopoieitai h J (Q) =∑n<m
QnmDnm.
Sunarthsh “Energeiac” gia to problhma Weighted Matching:
E (Q) =∑n<m
QnmDnm +γ
2
N∑n=1
(1−
M∑m=1
Qnm
)2
+δ
2
N∑n=1
M∑m=1
(Qmn −Qnm)2 .
H sunarthsh einai tetragwnikh!
28
Problhma Travelling Salesman
Dinontai N shmeia A1, A2, ..., AN ston qwro kai o pinakac apostasewn metaxu duo opoiwndhpotezeugwn: Dmn = d (Am, An). Zhteitai na brejei mia metajesh i1, i2, ...., iN twn 1, 2, ..., N , tetoia wstena elaqistopoieitai to ajroisma
Di1i2 + Di2i3 + ... + DiN−1iN + DiN i1 .
Sunarthsh “Energeiac” gia to problhma Travelling Salesman:
Qnk ={
1 an o komboc n einai o k -stoc komboc thc diadromhc,0 alliwc.
E (Q) =12
∑k,n,m
DnmQnk (Qm,k+1 + Qm,k−1) +γ
2
N∑n=1
(1−
N∑m=1
Qnm
)2
+γ
2
N∑m=1
(1−
N∑n=1
Qnm
)2
.
H sunarthsh einai tetragwnikh!
29
Sunduastikh Beltistopoihsh: Problhma Max-2-Sat
30
Grafoi
Orismoc 17 Enac grafoc G einai ena zeugoc G = (V,E) opou V = {1, 2, ..., N} einai oi korufec kaiE ⊆ V × V einai oi akmec.
Orismoc 18 H geitonia tou n ∈ V grafetai Vn kai orizetai
Vn = {m : (n, m) ∈ E}
Parathrhsh. m ∈ Vn ⇔ n ∈ Vm.Parathrhsh. Enac grafoc G prosdiorizetai isodunama apo tic korufec kai tic akmec tou (V,E) h apotic korufec kai tic geitoniec tou
(V, {Vn}n∈V
). An upojesoume oti kaje korufh eqei mh kenh geitonia,
tote o grafoc prosdiorizetai apo tic geitoniec V = {Vn}n∈V .
Orismoc 19 Mia klika tou G = (V,E) einai ena uposunolo U ⊆ V tetoio wste
n, m ∈ U ⇒ (n, m) ∈ E
h, isodunama∀n ∈ U : Vn = U − {n} .
Ja sumbolizoume to sunolo twn klikwn me C (V) h, pio apla, me C.
31
Markobiana Pedia
Estw enac grafoc V (me N korufec, dhl. V = {1, 2, ..., N}) kai ena sunolo Z = {z1, z2, ..., zL}. Sekaje korufh n ∈ {1, 2, ..., N} antistoiqizoume mia tuqaia metablhth Xn pou pairnei timec sto Z.
H dianusmatikh tuqaia metablhth X = [X1, ..., XN ]T prosdiorizetai plhrwc apo tic pijanothtec
p (x1, ..., xN ) = Pr (X1 = x1, X2 = x2, ..., XN = xN )
(gia kaje [x1, ..., xN ]T ∈ ZN ).
Orismoc 20 H tuqaia metablhth X legetai Markobiano Pedio wc proc ton grafo V, an isquoun taexhc:
1. Gia kaje [x1, ..., xN ]T ∈ ZN eqoume
Pr (X1 = x1, X2 = x2, ..., XN = xN ) > 0.
2. Gia kaje [x1, ..., xN ]T ∈ ZN kai gia kaje n ∈ V eqoume
Pr (Xn = xn|Xm = xm, m ∈ {1, 2, ..., n− 1, n + 1, ..., N}) = Pr (Xn = xn|Xm = xm kai m ∈ Vn) .
32
Katanomec Gibbs
Orismoc 21 Mia katanomh pijanothtac {p (x1, ..., xN )}[x1,...,xN ]T∈ZN legetai katanomh Gibbs wc procton grafo V an mporei na graftei sthn morfh
p (x1, ..., xN ) =1λ
exp(−E (x1, ..., xN )
T
)gia kaje [x1, ..., xN ]T ∈ ZN kai h E (x1, ..., xN ) eqei thn morfh
E (x1, ..., xN ) =∑C∈C
EC (x1, ..., xN )
opou, gia kaje C ∈ C, h EC (x1, ..., xN ) exartatai mono apo ta xn gia ta opoia n ∈ C. H E (x1, ..., xN )legetai sunarthsh energeiac.
Parathrhsh. To λ einai mia stajera kanonikopoihshc kai dinetai apo thn sqesh
λ =∑
[x1,...,xN ]T∈ZN
exp(−E (x1, ..., xN )
T
).
33
Protash 22 Estw enac grafoc V (me N korufec, dhl. V = {1, 2, ..., N}) kai h t.m. X = [X1, ..., XN ]T
me katanomh pijanothtac
Pr (X1 = x1, X2 = x2, ..., XN = xN ) = p (x1, ..., xN ) .
Ta parakatw einai isodunama
1. H X einai Markobiano Pedio wc proc to V.
2. H p einai katanomh Gibbs wc proc to V.
Protash 23 Estw oti h X eqei katanomh Gibbs wc proc ton V, me sunarthsh energeiac thn
E (x1, ..., xN ) =∑C∈C
EC (x1, ..., xN ) .
Tote, gia kaje n ∈ {1, 2, ..., N} kai [x1, ..., xn−1, x, xn+1, ..., xN ]T ∈ ZN eqoume
Pr (Xn = x|Xm = xm, m ∈ {1, 2, ..., n− 1, n + 1, ..., N})
=exp
(− 1
T
∑C:n∈C EC (x1, ..., xn−1, x, xn+1, ..., xN )
)∑z∈Z exp
(− 1
T
∑C:n∈C EC (x1, ..., xn−1, z, xn+1, ..., xN )
) .Paradeigma me diktuo Hopfield
34
O Algorijmoc Qalarwshc (Relaxation)
• Eisodoc:
– o grafoc V
– to sunolo Z = {z1, z2, ..., zL}– h sunarthsh energeiac E (x1, ..., xN ) =
∑C∈C EC (x1, ..., xN )
– h parametroc T .
• Epilegoume tuqaia thn arqikh katastash X (0) apo to ZN me omoiomorfh katanomh.
• Gia t = 1, 2, ...
– Epilegoume tuqaia to n apo to {1, 2, ..., N} me omoiomorfh katanomh.
– Epilegoume tuqaia to x apo to Z me katanomh Pr (Xn = x|Xm = xm (t− 1) , m 6= n).
– Jetoume Xn (t) = z kai Xm (t) = Xm (t− 1) (gia m 6= n).
• Epomeno t
Gia to diktuo Gibbs me stoqastikouc neurwnec kai Z = {−1,+1}, h epilogh tou x ginetai wc exhc:
x ={
+1 me pijan. p−1 me pijan. q = 1− p
opou
p =ehn(X(t))/T
ehn(X(t))/T + e−hn(X(t))/T
q =e−hn(X(t))/T
ehn(X(t))/T + e−hn(X(t))/T
dhladh einai akribwc o kanonac leitourgiac twn stoqastikwn neurwnwn (ex. (6) ).
35
Algorijmoc Qalarwshc: Sugklish
O algorijmoc qalarwshc Gibbs paragei mia stoqastikh (Markobianh) diadikasia X (t) gia thn opoiaisquei to exhc.
Protash 24 Gia kaje T > 0, gia kaje y,x ∈ ZN eqoume
limt→∞
Pr (X (t) = x|X (0) = y) = p (x)
opou p (x) einai h katanomh Gibbs pou antistoiqei sthn sunarthsh E (x).
36
Algorijmoc Anopthshc (Annealing) : Sugklish
Mporoume na tropopoihsoume ton algorijmo qalarwshc kai na qrhsimpopoihsoume mia qronometablhthparametro T (t). O tropopoihmenoc algorijmoc einai o algorijmoc anopthshc Gibbs . O algorijmocautoc paragei mia stoqastikh diadikasia X (t) gia thn opoia isquei to exhc.
Protash 25 An h sunarthsh T (t) ikanopoiei ta exhc
1. T (t) ↓ 0 otan t→∞.
2. Gia t = 1, 2, ... eqoume T (t) ≥ Nlog(t+1) · (maxx∈ZN [E (x)]−minx∈ZN [E (x)]) .
Tote, gia kaje y,x ∈ ZN eqoume
limt→∞
Pr (X (t) = x|X (0) = y) = p0 (x)
opou p0 (x) einai h katanomh pou isokatanemei olh thn pijanothta sta olika elaqista thc E (x), dhl.
p0 (x) ={
c otan E (x) = minx∈ZN E (x)0 alliwc.
.
37
Logikoc Sumperasmoc
aaaaaaaaaaaaaaaaaaaaaaaaaa
38