„Myslím, že když chcete být při žádosti o ERC grant úspěšní, musíte být realističtí, ale ne přehnaně skromní,“ říká Pavel Veselý z Informatického ústavu UK, který v červnu získal prestižní grant ERC CZ. Díky němu se zaměří na výzkum malých datových struktur robustních proti útokům, jejichž cílem je způsobit velkou chybu.
Na Matfyzu se zabýváte algoritmy pro analýzu velkých dat. O co přesně jde?
Jedná se o takzvané proudové (streaming) algoritmy, kterým stačí jen malá paměť a jeden průchod přes data. Používají se k odhadu jednoduše definovaných statistik s co nejmenší chybou v daném prostoru. Výsledným datovým strukturám se říká skeče, neboť se v malém prostoru snaží zachytit důležité vlastnosti vstupních dat.
Tradiční algoritmy mají prakticky libovolný přístup k datům a mohou po nich „skákat“ sem a tam jako po nějakém poli a nejsou typicky omezené pamětí, kterou si mohou navyšovat přímo úměrně velikosti dat. Oproti nim proudové algoritmy se na vstup dat dívají jako na sekvenci, jež postupně přichází. Představte si, že běží na síťovém zařízení, které monitoruje provoz, nebo na serveru, jemuž přichází určité požadavky, a on si měří, jak dlouho mu trvá každý zpracovat. Tyto informace se předají do datové struktury neboli proudového algoritmu. Ten ale nemá možnost se vrátit do minulosti k předchozím pozorováním.
Proudový algoritmus si tedy nemůže svoje poznatky ukládat?
Nemůže si uložit vše, protože pracuje s malou pamětí a ta možnosti ukládání poznatků o vstupu výrazně omezuje. Každé nové pozorování, které přijde, dokáže zpracovat velmi rychle, což je jeho další typická vlastnost. Kvůli své malé paměti umí úspěšně řešit jen určité základní problémy a musí se také naučit dobře zapomínat a vytáhnout z dat důležité vlastnosti, jež k řešení určitého problému potřebujeme. Například zjišťujeme, kolik požadavků trvalo víc jak půl sekundy nebo sekundu nebo i deset sekund. Takto dlouhých požadavků už může být relativně málo a zároveň si je nechceme, a kvůli té malé paměti ani nemůžeme, ukládat všechny.
Problém je, že kvůli tomu, že si proudové algoritmy nepamatují všechno, kromě naprosto triviálních úkolů (například součet všech čísel na vstupu) u nich vždycky musíme počítat s určitou chybou.
K čemu se proudové algoritmy v praxi používají?
Využívají se u aplikací, které pracují s velkými daty, u nichž nepotřebujeme znát přesný výsledek, ale stačí nám pouze přibližný. Například v oblasti online reklamy, kdy zadavatel potřebuje vědět, kolik různých uživatelů ji vidělo. Nepotřebuje však znát jejich přesný počet (zda jde o 101 nebo 102 tisíc lidí), takže nám malá chyba v řádech jednotek procent většinou nevadí.
Jak dlouho se proudovými algoritmy zabýváte?
Dostal jsem se k nim během postdoktorandského výzkumného pobytu na University of Warwick. Byl jsem postdokem Grahama Cormoda, jednoho z předních odborníků na tuto problematiku, jíž se zabývá přes dvacet let. Byla to pro mě ohromná příležitost se naučit něco nového.
O algoritmy se ale zajímám mnohem déle. Na doktorátu jsem řešil online algoritmy, které také zpracovávají vstup dat po jednotlivých prvcích. U nich nejsme omezeni pamětí, ale zase tím, že se během zpracování nového prvku musíme okamžitě rozhodnout. Například nám chodí úlohy k rozvržení, a my každou musíme hned přiřadit na nějaký stroj, který ji zpracuje, aniž bychom dopředu věděli, jaké další úlohy k nám budou přicházet. Tím pádem nemusíme vždy získat optimální řešení.
Věnujete se základnímu výzkumu?
Ano, ale současně mě zajímá, jak se proudové algoritmy chovají na reálných datech. Testovali jsme to ve spolupráci s americkou firmou Splunk, jež se zabývá zpracováním velkých dat včetně odhadu distribucí a percentilů. Dále spolupracuji s knihovnou otevřeného softwaru Apache DataSketches, pro kterou jsme vymysleli úplně nový proudový algoritmus na odhad percentilů s velkou přesností pro prvky na okraji distribuce.
Přenášíte tedy poznatky základního výzkumu do praxe, což se jen málokterým vědcům či vědkyním daří.
Na začátku se jedná víceméně o matematický výzkum. Dělám si analýzu, jak má algoritmus fungovat, a opravuji ho tak, aby měl určitou garanci chyby. Čím menší chybovost, tím samozřejmě lépe. Výsledek teoretického výzkumu mi zpravidla udá garanci chyby v tom nejhorším případě. Pomocí experimentů pak následně řeším, jak se algoritmus chová na reálných datech. Právě díky profesoru Cormodovi jsem se dostal až k lidem, kteří tyto algoritmy aplikují v praxi.
Co je na takové spolupráci nejzajímavější?
Zajímá mě, na jaké problémy narážejí lidé v praxi, a jejich zkušenosti se snažím využít pro zlepšení algoritmů. Například společnost Splunk používá algoritmus bez garance chyby, který v praxi velmi dobře funguje. Porovnávali jsme ho s naším proudovým algoritmem, který nám „vypadl“ z teoretického výzkumu. Výsledky jsou celkem nepřekvapivé. Heuristika Splunku se chová mnohem lépe na reálných datech, s nimiž se člověk setká v praxi, ale může mít libovolně velkou chybu, což může být někdy problém. Oproti tomu náš algoritmus se choval stabilně – na všech datových vstupech měl pořád víceméně stejnou chybovost. Z matematické analýzy nám také vyšlo, že ho lze jen velmi těžko „shodit“. Jedním z mých cílů nyní je překonat zmíněnou heuristiku, a zachovat přitom určitou garanci chyby.
Kdy vám došlo, že váš výzkum má potenciál získat grant ERC?
Mám rád výzvy a když se naskytla příležitost podat si žádost, využil jsem ji. Svým způsobem vám to srovná priority, donutí vás to zamyslet se, co je v případě vašeho výzkumu opravdu důležité, a jak vyzdvihnout jeho potenciál.
Čemu konkrétně se budete věnovat?
Chci se posunout k vývoji datových struktur robustních proti útokům, jejichž cílem je způsobit velkou chybu. Je zde řada poměrně velkých otevřených problémů.
Kolik času na jejich řešení máte?
ERC CZ jsem dostal na dva roky. Ministerstvo školství, mládeže a tělovýchovy ČR tento grant nabízí vědcům a vědkyním, kteří se svými projekty získali výborné hodnocení v soutěži o granty Evropské výzkumné rady (ERC), ale nebyli podpořeni pro nedostatek financí. Z praktického hlediska mi grant zaplatí kvalitního postdoktorandského výzkumníka, kterého jsem snad již našel, a dva nadějné doktorandy, z nichž jeden, Tomáš Domes, u mě dokončuje hezkou diplomku a začne doktorát v říjnu.
Je to váš první grant a nejspíš poprvé řešíte nejen výzkumnou, ale i manažerskou stránku věci.
Přesně tak. Nové pro mě bylo už psaní samotné žádosti o ERC. Musíte si vytvořit velkou vizi, výzvu, která ovšem vyžaduje skvělý nápad. K tomu je dobré se naučit nebýt příliš skromný a dokázat prodat předchozí úspěchy, jež jsou pro váš aktuální projekt relevantní. A nebát se riskovat. To je podle mě princip ERC grantů. Přijít s takovým nápadem, který dokáže výrazně posunout dosavadní vědecké poznání daného oboru, a zároveň je realistický, i když riskantní – nemusí se povést. Proto je součástí žádosti o tento grant i plán B.
Máte obavy?
Mám výzkum rád, takže víc, než že bych se bál, se na něj těším. Nejen na spolupráci s doktorandy a postdoky, ale i na tu mezinárodní. Ostatně na téma proudové algoritmy versus jejich adaptivní protivníci jsem přišel během přednášky na jedné konferenci. Zaujalo mě to a přemýšlel jsem nad směry, kterými by stálo za to se vydat. Je to zajímavý nový problém – jak matematicky, tak do jisté míry, jak už jsem zmiňoval, i prakticky.
Do jaké míry je vaše práce solitérní a kdy už ji potřebujete s někým konzultovat?
Věřím, že někteří kolegové si vystačí déle sami. Já mám spolupráci a diskuse rád, protože mě do značné míry motivují vymýšlet argumenty a hledat další možnosti řešení. Ale mám také období, třeba během posledního roku na doktorátu, kdy přemýšlím dlouho sám.
Co byste poradil středoškolským studentům, které baví matematika a informatika? Jak si udělat o těchto oborech jasnější představu?
Určitě bych jim doporučil korespondenční semináře, které připravují pro středoškoláky studenti Matfyzu. Mně konkrétně tehdy nejvíc zaujal ten programovací. Je to skvělá příležitost i pro nová kamarádství, protože v rámci korespondenčních seminářů se pořádají soustředění, tedy něco jako letní tábory, na nichž se účastníci potkají s lidmi, s nimiž si mohou povídat i o věcech, ke kterým se na běžném gymplu moc nedostanou. Během střední školy jsem pomáhal s vývojem většího softwaru, a na Matfyzu jsem se proto plánoval zaměřit na studium softwarového inženýrství. Ve druháku jsem si ale co by nadšený student nabral i kombinatorické hry. Zaujala mě matematika, zejména kombinatorika, a vydal jsem se víc teoretickým směrem. Chci tím říct, že podle mě je nejzásadnější podmínkou úspěchu najít, co vás baví, a k tomu si potřebujete na začátku vyzkoušet co nejvíc věcí. Ve všech oborech určitě najdete něco zajímavého, pokud k tomu máte vztah, a ten vám může pomoci navázat třeba dobrý mentor. Já na ně měl velké štěstí a jednou bych se rád, třeba i díky grantu ERC CZ, taky takovým průvodcem stal.
Autor: Jitka Jiřičková
Foto: Hynek Glos
Zdroj: Univerzita Karlova
Článek vyšel v on-line magazínu Univerzity Karlovy Forum.
Pavel Veselý vystudoval Matematicko-fyzikální fakultu UK. Doktorské studium zakončil dizertační prací pod vedením Jiřího Sgalla, v níž se zabývala problematikou online algoritmů. Jako postdok pak působil na University of Warwick ve výzkumném týmu profesora Grahama Cormoda. Nyní působí na Informatickém ústavu UK. Věnuje se teoretické informatice a kombinatorice se zaměřením na tvorbu účinných algoritmů, zejména proudových a datových struktur, takzvaných skečů. Letos v červnu získal prestižní grant ERC CZ na projekt Robustní proudové algoritmy versus adaptivní protivníci.
- Autor článku: ne
- Zdroj: Univerzita Karlova
