Druhy strojového učenia: s učiteľom, bez učiteľa, s čiastočným učiteľom a ďalšie

Nech je daný počítačový program a tieto tri objekty:

1. T — trieda úloh, ktoré má program riešiť (napr. „rozhodni o e-maile, či je spam“);
2. P — miera výkonu: pravidlo, ktoré výsledku programu na úlohách z T priradí číslo, pričom väčšie číslo znamená lepší výkon (napr. podiel správne zaradených e-mailov);
3. E — skúsenosť: dáta alebo interakcie, ktoré program pri učení dostane (napr. e-maily, ktoré už niekto roztriedil).

Program sa učí zo skúsenosti E vzhľadom na triedu úloh T a mieru výkonu P práve vtedy, keď sa jeho výkon na úlohách z T, meraný pomocou P, zlepšuje so skúsenosťou E — t. j. program, ktorý spracoval viac skúsenosti z E, dosahuje na T (v priemere) vyššiu hodnotu P.

Je to pojmová definícia, nie matematická: T, P a E sa pre každú konkrétnu úlohu ešte len musia zvoliť. Formálny tvar pre učenie s učiteľom je v ďalšej časti.

Nech 𝒳 je neprázdna množina (priestor vstupov), 𝒴 neprázdna množina (priestor výstupov) a p ∈ ℕ, p ≥ 1. Model s parametrami θ ∈ ℝ^p je sústava funkcií

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

t. j. každá voľba vektora θ určuje jednu funkciu zo vstupov do výstupov.

Nech J : ℝ^p → ℝ je účelová funkcia vypočítaná z dát (čím menšie J(θ), tým lepšie model s parametrami θ dáta opisuje). Učenie (tréning) je hľadanie parametrov

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

Ak je J diferencovateľná, hľadá sa typicky gradientným zostupom: zvoľ počiatočné θ₀ ∈ ℝ^p a rýchlosť učenia η > 0 a pre t = 0, 1, 2, … polož

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

kým sa J citeľne zmenšuje (alebo do pevného počtu krokov). Gradientný zostup vo všeobecnosti nájde len lokálne minimum, nie nutne prvok argmin.

Nech 𝒳 je priestor vstupov, 𝒴 priestor štítkov (správnych odpovedí) a P neznáme rozdelenie pravdepodobnosti dvojíc (X, Y) na 𝒳 × 𝒴. Ďalej nech

1. n ∈ ℕ, n ≥ 1, a trénovacia množina D = ((x_i, y_i))_i=1ⁿ je postupnosť dvojíc (x_i, y_i) ∈ 𝒳 × 𝒴 vybraných z P navzájom nezávisle;
2. {f_θ : 𝒳 → 𝒴 : θ ∈ ℝ^p} je model (pozri definíciu vyššie);
3. L : 𝒴 × 𝒴 → [0, ∞) je stratová funkcia — L(ŷ, y) je trest za odpoveď ŷ, ak je správna odpoveď y.

Učenie s učiteľom je hľadanie parametrov, ktoré minimalizujú empirické riziko R̂ : ℝ^p → [0, ∞):

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

Cieľom však nie je trénovacia množina — model má mať malé skutočné riziko R(θ) = E_{(X, Y) ∼ P}[L(f_θ(X), Y)], t. j. dobre fungovať na nových dátach z toho istého rozdelenia (generalizácia). R nepoznáme, preto sa odhaduje priemernou stratou na odloženej testovacej množine, ktorá sa na učenie nepoužila.

Klasifikácia je učenie s učiteľom, v ktorom je priestor štítkov konečná množina tried 𝒴 = {1, …, K}, K ∈ ℕ, K ≥ 2. Model k vstupu x ∈ 𝒳 vracia odhad rozdelenia cez triedy, t. j. čísla p_θ(k | x) ≥ 0 pre k = 1, …, K s ∑_k=1^K p_θ(k | x) = 1.

Bežná strata je krížová entropia: pre x ∈ 𝒳 so štítkom y ∈ 𝒴

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

kde [y = k] je 1 práve vtedy, keď y = k, a inak 0.

Logistická regresia pre dve triedy 𝒴 = {0, 1}: nech 𝒳 = ℝ^d, parametre sú w ∈ ℝ^d a b ∈ ℝ a σ : ℝ → (0, 1) je logistická funkcia

σ(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 zaradí do triedy 1 práve vtedy, keď σ(w^⊤x + b) ≥ 0,5, t. j. práve vtedy, keď w^⊤x + b ≥ 0. Rozhodovacia hranica je množina

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

— pre w ≠ 0 nadrovina, v rovine (d = 2) priamka.

Derivácia priemernej krížovej entropie J podľa váh vyjde prekvapivo jednoducho (vďaka σ′ = σ(1 − σ) sa skráti):

∂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čiatočné hodnoty
opakuj E epoch:                       # epocha = jeden prechod všetkými dátami
    g_w, g_b ← 0, 0
    pre každý príklad (x, y):
        p ← σ(w·x + b)                # odhad pravdepodobnosti triedy 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
trieda(x) = 1, ak σ(w·x + b) ≥ 0,5, inak 0

Presnosť (accuracy) je podiel správne zaradených príkladov: |{i ∈ {1, …, n} : trieda(x_i) = y_i}|/n.

Štart: w = (0,4; 1,2), b = −0,9, rýchlosť učenia η = 2,5. Prvý bod má súradnice (0,604; 0,673) a triedu 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 teda bodu triedy 0 priradí triedu 1 s pravdepodobnosťou 0,537 — chyba. Strata (y = 0, takže zo vzorca krížovej entropie vyššie zostane len druhý sčítanec) je −ln(1 − 0,537) = 0,770 (farby podľa vzorca vyššie) a príspevok ku gradientu (p − y) x = 0,537 · (0,604; 0,673) ťahá obe váhy nadol.

Na celých dátach: presnosť na štarte 15 %, po 5 epochách 95 %, od 16. epochy 100 %. Priemerná krížová entropia (prirodzený logaritmus) klesne z 0,780 na 0,175 po 60 epochách; hoci sú už všetky body správne, model ďalej zväčšuje váhy, aby si bol istejší.

Regresia je učenie s učiteľom, v ktorom sú štítky reálne čísla: 𝒴 = ℝ. Nech (x_i, y_i) ∈ 𝒳 × ℝ, i = 1, …, n, sú trénovacie dvojice a f : 𝒳 → ℝ model. Bežná strata je stredná kvadratická chyba

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

Lineárna regresia s jedným vstupom: nech 𝒳 = ℝ, n ≥ 2 a x₁, …, x_n nie sú všetky rovnaké. Model je f(x) = ax + b s parametrami a, b ∈ ℝ. Označme priemery x̄ = 1/n ∑_i=1ⁿ x_i a ȳ = 1/n ∑_i=1ⁿ y_i. Potom MSE má jediné minimum (metóda najmenších štvorcov) v bode

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

(Predpoklad, že x_i nie sú všetky rovnaké, zaručuje nenulový menovateľ.)

MSE(a, b) je kvadratická funkcia dvoch premenných, takže minimum je tam, kde sú obe parciálne derivácie nulové:

∂/∂b: 2/n ∑ (ax_i + b − y_i) = 0  ⇒  b = ȳ − ax̄ (priamka prechádza ťažiskom dát),

∂/∂a: 2/n ∑ (ax_i + b − y_i) x_i = 0; po dosadení b vyjde vzorec pre a z definície vyššie.

Pre 24 bytov v grafe: a = 0,797, b = 0,083, MSE = 0,0046, teda typická zvislá odchýlka (čiarkované úsečky) √MSE ≈ 0,068. Dáta sme vyrobili ako y = 0,12 + 0,72 x + šum so smerodajnou odchýlkou 0,06 — metóda z 24 bodov trafila skutočný sklon aj šum zhruba, nie presne.

Nech 𝒳 je priestor vstupov, P_X neznáme rozdelenie na 𝒳 a D = (x_i)_i=1ⁿ, x_i ∈ 𝒳, vstupy vybrané z P_X navzájom nezávisle — bez štítkov. Učenie bez učiteľa hľadá z D štruktúru rozdelenia P_X. Typické úlohy:

1. zhlukovanie — rozklad indexov {1, …, n} na k neprázdnych, navzájom disjunktných množín C₁, …, C_k (zhlukov) tak, aby si body v jednom zhluku boli podobné;
2. zníženie dimenzie — pre 𝒳 = ℝ^d zobrazenie g : ℝ^d → ℝ^m, m < d, ktoré zachová čo najviac informácie o dátach;
3. odhad hustoty — funkcia p̂ : 𝒳 → [0, ∞), ktorá aproximuje hustotu p(x) rozdelenia P_X.

Čo presne je „podobné“ alebo „čo najviac informácie“, určí až konkrétna metóda svojou účelovou funkciou — ako k-means nižšie.

Nech x₁, …, x_n ∈ ℝ^d sú body, k ∈ ℕ, 1 ≤ k ≤ n, a ‖·‖ je euklidovská norma. Pre rozklad bodov do k navzájom disjunktných zhlukov C₁, …, C_k (každý bod patrí práve do jedného) a stredy μ₁, …, μ_k ∈ ℝ^d je vnútrozhlukový súčet štvorcov

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

Úloha k-means je nájsť zhluky a stredy, pre ktoré je J minimálne.

Lloydov algoritmus (približné riešenie). Vstup: body x₁, …, x_n ∈ ℝ^d, počet zhlukov k a počiatočné stredy μ₁, …, μ_k ∈ ℝ^d. Výstup: zhluky C₁, …, C_k a stredy μ₁, …, μ_k. Opakuj:

1. priradenie: každý bod x_i zaraď do zhluku C_j s j ∈ argmin_{j′ ∈ {1, …, k}} ‖x_i − μ_j′‖² (najbližší stred);
2. presun stredov: pre každé j = 1, …, k s C_j ≠ ∅ polož μ_j = 1/|C_j| ∑_{x ∈ Cj} x (priemer bodov zhluku).

Zastavenie: keď sa v kroku 2 žiadny stred nezmení. Žiadny krok J nezvýši a možných rozkladov je konečne veľa, takže algoritmus skončí — ale vo všeobecnosti len v lokálnom minime J.

μ₁, …, μ_k ← počiatočné stredy
opakuj:
    pre každý bod x:                     # krok 1: priradenie
        c(x) ← argmin_j ‖x − μ_j‖²
    pre každé j = 1, …, k:               # krok 2: presun stredov
        μ_j ← priemer bodov s c(x) = j
kým sa stredy hýbu

Prečo J nerastie. Krok 1 mení len priradenie a každý bod prejde k bližšiemu stredu, takže jeho sčítanec ‖x − μ_j‖² nerastie. Krok 2 mení len stredy a priemer je bod, ktorý minimalizuje súčet štvorcov vzdialeností ku skupine bodov (derivácia ∑ ‖x − μ‖² podľa μ je −2 ∑ (x − μ), nulová práve pre priemer). Možných priradení je konečne veľa, takže algoritmus skončí.

V našom grafe (66 bodov) má J v jednotlivých iteráciách hodnoty 19,330 → 2,937 → 1,048 → 0,655 — najväčší kus práce urobí hneď prvý presun stredov zo zlého štartu.

Nech 𝒳 je priestor vstupov, 𝒴 priestor štítkov, P neznáme rozdelenie na 𝒳 × 𝒴 a l, u ∈ ℕ, l ≥ 1. Sú dané

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. veľká neoznačená množina D_U = (x_j)_j=l+1^l+u, x_j ∈ 𝒳, vybraná nezávisle z rozdelenia samotných vstupov X (štítky y_j existujú, ale nepoznáme ich), kde u ≫ l.

Učenie s čiastočným učiteľom má rovnaký cieľ ako učenie s učiteľom — model f_θ : 𝒳 → 𝒴 s malým skutočným rizikom —, ale na jeho dosiahnutie využije D_L aj D_U.

Neoznačené dáta môžu pomôcť len vtedy, keď rozdelenie vstupov niečo hovorí o štítkoch. Používajú sa tieto predpoklady (každá metóda stojí aspoň na jednom z nich):

1. hladkosť — ak sú dva vstupy x, x′ ∈ 𝒳 blízko seba v oblasti, kde je veľa dát, majú (s veľkou pravdepodobnosťou) rovnaký štítok;
2. zhluky — vstupy z jedného zhluku majú (s veľkou pravdepodobnosťou) rovnaký štítok, takže hranica tried vedie miestami s malou hustotou dát;
3. varieta — dáta v 𝒳 = ℝ^d ležia blízko plochy (variety) dimenzie m < d a vzdialenosť bodov sa má merať po tejto ploche, nie priamou čiarou v ℝ^d.

Vstup: body x₁, …, x_N ∈ ℝ^d, z ktorých niektoré majú štítok zo 𝒴 = {0, 1}, a počet susedov k ∈ ℕ (tu k = 4). Výstup: štítok pre každý bod, do ktorého sa dá z označených bodov dôjsť po hranách grafu.

1. Zostroj neorientovaný graf: body x_i a x_j (i ≠ j) spoj hranou práve vtedy, keď x_j patrí medzi k najbližších susedov bodu x_i alebo x_i medzi k najbližších susedov bodu x_j (podľa euklidovskej vzdialenosti).
2. V jednom kole prejdi všetky neoznačené body; každý, ktorý má aspoň jedného označeného suseda, dostane štítok, ktorý má väčšina jeho označených susedov (pri rovnosti hlasov štítok 0). Štítky pridelené v kole platia až od ďalšieho kola.
3. Zastavenie: opakuj krok 2, kým sú neoznačené body a v poslednom kole pribudol aspoň jeden štítok.

Nech D = (x_i)_i=1ⁿ, x_i ∈ 𝒳, sú neoznačené dáta a nech g je pevne zvolené (prípadne náhodné) pravidlo, ktoré z každého vstupu x ∈ 𝒳 automaticky, bez ľudskej práce, vyrobí dvojicu

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

kde x̃ je časť alebo poškodená verzia vstupu x a t to, čo v x̃ chýba. Samoučenie je učenie s učiteľom na trénovacej množine (g(x_i))_i=1ⁿ: model dostane x̃ a má predpovedať t. Táto umelo vyrobená úloha sa volá predtextová úloha (pretext task).

Predpoveď ďalšieho tokenu — tak sa predtrénovávajú veľké jazykové modely. Nech V je konečný slovník tokenov a text je postupnosť x₁, …, x_T ∈ V, T ≥ 1. Model pre každé t = 1, …, T vracia rozdelenie p_θ(· | x₁, …, x_t−1) na V (pre t = 1 bez podmienky) a parametre θ sa volia tak, aby bol čo najväčší súčet

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

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

Markovov rozhodovací proces (prostredie) je pätica (S, A, P, R, γ), kde

1. S je neprázdna množina stavov (u nás konečná — políčka mriežky);
2. A je neprázdna konečná množina akcií;
3. P je pravdepodobnosť prechodu: pre každé s ∈ S a a ∈ A je P(· | s, a) rozdelenie pravdepodobnosti na S, t. j. P(s′ | s, a) ≥ 0 a ∑_{s′ ∈ S} P(s′ | s, a) = 1 (P(s′ | s, a) je pravdepodobnosť, že akcia a v stave s vedie do stavu s′);
4. R : S × A × S → ℝ je odmena za prechod z s akciou a do s′;
5. γ ∈ [0, 1) je diskontný faktor.

Stratégia agenta je pravidlo π, ktoré každému stavu s ∈ S priradí rozdelenie π(· | s) na A. Agent začne v stave s₀ a pre t = 0, 1, 2, … volí akciu a_t podľa π(· | s_t), prostredie vyberie ďalší stav s_t+1 podľa P(· | s_t, a_t) a agent dostane odmenu r_t = R(s_t, a_t, s_t+1). Návrat je

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

(v koncovom stave epizóda končí a ďalšie odmeny sú 0) a cieľom je nájsť stratégiu, ktorá maximalizuje jeho strednú hodnotu E[G].

Hodnota akcie Q(s, a) je očakávaný návrat, keď agent v stave s vykoná akciu a a ďalej hrá najlepšie. Q-learning ju odhaduje tabuľkou Q : S × A → ℝ (na začiatku napr. samé nuly): po každom kroku (s, a, r, s′) s rýchlosťou učenia α ∈ (0, 1] vykoná

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

pričom ak je s′ koncový stav, berie sa max_a′ Q(s′, a′) = 0.

Nech A je konečná neprázdna množina akcií, Q : S × A → ℝ tabuľka hodnôt akcií a ε ∈ [0, 1]. Pre stav s ∈ S zvoľme a*(s) ∈ argmax_{a ∈ A} Q(s, a) (pri rovnosti ľubovoľnú z najlepších). ε-hladná stratégia zvolí v stave s akciu a ∈ A s pravdepodobnosťou

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

kde [a = a*(s)] je 1 práve vtedy, keď a = a*(s), inak 0. Inými slovami: s pravdepodobnosťou ε zvolí akciu náhodne (rovnomerne zo všetkých), inak akciu s najväčším Q(s, a). U nás ε = 0,2.

Prvý krok. Na začiatku je celá tabuľka Q nulová. Agent urobí krok na obyčajné 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

(farby podľa vzorca Q-learningu vyššie). Krok do cieľa je koncový, takže člen max_a′ Q(s′, a′) je 0: Q ← 0 + 0,5 · [10 − 0] = 5. Pri ďalších návštevách sa päťka posunie k 10 a po ceste späť sa šíri ďalej, vždy vynásobená 0,95 a zmenšená o cenu kroku.

Hodnota štartu. Najkratšia cesta má 10 krokov: deväť obyčajných za −1 a posledný do cieľa 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á tabuľka má na štarte max_a Q(štart, a) = −1,093 — Q-learning tu hodnotu optimálnej cesty našiel presne.

Nech J_zdroj, J_cieľ : ℝ^p → ℝ sú účelové funkcie zdrojovej úlohy (obvykle s veľa dátami) a cieľovej úlohy (obvykle s málo dátami) pre model s rovnakými parametrami θ ∈ ℝ^p a nech θ₀ sú parametre naučené na zdrojovej úlohe, t. j. (približne) θ₀ ∈ argmin_θ J_zdroj(θ). Prenos učenia hľadá

θ* ∈ argmin_θ J_cieľ(θ)

gradientným zostupom, ktorý začne v θ₀ (namiesto náhodných hodnôt). Pri doladení (fine-tuning) sa často menia len parametre s indexmi z malej množiny I ⊂ {1, …, p}; ostatné zostanú rovné hodnotám v θ₀.

Nech D_L je označená a D_U neoznačená množina (ako pri učení s čiastočným učiteľom), 𝒴 = {1, …, K} a model p_θ(· | x) natrénovaný na D_L. Aktívne učenie opakuje tieto kroky:

1. model sám vyberie vstup x* ∈ D_U, o ktorom si je najmenej istý — napríklad s najvyššou entropiou: x* ∈ argmax_{x ∈ DU} H(p_θ(· | x));
2. človek (učiteľ) mu doplní štítok y*; dvojica (x*, y*) sa presunie z D_U do D_L;
3. model sa znovu natrénuje na D_L;

kým sa neminie rozpočet na označovanie.

Nech p je rozdelenie na {1, …, K}, t. j. p(k) ≥ 0 a ∑_k=1^K p(k) = 1. Jeho entropia (v bitoch) je

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

Pre dve triedy: odhad 50 : 50 má H = −2 · 0,5 · log₂ 0,5 = 1 bit (najviac 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 len 0,081 bitu. Na označenie pôjde ako prvý príklad, pri ktorom model váha 50 : 50.

Nech 𝒳 je priestor vstupov a 𝒴 priestor štítkov.

1. Diskriminatívny model sa učí priamo podmienené rozdelenie p_θ(y | x) pre x ∈ 𝒳, y ∈ 𝒴, alebo rovno rozhodovaciu funkciu f_θ : 𝒳 → 𝒴 (a teda rozhodovaciu hranicu). O tom, ako sú rozdelené samotné vstupy x, nič nehovorí.
2. Generatívny model sa učí rozdelenie dát p_θ(x) na 𝒳, prípadne združené rozdelenie p_θ(x, y) na 𝒳 × 𝒴, a vie z neho vzorkovať nové dáta. Zo združeného rozdelenia sa dá dopočítať aj podmienené (pre konečné 𝒴): p_θ(y | x) = p_θ(x, y)/∑_{y′ ∈ 𝒴} p_θ(x, y′).