Dávid Pál (Google New York): Online problémy v strojovom učení

Online strojové učenie je matematický model, kde agent robí predpovede zároveň s tým ako prijíma dáta. Kľúčovým faktorom je rýchlosť konvergencie agenta k optimálnemu offline riešeniu. Zrekapitulujem niekoľko klasických problémov: učenie sa s pomocou expertov, problém mnohorukého banditu. Načrtnem súvislosti s inými oblasťami aplikovanej matematiky: gradientné metódy z optimalizácie, opakované hry a kompetitívna analýza online algoritmov. V druhej časti sa budem zaoberať opakovanými hrami s neúplnou informáciou, čo je zovšeobecnenie predchádzajúcich modelov. Pred dvoma rokmi sme ja, András Antos, Gábor Bartok, Dean Foster, Alexander Rakhlin, a Csaba Szepesvari klasifikovali všetky konečné opakované hry s neúplnou informáciou podľa minimax rýchlosti ich konvergencie. Vysvetlím štruktúru rôznych typov hier tejto klasifikácie.

Dávid Pál vyštudoval informatiku v roku 2004 na FMFI UK v Bratislave. Počas doktorandského štúdia na Univerzite vo Waterloo v Kanade sa pod vedením prof. Shaia Ben-Davida začal venovať teórii strojového učenia. Po skončení doktorandského štúdia absolvoval postdoc na Univerzite v Edmontone v Kanade pod vedením prof. Csabu Szepesvariho. Od roku 2011 pracuje pre Google New York.

Eduard Kejnovský (Biofyzikální Ústav AV ČR): Skákající geny - paraziti nebo pomocníci?

V poslední době se stále jasněji ukazuje, že genomy nejsou neměnné genetické entity. Jedná se naopak o systémy velice dynamické, generátory vlastních přestaveb citlivě reagující na změny prostředí. Významnou roli v dynamice genomů hrají mobilní genetické elementy, neboli transponovatelné elementy, transpozony či populárně „skákající geny“. Transposony tvoří často významnou část jaderného genomu, u člověka asi polovinu. V přednášce bude pojednáno o struktuře a životním cyklu různých typů transposonů, o jejich podílu v genomu, o místech genomu, kde se „skákající geny“ nacházejí. Bude zmínka o souvislosti retrotransposonů s dávným světem molekul RNA, který předcházel dnešnímu světu DNA a proteinů. Přednáška se bude zabývat i funkcí transposonů, jejich vlivu na fenotyp a případech tzv. „domestikace“ transposonů. V závěru bude zmíněna řada otázek týkajících se důležitosti transposonů pro strukturu, fungování i evoluci genomů.

Doc. RNDr. Eduard Kejnovský, CSc. je výzkumným pracovníkem Laboratoře vývojové genetiky rostlin Biofyzikálního ústavu AVČR, v.v.i. v Brně a vedoucím skupiny Dynamika genomu, Středoevropského technologického institutu CEITEC v Brně. Specializuje se na problematiku dynamiky genomů, evoluce pohlavních chromosomů a biologii transposonů.

Rišo Kráľovič (Google Zürich): Menej je niekedy viac: Mapreduce a Flume v paralelných výpočtoch

V porovnaní so sekvenčnými výpočtami sú výpočty využívajúce paralelizmus výrazne zložitejšie. Z teoretického pohľadu je veľmi prirodzeným modelom paralelných výpočtov model PRAM, ktorý je analógiou modelu RAM často používaného v teórii zložitosti. Z praktického pohľadu je však zaručenie úplnej synchronizácie a uniformného prístupu k zdieľanej pamäti, garantovaných modelom PRAM, značne problematické. Pre realizáciu paralelných výpočtov sa preto často využívajú distribuované systémy s rôznou mierou asynchónnosti.

Klasické systémy používané pre implementáciu paralelných výpočtov v distribuovaných systémoch, ako napr. MPI, poskytujú veľkú flexibilitu. To však so sebou prináša aj nevýhody. Používateľ sa totiž musí postarať o mnohé technické detaily, ako napr. správnu synchronizáciu výpočtu, odolnosť voči chybám, a pod., čo implementáciu paralelných algoritmov výrazne komplikuje.

Alternatívou k takýmto všeobecným systémom pre využitie paralelizmu sú systémy, ktoré kladú isté obmedzenia na komunikačnú štruktúru paralelného výpočtu. Sem patrí napr. systém MapReduce, určený na spracovávanie veľkého množstva dát. Používateľ tu stráca flexibilitu, čo znamená, že použitie takýchto systémov nie je vždy vhodné. Na druhej strane, používateľ sa môže sústrediť na samotné jadro logiky paralelného výpočtu; odolnosť voči chybám je k dispozícii bez jeho zásahu.

Z pohľadu užívateľa pozostáva výpočet v MapReduce pozostáva dvoch fáz: Vo fáze Map môže užívateľom určená funkcia vytvoriť, pre každú vstupnú položku, niekoľko párov (kľúč, hodnota). Vo fáze Reduce je, pre každú použitú hodnotu kľúča, zavolaná užívateľom definovaná funkcia, ktorá spracuje všetky hodnoty prislúchajúce k danému kľúču.

Systém MapReduce je, aj napriek jeho jednoduchosti, použiteľný pre prekvapivo veľké množstvo problémov. V mnohých situáciách je však na riešenie problému potrebných niekoľko cyklov MapReduce a ich ručné plánovanie a menežovanie býva zväčša zdĺhavé. Na uľahčenie tejto situácie bol navrhnutý system Flume, ktorý poskytuje užívateľovi komfortnú abstrakciu nad MapReduce. Flume poskytuje dátový typ pre paralelizovaný súbor dát, s ktorým potom môže užívateľ pracovať ako s jednoduchou premennou. Na súbore dát je možné spustiť paralelnú operáciu, ktorá aplikuje danú funkciu na každú položku jednotlivo. Okrem toho je možné preusporiadať súbor obsahujúci páry (kľúč, hodnota) podľa kľúča, podobne ako v systéme MapReduce. Knižnica Flume na základe vykonaných operácii navrhne, zoptimalizuje, a vykoná sériu MapReduce cyklov, ktoré realizujú užívateľom požadované operácie.

Richard Královič absolvoval štúdium informatiky na FMFI UK v Bratislave. Doktorát získal na FMFI UK, kde sa venoval najmä oblasti distribuovaných výpočtov a na ETH Zürich, kde sa v pracovnej skupine Juraja Hromkoviča zaoberal stavovou zložitosťou konečných automatov, aproximatívnymi algoritmami, online algoritmami a advice zložitosťou. Po skončení postdocu na ETH Zürich pracuje pre Google Zürich.