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 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.

• Příklad: Rozhodnutí, zda e-mail je spam (třída +1) či nikoliv (třída -1) na základě slovních příznaků.
  

• Účel: Najít hyperrovinu $\mathbf{w}^T\mathbf{x} + b = 0$ s maximální vzdáleností od nejbližších bodů (support vectors), což zvyšuje generalizaci.

1. Hard Margin:

   • Předpokládá lineární separabilitu dat.
     

   • Primární úloha:
     

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

   • Problém: Citlivý na odlehlé hodnoty a šum.

2. Soft Margin:

   • Povoluje chyby klasifikace pomocí relaxačních proměnných $\xi_i$.
     

   • Primární úloha:
     

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

   • Parametr $C$: Řídí kompromis mezi šířkou okraje a chybami (nízké $C$ = větší margin, vyšší $C$ = méně chyb).

• Princip: Mapuje data do vyšší dimenze pomocí jádrové funkce $K(\mathbf{x}_i, \mathbf{x}_j)$, aby se nelineárně separabilní data stala lineárně separabilními.
  

• Příklad: Gaussovo jádro (RBF) $K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$.
  

• Výhoda: Vyhýbá se explicitnímu výpočtu transformace (úspora výpočetního času).
  

• Rovnice: Rozhodovací funkce se stává $f(\mathbf{x}) = \sum_{i} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b$.

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ů.

1. Inicializace vah: Každému trénovacímu vzorku $(x_i, y_i)$ přiřadíme počáteční váhu $w_i^{(1)} = \frac{1}{m}$
   

1. Iterace pro $t = 1$ až $T$:
   1. Natrénuj slabý klasifikátor $h_t(x)$ s minimální váženou chybou $\epsilon_t = \sum_{i=1}^m w_i^{(t)} \mathbf{1}_{[h_t(x_i) \neq y_i]}$
      

1. Vypočti koeficient $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$
   

1. Aktualizuj váhy: $w_i^{(t+1)} = \frac{w_i^{(t)} \exp(-\alpha_t y_i h_t(x_i))}{Z_t}$ kde $Z_t$ je normalizační faktor
   

1. Výsledný klasifikátor: $H(x) = \text{sign} \left( \sum_{t=1}^T \alpha_t h_t(x) \right)$ [5]

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)$

• Rozpoznávání obličejů
  

• Detekce spamu
  

• Medicínská diagnostika
  

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).

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 △.

• Rozpoznávání obrazců (OCR, detekce objektů)
• Doporučovací systémy (“uživatelé s podobným profilem”)
• Lékařská diagnostika (klasifikace vzorků)

1. Jednoduchá implementace bez potřeby tréninkového modelu
   
2. Adaptabilita na nová data (stačí přidat vzorky)
   
3. Vhodná pro vysoký počet tříd (i stovky tříd) [1]
   
4. Neparametrická – nedělá předpoklady o distribuci dat

1. Výpočetní náročnost – O(n) pro každou klasifikaci (prohledávání všech vzorků)
   
2. Citlivost na šum a irelevantní atributy
   
3. Problém vysoké dimenzionality (curse of dimensionality)
   
4. Nevhodná pro nevyvážená data (dominance větších tříd)

• 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].
  

• Vážení atributů (např. ReliefF algoritmus)
  
• Normalizace dat (potlačení vlivu škálování)
  
• Výběr optimálního k (křížová validací)

• Efektivita klesá pro dimenze >20 (“curse of dimensionality”)
  
• Konstrukce stromu O(n log n), ale jednorázová investice [1]

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