Final Project: Topics

In this section, we present potential final projects. This is not an exact but only a general description. More or less anything from the description can be changed.

Recognition of individuals is of great importance in both human and animal kingdoms. While for humans, there are rather negative applications, for animals it allows us to monitor endangered populations. One such project is the database SeaTurtleID, which was created as a collaboration between several universities (including CTU) and a Greek non-profit organization Archelon. This database contains over 7500 photos of 400 individual turtles. These photos are from different angles and distances.

Your task will be to make an algorithm that recognizes individual turtles. We recommend our article from which you can implement the methods. Alternatively, you can invent your own method. Similar to the article, you can focus on how a possible split into the training and testing sets influences the results. At the same time, you can test the achieved results on some of the 30 other animal datasets.

Sports competitions are often divided into group and knockout stages. While in the group stage everyone plays everyone, in the knockout stage, teams progress in a tree. In amateur competitions, there is often an effort for teams to play as many matches as possible, and a double elimination variant is used, where eliminated teams fall into the lower bracket. The task of the project is to create a graphic representation of a text list of matches.

The input is a csv file where each line corresponds to one match. Let us give an example

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

In this case, the second match has the id PQ2 and the fourth team of group A and the fourth team of group B play against each other. The fourth match has id Q2 and the winner of PQ2 plays against the first team of group B. The output will be the image that this graph symbolizes. The case above corresponds to the tournament tree symbolized by the following image.

The graphics may be different from this image. However, it should not contain any crossing arrows and should be placed on a grid (i. e. matches for the positions P1 to P4 should be below each other). It can be assumed that there are a maximum of three groups and they are labeled A, B and possibly C.

The task of the project is to write automatic differentiation of functions. At the input there will be a function string representation such as

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

An internal representation is created from the text representation using the define_function function, which takes the function representation as the first argument and variables as the remaining arguments.

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

It should be possible to list, differentiate and evaluate this internal representation

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

You can specify a list of functions that the library should support. Do not forget that some operations are unary (have one input - sine), some are binary (have two inputs - addition) and some can be both (such as minus).

For the basic version of the project, it can be assumed that all variables are scalar and all operations are well bracketed. For more complex versions, you can consider vector variables (which is related to, for example, matrix-vector multiplication) or ignoring parentheses or some operators, such as multiplication

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

The task is to write a package to minimize functions. The package should contain methods of the zeroth order (they do not use the derivative - for example simulated annealing), the first order (they use the first derivative - for example steepest gradient descent) and the second order (they use the second derivative - for example Newton's method). There will be a minimize function, which takes a function as the first argument and possible the first or second derivatives. Keyword arguments may include for example bounds (intervals are enough), starting point, generation methods for the starting point, maximum number of iterations, printing method or anything else. The minimize function must also work on vector variables.

As an example, let us give the function (and its derivatives)

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

We can then call minimization in many ways. We will give an example

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)

The first call does not use derivatives and thus should select some zero-order method. The second call will use the BFGS method from the specified starting point. The third call randomly generates a starting point and uses the default first-order optimization method with constraints. The fourth call will use the default second-order method. The type BFGS can be defined for example as follows

abstract type FirstOrder end
 
struct BFGS <: FirstOrder
 
end