Matematicka lingvistika - 16.9.2020

Vše o státnicích úspěšně završujících roky studia na naší alma mater.
Jankus

Matematicka lingvistika - 16.9.2020

Příspěvek od Jankus »

Bol som na statniciach sam. Na zaciatku (tak 9:10) som dostal zadanie vsetkych piatich otazok. Na pripravu som mal ani nie pol hodiny (tak 9:35). Potom hned za sebou jednotlive skusania, vacsinou je niekto hlavny skusajuci, ostatni sa obcas spytaju ci komentuju bokom. Skusajuci su mili, snazia sa nasmerovat.

Datove struktury: Hashovanie, riesenie kolizii [Holan]
Motivacia, definicia, ze je to rychle, ale bez zaruky v najhorsom pripade. Problem s koliziami. Jak vobec spoznam, ze doslo ku kolizii? Co ked narazim vo vete na slovo, ktore som uz zahashoval, tak to predsa nie je kolizia. No tak ked zistim, ze v priehradke uz nieco je, tak najprv porovnam kluce a az ked sa lisia, tak to vyhlasim za koliziu. Dalej, ako ich riesit: popisal som separovane retazce, otvorenu adresaciu a ako sa skusaju dalsie priehradky (linearne, kvadraticky, dvojite hashovanie). Zmienil som este, ze sa daju prvky aj prepisovat, napr. pri cachovani, alebo ze mozme mat za istych podmienok aj perfektne hashovanie bez kolizii - ale to skusajuceho zas tak nezaujimalo... Ako sa v takom otvorenom hashovani maze? Oznacujeme za zmazane, ale nechavame, inac by sa mohlo stat, ze [ukazujem na obrazku]. Este nieco k tomu, ze ako dlho to cele potrva? To zalezi od zaplnenia tabulky (alfa=n/m). A co potom, ked je tabulka dost plna? Mozme ju prehashovat do inej, trebars 2x vacsej - to bude trvat v tej chvili dlho, ale celkovo sa to neprejavi (smerujem k amortizacii dynamickeho pola). No ale keby sme je nezdvojnasobili, ale pridali 10 priehradok. To by nestacilo, potom uz by to cele bezalo linearne. A keby sme zvysili o 10 %? Reku, neviem, ci by potom ta amortizacia vysla...
Potom ze dictionary v pythone (co je prave hashovacia tabulka) vraj funguje konstantne (dakde pisali) - ako by som tomu rozumel? No tak, ze priemerne konstantne, ale moze sa stat, ze nejake data budu take zle, ze to bude trvat dlho. A dokazal by som take data skodoradostne vymysliet? Vravim, ze este existuje univerzalne hashovanie, ktore ma pre kazde 2 prvky priemerne (cez hashovacie funkcie) rovnaku pravdepodobnost. Takze ak dictionary hashuje univezalne, tak sa ziadne take data vymysliet nedaju. Tak vraj sice uplne univerzalne nehashuje, ale pri kazdom spusteni voli funkciu nahodne, takze sa take data (aspon nijak jednoducho) vymysliet nedaju.
Z tohto som mal 1.

Zlozitost a vycislitelnost: NP uplne problemy [Holan]
Co znamena, ze je problem v NP (obe definicie, dokaz ekvivalencie sa nechcel) - ok. Co znamena, ze je NP tazky - ze nanho mozme previest akykolvek problem v NP. Co je ten prevod? Ze existuje poly. funkcia f, ktora prevadza instancie jedneho problemu M na druhy M' - ze ked M(a) prijme, tak prijme aj M'(f(a)). Je tam len implikacia? Tu som sa snazil popisat, ze tam implikacie nejak bude, lebo neplati opacne, ze by sme akykolvek problem v NP mohli previest na nejaky NP tazky. To je sice pravda, ale tato implikacia je inde, tu ma skutocne byt ekvivalencia: M(a) prijme <=> M'(f(a)) prijme.
Dalej NP uplne: su v NP a zaroven NP tazke, vsetko som to behom toho ukazoval na mnozinovom obrazku.
Potom nejake priklady: SAT, 3SAT, kachlikovanie, OC, HK... Ako vlastne ukazem, ze nejaky problem je NP uplny? Prevodom alebo priamo z definicie... To priamo som trosku motal. Ale popisal som kachlikovanie, zadanie aj prevod, to bolo ok (len ze vraj siet nemusi byt stvorcova... vravim, ze z oboch smerov si to ale mozme doplnit: prazdnymi znakmi / kopirovanim prijimacej konfiguracie - takze mozme pozadovat stvorcovu!).
Este nejaky iny prevod by som si vedel? Tak vravim SAT->3SAT, ze to mi prislo lahke. Tak sa skusajuci smiali, ze som si dobre vybral. I ked keby som si vybral opacne 3SAT->SAT, ze by to bolo este lahsie :D
Znamka 1,5 - 2

Zaklady NLP: Navrh a vyhodnotenie lingvistickych experimentov, evaluacne metriky [Zabokrtsky]
Chcel som rozpravat o metrikach precision/recall, tak som popisal situaciu, ze mame zlate, binarne anotovane data a chceme sa na nich vyhodnotit fungovanie nejakeho systemu. Ale mozeme mat aj ulohy bez anotovanych dat? Ano, napriklad rozne clustrovacie, cielom je trebars dat do skupin slova, co sa chovaju nejak podobne (slovne druhy, vetne cleny...). Dobre, tak k tym anotovanym. Niektore vzorky su oznacene ako pozitivne, cielom je ich urcit -> matica konfuzie. Musi to byt binarne? Nie, mozeme mat viac tried (ale aj tie mozem vyhodnocovat binarne, vzdy 1 proti ostatnym). Metriky accuracy (ta je nepresna), precision, recall. F1-score: preco to je geometricky priemer prec a rec. a nie aritmeticky. No lebo je lahke mat jedno z tych dvoch vysoke (oznacim vsetko -> vysoky recall) i ked druhe je nizke. Aritmeticky by povedal, ze to je tak stredne uspesne, geometricky tu nevyvazenost viac penalizuje. A preco je v tom F1 ta dvojka? No.. taky je ten priemer... asi by tam nemusela byt, sa to tym len nasobi. Tak inac, preco to F1 robime? No chceme nejak rovnomerne vyjadrit precision a recall spolu. To tak ale nemusi byt vzdy, mozme chciet dat jednemu z toho vacsiu vahu, napr. ked jeden typ chyb je drazsi nez iny alebo ked chyby v jednom smere toklo nevadia (napr. ked sa obcas spam dostane do schranky tak to tolko nevadi, jak ked dolezity e-mail skonci v spame).
Na papieri som mal este vzorec pre BLEU, tak nieco ze o tom. Sluzi to pre vyhodnotenie strojoveho prekladu. Brevity penalty ok. Suma, vahy n-gramov ok. Ale najprv zle povedal, co su to tie P_n. Ziadne pravdepodobnosti! Je to precision na tych n-gramoch - jednoducho kolko n-gramov z evaluovaneho prekladu bolo v referencnom preklade.
K mojmu prekvapeniu za 1 (myslim).

Lingvisticke teorie a formalizmy: Zakladne formalizmy (hlavne GB, HPSG, CG) [Hana]
Vraj k tomu mozem este pridaj aj dalsie, trebars zavislostne, ak chcem. Zacal som obecne rozdielom medzi zlozkovymi a zavislostnymi, potom pristupil ku kategorialnym gramatikam, akoze su najstarsie. Povedal som, ze co su tie kategorie, ze ich maju slova u seba v slovniku a ako sa podla toho analyzuje veta. To bolo sice spravne, ale bol to len popis syntaxe, ale ta gramatika je kompletna od fonetiky az po pragmatiku. Potom chcel skusajuci nieco o tych zavislostnych, nejake porovnanie so zlozkovymi, vratane stromov. Zakladny popis stromov... ok. Ze v zavislostnych sa zle koordinuje - ok. Ze v zlozkovych sa nedaju reprezentovat neprojektivne konstrukcie - to vraj zalezi, ako tu gramatiku vybudujeme (ze nikde nie je povedane, ze tie gramatiky musia byt bezkontextove). Keby som si mal vybrat smer, ktorym by som stromy prevadzal? Vravim, ze u zlozkovych by bol problem, ktory neterminal frazy by mal byt riadiaci clen ostatnych - ok, ale tak keby som to tam mal vyznacene. Naopak zo zavislostnych na zlozkove by bol problem, ze jeden zavislostny odpoveda viacerym zlozkovym.
Ku Government & Binding ani k HPSG sme sa prekvapivo uz vobec nedostali.
Znamka asi 2.

Statisticke metody a strojove ucenie: HMM, trellis, Viterbi, Baum-Welch [Straka+Dusek]
K tejto otazke som sa pri priprave uz nedostal, tak to bolo trochu zmatene (i ked keby som si povedal, ze chcem este viac casu, tak by mi ho iste dali). Chvilu mi trvalo, nez som poskladal, co to su HMM (museli sa mna spytat, co je na nich to "markovovske" - obmedzena historia). Trellis ok. Pomylil som si tie algoritmy, popisal som s pomocou skusajucich ucel a priebeh Viterbiho. Baum-Welcha som si nespomenul.
Viterbi dostane retazec, trebars slovo/vetu, emitovanu HMM, algoritmus ma zistit najpravdepodobnejsiu postupnost stavov. Baum-Welch dostane velke mnozstvo textu a ma natrenovat prechodove a vystupne pravdepodobnosti.
Dostal som 2,5.

Poslali ma na chvilu von, potom si ma zavovali a oznamili znamku. Ze par zaskobrnuti, obcas aj vaznejzich, tak ze pekna dvojka (tie jednotlive znamky z okruhov nevraveli, ale boli tam spisane na papieri). Odchadzal som cca o 10:50, takze samotne skusanie mohlo mat daco malo cez hodinu.
Odpovědět

Zpět na „Magisterské SZZ“