Priznakove-metody.md

# Příznakové metody rozpoznávání Nejlepší klasifikátor na světě se špatnými příznaky prohraje s k-NN na dobrých. Tohle je věta, kterou ti nikdo neřekne, dokud si ji sám nevyzkoušíš, a přitom rozhoduje o výsledku víc než volba algoritmu. Obrázek číslice `8×8` má 64 pixelů. Můžeš je nasypat rovnou do klasifikátoru a bude to fungovat překvapivě dobře. Můžeš z nich ale spočítat něco chytřejšího - třeba lokální binární vzory - a najednou ti stejný klasifikátor funguje i na fotkách obličejů při různém osvětlení, kde by surové pixely selhaly úplně. Tahle stránka je o tom, čím se objekt popisuje a jak se z popisu vybere to podstatné. Předpokládá to [klasifikaci a rozpoznávání](Klasifikace-a-rozpoznavani), zejména rozhodovací pravidlo `ω = d(x, q)` a diskriminační funkce. Pravděpodobnostní klasifikátory mají vlastní stránku, [Bayesovu klasifikaci](Bayesova-klasifikace). ## Příznakový vektor Obrazy objektů se reprezentují **vektory příznaků `x`** a klasifikace se dělá rozhodovacím pravidlem: ```ω = d(x)        resp.        ω = d(x, q)``` kde `x` je příznakový vektor a `q` je vektor nastavení klasifikátoru. Co všechno může být příznakem: - **přímo naměřené fyzikální veličiny** - hmotnost, délka, teplota,- **Bag of Words** - četnosti slov, buď přirozené, nebo binární,- **spektrální koeficienty** - typicky z Fourierovy transformace,- **binarizované hodnoty jasů pixelů**,- **histogramy a geometrické charakteristiky** - momenty, plochy, obvody,- **lokální binární vzory (LBP)**. Podívej se na ten seznam ještě jednou. **Jde od syrových dat k počítaným popisům a s každým krokem klesá rozměr a roste invariance.** Surové jasy pixelů se rozsypou, jakmile obrázek posuneš o pixel. Histogram jasů je vůči posunu úplně invariantní - ale zase ztratí veškerou prostorovou informaci. Návrh příznaků je hledání kompromisu mezi těmito dvěma extrémy. ## Lokální binární vzory LBP je krásná ukázka toho, jak se z chytrého nápadu stane robustní příznak. Princip: **popiš lokální texturu obrazu porovnáním jasu středového pixelu s jeho okolím.** Algoritmus: 1. Pro každý pixel vezmi jeho okolí `3×3`.2. Binarizuj sousedy vůči středu: ```s(in, ic) = 1  když in ≥ ic            0  když in < ic``` 3. Seřaď binární hodnoty po směru hodinových ručiček a převeď na dekadické číslo: ```LBP(P,R) = Σ  s(in, ic) · 2^n      pro n = 0 .. P−1``` **Klíčová vlastnost je v tom porovnání.** LBP nepracuje s absolutními hodnotami jasu, ale jen s tím, který soused je světlejší. Přinásob celý obrázek dvěma - přisvětlíš scénu - a **LBP kód se nezmění o jediný bit**. Tohle je invariance vůči monotónní změně osvětlení a je to důvod, proč LBP funguje na fotkách pořízených v různých podmínkách. Celkový algoritmus rozpoznávání pak vypadá takhle: 1. Rozdělení obrazu na bloky, například `8×8`.2. Výpočet LBP kódu pro každý pixel.3. Agregace: **histogram LBP kódů pro každý blok**.4. Konkatenace histogramů do globálního příznakového vektoru.5. Klasifikace - euklidovská vzdálenost nebo SVM. Kroky 1 a 3 spolu souvisejí a stojí za rozebrání. Histogram sám o sobě zahodí polohu. Rozdělení na bloky ji částečně vrátí - **víš, že tenhle histogram patří levému hornímu rohu**. Dostaneš tak popis, který je odolný vůči malým posunům uvnitř bloku, ale rozliší oko od úst. ## Výběr příznaků Motivace je trojí: **cena měření**, **cena výpočtu** a to hlavní - **nevhodné příznaky mohou snížit přesnost**. Ten třetí důvod je neintuitivní. Zdálo by se, že víc informace nemůže uškodit. Uškodí: příznak, který s třídou nesouvisí, přidává šum, a klasifikátor se na něm může přeučit. U [k-NN](#k-nejbližších-sousedů-k-nn) navíc každý nadbytečný rozměr ředí vzdálenosti a všechny body se stanou stejně vzdálené. ### Náhodný výběr Postupné přidávání nebo ubírání příznaků a ověření klasifikátorem. Hrubá síla, ale funguje a je to jediná metoda, která **měří to, co doopravdy chceš** - přesnost výsledného klasifikátoru. ### Dokumentová frekvence Pro textové úlohy. Term frequency: ```TF(i,j) = n(i,j) / Σk n(k,j)``` kolikrát se termín `i` vyskytl v dokumentu `j`, normalizováno délkou dokumentu. ### TF-IDF Samotné TF má vadu: slovo „a" má vysokou frekvenci ve všech dokumentech a nerozliší nic. IDF ho potlačí: ```TF-IDF = TF · IDF,        IDF(i) = log( |D| / |{j : ti ∈ dj}| )``` `|D|` je počet všech dokumentů, jmenovatel počet těch, ve kterých se termín vyskytl. **Slovo, které je ve všech dokumentech, má IDF rovné `log(1) = 0` a vypadne úplně.** Slovo, které je jen v pár dokumentech, dostane vysokou váhu. To je celá myšlenka TF-IDF: **důležité je to, co je časté tady a vzácné jinde.** ### Vzájemná informace Obecná míra závislosti mezi příznakem a třídou: ```MI(X; Y) = Σ  Σ  p(x, y) · log( p(x, y) / (p(x)·p(y)) )          y∈Y x∈X``` Když jsou `X` a `Y` nezávislé, platí `p(x,y) = p(x)·p(y)`, logaritmus je nula a `MI = 0`. **Vzájemná informace je tedy míra toho, o kolik se liší skutečnost od nezávislosti** - přesně to, co chceš u výběru příznaků vědět. Výhoda MI proti korelaci: zachytí i nelineární závislost. Nevýhoda: potřebuje odhad sdružené pravděpodobnosti, což u spojitých příznaků znamená diskretizaci a s ní další rozhodnutí. ## k-nejbližších sousedů (k-NN) Nejjednodušší použitelný klasifikátor, jaký existuje. Nemá žádné trénování - **trénovací data jsou model**. - **1-NN** - třída je určena podle nejbližšího souseda.- **k-NN** - vezme se `k` nejbližších a rozhodne většina.- Používají se různé [metriky vzdálenosti](Metriky-a-vyhodnoceni#metriky-vzdálenosti). Hranice mezi třídami je **lokální** - nedělí prostor jednou nadrovinou, ale skládá se z kousků kolem jednotlivých bodů. Proto k-NN zvládne libovolně zprohýbanou hranici, kterou by [perceptron](Neuron-a-perceptron) nikdy nenašel. **Volba `k` je kompromis.** Malé `k` (třeba 1) se přizpůsobí každému bodu včetně šumu a přeučí se. Velké `k` hranici vyhladí, ale rozmaže drobné třídy. Praktické pravidlo je zkusit několik hodnot [křížovou validací](Metriky-a-vyhodnoceni#křížová-validace) a **volit `k` liché**, aby u dvou tříd nevznikla remíza. **Kde k-NN přestává platit:** je pomalý při klasifikaci (musí spočítat vzdálenost ke všem trénovacím bodům), potřebuje mít celou trénovací množinu v paměti a **rozpadá se ve vysokých dimenzích**, kde jsou si všechny body zhruba stejně vzdálené. Na obrázcích `8×8` funguje výborně, na tisícirozměrných vektorech přestává. ## Klasifikátor na principu minimální vzdálenosti Ještě jednodušší než k-NN. Každou třídu reprezentuje **jeden vzorový obraz (etalon)** `es`, `s = 1, ..., R`, a klasifikuje se podle vzdálenosti k němu: ```ωr = ‖er − x‖ = min ‖es − x‖                s=1..R``` Ve scikit-learn se tomu říká `NearestCentroid` a etalonem je průměr trénovacích vektorů dané třídy. **Porovnání s k-NN je poučné.** Minimální vzdálenost drží `R` bodů (jeden na třídu), k-NN drží všechny. Minimální vzdálenost je proto řádově rychlejší a řádově hloupější - dělí prostor lineárně a **na třídu, která má dvě oddělená ohniska, selže úplně**, protože její průměr padne někam mezi ně. Přesně to se stane na datasetu Digits: `NearestCentroid` dá kolem 90 %, `KNeighborsClassifier(n_neighbors=3)` kolem 98 %. Rozdíl je vidět v [matici záměn](Metriky-a-vyhodnoceni#matice-záměn) - osmičky a trojky, které se píšou různě, padají na centroid. ## Klasifikační a regresní strom (CART) Popis vztahů pomocí stromu: **uzly jsou rozhodovací pravidla, listy přiřazení ke třídě**. - **Princip:** postupné dělení prostoru příznaků na menší, homogennější podoblasti.- **Rozhodování:** procházení od kořene k listu na základě testování `xj ≤ τ`.- **Dělení:** binární nebo ternární.- **Výhoda:** vysoká interpretovatelnost, tedy *white-box* model. Ta interpretovatelnost je hlavní důvod, proč se stromy pořád používají, přestože samotný strom bývá slabší než [neuronová síť](MLP-a-backpropagation). **Můžeš vytisknout cestu od kořene k listu a máš vysvětlení rozhodnutí ve tvaru, kterému rozumí i člověk, který o strojovém učení nikdy neslyšel** - „zůstatek pod 20 000 a nezaměstnaný, tedy zamítnuto". U banky nebo v medicíně to není luxus, ale požadavek. **Kde stromy přestávají platit:** jeden strom se snadno přeučí a je nestabilní - změna pár trénovacích bodů může přeskládat celý strom. Řeší se to spojením mnoha stromů do **náhodného lesa**, který je přesnější a o tu interpretovatelnost zase přijde. ## Kterou metodu kdy | Situace | Metoda ||---|---|| Málo dat, nízká dimenze, nechceš trénovat | k-NN || Potřebuješ rychlost a třídy jsou kompaktní | minimální vzdálenost || Potřebuješ vysvětlit rozhodnutí | rozhodovací strom || Hodně příznaků, textová data | [naivní Bayes](Bayesova-klasifikace) || Hodně dat, obrázky | [neuronová síť](Konvolucni-site) || Neznáš třídy | [shlukování](Shlukovani) | ## Co se na tom nejčastěji rozbije | Příznak | Kde je problém ||---|---|| Vysoká přesnost na trénovacích datech, nízká na testovacích | přeučení - u k-NN příliš malé `k`, u stromu chybí prořezání || Jeden příznak převálcuje všechny ostatní | chybí normalizace - viz [intervalové proměnné](Metriky-a-vyhodnoceni#základní-typy-dat) || Přidání příznaků zhoršilo výsledek | šumové příznaky, potřebuje výběr příznaků || Klasifikátor je ve vysoké dimenzi náhodný | prokletí dimenzionality, k-NN tam nefunguje || LBP nefunguje na hladkých plochách | LBP popisuje texturu, na plochách bez struktury nemá co měřit || Minimální vzdálenost plete dvě třídy | třída má víc ohnisek a centroid padl mezi ně | ## Co si odnést **Příznaky rozhodují víc než klasifikátor.** Dobré příznaky zachrání hloupou metodu, obráceně to neplatí. **LBP je invariantní vůči osvětlení**, protože porovnává, ne měří. **TF-IDF vyváží časté a vzácné.** Slovo ve všech dokumentech má váhu nula. **Vzájemná informace měří odchylku od nezávislosti** a zachytí i nelineární vztah. **k-NN nemá trénování, ale platí za to při klasifikaci** a ve vysoké dimenzi se rozpadá. **Strom je jediná metoda, která umí vysvětlit rozhodnutí větou.** ## Kam dál - **[Bayesova klasifikace](Bayesova-klasifikace)** - pravděpodobnostní přístup k témuž- **[Metriky a vyhodnocení](Metriky-a-vyhodnoceni)** - jak se pozná, který klasifikátor je lepší- **[Shlukování](Shlukovani)** - co dělat, když nemáš označená data- **[Konvoluční sítě](Konvolucni-site)** - metoda, která si příznaky navrhne sama- **[Nástroje pro UI](Nastroje-pro-UI)** - jak se tohle všechno napíše ve scikit-learn