Gradientný zostup: ako sa model učí

Nech d ∈ ℕ, d ≥ 1, a J : ℝ^d → ℝ je diferencovateľná stratová funkcia s gradientom ∇J : ℝ^d → ℝ^d, ∇J(θ) = (∂J/∂θ₁(θ), …, ∂J/∂θ_d(θ)) (pozri diel o deriváciách a gradiente).

Gradientný zostup je algoritmus:

• vstup: počiatočné parametre θ₀ ∈ ℝ^d, rýchlosť učenia η ∈ ℝ, η > 0, tolerancia ε > 0 a najväčší počet krokov T ∈ ℕ;
• výstup: parametre θ_t ∈ ℝ^d v okamihu zastavenia.

1. Polož t = 0.
2. Ak ‖∇J(θ_t)‖ < ε alebo t = T, zastav a vráť θ_t.
3. Polož θ_t+1 = θ_t − η ∇J(θ_t), zväčši t o 1 a pokračuj krokom 2.

Algoritmus teda opakovane posúva parametre o η-násobok gradientu proti jeho smeru, kým nie je gradient takmer nulový alebo kým sa neminú kroky.

Nech G = (U, H) je orientovaný acyklický graf s konečnou množinou uzlov U a množinou hrán H ⊆ U × U; hranu (u, v) ∈ H píšeme u → v. Pre v ∈ U označme rod(v) = {u ∈ U : u → v} množinu jeho rodičov. G je výpočtový graf práve vtedy, keď

1. každý uzol v nesie reálnu hodnotu, ktorú označujeme rovnakým písmenom v;
2. uzly s rod(v) = ∅ sú vstupy (dáta a parametre) a ich hodnoty sú dané;
3. každý uzol v s rod(v) ≠ ∅ má diferencovateľnú funkciu f_v a jeho hodnota je v = f_v((u)_{u ∈ rod(v)});
4. jeden vyznačený uzol L ∈ U je strata.

Topologické poradie je očíslovanie U = {v₁, …, v_N} také, že v_i → v_j ⇒ i < j (v acyklickom grafe vždy existuje).

Dopredný prechod vypočíta hodnoty v₁, …, v_N v tomto poradí podľa bodu 3 — každý uzol až po všetkých svojich rodičoch.

Spätný prechod vypočíta pre každý uzol u ∈ U jeho adjungovanú hodnotu ū = ∂L/∂u v obrátenom poradí v_N, …, v₁: položí L̄ = 1 a pre u ≠ L použije viacrozmerné reťazové pravidlo

ū = ∑_{v : u → v} v̄ · ∂f_v/∂u

(prázdny súčet je 0). Spätný prechod teda pre každý uzol sčíta príspevky zo všetkých uzlov, do ktorých u vstupuje; každá hrana sa pritom použije práve raz.

Všetky veličiny sú reálne čísla: p₁, p₂, b, w, x, z ∈ ℝ, cieľ t ∈ {0, 1} a výstup ŷ ∈ (0, 1).

Súčet z = p₁ + p₂ + b: ∂z/∂p₁ = ∂z/∂p₂ = ∂z/∂b = 1 — súčet pošle gradient do všetkých vstupov bez zmeny.

Súčin p = wx: ∂p/∂w = x a ∂p/∂x = w — gradient sa vynásobí druhým činiteľom.

Logistická funkcia σ : ℝ → (0, 1), σ(z) = 1/1 + e^−z: σ′(z) = e^−z/(1 + e^−z)² = σ(z)(1 − σ(z)) = ŷ(1 − ŷ), kde ŷ = σ(z).

Krížová entropia L = −t ln ŷ − (1 − t) ln(1 − ŷ): ∂L/∂ŷ = −t/ŷ + 1 − t/1 − ŷ.

Nech t ∈ {0, 1}, z ∈ ℝ, ŷ = σ(z) je logistická funkcia a L = −t ln ŷ − (1 − t) ln(1 − ŷ) krížová entropia. Potom

∂L/∂z = ŷ − t.

Dôkaz. Reťazové pravidlo cez ŷ: ∂L/∂z = ∂L/∂ŷ · ∂ŷ/∂z = (−t/ŷ + 1 − t/1 − ŷ) · ŷ(1 − ŷ) = −t(1 − ŷ) + (1 − t)ŷ = ŷ − t. ∎

Na obrázku: ∂L/∂z = 0,500 − 1 = −0,500. Delenie ŷ a násobenie ŷ(1 − ŷ) sa navzájom skrátia — preto sa krížová entropia páruje s logistickou funkciou (a ako uvidíte, aj so softmaxom).

Nech G = (U, H) je výpočtový graf s E = |H| hranami, v ktorom každý uzol ovplyvňuje stratu (z každého uzla vedie cesta do L), a nech každú hodnotu f_v aj každú lokálnu deriváciu ∂f_v/∂u možno vypočítať v konštantnom čase. Potom spätný prechod vypočíta všetky adjungované hodnoty ū, u ∈ U — medzi nimi všetky derivácie ∂L/∂θ_i podľa parametrov — v čase O(E), teda v rovnakom ráde ako dopredný prechod a nezávisle od počtu parametrov.

Dôkaz. Vo vzorci pre ū sa každá hrana u → v objaví v súčte práve raz, súčty dohromady teda majú E členov. Každý uzol okrem L má aspoň jednu odchádzajúcu hranu, takže |U| ≤ E + 1 a aj práca na jednotlivých uzloch je O(E). ∎

Numerická derivácia L(θ + he_i) − L(θ − he_i)/2h (e_i je i-tý jednotkový vektor, h > 0 malé číslo) by potrebovala dva dopredné prechody na každý parameter — pri sieti s miliardou parametrov dve miliardy prechodov namiesto jedného spätného.

Pre m ∈ ℕ, m ≥ 1, je softmax funkcia softmax : ℝ^m → (0, 1)^m daná po zložkách (pozri diel o softmaxe)

softmax(z)_i = e^z_i/∑_k=1^m e^z_k,   i = 1, …, m.

Nech n ∈ ℕ, n ≥ 1, je počet vrstiev, d₀, d₁, …, d_n ≥ 1 sú šírky vrstiev, x ∈ ℝ^d₀ je vstup a pre ℓ = 1, …, n sú W^(ℓ) ∈ ℝ^{d_ℓ×d_ℓ−1} váhy a b^(ℓ) ∈ ℝ^d_ℓ biasy vrstvy ℓ. Sieť so softmaxom vo všetkých vrstvách počíta a⁽⁰⁾ = x a pre ℓ = 1, …, n

z^(ℓ) = W^(ℓ)a^(ℓ−1) + b^(ℓ) ∈ ℝ^d_ℓ,   a^(ℓ) = softmax(z^(ℓ)) ∈ (0, 1)^d_ℓ,

po zložkách z_i^(ℓ) = ∑_j=1^d_ℓ−1 W_ij^(ℓ)a_j^(ℓ−1) + b_i^(ℓ) pre i = 1, …, d_ℓ (súčtová bázová funkcia).

Cieľ je vektor t ∈ {0, 1}^d_n s ∑_k t_k = 1 (jediná jednotka na pozícii správnej triedy) a strata je krížová entropia

L = −∑_k=1^d_n t_k ln a_k⁽ⁿ⁾.

Chyba vrstvy ℓ ∈ {1, …, n} je vektor

δ^(ℓ) = ∂L/∂z^(ℓ) ∈ ℝ^d_ℓ,   t. j. δ_i^(ℓ) = ∂L/∂z_i^(ℓ).

Chyba vrstvy teda hovorí, ako strata závisí od vstupu aktivácie; z nej sa potom dajú prečítať gradienty váh aj biasov.

Nech m ∈ ℕ, m ≥ 1, z ∈ ℝ^m a a = softmax(z). Pre i, j ∈ {1, …, m} označme δ_ij Kroneckerovo delta (δ_ij = 1 pre i = j, inak 0). Potom pre všetky i, j ∈ {1, …, m}

∂a_i/∂z_j = a_i(δ_ij − a_j),

maticovo

J = ∂a/∂z = diag(a) − aa^T ∈ ℝ^m×m.

Dôkaz. Označme S = ∑_k=1^m e^z_k, takže ∂S/∂z_j = e^z_j. Podľa pravidla pre podiel

pre i = j: ∂a_i/∂z_i = e^z_iS − e^z_ie^z_i/S² = a_i − a_i²,

pre i ≠ j: ∂a_i/∂z_j = −e^z_ie^z_j/S² = −a_ia_j. ∎

Dve vlastnosti budeme potrebovať: J je symetrická a každý jej riadok (aj stĺpec) má súčet nula, pretože ∑_j a_i(δ_ij − a_j) = a_i − a_i∑_ja_j = 0.

Nech sieť, cieľ t a strata L sú ako v definícii vyššie. Potom

δ⁽ⁿ⁾ = a⁽ⁿ⁾ − t.

Dôkaz. Píšeme a = a⁽ⁿ⁾, z = z⁽ⁿ⁾. Strata závisí od a ako ∂L/∂a_i = −t_i/a_i. Každé z_j ovplyvní všetky a_i, takže sa sčítava cez i a použije sa lema 1:

δ_j⁽ⁿ⁾ = ∑_i ∂L/∂a_i · ∂a_i/∂z_j = ∑_i (−t_i/a_i) · a_i(δ_ij − a_j) = −t_j + a_j ∑_i t_i = a_j − t_j,

pretože ∑_i t_i = 1. ∎

Je to rovnaký tvar ako ŷ − t pri jednom neuróne: logaritmus v strate zruší exponenciálu v softmaxe a z celej Jacobiho matice zostane rozdiel „čo sieť povedala“ mínus „čo mala povedať“.

Nech n ≥ 2, sieť, cieľ a strata sú ako v definícii vyššie a J⁽ⁿ⁻¹⁾ = diag(a⁽ⁿ⁻¹⁾) − a⁽ⁿ⁻¹⁾(a⁽ⁿ⁻¹⁾)^T je Jacobiho matica softmaxu vrstvy n − 1 (lema 1). Označme g⁽ⁿ⁻¹⁾ = ∂L/∂a⁽ⁿ⁻¹⁾ ∈ ℝ^d_n−1. Potom

1. g⁽ⁿ⁻¹⁾ = (W⁽ⁿ⁾)^T δ⁽ⁿ⁾,   po zložkách g_j = ∑_i W_ij⁽ⁿ⁾ δ_i⁽ⁿ⁾;
2. δ⁽ⁿ⁻¹⁾ = J⁽ⁿ⁻¹⁾ g⁽ⁿ⁻¹⁾,   po zložkách δ_j⁽ⁿ⁻¹⁾ = a_j (g_j − a·g),

kde a = a⁽ⁿ⁻¹⁾, g = g⁽ⁿ⁻¹⁾ a a·g = ∑_i a_ig_i je priemer g vážený aktiváciami vrstvy (váhy a_i sú kladné a dávajú súčet 1).

Dôkaz. Najprv gradient podľa výstupov vrstvy n − 1. Keďže z_i⁽ⁿ⁾ = ∑_j W_ij⁽ⁿ⁾a_j⁽ⁿ⁻¹⁾ + b_i⁽ⁿ⁾, je ∂z_i⁽ⁿ⁾/∂a_j⁽ⁿ⁻¹⁾ = W_ij⁽ⁿ⁾ a podľa reťazového pravidla g_j = ∑_i ∂L/∂z_i⁽ⁿ⁾ · W_ij⁽ⁿ⁾ = ∑_i W_ij⁽ⁿ⁾ δ_i⁽ⁿ⁾, čo je bod 1.

Chyba sa teda vracia po tých istých váhach, ktorými signál šiel dopredu, len v opačnom smere — odtiaľ transpozícia. Potom prejde späť softmaxom vrstvy n − 1; podľa lemy 1 a vďaka symetrii J:

δ_j⁽ⁿ⁻¹⁾ = ∑_i g_i ∂a_i/∂z_j = ∑_i a_i(δ_ij − a_j)g_i = a_jg_j − a_j ∑_i a_ig_i = a_j (g_j − a·g),

čo je bod 2. ∎

Výklad: neurón dostane chybu úmernú tomu, o koľko je „jeho“ gradient g_j nad váženým priemerom celej vrstvy, a navyše vynásobenú svojou aktiváciou. Softmax nerozlišuje absolútnu úroveň, len pomery — preto sa odčítava priemer.

Nech sieť, cieľ a strata sú ako v definícii vyššie, J^(ℓ) je Jacobiho matica softmaxu vrstvy ℓ (lema 1), ⊙ označuje násobenie po zložkách a 1 vektor jednotiek. Potom

1. (rekurzia) pre ℓ = n − 1, n − 2, …, 1 platí g^(ℓ) = (W^(ℓ+1))^T δ^(ℓ+1),   δ^(ℓ) = J^(ℓ)g^(ℓ) = a^(ℓ) ⊙ (g^(ℓ) − (a^(ℓ)·g^(ℓ)) 1), kde g^(ℓ) = ∂L/∂a^(ℓ);
2. (gradienty parametrov) pre ℓ = 1, …, n, i = 1, …, d_ℓ a j = 1, …, d_ℓ−1 platí ∂L/∂W_ij^(ℓ) = δ_i^(ℓ) a_j^(ℓ−1),   t. j. ∂L/∂W^(ℓ) = δ^(ℓ)(a^(ℓ−1))^T,   ∂L/∂b^(ℓ) = δ^(ℓ).

Dôkaz. (1) Úvaha z vety 3 nikde nevyužila, že vrstva n je posledná — len to, že z^(ℓ+1) závisí od a^(ℓ) lineárne s maticou W^(ℓ+1) a že a^(ℓ) = softmax(z^(ℓ)). Rozpísané cez všetky vrstvy:

δ^(ℓ) = J^(ℓ)(W^(ℓ+1))^T J^(ℓ+1)(W^(ℓ+2))^T ⋯ J⁽ⁿ⁻¹⁾(W⁽ⁿ⁾)^T (a⁽ⁿ⁾ − t).

(2) Váha W_ij^(ℓ) ovplyvní len z_i^(ℓ), a to s deriváciou ∂z_i^(ℓ)/∂W_ij^(ℓ) = a_j^(ℓ−1); bias b_i^(ℓ) s deriváciou 1. Reťazové pravidlo dá ∂L/∂W_ij^(ℓ) = δ_i^(ℓ) · a_j^(ℓ−1) a ∂L/∂b_i^(ℓ) = δ_i^(ℓ). ∎

Gradient váhy je teda „chyba neurónu, do ktorého váha vedie, krát aktivita neurónu, z ktorého vedie“. Váha z neaktívneho neurónu sa neučí.

Nech sieť, cieľ a strata sú ako v definícii vyššie. Potom pre každú vrstvu ℓ ∈ {1, …, n} platí

∑_j=1^d_ℓ δ_j^(ℓ) = 0,   a teda aj   ∑_j=1^d_ℓ ∂L/∂b_j^(ℓ) = 0.

Dôkaz. Pre ℓ = n: ∑(a_j − t_j) = 1 − 1 = 0. Pre skryté vrstvy: 1^Tδ^(ℓ) = 1^TJ^(ℓ)g^(ℓ) = 0, pretože stĺpce J majú súčet nula (lema 1). ∎

Dôvod je hlbší: softmax sa nezmení, keď ku všetkým z_i vo vrstve pripočítate rovnaké číslo. V smere (1, 1, …, 1) je teda strata plochá a gradient doň nemôže ukazovať.

Nech m ≥ 1, a ∈ (0, 1)^m s ∑_i a_i = 1 (výstup softmaxu) a J = diag(a) − aa^T. Potom všetky vlastné čísla J ležia v intervale [0, 1/2], a preto pre každé g ∈ ℝ^m platí

‖Jg‖ ≤ 1/2 ‖g‖.

Dôkaz. J je symetrická, takže má reálne vlastné čísla. Riadok i má na diagonále a_i(1 − a_i) a mimo nej čísla −a_ia_j, ktorých absolútne hodnoty dajú dohromady a_i(1 − a_i). Podľa Geršgorinovej vety leží každé vlastné číslo v niektorom intervale [0, 2a_i(1 − a_i)] a 2a(1 − a) ≤ 1/2 pre každé a ∈ ℝ. Pre symetrickú maticu je ‖Jg‖ ≤ max |λ| · ‖g‖, kde maximum je cez vlastné čísla λ. ∎

Každá softmaxová vrstva teda chybu cestou späť aspoň zmenší na polovicu (ak ju váhy nezosilnia). To je jeden z dôvodov, prečo sa softmax do skrytých vrstiev nedáva: v hlbokej sieti by gradient k prvým vrstvám takmer nedošiel. Uvidíte to aj v príklade.

Nech J : ℝ → ℝ, J(x) = x², štart x₀ ∈ ℝ, x₀ ≠ 0, rýchlosť učenia η > 0 a x_t+1 = x_t − ηJ′(x_t) pre t = 0, 1, 2, … Potom

1. x_t = (1 − 2η)^t x₀ pre všetky t ∈ ℕ₀;
2. x_t → 0 (zostup konverguje do minima) práve vtedy, keď |1 − 2η| < 1, t. j. práve vtedy, keď η < 1;
3. pre η = 0,5 je x₁ = 0 — zostup skončí v minime jediným krokom.

Dôkaz. Jeden krok je x_t+1 = x_t − η · 2x_t = (1 − 2η)x_t; indukciou dostaneme mocninu. Postupnosť q^t ide k nule práve pre |q| < 1. ∎

(1) Nech a > 0, J : ℝ → ℝ, J(x) = ax²/2 (druhá derivácia je a), η > 0 a x₀ ≠ 0. Potom krok zostupu je x ← (1 − ηa)x a zostup konverguje do minima 0 práve vtedy, keď

0 < η < 2/a.

Parabola x² má a = 2, odtiaľ hranica 1.

(2) Všeobecne: nech J : ℝ^d → ℝ je diferencovateľná a jej gradient má Lipschitzovu konštantu L > 0, t. j. ‖∇J(u) − ∇J(v)‖ ≤ L‖u − v‖ pre všetky u, v ∈ ℝ^d (zakrivenie nikde neprekročí L), a nech 0 < η ≤ 1/L. Potom J(θ_t+1) ≤ J(θ_t) pre každé t — strata v žiadnom kroku nevzrastie (štandardný výsledok, pozri napr. Nesterov: Introductory Lectures on Convex Optimization, 2004, odd. 1.2.3). Rýchlosť učenia sa teda musí riadiť najstrmším zakrivením krajiny.

Nech d ≥ 1 a A ∈ ℝ^d×d je symetrická pozitívne definitná matica; jej vlastné čísla sú reálne a kladné, označme λ_min > 0 najmenšie a λ_max najväčšie z nich. Číslo podmienenosti matice A je

κ = λ_max/λ_min ≥ 1,

pomer najväčšieho a najmenšieho vlastného čísla. Pre kvadratickú stratu J : ℝ^d → ℝ, J(θ) = 1/2 θ^TAθ, sú vlastné čísla A zakrivenia v hlavných smeroch a číslo podmienenosti straty je číslo podmienenosti A. Naše údolie má A = diag(1, 20), teda κ = 20.

Pre túto stratu platí (štandardný výsledok): gradientný zostup s rýchlosťou učenia η konverguje z každého štartu práve vtedy, keď 0 < η < 2/λ_max. Aj s najlepšou pevnou voľbou η = 2/λ_min + λ_max platí len ‖θ_t+1‖ ≤ κ − 1/κ + 1 ‖θ_t‖ (minimum je v θ = 0) — u nás 19/21 ≈ 0,905. Čím väčšie κ, tým bližšie je tento koeficient k 1 a tým pomalší zostup.

Nech J : ℝ^d → ℝ je diferencovateľná stratová funkcia, θ₀ ∈ ℝ^d počiatočné parametre, η > 0 rýchlosť učenia a β ∈ [0, 1) koeficient momentu. Zostup s momentom položí v₀ = 0 ∈ ℝ^d a pre t = 0, 1, 2, … počíta

v_t+1 = β v_t − η ∇J(θ_t),   θ_t+1 = θ_t + v_t+1;

zastaví sa rovnako ako gradientný zostup (malý gradient alebo vyčerpaný počet krokov). Vektor v_t ∈ ℝ^d je „rýchlosť“ a β hovorí, koľko z nej zostane do ďalšieho kroku (typicky 0,9; v našom údolí najlepšie 0,6). Pre β = 0 ide o obyčajný gradientný zostup.

Nech η > 0, β ∈ [0, 1), g ∈ ℝ^d a gradient je počas zostupu stále rovnaký, ∇J(θ_t) = g pre všetky t (rovný svah), a v₀ = 0. Potom pre každé t ≥ 1

v_t = −ηg(1 + β + … + β^t−1) = −ηg 1 − β^t/1 − β   a   v_t → −η/1 − β g   pre t → ∞.

Dôkaz. Indukciou z v_t+1 = βv_t − ηg; súčet geometrického radu, a β^t → 0, pretože 0 ≤ β < 1. ∎

Na rovnom svahu sa teda krok ustáli na η/1 − β-násobku gradientu: pre β = 0,6 je to 2,5-krát dlhší krok, pre obvyklé β = 0,9 desaťkrát. Keď sa znamienko gradientu strieda, súčet radu sa naopak takmer vyruší.

V smere x sa krok predĺžil z 0,4 na 0,6 (gradient má stále rovnaké znamienko), v smere y sa rýchlosť −2,4 a nový ťah +2,4 takmer vyrušili a guľa je pri dne údolia (y = −0,24). Obyčajný zostup je po dvoch krokoch len v (−3,31; 0,77).

Nech J : ℝ^d → ℝ je diferencovateľná stratová funkcia. Adam je algoritmus:

• vstup: počiatočné parametre θ₀ ∈ ℝ^d, rýchlosť učenia η > 0, koeficienty β₁, β₂ ∈ [0, 1), malé číslo ε > 0 a počet krokov T ∈ ℕ;
• výstup: parametre θ_T ∈ ℝ^d.

Polož m₀ = s₀ = 0 ∈ ℝ^d a pre t = 1, 2, …, T vykonaj (všetky operácie s vektormi — štvorec, odmocnina, delenie — sú po zložkách):

1. g_t = ∇J(θ_t−1);
2. m_t = β₁m_t−1 + (1 − β₁)g_t (priemer gradientov);
3. s_t = β₂s_t−1 + (1 − β₂)g_t² (priemer štvorcov gradientov);
4. m̂_t = m_t/1 − β₁^t,   ŝ_t = s_t/1 − β₂^t (oprava počiatočného skreslenia, pozri ďalšiu definíciu);
5. θ_t = θ_t−1 − η m̂_t/√ŝ_t + ε.

Obvyklé hodnoty: β₁ = 0,9, β₂ = 0,999, ε = 10⁻⁸. Adam teda robí krok v smere priemerného gradientu, v každej zložke vydelený typickou veľkosťou gradientu v tej zložke.

Nech g₁, g₂, … je postupnosť reálnych čísel (alebo vektorov z ℝ^d) a β ∈ [0, 1). Exponenciálny kĺzavý priemer tejto postupnosti je postupnosť (m_t)_{t ≥ 0} daná rekurziou

m₀ = 0,   m_t = βm_t−1 + (1 − β)g_t   pre t ≥ 1,

rozpísané m_t = (1 − β) ∑_k=1^t β^t−kg_k. Pre t ≥ 1 a β > 0 je jeho oprava o počiatočné skreslenie

m̂_t = m_t/1 − β^t.

Váhy (1 − β)β^t−k, k = 1, …, t, dajú dohromady len 1 − β^t, nie 1 — chýbajúca časť pripadá na počiatočnú nulu. Preto je m_t na začiatku skreslený k nule a oprava z neho robí skutočný vážený priemer (váhy po oprave dávajú súčet 1; pri stálom g_k = g je presne m̂_t = g).

Gradient v smere y je šesťkrát väčší než v smere x, a predsa sa oba parametre posunuli o rovnakých 0,5. Obyčajný zostup by sa v smere y posunul šesťkrát ďalej než v smere x.

Nech n ≥ 1 je počet príkladov v dátach, L₁, …, L_n : ℝ^d → ℝ sú diferencovateľné straty jednotlivých príkladov a celková strata je ich priemer

J(θ) = 1/n ∑_i=1ⁿ L_i(θ).

Stochastický gradientný zostup je gradientný zostup (so vstupmi θ₀, η a počtom krokov ako vyššie), v ktorom sa v každom kroku t namiesto ∇J(θ_t) použije odhad

g_t = 1/|B_t| ∑_{i ∈ Bt} ∇L_i(θ_t),   θ_t+1 = θ_t − ηg_t,

kde dávka B_t ⊆ {1, …, n} je v každom kroku znova náhodne vybraná neprázdna množina indexov (typicky pevnej veľkosti |B_t| ≪ n). Epocha je úsek krokov, počas ktorého sa každý z n príkladov použije práve raz (pri zamiešaní dát a prechádzaní po dávkach veľkosti b je to n/b krokov, ak je n deliteľné b).

Nech J = 1/n ∑_i=1ⁿ L_i je ako v definícii SGD, θ ∈ ℝ^d pevné a b ≥ 1. Nech I₁, …, I_b sú nezávislé náhodné indexy, každý s rovnomerným rozdelením na {1, …, n} (výber s vrátením), a

g = 1/b ∑_k=1^b ∇L_Ik(θ).

Potom

1. E[g] = ∇J(θ) — odhad je nestranný;
2. pre každú zložku j = 1, …, d je var(g_j) = 1/b var(∂L_I1/∂θ_j(θ)), takže smerodajná odchýlka (typická chyba) odhadu klesá ako 1/√b.

Dôkaz. (1) Pre jeden náhodný index I je E[∇L_I(θ)] = ∑_i=1ⁿ 1/n ∇L_i(θ) = ∇J(θ); priemer b takých odhadov má rovnakú strednú hodnotu. (2) Rozptyl priemeru b nezávislých rovnako rozdelených veličín je rozptyl jednej vydelený b. ∎

V praxi (aj v našom programe) sa dáta namiesto nezávislého výberu zamiešajú a berú postupne po dávkach — každý príklad sa v epoche použije práve raz. Na tvare záveru to takmer nič nemení.

Nech n ≥ 1 a (x_i, y_i) ∈ ℝ², i = 1, …, n, sú dáta. Pre parametre (a, b) ∈ ℝ² priamky ŷ = ax + b je stredná kvadratická chyba funkcia J : ℝ² → ℝ,

J(a, b) = 1/n ∑_i=1ⁿ (ax_i + b − y_i)².

Označme e_i = ax_i + b − y_i chybu na i-tom príklade. Potom (derivácia zloženej funkcie)

∂J/∂a = 2/n ∑_i=1ⁿ e_ix_i,   ∂J/∂b = 2/n ∑_i=1ⁿ e_i.

SGD počíta tie isté súčty, len cez dávku B a s 2/|B| namiesto 2/n.

Nech J : ℝ^d → ℝ a θ* ∈ ℝ^d.

1. θ* je globálne minimum J práve vtedy, keď ∀θ ∈ ℝ^d : J(θ*) ≤ J(θ).
2. θ* je lokálne minimum J práve vtedy, keď ∃r > 0 ∀θ ∈ ℝ^d : ‖θ − θ*‖ < r ⇒ J(θ*) ≤ J(θ). Lokálne maximum je definované rovnako s ≥ namiesto ≤.
3. Ak je J diferencovateľná, je θ* stacionárny bod práve vtedy, keď ∇J(θ*) = 0.
4. θ* je sedlo práve vtedy, keď je stacionárny bod a nie je lokálne minimum ani lokálne maximum.

V stacionárnom bode sa gradientný zostup zastaví, nech je to čokoľvek. Ak je J dvakrát spojito diferencovateľná, rozlíši typ stacionárneho bodu Hessova matica H ∈ ℝ^d×d, H_ij = ∂²J/∂θ_i ∂θ_j(θ*): ak má všetky vlastné čísla kladné, je θ* lokálne minimum; všetky záporné — lokálne maximum; kladné aj záporné — sedlo. Ak je niektoré vlastné číslo nulové a ostatné rovnakého znamienka, test nerozhodne.

Maximum pri 0,17 je „hrebeň“ medzi oboma údoliami: loptička, ktorá štartuje vpravo od neho, sa skotúľa do lokálneho minima, vľavo do globálneho. Sedlo v jednej premennej nevznikne — potrebuje aspoň dva smery. Najjednoduchšie je J(x, y) = x² − y²: v počiatku je ∇J = (2x, −2y) = 0 a H = diag(2, −2) má vlastné čísla oboch znamienok.

Definícia. Nech J : ℝ^d → ℝ. Funkcia J je konvexná práve vtedy, keď

∀u, v ∈ ℝ^d ∀λ ∈ [0, 1] : J(λu + (1 − λ)v) ≤ λJ(u) + (1 − λ)J(v)

— úsečka medzi dvoma bodmi grafu nikde neleží pod grafom.

Veta. Nech J : ℝ^d → ℝ je konvexná a θ* ∈ ℝ^d je lokálne minimum J. Potom θ* je globálne minimum J.

Dôkaz. Predpokladajme pre spor, že existuje u ∈ ℝ^d s J(u) < J(θ*). Pre body θ_λ = λu + (1 − λ)θ* platí J(θ_λ) ≤ λJ(u) + (1 − λ)J(θ*) < J(θ*) pre každé λ ∈ (0, 1]. Pre malé λ leží θ_λ ľubovoľne blízko θ* — to je spor s lokálnou minimalitou. ∎

Parabola aj údolie z predchádzajúcich oddielov sú konvexné, strata neurónovej siete s nelineárnymi aktiváciami vo všeobecnosti nie — preto pri sieťach záleží na štarte.