AdamátorZápiskyHlášky

Neuronové sítě (Hakl)

Zápisky z přednášek Ing. Františka Hakla, CSc.

Stránka, kde můžeme psát svoje připomínky k přednášce

Máme spoustu úloh, na jejichž řešení není známý žádný algoritmus, přestože je zvládnou řešit i celkem jednoduché biologické organismy, například rozpoznávání obrazu nebo autonomní pohyb. Neuronové sítě jsou pokus modelovat fungování těchto organismů.

Neuron uvažujeme jako funkci y:ℝn→⟨0,1⟩ skládající se z váhového vektoru w∈ℝn a nelineární aktivační funkce σ:ℝ→⟨0,1⟩, daná předpisem y(x)≔σ(w𝖳x).

Definice Nechť (x1,y1),…,(x1,ym) je posloupnost dvojic ℝn×{±1}. Potom aplikací delta pravidla dostaneme posloupnost {wi}1∞ danou rekurentním předpisem:
Věta Nechť posloupnost {wi}1∞ vznikla aplikací delta pravidla a existuje vektor w^,‖w^‖=1 splňující
∀i∈m^:sgnw^𝖳xi=yi.
Nechť dále
α≔maxi∈m^‖xi‖2,β≔mini∈m^(w^𝖳xi).
Potom existuje z∈ℕ takové, že wz+1=wz a platí
z≤αβ2+1.
Důkaz Nechť k je takové, že wk≠wk−1. Označme x~jp≔xjp⋅yjp.
wk=∑p=0k−1x~jp.
Platí w^𝖳x~io>0.
w^𝖳wk=∑p=0k−1w^𝖳x^jk≥(k−1)β>0.
(w^𝖳wk)2≥(k−1)2β2.
Podle Cauchy-Schwarzovy nerovnosti
‖w^‖2⋅‖wk‖2>|w^𝖳wk|2≥(k−1)2β2.
Současně
wk=wk−1+xjk−1,
‖wk‖2=‖wk−1‖2+2wk−1𝖳x~jk−1⏟≤0+‖xjk−1‖2≤‖wk−1‖2+‖x~jk−1‖2.
Steleskopením přes k dostáváme
‖wk‖2≤∑k=0k−1‖xjk−1‖2≤(k−1)α,
(k−1)2β2≤‖wk‖2≤(k−1)α.
Definice Nechť A,B⊂ℝn. Dvojice (w,t)∈ℝn×ℝ je lineární separátor množin A,B, pokud
∀a∈A:w𝖳a<t,∀b∈B:w𝖳b>t.
Lemma Nechť A⊂{±1}n,B≔{±1}n∖A a (w,t) je jejich lineární separátor. Potom existuje jejich lineární separátor (w*,t) takový, že
∀x,y∈{±1}n:x≠y⟹w*𝖳x≠w*𝖳y.
Důkaz Nebudeme si ukazovat, ale je v principu jednoduchý: pokud náhodou pro nějaké body budeme mít stejný skalární součin, stačí nadrovinu maličko posunout.
Věta Pro každé n∈ℕ existuje alespoň 2nn−12 podmnožin {±1}n, které se dají lineárně separovat od svého doplňku.
Důkaz Indukcí. Pro n=1 máme čtyři podmnožiny a všechny jsou separovat. Nyní předpokládejme, že věta platí pro n. Vezmeme lineární separátor (w*,t) z předchozí věty. Přímka při posouvání ve směru normály nikdy neprotne dva body najednou, takže posouváním můžeme vytvořit 2n+1 různých rozkladů. Nyní se přesuneme do (n+1)-rozměrného prostoru, kde se naše množina vrcholů krychle skládá ze dvou kopií vrcholů n-rozměrné krychle. Obě tyto podkrychle můžeme nezávisle na sobě rozdělit 2n−1 způsoby nadrovinou s normálou w*. Ty propojíme do jedné nadroviny, která v závislosti na obou posunutích může rozdělit vrcholy (n+1)-rozměrné krychle Kn+1≥Kn⋅(2n+1) způsoby, kde Kn je počet způsobů rozdělení původní krychle. Použitím indukčního předpokladu dostaneme, co chceme.
Věta Pro každé n∈ℕ existuje množina A⊂{±1}n taková, že pro každý její celočíselný separátor (w,t) platí
2n−22≤∑k=1n|wk|+|t|.
Důkaz Označme Pn množinu všech lineárně separabilních rozkladů (A,B) n-rozměrné krychle. Pro každé (A,B)∈Pn označme WA,B množinu celočíselných separátorů. Definujme
η(n)≔max(A,B)∈Pnmin(w,t)∈WA,B⌈log2(∑k=1n|wk|+t)⌉.
To znamená, že k zapsání každého separátoru stačí η(n)+1 bitů. Tedy různých celočíselných separátorů existuje nanejvýš 2(n+1)(η(n)+1). Zároveň podle předchozí věty je jich alespoň 2n(n−1)2. Tím dostáváme nerovnost
2(n+1)(η(n)+1)≥2n(n−1)2,
(n+1)(η(n)+1)≥n(n−1)2,
η(n)+1≥n(n−1)2(n+1)=n−22+1n+1>n−22,
což mělo být dokázáno.
Definice Nechť A={a1,…,ai},B={b1,…,bj}⊂ℝn. Potom Mangasarianův lineární problém je úloha lineárního programování ve tvaru nalezení y∈ℝi,z∈ℝj,w∈ℝn,t∈ℝ minimalizujících
∑α=1iyα+∑β=1jzβ
za podmínek
yα+w𝖳aα−t≥1,
zβ−w𝖳bβ+t≥1,
yα,zβ≥0.
Věta Nechť A={a1,…,ai},B={b1,…,bj}⊂ℝn. Potom
  1. množiny A,B jsou lineárně separovatelné, právě když optimální hodnota Mangasarianovy úlohy je 0,
  2. je-li optimální hodnota Mangasarianovy úlohy 0 a (y*,z*,w*,t*) je optimální řešení, potom (w*,t*) lineárně separuje A,B.
Důkaz Nestihl jsem si to opsat, protože ten ňouma maže tabuli rychleji než Šťovíček odchází z místnosti po skončení přednášky.
Definice Nechť (x0,y0),…,(xt,yt) jsou dvojice z ℝn×ℝ, t≥1, w0∈ℝn a η>0. Pro každé i∈ℕ označme τ(i)≔imodt. Posloupnost (wi) vznikla aplikací spojitého δ-pravidla, pokud
wk+1=wk+η⋅(yτ(k)−wk𝖳xτ(k))⋅xτ(k)=(𝐈−η⋅xτ(k)⋅xτ(k)𝖳)⋅wk+η⋅yτ(k)⋅xτ(k).
Poznámka V podstatě je to relaxační metoda pro speciální tvar matice.
Lemma Nechť B≔I−η⋅x⋅x𝖳,η>0,x∈ℝn. Potom B má vlastní číslo 1−η⋅‖x‖2 s vlastním vektorem x a vlastní číslo 1 s vlastním vektorem kolmým na x.
Lemma Nechť B≔I−η⋅x⋅x𝖳,x∈ℝn,0≤η≤2‖x‖2. Potom ‖B‖=ρ(B)=1.
Definice Nechť x1,…,xt∈ℝn. Označme Bp≔I−η⋅xp⋅xp𝖳. Potom pro každou permutaci π∈𝕊n definujeme
Λπ≔∏1i=tBπ(i),
h≔∑i=1tyπ(i)⋅(∏i+1j=tBπ(j))⋅xπ(i).
Lemma Nechť pro všechna p∈t^ platí 0≤η≤2‖xp‖2 a (x1,…,xt) je generátor ℝn. Potom pro každou permutaci π platí ‖Λπ‖<1.
Věta Nechť posloupnost (wn) vznikla z (x1,y1),…,(xt,yt) podle spojitého δ-pravidla, x1,…,xt generuje celý prostor ℝn a w* minimalizuje
E(w)≔∑p=1t(yp−w𝖳xp)2
a pro všechna p∈t^ platí 0≤η≤2‖xp‖2. Potom posloupnost (wi) konverguje ke konečnému cyklu délky t a každý vektor wi tohoto cyklu je jediný pevný bod kontrahujícího zobrazení Fi(w)≔Λπiw+ηhπi, kde πi≔(i+1,i+2,…,t,1,2,…,i). Navíc pokud w(η) je libovolný člen tohoto cyklu for pevné η>0, potom
‖w(η)−w*‖=ℴ(η),
‖E(w(η))−E(w*)‖=ℴ(η).
Definice Neuronová síť D je konečný souvislý orientovaný acyklický graf s množinou vrcholů I ohodnocených dvojicemi reálných čísel (yj,w0,j). Hrany jsou ohodnoceny reálnými čísly wi,j. Počty vstupních a výstupních hran pro daný vrchol značíme dj+,dj−. Je-li dj+=0, resp. dj−=0, jde o vstupní vrchol, resp. výstupní vrchol. Pro každý vrchol máme funkci Zj:ℝdj+×ℝdj++1→ℝ. Hodnotu každého nevstupního vrcholu spočteme jako yj≔Zj(sumj), kde
sumj≔∑i=1dj+wi,j⋅yi+w0,j.
Definice Pro každý vnitřní vrchol neuronové sítě označme
Sj≔∂Zj(sumj)∂sumj.
Cestu (i,j,j1,…,jk,v) označíme
ϑ(i,j,j1,…,jk,v).
Množinu všech takových cest z i do v začínajících hranou (i,j) označíme 𝒫i,wi,j,v.
Lemma metoda back-propagation Pro neuronovou síť D platí
∂yv∂wi,j=∑ϑ(i,wi,j,j1,…,jk,v)∈𝒫i,j,wyi⋅Sj⋅wj,j1⋅Sj1⋅wj1,j2⋅⋯⋅Sjk⋅wjk,v⋅Sv,
∂yv∂wj=∑ϑ(i,wi,j,j1,…,jk,v)∈𝒫i,j,wSj⋅wj,j1⋅Sj1⋅wj1,j2⋅⋯⋅Sjk⋅wjk,v⋅Sv,
Důkaz Vytvoříme pomocnou neuronovou síť D′, kde z D odebereme všechno, co není na cestě začínající hranou (i,j) a končící ve v. Potom stačí použít řetězové pravidlo.
Definice Mějme pro i∈p^ vzory (xi,di),xi∈ℝn,di∈ℝm. Nechť w=(w1,…,wK) je posloupnost vah a prahů dopředné neuronové sítě a yw,xi∈ℝm je odpovídající vektor hodnot výstupních uzlů. Potom chybová funkce je
E(w)≔∑i=1p∑j=1m((di)j−(ywi,xi)j)2≕∑i=1p∑j=1mei,j2.

Konvergence stochastických gradientních metod

Definice Konvexní ztrátová funkce je diferencovatelná funkce C:ℝn→ℝ, která má na ℝn jediné minimum w* a pro všechna ε>0 platí
inf(w−w*)2>ε{(w−w*)𝖳∇C(w)}>0.
Věta Nechť C je konvexní ztrátová funkce a funkce w splňuje diferenciální rovnici
w′(t)=−∇wC(w(t)).
Potom lim∞w=w*.
Důkaz Nechť h(t)≔(w(t)−w*)2. Potom
h′(t)=−2(w(t)−w*)⋅∇C(w(t))<0
Z toho vidíme, že h je kladná klesající funkce, takže existuje lim∞h≥0. Z toho také lim∞h′=0. Pro spor předpokládejme, že lim∞h=η>0. TBD
Lemma Nechť {ai} je nezáporná posloupnost. Označme
Vı+≔∑i=1t−1H(ai+1−ai),
kde H(x)≔[x>0]. Potom
limt→∞vt+<∞⟹limt→∞at<∞.
Důkaz Definujme analogicky
Vı−≔−∑i=1t−1H(ai−ai+1),
TBD
Lemma Nechť {gi},{βi} jsou kladné posloupnosti, ∑i=1∞βi<∞ a existují konstanty A,B∈ℝ+ splňující
gt+1−gt≤βt+1⋅(A+b⋅gt).
Potom limt→∞gt<∞.
Důkaz Definujeme pomocnou klesající posloupnost
μt≔∏i=1t11+βi⋅B.
Platí
−lnμt=∑i=1tln(1+βi⋅B)≤∑i=1tβi⋅B≤B⋅∑i=1∞βi=b⋅K.
Z toho
limt→∞μt≥exp−K>0.
Zároveň
μt+1⋅gt+1−μt⋅gt=(μt1+βt+1⋅B)⋅gt+1−μt⋅gt<μt⋅gt+1−μt⋅gt⋅(1+βk+1⋅B)=μt⋅(gt+1−gt−βt+1⋅B⋅gt)≤μt⋅βt+1⋅A.
Z toho
∑i=1∞μt⋅βt+1⋅A≤A⋅∑t=1∞βt+1<∞.
Jelikož μt⋅gt konverguje, musí i gt konvergovat.
Věta konvergence gradientní metody s konvexní ztrátovou funkcí Nechť C je konvexní ztrátová funkce a posloupnost {wt} je definována rekurencí
wi+1≔wt−γt⋅∇C(wt),
kde γi>0 pro všechna i a platí
∑i=1∞γi<∞,∑i=1∞γi=∞.
Nechť dále A,B jsou konstanty takové, že pro všechny w∈ℝn je
(∇C(w))2≤A+B⋅(w−w*)2.
Potom limt→∞wt=w*.
Lemma Nechť C je zobecněná konvexní funkce, Γ≔max{1,D}, {wi} je stochastická gradientní posloupnost pro C a pro k∈{2,3,4} existují Ak,Bk>0 taková, že pro všechna w∈ℝn je
𝔼z[‖H(zt,wt)‖k|𝒵t≤Ak+Bk⋅‖wi‖k].
Potom pro všechna t od nějakého t0 je ‖wt‖<Γ s pravděpodobností 1.
Důkaz náznak
ft+1=ψ(wt+1)
Schwarzova nerovnost
𝔼(ft+1−ft)=−2γtwtH(zt,wt)ψ−1(wt2)+γ2‖H‖2ψ−1(wt2)+4γt2‖wt‖2‖H‖2++4γt3‖wt‖‖h‖3+γt4‖H‖4