====== Statistické rozhodování. Klasifikátory a jejich učení. Neuronové sítě. B4B33RPZ (Webové stránky předmětu) ====== - 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”. - 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. 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 ===== **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”.** ==== Bayesianské rozhodování ==== 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) $$ ==== 1. Formulace úlohy ==== 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) $$ ==== Pro 0-1 ztrátovou funkci ==== 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). $$ ==== 3. Při přidání možnosti „nevím“ ==== $$ 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} $$ === Co je ? === $\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. === Intuice pravidla === * **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 ===== **Logistická regrese. Formulace úlohy. Algoritmus učení. Vlastnosti (výhody a nevýhody).** === Popis a účel: === 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}} $$ === Formulace úlohy: === * **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$. === Algoritmus učení: === - **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] $$ - **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} $$ - **Konvexita**: Funkce $E(w)$ je konvexní, což zaručuje globální minimum. === Vlastnosti: === **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. === Souvislost s softmax: === 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). === Příklad: === **Diagnóza choroby** na základě biomarkerů $x$: - Vstup: $x = [\text{teplota, bílkoviny}]$. - Model určí $P(\text{choroba} = 1 | x)$. === Vizuální příklady: === **Sigmoida**: \usepackage{amsmath} \usepackage{pgfplots} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \begin{document} \begin{tikzpicture} \begin{axis}[ domain=-5:5, samples=100, axis lines=middle, xlabel={$z$}, ylabel={$\sigma(z)$} ] \addplot [blue] {1/(1+exp(-x))}; \end{axis} \end{tikzpicture} \end{document} **Softmax pro 3 třídy**: \usepackage{amsmath} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \usepackage{pgfplots} \begin{document} \begin{tikzpicture} \begin{axis}[ domain=-2:2, samples=50, axis lines=center, xlabel={$z_k$}, ylabel={$P(y=k|x)$} ] \addplot [red, thick] {exp(x)/(exp(0)+exp(1)+exp(x))}; % příkladní vstupy \addplot [green] {exp(1)/(exp(0)+exp(1)+exp(x))}; \addplot [blue] {exp(0)/(exp(0)+exp(1)+exp(x))}; \end{axis} \end{tikzpicture} \end{document} === Závěr: === 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. ===== Support Vector Machine ===== **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 a účel === * **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. === Hard Margin vs. Soft Margin === - **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. \usepackage{amsmath} \usepackage{pgfplots} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \begin{document} \begin{tikzpicture} \begin{axis}[ axis equal image, axis lines=center, xmin=-0.5, xmax=9, ymin=-0.5, ymax=7, xtick=\empty, ytick=\empty, no markers ] % Bias and weight vectors \addplot[dashed,->] coordinates {(0,0) (11/5,22/5)} node[midway,left=5pt]{$b$}; \addplot[thick,->] coordinates {(0,0) (0.4472,0.8944)} node[below right]{$\hat{\mathbf{w}}$}; % Margin width arrow \addplot[dashed,<->] coordinates {(6.6,1.2) (7.4,2.8)} node[right=10pt,above]{$\tfrac{2}{\|\mathbf{w}\|}$}; % Hyperplanes D₋, D, D₊ \addplot[black,thin,domain=1:7] {(9 - x)/2} node[pos=0.05,sloped,above]{\tiny $D_{-}$}; \addplot[black,thick,domain=(7/5):(37/5)] {(11 - x)/2} node[pos=0.025,sloped,above]{\tiny $D$}; \addplot[black,thin,domain=(9/5):(39/5)] {(13 - x)/2} node[pos=0.05,sloped,above]{\tiny $D_{+}$}; % Data points (class a vs. class b) + support vectors (v) \addplot[ scatter,only marks, point meta=explicit symbolic, scatter/classes={ a={mark=*}, b={mark=*,draw=black,fill=white}, v={mark=o,draw=darkgray,thick,scale=2.25} } ] table[meta=label] { x y label 4 6 a 5 4 a 5.5 5 a 6.5 5 a 7 3.5 a 7 5.5 a 1 3 b 1.5 0.5 b 2 2.5 b 3 3 b 4 1 b 5 2 b 3 3 v 5 2 v 5 4 v }; \end{axis} \end{tikzpicture} \end{document} - **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). \usepackage{amsmath} \usepackage{pgfplots} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \begin{document} \begin{tikzpicture} \begin{axis}[ axis equal image, axis lines=center, xmin=-0.5, xmax=8, ymin=-0.5, ymax=6, xtick=\empty, ytick=\empty, no markers ] % Hyperplanes: thin, decision (thick), thin \addplot[black,thin,domain=1:7] {(9 - x)/2}; \addplot[black,thick,domain=(7/5):(37/5)] {(11 - x)/2}; \addplot[black,thin,domain=(9/5):(39/5)] {(13 - x)/2}; % Slack vectors xi_i, xi_j \addplot[dashed,->] coordinates {(3.8,3.6) (4.45,4.9)} node[above left]{$\xi_{i}$}; \addplot[dashed,->] coordinates {(4.4,3.3) (3.55,1.6)} node[above left]{$\xi_{j}$}; % Data points (class a vs. class b) \addplot[ scatter,only marks, point meta=explicit symbolic, scatter/classes={ a={mark=*}, b={mark=*,draw=black,fill=white} } ] table[meta=label] { x y label 4 6 a 5 4 a 5.5 5 a 6.5 5 a 7 3.5 a 7 5.5 a 1 3 b 1.5 0.5 b 2 2.5 b 3 3 b 4 1 b 5 2 b 3 3 b 5 2 b 5 4 a 4.5 5 b 3.5 1.5 a }; \end{axis} \end{tikzpicture} \end{document} === Kernel Trick === * **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$. === Vlastnosti, výhody a nevýhody === ^**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 ===== **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ů.** ==== Popis algoritmu ==== - **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}$\\ - **Iterace** pro $t = 1$ až $T$: - 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]}$\\ - Vypočti koeficient $\alpha_t = \frac{1}{2} \ln \left( \frac{1 - \epsilon_t}{\epsilon_t} \right)$\\ - 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\\ - **Výsledný klasifikátor**: $H(x) = \text{sign} \left( \sum_{t=1}^T \alpha_t h_t(x) \right)$ [5] ==== Minimalizace horního odhadu ==== 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] ==== Vlastnosti ==== **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 ==== Příklad ==== **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)$ \usepackage{amsmath} \usepackage{pgfplots} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \begin{document} \begin{tikzpicture}[scale=0.8] \draw[->] (0,0) -- (4,0) node[right] {$x$}; \draw[->] (0,0) -- (0,3) node[above] {$y$}; \draw[blue] (0.5,2.5) -- (1.5,0.5) node[midway,left] {$h_1$}; \draw[red] (2.5,2.5) -- (3.5,0.5) node[midway,right] {$h_2$}; \draw[thick] (0.5,2.7) .. controls (2,1.8) .. (3.5,0.3) node[right] {$H(x)$}; \fill (1,2.5) circle (2pt) node[above] {+}; \fill (2,0.5) circle (2pt) node[below] {-}; \fill (3,2.5) circle (2pt) node[above] {+}; \end{tikzpicture} \end{document} ==== Aplikace ==== * 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ě ===== **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.** ==== Struktura ==== * Skládá se z vrstev: **vstupní** (přijímá data), **skryté** (provádí výpočty) a **výstupní** (poskytuje výsledek). * Každý neuron počítá vážený součet vstupů plus bias: $z = \sum w_i x_i + b$, následovaný aktivační funkcí: $a = g(z)$. * Typické nelineární funkce: sigmoida, tanh, ReLU. ==== Učení metodou zpětného šíření ==== - **Dopředné šíření**: Výpočet výstupů vrstev postupně od vstupu. - **Výpočet chyby**: Porovnání výstupu s cílem pomocí loss funkce (např. MSE). - **Zpětné šíření**: * Gradienty chyby se šíří od výstupu ke vstupu pomocí řetězového pravidla. * Aktualizace vah: $w \leftarrow w - \alpha \frac{\partial L}{\partial w}$, kde $\alpha$ je learning rate. ==== Vlastnosti ==== * **Výhody**: Schopnost aproximovat libovolné spojité funkce (univerzální aproximátor), automatická extrakce příznaků. * **Nevýhody**: Pomalé trénování, riziko přetrénování, citlivost na inicializaci vah. ==== Konvoluce (příklad) ==== 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 $$ ==== Pooling a MaxPooling (příklad ==== 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} $$ ==== Použití Softmax ==== 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). ==== Nevýhody lineární aktivační funkce ==== 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 ===== **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.** ==== Příklad ==== Uvažujme 2D datovou sadu s třídami △ (modrá) a ● (červená): \usepackage{amsmath} \usepackage{pgfplots} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \begin{document} \begin{tikzpicture}[scale=0.6] \draw[gray!30] (0,0) grid (6,5); \draw[->] (0,0) -- (6.2,0); \draw[->] (0,0) -- (0,5.2); \foreach \point/\col in {(1,1)/blue, (1,3)/blue, (2,2)/blue, (4,4)/red, (5,3)/red, (5,5)/red} \fill[\col] \point circle (4pt); \node[blue] at (1,1) {$\triangle$}; \node[blue] at (1,3) {$\triangle$}; \node[blue] at (2,2) {$\triangle$}; \node[red] at (4,4) {$\bullet$}; \node[red] at (5,3) {$\bullet$}; \node[red] at (5,5) {$\bullet$}; \fill[green] (3,3) circle (4pt); % Testovací bod \node at (3,3.3) {?}; \end{tikzpicture} \end{document} 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 △. ==== Využití ==== * Rozpoznávání obrazců (OCR, detekce objektů) * Doporučovací systémy (“uživatelé s podobným profilem”) * Lékařská diagnostika (klasifikace vzorků) ==== Výhody ==== - **Jednoduchá implementace** bez potřeby tréninkového modelu\\ - **Adaptabilita** na nová data (stačí přidat vzorky)\\ - **Vhodná pro vysoký počet tříd** (i stovky tříd) [1]\\ - **Neparametrická** – nedělá předpoklady o distribuci dat ==== Nevýhody ==== - **Výpočetní náročnost** – O(//n//) pro každou klasifikaci (prohledávání všech vzorků)\\ - **Citlivost na šum a irelevantní atributy**\\ - **Problém vysoké dimenzionality** (curse of dimensionality)\\ - **Nevhodná pro nevyvážená data** (dominance větších tříd) ==== Řešení nevýhod ==== * **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í) ==== Omezení k-D stromů ==== * Efektivita klesá pro dimenze >20 (“curse of dimensionality”)\\ * Konstrukce stromu O(//n// log //n//), ale jednorázová investice [1] ===== Shlukování metodou k-means ===== **Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění – použití pro jiné ztrátové funkce než L2.** ==== Formulace úlohy ==== 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). ==== Popis algoritmu ==== - **Inicializace:** Náhodný výběr $k$ počátečních centroidů.\\ - **Přiřazení bodů:** Každý bod přiřazen k nejbližšímu centroidu (Eukleidovská vzdálenost):\\ $$ C_i = \{ \mathbf{x} : \|\mathbf{x} - \boldsymbol{\mu}_i\|^2 \leq \|\mathbf{x} - \boldsymbol{\mu}_j\|^2 \, \forall j \} $$\\ - **Aktualizace centroidů:**\\ $$ \boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\mathbf{x} \in C_i} \mathbf{x} $$\\ - **Ukončení:** Opakování kroku 2–3, dokud se přiřazení bodů nemění nebo nedojde k maximálnímu počtu iterací. ==== Příklad ==== \usepackage{amsmath} \usepackage{pgfplots} \usetikzlibrary{automata, positioning, arrows, calc, cd, intersections,arrows.meta} \begin{document} \begin{tikzpicture} % Data points \filldraw[blue] (0.5,1.5) circle (2pt); \filldraw[blue] (1,1) circle (2pt); \filldraw[blue] (1.5,0.5) circle (2pt); \filldraw[red] (3,2) circle (2pt); \filldraw[red] (3.5,2.5) circle (2pt); \filldraw[red] (4,3) circle (2pt); \filldraw[green] (2,4) circle (2pt); \filldraw[green] (2.5,4.5) circle (2pt); \filldraw[green] (3,5) circle (2pt); % Centroids (after convergence) \filldraw[black] (1,1) circle (4pt) node[below] {$\mu_1$}; \filldraw[black] (3.5,2.5) circle (4pt) node[below] {$\mu_2$}; \filldraw[black] (2.5,4.5) circle (4pt) node[above] {$\mu_3$}; \end{tikzpicture} \end{document} //Výsledek po konvergenci: 3 shluky s centroidy $\mu_1, \mu_2, \mu_3$.// ==== Vlastnosti algoritmu ==== * **Rychlý a škálovatelný** pro velká data ($O(n \cdot k \cdot d)$ na iteraci).\\ * **Citlivý na inicializaci** (špatná volba centroidů → suboptimální řešení).\\ * **Předpokládá konvexní shluky** stejné velikosti (špatně zpracuje nestejnoměrná data).\\ * **Lokální optimum:** Konverguje k nejbližšímu lokálnímu minimu $J$. ==== Zobecnění pro jiné ztrátové funkce ==== 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í. ==== K-means++ ==== 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í. ==== Aplikace ==== * Segmentace zákazníků, analýza genomických dat, komprese obrazu (redukce barev), detekce anomálií.