Strojové učení

Note	Strojové učení a rozpoznávání vzorů: problém klasifikace a regrese, shluková analýza, učení s učitelem a bez učitele. Vícevrstvé neuronové sítě, vícevrstvé perceptrony, ztrátové funkce, zpětná propagace. ~~Hopfieldova síť,~~ konvoluční sítě, rekurentní sítě~~, samo-organizující mapy~~. PV021

Tip	Velkou část zpracování téhle otázky jsem ukradl sám sobě.

Strojové učení a rozpoznávání vzorů

Machine learning / strojové učení

Oblast informatiky zabývající se konstrukcí systémů, které nemají svoji funkcionalitu explicitně naprogramovanou, ale naučí se ji až na základě vstupních dat. [2] [1]

Používá se např. pro:

filtrování spamu v emailech,
rozpoznávání řeči, rukopisu, tváří, zvuků, atd.,
klasifikaci textů,
herní strategie,
analýzu trhu,
autonomní řízení vozidel.

Rozpoznávání vzorů / pattern recognition

Problém automatizovaného rozpoznávání vzorů v datech (např. číslic v obrázku). Příklady jsou klasifikace, regrese a shluková analýza. [6]

Klasifikace

Problém identifikace kategorie, do které patří vstupní data. Výstupem klasifikace je buď jedna konkrétní kategorie nebo vektor popisující s jakou pravděpodobností vstup do každé kategorie patří. [3]

Regrese

Problém odhadu hodnoty nějaké proměnné na základě znalosti jiných proměnných. Výstupem regrese je obvykle reálné číslo. [4]

Například při lineární regresi se snažíme data napasovat na přímku — najít její offset a směrnici. Při logistické regresi chceme to samé ale místo přímky máme logistic sigmoid. A tak dále. [1]

Shluková analýza / cluster analysis

Vicedimenzionální problém rozdělení vstupních dat do skupin (shluků) tak, aby data v jednom shluku byla podobnější sobě než datům v jiných shlucích. [5]

Souvisejícím problémem je vyjádření toho, že jsou si data v nějakém smyslu podobná.

Supervised learning / učení s učitelem

Síť se učí na základě množiny trénovacích vstupů ve formátu (vstup, výstup). Supervised learning algoritmy se snaží síť modifikovat tak, aby vracela výstupy co možná nejpodobnější těm trénovacím. [1]

Unsupervised learning / učení bez učitele

Síť dostává jen vstupy. Cílem je získat o vstupní množině dat nějakou užitečnou informaci, třeba kde jsou shluky. [1]

Neuronové sítě

Neural network / neuronová síť

Neuronová síť je množina propojených neuronů, jejíž chování je zakódováno do spojení mezi neurony. Je primitivním modelem biologických neuronových sítí.

Typ neuronové sítě je dán její architekturou (způsobem zapojení), aktivitou (transformací vstupů na výstupy) a učením (metodou změny vah při trénování).

Architektura

Neuron může být input, output nebo hidden. Může být dokonce input i output najednou. Hidden je, právě když není input ani output.

Síť být cyklická — recurrent — nebo acyklická — feed-forward.

Stav sítě

Vektor výstupů všech neuronů sítě (nejen output).

Stavový prostor sítě

Množina všech možných stavů sítě.

Vstup sítě

Vektor reálných čísel (prvek $R^{n}$ ), kde $n$ je počet vstupů.

Vstupní prostor sítě

Množina všech vstupů sítě.

Iniciální stav

Input neuronům je za výstup ( $y$ ) dán vektor vstupů ( $x$ ). Všem ostatním neuronům je výstup ( $y$ ) nastaven na 0.

Výstup sítě

Vektor výstupů ( $y$ ) output neuronů. Výstup se v průběhu výpočtu může měnit.

Výpočet

Typicky po diskrétních krocích:

Zvolí se množina neuronů (vybrané podle pravidla daného architekturou).
Zvoleným neuronům je nastaven výstup — prostě se vyhodnotí aktivační funkce.
Vrať se ke kroku 1.

Výpočet je konečný, pokud se stav sítě dále nemění po konečném množství opakování postupu výše.

Konfigurace

Vektor hodnot všech vah.

Vahový prostor

Množina všech konfigurací.

Iniciální konfigurace

Počáteční hodnoty vah (než začne trénování).

Multilayer perceptron (MLP) / vícevrstvé neuronové sítě

Perceptron — jeden neuron

Hrubá matematická aproximace biologického neuronu.
Binární klasifikátor — rozlišuje jestli vstup patří nebo nepatří do nějaké jedné kategorie.[1]
Linerání klasifikátor — jeho funkce kombinuje vstupy lineárně.

$x_{i}$ — inputy
$w_{i}$ — váhy
$ξ = w_{0} + \sum_{i = 1}^{n} w_{i} x_{i}$ — vnitřní potenciál
$y$ — výstup
$y = σ (ξ)$ — aktivační funkce udávající výstup
bias — udává "jak těžké" je pro neuron se aktivovat (čím vyšší číslo, tím těžší je pro neuron vydat nenulový výstup)
$x_{0}$ — pro snažší implementaci se závádí dodatečný vstup, který má vždy hodnotu 1 a váhu rovnu -bias

Note	Vnitřní potenciál funguje jako nadrovina (čára při 2D, rovina při 3D, nepředstavitelný mostrum ve vyšších dimenzí), která rozděluje prostor vstupů na část, kde je $ξ < 0$ a kde $ξ > 0$ .

Multilayer perceptron (MLP)

MLP je feed-forward (neobsahuje cykly) architektura NN, kde platí:

Neurony rozděleny do vrstev — jedné vstupní, jedné výstupní a libovolného počtu skrytých vrstev uprostřed.
Vrstvy jsou dense — každý neuron v $i$ -té vrstvě je napojen na každý neuron v $(i + 1)$ -ní vrstvě.

Kde:

$X$ — množina input neuronů
$Y$ — množina output neuronů
$Z$ — množina všech neuronů
Neurony mají indexy $i$ , $j$ , …
$ξ_{j}$ — vnitřní potenciál neuronu $j$ po skončení výpočtu
$y_{j}$ — výstup neuronu $j$ po skončení výpočtu
$x_{0} = 1$ — hodnota formálního jednotkového vstupu (kvůli biasům)
$w_{j, i}$ — váha spojení z neuronu $i$ do neuronu $j$ (dst ← src)
$w_{j, 0} = - b_{j}$ — bias — váha z formální jednotky do neuronu $j$
$j_{\leftarrow}$ — množina neuronů $i$ , jenž mají spojení do $j$ (j ← i)
$j^{\to}$ — množina neuronů $i$ , do nichž vede spojení z $j$ (j → i)

Aktivita

Pravidlo pro výběr neuronů při výpočtu: V i-tému kroku vezmi i-tou vrstvu.
Vnitřní potenciál neuronu $j$: $ξ_{j} = \sum_{i \in j_{\leftarrow}} w_{ji} y_{i}$
Aktivační funkce neuronu $j$: $σ_{j} : R \to R$ (třeba logistic sigmoid)
Stav nevstupního neuronu $j$: $y_{j} = σ_{j} (ξ_{j})$ resp. $y_{j} (w, x)$
Logistic sigmoid: Většina aktivačních funkcí vychází s funkce sigmoid. (Jsou sigmoidní, vypadají trochu jako písmeno S). Přidávají do výpočtu nelinearitu, která je potřeba, aby NN mohla modelovat libovolné funkce. Zároveň je podobná klasickému thresholdu, ale je "vyhlazená".

$σ (ξ) = \frac{1}{1 + e ^{- λ \cdot ξ}}$

kde $λ$ je steepness parametr, který určuje, jak rychle sigmoid roste.

Trénink

Important

Pro likelihood viz otázka Statistika.

Neuronka je model, kde váhy neuronů jsou parametry. Při učení neuronek je naším cílem maximalizovat likelihood, jakožto míru toho, že naše síť sedí na "naměřená data", training set $T$ . Tomuhle přístupu se říká maximum likelihood principle.

Training set $T$

je množina $p$ samplů, kde $x \in R^{∣ X ∣}$ jsou vstupní vektory a $d \in R^{∣ Y ∣}$ jejich očekáváné výstupy.

T = {(x_{1}, d_{1}), (x_{2}, d_{2}), ..., (x_{p}, d_{p})}

Ztrátové funkce / loss function / error function

Popisuje způsob, jakým je při tréninku výstup z NN porovnán s očekáváným výstupem.

Její volba závisí na tom, co NN modeluje. Např. volíme:

mean squared error (MSE) — pro regresi,

$E_{k} (w) E (w) = \frac{1}{2} j \in Y \sum (y_{j} (w, x_{k}) - d_{kj})^{2} = \frac{1}{p} k = 1 \sum p E_{k} (w)$
(categorical) cross-entropy — pro (multi-class) klasifikaci.

$E (w) = - \frac{1}{p} k = 1 \sum p j \in Y \sum d_{kj} ln (y_{j})$

Gradient descent

Algoritmus počítající, jak se mají vahy neuronů upravit, aby se zmenšila ztráta. Vychází z gradientu ztrátové funkce.

Δ w^{(t)} = - ε (t) \cdot \nabla E (w^{(t)})

Stochastic Gradient Descent (SGD)

Sample nebereš po jednom ale po malých randomizovaných várkách — minibatchích $T$ , a váhy upravuješ až po zpracování minibatche.

Δ w^{(t)} = - ε (t) \cdot k \in T \sum \nabla E_{k} (w^{(t)})

Backpropagation / zpětná propagace

Technika, kdy se v průběhu gradient descent ztráta způsobená konkrétním neuronem dedukuje na zákládě jeho příspěvku k výsledku. Algoritmus tak postupuje od output vrstvy směrem k input vrstvě.

Learning rate $ε$

Hyperparametr $0 < ε \leq 1$ ovlivňující rychlost učení. Může záviset na iteraci $t$ , pak je to funkce $ε (t)$ .

Příklad 1. Gradient descent v MLP

w_{ji}^{(t + 1)} Δ w_{ji}^{(t)} \frac{\partial E}{\partial w _{ji}} \frac{\partial E _{k}}{\partial w _{ji}} = w_{ji}^{(t)} + Δ w_{ji}^{(t)} = - ε (t) \cdot \frac{\partial E}{\partial w _{ji}} (w^{(t)}) = k = 1 \sum p \frac{\partial E _{k}}{\partial w _{ji}} = \frac{\partial E _{k}}{\partial y _{j}} \cdot \frac{\partial y _{j}}{\partial ξ _{j}} \cdot \frac{\partial ξ _{j}}{\partial w _{ji}} = \frac{\partial E _{k}}{\partial y _{j}} \cdot σ_{j}^{'} (ξ_{j}) \cdot y_{i}

Za předpokladu, že $E$ je squared error, pak:

Warning

V případě, že

E

není squared error, následující výpočet neplatí.

\frac{\partial E _{k}}{\partial y _{j}} = ⎩ ⎨ ⎧ y_{j} - d_{kj} \sum_{r \in j^{\to}} \frac{\partial E _{k}}{\partial y _{r}} \cdot \frac{\partial y _{r}}{\partial ξ _{r}} \cdot \frac{\partial ξ _{r}}{\partial y _{j}} = \sum_{r \in j^{\to}} \frac{\partial E _{k}}{\partial y _{r}} \cdot σ_{r}^{'} (ξ_{r}) \cdot w_{r j} pokud j \in Y; jinak .

Algoritmus pro výpočet

\frac{\partial E}{\partial w _{ji}}

Inicializuj $ε_{ji} := 0$ .
forward pass — vyhodnoť NN pro sample $k$ (t.j. $y_{j} (w, x_{k})$ pro všechny $j \in Z$ )
backward pass — od konce pro každou vrstvu spočítej $\frac{\partial E _{k}}{\partial y _{j}}$
1. pokud $j \in Y$ , pak $\frac{\partial E _{k}}{\partial y _{j}} = y_{j} - d_{kj}$
2. pokud $j \in Z ∖ Y \cup X$ , a $j$ je v $l$ -té vrstvě, pak $\frac{\partial E _{k}}{\partial y _{j}} = \sum_{r \in j^{\to}} \frac{\partial E _{k}}{\partial y _{r}} \cdot σ_{r}^{'} (ξ_{r}) \cdot w_{r j}$
weight update — pro všechna $w_{ji}$ spočítej $\frac{\partial E _{k}}{\partial w _{ji}} := \frac{\partial E _{k}}{\partial y _{j}} \cdot σ_{j}^{'} (ξ_{j}) \cdot y_{i}$
$ε_{ji} := ε_{ji} + \frac{\partial E _{k}}{\partial w _{ji}}$
$ε_{ji}$ obsahuje výslednou hodnotu $\frac{\partial E}{\partial w _{ji}}$

Konvoluční sítě

Neuronové sítě uzpůsobené ke zpracování obrazu. Místo násobení matic používají alespoň v jedné vrstvě konvoluci. Konvoluční sítě mají dva nové typy vrstev: konvoluční a pooling, ale jinak se od klasických MLP moc neliší. Aktivace a trénink zůstavají v podstatě stejné. [9]

Important

Pro konvoluci viz otázka Zpracování rastrového obrazu.

Obrázek 1. Typical CNN by Aphex34

Konvoluční vrstva

Každý neuron je napojen jen na malý receptive field neuronů o vrstvu níže, který se posouvá o daný stride.
Výstup z neuronu v konvoluční vrstvě je dán konvolucí jeho receptive field s váhami a přičtením biasu.
Všechny neurony v konvoluční vrstvě sdílí stejné váhy a biasy dané velikostí receptive field, což jim umožňuje naučit se nějaký vzor o velikosti receptive field — říkáme, že taková vrstva je feature mapa.
Vzorů se chceme zpravidla naučit více, máme vícero vzájemně nezávislých feature map napojených na stejnou vstupní vrstvu.

Pooling vrstva

Nemají váhy. Slouží ke snížení počtu parametrů. Každý neuron počítá nějakou jednoduchou funkci na svém receptive field:

max-pooling: maximum,
L2-pooling: square root of sum of squares,
average-pooling: mean.

Backpropagation

Algoritmus je potřeba trochu poupravit, aby podporovat konvoluční a pooling vrstvy.

U konvolučních vrstev nestačí pro každou váhu $w_{ji}$ spočítat $\frac{\partial E _{k}}{\partial w _{ji}}$ , protože pro každou váhu existuje víc než jeden výstup $y_{j}$ . Tedy:

\frac{\partial E _{k}}{\partial w _{ji}} = r l \in [ji] \sum \frac{\partial E _{k}}{\partial y _{r}} \cdot σ_{r}^{'} (ξ_{r}) \cdot y_{l}

kde $[ji]$ je množina spojení (dvojic neuronů) sdílících váhu $w_{ji}$ .

Pokud $j \in Z ∖ Y$ a $j^{\to}$ je max-pooling, pak $j^{\to} = {i}$ a platí:

\frac{\partial E _{k}}{\partial y _{j}} = {\frac{\partial E _{k}}{\partial y _{i}} 0 pokud j = arg max_{r \in i_{\leftarrow}} y_{r} jinak

Rekurentní sítě

Neuronové sítě, jejichž architektura obsahuje cykly. Tedy výstup v jednom bodě v čase sítě přispívá k výstup v budoucnosti. Jinými slovy, je to neuronka s pamětí. Recurrent neural networks (RNN) konkrétně jsou MLP minimálně rozšířené tak, aby měly paměť. [10]

Important

Výhody

Umí zpracovat vstupy s variabilní, předem neznámou délkou.
Velikost modelu (množiny vah) je fixní nezávisle na velikosti vstupu.
Váhy se sdílí mezi vstupy (např. slova ve větě), což umožňuje naučit se nějaký kontext.

Warning

Nevýhody

Trénování je složitější, protože se vyskytuje zpětná vazba.
Výpočetně náročnější.
Gradient může explodovat (exploding) nebo zaniknout (diminishing).

Notace

V čase $t$ :

$x_{t} = (x_{t, 1}, x_{t, 2}, ..., x_{t, M})$ je vstupní vektor předávaný $M$ vstupním neuronům,
$h_{t} = (h_{t, 1}, h_{t, 2}, ..., h_{t, H})$ je vektor hodnot $H$ skrytých neuronů,
$y_{t} = (y_{t, 1}, y_{t, 2}, ..., y_{y, N})$ je výstupní vektor $N$ neuronů,
$U_{j, i}$ je váha mezi inputem $i$ a hiddenem $j$ ,
$W_{j^{'}, i^{'}}$ je váha mezi hiddenem $i^{'}$ a hiddenem $j^{'}$ ,
$V_{j^{''}, i^{''}}$ je váha mezi hiddenem $i^{''}$ a outputem $j^{''}$ .

Aktivita

Na počátku je výstup neuronky vynulován. Paměť je tedy prázdná.
RNN zpracovává sekvenci vstupů $x = x_{1}, x_{2}, ..., x_{T}$ délky $T$ .
Pro každý prvek $x_{t} \in x$ , síť vyprodukuje výstup z hidden neuronů:

$h_{t} = σ (U \cdot x_{t} + W \cdot h_{t - 1})$
Pro výstup pak:

$y_{t} = σ (V \cdot h_{t})$

Trénink

Trénovací set je množina dvojic — (vstupní sekvence, výstupní sekvence).

T = {(x_{1}, d_{1}), ..., (x_{p}, d_{p})}

Note	Ano, to znamená, že $x_{lt 1}$ je první prvek $t$ -ho prvku v $l$ -té vstupní sekvenci.

Squared error samplu $(x, d)$ :

E_{(x, d)} = t = 1 \sum T k = 1 \sum N \frac{1}{2} (y_{t k} - d_{t k})^{2}

Gradient descent je podobný. Na začátku jsou všechny váhy inicalizovány poblíž 0 a pak iterativně přepočítávány:

U_{k k^{'}}^{(l + 1)} V_{k k^{'}}^{(l + 1)} W_{k k^{'}}^{(l + 1)} \frac{\partial E _{(x, d)}}{\partial U _{k k^{'}}} \frac{\partial E _{(x, d)}}{\partial V _{k k^{'}}} \frac{\partial E _{(x, d)}}{\partial W _{k k^{'}}} = U_{k k^{'}}^{(l)} - ε (l) \cdot \frac{\partial E _{(x, d)}}{\partial U _{k k^{'}}} = V_{k k^{'}}^{(l)} - ε (l) \cdot \frac{\partial E _{(x, d)}}{\partial V _{k k^{'}}} = W_{k k^{'}}^{(l)} - ε (l) \cdot \frac{\partial E _{(x, d)}}{\partial W _{k k^{'}}} = t = 1 \sum T \frac{\partial E _{(x, d)}}{\partial h _{t k}} \cdot σ^{'} \cdot x_{t k^{'}} = t = 1 \sum T \frac{\partial E _{(x, d)}}{\partial y _{t k}} \cdot σ^{'} \cdot h_{t k^{'}} = t = 1 \sum T \frac{\partial E _{(x, d)}}{\partial h _{t k}} \cdot σ^{'} \cdot h_{(t - 1) k^{'}}

Za předpokladu squared error je backpropagation:

\frac{\partial E _{(x, d)}}{\partial y _{t k}} \frac{\partial E _{(x, d)}}{\partial h _{t k}} = y_{t k} - d_{t k} = k^{'} = 1 \sum N \frac{\partial E _{(x, d)}}{\partial y _{t k^{'}}} \cdot σ^{'} \cdot V_{k^{'} k} + k^{'} = 1 \sum H \frac{\partial E _{(x, d)}}{\partial h _{(t + 1) k^{'}}} \cdot σ^{'} \cdot W_{k^{'} k}

Tip	Pokud $σ^{'} \cdot W_{k^{'} k} \neq \approx 1$ , pak gradient buď vybouchne nebo se ztratí.

Long Short-Term Memory (LSTM): LSTM řeší problém s vanishing a exploding gradientem, kterým RNN. V RNN je $σ$ typicky $tanh$ . V LSTM obsahuje jeden hidden neuron vlastně čtyři "podvrstvy", které mimo jiné umožňují část paměti zapomenout:

Zdroje

[1] T. Brázdil: PV021 Neural Networks
[2] Wikipedia: Machine learning
[3] Wikipedia: Statistical classification
[4] Wikipedia: Regression analysis
[5] Wikipedia: Cluster analysis
[6] Wikipedia: Pattern recognition
[7] Wikipedia: Hopfield network
[8] Wikipedia: Hebbian theory
[9] Wikipedia: Convolutional neural network
[10] Wikipedia: Recurrent neural network
[11] Wikipedia: Self-organizing map
[12] Self-Organizing Maps: Tutorial
[13] SDL Component Suite: Kohonen Network