Úkol 3

Jedním z nejpopulárnějších klasifikátorů je SVM (support vector machine). Mějme $n$ pozorování $\mathbf x_1,\dots,\mathbf x_n\in\mathbb R^d$. Pro jednoduchost předpokládejme, že se jedná o binární klasifikaci s labely $y_1,\dots,y_n\in\{-1,1\}$, a že bias je už zakomponován v datech. SVM hledá lineární oddělovací nadrovinu $\mathbf w^\top \mathbf x$ tak, že si pro každé pozorování $i$ zavede pomocnou proměnnou $\xi_i\ge 0$, která měří míru misklasifikace. Toho dosáhne pomocí podmínky $$ \xi_i \ge 1 - y_i\mathbf w^\top \mathbf x_i. $$ Vzhledem k tomu, že budeme chtít minimalizovat $\xi_i$, jeho minimální hodnoty dosáhneme pro $y_i\mathbf w^\top \mathbf x_i\ge 1$. Tedy pro label $y_i=1$ chceme podmínku $\mathbf w^\top \mathbf x_i\ge 1$ a podobně pro záporný label. Toto je silnější podmínka než klasické $\mathbf w^\top \mathbf x_i\ge 0$. Jinými slovy se SVM snaží o dosažení určité vzdálenost dobře klasifikovaných pozorování od oddělovací nadroviny, což přidává robustnost.

Celý optimalizační problém pak jde zapsat jako \begin{align*} \operatorname*{minimalizuj}_{w,\xi}\qquad &C\sum_{i=1}^n\xi_i + \frac12||\mathbf w||^2 \\ \text{za podmínek}\qquad &\xi_i \ge 1 - y_i\mathbf w^\top \mathbf x_i, \\ &\xi_i\ge 0. \end{align*} V účelové funkci se objevila regularizace $\frac12||\mathbf w||^2$ a regularizační konstanta $C>0$. I když jde tento problém řešit v této formulaci, standardně se převede do duální formulace \begin{align*} \operatorname*{maximalizuj}_{z}\qquad &-\frac12\mathbf z^\top Q\mathbf z + \sum_{i=1}^nz_i \\ \text{za podmínek}\qquad &0\le z_i\le C, \end{align*} kde matice $Q$ má prvky $q_{ij}=y_iy_j\mathbf x_i^\top \mathbf x_j$. Po vyřešení tohoto problému se řešení dostane pomocí $\mathbf w=\sum_{i=1}^ny_iz_i\mathbf x_i$.

Tento problém jde vyřešit pomocí metody coordinate descent. Tato metoda v každé iteraci updatuje pouze jednu komponentu vektoru $\mathbf z$. To znamená, že optimalizaci přes $\mathbf z$ nahradíme optimalizaci přes $\mathbf z+d\mathbf e_i$, kde $\mathbf e_i$ je nulový vektor s jedničkou na komponentě $i$. V každé iteraci se pak řeší \begin{align*} \operatorname*{maximalizuj}_d\qquad &-\frac12(\mathbf z+d\mathbf e_i)^\top Q(\mathbf z+d\mathbf e_i) + \sum_{i=1}^nz_i + d\\ \text{za podmínek}\qquad &0\le z_i + d\le C. \end{align*} Tento optimalizační problém je jednoduchý, neboť $d\in\mathbb R$ a existuje řešení v uzavřené formě.

Naimplementujte funkce Q = computeQ(X, y), w = computeW(X, y, z), z = solve_SVM_dual(Q, C; max_iter) a w = solve_SVM(X, y, C; kwargs…). Toto schéma ukazuje jak vstupní tak výstupní argumenty. Podrobněji tyto argumenty jsou:

• X: matice $n\times d$ vstupních dat;
• y: vektor $n\times 1$ vstupních labelů;
• C: kladná regularizační konstanta;
• w: řešení primárního problému $\mathbf w$;
• z: řešení duálního problému $\mathbf z$;
• Q: matice duálního problému $Q$.

Funkce computeQ spočte matici Q a funkce computeW spočte w z duálního řešení. Funkce solve_SVM_dual dostává jako vstupy parametry duálního problému a udělá max_iter iterací metody coordinate descent. V každé iteraci se popořadě spočítá $n$ updatů účelové funkce dle algoritmu. Funkce solve_SVM zkombinuje předchozí funkce do jedné.

Nakonec napište funkci w = iris(C; kwargs…), která načte iris dataset, jako pozitivní třídu bude uvažovat versicolor, jako negativní třídu virginica, jako featury použije PetalLength a PetalWidth, tyto vstupy znormuje, přidá bias a nakonec použije výše napsané funkce na spočtení optimální oddělovací nadroviny w.

Úkoly budou automaticky vyhodnocovány systémem BRUTE. Vypracovaný úkol je třeba před nahráním uložit do souboru s názvem run.jl a zabalit do formátu .zip.

Můžete použít balík RDatasets a Julia core knihovny (Statistics, LinearAlgebra, Random, …).