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

Zadania dobrovoľných domácich úloh sa budú priebežne zjavovať na tejto stránke. 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 ;)

ZBS-6 (15 bodov) Naivný Bayesovský klasifikátor (do 25.5.2012)

a) Ukážte, že ak naivný Bayesovský klasifikátor s diskrétnymi binárnymi premennými trénujeme pomocou princípu maximálnej vierohodnosti, a potom používame na klasifikáciu tak, že vezmeme hodnotu indikačnej premennej s väčšou aposteriórnou pravdepodobnosťou, tak sa vlastne jedná o klasifikáciu s jednoduchým lineárnym klasifikátorom. Vyjadrite koeficienty explicitne. Ide o najlepší možný lineárny klasifikátor? (ukážte na príklade) b) Ukážte, že ak taký istý naivný Bayesovský klasifikátor trénujeme ako diskriminačný model (t.j. maximalizujeme podmienenú pravdepodobnosť indikačnej premennej), tak dostaneme lineárny klasifikátor práve keď obmedzíme tvar aposteriórnej distribúcie indikačnej premennej na Pr(Y=y|X=x)=1/(1+exp(--theta)), kde vektor beta a skalár theta sú parametre modelu. Ide v takomto prípade o najlepší možný lineárny klasifikátor?

APP-4 (15/30 bodov) Prepínací model evolúcie (do 25.5.2012)

Predstavte si evolúciu, pričom na každej hrane evolučného stromu sa môžu sekvencie vyvíjať pomaly (hodnota 0) alebo rýchlo (hodnota 1). Predpoklad je, že prepínanie medzi pomalou a rýchlou evolúciou nenastáva príliš často. Dáta: Máme údaje pre niekoľko génov, pričom pre každý gén a pre každú konfiguráciu pomalých/rýchlych hrán (t.j. vektor hodnôt 0 a 1, pre každú hranu jedna hodnota) sme spočítali vierohodnosť takejto kombinácie. (Vierohodnosť konfigurácie je v tomto prípade pravdepodobnosť vygenerovania bližšie nešpecifikovaných dát o danom géne v bližšie nešpecifikovanom evolučnom modeli, ktorého parametrom je práve takáto konfigurácia hrán.) Úloha: Navrhnite pravdepodobnostný model, ktorý vezme do úvahy vyššieuvedený predpoklad (má v sebe zakódované akési prepínanie rýchlej a pomalej evolúcie, pričom sa to nedeje príliš často). Popíšte algoritmus, ktorým by ste tento model trénovali. Popíšte, ako by ste urobili inferenciu (cieľom je nájsť čo najpravdepodobnejšiu konfiguráciu pre každý gén). Hint: Trénovanie môžete robiť pre všetky gény súčasne, pričom parametre vášho modelu budú pre všetky gény rovnaké. Následne inferenciu urobíte s fixovanými parametrami pre každý gén zvlášť. Za ďalších 15 bodov: Naimplementujte, aplikujte na reálne dáta uvedené nižšie a porovnajte výsledky s tým, keby ste jednoducho u každého génu vybrali konfiguráciu s najväčšou hodnotou vierohodnosti. Súbor mampam-modely obsahuje očíslovanie všetkých konfigurácií zodpovedajúcich stromu na obrázku. Súbor mampam-lnl obsahuje pre každý gén a pre každú konfiguráciu logaritmus vierohodnosti tejto konfigurácie. Konfigurácia 0,0,...,0 nie je povolená, preto sa v dátach ani nevyskytuje (vysporiadajte sa s tým buď ako s chýbajúcimi dátami, alebo jednoducho ignorujte). Strom považujte za nezakorenený (t.j. dve hrany vedúce z koreňa sú v skutočnosti súčasťou tej istej hrany s označením dog).

ZBS-5 (15+5 bodov) Spojité náhodné premenné (do 25.5.2012)

Predpokladajme Bayesovskú sieť, kde pravdepodobnostná distribúcia každej premennej je normálne rozdelenie so strednou hodnotou, ktorá je lineárnou kombináciou hodnôt jej rodičov a danou konštantnou štandardnou odchýlkou. Parametre jednotlivých lineárnych kombinácií sú parametrami modelu. Popíšte, ako by ste takúto sieť trénovali s úplnými dátami a robili v nej inferenciu (vrátane odvodenia potrebných vzorcov). Za ďalších 5 bodov: Čo by sa zmenilo, ak by niektoré premenné boli diskrétne s hodnotami 0/1, pričom rozdelenie v tomto prípade je určené tabuľkou s fixnými intervalmi hodnôt v prípade spojitých rodičov?

APP-3 (15/25/70 bodov) Metro (do 25.5.2012)

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ť.)

JT-2 (10 bodov) Veľkosť maximálnej kliky (do 23.4.2012)
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 23.4.2012)
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.

ZBS-5 (10 bodov) Ekvivalencia Bayesovských a Markovovoských sietí (do 23.4.2012)
Dokážte alebo vyvráťte: Bayesovská sieť v tvare orientovanej cesty reprezentuje presne tú istú množinu pravdepodobnostných distribúcií ako Markovovoská sieť v tvare neorientovanej cesty.

APP-2 (20 bodov) Transparency international (do 16.4.2012)
Transparency international vypísala súťaž o data mining algoritmy z verejných dát o zmluvách na ich portáli. Bližšie podmienky tu. Za max. 10 bodov: Navrhnite použitie grafových modelov na data mining v duchu tejto súťaže (zadanie úlohy a návrh riešenia). Bonus 10 bodov: Implementujte a vyskúšajte.

ZBS-4 (5 bodov) Ekvivalencia pomocou V-štruktúr II (do 11.4.2012)
Je podmienka z úlohy ZBS-3 aj nutnou podmienkou?

ZBS-3 (10 bodov) Ekvivalencia pomocou V-štruktúr (do 11.4.2012)

Ukážte, že ak dve Bayesovské siete majú rovnakú štruktúru podkladového grafu (neorientovaný graf, ktorý vznikne odstránením orientácií hrán) a súčasne rovnakú množinu V-štruktúr (dvojica hrán, ktorá smeruje do toho istého vrcholu), potom sú ekvivalentné (t.j. reprezentujú tú istú množinu distribúcií). Všimnite si, že ekvivalencia stromových Bayesovských sietí, ktorú sme rozoberali na prednáške, je špeciálnym prípadom tohto tvrdenia.

ZBS-2 (10 bodov) Správnosť a úplnosť algoritmu Bayes Ball (do 11.4.2012)
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 11.4.2012)

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?

HMM-5 (5 bodov) Stavy vyšších rádov a tiché stavy (do 11.4.2012)
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?

APP-1 (20 bodov) Spracovanie GPS trackov (do 25.3.2012)

Predstavme si GPSku, ktorá jednoducho celý deň nahráva polohové dáta. Typický turista sa dovezie na začiatok turistickej značky (napr. autom), potom si urobí túru, a potom sa zasa odvezie domov, pričom v medzičase si urobí niekoľko prestávok, kedy stojí (pri státí sa obvykle prejavujú všetky chyby GPS meraní, preto to v zázname vyzerá, ako keby turista poskakoval okolo jedného miesta ako žaba). Našou úlohou je zistiť, v ktorých časoch sa turista viezol, v ktorých sa pohyboval pešo a v ktorých stál. Za max. 10 bodov: Navrhnite riešenie založené na HMM, vrátane modelu, spôsobu trénovania a spôsobu inferencie. Podrobne riešenie popíšte a zdôvodnite, prečo si myslíte, že by mohlo fungovať. Bonus 10 bodov: Implementujte svoje riešenie, aplikujte ho na tieto dáta a pokúste sa vyhodnotiť jeho úspešnosť. Na prezentáciu dát odporúčame Google Earth (ide o skutočné dáta namerané GPSkou).

HMM-4 (10 bodov) Ťažký alebo ľahký HMM? (do 18.3.2012)
Pre HMM na obrázku nájdite polynomiálny algoritmus, ktorý hľadá najpravdepodobnejšiu anotáciu, alebo dokážte že výpočet najpravdepodobnejšej anotácie je v tomto prípade NP-ťažký.

HMM-3 (5 bodov) Súčet všetkých ciest (do 18.3.2012)
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-2 (10 bodov) Najpravdepodobnejšia stopa (do 18.3.2012)

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 18.3.2012)

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.