Predbežné informácie k štátniciam

Na tejto stránke sú predbežné neoficiálne informácie k magisterskému štátnicovému predmetu Bioinformatika a strojové učenie pre školský rok 2018/19. Môže ešte dôjsť k nejakým zmenám (najmä v oblasti dátových štruktúr), finálna verzia by sa v prebehu pár dní mala objaviť na stránke Katedry informatiky.

Úvod

Jedným z cieľov štátnic je uvedomiť si prepojenia medzi rôznymi predmetmi. Predmety v štátnicovom predmete Bioinformatika a strojové učenie navzájom súvisia, ale tieto súvislosti sa len v malej miere ukážu priamo v osnovách jednotlivých predmetov. Preto sme vybrali články z vedeckej literatúry, ktoré spájajú témy z viacerých predmetov a budú odrazovým mostíkom pre diskusiu na štátnych skúškach. Na štátnej skúške si vylosujete jeden z nižšie uvedených článov a trojicu otázok s ním súvisiacich. V prvej otázke bude vždy vašim cieľom sumarizovať hlavné výsledky článku a vysvetliť ich aj informatikom, ktorí nie sú priamo odborníkmi v oblasti zamerania článku. V tejto otázke očakávame cca 5-minútový prehľad článku s dôrazom na vysvetlenie potrebných pojmov a základných myšlienok článku, nie technických detailov. Druhá otázka bude z nižšie uvedených okruhov učiva. Môže ale nemusí súvisieť s témou článku. Tretia otázka bude podrobne vysvetliť niektorý technický detail článku (napr. nejakú časť algoritmu, zložitejšiu definíciu, dôkaz lemy, detaily experimentu a podobne). Po vylosovaní otázky dostanete k dispozícii vytlačený článok a budete mať aspoň hodinu času na prípravu, takže nie je potrebné tieto články poznať naspamäť. Pri príprave na štátnice vám odporúčame okrem opakovania si učiva v uvedených okruhoch pozrieť si aj uvedené články a s nimi súvisiacu terminológiu.

Články

• Apostolico A, Bock ME, Lonardi S, Xu X. Efficient detection of unusual words. Journal of Computational Biology. 2000 Feb 1;7(1-2):71-94. [1]

• Štefankovič D, Vempala S, Vigoda E. A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM Journal on Computing. 2012 Apr 19;41(2):356-66. [2]

• Dowell RD, Eddy SR. Evaluation of several lightweight stochastic context-free grammars for RNA secondary structure prediction. BMC Bioinformatics. 2004 Jun 4;5(1):1. [3]

• Heng L, Durbin R. (2009): Fast and accurate short read alignment with Burrows-Wheeler transform. Bioinformatics 25(14): 1754-1760 [4]

• Wieland SC, Cassa CA, Mandl KD, Berger B. Revealing the spatial distribution of a disease while preserving privacy. Proceedings of the National Academy of Sciences. 2008 Nov 18;105(46):17608-13. [5]

• Elias I, Lagergren J. Fast neighbor joining. Theoretical Computer Science. 2009 May 17;410(21):1993-2000. [6]

• Bachem O, Lucic M, Hassani H, Krause A. Fast and provably good seedings for k-means. In Advances in Neural Information Processing Systems 2016 (pp. 55-63). [7]

• Turk M, Pentland A. Eigenfaces for recognition. Journal of cognitive neuroscience. 1991 Jan;3(1):71-86. [8]

Okruhy učiva

V zátvorke skratky súvisiacich predmetov: AOP: Aproximácia optimalizačných problémov; G: Genomika; IDZ: Integrácia dátových zdrojov; MBI: Metódy v bioinformatike; NS: Neurónové siete; PaŠ: Pravdepodobnosť a štatistika; SU: Strojové učenie; VPDŠ: Vybrané partie z dátových štruktúr

• Neurónové siete: viacvrstvový perceptrón, metóda spätného šírenia chyby, hlboké architektúry neurónových sietí (SU,NS)

• Modelovanie sekvenčných dát: Skryté Markovove modely, podmienená pravdepodobnosť a Bayesove vety, Viterbiho a dopredný algoritmus, príklady využitia v bioinformatike (hľadanie génov a profilové HMM), rekurentné neurónové siete (MBI,PaŠ,NS)

• Klasifikačné modely: support vector machines, rozhodovacie stromy, náhodné lesy, bagging, boosting (SU)

• Regresia: lineárna a generalizovaná lineárna regresia, metóda najmenších štvorcov, štatistický model s normálnym rozdelením chýb, regularizácia (PaŠ,SU)

• Teória strojového učenia: štatistický model strojového učenia, výchylka vs. rozptyl, preučenie a podučenie, PAC učenie, odhady pomocou VC dimenzie (SU,NS)

• Strojové učenie bez učiteľa: zhlukovanie, samoorganizujúce sa zobrazenia, analýza hlavných komponentov, využitie na analýzu génovej expresie (SU,NS,MBI)

• Testovanie štatistických hypotéz: Fisherov exaktný test, Welchov t-test, Mann-Whitneyho U-test, Bonferroniho korekcia viacnásobného testovania, log likelihood ratio test, príklady použitia testov v bioformatike (PaŠ,IDZ,MBI)

• Stredná hodnota náhodnej premennej: linearita strednej hodnoty, Markovova a Čebyševova nerovnosť (PaŠ)

• Limitné vety teórie pravdepodobnosti: centrálna limitná veta, Moivrova-Laplaceova veta, slabý zákon veľkých čísel (PaŠ)

• Sekvenovanie DNA: technológie sekvenovania a ich charakteristiky (Sanger, Illumina, nanopórové sekvenovanie), skladanie genómov, deBruijnove grafy, RNA-seq (MBI,G)

• Fylogenetika a komparatívna genomika: metóda spájania susedov, metóda úspornosti, Jukes-Cantorov model a iné substitučné modely, pozitívna a negatívna selekcia a jej vplyv na evolúciu biologických sekvencií (MBI, G)

• Zarovnania a algoritmy na reťazcoch: lokálne a globálne zarovnávanie sekvencií, BLAST (jadrá zarovnaní), perfektné hešovanie, Bloomov filter, efektívna reprezentácia sekvencií (sufixové stromy a polia, Burrowsova–Wheelerova transformácia, FM index) (MBI,VPDŠ)

• Metóda maximálnej vierohodnosti: odhad parametrov rozdelenia, nevychýlené odhady parametrov, metóda maximálnej vierohodnosti na rekonštrukciu fylogenetických stromov, Felsensteinov algoritmus, EM algoritmus, trénovanie skrytých Markovových modelov, hľadanie sekvenčných motívov (PaŠ, MBI)

• Lineárne programovanie: lineárne a kvadratické programovanie, simplexová metóda, dualita, celočíselné lineárne programovanie a jeho využitie na riešenie ťažkých problémov v bioinformatike, využitie lineárneho programovania v aproximačných algoritmoch (deterministické zaokrúhľovanie, iterované zaokrúhľovanie, randomizované zaokrúhľovanie + derandomizácia, primárno-duálne metódy), semidefinitné programovanie a max-cut, využitie duality v support vector machines (kernelové metódy) (AOP, SU, MBI)

• Aproximovateľnosť: Zložitostné triedy aproximačných algoritmov, PCP veta a jej použitie, AP-redukcia, APX úplné problémy, aproximovateľnosť problému obchodného cestujúceho, polynomiálne aproximačné schémy a príklady PTAS algoritmov (AOP)

• Aplikácie formálnych jazykov: Knuth-Morris-Pratt algoritmus na hľadanie vzorky v texte, stochastické bezkontextové gramatiky, kovariačný model a rodiny RNA, Nussinovovej algoritmus (MBI, VPDŠ)

• Modely dátových štruktúr: amortizovaná zložitosť a potenciálová funkcia, I/O model a B-stromy, cache-oblivious model a statický binárny strom s van Emde Boas rozložením, úsporné dátové štruktúry (rank a select) (VPDŠ)

• Dátové štruktúry pre intervaly: range minimum query, lowest common ancestor, segmentové stromy, rozsahové stromy (VPDŠ)

Príklad otázok

Príklady otázok ku článku Glorot X, Bengio Y. Understanding the difficulty of training deep feedforward neural networks. [9]

Otázka 1: Sumarizujte hlavné výsledky článku a vysvetlite, prečo je skúmaný problém dôležitý pre moderné strojové učenie (ak v odpovedi na túto otázku nevysvetlíte, čo je neurónová sieť, pravdepodobne sa vás spýtame na definíciu)

Otázka 2: Vysvetlite, čo je normalizovaná inicializácia a na obrázkoch 7 a 9 vysvetlite, aký má normalizovaná inicializácia vplyv na priebeh učenia. (bude k dispozícii projektor, na ktorom sa dajú obrázky z článku ukázať)

Otázka 3: Štatistický model strojového učenia, výchylka vs. rozptyl, preučenie a podučenie