Pozn. k dotazu na vlastnosti klasifikátorů a s nimi spojených metod učení. Vyjádřete se: 1. k typu úlohy, pro který je metoda vhodná (např. 2 třídy, menší počet tříd, velmi vysoký počet tříd), množství dat, které je typicky potřeba (schopnost generalizace), k předpokládaným vlastnostem dat, 2. k vlastnostem algoritmu učení (vztah mezi kritériem použitím při učení a jeho vztahem ke kritériu, typicky chybě na testovacích datech), k době učení, konvergenci algoritmu (do lokálního nebo globálního minima) a 3. k vlastnostem z pohledu nasazení (při rozhodování) - paměťová a výpočetní náročnost.
Bayesovská formulace statistického rozhodování (rozpoznávání). Popis řešení úlohy při znalosti statistického modelu pro ztrátovou funkci 0 (za správné rozhodnutí), 1 (při jakékoli chybě). Rozhodování s možností “nevím”.
Nechť:
Kvalitu strategie $q$ lze měřit různými způsoby, nejběžnější z nich je očekávaná (průměrná) ztráta (loss) označovaná jako riziko $R(q)$:
$$ R(q) = \sum_{x \in X} \sum_{k \in K} p_{XK}(x, k)W\bigl(k,\,q(x)\bigr)\,. $$
$$ p_{XK}(x,k) = p_{XK}(x | k)p_K(k) $$
Nechť jsou dány množiny $X$, $K$ a $D$, spojitá pravděpodobnost
$$
p_{XK}: X \times K \longrightarrow \mathbb{R}
$$ a penalizační funkce
$$
W: K \times D \longrightarrow \mathbb{R}.
$$ Pro strategii
$$
q: X \longrightarrow D
$$ je očekávání $W(k, q(x))$ definováno jako:
$$ R(q) =\sum_{x \in X}\ \sum_{k \in K} p_{XK}(x,k)W\bigl(k,\,q(x)\bigr)\,. $$
Kvantita $R(q)$ se nazývá Bayesovské riziko. Naším úkolem je nalézt takovou strategii $q^*$, která minimalizuje Bayesovské riziko:
$$ q^* = \underset{q : X \to D}{\arg\min} R(q)\,, $$
kde minimum je bráno přes všechny možné strategie $q : X \to D$. Stratetegie, která toto minimum dosahuje, se nazývá Bayesovská strategie.
Risk se dá převést na Partial risk: $$ R(x,d) = \sum_{k \in K}p_{Kx}(k|x)W(k,d) $$ Díky partial risku se se dá optimální strategie najít $$ q^*(x) = \underset{d \in D}{\arg\min} \sum_{k \in K}p_{Kx}(k|x)W(k,d) $$
Rozhodnutí $D$ = skryté stavy $K$:
$$ W(k, q(x)) = \begin{cases} 0, & \text{pokud } q(x) = k,\\ 1, & \text{pokud } q(x) \neq k. \end{cases} $$
Částečné riziko je poté dáno jako:
$$ R(x, d) \;=\; \sum_{k \in K} p_{KX}(k \mid x)\;W(k, d) \;=\; \sum_{k \neq d} p_{KX}(k \mid x) \;=\; 1 - p_{KX}(d \mid x). $$
Optimální strategie je následně:
$$ q^*(x) \;=\; \underset{d \in D}{\arg\min}\;R(x, d) \;=\; \underset{d \in D}{\arg\max}\;p_{KX}(d \mid x). $$
$$ W(k,d)= \begin{cases} 0, & \text{jestliže } d=k,\\[4pt] 1, & \text{jestliže } d\neq k \text{ a } d\neq \text{not known},\\[4pt] \varepsilon, & \text{jestliže } d=\text{not known}. \end{cases} $$
Potom se optimální strategie minimalizuje jako
$$ q^{*}(x)= \begin{cases} \displaystyle \arg\min_{d\in K} R(x,d), & \text{pokud } \displaystyle\min_{d\in K} R(x,d) < R\bigl(x,\text{not known}\bigr),\\[8pt] \text{not known}, & \text{jinak}. \end{cases} $$
$$ \begin{aligned} \min_{d\in K} R(x,d) &= \min_{d\in K} \sum_{k\in K} p_{K|X}(k\,|\,x)\,W(k,d) \\[4pt] &= \min_{d\in K} \sum_{k\in K\setminus\{d\}} p_{K|X}(k\,|\,x) \\[4pt] &= \min_{d\in K} \Bigl(1 - p_{K|X}(d\,|\,x)\Bigr) \\[4pt] &= 1-\max_{d\in K} p_{K|X}(d\,|\,x). \end{aligned} $$
$$ \begin{aligned} R\bigl(x,\text{not known}\bigr) &= \sum_{k\in K} p_{K|X}(k\,|\,x)\,W\bigl(k,\text{not known}\bigr) \\[4pt] &= \sum_{k\in K} p_{K|X}(k\,|\,x)\,\varepsilon = \varepsilon. \end{aligned} $$
Proto platí
$$ q^{*}(x)= \begin{cases} \displaystyle \arg\max_{k\in K} p_{K|X}(k\,|\,x), & \text{jestliže } 1-\max_{k\in K} p_{K|X}(k\,|\,x) < \varepsilon,\\[8pt] \text{not known}, & \text{jestliže } 1-\max_{k\in K} p_{K|X}(k\,|\,x) \ge \varepsilon. \end{cases} $$
$\varepsilon$ (epsilon) je penalizace za odpověď „nevím“ (často také „reject option“).
* $\varepsilon\in(0,1)$ — typicky malá hodnota.
* Když je $\varepsilon$ blízké 0, systém raději řekne „nevím“ než riskovat chybu.
* Když je $\varepsilon$ blízké 1, „nevím“ se téměř nevyplatí a pravidlo se blíží běžné volbě nejpravděpodobnější třídy.
– 0 za správně, 1 za špatně, $\varepsilon$ za „nevím“.
$$ \max_{k} p_{K|X}(k\,|\,x) > 1-\varepsilon; $$ jinak bezpečně odpověz „nevím“.
Logistická regrese. Formulace úlohy. Algoritmus učení. Vlastnosti (výhody a nevýhody).
Logistická regrese slouží ke binární klasifikaci, kde se rozhodujeme mezi dvěma třídami (např. spam/ne-spam). Cílem je nalézt lineární kombinaci vstupních proměnných $x$, která maximalizuje pravděpodobnost správného přiřazení třídy. Výstup predikce je pravděpodobnost patření do třídy $1$, získaná pomocí logistické sigmoidy:
$$ \sigma(z) = \frac{1}{1 + e^{-z}} $$
Výhody: - Jednoduchý a rychlý algoritmus. - Interpretace koeficientů $w$ jako vliv vstupních proměnných. - Dobře funguje pro lineárně separovatelná data.
Nevýhody: - Předpokládá lineární separaci tříd. - Není robustní vůči outlierům. - Nespracuje chybějící hodnoty v datech.
Softmax je zobecněním logistické regrese na vícetřídnou klasifikaci. Výstupní pravděpodobnosti pro $K$ tříd jsou získány jako: $$ P(y = k | x) = \frac{e^{w_k^T x + b_k}}{\sum_{j=1}^K e^{w_j^T x + b_j}} $$ Toto zajišťuje, že výstupy tvoří distribuci pravděpodobností (všechny hodnoty mezi 0 a 1, součet 1).
Diagnóza choroby na základě biomarkerů $x$: - Vstup: $x = [\text{teplota, bílkoviny}]$. - Model určí $P(\text{choroba} = 1 | x)$.
Sigmoida:
Softmax pro 3 třídy:
Logistická regrese je základním nástrojem pro klasifikaci, který lze rozšířit pomocí softmaxu na více tříd. Funkce sigmoidy a softmaxu zajistí interpretaci výstupů jako pravděpodobnosti, což je klíčové pro mnoho aplikací v ML.
Klasifikátor hledající optimální hranici mezi třídami s maximální mezí. Používá se pro binární klasifikaci, regresi a detekci odlehlých hodnot. Efektivní i ve vysokodimenzionálních prostorech.
Hard Margin:
$$ \min_{\mathbf{w},b} \frac{1}{2} \|\mathbf{w}\|^2 \quad \text{za podmínek} \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 \quad \forall i $$
Soft Margin:
$$ \min_{\mathbf{w},b,\xi} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i \quad \text{za podmínek} \quad y_i(\mathbf{w}^T\mathbf{x}_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0 $$
| Vlastnost | Výhody | Nevýhody |
|---|---|---|
| Přesnost | Vysoká díky maximalizaci okraje. | Citlivost na volbu hyperparametrů ($C$, $\gamma$). |
| Efektivita | Rychlé předpovědi (pouze support vectors). | Pomalé učení pro velké datasety. |
| Kernely | Univerzálnost (lineární, polynomiální, RBF). | Nutnost křížové validace pro výběr jádra. |
| Nelinearita | Zpracuje složité nelineární hranice. | Interpretovatelnost modelu klesá. |
| Odolnost proti přetrénování | Dobrá pro vysokodimenzionální data. | Vyžaduje normalizaci vstupů. |
Adaboost, popis algoritmu, jeho interpretace jako minimalizace horního odhadu empirického rizika. Vlastnosti (výhody a nevýhody).
Adaboost (Adaptive Boosting) je algoritmus ensemble learningu, který kombinuje slabé klasifikátory do silného klasifikátoru. Minimalizuje horní odhad empirického rizika a iterativně upravuje váhy chybně klasifikovaných vzorků.
Empirické riziko je horní odhad chyby:
$$ \mathcal{E}(H) \leq \prod_{t=1}^T Z_t \quad \text{kde} \quad Z_t = 2\sqrt{\epsilon_t(1-\epsilon_t)} $$
Algoritmus v každé iteraci volí $h_t$ a $\alpha_t$ minimalizující $Z_t$, čímž exponenciálně snižuje chybu. [5]
Výhody:
- Jednoduchá implementace
- Odolnost proti přetrénování
- Univerzálnost (kombinuje libovolné klasifikátory)
Nevýhody:
- Citlivý na šum a odlehlé hodnoty
- Vyžaduje pečlivé nastavení parametrů
- Problémy s nevyváženými třídami
Binární klasifikace s rozhodovacími stromy:
- Data: $\{(x_1=1, y_1=1), (x_2=2, y_2=-1), (x_3=3, y_3=1)\}$
- Iterace 1: $h_1(x)$ chybuje u $x_2$ → $\epsilon_1=0.33$, $\alpha_1=0.55$
- Iterace 2: $h_2(x)$ opravuje chybu u $x_2$ s vyšší vahou
- Výsledek: $H(x) = 0.55h_1(x) + 0.8h_2(x)$
Princip zesilování slabých klasifikátorů z něj činí efektivní nástroj pro různé klasifikační úlohy.
Neuronové sítě s dopředným šířením. Struktura. Učení pomocí metody zpětného šíření. Vlastnosti (výhody a nevýhody).
Neuronové sítě s dopředným šířením jsou vícevrstvé architektury inspirované biologickými neurony, které transformují vstupy na výstupy pomocí vážených spojení a nelineárních aktivačních funkcí. Učí se metodou zpětného šíření chyby.
Operace aplikuje filtr (jádro) na vstupní matici pro extrakci lokálních vzorů. Příklad pro vstup $X$ a jádro $K$: $$ X = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}, \quad K = \begin{pmatrix} 0 & -1 \\ 1 & 0 \end{pmatrix} $$ Výstup pro pozici (1,1): $$ (1 \cdot 0) + (2 \cdot -1) + (4 \cdot 1) + (5 \cdot 0) = -2 + 4 = 2 $$
Snižuje prostorové rozměry, zachovává dominantní rysy. MaxPooling vybírá maximální hodnotu v okně. Příklad pro okno 2×2: $$ \text{Vstup: } \begin{pmatrix} 5 & 8 & 2 \\ 3 & 1 & 4 \\ 6 & 7 & 9 \end{pmatrix} \quad \text{Výstup: } \begin{pmatrix} \max(5,8,3,1) & \max(2,4) \\ \max(6,7) & \max(9) \end{pmatrix} = \begin{pmatrix} 8 & 4 \\ 7 & 9 \end{pmatrix} $$
Převede výstupní vektor na pravděpodobnostní distribuci: $$ \text{softmax}(z_i) = \frac{e^{z_i}}{\sum_{j=1}^K e^{z_j}} $$ Používá se ve výstupní vrstvě pro klasifikační úlohy (např. rozpoznání digitů v MNIST).
Pokud by všechny vrstvy používaly pouze lineární funkce ($g(z) = z$): - Síť by se degradovala na jediný perceptron (lineární kombinátor). - Ztratila by schopnost modelovat nelineární vztahy, např. XOR problém. - Klesla by výrazně expresivita modelu.
Klasifikace metodou nejbližšího souseda. Výhody a nevýhody. Řadu nevýhod triviální implementace lze odstranit, jak?
Metoda k-NN (k-Nearest Neighbors) je algoritmus učení s učitelem, který klasifikuje neznámý vzorek na základě většinové třídy jeho k nejbližších sousedů v trénovacích datech. Nevýhody triviální implementace řeší např. k-D stromy.
Uvažujme 2D datovou sadu s třídami △ (modrá) a ● (červená):
Pro testovací bod (3,3) a k=3:
1. Vzdálenosti k △: √5≈2.24, √1=1, √2≈1.41
2. Vzdálenosti k ●: √2≈1.41, √4=2, √5≈2.24
Nejbližší sousedé: △ (1.0), ● (1.41), △ (1.41) → většina △ → klasifikace jako △.
k-D stromy (k-dimensional trees):
Binární stromy pro hierarchické rozdělení prostoru. Příklad pro 2D:
Root: (x=3.5) ├─ Vlevo: body s x<3.5 (rozděl na y=2.5) └─ Vpravo: body s x≥3.5 (rozděl na y=4)
Složitost klesne na O(log n) při nízkých dimenzích [1].
Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění – použití pro jiné ztrátové funkce než L2.
Cílem je rozdělit množinu $n$ datových bodů $\mathcal{D} = \{ \mathbf{x}_1, \ldots, \mathbf{x}_n \}$ v $d$-rozměrném prostoru do $k$ shluků ($k$ předem zadané). Optimalizuje se ztrátová funkce:
$$
J = \sum_{i=1}^k \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|^2
$$
kde $C_i$ je $i$-tý shluk a $\boldsymbol{\mu}_i$ jeho centroid (průměr bodů ve shluku).
$$
C_i = \{ \mathbf{x} : \|\mathbf{x} - \boldsymbol{\mu}_i\|^2 \leq \|\mathbf{x} - \boldsymbol{\mu}_j\|^2 \, \forall j \}
$$
$$
\boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\mathbf{x} \in C_i} \mathbf{x}
$$
Výsledek po konvergenci: 3 shluky s centroidy $\mu_1, \mu_2, \mu_3$.
Místo Eukleidovské vzdálenosti ($\ell_2$) lze použít:
- Manhattanská vzdálenost ($\ell_1$):
$$
J = \sum_{i=1}^k \sum_{\mathbf{x} \in C_i} \|\mathbf{x} - \boldsymbol{\mu}_i\|_1
$$
Centroid aktualizován jako medián shluku (odolnější vůči odlehlým hodnotám).
- Obecná Minkowského metrika ($\ell_p$):
$$
\|\mathbf{x} - \boldsymbol{\mu}_i\|_p = \left( \sum_{j=1}^d |x_j - \mu_{ij}|^p \right)^{1/p}
$$
- Kosinová podobnost: Pro textová/data s vysokou dimenzí.
Vylepšení inicializace centroidů:
1. První centroid náhodně vybrán z dat.
2. Každý další centroid vybrán s pravděpodobností úměrnou $\|\mathbf{x} - \mu_{\text{nejblížší}}\|^2$.
Výhody: Snižuje riziko špatné konvergence, často dosáhne globálního optima s menším počtem iterací.