12. Jádrové metody: jádrová regrese, bázové funkce, Support Vector Machine (SVM): separabilní a neseparabilní případ. (NI-ADM)

---

link

Lineární regrese

Lineární regrese se snaží naučit lineární vztah mezi vstupními příznaky a výstupní hodnotou. Hledá takovou spojitou hodnotu která na zaklade příznaku předpovídá nějakou řešenou hodnotu. Například na zaklade velikosti bytu a lokality předpovídá cenu bytu

Matematicky: $Y = w_0 + w_1x_1 + ... + w_px_p + \varepsilon = w^Tx+\varepsilon$

• Model kombinuje vstupní příznaky ($x$) pomocí vah ($w$)
• $w_0$ je posun (bias), který určuje základní úroveň predikce
• $\varepsilon$ je chybový člen zachycující náhodnou variabilitu, kterou model nedokáže vysvětlit

Učení modelu:

• Cílem je najít takové váhy, které minimalizují chybu predikce
• Typicky se používá metoda nejmenších čtverců
• Model postupně upravuje váhy, aby se predikce co nejvíce blížily skutečným hodnotám

Jádrové metody

Jádrová metody rozšiřuji koncept lineární regrese pro modelování nelineárních vztahů. Namísto hledání lineární funkce se snaží najít složitější vztah mezi příznaky. Například při předpovídání ceny bytu může zachytit, že vztah mezi velikostí a cenou není lineární - každý další metr čtvereční má jiný vliv na cenu.

Lineární bázová expanze

Bázová expanze je první krok v tomto procesu. Použijeme nelineární transformace na příznacích které posunou příznaky "jinam" a v tomto novem rozložení již budeme moct udělat lineární regresi.

Matematicky: $Y= w^T\varphi (x) +\varepsilon$

• Model transformuje vstupní příznaky ($x$) pomoci nelineární transformace nazývané bázová funkce $\varphi$ a tyto transformované hodnoty nakonec násobí pomocí vah ($w$)
• $\varepsilon$ je chybový člen zachycující náhodnou variabilitu, kterou model nedokáže vysvětlit
• Jedna z možných bázových funkci je třeba $\varphi (x_i) = x_i^2$

Učení modelu

• Cílem je najit váhy $w$ tak aby nejlépe minimalizovali chybu predikce
• Můžeme pro to použít Regularizovanou Residuální Sumu Čtverců: $$RSS_\lambda (w) = || Y- \varphi (X) w||^2 + \lambda \sum_{i=1}^nw_i^2$$
  • V případě ze $\lambda > 0$ existuje přesně jedno řešeni této rovnice

Jádrová regrese

Jádrová regrese rozšiřuje princip lineární regrese pro nelineární vztahy pomocí implicitní transformace dat do vyšší dimenze. Na rozdíl od bázové expanze (kde explicitně definujeme transformaci $\phi$), jádrové metody pracují s jádrovou funkcí, která implicitně měří podobnost mezi datovými body v transformovaném prostoru. To umožňuje modelovat komplexní vztahy bez výpočetní náročnosti spojené s vysokými dimenzemi.

Kernel Trick

Jádrový trik funguje na principu nahrazení výpočtu v transformovaném prostoru. Namísto toho, abychom počítali skalární součin transformovaných dat $\varphi(x)^T\varphi(y)$, použijeme jádrovou funkci $K(x,y)$, která nám dá stejný výsledek, ale počítá se v původním prostoru.

Definice jádrové funkce: $K(x,y) = \varphi(x)^T\varphi(y)$

Tento přístup využívá Gramovu matici, která obsahuje všechny skalární součiny mezi dvojicemi bodů našeho datasetu. Pro dataset s $n$ vzorky má Gramova matice rozměr $n \times n$ a na pozici $i,j$ obsahuje hodnotu $K(x_i,x_j)$. Důležité vlastnosti této matice jsou její symetrie (hodnota pro body A,B je stejná jako pro B,A) a pozitivní semidefinitnost.

Hlavní výhoda spočívá v tom, že velikost Gramovy matice závisí pouze na počtu vzorků v datasetu, ne na dimenzi prostoru, do kterého data transformujeme. To znamená, že můžeme pracovat i s velmi vysokými dimenzemi, aniž by se zvýšila paměťová nebo výpočetní náročnost.

Jádrová regrese

Matematická formulace: $$\hat{f}(x) = \sum_{i=1}^n \alpha_i K(x,x_i) + \varepsilon$$

kde:

• $\alpha_i$ jsou váhy získané řešením optimalizačního problému
• $K(x,x_i)$ je jádrová funkce
• $x_i$ jsou trénovací body
• $\varepsilon$ náhodný sum

Typy jádrových funkcí:

1. Polynomiální jádro (Polynomial kernel): $$k(x,y) = (x^Ty + 1)^n$$

   • Modeluje polynomiální vztahy stupně n
   • Parametr n určuje složitost modelu
   • Často používané v zpracování přirozeného jazyka

2. Kosinová podobnost (Cosine similarity): $$k(x_i,x_j) = \frac{x_i^Tx_j}{\|x_i\|\|x_j\|}$$

   • Měří úhel mezi vektory
   • Nezávislá na velikosti vektorů
   • Používá se pro porovnávání textových dokumentů nebo při zpracování obrazu

3. RBF (Gaussian) kernel: $$k(x,y) = \exp(-\gamma\|x-y\|^2)$$

   • Nejpoužívanější nelineární jádro
   • $\gamma$ kontroluje šířku Gaussovy křivky
   • Vhodné pro většinu praktických aplikací

4. Lineární jádro: $$k(x,y) = x^Ty$$

   • Nejjednodušší jádrová funkce
   • Ekvivalentní standardní lineární regresi
   • Vhodné pro lineárně separovatelná data

Support Vector Machine (SVM)

Support Vector Machine (SVM) je metoda pro binární klasifikaci, kde cílem je nalézt rozhodovací hranici s maximálním odstupem (margin) od obou tříd. Předpokládejme transformaci do prostoru příznaků $\phi(x)$, ve kterém hledáme lineární separator:

$$f(x) = w^T \phi(x) + w_0.$$

Znaménko $f(x)$ pak určuje, do které třídy $x$ zařadíme:

• $f(x) > 0$ $\Rightarrow$ třída $+1$,
• $f(x) < 0$ $\Rightarrow$ třída $-1$.

Lineárně separabilní případ

Discriminantní funkce a velký margin

Pokud lze data ve feature prostoru $\phi(x)$ beze zbytku lineárně oddělit, existuje potenciálně více hyperrovin splňujících $y_i f(x_i) > 0$. Abychom vybrali "nejlepší" z nich, požadujeme maximální margin – tedy nejmenší vzdálenost hyperroviny k libovolnému trénovacímu bodu co největší.

1. Discriminantní funkce: $f(x) = w^T \phi(x) + w_0$. Vektor $w$ je normála k separující hyperrovině.
2. Podmínka odstupu: Body ležící na marginu splňují $\; y_i \bigl(w^T \phi(x_i) + w_0 \bigr) = 1$.
3. Minimalizace: Abychom maximalizovali odstup, lze (v jistém měřítku) minimalizovat $\tfrac12 \|w\|^2$ za podmínek, že $\; y_i f(x_i) \ge 1$ pro všechny body.

Lineárně neseparabilní případ

V reálných datech často nenajdeme ideální hyperrovinu. Proto se zavádějí slack proměnné $\xi_i \ge 0$, které umožňují některým bodům porušit striktní hranici:

$$y_i \bigl(w^T \phi(x_i) + w_0 \bigr) \;\ge\; 1 - \xi_i.$$

• $\xi_i = 0$: Bod je na správné straně marginu nebo přímo na něm.
• $0 < \xi_i < 1$: Bod leží na správné straně hranice, ale uvnitř marginu.
• $\xi_i > 1$: Bod leží na špatné straně hranice (chybně klasifikovaný).

Abychom omezili počet i míru chyb, přidáme penalizační člen do minimalizace:

$$\min_{w,w_0,\{\xi_i\}} \;\;\tfrac12 \|w\|^2 \;+\; C \sum_{i=1}^N \xi_i,$$

kde $C$ je regularizační parametr, který určuje kompromis mezi šířkou marginu a povoleným počtem chyb.

Support Vector Machine

SVM v situaci neseparabilních dat povoluje menší či větší míru chybné klasifikace zavedením slack proměnných $\xi_i \ge 0$, které zachycují „porušení“ marginu. Jejich hodnoty říkají, jak daleko je bod na špatné straně hranice, případně zda se nachází jen v zakázaném pásmu mezi třídami:

• $\xi_i = 0$ označuje body mimo (či na) margin, tedy „bez problémů“.
• $0 < \xi_i \le 1$ značí body uvnitř marginu, ale stále správně klasifikované.
• $\xi_i > 1$ ukazuje, že bod je chybně klasifikovaný (na špatné straně hranice).

Optimalizace

$$\min_{w,w_0,\xi} \tfrac12 \|w\|^2 \;+\; C \sum_{i=1}^N \xi_i$$

pod podmínkami

$$\xi_i \ge 0, \quad Y_i \bigl(w^T \phi(x_i) + w_0\bigr) + \xi_i - 1 \ge 0$$

vyvažuje co největší odstup (inverzní k $\|w\|$) a co nejméně porušení hranice (vyjádřených $\sum_i \xi_i$). Parametr $C$ určuje, nakolik penalizujeme chyby:

• Vysoké $C$ klade větší důraz na minimalizaci $\xi_i$, obvykle vede k menšímu počtu chyb, ale i užšímu marginu.
• Nízké $C$ naopak posiluje roli šířky marginu i toleranci chyb.

Takto vzniklá hyperrovina (či více dimenzionální ekvivalent) nejlépe separuje třídy i za cenu určitých chyb, jež mohou být nevyhnutelné u neseparabilních dat.