======= Strojové učení ======= Tato úloha se skládá z části věnované **klasifikaci znaků** a **určení optimálního parametru 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|}}. ==== 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]].// ====== Určení optimálního parametru klasifikátoru ====== V zip balíčku {{:courses:b3b33kui:cviceni:strojove_uceni/kui_classification_students.zip|}} máte dán jednoduchý binární klasifikátor písmene I (soubor ''simpleIClassif.m''). Klasifikace je závislá na hodnotě parametru, který je vstupem klasifikátoru ''simpleIClassif''. Vaším úkolem je vhodně stanovit hodnotu tohoto parametru. K tomuto účelu využijte soubory ''dataI.mat'' (obrázky písmen) a ''dataI_labels.mat'' (označení zda na obrázku je I nebo ne). Formát souborů je analogický formátu z části //Klasifikace znaků//. V krátkém (rozhodně méně než jedna A4) **pdf reportu** vaší volbu parametru zdůvodněte (užijte pojmy jako např. sensitivita, falešně pozitivní, ROC křivka atd.). **Report odevzdejte do upload systému**. ====== 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.