Rozpoznávání (33RPZ)
poslední úprava: , J. Matas



Tento document v PDF
http://cmp.felk.cvut.cz/cmp/courses/recognition/recognition.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
..

Anotace.

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.

Osnova přednášek.

  1. Formulace úlohy rozpoznávání. Základní pojmy, 'mapa' předmětu. Příklady aplikací.
  2. Bayesovká formulace rozhodování jako minimalizace střední ztráty.
  3. Nebayesovské úlohy statistického rozhodování.
  4. Odhady parametrů. Metoda maximální věrohodnosti. Bayesovské odhadování.
  5. EM algoritmus (expectation maximization).
  6. Neparametrické techniky. Metoda k nejbližších sousedů. Parzenova okna.
  7. Klasifikátory předpokládající normální rozdělení příznaků. Lineární diskriminační funkce.
  8. Neuronové sítě 1. Perceptron. Perceptronový algoritmus a jeho konvergence.
  9. Neuronové sítě 2. Vícevrstvé sítě MLP (multilayer perceptron) a RBF (radial basis functions). Učení zpětným šířením (backpropagation).
  10. Vapnikova teorie učení. Strukturální riziko.
  11. Support Vector machines.
  12. Výběr příznaků.
  13. 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').

Zpětná vazba. Vaše názory.

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.

Zápis z přednášky 00/01 a 01/02

http://cmp.felk.cvut.cz/cmp/courses/recognition/zapis_prednasky

Osnova cvičení 01/02

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

Zkouška.

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.

Tématické okruhy. Podrobny obsah předmětu s materiály.

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.
  1. Formulace úlohy rozpoznávání. Základní pojmy.
    [3] kap. 1, http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p1.ps
    1. Formulace úlohy rozpoznávání.
    2. Definice základní pojmů - třída (skrytý stav), příznak (pozorovatelný stav), rozhodovací strategie, matice ztrát, střední ztráta.
    3. Problém učení (generalizace). Trénovací a testovací množina.

  2. 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
    1. Definujte obecnou úlohy minimalizaci střední ztráty (t.j. úlohy Bayesovského rozpoznávání). Odvoďte vztah pro optimální rozhodovací pravidlo.
    2. Rozhodování podle kritéria minimální chyby. Definujte. Ukažte, ze je speciálním případem Bayesovského rozhodování.
    3. Diskriminační funkce. Definice, význam.
    4. 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
    5. Reject option (zavedení třídy 'nevím'). Definujte rozpoznávací úlohu s 'reject option'. Odvoďte optimální rozhodovací pravidlo.
    6. 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.

  3. 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
    1. Omezení a problémy Bayesovké formulace úlohy rozpoznávání
    2. Neyman-Pearsonova úloha. Formulace. Předpoklady. Definice rozhodovací strategie. Nalezení optimální strategie.
    3. Minimaxní úloha. Formulace. Předpoklady. Definice rozhodovací strategie. Nalezení optimální strategie.
    4. Waldova úloha. Formulace. Předpoklady. Definice rozhodovací strategie. Nalezení optimální strategie.
    5. Linnikova úloha. Formulace. Předpoklady. Definice rozhodovací strategie. Nalezení optimální strategie.

  4. 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
    1. Formulujte úlohu učení. Odlišnosti řízeného a neřízeného učení.
    2. Metody řízeného učení, základní principy.
    3. Metody neřízeného učení.
    4. Odhady základních statistických veličin, jejich vlastnosti.

  5. Parametrické klasifikátory.
    http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p4.ps.gz

    1. Vlastnosti bayesovského klasifikátoru při lineární transformaci prostoru měření.
    2. Nelineární diskriminační funkce.
    3. Učení lineárního klasifikátoru.

  6. 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
    1. Vlastnosti. k-NN jako estimátor hustoty pravděpodobnosti.
    2. Urychlení k-NN klasificase.
    3. Kondenzace.
    4. Asymptotická chyba.
    5. Editace.

  7. 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
    1. Perceptron. Perceptronový algoritmus a jeho konvergence.
    2. MLP (multileyer perceptron) a jeho učení metodou zpětného šíření.
    3. RBF (radial basis functions) a jejich učení

  8. 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
    1. Definice očekávané střední ztrátu a empirického risku.
    2. Definujte Vapnik-Červoněnkisovu (VC) dimenzi.
    3. Vztah empirického risku a VC dimenze.

  9. Support Vector Machines
    http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/svmBurges.ps.gz,str. 9-21
    1. Definice. Učení SVM jako minimalizace strukturálního rizika.
    2. Formulace učení SVM jako minimlazační problém.
    3. Lineární a nelineární SVM.

  10. 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
    1. Extrakce a selekce příznaků. Definice. Vlastnosti. Cíle.
    2. Extrakce příznaků pomocí Karhunen-Loevova rozvoje
    3. Fisherův lineární diskriminant.
    4. Selekce příznaků: suboptimální metody (backward and forward selection)
    5. Selekce příznaků: branch and bound
    6. Odhad pravděpodobnosti chybného rozhodnutí

  11. Shluková analýza
    [4] str. 3-32
    http://cmp.felk.cvut.cz/cmp/courses/recognition/resources/p7.ps.gz
    1. Základní skupiny algoritnů shlukové analýzy. Vysvětlete funkci typického alogritmu z každé skupiny.
    2. Typy proměnných. Metriky.
    3. Normalizace dat ve shlukové analýze, důvod použití.
    4. Algoritmus k-means.

Literatura

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