1, Seznamujeme se
Celou inzenyrskou etapu jsem spojoval tranzistory a zabyval se zpracovanim signalu pomoci nejruznejsich filtru. Nyni je mi predestrena literatura obsahujici ve vztazich neuveritelne mnozstvi pismenek a pojmu, u kterych se explicitne predpoklada, ze jejich obsah je zcela zrejmy. Priznam se, ze mne zcela zrejmy neni vubec. Po prostudovani nekolika clanku a prednasek jsem dosel k zaveru, ze EM algoritmus, kteremu se mam venovat, je, napasuji-li ho na sve znalosti, ve sve podstate adaptivni filtr. Na jeho principu neni nic zarazejiciho, proste je to algoritmus, ktery modifikuje vlastni parametry, aby produkoval co nejmensi chybu. K modifikaci parametru vsak nepouziva metod LMS nebo RSA a dalsich, ktere jsou zname v oblasti filtru, ale jakousi jinou metodu e-stepu a m-stepu.
Problemy ovsem zacinaji v okamziku, kdy mam do takoveho algoritmu "zavest konecnou smes Gaussovych rozdeleni". Pokud se pohybuji v rovine filtru, je vse jasne - na vstup filtru prichazi signal x(k) a na vystupu leze signal y(k). Vztah mezi vzorkem y(k) a x(k) je dan prenosovou funkci filtru.
Tato pro me zcela samozrejma a pomerne hmatatelna predstava je vsak pro odhad parametru pravdepodobnostniho rozdeleni zcela nepouzitelna.
Nezbyva tedy nez doplnit nejderavejsi cast znalosti z oblasti statistiky. Otevrel jsem proto opet skripta Pravdepodobnost a Statistika pro inzenyry od pana Rogalewicze a na strane 116 jsem nalezl kapitolu Metoda maximalni verohodnosti (Maximum Likehood). Zde je konecne vysvetleni kompletni a uprimne nic noveho pod sluncem. Za pouziti znameho triku s derivaci hledame maximum funkce.
K dalsimu pochopeni zadani jeste nahlednu na stranu 94, kde je definice normalniho (gaussova) rozdeleni a obcerstvim si znalosti ohledne stredni hodnoty a rozptylu. Trochu zarazejici v zadani je, ze gaussovo rozdeleni je zadano pomoci stredni hodnoty a kovariancni matice (nikoli rozptylu). To bude dano s nejvetsi pravdepodobnosti tim, ze se jedna o rozdeleni - cituji zadani "mnoharozmerne" - radeji ho nazvu vicerozmerne. Definici takoveho rozdelni pak nalezneme na strane 97. Zde se nam odnekud vyrojilo pismenko ro a stale neni pouzit pojem kovariancni matice. Jak tomu tedy je doopravdy, se dozvime na strane 81 v charakterisktikach nahodneho vektoru.
Tim bychom tedy meli mit jasno ve statistice a nezbyva nez se vratit k zadani.
To nam rika, ze mame implementovat EM algoritmus pro pripad korelovanych a nekorelovanych dat, kde korelovana jsou specifikovana "plnou konvariancni matici" a nekorelovana diagonalni matici rozptylu. Jak vypada diagonalni matice jeste z hodin matematiky snad pamatujeme, po terminu "plna matice" vsak v pameti patrame zbytecne. S nejvetsi pravdepodobnosti se vsak bude jednat o matici, ktera ma vsechny prvky reprezentujici rozptyly obsazeny nenulovymi hodnotami - tedy nejedna se o matici diagonalni ani horni/dolni trojuhelnikovou.
2, EM algoritmujeme
Protoze ukolem doktorandskeho studia neni vynalezat kolo, pokusime se najit EM algoritmus ve svetove pameti. Zvlaste napomocna by nam mohla byt stranka
http://www.science.uva.nl/~vlassis/publications
, nebo jeste lepe:
http://cmp.felk.cvut.cz/~xfrancv/stprtool/html/unsuni.html
, kde se pak dozvime, ze EM algoritmus je jinak receno tez algoritmus uceni bez ucitele implementovany ve funkci unsuni (skoda jen tech nekolika hodin ztracenych pri hledani).
V napovede k funkci pak objevime malou chybicku:
"Unsupervised learning algorithm (Expectation-Maximization algorithm) finds mixture of normal distributions with independent fetures"
Na konci by melo byt zrejme "features".
3, Generujeme Gausse
Ke generovani smesi gaussovych rozdeleni muzeme pouzit fci nmix.
Bohuzel krome male chybicky v helpu:
SIGMA [Dx(kxD)] contains K covariance D-by-D matrices
melo by byt: SIGMA [Dx(KxD)] atd.
se nedozvime, jakych hodnot vlastne mohou jednotlive parametry nabyvat.
4, Odhadujeme statisticky model
Dalsi orisek na nas ceka na zacatku cvrteho bodu zadani - mame odhadnout statisticky model cislic 0 a 1. Ciste rozumove vzato, pokud by clovek nevedel nic o rozpoznavani, tak s klidem prohlasi, ze pravdepodobnost vyskytu cislice 0 a 1 je 1/10 (ac 0 ma mozna trochu vyssi pravdepodobnost) a tim by pro nej statisticky model byl u konce. Zde se vsak predpoklada nalezeni statistickeho modelu cislic 0 a 1 zaznamenanych jako obrazek tvoreny matici 8x8 bodu. Tedy statisticky model >obrazku< cislice. Zde uz s beznym rozumem nevystacime. Osobne si takovy statisticky model v tuto chvili nedokazi predstavit. Lepe na tom budeme ovsem v okamziku, kdy si rekneme napr. toto: Model cislice se bude skladat z osmi prvku (carek) reprezentujicich jednotlive radky matice obrazovych bodu. Kazdy takovy radek pak bude moci byt reprezentovan svou stredni hodnotou a rozptylem.
Z trenovaci mnoziny zjistime, jakych hodnot mohou nabyvat parametry pro jednotlive radky cislic. Tim se vytvori jakysi osmirozmerny prostor (mame osm radku obrazu), ve kterem mohou vznikat shluky bodu reprezentujich bud jednicku nebo nulu. Pokud dokazeme identifikovat nejake teziste takoveho shluku, muzeme pri dalsi klasifikaci odhadovat zda zadana cislice patri do testovaneho shluku nebo ne.
5, Klasifikujeme
K tomu, abychom mohli klasifikovat (testovat) do jakeho shluku cislice patri, muzeme pouzit tzv. bayesovsky klasifikator. Jeho implementaci opet najdeme v stprtoolboxu, kde na strance
http://cmp.felk.cvut.cz/~xfrancv/stprtool/html/bayescln.html
je v popisu k Figure 1 dalsi drobna chybicka - pouzito jednou color, jednou colour.
Ke zjisteni onoho teziste shluku z trenovacich dat si dovolim zkusit pouzit zcela obycejny prumer pres vsechny trenovaci prvky. Tedy budu mit jeden vektor strednich hodnot v 8D prostoru reprezentujici stred shluku a kovariancni matici reprezentujici rozptyl hodnot. Zkusim odvazne povazovat hodnoty za nekorelovane.
Vysledek nami provedene klasifikace tedy vypada nasledovne (prikaz emgas)
Dobre rozpoznanych NUL: 149 z 177 = 84.1808% z trenovaci mnoziny!
Dobre rozpoznanych NUL: 128 z 177 = 72.3164% z testovaci mnoziny!
Dobre rozpoznanych JEDNICEK: 112 z 149 = 75.1678% z trenovaci mnoziny!
Dobre rozpoznanych JEDNICEK: 125 z 150 = 83.3333% z testovaci mnoziny!
Tusim, ze jsem kdesi cetl, ze uspech klasifikace na trenovaci mnozine by mela byt 100%. Protoze ovsem zkusenost mi rika, ze 100% nevime nikdy nic, troufnu si tvrdit ze dany vysledek je prijatelny.
(Navic jsem se nasledne dozvedel neco o optimalizaci generalizace, coz me v mem nazoru jen utvrdilo.)
Dobre rozpoznanych cislic celkem: 514 z 653 = 78.7136%
Uprimne, nechtel bych, aby mi tento klasifikator klasifikoval neco zasadniho, protoze pravdepodobnost uspechu mi, pro rekneme kriticke rozpoznavani, prijde prilis mala, ovsem moje zkusenost s rozpoznavanim je jeste mensi, takze mohu tezko posoudit na kolik je to klasifikace dobra nebo spatna.
Diskuse: jako mnohem lepsi bych videl rozdelit obrazce na 4 kvadranty, z nich nasledne urcit stredni hodnotu atd. Dalsi varianta, ktera me napada, je moznost klasifikovat kazdy bod. Domnivam se, ze tam ale zbytecne narusta vypocetni narocnost a vysledek to nezlepsi. Je tedy treba zvolit kompromisni reseni.
Nakonec uprimne priznani - netusil jsem, co prace mi da pochopeni tohoto jednoducheho zadani a jeho vypracovani. Vsechno plyne prave z toho, co jsem napsal na zacatku - zatimco na K333 potkate bayesovsky klasifikator za kazdym rohem, je tento pojem absolventum jinych zamereni cizi. Pro absolventa zamereneho na zpracovani signalu je to nicmene zajimavy prvek, protoze v podstate navazuje na upravu signalu, ktera umoznuje zkvalitnit parametry pro pripadnou klasifikaci.