Gradientní sestup: jak se model učí

Nechť d ∈ ℕ, d ≥ 1, a J : ℝ^d → ℝ je diferencovatelná ztrátová funkce s gradientem ∇J : ℝ^d → ℝ^d, ∇J(θ) = (∂J/∂θ₁(θ), …, ∂J/∂θ_d(θ)) (viz díl o derivaci a gradientu).

Gradientní sestup je algoritmus:

• vstup: počáteční parametry θ₀ ∈ ℝ^d, rychlost učení η ∈ ℝ, η > 0, tolerance ε > 0 a největší počet kroků T ∈ ℕ;
• výstup: parametry θ_t ∈ ℝ^d v okamžiku zastavení.

1. Polož t = 0.
2. Je-li ‖∇J(θ_t)‖ < ε nebo t = T, zastav a vrať θ_t.
3. Polož θ_t+1 = θ_t − η ∇J(θ_t), zvětši t o 1 a pokračuj krokem 2.

Algoritmus tedy opakovaně posouvá parametry o η-násobek gradientu proti jeho směru, dokud není gradient skoro nulový nebo nedojdou kroky.

Nechť G = (U, H) je orientovaný acyklický graf s konečnou množinou uzlů U a množinou hran H ⊆ U × U; hranu (u, v) ∈ H píšeme u → v. Pro v ∈ U označme rod(v) = {u ∈ U : u → v} množinu jeho rodičů. G je výpočetní graf, právě když

1. každý uzel v nese reálnou hodnotu, kterou značíme stejným písmenem v;
2. uzly s rod(v) = ∅ jsou vstupy (data a parametry) a jejich hodnoty jsou dané;
3. každý uzel v s rod(v) ≠ ∅ má diferencovatelnou funkci f_v a jeho hodnota je v = f_v((u)_{u ∈ rod(v)});
4. jeden vyznačený uzel L ∈ U je ztráta.

Topologické pořadí je očíslování U = {v₁, …, v_N} takové, že v_i → v_j ⇒ i < j (v acyklickém grafu vždy existuje).

Dopředný průchod spočítá hodnoty v₁, …, v_N v tomto pořadí podle bodu 3 — každý uzel až po všech svých rodičích.

Zpětný průchod spočítá pro každý uzel u ∈ U jeho adjungovanou hodnotu ū = ∂L/∂u v obráceném pořadí v_N, …, v₁: položí L̄ = 1 a pro u ≠ L použije vícerozměrné řetízkové pravidlo

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

(prázdný součet je 0). Zpětný průchod tedy pro každý uzel sečte příspěvky ze všech uzlů, do kterých u vstupuje; každá hrana se při tom použije právě jednou.

Všechny veličiny jsou reálná čísla: p₁, p₂, b, w, x, z ∈ ℝ, cíl t ∈ {0, 1} a výstup ŷ ∈ (0, 1).

Součet z = p₁ + p₂ + b: ∂z/∂p₁ = ∂z/∂p₂ = ∂z/∂b = 1 — součet pošle gradient do všech vstupů beze změny.

Součin p = wx: ∂p/∂w = x a ∂p/∂x = w — gradient se vynásobí druhým činitelem.

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

Křížová entropie L = −t ln ŷ − (1 − t) ln(1 − ŷ): ∂L/∂ŷ = −t/ŷ + 1 − t/1 − ŷ.

Nechť t ∈ {0, 1}, z ∈ ℝ, ŷ = σ(z) je logistická funkce a L = −t ln ŷ − (1 − t) ln(1 − ŷ) křížová entropie. Pak

∂L/∂z = ŷ − t.

Důkaz. Řetízkové pravidlo přes ŷ: ∂L/∂z = ∂L/∂ŷ · ∂ŷ/∂z = (−t/ŷ + 1 − t/1 − ŷ) · ŷ(1 − ŷ) = −t(1 − ŷ) + (1 − t)ŷ = ŷ − t. ∎

V obrázku: ∂L/∂z =0,500 − 1 = −0,500. Dělení ŷ a násobení ŷ(1 − ŷ) se navzájem zkrátí — proto se křížová entropie páruje s logistickou funkcí (a jak uvidíte, i se softmaxem).

Nechť G = (U, H) je výpočetní graf s E = |H| hranami, ve kterém každý uzel ovlivňuje ztrátu (z každého uzlu vede cesta do L), a nechť každou hodnotu f_v i každou lokální derivaci ∂f_v/∂u lze spočítat v konstantním čase. Pak zpětný průchod spočítá všechny adjungované hodnoty ū, u ∈ U — mezi nimi všechny derivace ∂L/∂θ_i podle parametrů — v čase O(E), tedy ve stejném řádu jako dopředný průchod a nezávisle na počtu parametrů.

Důkaz. Ve vzorci pro ū se každá hrana u → v objeví v součtu právě jednou, součty dohromady tedy mají E členů. Každý uzel kromě L má aspoň jednu odchozí hranu, takže |U| ≤ E + 1 a i práce na jednotlivých uzlech je O(E). ∎

Numerická derivace L(θ + he_i) − L(θ − he_i)/2h (e_i je i-tý jednotkový vektor, h > 0 malé číslo) by potřebovala dva dopředné průchody na každý parametr — u sítě s miliardou parametrů dvě miliardy průchodů místo jednoho zpětného.

Pro m ∈ ℕ, m ≥ 1, je softmax funkce softmax : ℝ^m → (0, 1)^m daná po složkách (viz díl o softmaxu)

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

Nechť n ∈ ℕ, n ≥ 1, je počet vrstev, d₀, d₁, …, d_n ≥ 1 jsou šířky vrstev, x ∈ ℝ^d₀ je vstup a pro ℓ = 1, …, n jsou W^(ℓ) ∈ ℝ^{d_ℓ×d_ℓ−1} váhy a b^(ℓ) ∈ ℝ^d_ℓ biasy vrstvy ℓ. Síť se softmaxem ve všech vrstvách počítá a⁽⁰⁾ = x a pro ℓ = 1, …, n

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

po složkách z_i^(ℓ) = ∑_j=1^d_ℓ−1 W_ij^(ℓ)a_j^(ℓ−1) + b_i^(ℓ) pro i = 1, …, d_ℓ (součtová bázová funkce).

Cíl je vektor t ∈ {0, 1}^d_n s ∑_k t_k = 1 (jediná jednička na pozici správné třídy) a ztráta je křížová entropie

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

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

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

Chyba vrstvy tedy říká, jak ztráta závisí na vstupu aktivace; z ní se pak dají přečíst gradienty vah i biasů.

Nechť m ∈ ℕ, m ≥ 1, z ∈ ℝ^m a a = softmax(z). Pro i, j ∈ {1, …, m} označme δ_ij Kroneckerovo delta (δ_ij = 1 pro i = j, jinak 0). Pak pro všechna i, j ∈ {1, …, m}

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

maticově

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. Podle pravidla pro podíl

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

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

Dvě vlastnosti budeme potřebovat: J je symetrická a každý její řádek (i sloupec) má součet nula, protože ∑_j a_i(δ_ij − a_j) = a_i − a_i∑_ja_j = 0.

Nechť síť, cíl t a ztráta L jsou jako v definici výše. Pak

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

Důkaz. Píšeme a = a⁽ⁿ⁾, z = z⁽ⁿ⁾. Ztráta závisí na a jako ∂L/∂a_i = −t_i/a_i. Každé z_j ovlivní všechna a_i, takže se sčítá přes i a použije se lemma 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,

protože ∑_i t_i = 1. ∎

Je to stejný tvar jako ŷ − t u jednoho neuronu: logaritmus ve ztrátě zruší exponenciálu v softmaxu a z celé Jacobiho matice zbude rozdíl „co síť řekla“ minus „co měla říct“.

Nechť n ≥ 2, síť, cíl a ztráta jsou jako v definici výše a J⁽ⁿ⁻¹⁾ = diag(a⁽ⁿ⁻¹⁾) − a⁽ⁿ⁻¹⁾(a⁽ⁿ⁻¹⁾)^T je Jacobiho matice softmaxu vrstvy n − 1 (lemma 1). Označme g⁽ⁿ⁻¹⁾ = ∂L/∂a⁽ⁿ⁻¹⁾ ∈ ℝ^d_n−1. Pak

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

kde a = a⁽ⁿ⁻¹⁾, g = g⁽ⁿ⁻¹⁾ a a·g = ∑_i a_ig_i je průměr g vážený aktivacemi vrstvy (váhy a_i jsou kladné a dávají součet 1).

Důkaz. Nejdřív gradient podle výstupů vrstvy n − 1. Protože z_i⁽ⁿ⁾ = ∑_j W_ij⁽ⁿ⁾a_j⁽ⁿ⁻¹⁾ + b_i⁽ⁿ⁾, je ∂z_i⁽ⁿ⁾/∂a_j⁽ⁿ⁻¹⁾ = W_ij⁽ⁿ⁾ a podle řetízkového pravidla g_j = ∑_i ∂L/∂z_i⁽ⁿ⁾ · W_ij⁽ⁿ⁾ = ∑_i W_ij⁽ⁿ⁾ δ_i⁽ⁿ⁾, což je bod 1.

Chyba se tedy vrací po stejných vahách, kterými signál šel dopředu, jen v opačném směru — odtud transpozice. Pak projde zpátky softmaxem vrstvy n − 1; podle lemmatu 1 a díky 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),

což je bod 2. ∎

Výklad: neuron dostane chybu úměrnou tomu, o kolik je „jeho“ gradient g_j nad váženým průměrem celé vrstvy, a navíc vynásobenou svou aktivací. Softmax nerozlišuje absolutní úroveň, jen poměry — proto se odečítá průměr.

Nechť síť, cíl a ztráta jsou jako v definici výše, J^(ℓ) je Jacobiho matice softmaxu vrstvy ℓ (lemma 1), ⊙ značí násobení po složkách a 1 vektor jedniček. Pak

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

Důkaz. (1) Úvaha z věty 3 nikde nevyužila, že vrstva n je poslední — jen to, že z^(ℓ+1) závisí na a^(ℓ) lineárně s maticí W^(ℓ+1) a že a^(ℓ) = softmax(z^(ℓ)). Rozepsáno přes všechny vrstvy:

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

(2) Váha W_ij^(ℓ) ovlivní jen z_i^(ℓ), a to s derivací ∂z_i^(ℓ)/∂W_ij^(ℓ) = a_j^(ℓ−1); bias b_i^(ℓ) s derivací 1. Řetízkové pravidlo dá ∂L/∂W_ij^(ℓ) = δ_i^(ℓ) · a_j^(ℓ−1) a ∂L/∂b_i^(ℓ) = δ_i^(ℓ). ∎

Gradient váhy je tedy „chyba neuronu, do kterého váha vede, krát aktivita neuronu, ze kterého vede“. Váha z neaktivního neuronu se neučí.

Nechť síť, cíl a ztráta jsou jako v definici výše. Pak pro každou vrstvu ℓ ∈ {1, …, n} platí

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

Důkaz. Pro ℓ = n: ∑(a_j − t_j) = 1 − 1 = 0. Pro skryté vrstvy: 1^Tδ^(ℓ) = 1^TJ^(ℓ)g^(ℓ) = 0, protože sloupce J mají součet nula (lemma 1). ∎

Důvod je hlubší: softmax se nezmění, když ke všem z_i ve vrstvě přičtete stejné číslo. Ve směru (1, 1, …, 1) je tedy ztráta plochá a gradient do něj nemůže ukazovat.

Nechť m ≥ 1, a ∈ (0, 1)^m s ∑_i a_i = 1 (výstup softmaxu) a J = diag(a) − aa^T. Pak všechna vlastní čísla J leží v intervalu [0, 1/2], a proto pro každé g ∈ ℝ^m platí

‖Jg‖ ≤ 1/2 ‖g‖.

Důkaz. J je symetrická, takže má reálná vlastní čísla. Řádek i má na diagonále a_i(1 − a_i) a mimo ni čísla −a_ia_j, jejichž absolutní hodnoty dají dohromady a_i(1 − a_i). Podle Geršgorinovy věty leží každé vlastní číslo v některém intervalu [0, 2a_i(1 − a_i)] a 2a(1 − a) ≤ 1/2 pro každé a ∈ ℝ. Pro symetrickou matici je ‖Jg‖ ≤ max |λ| · ‖g‖, kde maximum je přes vlastní čísla λ. ∎

Každá softmaxová vrstva tedy chybu cestou zpátky přinejmenším zpoloviční (pokud ji váhy nezesílí). To je jeden z důvodů, proč se softmax do skrytých vrstev nedává: v hluboké síti by gradient k prvním vrstvám skoro nedošel. Uvidíte to i v příkladu.

Nechť J : ℝ → ℝ, J(x) = x², start x₀ ∈ ℝ, x₀ ≠ 0, rychlost učení η > 0 a x_t+1 = x_t − ηJ′(x_t) pro t = 0, 1, 2, … Pak

1. x_t = (1 − 2η)^t x₀ pro všechna t ∈ ℕ₀;
2. x_t → 0 (sestup konverguje do minima), právě když |1 − 2η| < 1, tj. právě když η < 1;
3. pro η = 0,5 je x₁ = 0 — sestup skončí v minimu jediným krokem.

Důkaz. Jeden krok je x_t+1 = x_t − η · 2x_t = (1 − 2η)x_t; indukcí dostaneme mocninu. Posloupnost q^t jde k nule právě pro |q| < 1. ∎

(1) Nechť a > 0, J : ℝ → ℝ, J(x) = ax²/2 (druhá derivace je a), η > 0 a x₀ ≠ 0. Pak krok sestupu je x ← (1 − ηa)x a sestup konverguje do minima 0, právě když

0 < η < 2/a.

Parabola x² má a = 2, odtud hranice 1.

(2) Obecně: nechť J : ℝ^d → ℝ je diferencovatelná a její gradient má Lipschitzovu konstantu L > 0, tj. ‖∇J(u) − ∇J(v)‖ ≤ L‖u − v‖ pro všechna u, v ∈ ℝ^d (zakřivení nikde nepřesáhne L), a nechť 0 < η ≤ 1/L. Pak J(θ_t+1) ≤ J(θ_t) pro každé t — ztráta v žádném kroku nevzroste (standardní výsledek, viz např. Nesterov: Introductory Lectures on Convex Optimization, 2004, odd. 1.2.3). Rychlost učení se tedy musí řídit nejstrmějším zakřivením krajiny.

Nechť d ≥ 1 a A ∈ ℝ^d×d je symetrická pozitivně definitní matice; její vlastní čísla jsou reálná a kladná, označme λ_min > 0 nejmenší a λ_max největší z nich. Číslo podmínky matice A je

κ = λ_max/λ_min ≥ 1,

poměr největšího a nejmenšího vlastního čísla. Pro kvadratickou ztrátu J : ℝ^d → ℝ, J(θ) = 1/2 θ^TAθ, jsou vlastní čísla A zakřivení v hlavních směrech a číslo podmínky ztráty je číslo podmínky A. Naše údolí má A = diag(1, 20), tedy κ = 20.

Pro tuto ztrátu platí (standardní výsledek): gradientní sestup s rychlostí učení η konverguje z každého startu, právě když 0 < η < 2/λ_max. I s nejlepší pevnou volbou η = 2/λ_min + λ_max platí jen ‖θ_t+1‖ ≤ κ − 1/κ + 1 ‖θ_t‖ (minimum je v θ = 0) — u nás 19/21 ≈ 0,905. Čím větší κ, tím blíž je tento koeficient k 1 a tím pomalejší sestup.

Nechť J : ℝ^d → ℝ je diferencovatelná ztrátová funkce, θ₀ ∈ ℝ^d počáteční parametry, η > 0 rychlost učení a β ∈ [0, 1) koeficient momenta. Sestup s momentem položí v₀ = 0 ∈ ℝ^d a pro t = 0, 1, 2, … počítá

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

zastaví se stejně jako gradientní sestup (malý gradient nebo vyčerpaný počet kroků). Vektor v_t ∈ ℝ^d je „rychlost“ a β říká, kolik z ní zůstane do dalšího kroku (typicky 0,9; v našem údolí nejlépe 0,6). Pro β = 0 jde o obyčejný gradientní sestup.

Nechť η > 0, β ∈ [0, 1), g ∈ ℝ^d a gradient je v průběhu sestupu pořád stejný, ∇J(θ_t) = g pro všechna t (rovný svah), a v₀ = 0. Pak pro každé t ≥ 1

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

Důkaz. Indukcí z v_t+1 = βv_t − ηg; součet geometrické řady, a β^t → 0, protože 0 ≤ β < 1. ∎

Na rovném svahu se tedy krok ustálí na η/1 − β-násobku gradientu: pro β = 0,6 je to 2,5krát delší krok, pro obvyklé β = 0,9 desetkrát. Když se znaménko gradientu střídá, součet řady se naopak skoro vyruší.

Ve směru x se krok prodloužil z 0,4 na 0,6 (gradient má pořád stejné znaménko), ve směru y se rychlost −2,4 a nový tah +2,4 skoro vyrušily a koule je u dna údolí (y = −0,24). Obyčejný sestup je po dvou krocích teprve v (−3,31; 0,77).

Nechť J : ℝ^d → ℝ je diferencovatelná ztrátová funkce. Adam je algoritmus:

• vstup: počáteční parametry θ₀ ∈ ℝ^d, rychlost učení η > 0, koeficienty β₁, β₂ ∈ [0, 1), malé číslo ε > 0 a počet kroků T ∈ ℕ;
• výstup: parametry θ_T ∈ ℝ^d.

Polož m₀ = s₀ = 0 ∈ ℝ^d a pro t = 1, 2, …, T proveď (všechny operace s vektory — čtverec, odmocnina, dělení — jsou po složkách):

1. g_t = ∇J(θ_t−1);
2. m_t = β₁m_t−1 + (1 − β₁)g_t (průměr gradientů);
3. s_t = β₂s_t−1 + (1 − β₂)g_t² (průměr čtverců gradientů);
4. m̂_t = m_t/1 − β₁^t,   ŝ_t = s_t/1 − β₂^t (oprava počátečního zkreslení, viz další definice);
5. θ_t = θ_t−1 − η m̂_t/√ŝ_t + ε.

Obvyklé hodnoty: β₁ = 0,9, β₂ = 0,999, ε = 10⁻⁸. Adam tedy dělá krok ve směru průměrného gradientu, v každé složce vydělený typickou velikostí gradientu v té složce.

Nechť g₁, g₂, … je posloupnost reálných čísel (nebo vektorů z ℝ^d) a β ∈ [0, 1). Exponenciální klouzavý průměr této posloupnosti je posloupnost (m_t)_{t ≥ 0} daná rekurzí

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

rozepsáno m_t = (1 − β) ∑_k=1^t β^t−kg_k. Pro t ≥ 1 a β > 0 je jeho oprava o počáteční zkreslení

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

Váhy (1 − β)β^t−k, k = 1, …, t, dají dohromady jen 1 − β^t, ne 1 — chybějící část připadá na počáteční nulu. Proto je m_t na začátku zkreslený k nule a oprava z něj dělá skutečný vážený průměr (váhy po opravě dávají součet 1; při stálém g_k = g je přesně m̂_t = g).

Gradient ve směru y je šestkrát větší než ve směru x, a přesto se oba parametry posunuly o stejných 0,5. Obyčejný sestup by se ve směru y posunul šestkrát dál než ve směru x.

Nechť n ≥ 1 je počet příkladů v datech, L₁, …, L_n : ℝ^d → ℝ jsou diferencovatelné ztráty jednotlivých příkladů a celková ztráta je jejich průměr

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

Stochastický gradientní sestup je gradientní sestup (se vstupy θ₀, η a počtem kroků jako výše), ve kterém se v každém kroku t místo ∇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ždém kroku znovu náhodně vybraná neprázdná množina indexů (typicky pevné velikosti |B_t| ≪ n). Epocha je úsek kroků, během kterého se každý z n příkladů použije právě jednou (při zamíchání dat a procházení po dávkách velikosti b je to n/b kroků, je-li n dělitelné b).

Nechť J = 1/n ∑_i=1ⁿ L_i je jako v definici SGD, θ ∈ ℝ^d pevné a b ≥ 1. Nechť I₁, …, I_b jsou nezávislé náhodné indexy, každý s rovnoměrným rozdělením na {1, …, n} (výběr s vracením), a

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

Pak

1. E[g] = ∇J(θ) — odhad je nestranný;
2. pro každou složku j = 1, …, d je var(g_j) = 1/b var(∂L_I1/∂θ_j(θ)), takže směrodatná odchylka (typická chyba) odhadu klesá jako 1/√b.

Důkaz. (1) Pro jeden náhodný index I je E[∇L_I(θ)] = ∑_i=1ⁿ 1/n ∇L_i(θ) = ∇J(θ); průměr b takových odhadů má stejnou střední hodnotu. (2) Rozptyl průměru b nezávislých stejně rozdělených veličin je rozptyl jedné vydělený b. ∎

V praxi (i v našem programu) se data místo nezávislého výběru zamíchají a berou postupně po dávkách — každý příklad se v epoše použije právě jednou. Na tvaru závěru to skoro nic nemění.

Nechť n ≥ 1 a (x_i, y_i) ∈ ℝ², i = 1, …, n, jsou data. Pro parametry (a, b) ∈ ℝ² přímky ŷ = ax + b je střední kvadratická chyba funkce 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-tém příkladu. Pak (derivace složené funkce)

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

SGD počítá tytéž součty, jen přes dávku B a s 2/|B| místo 2/n.

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

1. θ* je globální minimum J, právě když ∀θ ∈ ℝ^d : J(θ*) ≤ J(θ).
2. θ* je lokální minimum J, právě když ∃r > 0 ∀θ ∈ ℝ^d : ‖θ − θ*‖ < r ⇒ J(θ*) ≤ J(θ). Lokální maximum je definováno stejně s ≥ místo ≤.
3. Je-li J diferencovatelná, je θ* stacionární bod, právě když ∇J(θ*) = 0.
4. θ* je sedlo, právě když je stacionární bod a není lokální minimum ani lokální maximum.

Ve stacionárním bodě se gradientní sestup zastaví, ať je to cokoli. Je-li J dvakrát spojitě diferencovatelná, rozliší typ stacionárního bodu Hessova matice H ∈ ℝ^d×d, H_ij = ∂²J/∂θ_i ∂θ_j(θ*): má-li všechna vlastní čísla kladná, je θ* lokální minimum; všechna záporná — lokální maximum; kladná i záporná — sedlo. Je-li některé vlastní číslo nulové a ostatní stejného znaménka, test nerozhodne.

Maximum u 0,17 je „hřeben“ mezi oběma údolími: míček, který startuje vpravo od něj, se skutálí do lokálního minima, vlevo do globálního. Sedlo v jedné proměnné nevznikne — potřebuje aspoň dva směry. Nejjednodušší je J(x, y) = x² − y²: v počátku je ∇J = (2x, −2y) = 0 a H = diag(2, −2) má vlastní čísla obou znamének.

Definice. Nechť J : ℝ^d → ℝ. Funkce J je konvexní, právě když

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

— úsečka mezi dvěma body grafu nikde neleží pod grafem.

Věta. Nechť J : ℝ^d → ℝ je konvexní a θ* ∈ ℝ^d je lokální minimum J. Pak θ* je globální minimum J.

Důkaz. Předpokládejme pro spor, že existuje u ∈ ℝ^d s J(u) < J(θ*). Pro body θ_λ = λu + (1 − λ)θ* platí J(θ_λ) ≤ λJ(u) + (1 − λ)J(θ*) < J(θ*) pro každé λ ∈ (0, 1]. Pro malé λ leží θ_λ libovolně blízko θ* — to je spor s lokální minimalitou. ∎

Parabola i údolí z předchozích oddílů jsou konvexní, ztráta neuronové sítě s nelineárními aktivacemi obecně ne — proto u sítí záleží na startu.