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í, zejména rozhodovací pravidlo ω = d(x, q) a diskriminační funkce. Pravděpodobnostní klasifikátory mají vlastní stránku, Bayesovu klasifikaci.

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 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.

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 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í 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 - 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íť. 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

Co se na tom nejčastěji rozbije

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 - pravděpodobnostní přístup k témuž
• Metriky a vyhodnocení - jak se pozná, který klasifikátor je lepší
• Shlukování - co dělat, když nemáš označená data
• Konvoluční sítě - metoda, která si příznaky navrhne sama
• Nástroje pro UI - jak se tohle všechno napíše ve scikit-learn