2-INF-238: Grafové modely v strojovom učení Leto 2010 Domáce úlohy

Dobrovoľné domáce úlohy je potrebné odovzdať písomne najneskôr do dátumu uvedeného pri každej úlohe do odovzdávacej schránky pod dverami M-163. Maximálny počet bodov je uvedený u každej úlohy. Nie u každej úlohy je zaručená existencia rozumného riešenia ;)

UM-1 (10 bodov) IPF algoritmus (do 21.5.2010)
Dokážte, že pri iterácii algoritmu Iterative Proportional Fitting sa nezmení normalizačná konštanta Z.

APP-2 (15/25/70 bodov) Metro (do 21.5.2010)

Predstavte si metro (so známou štruktúrou koľajísk). V jednotlivých tuneloch sa nachádzajú senzory, ktoré reagujú na prechod vozňa: každú sekundu senzor oznámi, či cez neho práve prechádza vozeň, alebo nie; môže sa stať, že v niektorých častiach jedna súprava naraz aktivuje viacero senzorov, ale aj to, že v určitých okamihoch súprava je celá medzi dvoma senzormi (t.j. vlastne nikto ju neregistruje). Senzory sú chybové, s určitou pravdepodobnosťou môžu vyslať chybný signál. Navrhnite model, pomocou ktorého by bolo možné vytvoriť dispečersku aplikáciu, ktorá sleduje, kde sa na trati nachádzajú jednotlivé vlaky. Ako by ste do vášho modelu zapracovali to, že chybovosť jednotlivých senzorov môže byť rôzna, alebo môže závisieť od aktuálneho stavu tunela (napr. v tuneli, ktorý je vlhký lebo v oblasti pršalo sú senzory chybovejšie)? Za 25 bodov: Naimplementujte jednoduchý simulátor a váš model aj s jednoduchým zobrazovaním predpokladanej polohy jednotlivých súprav. Za 70 bodov: Namiesto simulátora použite fyzický model, ktorý komunikuje s počítačom. (Musí byť lokalizovaný v Bratislave, aby som sa naň mohol prísť pozrieť.)

APP-1 (15/25/70 bodov) Lokalizácia vlaku na koľajisku (do 21.5.2010)

Predstavte si modelovú železnicu, po ktorej sa pohybuje vlak, pričom poznáte mapu koľajiska, ale neviete ako sú poprehadzované výhybky, ani kde sa vlak práve nachádza. Vlak pri prechode výhybkou pomocou senzorov zistí, či išiel po výhybke vľavo, vpravo, alebo či naopak prešiel výhybkou opačným smerom. Senzory sú však chybové, preto vlak môže s určitou pravdepodobnosťou oznámiť chybnú informáciu. Navrhnite grafový model, pomocou ktorého by bolo možné časom zistiť, kde sa vlak na koľajisku nachádza a ako sú poprehadzované výhybky. Ako by ste do vášho modelu zapracovali prípadné občasné vynechanie senzoru (t.j. vlak vôbec neoznámi, že prešiel cez výhybku), prípadne časové závislosti? Za 25 bodov: Naimplementujte jednoduchý simulátor a váš model aj s jednoduchým zobrazovaním aposteriórnej pravdepodobnosti výskytu vlaku na jednotlivých segmentoch koľajiska. Za 70 bodov: Namiesto simulátora použite fyzický model, ktorý komunikuje s počítačom. (Musí byť lokalizovaný v Bratislave, aby som sa naň mohol prísť pozrieť.)

NB-2 (10 bodov) Kombinácie diskrétnych a spojitých náhodných premenných (do 7.5.2010)
Na prednáškach sme odvodili aposteriórnu pravdepodobnosť náhodnej premennejň určujúcej triedu za predpokladu, že všetky atribúty sú buď diskrétne, alebo všetky atribúty sú Gaussovsky rozdelené. Ako to bude fungovať s kombináciami diskrétnych a spojitých premenných?

NB-1 (10 bodov) Spojité náhodné premenné (do 7.5.2020)
Pri nainvnom Bayesovskom klasifikátore sme predpokladali, že každá spojitá premenná je Gaussovsky distribuovaná, s rôznou strednou hodnotou podľa toho o ktorú triedu ide, ale s rovnakým rozptylom. Ako by vyzerala aposteriórna pravdepodobnosť, ak by sme nepredpokladali rovnaký rozptyl?

ZBS-3 (10 bodov) Ekvivalencia Bayesovských sietí (do 23.4.2010)
Ukážte, že ak máme Bayesovské siete A a B vo forme stromu, pričom siete A a B sa líšia iba zakorenením tohto stromu, tak A a B sú ekvivalentné (t.j. charakterizujú tú istú množinu pravdepodobnostných distribúcií). Viete podobné tvrdenie vymyslieť pre iné typy DAGov?

ZBS-2 (10 bodov) Správnosť a úplnosť algoritmu Bayes Ball (do 23.4.2010)
Formálne dokážte, že A#B|C práve vtedy, keď sa algoritmus Bayes Ball nevie dostať z A do B ani z B do A. (# tu označuje podmienenú nezávislosť)

ZBS-1 (10 bodov) Algebraická štruktúra podmienených nezávislostí (do 23.4.2010)

Na prednáške sme hovorili, že každá Bayesovská sieť implikuje množinu podmienených nezávislostí, ktoré jednoznačne charakterizujú distribúcie, ktoré možno pomocou danej Bayesovskej siete reprezentovať. Takýchto podmienených nezávislostí je však veľa, pričom niektoré je možné jednoducho odvodiť z iných. Je možné podmienené nezávislosti v rámci Bayesovskej siete charakterizovať pomocou malého množstva podmienených nezávislostí (nazvime ich bázových), pričom všetky ostatné je možné odvodiť z nich na základe jednoduchých prepisovacích pravidiel? Ako?

JT-2 (10 bodov) Veľkosť maximálnej kliky (do 16.4.2010)
Na zostrojenie junction tree potrebujeme chordálny graf, do nechordálneho teda pridávame ďalšie hrany, aby sa stal chordálnym. Toto môžeme robiť rôznymi spôsobmi, najlepšie sú však také, ktoré minimalizujú veľkosť najväčšej kliky vo výslednom grafe. Nájdite horný a dolný odhad najväčšej kliky v najlepšej triangulizácii a) cyklu dĺžky n b) mriežky s nxn vrcholmi.

JT-1 (10 bodov) Algoritmus na nájdenie junction tree (do 16.4.2010)
Navrhnite a analyzujte algoritmus, ktorý má na vstupe chordálny graf a zostaví jeho junction tree. Jedna možnosť je nájsť všetky maximálne kliky a ich separátory, potom zbehnúť maximálnu kostru. Pokiaľ možno by to malo bežať v čase O(n^2), alebo aspoň rýchlo pre grafy s malými klikami.

HMM-5 (5 bodov) Stavy vyšších rádov a tiché stavy (do 26.3.2010)
Je možné reprezentovať HMM so stavmi vyšších rádov a/alebo s tichými stavmi pomocou HMM bez stavov vyšších rádov a tichých stavov? Ako?

HMM-4 (5 bodov) Súčet všetkých ciest (do 26.3.2010)
Ukážte, že pre HMM s koncovým stavom je súčet pravdepodobností všetkých párov ciest a sekvencií pre všetky dĺžky dohromady je 1. Ako je to pre HMM bez koncových stavov?

HMM-3 (10 bodov) Aposteriórne dekódovanie (do 26.3.2010)
Nájdite čo najjednoduchší príklad HMM a sekvencie, kde aposteriórne dekódovanie vytvorí cestu, ktorá má nulovú pravdepodobnosť v HMM.

HMM-2 (10 bodov) Najpravdepodobnejšia stopa (do 26.3.2010)

Stopou postupnosti stavov s_1...s_n nazveme zmodifikovanú postupnosť, kde sa každá podpodpostupnosť rovnakých stavov zmodifikuje iba na jeden výskyt. Napr. postupnosti stavov aabbbabb a abbbbbab majú rovnakú stopu abab. Pravdepodobnosť stopy x je súčet pravdepodobností všetkých ciest, ktoré majú tú istú stopu x. Navrhnite algoritmus na spočítanie najpravdepodobnejšej stopy. Ak neviete nájsť efektívny algoritmus, ktorý by fungoval vo všeobecnom prípade, pokúste sa nájsť triedy HMM, pre ktoré existuje efektívny algoritmus.

HMM-1 (10 bodov) Pravdepodobnosť generovania podreťazca (do 12.3.2010)

Pre dané HMM a daný reťazec chceme vedieť rýchlo spočítať, aká je pravdepodobnosť vygenerovania podreťazca x_i..x_j počínajúc v stave s (na i-tej pozícii) a končiac v stave t (na j-tej pozícii). Triviálne je to možné urobiť v lineárnom čase. Navrhnite netriviálny algoritmus, kde pre konkrétny reťazec a konkrétne HMM najprv spustíme predspracovanie (pokiaľ možno subkvadratické), a potom budeme vedieť tieto dotazy vo forme (i,j,s,t) zodpovedať v sublineárnom čase. Ak to neviete urobiť vo všeobecnosti, tak skúste vymyslieť takýto algoritmus pre prakticky motivované špeciálne prípady.