Statistické rozhodování. Klasifikátory a jejich učení. Neuronové sítě. B4B33RPZ (Webové stránky předmětu)

1. 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”.
2. Logistická regrese. Formulace úlohy. Algoritmus učení. Vlastnosti (výhody a nevýhody).
3. Klasifikátor typu Support Vector Machine. Formulace úlohy učení, i pro neseparabilní data. Učení SVM, jak lineární, tak s jádrovou funkcí (kernel SVM). Vlastnosti (výhody a nevýhody).
4. Adaboost, popis algoritmu, jeho interpretace jako minimalizace horního odhadu empirického rizika. Vlastnosti (výhody a nevýhody).
5. Neuronové sítě s dopředným šířením. Struktura. Učení pomocí metody zpětného šíření. Vlastnosti (výhody a nevýhody).
6. Klasifikace metodou nejbližšího souseda. Výhody a nevýhody. Řadu nevýhod triviální implementace lze odstranit, jak?
7. Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění - použití pro jiné ztrátové funkce než L2.

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ť:

• $X$ je množina pozorování. Pozorování (neboli měření, vektor rysů) $x \in X$ reprezentuje to, co je o daném objektu známo.
• $K$ je množina tříd (skrytých stavů). Stav $k \in K$ vyjadřuje to, co o objektu není známo (např. skrytý parametr, skrytý stav, stav přírody, třída).
• $D$ je množina možných rozhodnutí (akcí).
• $p_{XK}: X \times K \to \mathbb{R}$ je společná pravděpodobnost toho, že objekt je ve stavu $k$ a zároveň se pozoruje $x$.
  

• $W: K \times D \to \mathbb{R}$ je penalizační (loss) funkce. Hodnota $W(k, d)$, kde $k \in K$, $d \in D$, je trest (penalizace), kterou zaplatíme, pokud je objekt ve stavu $k$ a rozhodneme se pro akci $d$. Tato funkce je definována pro tzv. Bayesovské úlohy (brzy se jí budeme věnovat podrobněji).
• $q: X \to D$ je rozhodovací funkce (pravidlo, strategie), která přiřazuje každému $x \in X$ rozhodnutí $q(x) \in D$.

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.

• Ztrátová funkce $W(k,d)$ říká:
  

– 0 za správně, 1 za špatně, $\varepsilon$ za „nevím“.

• Riziko $R(x,d)$ je očekávaná ztráta při rozhodnutí $d$.
  

• Optimalizace ukazuje, že rozhodujeme podle maximální posteriorní pravděpodobnosti, ale jen tehdy, když očekávané riziko chyby je menší než riziko „nevím“ ($\varepsilon$).
  

• Prakticky to znamená: vyber třídu jen tehdy, když její posterior převýší práh
  

$$ \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}} $$

• Lineární kombinace: $z = w^T x + b$, kde $w$ jsou váhy, $b$ bias.
• Posterior pravděpodobnost: $P(y=1 | x) = \sigma(z)$.
• Cíl: Maximální věrohodnost (maximum likelihood) parametrů $w, b$.

1. Log-likelihood: Často se používá logaritmus věrohodnosti pro optimalizaci: $$ \ell(w) = \sum_{i=1}^n \left[ y_i \ln \sigma(z_i) + (1 - y_i) \ln(1 - \sigma(z_i)) \right] $$
2. Gradientní sestup: Hledá se minimum funkce $E(w) = -\ell(w)$. Gradient je: $$ \frac{\partial E}{\partial w_j} = -\sum_{i=1}^n (y_i - \sigma(z_i)) x_{i,j} $$
3. Konvexita: Funkce $E(w)$ je konvexní, což zaručuje globální minimum.

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 typu Support Vector Machine. Formulace úlohy učení, i pro neseparabilní data. Učení SVM, jak lineární, tak s jádrovou funkcí (kernel SVM). Vlastnosti (výhody a nevýhody).

Pro lineárně separabilní data hledáme hranici (hyperrovinu) $w \cdot x + b = 0$, která maximálně odděluje třídy. Margin je vzdálenost mezi podpůrnými vektory (nejblíže ležícími body) a hyperrovinou. Úloha se převede na kvadratickou optimalizaci:
$$\min_{w,b} \frac{1}{2} \|w\|^2 \quad \text{s omezením } y_i(w \cdot x_i + b) \geq 1\text{ [4]}.$$
Pro neseparabilní data se přidají slack proměnné $\xi_i$, které umožňují porušení marginu:
$$\min_{w,b,\xi} \frac{1}{2}\|w\|^2 + C\sum \xi_i \quad \text{s } y_i(w \cdot x_i + b) \geq 1 - \xi_i, \xi_i \geq 0\text{ [4]}.$$

Pro data nelineárně separabilní se používá kernel trick:
$$K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j),$$
kde $\phi$ je vektorizace do vyšší dimenze. Tím se vyhnete explicitnímu výpočtu $\phi(x)$ [4].

Výhody:
- Dobrá generalizace díky maximalizaci marginu.
- Podpora kernelů umožňuje řešit nelineární problémy.

Nevýhody:
- Výpočetně náročné pro velké datové sady.
- Náročné volit kernel a regulkařní parametr $C$.

SVM hledá hard margin mezi třídami, zatímco softmax v logistické regresi modeluje pravděpodobnosti tříd:
$$P(y=i|x) = \frac{e^{w_i \cdot x}}{\sum_j e^{w_j \cdot x}}.$$
Rozdíl: SVM maximalizuje rozmezí mezi třídami, softmax minimalizuje křížovou entropii. Softmax je vhodnější pro více tříd, SVM vyžaduje rozšíření (např. one-vs-rest).

Hard margin (separabilní data):

Soft margin (neseparabilní data):

Podpůrné vektory (SV) leží na marginu, $\xi_i$ označují porušení marginu.

Adaboost, popis algoritmu, jeho interpretace jako minimalizace horního odhadu empirického rizika. Vlastnosti (výhody a nevýhody).

Neuronové sítě s dopředným šířením. Struktura. Učení pomocí metody zpětného šíření. Vlastnosti (výhody a nevýhody).

Klasifikace metodou nejbližšího souseda. Výhody a nevýhody. Řadu nevýhod triviální implementace lze odstranit, jak?

Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění - použití pro jiné ztrátové funkce než L2.