Druhy strojového učení: s učitelem, bez učitele, s částečným učitelem a další

Nechť je dán počítačový program a tyto tři objekty:

1. T — třída úloh, které má program řešit (např. „rozhodni o e-mailu, zda je spam“);
2. P — míra výkonu: pravidlo, které výsledku programu na úlohách z T přiřadí číslo, přičemž větší číslo znamená lepší výkon (např. podíl správně zařazených e-mailů);
3. E — zkušenost: data nebo interakce, které program při učení dostane (např. e-maily, které už někdo roztřídil).

Program se učí ze zkušenosti E vzhledem ke třídě úloh T a míře výkonu P, právě když se jeho výkon na úlohách z T, měřený pomocí P, zlepšuje se zkušeností E — tj. program, který zpracoval víc zkušenosti z E, dosahuje na T (v průměru) vyšší hodnoty P.

Je to pojmová definice, ne matematická: T, P a E se pro každou konkrétní úlohu teprve musí zvolit. Formální tvar pro učení s učitelem je v další části.

Nechť 𝒳 je neprázdná množina (prostor vstupů), 𝒴 neprázdná množina (prostor výstupů) a p ∈ ℕ, p ≥ 1. Model s parametry θ ∈ ℝ^p je soustava funkcí

f_θ : 𝒳 → 𝒴,   x ↦ f_θ(x),   θ ∈ ℝ^p,

tj. každá volba vektoru θ určuje jednu funkci ze vstupů do výstupů.

Nechť J : ℝ^p → ℝ je účelová funkce spočítaná z dat (čím menší J(θ), tím lépe model s parametry θ data popisuje). Učení (trénink) je hledání parametrů

θ* ∈ argmin_{θ ∈ ℝ^p} J(θ) = {θ ∈ ℝ^p : J(θ) ≤ J(θ′) pro všechna θ′ ∈ ℝ^p}.

Je-li J diferencovatelná, hledá se typicky gradientním sestupem: zvol počáteční θ₀ ∈ ℝ^p a rychlost učení η > 0 a pro t = 0, 1, 2, … polož

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

dokud se J znatelně zmenšuje (nebo do pevného počtu kroků). Gradientní sestup obecně najde jen lokální minimum, ne nutně prvek argmin.

Nechť 𝒳 je prostor vstupů, 𝒴 prostor štítků (správných odpovědí) a P neznámé rozdělení pravděpodobnosti dvojic (X, Y) na 𝒳 × 𝒴. Dále nechť

1. n ∈ ℕ, n ≥ 1, a trénovací množina D = ((x_i, y_i))_i=1ⁿ je posloupnost dvojic (x_i, y_i) ∈ 𝒳 × 𝒴 vybraných z P navzájem nezávisle;
2. {f_θ : 𝒳 → 𝒴 : θ ∈ ℝ^p} je model (viz definice výše);
3. L : 𝒴 × 𝒴 → [0, ∞) je ztrátová funkce — L(ŷ, y) je trest za odpověď ŷ, je-li správná odpověď y.

Učení s učitelem je hledání parametrů, které minimalizují empirické riziko R̂ : ℝ^p → [0, ∞):

R̂(θ) = 1/n ∑_i=1ⁿ L(f_θ(x_i), y_i),   θ* ∈ argmin_{θ ∈ ℝ^p} R̂(θ).

Cílem ale není trénovací množina — model má mít malé skutečné riziko R(θ) = E_{(X, Y) ∼ P}[L(f_θ(X), Y)], tj. dobře fungovat na nových datech z téhož rozdělení (generalizace). R neznáme, proto se odhaduje průměrnou ztrátou na odložené testovací množině, která se k učení nepoužila.

Klasifikace je učení s učitelem, ve kterém je prostor štítků konečná množina tříd 𝒴 = {1, …, K}, K ∈ ℕ, K ≥ 2. Model k vstupu x ∈ 𝒳 vrací odhad rozdělení přes třídy, tj. čísla p_θ(k | x) ≥ 0 pro k = 1, …, K s ∑_k=1^K p_θ(k | x) = 1.

Běžná ztráta je křížová entropie: pro x ∈ 𝒳 se štítkem y ∈ 𝒴

L = −∑_k=1^K [y = k] log p_θ(k | x) = −log p_θ(y | x),

kde [y = k] je 1, právě když y = k, a jinak 0.

Logistická regrese pro dvě třídy 𝒴 = {0, 1}: nechť 𝒳 = ℝ^d, parametry jsou w ∈ ℝ^d a b ∈ ℝ a σ : ℝ → (0, 1) je logistická funkce

σ(z) = 1/1 + e^−z.

Model je p(y = 1 | x) = σ(w^⊤x + b) a p(y = 0 | x) = 1 − σ(w^⊤x + b). Bod x zařadí do třídy 1, právě když σ(w^⊤x + b) ≥ 0,5, tj. právě když w^⊤x + b ≥ 0. Rozhodovací hranice je množina

{x ∈ ℝ^d : w^⊤x + b = 0}

— pro w ≠ 0 nadrovina, v rovině (d = 2) přímka.

Derivace průměrné křížové entropie J podle vah vyjde překvapivě jednoduše (díky σ′ = σ(1 − σ) se zkrátí):

∂J/∂w = 1/n ∑_i=1ⁿ (p_i − y_i) x_i,   ∂J/∂b = 1/n ∑_i=1ⁿ (p_i − y_i),

kde p_i = σ(w^⊤x_i + b).

w, b ← počáteční hodnoty
opakuj E epoch:                       # epocha = jeden průchod všemi daty
    g_w, g_b ← 0, 0
    pro každý příklad (x, y):
        p ← σ(w·x + b)                # odhad pravděpodobnosti třídy 1
        g_w ← g_w + (p − y)·x         # chyba odhadu krát vstup
        g_b ← g_b + (p − y)
    w ← w − η·g_w / n                 # krok proti gradientu
    b ← b − η·g_b / n
třída(x) = 1, pokud σ(w·x + b) ≥ 0,5, jinak 0

Přesnost (accuracy) je podíl správně zařazených příkladů: |{i ∈ {1, …, n} : třída(x_i) = y_i}|/n.

Start: w = (0,4; 1,2), b = −0,9, rychlost učení η = 2,5. První bod má souřadnice (0,604; 0,673) a třídu 0:

z = 0,4 · 0,604 + 1,2 · 0,673 − 0,9 = 0,148,   p = σ(0,148) = 1/1 + e^−0,148 = 0,537.

Model tedy bodu třídy 0 přisoudí třídu 1 s pravděpodobností 0,537 — chyba. Ztráta (y = 0, takže ze vzorce křížové entropie výše zbude jen druhý sčítanec) je −ln(1 − 0,537) = 0,770 (barvy podle vzorce výše) a příspěvek ke gradientu (p − y) x = 0,537 · (0,604; 0,673) táhne obě váhy dolů.

Na celých datech: přesnost na startu 15 %, po 5 epochách 95 %, od 16. epochy 100 %. Průměrná křížová entropie (přirozený logaritmus) klesne z 0,780 na 0,175 po 60 epochách; i když jsou už všechny body správně, model dál zvětšuje váhy, aby si byl jistější.

Regrese je učení s učitelem, ve kterém jsou štítky reálná čísla: 𝒴 = ℝ. Nechť (x_i, y_i) ∈ 𝒳 × ℝ, i = 1, …, n, jsou trénovací dvojice a f : 𝒳 → ℝ model. Běžná ztráta je střední kvadratická chyba

MSE(f) = 1/n ∑_i=1ⁿ (f(x_i) − y_i)².

Lineární regrese s jedním vstupem: nechť 𝒳 = ℝ, n ≥ 2 a x₁, …, x_n nejsou všechna stejná. Model je f(x) = ax + b s parametry a, b ∈ ℝ. Označme průměry x̄ = 1/n ∑_i=1ⁿ x_i a ȳ = 1/n ∑_i=1ⁿ y_i. Pak MSE má jediné minimum (metoda nejmenších čtverců) v bodě

a = ∑_i=1ⁿ (x_i − x̄)(y_i − ȳ)/∑_i=1ⁿ (x_i − x̄)²,   b = ȳ − ax̄.

(Předpoklad, že x_i nejsou všechna stejná, zaručuje nenulový jmenovatel.)

MSE(a, b) je kvadratická funkce dvou proměnných, takže minimum je tam, kde jsou obě parciální derivace nulové:

∂/∂b: 2/n ∑ (ax_i + b − y_i) = 0  ⇒  b = ȳ − ax̄ (přímka prochází těžištěm dat),

∂/∂a: 2/n ∑ (ax_i + b − y_i) x_i = 0; po dosazení b vyjde vzorec pro a z definice výše.

Pro 24 bytů v grafu: a = 0,797, b = 0,083, MSE = 0,0046, tedy typická svislá odchylka (čárkované úsečky) √MSE ≈ 0,068. Data jsme vyrobili jako y = 0,12 + 0,72 x + šum se směrodatnou odchylkou 0,06 — metoda z 24 bodů trefila skutečný sklon i šum zhruba, ne přesně.

Nechť 𝒳 je prostor vstupů, P_X neznámé rozdělení na 𝒳 a D = (x_i)_i=1ⁿ, x_i ∈ 𝒳, vstupy vybrané z P_X navzájem nezávisle — bez štítků. Učení bez učitele hledá z D strukturu rozdělení P_X. Typické úlohy:

1. shlukování — rozklad indexů {1, …, n} na k neprázdných, navzájem disjunktních množin C₁, …, C_k (shluků) tak, aby si body v jednom shluku byly podobné;
2. snížení dimenze — pro 𝒳 = ℝ^d zobrazení g : ℝ^d → ℝ^m, m < d, které zachová co nejvíc informace o datech;
3. odhad hustoty — funkce p̂ : 𝒳 → [0, ∞), která aproximuje hustotu p(x) rozdělení P_X.

Co přesně je „podobné“ nebo „co nejvíc informace“, určí až konkrétní metoda svou účelovou funkcí — jako k-means níže.

Nechť x₁, …, x_n ∈ ℝ^d jsou body, k ∈ ℕ, 1 ≤ k ≤ n, a ‖·‖ je eukleidovská norma. Pro rozklad bodů do k navzájem disjunktních shluků C₁, …, C_k (každý bod patří právě do jednoho) a středy μ₁, …, μ_k ∈ ℝ^d je vnitroshluková suma čtverců

J(C₁, …, C_k, μ₁, …, μ_k) = ∑_j=1^k ∑_{x ∈ Cj} ‖x − μ_j‖².

Úloha k-means je najít shluky a středy, pro které je J minimální.

Lloydův algoritmus (přibližné řešení). Vstup: body x₁, …, x_n ∈ ℝ^d, počet shluků k a počáteční středy μ₁, …, μ_k ∈ ℝ^d. Výstup: shluky C₁, …, C_k a středy μ₁, …, μ_k. Opakuj:

1. přiřazení: každý bod x_i zařaď do shluku C_j s j ∈ argmin_{j′ ∈ {1, …, k}} ‖x_i − μ_j′‖² (nejbližší střed);
2. přesun středů: pro každé j = 1, …, k s C_j ≠ ∅ polož μ_j = 1/|C_j| ∑_{x ∈ Cj} x (průměr bodů shluku).

Zastavení: když se v kroku 2 žádný střed nezmění. Žádný krok J nezvýší a možných rozkladů je konečně mnoho, takže algoritmus skončí — ale obecně jen v lokálním minimu J.

μ₁, …, μ_k ← počáteční středy
opakuj:
    pro každý bod x:                     # krok 1: přiřazení
        c(x) ← argmin_j ‖x − μ_j‖²
    pro každé j = 1, …, k:               # krok 2: přesun středů
        μ_j ← průměr bodů s c(x) = j
dokud se středy hýbou

Proč J neroste. Krok 1 mění jen přiřazení a každý bod přejde k bližšímu středu, takže jeho sčítanec ‖x − μ_j‖² neroste. Krok 2 mění jen středy a průměr je bod, který minimalizuje součet čtverců vzdáleností ke skupině bodů (derivace ∑ ‖x − μ‖² podle μ je −2 ∑ (x − μ), nulová právě pro průměr). Možných přiřazení je konečně mnoho, takže algoritmus skončí.

V našem grafu (66 bodů) má J v jednotlivých iteracích hodnoty 19,330 → 2,937 → 1,048 → 0,655 — největší kus práce udělá hned první přesun středů ze špatného startu.

Nechť 𝒳 je prostor vstupů, 𝒴 prostor štítků, P neznámé rozdělení na 𝒳 × 𝒴 a l, u ∈ ℕ, l ≥ 1. Jsou dány

1. malá označená množina D_L = ((x_i, y_i))_i=1^l, (x_i, y_i) ∈ 𝒳 × 𝒴, vybraná nezávisle z P;
2. velká neoznačená množina D_U = (x_j)_j=l+1^l+u, x_j ∈ 𝒳, vybraná nezávisle z rozdělení samotných vstupů X (štítky y_j existují, ale neznáme je), kde u ≫ l.

Učení s částečným učitelem má stejný cíl jako učení s učitelem — model f_θ : 𝒳 → 𝒴 s malým skutečným rizikem —, ale k jeho dosažení využije D_L i D_U.

Neoznačená data mohou pomoci jen tehdy, když rozdělení vstupů něco říká o štítcích. Používají se tyto předpoklady (každá metoda stojí aspoň na jednom z nich):

1. hladkost — jsou-li dva vstupy x, x′ ∈ 𝒳 blízko sebe v oblasti, kde je hodně dat, mají (s velkou pravděpodobností) stejný štítek;
2. shluky — vstupy z jednoho shluku mají (s velkou pravděpodobností) stejný štítek, takže hranice tříd vede místy s malou hustotou dat;
3. varieta — data v 𝒳 = ℝ^d leží blízko plochy (variety) dimenze m < d a vzdálenost bodů se má měřit po této ploše, ne přímou čarou v ℝ^d.

Vstup: body x₁, …, x_N ∈ ℝ^d, z nichž některé mají štítek ze 𝒴 = {0, 1}, a počet sousedů k ∈ ℕ (zde k = 4). Výstup: štítek pro každý bod, do kterého se dá z označených bodů dojít po hranách grafu.

1. Sestroj neorientovaný graf: body x_i a x_j (i ≠ j) spoj hranou, právě když x_j patří mezi k nejbližších sousedů bodu x_i, nebo x_i mezi k nejbližších sousedů bodu x_j (podle eukleidovské vzdálenosti).
2. V jednom kole projdi všechny neoznačené body; každý, který má aspoň jednoho označeného souseda, dostane štítek, který má většina jeho označených sousedů (při rovnosti hlasů štítek 0). Štítky přidělené v kole platí až od dalšího kola.
3. Zastavení: opakuj krok 2, dokud jsou neoznačené body a v posledním kole přibyl aspoň jeden štítek.

Nechť D = (x_i)_i=1ⁿ, x_i ∈ 𝒳, jsou neoznačená data a nechť g je pevně zvolené (případně náhodné) pravidlo, které z každého vstupu x ∈ 𝒳 automaticky, bez lidské práce, vyrobí dvojici

g(x) = (x̃, t),

kde x̃ je část nebo poškozená verze vstupu x a t to, co v x̃ chybí. Samoučení je učení s učitelem na trénovací množině (g(x_i))_i=1ⁿ: model dostane x̃ a má předpovědět t. Tato uměle vyrobená úloha se jmenuje předtextová úloha (pretext task).

Předpověď dalšího tokenu — tak se předtrénovávají velké jazykové modely. Nechť V je konečný slovník tokenů a text je posloupnost x₁, …, x_T ∈ V, T ≥ 1. Model pro každé t = 1, …, T vrací rozdělení p_θ(· | x₁, …, x_t−1) na V (pro t = 1 bez podmínky) a parametry θ se volí tak, aby byla co největší

∑_t=1^T log p_θ(x_t | x₁, …, x_t−1).

Tady x̃ = (x₁, …, x_t−1) a t-tý token je štítek.

Markovův rozhodovací proces (prostředí) je pětice (S, A, P, R, γ), kde

1. S je neprázdná množina stavů (u nás konečná — políčka mřížky);
2. A je neprázdná konečná množina akcí;
3. P je pravděpodobnost přechodu: pro každé s ∈ S a a ∈ A je P(· | s, a) rozdělení pravděpodobnosti na S, tj. P(s′ | s, a) ≥ 0 a ∑_{s′ ∈ S} P(s′ | s, a) = 1 (P(s′ | s, a) je pravděpodobnost, že akce a ve stavu s vede do stavu s′);
4. R : S × A × S → ℝ je odměna za přechod z s akcí a do s′;
5. γ ∈ [0, 1) je diskontní faktor.

Politika agenta je pravidlo π, které každému stavu s ∈ S přiřadí rozdělení π(· | s) na A. Agent začne ve stavu s₀ a pro t = 0, 1, 2, … volí akci a_t podle π(· | s_t), prostředí vybere další stav s_t+1 podle P(· | s_t, a_t) a agent dostane odměnu r_t = R(s_t, a_t, s_t+1). Návrat je

G = ∑_t=0^∞ γ^t r_t

(v koncovém stavu epizoda končí a další odměny jsou 0) a cílem je najít politiku, která maximalizuje jeho střední hodnotu E[G].

Hodnota akce Q(s, a) je očekávaný návrat, když agent ve stavu s provede akci a a dál hraje nejlépe. Q-learning ji odhaduje tabulkou Q : S × A → ℝ (na začátku např. samé nuly): po každém kroku (s, a, r, s′) s rychlostí učení α ∈ (0, 1] provede

Q(s, a) ← Q(s, a) + α [r + γ max_{a′ ∈ A} Q(s′, a′) − Q(s, a)],

přičemž je-li s′ koncový stav, bere se max_a′ Q(s′, a′) = 0.

Nechť A je konečná neprázdná množina akcí, Q : S × A → ℝ tabulka hodnot akcí a ε ∈ [0, 1]. Pro stav s ∈ S zvolme a*(s) ∈ argmax_{a ∈ A} Q(s, a) (při rovnosti libovolnou z nejlepších). ε-hladová politika zvolí ve stavu s akci a ∈ A s pravděpodobností

π(a | s) = ε/|A| + (1 − ε) · [a = a*(s)],

kde [a = a*(s)] je 1, právě když a = a*(s), jinak 0. Jinými slovy: s pravděpodobností ε zvolí akci náhodně (rovnoměrně ze všech), jinak akci s největším Q(s, a). U nás ε = 0,2.

První krok. Na začátku je celá tabulka Q nulová. Agent udělá krok na obyčejné políčko: r = −1 a max_a′ Q(s′, a′) = 0, takže

Q(s, a) ← 0 + 0,5 · [−1 + 0,95 · 0 − 0] = −0,5

(barvy podle vzorce Q-learningu výše). Krok do cíle je koncový, takže člen max_a′ Q(s′, a′) je 0: Q ← 0 + 0,5 · [10 − 0] = 5. Při dalších návštěvách se pětka posune k 10 a po cestě zpět se šíří dál, vždy vynásobená 0,95 a zmenšená o cenu kroku.

Hodnota startu. Nejkratší cesta má 10 kroků: devět obyčejných za −1 a poslední do cíle za +10. Nediskontovaný návrat je 9 · (−1) + 10 = 1, diskontovaný

G = −(1 + 0,95 + … + 0,95⁸) + 0,95⁹ · 10 = −1 − 0,95⁹/1 − 0,95 + 10 · 0,95⁹ = −7,395 + 6,302 = −1,093.

Naučená tabulka má na startu max_a Q(start, a) = −1,093 — Q-learning tu hodnotu optimální cesty našel přesně.

Nechť J_zdroj, J_cíl : ℝ^p → ℝ jsou účelové funkce zdrojové úlohy (obvykle s hodně daty) a cílové úlohy (obvykle s málo daty) pro model se stejnými parametry θ ∈ ℝ^p, a nechť θ₀ jsou parametry naučené na zdrojové úloze, tj. (přibližně) θ₀ ∈ argmin_θ J_zdroj(θ). Přenos učení hledá

θ* ∈ argmin_θ J_cíl(θ)

gradientním sestupem, který začne v θ₀ (místo náhodných hodnot). Při doladění (fine-tuning) se často mění jen parametry s indexy z malé množiny I ⊂ {1, …, p}; ostatní zůstanou rovné hodnotám v θ₀.

Nechť D_L je označená a D_U neoznačená množina (jako u učení s částečným učitelem), 𝒴 = {1, …, K} a model p_θ(· | x) natrénovaný na D_L. Aktivní učení opakuje tyto kroky:

1. model sám vybere vstup x* ∈ D_U, o kterém je nejméně jistý — například s nejvyšší entropií: x* ∈ argmax_{x ∈ DU} H(p_θ(· | x));
2. člověk (učitel) mu doplní štítek y*; dvojice (x*, y*) se přesune z D_U do D_L;
3. model se znovu natrénuje na D_L;

dokud nedojde rozpočet na označování.

Nechť p je rozdělení na {1, …, K}, tj. p(k) ≥ 0 a ∑_k=1^K p(k) = 1. Jeho entropie (v bitech) je

H(p) = −∑_k=1^K p(k) log₂ p(k),   kde se klade 0 · log₂ 0 = 0.

Pro dvě třídy: odhad 50 : 50 má H = −2 · 0,5 · log₂ 0,5 = 1 bit (nejvíc možného), odhad 90 : 10 H = −0,9 log₂ 0,9 − 0,1 log₂ 0,1 ≈ 0,137 + 0,332 = 0,469 bitu, odhad 99 : 1 jen 0,081 bitu. K označení půjde jako první příklad, kde model váhá 50 : 50.

Nechť 𝒳 je prostor vstupů a 𝒴 prostor štítků.

1. Diskriminativní model se učí přímo podmíněné rozdělení p_θ(y | x) pro x ∈ 𝒳, y ∈ 𝒴, nebo rovnou rozhodovací funkci f_θ : 𝒳 → 𝒴 (a tedy rozhodovací hranici). O tom, jak jsou rozdělené samotné vstupy x, nic neříká.
2. Generativní model se učí rozdělení dat p_θ(x) na 𝒳, případně sdružené rozdělení p_θ(x, y) na 𝒳 × 𝒴, a umí z něj vzorkovat nová data. Ze sdruženého rozdělení se dá dopočítat i podmíněné (pro konečné 𝒴): p_θ(y | x) = p_θ(x, y)/∑_{y′ ∈ 𝒴} p_θ(x, y′).