Rozpoznávání (33RPZ)
poslední úprava: , J. Matas
Tento document v PDF
Přednáší :
J. Matas, prac. 124, tel. 24357212, matas@cmp.felk.cvut.cz
Cvičí :
V. Franc, prac. 125, tel. 24357321, xfrancv@cmp.felk.cvut.cz
O. Drbohlav, prac. 131, tel. 24357264, drobhlav@cmp.felk.cvut.cz
..
Základní úlohou rozpoznávání je nalezení strategie rozhodování
minimalizující ztrátu plynoucí z chybných rozhodnutí.
Potřebná znalost o (typicky statistickém) vztahu příznaků, t.j. pozorovatelných vlastností
objektů, a skrytých parametrů objektů (t.j. třídě) je získána učením.
Jsou představeny základní formulace úlohy rozpoznávání a principy učení.
Návrh, učení a vlastnosti základních typů klasifikátorů
(t.j. strojů realizujicí rozhodovací strategii) jsou rozebrány do hloubky.
Do této skupiny jsou zahrnuty parametrické klasifikátory, perceptron,
vícevrstvé neuronové sítě, klasifikátory
typu nejbližší soused ale i moderní klasifikátory typu support vector machines.
Tématům shlukování a výběru příznaků vhodných pro rozpoznávání
se každému věnuje jedna přenáška.
- Formulace úlohy rozpoznávání. Základní pojmy, 'mapa' předmětu. Příklady aplikací.
- Bayesovká formulace rozhodování jako minimalizace střední ztráty.
- Nebayesovské úlohy statistického rozhodování.
- Odhady parametrů. Metoda maximální věrohodnosti. Bayesovské odhadování.
- EM algoritmus (expectation maximization).
- Neparametrické techniky. Metoda k nejbližších sousedů. Parzenova okna.
- Klasifikátory předpokládající normální rozdělení příznaků. Lineární diskriminační funkce.
- Neuronové sítě 1. Perceptron. Perceptronový algoritmus a jeho konvergence.
- Neuronové sítě 2. Vícevrstvé sítě MLP (multilayer perceptron) a RBF (radial basis functions). Učení zpětným šířením (backpropagation).
- Vapnikova teorie učení. Strukturální riziko.
- Support Vector machines.
- Výběr příznaků.
- Shluková analýza.
Ke všem přednáškám jsou na WWW připraveny materiály. Odkazy na tyto
dokumenty jsou uvedeny na seznamu zkouškových otázek (viz kapitola
'Zkouškové otázky').
Velmi rád se dozvím váš názor na obsah a kvalitu přednášek a cvičení,
na zkouškové otázky, způsob hodnocení. K anonymnímu odeslání názoru můžete
použít WWW formulář
http://cmp.felk.cvut.cz/cmp/courses/recognition/feedback.html.
http://cmp.felk.cvut.cz/cmp/courses/recognition/zapis_prednasky
http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_01-02s
Cvičení z předchozích let:
01/02s http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_01-02s
00/01s http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_00-01s
00/01w http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_00-01w
99/00s http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_99-00s
98/99s http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_98-99s
97/98s http://cmp.felk.cvut.cz/cmp/courses/recognition/Lab_archive/RPZ_97-98s
Celková známka z předmětu záleží na práci ve cvičeních (10%), semestrální práci
(20%), zkouškové písemce (50%) a ústní zkoušce (20%). Seznam typických otázek
pro písemnou práci, spolu se ukázkami písemek z minulých semestrů, je k dispozici
v direktoráři
http://cmp.felk.cvut.cz/cmp/courses/recognition/Exam-questions
Okruhy k ústní části zkoušky jsou uvedeny v následující kapitole.
U každého tematického okruhu je uveden studijní materiál, a to buď
obsah přednášky v postscriptu, odkaz na ucelený studijní materiál
na WWW, nebo odkaz na dostupnou knihu (včetně rozsahu stránek). Je-li
u okruhu více než jeden odkaz, jedná se o alternativy.
- Formulace úlohy rozpoznávání. Základní pojmy.
[3] kap. 1,
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p1.ps
- Formulace úlohy rozpoznávání.
- Definice základní pojmů -
třída (skrytý stav), příznak (pozorovatelný stav),
rozhodovací strategie, matice ztrát, střední ztráta.
- Problém učení (generalizace). Trénovací a testovací množina.
- Bayesovské rozhodování
[8] str. 107-116, [9], kapitola 2.4,
str. 21-28,
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/bayes.ps.gz
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/PR-uni-arizona/lecture1.pdf
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p2.ps.gz
- Definujte obecnou úlohy minimalizaci střední ztráty (t.j.
úlohy Bayesovského rozpoznávání). Odvoďte vztah pro optimální rozhodovací
pravidlo.
- Rozhodování podle kritéria minimální chyby.
Definujte. Ukažte, ze je speciálním případem Bayesovského rozhodování.
- Diskriminační funkce. Definice, význam.
- Rozhodování podle kritéria minimální chyby pro Gaussovské rozdělení.
Odvoďte tvar diskriminační funkce, obecně a pro speciální případy -
shodná disperzní matice, stejná apriorní pravděpodobnost, diagonální
disperzní matice
- Reject option (zavedení třídy 'nevím').
Definujte rozpoznávací úlohu s 'reject option'. Odvoďte optimální
rozhodovací pravidlo.
- Chyba bayesovské strategie a její odhad. Černoffův a
Bhattachayyův odhad chyby. Metody křížového ověření (cross-validation),
metody hold-out a leave-one-out.
- Nebayesovské úlohy statistického rozhodování
[7] str. 59-63 a 114-117,
[12] 2. přednáška
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/PR-uni-arizona/lecture2.pdf
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/PR-uni-arizona/lecture3.pdf
- Omezení a problémy Bayesovké formulace úlohy rozpoznávání
- Neyman-Pearsonova úloha. Formulace. Předpoklady. Definice rozhodovací
strategie. Nalezení optimální strategie.
- Minimaxní úloha. Formulace. Předpoklady. Definice rozhodovací
strategie. Nalezení optimální strategie.
- Waldova úloha. Formulace. Předpoklady. Definice rozhodovací
strategie. Nalezení optimální strategie.
- Linnikova úloha. Formulace. Předpoklady. Definice rozhodovací
strategie. Nalezení optimální strategie.
- Učení (trénování) a odhady parametrů.
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p3.ps.gz
[1] str. 252-273, [9] str. 28-29,
[8] str. 194-210, [3] kap. 2
- Formulujte úlohu učení. Odlišnosti řízeného a neřízeného učení.
- Metody řízeného učení, základní principy.
- Metody neřízeného učení.
- Odhady základních statistických veličin, jejich vlastnosti.
- Parametrické klasifikátory.
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p4.ps.gz
- Vlastnosti bayesovského klasifikátoru při lineární
transformaci prostoru měření.
- Nelineární diskriminační funkce.
- Učení lineárního klasifikátoru.
- Neparametrické klasifikátory.
Metody nejbližšího souseda (1-NN a k-NN klasifikátor).
[9] str. 35-39, [3], kap. 2.5.4,
str. 55-57
- Vlastnosti. k-NN jako estimátor hustoty pravděpodobnosti.
- Urychlení k-NN klasificase.
- Kondenzace.
- Asymptotická chyba.
- Editace.
- Neuronové sítě.
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p12.ps.gz
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/nnBook.ps.gz,str. 1-54
- Perceptron. Perceptronový algoritmus a jeho konvergence.
- MLP (multileyer perceptron) a jeho učení metodou zpětného šíření.
- RBF (radial basis functions) a jejich učení
- Strukturální risk a VC dimenze
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/svmBurges.ps.gz,str. 1-9,
[3] kap. 9.9
- Definice očekávané střední ztrátu a empirického risku.
- Definujte Vapnik-Červoněnkisovu (VC) dimenzi.
- Vztah empirického risku a VC dimenze.
- Support Vector Machines
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/svmBurges.ps.gz,str. 9-21
- Definice. Učení SVM jako minimalizace strukturálního rizika.
- Formulace učení SVM jako minimlazační problém.
- Lineární a nelineární SVM.
- Výběr příznaků.
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/pcafld.pdf
[8] str. 131-146, 154-165 [9] str. 45-48,
[7] str. 489-501, [3] kap 8.5, 8.6
- Extrakce a selekce příznaků. Definice. Vlastnosti. Cíle.
- Extrakce příznaků pomocí Karhunen-Loevova rozvoje
- Fisherův lineární diskriminant.
- Selekce příznaků: suboptimální metody (backward and forward selection)
- Selekce příznaků: branch and bound
- Odhad pravděpodobnosti chybného rozhodnutí
- Shluková analýza
[4] str. 3-32
http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p7.ps.gz
- Základní skupiny algoritnů shlukové analýzy. Vysvětlete funkci
typického alogritmu z každé skupiny.
- Typy proměnných. Metriky.
- Normalizace dat ve shlukové analýze, důvod použití.
- Algoritmus k-means.
- 1
-
J. Andel.
Matematicka statistika.
SNTL, 1985.
- 2
-
M. R. Anderberg.
Cluster Analysis for Applications.
Academic Press, 1973.
- 3
-
Christopher M. Bishop.
Neural Networks for Pattern Recognition.
Oxford University Press, 1996.
- 4
-
C.H. Chen and L.F. Pau.
Handbook of Pattern Recognition and Computer Vision.
World Scientific, 1996.
- 5
-
Pierre Devijver and Josef Kittler.
Pattern Recogntion: A statistical approach.
Prentice Hall, 1982.
- 6
-
R. E. Duda, P. E. Hart, and DG Storck.
Pattern Classification and Scene Analysis.
John Wiley, 2001.
- 7
-
K. Fukunaga.
Introduction to Statististical Pattern Recognition.
Academic Press, 1990.
- 8
-
Zdenek Kotek, Ivan Bruha, Vaclav Chalupa, and Jan ik
Jelínek.
Adaptivní a ucici se systemy.
SNTL Praha, 1980.
- 9
-
Zdenek Kotek, Vladimír Marík, Václav Hlavác,
Josef Psutka, and Zdenek Zdráhal.
Metody rozpoznávání a jejich aplikace.
ACADEMIA Praha, 1993.
- 10
-
G. J. MacLachlan.
Discriminant analysis and statistical pattern recognition.
Wiley, 1992.
- 11
-
M Mitchel.
An Introduction to Genetic Algorithms.
Bradford Book, 1996.
- 12
-
Michail I. Schlesinger and Václav Hlavác.
Deset predmášek z teorie statistického a
strukturního rozpoznávání.
CVUT, Prague, Czech Republic, 1999.
Jiri Matas
2002-05-31