Strojové učení 1 ⬩ 01SU1

Aproximovaná interpolace

Máme dané nějaké body a chceme najít nějakou hezkou funkci, která jimi prochází. Dala se použít například Lagrangeova interpolace, ale ta většinou vychází dost hnusně. Abychom nějak zahrnuli hezkost funkce do úlohy, přidáme regularizační člen: například chceme minimalizovat ${\left(f^{″}\right)}^2$.

Multiclass SVM

Když máme klasifikátor rozlišující dvě třídy, jak ho zobecnit, aby dokázal rozlišit víc tříd?

One vs. one

Pro každou dvojici tříd uděláme klasifikátor mezi nimi. Problém je, že potom budou muset nějak hlasovat, co je správně, a bude to hodně výpočetně náročné.

One vs. rest

Pro každou třídu uděláme klasifikátor, který ji rozliší od ostatních.

Intrinsic multiclass

Klasifikátor uděláme tak, aby přímo rozpoznával více tříd. To se ovšem hodně blbě trénuje.

Obecně SVM klasifikátory nejsou dobré na rozlišování vícero tříd.

Bayesovský klasifikátor

Často se stane, že pro nějaké jevy $A,B$ dokážeme dobře odhadnout $P\left(A\right|B)$, ale potřebujeme $P\left(B\right|A)$. Mezi nimi můžeme snadno převádět pomocí Bayesovy věty:

Mějme náhodnou veličinu $X$, která pro jednu třídu má rozdělení $f$ a pro druhou rozdělení $g$. Klasifikátor stanovíme tak, že máme nějakou hranici $a$, přičemž pro $x<a$ zařadíme do první třídy a pro $x>a$ do druhé třídy. Potom pravděpodobnost chyby je

Klasifikace bez učení

Máme nějaká data a potřebujeme je roztřídit, aniž bychom věděli, jaké třídy jsou nebo kolik jich je.

Snažíme se tedy najít shluky. Ovšem není možné rigorózně definovat, jestli něco je shluk, takže místo toho budeme podle nějakého subjektivního kritéria porovnávat, jestli dané shlukování je dostatečně dobré.

Wardovo kritérium funguje dobře pro eliptické shluky, ale nikoliv pro nějaké divné, protože z kovarianční matice zohledňuje jen diagonálu (konkrétně počítá její stopu):

Také je důležité, že jím můžeme srovnávat jen shlukování se stejným počtem shluků! (Pokud bychom každý vzorek dali do samostatného shluku, vyšla by nula, ale to je nám samozřejmě k ničemu.)

Wardovo kritérium navíc často vytvoří jiné shluky, než jaké bychom intuitivně očekávali. Konkrétně preferuje, aby shluky měly přibližně stejné rozptyly.

Úplně se to rozbije, když jsou shluky nekonvexní a třeba je jeden uvnitř druhého.

Sekvenční shlukování je hodně špatný algoritmus, který se nikdy nepoužívá a jediná jeho výhoda je, že je rychlý.

Algoritmus N-means clustering vždy zkonverguje do lokálního minima Wardova kritéria, ale ne nutně do globálního.

Existuje i vylepšená verze N-means++, která se pokouší počáteční konfiguraci zvolit chytře. Pokud dosáhne příliš velké chyby, pravděpodobně to znamená, že data nejsou vhodná pro clustering.

Redukce dimenze

Extrakce příznaků: na původní příznaky aplikujeme nějakou funkci, například je všechny sečteme, čímž vytvoříme nové umělé příznaky, které nemají přímý význam.

Výběr příznaků: z původních příznaků zahodíme ty, které nám nepřijdou důležité.

Problém jedné třídy je, když nevíme předem, do jakých tříd máme data rozdělit (tedy je nutné provádět něco jako shlukovou analýzu).

Problém více tříd je, když máme předem dané třídy, což nám umožní snadněji vybírat potřebné příznaky.

Karhunenova–Loeveova transformace se používá na problémy jedné třídy. Myšlenka je, že pokud jsou příznaky (přibližně) lineárně závislé, tedy je mezi nimi vysoká korelace, znamená to, že některé jsou zbytečné. Snažíme se tedy nějakou lineární transformací převést data do nových souřadnic, kde už budou příznaky nekorelované, tedy kovarianční matice bude diagonální. Jelikož kovarianční matice je symetrická, můžeme ji diagonalizovat klasickými metodami a transformační matice bude ortogonální. Vlastní čísla původní kovarianční matice potom budou na diagonále té nové, takže budou odpovídat rozptylům nových příznaků. To nám umožní z nich vybrat jen pár nejvýznamnějších (těm se říká hlavní složky (principal components)). Pozor, nemusí nutně platit, že tím dosáhneme dobré separability; je to jen heuristika!

Často se to používá například u multispektrálních obrázků (např. družicové snímky). Tam máme hodně pásem, která jsou vysoce korelovaná, ale sama o sobě nic moc neříkají. Chceme-li je nějak vizualizovat, můžeme vybrat tři z nich a namapovat je na RGB, ale z toho nevznikne nic zajímavého. Pokud ovšem místo toho vezmeme tři hlavní složky, můžeme už získat hezký obrázek.

Jak určíme, kolik složek si chceme nechat? Často to je určené předem, ale pokud není, můžeme použít pravidlo kolene (elbow rule): seřadíme vlastní čísla a podíváme se, odkud dál už jsou bezvýznamná. Nebo si můžeme stanovit nějakou hranici, kolik procent z celkového součtu vlastních čísel chceme. Většinou i 90 % dostaneme z několika málo vlastních čísel.

Transformace do hlavních složek ovšem nemusí být vhodná pro klasifikaci. Data totiž můžou mít velký rozptyl i podél dimenze, která pro klasifikaci nemá význam, takže při výběru hlavních složek se zahodí ty důležitější. To se ale celkově týká problémů jedné třídy, takže není rozumný způsob, jak to vyřešit.

Na metodě hlavních složek je založena například metoda vlastních obličejů pro rozpoznávání obličejů. Máme různé fotky, které bereme jako datové vzorky a jednotlivé vzorky jako původní příznaky. Jako hlavní složky potom dostaneme vlastní obličeje. Když potom dostaneme nový obrázek, vyjádříme ho v naší nové bázi a porovnáme jeho souřadnice s ostatními. Pokud je od všeho daleko, nejspíš to vůbec není obrázek obličeje.

Další možný přístup je použití rozkladu na singulární hodnoty, kde vycházíme přímo z matice dat (tedy řádky jsou vzorky a sloupce jsou příznaky). Ukazuje se, že tím dostaneme v podstatě to samé jako z metody hlavních složek.

Pro problémy více tříd se většinou umělé příznaky nepoužívají a jen se vybírá z existujících.

Wardovo kritérium nemá smysl používat, protože teď optimalizujeme přes výběr příznaků, nikoliv přes seskupení dat, což je něco úplně jiného.

Algoritmy pro výběr příznaků se dělí na dopředné a zpětné, kde dopředné postupně vybírají příznaky, zatímco zpětné je postupně vyhazují. Zpětné se samy o sobě moc nepoužívají, protože většinou chceme vyhodit téměř všechny příznaky, což by výrazně zvýšilo složitost. Ale dají se kombinovat.

Hladový přístup pro výběr příznaků nemusí být dobrý, protože když třeba máme dva téměř stejné, které mají dobrou separabilitu, tak je algoritmus vybere oba, i když je to zbytečné.

Linear discriminant analysis funguje podobně jako metoda hlavních složek, ale místo kovarianční matice diagonalizujeme matici $W^{-1}B$.