next up previous
Next: Metoda nejmenších čtverců Up: Výběr modelu pomocí metody Previous: Výběr modelu pomocí metody

Úvod a popis problému

V tomto cvičení byste si měli osvojit používání metody cross-validation pro výběr modelu. Metodu použijeme na konkrétním problému aproximace experimentálně naměřených dat polynomem. Stupeň polynomu, který by se pro aproximaci měl použít, není předem známý. Je třeba ho určit tak, aby výsledná aproximace co nejlépe odpovídala skutečnému průběhu měřené funkce. Problém je následující. Máme k dispozici $K$ vzorků $(x_1,y_1),...,(x_K,y_K)$, kde ${y_i}$ je změřená hodnota neznámé reálné funkce $f(x)$ v bodě ${x_i}$. Naměřené vzorky $y_i$ jsou porušeny šumem, který má v našem případě Gaussovské rozdělení $N(0,\sigma)$ s nulovou střední hodnotou a variancí $\sigma$. Uvažujeme tedy model měření
\begin{displaymath}
y = f(x) + N(0,\sigma).
\end{displaymath} (1)

Naším cílem je aproximovat neznámou funkci $f(x)$ polynomem $p(x,{\mathbf a},d)$
\begin{displaymath}
p(x,{\mathbf a},d) = a_0 + a_1 \cdot x + ... + a_d \cdot x^d \:,
\end{displaymath} (2)

kde $d$ je stupeň polynomu a vektor ${\mathbf a}=[a_0,a_1,...,a_d]$ je vektor koeficientů tohoto polynomu. Chceme zvolit takový stupeň polynomu $d$ a takový vektor ${\mathbf a}$, aby tato aproximace byla co nejlepší. Jak to však provést? Především je třeba si rozmyslet, co znamená ``nejlepší aproximace funkce''. Tradiční volbou je hodnocení chyby aproximace jako součtu odchylek aproximace od naměřených dat umocněných na druhou a hledání takových parametrů aproximačního modelu, které tento součet minimalizují (= metoda nejmenších čtverců). Ukažme si takový přístup na příkladě, který se nám v dalším bude hodit. Nechť zvolený řád polynomu je $d$ a máme dánu podmnožinu naměřených vzorků. Ta nechť je zadána množinou ${TRN}$, ve které jsou indexy vybraných vzorků, tj. ${TRN}\subset\{1,2,\ldots,K\}$. Vektor ${\mathbf a}$ se ve smyslu nejmenších čtverců (Least Squares, LS) spočítá jako
\begin{displaymath}
{\mathbf a} = %%\argmin_{\vect{a}} E_{TRN}(\vect{a}) =
...
...}} \sum_{i\in{TRN}} (y_i - p(x_i,{\mathbf a}^{*},d))^2 \:.
\end{displaymath} (3)

Vyřešení této úlohy je popsáno v oddíle 2. Teď se však zamysleme, jestli bychom pomocí metody nejmenších čtverců dokázali najít jak ${\mathbf a}$, tak i stupeň polynomu $d$. Odpověď zní že ano, ale řešení by se nám nelíbilo. Pro vysoké stupně polynomu $d$ totiž dochází k tzv. ``přefitování''. To znamená, že s rostoucím řádem polynomu chyba na trénovacích datech klesá (nebo je dokonce nulová), ale polynom s vysokým stupněm nemusí vůbec dobře odpovídat skutečné funkci $f(x)$. Nyní se dostáváme k principu metody cross-validation. V tomto případě se určí stupeň polynomu $d$ tak, aby byla nejmenší tzv. cross-validační chyba $E_{CROSS}$. Cross-validační chyba se spočítá následujícím způsobem. Náhodně rozdělíme naměřenou množinu dat $(x_1,y_1),...,(x_K,y_K)$ na $n$ skupin. Tyto skupiny nechť jsou opět zadány pomocí množin indexů vzorků, které označme ${TST}_1,
{TST}_2,...,{TST}_n$. Tyto množiny nechť se nepřekrývají, jsou stejně velké a jejich sjednocení dá celou množinu, takže $\bigcup_{i=1}^{n}{TST}_i=\{1,2,\ldots,K\}$. Těmto množinám budeme říkat ``testovací''. Výpočet cross-validační chyby popisuje následující pseudokód: Podle počtu podmnožin $n$ mluvíme o tzv. $n$-fold cross-validační chybě. Oblíbená je volba $n=10$. Pozn: limitní případ, kdy $n$ je rovno počtu naměřených dat se nazýva one-leave-out.
next up previous
Next: Metoda nejmenších čtverců Up: Výběr modelu pomocí metody Previous: Výběr modelu pomocí metody
Ondrej Drbohlav 2002-10-30