# 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