Cvičení na (příznakové) rozpoznávání

Autoři textu: Tomáš Svoboda, Tomáš Werner, David Hurych a další¹⁾
Úprava: Tibor Strašrybka²⁾

Toto je podpůrný text pro blok cvičení na (příznakové) rozpoznání, rozhodování za neurčitosti, v rámci bakalářského předmětu A3B33KUI (původně X33KUI). Přiřazení jednotlivých příkladů k prvnímu či druhému seminárnímu cvičení je pouze orientační, není závazné. Pro zájemce o hlubší znalost lze doporučit knihy [1, 3], které jsou dobře čitelné i pro bakalářského studenta. Česká kniha [5] jde více do hloubky a je výborná pro skutečné porozumění, i když vyžaduje větší úsilí při studiu. K dostání je i její anglické vydání [6]. Pro praktické použití statistického rozpoznávání doporučujeme volně dostupný toolbox pro Matlab [4].

Je známé rozdělení pravděpodobnosti výšky těla mužů a žen (viz tabulka). Odhadněte, zda člověk s výškou 168 cm (tj. L) je muž nebo žena.

$$ \begin{array}{c||l|l|l|l|l|l||c} \begin{subarray}{c} x \\ \text{cm} \end{subarray} & \begin{subarray}{c} \text{XS} \\ \text{(0–100)} \end{subarray} & \begin{subarray}{c} \text{S} \\ \text{(100–125)} \end{subarray} & \begin{subarray}{c} \text{M} \\ \text{(125–150)} \end{subarray} & \begin{subarray}{c} \text{L} \\ \text{(150–175)} \end{subarray} & \begin{subarray}{c} \text{XL} \\ \text{(175–200)} \end{subarray} & \begin{subarray}{c} \text{XXL} \\ \text{(200-}\infty\text{)} \end{subarray} & \sum \\ \hline \hline P(x|\text{muž}) & 0.05 & 0.15 & 0.2 & 0.25 & 0.3 & 0.05 & \boldsymbol 1 \\ \hline P(x|\text{žena}) & 0.05 & 0.1 & 0.3 & 0.3 & 0.25 & 0.0 & \boldsymbol 1 \\ \hline \end{array} $$

Řešte úlohu za předpokladu, že změřený člověk byl náhodně vybrán ze společnosti, ve které je 60 % mužů a 40 % žen.

Jak byste zjistili podmíněné pravděpodobnosti $P(x|s)$ případně apriorní $P(s)$?

Můžeme při měření pouhé výšky člověka dosáhnout nulové chyby rozhodování, tj. nikdy se nesplést? Pro jaké lidi bude odhad podle výšky člověka zvláště špatný?

Navrhni klasifikátor, který pomocí dvou vhodně vybraných měření na člověku odhadne, zda je to muž nebo žena. Diskutujte vhodnost možných měření.

Máme pytel starých mincí v různém stádiu opotřebení, mince stejných hodnot tedy mohou být různě veliké. Hodnota mince je nicméně okem čitelná. Máme za úkol roztřídit mince v pytli podle jejich hodnoty měřením hmotnosti mincí. Víme, že v pytli jsou mince o hodnotě 1, 2 a 5 Kč. Tedy $s \in \{1,2,5\}$. Jako ztrátovou funkci rozhodování zvolte

$$l(s, d) = |h_d - h_s|$$

kde $h_s$ je hodnota mince $s$ a $h_d$ je naše rozhodnutí o hodnotě mince.
Máme k dispozici jednoduché rychle měřící váhy, které váží s přesností 5 gramů. Rozmyslete strategii třídění (rozhodování), která povede k minimalizaci ztráty a ruční práce. Ruční práce je tu zmíněna proto, že mohu pytel roztřídit ručně, pokud požaduji absolutní přesnost. To ovšem už není možné např. v automatu na nápoje, který akceptuje mince různé hodnoty. Diskutujte vliv množství ruční práce na celkovou ztrátu způsobenou chybnými rozhodnutími.
Zkusíme odhadnout pravděpodobnou hmotnost jednotlivých hodnot mincí na základě experimentu. Náhodně vybereme 100 mincí, zvážíme je a zaznamenáme jejich hodnoty. Vytvoříme tak trénovací multimnožinu³⁾. Po zvážení trénovací multimnožiny máme k dispozici tabulku

$$ \begin{array}{c|rrrrr|c} s/x & \text{5 g} & \text{10 g} & \text{15 g} & \text{20 g} & \text{25 g} & \sum \\ \hline \text{1 Kč} & 15 & 10 & 3 & 0 & 0 & \boldsymbol{28} \\ \text{2 Kč} & 7 & 13 & 16 & 6 & 1 & \boldsymbol{43} \\ \text{5 Kč} & 0 & 1 & 2 & 11 & 15 & \boldsymbol{29} \\ \hline \sum & 22 & 24 & 21 & 17 & 16 & \boldsymbol{100} \\ \end{array} $$

Kolik je možných strategií? Váha navážila 10 gramů, do jaké třídy minci zařadíte?

Dostanete ČB obrázek o rozměrech 10×10 pixelů, z nichž každý může nabývat 256 hodnot intenzity. Jako příznaky zvolte intenzity jednotlivých pixelů. Kolik bude příznaků? Jak velká je množina možných měření? Kolik je možných strategií?
O obrázku víte, že je na něm zobrazeno jedno z písmen $S = \{A,...,Z\}$. Jak byste reprezentovali a odhadli pravděpodobnosti $P(\vec{x}|s)$?

Navrhněte klasifikátor pro řešení předchozího příkladu, který předpokládá, že příznaky jsou podmíněně nezávislé.

Dokažte, že pro ztrátovou funkci

$$ l(s,d) = \cases{ 0 & \text{když $d = s$} \cr 1 & \text{když $d \neq s$} } $$ je strategie minimalizující střední riziko stejná jako strategie maximalizující aposteriorní pravděpodobnosti $P(s|\vec{x})$.

Napište vzorcem klasifikátor, který odhadne pohlaví člověka metodou prvního nejbližšího souseda (1-NN) při dvou příznacích výška a věk. Změní se klasifikátor, když budeme měrit výšku v jiných jednotkách?

Poznámka: 1-NN je přes svou jednoduchost poměrně dobrý klasifikátor. Dá se ukázat, že asymptoticky (tj. když se velikost trénovací multimnožiny blíží $\infty$) je pravděpodobnost chybné klasifikace nejvýš dvakrát horší než v případě, kdy známe skutečné pravděpodobnosti [2].

Další možností, jak se vyhnout odhadování a reprezentaci pravděpodobností, je konstruovat přímo diskriminační funkce $g_s(x)$⁴⁾. Jedna z možností je lineární klasifikátor, kdy předepíšeme diskriminační funkce ve tvaru:

$$g_s(\vec{x})=\vec{w}_s^{\top}\vec{x}+b_s$$

kde $\vec{w}_s$ je vektor vah a skalár $b_s(x)$ je posunutí⁵⁾. Objekt $\vec{x}$ je zařazen do takové třídy $s$, jejíž hodnota diskriminační funkce $g_s(\vec{x})$ je vyšší než všech ostatních tříd. Úloha učení klasifikátoru se pak mění na optimalizační úlohu, kde hledáme takové parametry lineárních diskriminačních funkcí, které minimalizují nějaké kritérium, např. počet chybných rozhodnutí na trénovací multimnožině.

Dokažte, že u lineárního klasifikátoru je množina příznakových vektorů klasifikovaná do jediné třídy konvexní.

Lze pro trénovací multimnožinu na obrázku 1 dosáhnout lineárním klasifikátorem nulové trénovací chyby? Pokud ano, nakreslete, jak může vypadat rozdělení příznakového prostoru lineárním klasifikátorem tak, aby byla nulová trénovací chyba.

Obrázek 1: Trénovací multimnožina v příznakovém prostoru dimenze 2 a pro 4 třídy.

Úkolem je klasifikace některých písmen na registračních značkách automobilů. Předpokládáme, že značka byla již nalezena, viz obrázky 5 a 6. Obrázky písmen jsou normalizovány na velikost 10×10 pixelů. K dispozici máte trénovací data, která byla náhodně vybrána. Jasové hodnoty pixelu jsou přerovnány do řádkových vektorů po sloupcích, viz obrázek 3. Co řádek ve vstupním textovém souboru, to jeden obrázek. Soubor train.txt obsahuje příznakové vektory, soubor train_labels.txt pak odpovídající označení tříd. Obrázky jsou pouze pro náhledy, rozhodující jsou data v textových ASCII souborech. Výsledkem klasifikace bude textový soubor s označením příslušnosti ke třídě. Co řádek to jedno písmeno.
Je dobré si uvědomit, že to je obvykle vše, co dá zákazník k dispozici. Poté, co připravíte kód, zákazník, kterého v tomto případě představuje cvičící, přinese testovací data, na kterých vaši práci ohodnotí. Testovací data budou v souborech test.txt, respektive test_labels.txt. Doporučujeme odsimulovat rozdělením dat, která máte k dispozici na trénovací a testovací množinu.

Implementujte následující algoritmy a použijte pro řešení výše uvedeného problému.

Klasifikátor podle nejbližšího souseda Implementujte klasifikátor podle nejbližšího souseda. Ověřte jeho bezchybnost na trénovací množině.

Bayesovská klasifikace Implementujte naivní Bayesův klasifikátor. Předpokládejte podmíněnou nezávislost intenzit v jednotlivých pixelech. V rámci každé třídy tedy platí:

$$P(\vec{x}|s)=P(x_1|s) \cdot P(x_2|s) \dotsc P(x_n|s)$$

kde $x_i$ označuje intenzitu v $i$-tém pixelu.

K dispozici máte vzorové řešení jednoho možného klasifikátoru – perceptronu. Příklad použití je dobře vidět ve funkci main v MainFrame.java.

Obecná třída classifier obsahuje metody pro I/O operace load_matrix pro načtení příznakových vektorů, load_labels pro načtení označení správné klasifikace a pro vyhodnocení úspešnosti klasifikace, count_confusion. Každý jednotlivý klasifikátor je speciální třída, která dědí z tříd classifier. Základní metody jsou learn() a classify().

Obrázek 2: Příklady normalizovaných obrázků písmen z registračních značek automobilů.

Obrázek 3: Pixely jsou v řádkovém vektoru organizovány po sloupcích. Nejprve první sloupec, pak druhý, atd. Je zřejmé, že tmavé sloupce písmene J, které jsou na obrázku vpravo, jsou na konci vektoru dat.

Obrázek 4: Třídní diagram

Třída obsahuje metody a datové struktury společné pro všechny klasifikátory. Všechny konkrétní třídy reprezentující jednotlivé klasifikátory (bayes, nearest neighbor, perceptron) z ní dědí.

metody třídy Classifier

load_matrix(String fileName) - metoda slouží k načtení trénovacích nebo testovacích dat ze souboru, s názvem předaným ve vstupním parametru, do proměnné matrix.

load_labels(String fileName) - metoda slouží k načtení popisku k trénovacím nebo testovacím datům. Název souboru je předán jako vstupní parametr.

count_confusion() - metoda nejprve zkontroluje, zdali jsou již spočteny výsledky klasifikace. Jako parametr metodě předáme název souboru, ve kterém jsou uloženy správné popisky (labely), které chceme porovnat se spočítaným výsledkem. Program data ze souboru načte pomocí metody load_labels() a zkontroluje, jestli mají oba vektory stejný počet prvků. Po přípravné fázi (vynulování table) proběhne výpočet confusion table.

Toto rozhraní předepisuje povinnost implementace metod learn() a classify(). Každý konkrétní klasifikátor musí implementovat tato rozhraní.

MainFrame je hlavní třida, která obsahuje metodu main() v níž můžeme vytvářet instance konkrétních klasifikátorů a volat jejich metody pro učení a klasifikaci dat. Třída také obsahuje metody pro serializaci/deserializaci objektů-klasifikátorů a tím umožnuje uložit/načíst tyto objekty i s jejich naučenými parametry. Není tedy nutné před každou klasifikací spouštet časově náročné učení klasifikátoru.

metody třídy MainFrame

main()

saveClassifier(String fileName, Classifier c) - metoda umožnuje serializovat (uložit do souboru) instanci konkrétního klasifikátoru c do souboru filename.

loadClassifier(String fileName) - metoda umožnuje deserializovat (načíst uloženou instanci) klasifikátor ze souboru fileName do proměnné konkrétního klasifikátoru.

Konkrétní implementace klasifikátoru Perceptron. Třída dědí z třídy Classifier a implementuje rozhraní ClassifierInterface.

metody třídy Perceptron

learn() - metoda nejprve zkontroluje, zdali jsou načtená data v proměnné matrix a labels, aby měla s čím pracovat. Potom obsahuje přípravnou fázi, ve které je nalezen počet možných klasifikací, Klasifikace jsou namapovány na čísla a je vynulována matice w a vektor b s parametry klasifikátoru. Potom následuje část zajišťující samotné učení klasifikátoru dle algoritmu:

1. Nastav $\vec{w}_y=\vec{0}$ a $b_y=0$ pro všechna $y \in Y$ ($Y$ - množina možných klasifikací).
2. Mezi trénovacími vzory najdi libovolný špatný klasifikovaný vzor. Pokud takový vzor neexistuje, skonči, protože parametry určují klasifikátor s nulovou trénovací chybou.
3. Nechť $\vec{x}_t,y_t$ je špatně klasifikovaný vzor a ˆ$\hat{y}$ je klasifikace $\vec{x}_t$ pomocí aktuálního klasifikátoru. Adaptuj parametry klasifikátoru tak, že
   $ \eqalign{ \vec{w}_{y_t} &= \vec{w}_{y_t} + \vec{x}_t \cr b_{y_t} &= b_{y_t} + 1 \cr \vec{w}_{\hat{y}} &= \vec{w}_{\hat{y}} - \vec{x}_t \cr b_{\hat{y}}&= b_{\hat{y}} - 1 } $
4. Pokračuj krokem 2.

classify() - metoda nejprve zkontroluje, jestli je klasifikátor již naučen a zda souhlasí datové struktury. Pokud je vše v pořádku, proběhne samotná klasifikace dle vzorce

$$\hat{y}=\arg \max\limits_{y \in Y} \vec{x}_t^\top\vec{w}_y+b_y$$

a výsledek je uložen do result_labels a vypsán na standardní výstup.

Třída pro klasifikátor nearest neighbor připravená k implementaci. Výsledek klasifikace musí být uložen do vektoru result_labels (aby mohla být vypočtena confusion table).

Třída pro Bayesův klasifikátor připravená k implementaci. Výsledek klasifikace musí být uložen do vektoru result_labels (aby mohla být vypočtena confusion table).

• Implementace klasifikátoru podle nejbližšího souseda (1-NN): [0–3 body].
• Implementace Bayesovského klasifikátoru za předpokladu nezávislosti podmíněných pravděpodobností: [0–6 bodu]
• Bezchybná funkcionalita⁶⁾ i na dodaných testovacích datech: [0–1 bod].
• Bonusové body za efektivní, zajímavou implementaci, kódy navíc [0–1 bod].

Christopher M. Bishop. Pattern Recognition and Machine Learning. Springer Science+Bussiness Media, New York, NY, 2006.

T.M. Cover and P.E. Hart. Nearest neighbor pattern classification. IEEE Transactions on Information Theory, 13(1):21–27, January 1967.

Richard O. Duda, Peter E. Hart, and David G. Stork. Pattern classification. Wiley Interscience Publication. John Wiley, New York, 2nd edition, 2001.

Vojtěch Franc and Václav Hlaváč. Statistical pattern recognition toolbox for Matlab. Research Report CTU–CMP–2004–08, Center for Machine Perception, K13133 FEE. Czech Technical University, Prague, Czech Republic, June 2004. http://cmp.felk.cvut.cz/cmp/software/stprtool/index.html.

Michail I. Schlesinger and Václav Hlaváč. Deset přednášek z teorie statistického a strukturního rozpoznávání. CVUT, Prague, Czech Republic, 1999.

Michail I. Schlesinger and Václav Hlaváč. Ten Lectures on Statistical and Structural Pattern Recognition. Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002.

Obrázek 5: Příklad automatické lokalizace textu v obrazech. Více informací na http://cmp.felk.cvut.cz/~zimmerk/lpd/index.html.

Obrázek 6: Příklad komerční aplikace na rozpoznávání registračních značek ve videu. Demonstrační videa lze nalézt na adrese http://cmp.felk.cvut.cz/cmp/courses/X33KUI/Videos/RP_recognition a viděli jste také demonstraci algoritmu během prvního, demonstračního, cvičení.