======= Strojové učení ======= 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 [[https://cw.felk.cvut.cz/upload/|Upload Systému]]. Obě části se odevzdávají (samostatně) do upload systému. Hodnocení viz [[.:hodnoceni|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). ====== Klasifikace znaků ====== /*podekovani??*/ Některá data poskytnuta laskavostí firmy [[http://www.eyedea.cz|Eyedea Recognition]]. ==== Problém ==== Ú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 {{:courses:b3b33kui:cviceni:strojove_uceni/kui_classification_students.zip|}}. Vyvarujte se použití built-in funkce ''sumsqr''. Tato funkce není v Matlabu, v odevzdávacím systému, dostupná. ==== Zadání samostatné práce ==== 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$. ==== Vzorové řešení – perceptronový algoritmus ==== 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()''. {{:courses:be5b33kui:labs:machine_learning:02_03_04_obr2.png?800|Příklady normalizovaných obrázků písmen z registračních značek automobilů.}} Obr. 1: //Příklady normalizovaných obrázků písmen z registračních značek automobilů.// {{:courses:be5b33kui:labs:machine_learning:02_03_04_obr3.png?800|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. 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.// ==== Popis podpůrných kódů ==== == Hlavní skript == 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é. == Klasifikátor Perceptron == 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: - Nastav $\vec{w}_y=\vec{0}$ a $b_y=0$ pro všechna $y \in Y$ ($Y$ - množina možných klasifikací). - 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. - 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 } $ - 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. == Confusion Matrix == ''confusionMatrix()'' - funkce vypíše výsledky klasifikace a [[http://en.wikipedia.org/wiki/Confusion_matrix|confusion matrix]]. Vstupem funkce jsou skutečné popisky a popisky získané klasifikací. == Klasifikátor podle nejbližšího souseda == 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. == Naivní bayesovský klasifikátor == 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. ===== Příklady použití ===== {{:courses:be5b33kui:labs:machine_learning:02_03_04_obr5.png?800|Příklad automatické lokalizace textu v obrazech. Více informací na [[http://cmp.felk.cvut.cz/~zimmerk/lpd/index.html|http://cmp.felk.cvut.cz/~zimmerk/lpd/index.html]].}} Obr. 3: //Příklad automatické lokalizace textu v obrazech. Více informací na [[http://cmp.felk.cvut.cz/~zimmerk/lpd/index.html|http://cmp.felk.cvut.cz/~zimmerk/lpd/index.html]].// {{:courses:be5b33kui:labs:machine_learning:02_03_04_obr6.png?800|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í.}} 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|http://cmp.felk.cvut.cz/cmp/courses/X33KUI/Videos/RP_recognition]].// ====== Výběr optimálního klasifikátoru ====== 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 {{:courses:b3b33kui:cviceni:strojove_uceni/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ýběr vhodného parametru === 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. === Přísně tajné! === 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. === Hlavně bezpečně === 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. ====== Relevantní zdroje ====== 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.