0 dní v řadě · 0 bodů

Strojové učení · 28 min

Gradientní sestup

Algoritmus, který stojí za tréninkem většiny modelů i neuronových sítí. Pochopíš ho na kopci v mlze a napíšeš ho v NumPy.

Hloubka
Úkoly
Lidsky řečeno

Stojíš v husté mlze na svahu a chceš dolů do údolí. Nevidíš dál než na špičky bot. Nohou ale poznáš, kam se terén svažuje. Uděláš krok tím směrem, znovu ohmatáš zem a zase krok. Mapu nepotřebuješ. Gradientní sestup hledá nejmenší chybu modelu úplně stejně.

Proč nestačí vzorec

Lineární regrese z minulé lekce má přesné řešení. To je výjimka. U logistické regrese ani u neuronových sítí žádný vzorec neexistuje a i tam, kde existuje, může být na obrovská data příliš drahý. Potřebujeme postup, který umí jediné: ze současného stavu se trochu zlepšit.

Začneme co nejjednodušeji. Model má jediný parametr w a jeho chyba je chyba(w) = (w - 3)² + 1. Vidíš, že nejmenší je při w = 3. Algoritmus to neví, smí se jen ptát na hodnotu v místě, kde stojí.

Sklon zjistíš tak, že se o kousíček posuneš a změříš, jak se chyba změnila. V matematice se tomu říká derivace. Kladný sklon znamená, že doprava chyba roste. Záporný, že doprava klesá.

def chyba(w):
    return (w - 3) ** 2 + 1

def sklon(w, h=1e-6):
    return (chyba(w + h) - chyba(w - h)) / (2 * h)

for w in [0.0, 1.0, 3.0, 5.0]:
    print(f"w = {w}   chyba = {chyba(w):5.2f}   sklon = {sklon(w):+.3f}")
Výstup
w = 0.0   chyba = 10.00   sklon = -6.000
w = 1.0   chyba =  5.00   sklon = -4.000
w = 3.0   chyba =  1.00   sklon = +0.000
w = 5.0   chyba =  5.00   sklon = +4.000

Všimni si dvou věcí. Znaménko sklonu ukazuje do kopce, takže jít se musí opačně. A velikost sklonu se směrem k minimu zmenšuje, v minimu je nulová. Pro tuhle funkci jde sklon spočítat přesně, je to 2 * (w - 3).

Pravidlo jednoho kroku

Celý algoritmus je jediný řádek, který se opakuje:

text
w = w - rychlost_uceni * sklon

Rychlost učení (learning rate, v kódu lr) určuje délku kroku. Mínus zajistí pohyb z kopce. Protože se sklon u dna zmenšuje, kroky se samy zkracují. Zkus si tipnout výsledek jednoho kroku.

w = 0.0
lr = 0.25
sklon = 2 * (w - 3)
w = w - lr * sklon
print(w)
Výstup
1.5

Když má funkce víc parametrů, má sklon v každém z nich. Všechny dohromady tvoří gradient: pole čísel, které ukazuje směr nejstrmějšího stoupání. Odtud název gradientní sestup.

Slož kód

Slož tréninkovou smyčku

Model má tvar odhad = w * x. Slož program tak, aby našel w pro jediný příklad x = 2, y = 10. Jeden z řádků je navíc.

Rychlost učení

Tohle je nejdůležitější nastavení celého postupu. Posouvej lr a sleduj, jak se hvězdička blíží ke svislé čáře, která značí minimum.

# lr a kroky nastavují posuvníky
w = 0.0
for krok in range(int(kroky) + 1):
    pozice = max(0, min(50, int(round(w * 8))))
    radek = [" "] * 51
    radek[24] = "|"
    radek[pozice] = "*"
    print(f"{krok:2d} {w:9.3f}  " + "".join(radek))
    if abs(w) > 1000:
        print("rozletělo se to")
        break
    w = w - lr * 2 * (w - 3)
Výstup
 0     0.000  *                       |
 1     0.600       *                  |
 2     1.080           *              |
 3     1.464              *           |
 4     1.771                *         |
 5     2.017                  *       |
 6     2.214                    *     |
 7     2.371                     *    |
 8     2.497                      *   |
 9     2.597                       *  |
10     2.678                       *  |
11     2.742                        * |
12     2.794                        * |
13     2.835                         *|
14     2.868                         *|
15     2.894                         *|

Stejný experiment v číslech, po 30 krocích ze startu w = 0:

def sestup(lr, kroky=30):
    w = 0.0
    for _ in range(kroky):
        w = w - lr * 2 * (w - 3)
    return w

for lr in [0.001, 0.01, 0.1, 0.5, 0.9, 1.0, 1.1]:
    print(f"lr = {lr:<6} w = {sestup(lr):12.4f}")
Výstup
lr = 0.001  w =       0.1749
lr = 0.01   w =       1.3635
lr = 0.1    w =       2.9963
lr = 0.5    w =       3.0000
lr = 0.9    w =       2.9963
lr = 1.0    w =       0.0000
lr = 1.1    w =    -709.1289
  • Příliš malá rychlost: postup je správný, ale do konce se nedojde.
  • Rozumná rychlost: w se rychle usadí u 3.
  • Na hraně (0.9): přeskakuje z jedné strany údolí na druhou a chvíli mu to trvá.
  • 1.0: skáče pořád mezi dvěma body a nikdy se nezlepší.
  • Příliš velká: každý přeskok je větší než předchozí a hodnoty utečou.
Kvíz

Gradient parametru vyšel kladný. Co s parametrem udělá další krok?

Sestup pro lineární regresi

Vrátíme se k účtenkám z taxíku. Parametry jsou dva, w a b, a chybou je MSE. Sklon v obou směrech dá derivace podle řetízkového pravidla: druhá mocnina přinese 2 * rozdíl a změna w se v odhadu projeví násobená x, změna b beze změny.

text
chyba = průměr((w * x + b - y)²)

dw = průměr(2 * (w * x + b - y) * x)
db = průměr(2 * (w * x + b - y))

Výsledek můžeme porovnat s přesným řešením.

import numpy as np

x = np.array([1.2, 2.5, 3.1, 4.8, 6.0, 7.4, 9.5, 12.0])
y = np.array([85, 120, 130, 185, 210, 245, 315, 380], dtype=float)

w, b = 0.0, 0.0
lr = 0.01

for krok in range(5001):
    rozdil = w * x + b - y
    dw = (2 * rozdil * x).mean()
    db = (2 * rozdil).mean()
    w -= lr * dw
    b -= lr * db
    if krok % 1000 == 0:
        print(f"krok {krok:4d}  MSE {np.mean(rozdil ** 2):10.2f}  w {w:6.2f}  b {b:6.2f}")

print("přesně:", np.round(np.polyfit(x, y, 1), 2))
Výstup
krok    0  MSE   52562.50  w  30.80  b   4.17
krok 1000  MSE      17.99  w  27.50  b  48.81
krok 2000  MSE      17.97  w  27.47  b  49.07
krok 3000  MSE      17.97  w  27.47  b  49.08
krok 4000  MSE      17.97  w  27.47  b  49.08
krok 5000  MSE      17.97  w  27.47  b  49.08
přesně: [27.47 49.08]

Chyba nejdřív prudce spadne a pak se dlouho dolaďuje hlavně b. Výsledek odpovídá vzorci, jen k němu vedla jiná cesta.

Úkol

Spočítej gradient

Napiš gradient(w, b, x, y), která pro pole x a y vrátí dvojici (dw, db) podle vzorců výše.

import numpy as np

def gradient(w, b, x, y):
    # doplň
    return 0.0, 0.0

print(gradient(1.0, 0.0, np.array([1.0, 2.0]), np.array([2.0, 3.0])))
Výstup
Úkol

Trénovací smyčka

Napiš trenuj(x, y, lr, kroky). Začni s w = 0 a b = 0, proveď zadaný počet kroků gradientního sestupu a vrať (w, b). Oba gradienty počítej ze stejných starých hodnot.

import numpy as np

def trenuj(x, y, lr, kroky):
    w, b = 0.0, 0.0
    # doplň
    return w, b

x = np.array([0.0, 1.0, 2.0, 3.0])
print(trenuj(x, 2 * x + 1, 0.05, 5000))
Výstup

Měřítko vlastností

Proč bylo u taxíku potřeba tolik kroků? Vlastnosti v různých jednotkách protáhnou údolí chyby do úzkého žlabu. Ve strmém směru se musíš pohybovat opatrně, jinak to vyletí, a v plochém směru pak lezeš jako šnek.

Řešením je standardizace: od každého sloupce odečti průměr a vyděl ho směrodatnou odchylkou. Všechny vlastnosti pak mají průměr 0 a podobný rozsah. Ukázka počítá kroky, než gradient skoro zmizí, s limitem 10 000. Plocha bytu se měří v desítkách až stovkách, pokoje v jednotkách.

import numpy as np

rng = np.random.default_rng(0)
n = 100
plocha = rng.uniform(30, 120, n)
pokoje = np.clip(np.round(plocha / 30 + rng.normal(0, 0.5, n)), 1, 6)
cena = 0.5 + 0.06 * plocha + 0.2 * pokoje + rng.normal(0, 0.2, n)   # miliony Kč

def sestup(X, y, lr, limit=10_000, tol=1e-3):
    theta = np.zeros(X.shape[1])
    for krok in range(limit):
        g = 2 / len(y) * X.T @ (X @ theta - y)
        if np.linalg.norm(g) < tol:
            return theta, krok
        theta -= lr * g
    return theta, limit

surove = np.column_stack([plocha, pokoje])
prumer, odchylka = surove.mean(axis=0), surove.std(axis=0)
skalovane = (surove - prumer) / odchylka

A = np.column_stack([np.ones(n), surove])
B = np.column_stack([np.ones(n), skalovane])

theta_a, kroky_a = sestup(A, cena, lr=1e-4)
theta_b, kroky_b = sestup(B, cena, lr=0.1)
print(f"surová data:   {kroky_a} kroků, MSE {np.mean((A @ theta_a - cena) ** 2):.4f}")
print(f"škálovaná:     {kroky_b} kroků, MSE {np.mean((B @ theta_b - cena) ** 2):.4f}")

# Převod vah zpět do původních jednotek
vahy = theta_b[1:] / odchylka
posun = theta_b[0] - vahy @ prumer
print("zpět v původních jednotkách:", np.round([posun, *vahy], 3))
print("přesné řešení:              ", np.round(np.linalg.lstsq(A, cena, rcond=None)[0], 3))
Výstup
surová data:   10000 kroků, MSE 0.0709
škálovaná:     165 kroků, MSE 0.0489
zpět v původních jednotkách: [0.521 0.06  0.191]
přesné řešení:               [0.52  0.06  0.189]

Na surových datech sestup vyčerpal celý limit a chyba je pořád vyšší než po škálování, kterému stačilo pár set kroků. Větší lr by surovým datům nepomohlo, sestup by se rozletěl. Naučené váhy po škálování platí pro škálovaná čísla, proto je na konci převádíme zpět.

Úkol

Standardizace bez úniku

Napiš standardizuj(X_train, X_test). Průměr a směrodatnou odchylku každého sloupce spočítej jen z X_train a stejnými čísly uprav obě pole. Vrať dvojici upravených polí. Důvod znáš z lekce o dělení dat.

import numpy as np

def standardizuj(X_train, X_test):
    # doplň
    return X_train, X_test

print(standardizuj(np.array([[1.0], [3.0]]), np.array([[5.0]])))
Výstup

Po dávkách: stochastický sestup

Zatím každý krok prošel všechna data. Při milionech řádků by jeden krok trval věčnost a přitom je zbytečně přesný. Gradient jde odhadnout z malé náhodné dávky (mini-batch), stejně jako průzkum veřejného mínění neobchází všechny voliče. Jednomu průchodu všemi daty se říká epocha.

Ukázka dává všem variantám stejný rozpočet: pět epoch, tedy stejný počet zpracovaných řádků.

import numpy as np

rng = np.random.default_rng(0)
n = 1000
X = np.column_stack([np.ones(n), rng.normal(size=(n, 3))])
spravne = np.array([3.0, 2.0, -1.0, 0.5])
y = X @ spravne + rng.normal(0, 0.5, n)

def mse(theta):
    return np.mean((X @ theta - y) ** 2)

def trenuj(velikost_davky, lr=0.05, epochy=5):
    rng = np.random.default_rng(1)
    theta = np.zeros(X.shape[1])
    kroku = 0
    for _ in range(epochy):
        poradi = rng.permutation(n)
        for start in range(0, n, velikost_davky):
            i = poradi[start:start + velikost_davky]
            g = 2 / len(i) * X[i].T @ (X[i] @ theta - y[i])
            theta -= lr * g
            kroku += 1
    return theta, kroku

print(f"nejlepší možná MSE: {mse(np.linalg.lstsq(X, y, rcond=None)[0]):.3f}")
for davka in [1000, 32, 1]:
    theta, kroku = trenuj(davka)
    print(f"dávka {davka:4d}: {kroku:4d} kroků, MSE {mse(theta):.3f}")
Výstup
nejlepší možná MSE: 0.253
dávka 1000:    5 kroků, MSE 5.232
dávka   32:  160 kroků, MSE 0.253
dávka    1: 5000 kroků, MSE 0.287

Celá data dovolí jen pět opatrných kroků a model zůstane daleko od cíle. Malé dávky za stejnou práci udělají kroků mnohem víc. Dávka velikosti 1 je nejrozkmitanější, šum ji drží kolem minima. Střední velikost je běžný kompromis a přesně tak se trénují neuronové sítě.

Ve scikit-learn tuto metodu najdeš jako SGDRegressor. Škálování k ní patří povinně, proto je spojené s modelem do jednoho řetězce. Podrobně se k tomu vrací lekce Pipelines a únik dat.

from sklearn.datasets import make_regression
from sklearn.linear_model import LinearRegression, SGDRegressor
from sklearn.model_selection import train_test_split
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler

X, y = make_regression(n_samples=1000, n_features=5, noise=10, random_state=0)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=0)

sgd = make_pipeline(
    StandardScaler(),
    SGDRegressor(max_iter=1000, tol=1e-3, random_state=0),
)
sgd.fit(X_train, y_train)
presne = LinearRegression().fit(X_train, y_train)

print(f"SGD:      R² = {sgd.score(X_test, y_test):.4f}")
print(f"vzorec:   R² = {presne.score(X_test, y_test):.4f}")
print("epoch SGD:", sgd[-1].n_iter_)
Výstup
SGD:      R² = 0.9913
vzorec:   R² = 0.9913
epoch SGD: 16

Obě hodnoty R² by měly vyjít velmi blízko sebe. Poslední řádek říká, po kolika epochách se trénink sám zastavil.

Když údolí není jedno

Chyba lineární regrese má tvar misky, odborně je konvexní: má jediné dno a sestup ho najde odkudkoli, pokud nepřestřelí. Složitější modely mají krajinu s více údolími a výsledek pak závisí na tom, kde jsi začal.

def chyba(w):
    return w ** 4 - 3 * w ** 2 + w

def sklon(w):
    return 4 * w ** 3 - 6 * w + 1

for start in [-2.0, -0.5, 0.5, 2.0]:
    w = start
    for _ in range(500):
        w -= 0.01 * sklon(w)
    print(f"start {start:+.1f}  ->  w = {w:+.3f}, chyba = {chyba(w):+.3f}")
Výstup
start -2.0  ->  w = -1.301, chyba = -3.514
start -0.5  ->  w = -1.301, chyba = -3.514
start +0.5  ->  w = +1.131, chyba = -1.070
start +2.0  ->  w = +1.131, chyba = -1.070

Starty skončily ve dvou různých údolích a jedno je hlubší než druhé. Sestup se ven sám nedostane, protože na dně je sklon nulový. U neuronových sítí s miliony parametrů je krajina mnohem složitější a dokonalé minimum nikdo nehledá, stačí dostatečně dobré. Tomu se věnuje lekce Optimalizátory a trénink sítí.

Kvíz

Proč se před gradientním sestupem vlastnosti škálují?

Kvíz

Co je jedna epocha?

Pod kapotou · proč rozhoduje číslo podmíněnosti

Pro MSE je gradient lineární v parametrech a Hessova matice je konstantní, H = 2 XᵀX / n. V bázi jejích vlastních vektorů se úloha rozpadne na nezávislé paraboly: chyba ve směru i se každým krokem násobí (1 - lr * λi). Konvergence proto vyžaduje 0 < lr < 2 / λmax a nejlepší pevný krok 2 / (λmax + λmin) dává rychlost (κ - 1) / (κ + 1), kde κ = λmax / λmin je číslo podmíněnosti. Počet kroků roste zhruba úměrně κ. Momentum ho umí stlačit přibližně na sqrt(κ).

import numpy as np

rng = np.random.default_rng(0)
n = 100
plocha = rng.uniform(30, 120, n)
pokoje = np.clip(np.round(plocha / 30 + rng.normal(0, 0.5, n)), 1, 6)
surove = np.column_stack([plocha, pokoje])
skalovane = (surove - surove.mean(axis=0)) / surove.std(axis=0)

for nazev, Z in [("surová", surove), ("škálovaná", skalovane)]:
    X = np.column_stack([np.ones(n), Z])
    vlastni = np.linalg.eigvalsh(2 * X.T @ X / n)
    kappa = vlastni[-1] / vlastni[0]
    print(f"{nazev:10s} lr musí být < {2 / vlastni[-1]:.5f}   κ = {kappa:,.0f}")
Výstup
surová     lr musí být < 0.00014   κ = 68,796
škálovaná  lr musí být < 0.54812   κ = 10

Horní mez vysvětluje lr z předchozí ukázky a κ rozdíl v počtu kroků. Škálování je vlastně levný předpodmiňovač. Náklady se liší i proti přímému řešení: krok stojí O(n * d), lstsq O(n * d²), takže iterace vyhrává při velkém d nebo řídkých datech.

U SGD s pevným lr se parametry neustálí v bodě, ale v oblasti, jejíž velikost roste s lr a klesá s velikostí dávky. Proto se lr v čase snižuje. Dvě praktické věci: data míchej každou epochu, protože seřazená data z gradientu dělají systematicky vychýlený odhad, a u vlastních gradientů si je ověř číselně, tedy centrální diferencí jako v sklon na začátku lekce. Odhalí většinu chyb v odvození a hodí se i při psaní vlastních vrstev sítí.

Vyzkoušej si: Gradientní sestup naživo

Nastav rychlost učení a výchozí bod a krokuj nebo přehrávej. Sleduj, kdy sestup konverguje a kdy se rozběhne.