Strojové učení

Učení s učitelem

• klasifikace, regrese (základní typy úloh)
  • úloha klasifikace spočívá v přiřazení vhodné třídy (nebo sady tříd) konkrétní položce
    • typická je binární klasifikace
  • při regresi přiřazujeme položce $x$ vhodnou funkční hodnotu $y$
• standardní evaluační metriky
  • regrese
    • mean square error, $\mathrm{MSE}=\frac1N\sum_{i=1}^N (y_i-t_i)^2$
      • $y_i$ … predikce funkční hodnoty pro $x_i$
      • $t_i$ … reálná funkční hodnota pro $x_i$ (v trénovacích/testovacích datech)
  • klasifikace
    • negative log likelihood, $\mathrm{NLL}=-\sum_{i=1}^N p_i(t_i)$
      • $t_i$ … reálná třída $x_i$
      • $p_i$ … pravděpodobnostní rozdělení, které model vrací pro $x_i$ (pravděpodobnosti, že $x_i$ náleží jednotlivým třídám)
      • místo $p_i(t_i)$ lze také zapsat $p(t_i\mid x_i)$
    • accuracy (přesnost)
      • počet správně klasifikovaných ÷ celkový počet
      • $\frac{tp+tn}{tp+tn+fp+fn}$ (u binární klasifikace)
      • nevhodná metrika, pokud jsou třídy nevyvážené (např. testujeme vzácné onemocnění)
    • confusion matrix
      • řádky jsou označeny pravdivými hodnotami, sloupce predikovanými hodnotami (nebo naopak – je to potřeba uvést)
      • v každé buňce je počet testovacích dat s konkrétní kombinací targetu a predikce
      • na diagonále jsou tedy počty správně klasifikovaných testovacích dat
      • při binární klasifikaci buňky vlastně obsahují počty TP, FN, FP, TN
      • 
  • binární klasifikace (navíc)
    • základní dělení výsledků klasifikace
      • predikce je pozitivní, realita (target) rovněž → true positive (TP)
      • predikce je pozitivní, realita je negativní → false positive (FP)
      • predikce je negativní, realita je pozitivní → false negative (FN)
      • predikce je negativní, realita také → true negative (TN)
    • precision, $P=\frac{tp}{tp+fp}$
    • recall, $R=\frac{tp}{tp+fn}$
    • F-measure
      • vážený harmonický průměr precision a recallu
      • $F_\beta=\frac{(\beta^2+1)PR}{\beta^2P+R}=\frac{tp+\beta^2\cdot tp}{tp+fp+\beta^2(tp+fn)}$
      • $F_1=\frac{2PR}{P+R}=\frac{tp+tp}{tp+fp+tp+fn}$
      • je užitečné mít jednu hodnotu místo dvou ($P,R$)
    • ROC (receiver operating characteristic) křivka
      • zachycuje, jak se mění vlastnosti binárního klasifikátoru, když posouváme práh (threshold, tzn. hodnotu, od níž výsledek prohlásíme za pozitivní – typicky uvažujeme 0.5)
      • na ose $x$ je false positive rate, $\mathrm{FPR}=\frac{fp}{fp+tn}$ (v čitateli jsou všechny negativní instance)
      • na ose $y$ je true positive rate (recall), $\mathrm{TPR}=\frac{tp}{tp+fn}$
      • každý bod na křivce odpovídá jinému thresholdu
      • pro náhodný „klasifikátor“ bude ROC křivka diagonála
      • pro dokonalý klasifikátor bude ROC křivka jeden bod vlevo nahoře
        • FPR = 0, TPR = 1
    • AUC (area under curve)
      • plocha pod ROC křivkou
      • pro náhodný „klasifikátor“ je AUC = 0.5, pro dokonalý klasifikátor to bude AUC = 1
• ohodnocení modelu (testovací data, křížová validace, maximální věrohodnost)
  • testovací data slouží k ověření toho, jak dobře náš model generalizuje
    • snažíme se zjistit, jak dobré výsledky model vrací pro data, která dosud neviděl
    • testovací data nesmím použít v procesu trénování modelu a ladění hyperparametrů
  • pokud je potřeba ladit hyperparametry, používá se train-dev-test split
    • parametry modelu trénujeme na trénovacích datech
    • hyperparametry určujeme pomocí vývojových dat (zjistíme, pro které hodnoty hyperparametrů má model nejlepší výkon)
      • vývojová data se někdy označují jako validační (validation set)
    • k finálnímu vyhodnocení modelu slouží testovací data
  • pokud mám dat málo a nelze z nich jednoduše vyčlenit testovací (nebo vývojová) data, používá se křížová validce (cross-validation)
    • trénovací data rozdělím na $n$ dílů
    • model natrénuju na datech z $n-1$ dílů
    • na zbylých datech model vyhodnotím
    • proces opakuju pro $n$ možných voleb
    • jako výsledné skóre modelu použiju průměr průběžných hodnocení
  • maximální věrohodnost (maximum likelihood)
    • máme-li fixní trénovací data, pak likelihood $L(w)$ (kde $w$ jsou váhy modelu) se rovná součinu pravděpodobností targetů trénovacích dat
    • odhadujeme váhy modelu tak, aby byl likelihood (věrohodnost) trénovacích dat co největší
    • přesněji
      • pro model s fixními vahami $w$ máme pravděpodobnostní distribuci $p_\text{model}(x;w)$, že model vygeneruje $x$
      • pro model s fixními vahami $w$ a konkrétní řádek $x$ máme pravděpodobnostní distribuci $p_\text{model}(t\mid x;w)$, jak model klasifikuje $x$
      • místo toho zafixujeme trénovací data a budeme měnit váhy → dostaneme $L(w)=p_\text{model}(X;w)=\prod_i p_\text{model}(x_i;w)$
      • $w_\text{MLE}=\text{arg max}_w\,p_\text{model}(X;w)$
        • MLE … maximum likelihood estimation
• přeučení a regularizace (generalizační chyba, včasné zastavení trénování, L2 a L1 regularizace)
  • underfitting – model je příliš slabý (příliš jednoduchý), plně jsme nevyužili jeho potenciál
  • overfitting (přeučení) – model špatně generalizuje, příliš se přizpůsobil trénovacím datům
  • generalizační chyba
    • zachycuje, jak dobře model generalizuje
    • typicky odpovídá výkonu modelu na testovacích datech (případně lze k jejímu určení použít křížovou validaci)
      • výkon = vhodná metrika (F-measure, accuracy, …)
  • generalizační chybu lze zachytit v grafu vedle trénovací chyby (výkonu modelu na trénovacích datech)
    • pokud se testovací (generalizační) křivka přibližovala k trénovací a v určitý moment se začala vzdalovat, došlo k přetrénování (overfitting) modelu
      • je potřeba zesílit regularizaci nebo včas zastavit trénování
    • pokud se testovací křivka ani nezačala přibližovat, je potřeba trénovat déle
  • regularizace
    • intuice
      • penalizujeme modely s většími váhami
      • preferujeme menší změny modelu
      • omezujeme efektivní kapacitu modelu
      • čím je model složitější, tím větší má váhy
    • ke ztrátové funkci (loss :.|:;) přičteme normu vah vynásobenou parametrem $\lambda$
      • $L^1$ regularizace … $\lambda(|w_1|+|w_2|+\dots+|w_n|)$
      • $L^2$ regularizace … $\lambda(w_1^2+w_2^2+\dots+w_n^2)$
        • nebo také $\lambda\lVert w\rVert^2$, případně $\frac\lambda2\lVert w\rVert^2$, aby nám vyšla hezká derivace
  • jak bojovat s overfittingem
    • $L^2$ regularizací
    • early stoppingem (s trénováním přestaneme, když začne validační chyba růst)
    • vhodným nastavením learning ratu $\alpha$ (případně volbou rozumného learning rate schedule)
• prokletí dimenzionality
  • s rostoucím počtem dimenzí (features) potřebujeme čím dál víc (exponenciálně) trénovacích dat, aby model rozumně generalizoval
  • chceme mít v trénovacích datech několik vzorků pro každou kombinaci features → s každou další dimenzí potřebujeme násobně víc vzorků
  • k redukci počtu dimenzí se obvykle používají následující přístupy
    • filter
      • nezávislý na modelu, features vybírá na základě jejich vlastností
      • k hodnocení relevance features se používají statistické metody
        • konzistence – nemůžeme odstranit features, pokud bychom tak ztratili možnost odlišit prvky s různými targety (třídami)
        • korelace – dobré features korelují s třídami a nekorelují s jinými features
        • vzdálenost mezi třídami
        • metriky z teorie informace – např. vzájemná informace
    • wrapper
      • závislý na modelu, features vybírá tak, aby optimalizoval jeho výsledky
      • model se natrénuje, pak se vyhodnotí pomocí standardních technik (accuracy, F-measure apod.)

Učení založené na příkladech

• algoritmus k-nejbližších sousedů
  • regrese: $t=\sum_i\frac{w_i}{\sum_j w_j}\cdot t_i$
    • vážený průměr
  • klasifikace
    • pro uniformní váhy můžeme hlasovat (nejčastější třída vyhrává, remízy rozhodujeme náhodně)
    • jinak uvažujeme one-hot kódování $t_i$ opět můžeme použít predikci $t=\sum_i\frac{w_i}{\sum_j w_j}\cdot t_i$ (zvolíme třídu s největší predikovanou pravděpodobností)
  • volba vah (weighting)
    • uniform: všech $k$ nejbližších sousedů má stejné váhy
    • inverse: váhy jsou nepřímo úměrné vzdálenosti
    • softmax: váhy jsou přímo úměrné softmaxu záporných vzdáleností
  • jak určit nejbližší sousedy / vzdálenosti?
    • $p$-norma: $\|x\|_p=\sqrt[p]{\sum_i|x_i|^p}$
    • obvykle se používá $p\in\set{1,2,3,\infty}$
    • vzdálenost $x$ a $y$ pak lze určit jako $\|x-y\|_p$

Lineární regrese

• analytické řešení metodou nejmenších čtverců
  • sum of squares error: $\frac12\sum_{i}(x_i^Tw-t_i)^2$
    • lze ho zapsat jako $\frac12\lVert Xw-t\rVert^2$
  • snažíme se ho minimalizovat → hledáme hodnoty, kde je derivace chybové funkce podle každé z vah nulová
    • $\frac{\partial}{\partial w_j}\frac12\sum_{i}(x_i^Tw-t_i)^2=\sum_i x_{ij}(x_i^Tw-t_i)$
    • chceme, aby $\forall j:\sum_i x_{ij}(x_i^Tw-t_i)=0$
      • $X^T(Xw-t)=0$
      • $X^TXw=X^Tt$
  • je-li $X^TX$ invertibilní, pak lze určit explicitní řešení jako $w=(X^TX)^{-1}X^Tt$
• trénování pomocí stochastic gradient descent
  • gradient descent
    • snažíme se minimalizovat hodnotu chybové funkce $E(w)$ pro dané váhy $w$ volbou lepších vah
      • spočítáme $\nabla_wE(w)$ → tak zjistíme, jak váhy upravit
      • nastavíme $w\leftarrow w-\alpha\nabla_wE(w)$
        • $\alpha$ … learning rate (hyperparametr), „délka kroku“
      • tomu se říká gradient descent
    • standard gradient descent – používáme všechna trénovací data k výpočtu $\nabla_wE(w)$
    • stochastic (online) gradient descent – používáme jeden náhodný řádek
    • minibatch stochastic gradient descent – používáme $B$ náhodných nezávislých řádků
  • algoritmus pro trénink modelu lineární regrese (minibatch SGD)
    • náhodně inicializujeme $w$ (nebo nastavíme na nulu)
    • opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
      • samplujeme minibatch řádků s indexy $\mathbb B$
        • buď uniformně náhodně, nebo budeme chtít postupně zpracovat všechna trénovací data (to se obvykle dělá, jednomu takovému průchodu se říká epocha), tedy je nasekáme na náhodné minibatche a procházíme postupně
      • $w\leftarrow w-\alpha\frac1{|\mathbb B|}\sum_{i\in \mathbb B}((x_i^Tw-t_i)x_i)-\alpha\lambda w$
        • jako $E$ se používá polovina MSE (s $L^2$ regularizací): $E(w)=\frac1{|\mathbb B|}\sum_{i\in\mathbb B}\frac12 (x_i^Tw-t_i)^2+\frac{\lambda}2 \lVert w\rVert^2$ (stačí to zderivovat)

Logistická regrese

• binární klasifikace (sigmoid, metody trénování)
  • aktivační funkce sigmoid … $\sigma(x)=\frac1{1+e^{-x}}$
  • predikce $y(x;w)=\sigma(\bar y(x;w))=\sigma(x^Tw)$
    • správnou třídu získáme zaokrouhlením
    • přesná hodnota se rovná pravděpodobnosti, že je $x$ klasifikováno jako 1 (uvažujeme třídy 0 a 1)
    • $\bar y$ … „lineární složka“ logistické regrese
  • velikost vektoru vah $w$ odpovídá počtu features
    • nesmíme zapomenout také na bias, ten opět může být reprezentován jako další váha
  • při trénování se jako ztrátová funkce používá negative log likelihood (NLL)
    • pravděpodobnost targetu $t$ pro položku $x$ lze vyjádřit jako $p(t\mid x;w)=\sigma(x^Tw)^{t}(1-\sigma(x^Tw))^{1-{t}}$
  • algoritmus trénování pomocí minibatch SGD
    • klasifikujeme do tříd $\set{0,1}$, na vstupu máme dataset $X$ a learning rate $\alpha\in\mathbb R^+$
    • náhodně inicializujeme $w$ (nebo nastavíme na nulu)
    • opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
      • samplujeme minibatch řádků s indexy $\mathbb B$
      • $w\leftarrow w-\alpha\frac1{|\mathbb B|}\sum_{i\in \mathbb B}(\sigma(x^Tw)-t)x-\alpha\lambda w$
        • jako $E$ se používá NLL (s $L^2$ regularizací)
        • výsledek se překvapivě podobá lineární regresi
          • gradient je také $(y(x)-t)x$
• klasifikace do více tříd (softmax, metody trénování)
  • klasifikujeme do jedné z $K$ tříd
  • parametry modelu: váhová matice $W$ (sloupce odpovídají třídám, řádky featurám), vektor biasů (jeden bias za každou třídu)
  • aktivační funkce … $\text{softmax}(z)_i=\frac{e^{z_i}}{\sum_je^{z_j}}$
    • softmax je invariantní k přičtení konstanty $\text{softmax}(z+c)_i=\text{softmax}(z)_i$
    • $\sigma(x)=\text{softmax}([x,0])_0=\frac{e^x}{e^x+e^0}=\frac1{1+e^{-x}}$
  • klasifikace: $p(C_i\mid x;W)=y(x;W)_i=\text{softmax}(\bar y(x;W))_i=\text{softmax}(x^TW)_i$
    • softmax zajišťuje normalizaci (aby se pravděpodobnosti sečetly na jedničku)
  • z linearity $\bar y$ lze dokázat, že oblasti tříd jsou konvexní – nemůže se stát, že by na úsečce mezi dvěma body v jedné třídě byl bod v jiné třídě
  • algoritmus trénování pomocí minibatch SGD
    • klasifikujeme do tříd $\set{0,\dots,K-1}$, na vstupu máme dataset $X$ a learning rate $\alpha\in\mathbb R^+$
    • náhodně inicializujeme $w$ (nebo nastavíme na nulu)
    • opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
      • samplujeme minibatch řádků s indexy $\mathbb B$
      • $w\leftarrow w-\alpha\frac1{|\mathbb B|}\sum_{i\in \mathbb B}\left((\text{softmax}(x^TW)-1_t)x^T\right)^T-\alpha\lambda w$
        • jako $E$ se používá NLL (s $L^2$ regularizací)
        • srovnání gradientu logistické regrese
          • binary: $(y(x)-t)x$
          • multiclass: $((y(x)-1_t)x^T)^T$
        • přičemž $1_t$ je one-hot reprezentace targetu $t$ (tedy vektor s jedničkou na $t$-té pozici a nulami všude jinde)

Rozhodovací stromy

• algoritmus učení a kritéria větvení
  • v každém vnitřním vrcholu je uložena feature, podle které dělíme, a konkrétní hodnota, která určuje rozhraní
  • každému vrcholu náleží podmnožina trénovacích dat
    • predikce listu odpovídá tomu, jaká data v něm jsou (při regresi průměrujeme, při klasifikaci volíme největší třídu = většinové hlasování / majority vote)
  • možná kritéria větvení ve vrcholu $\mathcal T$
    • squared error criterion (používá se při regresi)
      • squared error criterion říká, jak homogenní je podmnožina trénovacích dat, která náleží vrcholu $\mathcal T$
      • $c_\text{SE}(\mathcal T)=\sum_{i\in I_\mathcal T}(t_i-\hat t_{\mathcal T})^2$
      • $I_\mathcal T$ jsou indexy řádků trénovacích dat, které náleží danému vrcholu
      • $\hat t_\mathcal T$ je průměr targetů v daném vrcholu
    • Gini index / Gini impurity (používá se při klasifikaci)
      • $c_\text{Gini}(\mathcal T)=|I_\mathcal T|\sum_kp_\mathcal T(k)(1-p_\mathcal T(k))$
      • jak často by byl náhodně vybraný prvek špatně klasifikován, kdyby byl klasifikován náhodně podle rozdělení $p_\mathcal T$
        • $p_\mathcal T(k)$ … pravděpodobnost, že vybereme prvek ze třídy $k$
        • $(1-p_\mathcal T(k))$ … pravděpodobnost, že mu přiřadíme jinou třídu než $k$
      • v binární klasifikaci Gini odpovídá squared error ztrátové funkci (skoro MSE)
    • entropy criterion (používá se při klasifikaci)
      • $c_\text{entropy}(\mathcal T)=|I_\mathcal T|\cdot H(p_\mathcal T)=-|I_\mathcal T|\sum_k p_\mathcal T(k)\log p_\mathcal T(k)$
      • ze součtu vynecháme třídy s nulovou pravděpodobností, aby nám nerozbily logaritmus
      • entropy criterion lze odvodit ze ztrátové funkce negative log likelihood (NLL)
  • algoritmus CART (Classification and Regression Trees)
    • trénovací data jsou uložena v listech
    • začneme s jedním listem
    • list můžeme rozdělit (stane se z něj vnitřní vrchol a pod něj připojíme dva nové listy)
    • list dělíme tak, aby rozdíl $c_{\mathcal T_L}+c_{\mathcal T_R}-c_{\mathcal T}$ byl co nejmenší
      • $c_\mathcal T$ … criterion současného vrcholu
      • $c_{\mathcal T_L}$ … criterion nového levého syna
      • $c_{\mathcal T_R}$ … criterion nového pravého syna
    • někdy stanovujeme omezení: maximální hloubku stromu, minimální počet dat v děleném listu (abychom nedělili zbytečně listy, co mají málo dat), maximální počet listů
      • obvykle se listy dělí prohledáváním do hloubky
      • pokud je stanoven maximální počet listů, je vhodnější je dělit ty s nejmenším rozdílem $c_{\mathcal T_L}+c_{\mathcal T_R}-c_{\mathcal T}$
  • dosud nás vždycky zajímaly parametry, které minimalizují ztrátovou funkci
  • tím, že minimalizujeme dělicí kritérium, minimalizujeme minimální dosažitelnou hodnotu ztrátové funkce pro daný strom
• prořezávání
  • prořezávání (pruning) lze použít ke zjednodušení rozhodovacího stromu, tím je možné omezit overfitting
  • prořezávat lze shora dolů nebo zespoda nahoru (bottom-up pruning × top-down pruning)
  • příklad: reduced error pruning
    • bottom-up přístup
    • na testovacích datech ověřujeme přesnost (accuracy)
    • postupně zkoušíme rušit větvení ve vnitřních vrcholech – pokud tím nedojde ke snížení přesnosti, tak změnu provedeme
      • tedy se z vnitřního vrcholu stane list, který predikuje třídu s největším počtem položek

Metoda podpůrných vektorů

• klasifikátor pro lineárně separabilní třídy
  • hard-margin SVM (support-vector machine)
  • je to kernelová (jádrová) metoda strojového učení
    • model má k dispozici spoustu polynomiálních features, aniž bychom je museli explicitně počítat
    • používáme jádrovou funkci $K$
  • model je neparametrický – využívá se duální formulace
    • nemáme váhy, ale koeficienty u trénovacích dat
    • duální formulace vychází z pozorování, že klasické váhy jsou lineárními kombinacemi trénovacích dat
  • princip je podobný jako u perceptronu
    • jedná se o binární klasifikaci do tříd $\set{-1,1}$
    • tentokrát ale chceme zajistit, aby byla dělicí nadrovina (decision boundary) co nejlepší – aby byl margin (mezera mezi nadrovinou a body) co největší
  • jak se odvozuje
    • uvažujeme váhy $w$ a bias $b$, dále mapování $\varphi$ do prostoru features, predikci označíme $y(x)=\varphi(x)^Tw+b$
    • pro všechny body chceme maximalizovat vzdálenost od decision boundary
      • váhy i bias můžeme libovolně škálovat, proto určíme, že pro body nejbližší k decision boundary bude platit $t_iy(x_i)=1$
      • díky tomu nám stačí „minimalizovat váhy“ takto: $\mathrm{argmin}_{w,b}\,\frac12\|w\|^2$
        • za předpokladu, že $t_iy(x_i)\geq 1$
    • tuhle minimalizaci s omezující podmínkou provádíme pomocí lagrangiánu a KKT podmínek
      • místo multiplikátorů $\lambda_i$ se tradičně používají $a_i$
    • díky KKT podmínkám víme, že nás při maximalizaci lagrangiánu zajímají jenom některá trénovací data – ta, která leží na okraji (support vektory)
      • je tam podmínka $a_i(t_iy(x_i)-1)=0$
      • z toho vyplývá, že pro každé $x_i$ platí $t_iy(x_i)=1$ (bod je na marginu) nebo $a_i=0$ (bod se nepoužívá k predikci)
  • predikce … $y(x)=\sum_i a_it_iK(x,x_i)+b$
• klasifikátor pro lineárně neseparabilní třídy
  • soft-margin SVM
  • v mnohém se podobá hard-margin SVM
  • dovolíme některým bodům, aby porušily pravidlo (aby byly uvnitř marginu nebo na opačné straně decision boundary)
  • pořídíme si slack variables $\xi_i\geq 0$
    • pro body, které porušují $t_iy(x_i)\geq1$ bude platit $\xi_i=|t_i-y(x_i)|$
    • jinak $\xi_i=0$
  • takže podmínku $t_iy(x_i)\geq1$ nahradíme $t_iy(x_i)\geq1-\xi_i$
  • úpravy lagrangiánu
    • musíme tam přidat další multiplikátory, které zajistí nezápornost $\xi_i$
    • výsledný lagrangián bude stejný jako minule, akorát $a_i$ (odpovídají lambdám) budou navíc omezeny shora nějakým $C$
  • support vektory teďka nebudou jenom body na okrajích marginu, ale i všechny, které mají kladné $\xi_i$ (jsou divné)
  • pozorování: $\xi_i=\max(0,1-t_iy(x_i))$
    • téhle funkci se říká hinge loss
  • soft-margin SVM lze vlastně formulovat jako $\text{argmin}_{w,b}\,C\sum_i\mathcal L_\mathrm{hinge}(t_i,y(x_i))+\frac12\|w\|^2$
    • to nám hodně připomíná klasický vzorec pro logistickou regresi apod.
    • akorát místo regularizační konstanty $\lambda$ tady máme $C$, které hraje opačnou roli (čím větší $C$, tím slabší regularizace)
  • k trénování se používá sequential minimal optimization
    • bereme řádky po jednom, k tomu $a_i$, náhodně $a_j$ a taky bias, postupně zlepšujeme lagrangián
• jádrové funkce
  • idea
    • uvažujeme duální formulaci modelu (místo vah máme koeficienty, kterými přispívají řádky trénovacích dat)
    • máme polynomiální features (pomocí zobrazení $\varphi$)
    • při predikci bychom museli $N$-krát počítat $\varphi(x_i)^T\varphi(z)$
    • když si ale například představíme features 0. až 3. řádu, tak si můžeme všimnout toho, že $\varphi(x)^T\varphi(z)=1+x^Tz+(x^Tz)^2+(x^Tz)^3$
  • zobecnění
    • budeme uvažovat kernelové funkce (kernely), které mají všechny následující vzorec (pro různé $\varphi$): $K(x,z)=\varphi(x)^T\varphi(z)$
    • kernel je tedy funkce, která dostane dva vektory a ona mi vrátí součin features těch vektorů
    • výše jsme si jeden takový kernel ukázali
  • polynomiální kernel stupně $d$ (homogenní polynomiální kernel)
    • vyrábí kombinace $d$ vstupních features
    • $K(x,z)=(\gamma x^Tz)^d$
    • $\gamma$ je hyperparametr, který škáluje features
  • polynomiální kernel stupně nejvýše $d$ (nehomogenní polynomiální kernel)
    • $K(x,z)=(\gamma x^Tz+1)^d$
  • Gaussian Radial basis function (RBF) kernel
    • obsahuje polynomiální features všech řádů
    • $K(x,z)=e^{-\gamma\|x-z\|^2}$
    • je to funkce vzdálenosti
      • pro stejné vektory vrací jedničku, pro hodně vzdálené vektory vrací nulu, pro ostatní něco mezi tím
      • dá se to interpretovat jako rozšířenou verzi algoritmu $k$ nejbližších sousedů ($k$-NN)
      • $\gamma$ ovlivňuje, co už je „moc daleko“
    • polynomiální features vysokých řádů mají nízké váhy
  • kernely se typicky používají tam, kde potřebujeme lineárně separabilní data (například v SVM) – transformují nám původní data do více dimenzí, tam už je pak obvykle můžeme rozumně separovat
• klasifikace do více tříd
  • kombinujeme několik binárních klasifikátorů
  • první možný (nepoužívaný!) přístup: one-versus-rest (ovr) schéma
    • natrénuju $K$ nezávislých binárních klasifikátorů (patří prvek konkrétní třídě? ano/ne)
    • při predikci vyberu třídu, které její klasifikátor přisuzuje největší pravděpodobnost
    • je potřeba klasifikátory kalibrovat, aby se ty pravděpodobnosti daly porovnávat!
    • takhle se to u SVM nedělá
  • alternativní přístup: one-versus-one schéma
    • klasifikátor na každou dvojici tříd, které existují
    • většinové hlasování (každý klasifikátor hlasuje pro jednu třídu)
    • klasifikátorů je víc, ale trénujeme je na méně datech

Kombinace více modelů

• bagging a boosting
  • jedná se o dva různé přístupy k trénování více modelů
  • bagging
    • modely se trénují nezávisle
    • pro každý model náhodně vybereme vzorek trénovacích dat, na nichž se učí (typicky samplujeme s opakováním = bootstrapping)
  • boosting
    • modely se trénují sekvenčně
    • snažíme se postupně opravovat chyby předchozích modelů
    • princip algoritmu AdaBoost
      • postupně trénujeme slabé klasifikátory (např. mělké rozhodovací stromy/pařezy) na vážených trénovacích datech
      • v každé iteraci upravujeme váhy trénovacích dat, aby špatně klasifikovaná data měla větší váhy
      • rovněž přiřazujeme váhy klasifikátorům podle jejich přesnosti (accuracy)
• metoda náhodných lesů
  • trénování
    • pro každý strom náhodně (s opakováním) vybereme sample trénovacích dat (= bagging)
    • pro každý vrchol náhodně vybereme podmnožinu features, které při dělení bereme v úvahu
  • predikce
    • u regrese průměrujeme hodnoty jednotlivých stromů
    • u klasifikace hlasujeme
  • les vs. strom
    • strom se dá rychle natrénovat, jeho predikci lze snadno interpretovat (jako sérii rozhodnutí)
    • les je obvykle přesnější a lépe generalizuje

Statistické testy

• studentův t-test (jednovýběrový a dvouvýběrový)
  • jednovýběrový t-test
    • způsob, jak získat intervalový odhad pro $\theta$, neznáme-li rozptyl $\sigma^2$
    • uvažujeme statistiku $T=\frac{\overline{X_n}-\theta_0}{\bar\sigma/\sqrt n}$, která má t-rozdělení s $n-1$ stupni volnosti, pokud $H_0$ platí
    • intervalový odhad
      • najdeme bodový odhad $\hat\theta$ pro $\theta$
        • třeba pokud nás zajímá $\mu$, tak prostě použijeme výběrový průměr
      • máme $n$ hodnot
      • $\delta=\frac{\bar\sigma}{\sqrt n}\cdot \Psi^{-1}_{n-1}(1-\alpha/2)$
        • kde $\Psi^{-1}_{n-1}$ je kvantilová funkce studentova t-rozdělení
      • vrátíme $[\hat\theta-\delta,\hat\theta+\delta]$
        • v tomto intervalu bude pravděpodobně reálná hodnota $\theta$ pro populaci, z níž jsme data vybrali
    • testování hypotézy
      • např. pokud ověřujeme, že se střední hodnota rovná nějaké konstantě, tak konstantu i výběrový průměr dosadíme do vzorce pro $T$
      • $H_0$ … $T$ má t-rozdělení s $n-1$ stupni volnosti
      • $H_0$ zamítáme, když je spočítaná hodnota statistiky větší než kritická hodnota
    • poznámka: proč uvažujeme $n-1$ stupňů volnosti, když máme $n$ hodnot?
      • z $n-1$ hodnot můžu $n$-tou hodnotu dopočítat
  • dvouvýběrový t-test
    • můžeme testovat třeba to, jestli se rovnají střední hodnoty parametru $\theta$ u dvou různých populací (samplujeme nezávisle, vzorků může být různý počet)
    • např. $H_0$ … $\mu_X=\mu_Y$
    • opět uvažujeme testovou statistiku $T$ s t-rozdělením
      • $T=\frac{\overline{X_n}-\overline{Y_m}}{\mathrm{SE}}$
      • přičemž $\mathrm{SE}$ je směrodatná chyba (vzorec je komplikovaný)
  • bonus: párový test
    • data jsou ve dvojicích, dvojice dat spolu nějak souvisí
    • např. $H_0$ … $\mu_X=\mu_Y$
    • uvažuju $R_i=Y_i-X_i$ (rozdíl dvojice), použiju jednovýběrový test
• chí-kvadrát test (test dobré shody)
  • Pearsonův chí-kvadrát test dobré shody
  • $O_i$ … pozorovaná četnost kategorie $i$
  • $E_i$ … očekávaná četnost kategorie $i$
  • testová statistika: $\sum_i\frac{(E_i-O_i)^2}{E_i}$
  • typická úloha: je kostka spravedlivá?
    • použijeme $\chi^2$ distribuci pro 5 stupňů volnosti
      • pokud $\chi^2$ pro naši konkrétní kostku náleží kritickému oboru $W$, prohlásíme, že kostka není spravedlivá
  • $H_0$ … pozorované četnosti jednotlivých kategorií odpovídají jejich očekávaným četnostem
  • pokud $H_0$ platí, má testová statistika rozdělení $\chi^2$ rozdělení s $n-1$ stupni volnosti, přičemž $n$ je počet kategorií
  • $H_0$ zamítáme, když je spočítaná hodnota statistiky větší než kritická hodnota

Učení bez učitele

• shlukování (algoritmus k-means)
  • algoritmus
    • na vstupu máme body $x_1,\dots,x_N$, počet clusterů $K$
    • inicializujeme středy clusterů $\mu_1,\dots,\mu_K$
      • buď náhodně (ze vstupních bodů)
      • nebo pomocí kmeans++
        • první střed se vybere náhodně (ze vstupních bodů)
        • každý další střed vybereme z nepoužitých bodů tak, že pravděpodobnost výběru každého bodu úměrně roste s druhou mocninou vzdálenosti jeho nejbližšího středu (clusteru)
    • opakujeme, dokud to nezkonverguje nebo nám nedojde trpělivost
      • body přiřadíme clusterům (každý bod přiřadíme tomu clusteru, k jehož středu má nejblíž)
      • aktualizujeme středy clusterů (vždy zprůměrujeme body, které jsme danému clusteru přiřadili)
  • použití
    • $K$-means se používá ke clusteringu, tedy k dělení dat do skupin, clusterů
    • je to technika učení bez učitele (unsupervised), neznáme targety
    • konkrétní příklady: seskupení pixelů podobné barvy, určení skupin zákazníků
  • ztrátová funkce, kterou algoritmus optimalizuje
    • $J=\sum_{i=1}^N\sum_{k=1}^Kz_{i,k}\|x_i-\mu_k\|^2$
    • kde $z_{i,k}$ je indikátor přiřazení bodu $x_i$ do clusteru $k$
  • konvergence
    • aktualizace přiřazení bodů ke clusterům nezvyšuje loss
    • aktualizace středů clusterů nezvyšuje loss
    • takže $K$-means konverguje k lokálnímu optimu
• hierarchické shlukování
  • dva přístupy: postupné spojování menších shluků (aglomerativní shlukování) nebo naopak dělení velkých shluků na menší (divisivní shlukování) podle zadaných pravidel
  • algoritmus spojování menších clusterů/shluků
    • na začátku je každý cluster singleton (patří tam jeden bod)
    • slučujeme nejpodobnější clustery, dokud nezískáme cílový počet clusterů
  • dají se používat různé metriky podobnosti shluků (např. vzdálenost mezi centroidy shluků nebo přímo mezi jejich body, průměry vzdáleností, …)
  • příklady algoritmů divisivního shlukování
    • DIANA (divisive analysis)
      • na začátku jsou všechny body v jednom clusteru
      • v něm najdeme bod, který se nejvíc liší od všech ostatních a oddělíme ho do samostatného clusteru
      • do téhož (nového) clusteru po jednom přidáváme i další body z původního clusteru, pokud se více hodí do nového clusteru (jsou mu blíže než původnímu)
    • principal directions divisive partitioning (PDDP)
      • používá princip PCA – dělí clustery pomocí projekce na hlavní komponenty
  • většinou se jedná o hladové algoritmy → nelze zaručit, že je řešení optimální
• redukce dimenzionality (analýza hlavních komponent)
  • singulární rozklad (SVD, singular value decomposition)
    • mějme matici $X\in\mathbb R^{m\times n}$ s hodností $r$
    • $X=U\Sigma V^T$
      • $U\in\mathbb R^{m\times m}$ ortonormální
      • $\Sigma\in\mathbb R^{m\times n}$ diagonální matice s nezápornými hodnotami (tzv. singulárními čísly) zvolenými tak, aby byly uspořádány sestupně
      • $V\in\mathbb R^{n\times n}$ ortonormální
    • možný pohled na dekompozici
      • $X=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\dots+\sigma_ru_rv_r^T$
      • $\sigma_i$ … $i$-té singulární číslo
      • $u_i$ … $i$-tý sloupec matice $U$
      • $v_i^T$ … $i$-tý řádek matice $V^T$
    • redukovaná verze SVD
      • $\sigma$ označme vektor singulárních čísel
      • pro matici $X$ s hodností $r$ bude v tom vektoru nejvýše $r$ nenulových hodnot
      • tedy matici $\Sigma$ můžeme redukovat na rozměry $r\times r$, podobně $U$ můžeme redukovat na $m\times r$ a $V^T$ na $r\times n$, touto kompresí nepřijdeme o žádné informace
    • dokonce můžeme $\Sigma$ zmenšit ještě víc
      • zvolíme $k\lt r$
      • necháme jenom $k$ největších singulárních čísel, všechny ostatní zahodíme
      • tím už se nějaké informace ztratí
      • budeme mít aproximaci původní matice $X$, ta aproximace bude mít hodnost $k$
  • algoritmus určení PCA (principal component analysis) $M$-té dimenze na základě datové matice $X$
    • spočteme SVD matice $(X-\bar x)$
      • kde $\bar x$ je průměr řádků matice (vektor průměrných hodnot jednotlivých features)
      • k určení SVD (respektive nalezení $V$) lze použít algoritmus power iteration
        • do proměnné $S$ uložíme kovarianční matici $\text{cov}(X)=\frac 1N(X-\bar x)^T(X-\bar x)$
        • pro každou komponentu hledáme vektor $v_i$ (sloupec matice $V$) tak, že začneme s náhodným vektorem a poté ho zleva násobíme maticí $S$ a normalizujeme (dělíme vlastní normou), dokud to nezkonverguje
        • od matice $S$ na konci každého kroku odečteme $\lambda_iv_iv_i^T$, kde $\lambda_i$ je norma vektoru $v_i$ před poslední normalizací
    • necháme prvních $M$ řádků $V^T$, ostatní zahodíme (takže $V$ bude mít $M$ sloupců)
    • pokud chceme získat hodnoty nových $M$ komponent, tak stačí vynásobit $XV$, tak dostaneme matici $N\times M$
    • funguje to díky tomu, že pomocí SVD matice $(X-\bar x)$ získáváme vlastní vektory kovarianční matice $\text{cov}(X)=\frac 1N(X-\bar x)^T(X-\bar x)$
  • aplikace PCA
    • aproximace matic
    • snížení šumu v datech
    • redukce dimenzí dat, extrakce features
    • vizualizace dat
    • praktické použití: doporučovací systémy
  • příklad použití PCA
    • 
    • PCA postupně hledá osy s největším rozptylem