Závěrečný projekt: Témata

V této části specifikujeme potenciální závěrečné projekty. Nejedná se o přesný popis, ale pouze o rámcový popis. Víceméně cokoli z uvedeného postupu lze změnit.

Rozpoznávání jedinců má velký význam jak v lidské tak zvířecí říši. Zatímco u lidí se jedná spíše o negativní aplikace, u zvířat nám umožňuje monitorování ohrožených populací. Jedním z takovýchto projektů je databáze SeaTurtleID, která vznikla jako spolupráce několika univerzit (včetně ČVUT) a řecké neziskové organizace Archelon. Tato databáze obsahuje přes 7500 fotek 400 želv karet. Tyto fotky jsou z různých úhlů a vzdáleností.

Vaším úkolem bude udělat algoritmus, který jednotlivé želvy rozpozná. Doporučujeme náš článek, ze kterého můžete implementovat metody. Případně si můžete vymyslet vlastní. Podobně jako v článku, se můžete zaměřit na to, jak možné rozdělení na trénovací a testovací množinu ovlivňuje výsledky. Zároveň dosažené výsledky můžete otestovat na některém z 30 dalších zvířecích datasetů.

Sportovní soutěže jsou často rozděleny do skupinové a vyřazovací fáze. Zatímco v skupinové fázi hraje každý s každým, ve vyřazovací fázi se postupuje pavoukem. V amatérských soutěžích je často snaha, aby týmy hrály co nejvíce zápasu a používá se varianta double elimination, kdy vyřazený tým propadá do spodního pavouku. Úkolem projektu je z textového seznamu zápasů vytvořit jeho grafickou reprezentaci.

Na vstupu je csv soubor, kde každý řádek odpovídá jednomu zápasu. Jako příklad uveďme

PQ1,B3,A5
PQ2,A4,B4
Q1,B2,A3
Q2,B1,WPQ2
Q3,A2,WPQ1
P9,LPQ1,LPQ2
S1,A1,WQ1
S2,WQ2,WQ3
S3,LQ1,WP9
S4,LQ2,LQ3
P1,WS1,WS2
P3,LS1,LS2
P5,WS3,WS4
P7,LS3,LS4

V tomto případě má druhý zápas id PQ2 a utkají se v něm čtvrtý tým skupiny A a čtvrtý tým skupiny B. Čtvrtý zápas má id Q2 a utká se v něm vítěz zápasu PQ2 a první tým skupiny B. Výstupem bude obrázek, který tento graf symbolizuje. Případ nahoře odpovídá pavouku, který jde symbolizaovat jako následující obrázek.

Grafické zobrazení může být provedeno jinak než je tento obrázek. Nemělo by však obsahovat žádné křižící se šipky a mělo by být umístěno na gridu (tedy například zápasy o umístění P1 až P4 by měly být pod sebou). Může se předpokládat, že skupiny jsou maximálně tři a jsou označeny A, B a případně C.

Úkolem projektu je napsat automatické derivování funkcí. Na vstupu bude funkční předpis, například

f_text = "-(sin(x+y))^2+1-x"

Z textového předpisu se utvoří vnitřní reprezentace pomocí funkce define_function, která jako první argument vezme funkční předpis a jako zbylé argumenty proměnné.

f = define_function(f_text, "x", "y")

Tento vnitřní předpis by mělo jít vypisovat, diferencovat a vyhodnocovat

julia> f_der_x = differentiate(f, "x")
-2*sin(x+y)*cos(x+y)-1
 
julia> evaluate(f_der_x, 0, 0)
-1

Můžete specifikovat seznam funkcí, která má knihovna podporovat. Nezapoměňte, že některé operace jsou unární (mají jeden vstup - sinus), některé binární (mají dva vstupy - sčítání) a některé mohou být obojí (například mínus).

Pro základní verzi projektu lze předpokládat, že všechny proměnné jsou skalární a všechny operace jsou dobře uzávorkované. Pro složitější verzi lze uvažovat vektorové proměnné (s čímz souvisí například násobení matice-vektor) nebo ignorování závorek či některých operátorů jako například násobení

define_function("xy", "x", "y")

Úkolem je napsat balík pro minimalizaci funkcí. Balík by měl obsahovat metody nultého (nevyužívají derivace - například simulované žíhání), prvního (používají první derivace - například metoda největšího spádu) i druhého řádu (používají druhé derivace - například Newtonova metoda). Půjde tedy o funkci minimize, která jako první argument bere funkci, další argumenty první či druhou derivaci. Jako keyword argumenty mohou být použity například meze (stačí intervaly), počáteční bod, způsob generování počátečního bodu, maximální počet iterací, způsob výpisu či cokoli jiného. Funkce minimize musí pracovat i na vektorových proměnných.

Jako příklad uveďme funkci (a její derivace)

f(x) = sin(x) + x^2
g(x) = cos(x) + 2*x
h(x) = -sin(x) + 2

Minimalizaci můžeme pak volat mnoha způsoby. Jako příklad uvedeme

x1 = minimize(f)
x2 = minimize(f, g; method=BFGS(), x0=0)
x3 = minimize(f, g; lb=0, ub=1, x0='random')
x4 = minimize(f, g, h)

První volání nepoužívá derivace a tedy by mělo vybrat nějakou metodu nultého řádu. Druhé volání použije metodu BFGS ze specifikovaného počátečního bodu. Třetí volání náhodně vygeneruje počáteční bod a použije defaultní metodu pro optimalizaci prvního řádu s omezeními. Čtvrté volání použije defaultní metodu druhého řádu. Typ BFGS může být definován například následovně

abstract type FirstOrder end
 
struct BFGS <: FirstOrder
 
end