I080 Základy strukturního rozpoznávání náhodných dat

Fakulta informatiky
podzim 2000
Rozsah
2/0. 2 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k.
Vyučující
prof. M.I. Schlesinger, DrSC. (přednášející), prof. RNDr. Mojmír Křetínský, CSc. (zástupce)
doc. RNDr. Petr Sojka, Ph.D. (cvičící)
Garance
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Mojmír Křetínský, CSc.
Předpoklady
Predbězné znalosti získané samostudiem monografie: M.I. Schlesinger, V. Hlaváč "Deset přednásek z teorie statistického a strukturního rozpoznávání", Vydavatelství ČVUT Praha, 1999. - Bayesovské úlohy rozpoznávání, [SH10] 1. přednáška, str. 1-24). Přednášející doporučuje, aby si přednášku přečetli i ti, kteří si myslí, že se v bayesovských metodách již dost dobře vyznají. - Tři formulace úloh učení v rozpoznávání, [SH10] str. 103-108. - Algoritmus perceptronu a Novikoffova věta, [SH10] str. 167-168. - Algoritmy učení bez učitele a jejich analýza, [SH10] str. 240-248.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Cíle předmětu
Rozpoznávání markovských posloupností. Markovská posloupnost a autonomní stochastický automat. Rozpoznávání stochastického automatu. Vyhledávání nejpravděpodobnější posloupnosti stavů stochastického automatu podle posloupnosti jeho výstupních signálů. Vyhledávání posloupnosti nejpravděpodobnějších stavu. Vyhledávání určitého počtu nejpravděpodobnějších posloupností. Segmentace markovských posloupností. Odhad funkce závislé na posloupnosti. Podmínky pro přerušení pozorování automatu. Úlohy učení s učitelem a bez učitele pro stochastické automaty. Syntéza nejpravděpodobnější acyklické struktury markovského objektu. Rozpoznávání mnoharozměrných markovských objektů. Lokálně konjunktní funkce bez skrytých a ze skrytými proměnnými. Úloha konzistentního značkování. Relaxační značkování. Obecná úloha značkování. Algoritmus pro úlohu obecného značkování pro acyklické a jednoduché sítě. Některé třídy řešitelných úloh značkování. Triviální a ekvivalentní úlohy značkování. Řešení úloh značkování pomocí postupných ekvivalentních transformací úlohy, která končí triviálním úlohou.
Osnova
  • Část I - Rozpoznávání markovských posloupností. - Markovská posloupnost a autonomní stochastický automat. Rozpoznávání stochastického automatu (2 hodiny). - Vyhledávání nejpravděpodobnější posloupnosti stavů stochastického automatu podle posloupnosti jeho výstupních signálů (2 hodiny). - Vyhledávání posloupnosti nejpravděpodobnějších stavu (2 hodiny). - Zvláště důležité zvláštní případy úloh (4 hodiny). a) Vyhledávání určitého počtu nejpravděpodobnějších posloupností. b) Segmentace markovských posloupností. c) Odhad funkce závislé na posloupnosti. d) Podmínky pro přerušení pozorování automatu. - Úlohy učení s učitelem a bez učitele pro stochastické automaty (4 hodiny). - Syntéza nejpravděpodobnější acyklické struktury markovského objektu (2 hodiny). Část II - Rozpoznávání mnoharozměrných markovských objektů. - Lokálně konjunktní funkce bez skrytých a ze skrytými proměnnými. Úloha konzistentního značkování. Relaxační značkování. Obecná úloha značkování (4 hodiny). - Algoritmus pro úlohu obecného značkování pro acyklické a jednoduché sítě (2 hodiny). - Některé třídy řešitelných úloh značkování (2 hodiny). - Triviální a ekvivalentní úlohy značkování. Řešení úloh značkování pomocí postupných ekvivalentních transformací úlohy, která končí triviálním úlohou (4 hodiny).
Předmět je zařazen také v obdobích jaro 2002.