Odpověď na téma: 42. CP SOČ online – obor 01 matematika a statistika

[Martin Biroščák]

Dobrý den Vážená poroto, děkuji mockrát že jste mi vyhověli odpovídat den předem.

K otázkám:

1)Formulujte úlohu konvexního kvadratického programování, kterou řešíte.

V textu řeším tři úlohy, a to sice Hard Margin SVM formulace, Soft Margin SVM formulace s L1 penalizací a Soft Margin SVCM formulace s L2 penalizací.
Hard margin formulace je úloha maximalizace vzdálenosti mezi nadrovinami skrz support vektory, mezi nimiž leží separující nadrovina. Když omezím úlohu pouze na separující nadroviny, pro které platí:
y_i^T(w^Tx_i+b)>= 1 (Tedy požadujeme ze „vzdálenost“ každého vzorku musí být minimálně jedna, v w^Tx+b 1 a -1 leží právě ty nadroviny skrz support vektory)
Můžu dojít odvozením k tomu je tato vzdálenost:
1/2||w||^2.
Tudíž maximalizační problém zní:
arg max 1/2||w||^2 s.t. y^T(w^Tx_i+b)>= 1
(arg max misto max protože chci získat získat parametry rovnice nadroviny, a hodnota samotné minimalizaca pro mě není důležitá (Pomineme-li že se snažím o její maximalizaci))

U soft margin formulace maximalizace jde o to, nevyžaduji že všechny vzorky leží mimo zónu kolem separující nadroviny, tudíž se formulace trošku změní na:
Kde epsilon meri jak moc vzorek zonu porsuil. Pribide omezeni epsilon_i, protoze mereni chyby by nemelo byt negativni. Tudiz tato formulace je:
arg max 1/2||w||^2 + (epsilon1 + epsilon2 + … + epsilonN) s.t. y_i^T(w^Tx_i+b)>= 1-epsilon_i, epsilon_i >= 0

Toto byla L1, L2 formulace je trosku jina, protoze nepricitam epsilon ale epsilon^2, tudiz zmizi omezeni epsilon_i >= 0, a cela optimalizacni uloha se chova trosku jinak.
arg max 1/2||w||^2 + (epsilon1^2 + epsilon2^2 + … + epsilonN^2) s.t. y_i^T(w^Tx_i+b)>= 1-epsilon_i

2)Vysvětlete použití Lagrangiánu, KKT-podmínek a duální úlohy při výpočtu řešení.
Dualni uloha odkazuje k tomu, ze u nekterych uloh muzu vyresit misto mnou nadefinovane ulohy (v prvni otazce napriklad) ulohu dualni, ktera je mnohdy snazsi na vyreseni. Pro to aby se optimum dualniho problemu rovnalo optimu toho prvniho, tak musi platit uricte podminky.

Lagrangian je metoda, ktera se da pouzit pri optimalizacni ulohach k jejich vyreseni. Zakladnim principem Lagrangovskeho multiplikatoru je to, ze si nadefinuji Lagrangian, ktery puvodni ulohu s linarnimi omezenimi pretransformuje na ulohu bez linearnich omezeni, vysledek jejichz optimalizace vsak odpovida puvodni uloze.
KKT podminky jsou vlastne takove zobecneni Lagrangeovske metody i pro nerovnostni omezeni, k Lagrangianu vlastne pribidou complementary slackness conditions.

3) Jaký je obecný princip učení s učitelem (SVM je totiž jen jednou z metod strojového učení, která učení s učitelem využívá)?

Verim ze zakladni princip strojoveho uceni je to, ze pocitac se snazi odvodit nejakou funkci, ktera by prevedla pozadovany vstup na pozadovany vystup.
Jsou ruzne metody, linarni regrese, logisticka regrese, neuralni site, decision trees. Vzdy je treba algoritmus strojoveho uceni natrenovat, zde si prave odvodi danou funkci, ktera bude prevadet vstup na vystup. U linearni regrese se vytvori krivka ktera minimalizuje mean square error, neuralni site jsou vlastne sit jednoduduchych funkci, ktere se porad dokolecka v epochach trenuji, dokud dostatecne neaproximuji funkci, atd. Vetsinou se u strojoveho uceni optimalizuji ruzne hyperparametry algoritmu ktere ovlivnuji jaka funkce vzninke a jak dobre bude model aproximovat funkci jejz se jej snazime „naucit“. Pro to je dulezite znat, jak uspesny je v te aproximaci, pro to se pouzivaji ruzne metriky. Jakmile najdeme ruznymi metodami uspokojivy model, ktery dostatecne spravne prevadi vstup na pozdaovany vystup, tak se model zacne pouzivat, a muze transformovat na nova data (V pripade predikce predpovida hodnoty, v pripade klasifikace rozrazuje do ruznych skupin).

4) Vysvětlete podrobněji výhody využití „nested k-fold validace“ v uváděných experimentech (viz str. 93). Co si představit pod pojmy „biologický target“ a „ligand“? Jaký je rozdíl v obou zmiňovaných přístupech? O co opíráte volbu „k=4“ u cross validace (str. 96; mimochodem v češtině spíše „křížové validace“)?

Biologický target je něco v těle na co se daný lék/sloučenina váže, něco k čemu se připojí a nějak jej reguluje. Ligand je vlastně ten lék co polykáte, nebo nějaká sloučenina co ten biologický cíl/target reaguje. U většího počtu k trvalo trénování příliš dlouho. Je také nutno nevybrat přemrštěně velké k, jelikož to by mohlo vyústit v ten hold-out dataset jenž by neobsahoval téměř žádné prvky. Výhoda nested validace je že nevzniká žádný bias, a že nemusím manuálně hledat optimální model, a až potom jej ručně validovat.

5) V čem spočívá Váš osobní přínos při řešení dané problematiky? Tuším, že jsem na toto odpoívdal již v krajském kole. Na univerzite VSB-TU v Ostrave probiha projekt PermonSVM, ktery je neco mnohem rozsahlejsiho podobneho zameru jako muj projekt. Jejich projekt je v C, kde se ovsem hur prototypuje, a timpadem byl zajem vytvorit neco co by bylo privetivejsi pro rychle zkouseni novych veci, timpadem vzinkl tento projekt. Navic text podle me funguje jako komprehensivni zhrnuti problematiky, minimalne pro ceske studenty. Navic tusim ze nikde nejde najit tak hezky na jednom miste vse shrnuto.