Tato úloha se skládá z části věnované klasifikaci znaků a výběr optimálního klasifikátoru. Termín odevzdání úlohy je v Upload Systému. Obě části se odevzdávají (samostatně) do upload systému. Hodnocení viz hodnoceni. Předpokládá se, že studenti požadované metody sami implementují a nebudou využívat již hotových řešení (např. funkce fitcknn, predict).

Některá data poskytnuta laskavostí firmy Eyedea Recognition.

Ú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 3 a 4. 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 2. Co řádek ve vstupním MAT-souboru, to jeden obrázek.

Soubor train.mat obsahuje příznakové vektory, soubor train_labels.mat pak odpovídající označení tříd. Obrázky jsou pouze pro náhledy, rozhodující jsou data v MAT-souborech. Výsledek klasifikace bude ve stejném formátu jako proměnná v train_labels.mat. Obrázky v řádcích v train.mat odpovídají popiskům v train_labels.mat.

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.mat, respektive test_labels.mat. Doporučujeme odsimulovat rozdělením dat, která máte k dispozici, na trénovací a testovací množinu.

Pro implementaci použijte MATLAB. Připravené soubory jsou dostupné zde kui_classification_students.zip.

Implementujte následující algoritmy a použijte pro řešení výše uvedeného problému. Do upload systému nahrajte zip soubor s implementovanými funkcemi nnLearn(), nnClassify(), bayesLearn() a bayesClassify() ve stejnojmenných .m souborech.

Klasifikátor podle nejbližšího souseda. Implementujte klasifikátor podle nejbližšího souseda. Ověřte jeho bezchybnost na trénovací množině. (nejbližší soused ~ nearest neighbour ~ nn)

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.

Poznámka K vyhnutí se nulovým pravděpodobnostem, které jsou důsledkem relativně malé trénovací množiny, je nezbytné přidat malou kladnou hodnotu k $P(x_i|s)$ pro všechna $i$. Když se to neprovede, jedna jediná nulová pravděpodobnost $P(x_i|s)$ způsobí $P(\vec{x}|s)=0$.

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

V tomto skriptu je ukázáno, jak načíst vstupní data, natrénovat perceptron, použít ho pro klasifikaci a získat výsledky (“confusion matrix”) klasifikace.

Základní funkce jsou perceptronLearn(), perceptronClassify() a confusionMatrix().

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

Obr. 2: 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.

Hlavní skript main volá funkce učení a klasifikace pro všechny klasifikátory. Také načítá vstupní data a volá funkce pro výpis výsledků klasifikace. Skript provádí všechna potřebná volání funkcí. Nezapomeňte ale na začátku zakomentovat funkce, které na začátku nejsou ještě implementované.

Studentům je poskytnuta konkrétní implementace perceptronového klasifikátoru. Pro detailnější informace o implementaci je možné se podívat do okomentovaného zdrojové kódu.

Učení

perceptron = perceptronLearn(train, train_labels) - vstupem funkce jsou trénovací data a jejich popisky. Výstupem funkce je struktura s naučeným klasifikátorem. Funkce nejdříve vytvoří mapování z písmen (char) do čísel (“převodní tabulka”) a provede mapování z popisků ve formě písmen do číselných popisků. Samotné učení probíhá podle naásledujícího 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ý vstup a $\hat{y}$ je klasifikace $\vec{x}_t$ získaná aktuálním klasifikátorem. Uprav parametry klasifikátoru podle:
   $ \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.

Klasifikace

classLabels = perceptronClassify(perceptron, test) - vstupem funkce je struktura s naučeným klasifikátorem a testovací data. Výstupem funkce je pole s popisky tříd. Klasifikace probíhá podle

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

číselné popisky jsou převedeny na popisky písmeny a vráceny jako výstup.

confusionMatrix() - funkce vypíše výsledky klasifikace a confusion matrix. Vstupem funkce jsou skutečné popisky a popisky získané klasifikací.

Funkce nnLearn a nnClassify pro nejbližšího souseda (NN) jsou připraveny na implementaci studenty.

nn = nnLearn(train, trainLabels) - vstupem funkce jsou trénovací data a jejich popisky. Výstupem funkce je struktura a naučeným klasifikátorem.

classLabels = nnClassify(nn,test) - vstupem funkce je struktura s naučeným klasifikátorem a testovací data. Výstupem funkce je pole s popisky tříd.

Funkce bayesLearn a bayesClassify pro naivní Bayesovský klasifikátor jsou připraveny na implementaci studenty.

bayes = bayesLearn(train, train_labels) - vstupem funkce jsou trénovací data a jejich popisky. Výstupem funkce je struktura a naučeným klasifikátorem.

classLabels = bayesClassify(bayes, test) - vstupem funkce je struktura s naučeným klasifikátorem a testovací data. Výstupem funkce je pole s popisky tříd.

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

Obr. 4: 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.

Při řešení praktických úloh strojového učení máme často k dispozici více klasifikátorů a musíme se rozhodnout který je nejvhodnější pro danou úlohu. V zip balíčku kui_classification_students.zip je soubor classif_result_tables.mat (MATLAB) se kterým budete při řešení úlohy pracovat. Předpokládá se, že k řešení úlohy bude použit MATLAB. Do odevzdávacího systému se odevzdává pdf report a jedna funkce v MATLABU související s částí Hlavně bezpečně. Celková délka reportu by měla být rozhodně kratší než dvě strany A4. Doporučená délka reportu je jedna strana A4.

Mějme 5 různých natrénovaných binárních klasifikátorů. Výsledek klasifikace každého z klasifikátorů je závislý na hodnotě parametru $\alpha$. Výsledek klasifikace daného klasifikátoru lze tedy vyjádřit jako funkci $C(\bf x, \alpha) \in \{0,1\}$, kde $\bf x$ je vektor náležící vzorku který chceme klasifikovat.

Všechny klasifikátory pustíme na testovací množině $X = \{{\bf x}_1, {\bf x}_2, \dots, {\bf x}_{100} \}$. Zároveň vyzkoušíme všechny přípustné hodnoty parametru $\alpha\in\{\alpha_1, \alpha_2, \dots, \alpha_{50}\}$. Pro klasifikátor $i\in\{1,2, \dots,5\}$ dostane tabulku s hodnotami $C_i(\bf x_j,\alpha_k)\in \{0,1\}$, kde $j \in \{1, 2,.., 100\}$, $k \in \{1, 2,.., 50\}$ (viz C1, C2, C3, C4, C5 v souboru classif_result_tables.mat). Dále máme k dispozici skutečnou příslušnost vzorků $\bf x_1, \bf x_2, \dots, \bf x_{100}$ z testovací množiny (viz GT v souboru classif_result_tables.mat).

V této části předpokládejme, že klasifikátory slouží k binární klasifikaci obrázků (např. jestli je na obrázku pes). Pro klasifikátor 1 (tabulka C1) určete která hodnota parametru $\{\alpha_1, \alpha_2, \dots, \alpha_{50}\}$ je nejvhodnější. Uvědomte si, že zatím nevíte pro jakou konkrétní úlohu bude daný klasifikátor použit a proto je nutné použít dostatečně obecnou úvahu. Tedy použitá úvaha by neměla použití klasifikátoru eliminovat na jednu konkrétní úlohu.

V krátkém pdf reportu vaší volbu parametru zdůvodněte (užijte pojmy jako např. sensitivita, falešně pozitivní, ROC křivka atd.). Do reportu také vykreslete ROC křivku a na této křivce znázorněte bod, který odpovídá optimální hodnotě parametru.

Nyní si představte, že jste agent/ka 00111 a chcete k zabezpečení velmi tajných dokumentů použít svůj otisk prstu. Jedná se o velmi citlivá data, takže pokud nebudou kvalitně zabezpečena, tak bude lepší je zničit. K odemčení dat je vždy dostatek času. K dispozici máte 5 natrénovaných klasifikátorů (s různými hodnota parametru $\alpha$). Vstupem klasifikátoru je sken otisku prstu a v případě že se jedná o váš otisk prstu, tak požadovaným výstupem klasifikátoru je hodnota 1 (dojde k odemčení dat), jinak hodnota 0. Všechny klasifikátory byly otestovány na testovací množině $X$ pro všechny hodnoty parametru $\alpha$. Výsledky testu pro jednotlivé klasifikátory jsou uloženy v tabulkách C1, C2, C3, C4, C5 (viz výše). K dispozici je také skutečná příslušnost jednotlivých otisků prstů (viz GT).

Vyberte vhodný klasifikátor a jeho parametr $\alpha$.

V pdf reportu uveďte svoji volbu a vysvětlete podle jakých kritérií byla provedena.

Tato část navazuje na předchozí část Přísně tajné!. Váš kolega, také agent, se nabídne, že vám poskytne svůj klasifikátor, který je opět závislý na parametru $\alpha$. Protože není jisté jestli se nejedná o dvojitého agenta, tak bude dobré nejdříve zjistit jestli je klasifikátor lepší než klasifikátor vybraný v předchozí části.

Z bezpečnostních důvodů bude muset rozhodnutí provést předem vytvořená funkce v MATLABU. Vstupem funkce bude tabulka C6 s výsledky klasifikace na testovací množině pro různé parametry $\alpha$ (ve stejném f formátu jako C1, C2, atd.) a případně dalšími parametry dle uvážení. Výstupem funkce bude rozhodnutí, zda je nový klasifikátor lepší než ten z předchozí části (true pokud je klasifikátor lepší, jinak false). V pdf reportu vysvětlete podle jakých kritérií se bude funkce rozhodovat a odevzdejte také řešící funkci.

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áč. Ten Lectures on Statistical and Structural Pattern Recognition. Kluwer Academic Publishers, Dordrecht, The Netherlands, 2002.