\[ \def\_#1{\mathbf{#1}} \def\x{\times} \def\R{\mathbb{R}} \def\mat#1{\begin{bmatrix}#1\end{bmatrix}} \def\matr#1{\begin{bmatrix*}[r]#1\end{bmatrix*}} \]

Minimaxní lineární regrese

Dáno je $m$ bodů $(\_x_1,y_1),\ldots,(\_x_m,y_m)$, kde $\_x_i\in\R^n$ a $y_i\in\R$. Úkolem je nalézt takovou afinní funkci \begin{equation} f(\_x) = \_a^T\_x + b , \label{eq:f} \end{equation} parametrizovanou vektorem $\_a\in\R^n$ a skalárem $b\in\R$, která `nejlépe' aproximuje funkční závislost odpovídající daným bodům.

Je mnoho způsobů, jak formalizovat kvalitu aproximace. Určitě znáte formulaci ve smyslu nejmenších čtverců. V této úloze si jako míru kvality aproximace zvolíme maximální absolutní odchylku \begin{equation} r = \max_{i=1}^m |f(\_x_i)-y_i| . \label{eq:r} \end{equation} Cílem je nalézt parametry $\_a,b$ afinní funkce, pro které je číslo $r$ nejmenší.

Pro $n=1$ má úloha názorný geometrický význam (viz obrázek): hledáme pás s minimální šířkou (měřeno svisle), do něhož se vejdou všechny body.

Úkoly k vypracování:

  1. Úlohu (pro obecná $m,n$) převeďte na lineární program.
    Výstup úkolu (do zprávy): matematická formulace (matlabská notace není přípustná) lineárního programu a vysvětlení, proč tento program minimalizuje funkci \eqref{eq:r}.
  2. Implementujte funkci [a,b,r]=minimaxfit(x,y), kde $\_x\in\R^{n\x m}$ a $\_y\in\R^{1\x m}$ obsahují zadané dvojice $(\_x_1,y_1),\dots,(\_x_m,y_m)$, $\_a\in\R^{n\x1}$ a $b\in\R$ jsou hledané parametry funkce \eqref{eq:f}, a $r\in\R$ je minimální hodnota kritéria \eqref{eq:r}. Funkce nemá nic vypisovat ani vykreslovat. Pro řešení lineárního programu použijte matlabskou funkci linprog (která je součástí Optimalizačního toolboxu).
    Výstup úkolu: soubor minimaxfit.m.
  3. Implementujte funkci plotline(x,y,a,b,r), která pro případ $n=1$ vykreslí obrázek s body a nalezeným pásem, podle vzorového obrázku výše. Tedy $\_x,\_y\in\R^{1\x m}$. Při implementaci použijte funkce plot a hold on/off, na konci zavolejte příkaz axis tight equal. Pro účely ladění si můžete sami vytvářet množiny bodů příkazem ginput.
    Výstup úkolu: soubor plotline.m.
  4. Pro případ $n=1$ vidíme v obrázku výše, že horní modrá přímka (horní okraj pásu) prochází jedním bodem a dolní modrá přímka (dolní okraj pásu) prochází dvěma body. Zamyslete se nad tímto jevem a co nejlépe ho vysvětlete. (Proč tomu tak je? Musí tomu pro $n=1$ tak být vždy? Za jakých podmínek tomu může být jinak? Jak je to pro obecné $n$?)
    Výstup úkolu (do zprávy): vysvětlení
courses/b0b33opt/cviceni/hw/lp1/linefit/start.txt · Last modified: 2020/05/15 23:10 by wernetom