Warning
This page is located in archive.

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

Klasifikace znaků

Některá data poskytnuta laskavostí firmy 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 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().

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

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:

  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.

Confusion Matrix

confusionMatrix() - funkce vypíše výsledky klasifikace a 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í

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.

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.

Určení optimálního parametru klasifikátoru

V zip balíčku 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.

courses/b3b33kui/cviceni/strojove_uceni/start.txt · Last modified: 2018/05/16 13:41 by strakzd1