Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
statnice:bakalar:b4b33rpz [2025/06/07 11:26] – [Support Vector Machine] mistrjirkastatnice:bakalar:b4b33rpz [2025/06/07 11:45] (current) – [Příklad s TikZ] mistrjirka
Line 449: Line 449:
 ===== Adaboost ===== ===== Adaboost =====
 **Adaboost, popis algoritmu, jeho interpretace jako minimalizace horního odhadu empirického rizika. 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).**
 +
 +
 +**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)$
 +
 +<tikzjax>
 +\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}
 +</tikzjax>
 +==== 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ě =====
 **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. 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 =====
 **Klasifikace metodou nejbližšího souseda. Výhody a nevýhody. Řadu nevýhod triviální implementace lze odstranit, jak?** **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á):
 +
 +<tikzjax>
 +\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}
 +</tikzjax>
 +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 ====
 +
 +  * <WRAP>
 +**k-D stromy** (k-dimensional trees):\\
 +Binární stromy pro hierarchické rozdělení prostoru. Příklad pro 2D:
 +<code>
 +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)  
 +</code>
 +
 +Složitost klesne na O(log //n//) při nízkých dimenzích [1].\\
 +
 +</WRAP>
 +  * **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 =====
-**Shlukování metodou k-means, formulace úlohy a popis algoritmu. Vlastnosti algoritmu. Zobecnění - použití pro jiné ztrátové funkce než L2.** 
  
 +**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 ====
 +
 +<tikzjax>
 +\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}
 +</tikzjax>
 +//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í.
  

Trace: • b4b35osy • zkousky • b4b33rpz • b4b39iur • b0b36dbs

Navigation

Playground

QR Code
QR Code statnice:bakalar:b4b33rpz (generated for current page)