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 (SVM) je metoda pro binární klasifikaci, která hledá optimální rozhodovací hranici maximalizující margin mezi třídami. Pro neseparabilní data zavádí slack proměnné nebo využívá kernel trik pro transformaci do vyšší dimenze.

Pro lineárně separabilní data řešíme optimalizační problém: $$\min \frac{1}{2} \|w\|^2 \quad \text{za podmínky} \quad y_i(w \cdot x_i + b) \geq 1$$ kde w je normálový vektor, b posun a y_i ∈ {-1,1} třídní štítky . Geometricky jde o maximalizaci marginu $m^* = \frac{2}{\|w\|}$ mezi rovnoběžnými hyperrovinami $w \cdot x + b = \pm 1$.

Pro nelineární rozhodovací hranice používáme kernel funkce $K(x_i,x_j) = \phi(x_i) \cdot \phi(x_j)$, které implicitně mapují data do vyšší dimenze bez výpočetní náročnosti . Běžné jádra: - Lineární: $K(x_i,x_j) = x_i \cdot x_j$ - Polynomiální: $K(x_i,x_j) = (x_i \cdot x_j + c)^d$ - RBF: $K(x_i,x_j) = \exp(-\gamma\|x_i - x_j\|^2)$

Výhody: - Efektivní v vysokých dimenzích díky kernel triku - Robustnost díky maximalizaci marginu - Přesnost závislá pouze na support vektorech

Nevýhody: - Výpočetně náročné pro velké datasety - Citlivost na volbu kernelu a parametrů (C, γ) - Omezená interpretovatelnost výsledků

SVM se využívá pro: detekci spamu, klasifikaci textu, rozpoznávání obrazu a bioinformatiku, kde je klíčová schopnost pracovat s komplexními datovými strukturami pomocí kernelů.

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.