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

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

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.