The wiki page is under active construction, expect bugs.

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/03 10:48] – [1. Formulace úlohy] mistrjirkastatnice:bakalar:b4b33rpz [2025/06/07 11:45] (current) – [Příklad s TikZ] mistrjirka
Line 7: Line 7:
   - 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?
   - 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.
-  - 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.+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 =====
 **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”.** **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í =====+==== Bayesianské rozhodování ====
  
 Nechť: Nechť:
Line 62: Line 62:
 Risk se dá převést na Partial risk: Risk se dá převést na Partial risk:
 $$ $$
-R(x,d) = \sum{k \in K}p_{Kx}(k|x)W(k,d)+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 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)+q^*(x) = \underset{d \in D}{\arg\min} \sum_{k \in K}p_{Kx}(k|x)W(k,d)
 $$ $$
-==== Speciální případ: 0-1 loss funkce ====+==== 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 =====
 +
 **Logistická regrese. Formulace úlohy. Algoritmus učení. Vlastnosti (výhody a nevýhody).** **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**:
 +
 +<tikzjax>
 +\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}
 +</tikzjax>
 +**Softmax pro 3 třídy**:
 +
 +<tikzjax>
 +\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}
 +</tikzjax>
 +=== 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 ===== ===== Support Vector Machine =====
-**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).**+ 
 +**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 === 
 + 
 +  - <WRAP> 
 +**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. 
 +<tikzjax> 
 +\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} 
 +</tikzjax> 
 +</WRAP> 
 +  - <WRAP> 
 +**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). 
 +<tikzjax> 
 +\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} 
 +</tikzjax> 
 +</WRAP> 
 +=== 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 =====
 **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:

Navigation

Playground

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