# Theory Test *English translation by SOTA – AI Community of the Romanian original, published with the permission of Asociația Nitro. Organisers who would like this translation removed can email team@sota-ai.org.* **National Artificial Intelligence Team Training Camp – June 2025** **THEORY TEST** ## Problem 1 1. Consider the following dataset about users: | ID | MonthlyIncome (euro) | SatisfactionScore (0–10) | |:-:|:-:|:-:| | 1 | 2300 | 7 | | 2 | 4500 | 8 | | 3 | 1000 | 4 | | 4 | 12000 | 6 | | 5 | 3100 | 9 | | 6 | 5000 | 8 | **a)** If we train a distance-based machine learning model (e.g. KNN), why is it important to normalise these columns? Specify a method by which they can be normalised. **b)** The IQR method is a robust technique for detecting atypical values (outliers) in a numerical dataset. It is based on setting limits, as follows: - Q1 (the first quartile) – the value at 25% of the sorted data; - Q3 (the third quartile) – the value at 75% of the sorted data; - Lower limit $= Q1 - 1.5 \times (Q3 - Q1)$ and Upper limit $= Q3 + 1.5 \times (Q3 - Q1)$ - Any value that lies outside these limits is considered an outlier. Apply the IQR method (described above) to identify any atypical values (outliers) in the **MonthlyIncome** column. **c)** Specify which of **Standard Scaling** and **Robust Scaling** would be more suitable to apply to the **MonthlyIncome** column. Justify your choice! ## Problem 2 2. Consider the following dataset about food products: | ID | FoodCategory | FatContent | Price | |:-:|:-:|:-:|:-:| | 1 | *dairy* | *high* | 5.4 | | 2 | *meat* | *low* | 13.5 | | 3 | *vegetables* | *medium* | 3.8 | | 4 | *meat* | *high* | 11.0 | | 5 | *vegetables* | *low* | 3.5 | **a)** Propose a complete encoding strategy for the categorical columns, justifying the choice for each one. **b)** Normalise the *Price* column using the **Min-Max Scaling** method. ## Problem 3 3. Consider the following situations in the process of training a predictive model, in which we want to apply regularisation: **a)** Suppose we have a large number of strongly correlated features and we want to reduce their contribution gradually, without eliminating them completely. **b)** We want to eliminate irrelevant features and to perform the selection of the relevant ones automatically. **c)** Suppose that only a small subset of the features is truly relevant for the prediction task. **d)** We want to reduce overfitting through a penalty distributed uniformly over all the coefficients of the model. Match each situation with the most suitable form of regularisation, choosing between L1 (Lasso) and L2 (Ridge). ## Problem 4 4. Suppose we want to determine whether Josh is in the office ($Y = 1$) or not ($Y = 0$) by analysing the data provided by three sensors installed in that space: - `Xc`: a chair pressure sensor, which indicates whether a person is sitting on the chair (`Xc = 1`) or not (`Xc = 0`); - `Xm`: a motion sensor, which detects whether there is movement in the room (`Xm = 1`) or not (`Xm = 0`); - `Xp`: an electricity meter, which shows whether there is energy consumption in the room (`Xp = 1`) or not (`Xp = 0`). Each sensor offers only a partial view of Josh's presence. For example, if Josh is in the office but is not sitting on the chair, the pressure sensor will not detect him. We have a historical dataset that includes the values measured by the sensors and the information on whether or not Josh was present at those moments. | **Day** | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | `Xc` | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | | `Xm` | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | | `Xp` | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | | `Y` | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | **a)** Using the Naive Bayes classifier, model the relationship between the sensor measurements and Josh's presence. Fill in the probability tables using maximum likelihood estimation (**Maximum Likelihood Estimation – MLE**). | `Y` | `P(Y)` | |:-:|:-:| | ⋮ | ⋮ | | `Xc` | `Y` | `P(Xc \| Y)` | |:-:|:-:|:-:| | ⋮ | ⋮ | ⋮ | | `Xm` | `Y` | `P(Xm \| Y)` | |:-:|:-:|:-:| | ⋮ | ⋮ | ⋮ | | `Xp` | `Y` | `P(Xp \| Y)` | |:-:|:-:|:-:| | ⋮ | ⋮ | ⋮ | **b)** Assuming that we receive a new set of observations from the sensors: `Xc = 0, Xm = 0, Xp = 1` – according to the probability tables estimated by MLE, is it more likely that Josh is present or absent? **c)** If, instead of MLE, we use **Laplace smoothing (Laplace Smoothing)** to estimate the probability tables, assuming a correction factor (k) equal to 1, how do the estimates change? **Laplace Smoothing:** $$ P_{\text{Laplace}}(x_i \mid y) = \frac{N(x_i, y) + k}{N(y) + k \cdot V} $$ where - $N(x_i, y)$ is the number of occurrences of the value $x_i$ together with the class $y$; - $N(y)$ is the total number of examples that belong to the class $y$; - $V$ is the total number of possible values for the features; - $k$ is the correction factor. ## Problem 5 5. We want to build a decision tree that predicts whether or not a student passes an exam. For this, we start from the following dataset, which contains 2 attributes: the type of coursework score (high, medium, low) and whether or not the student studied for the exam. | Coursework | Studied | Exam | |:--|:--|:--| | low | no | failed | | low | yes | passed | | medium | no | failed | | medium | yes | passed | | high | no | passed | | high | yes | passed | **a)** Compute the entropy $E(\mathit{Exam})$ ($\log_2 3 \approx 1.58$). **b)** Compute the entropy $E(\mathit{Exam} \mid \mathit{Coursework})$. **c)** Build a decision tree for the given dataset. $$ E(X) = -\sum_{i=1}^{n} p_i \cdot \log_2(p_i) $$ $$ E(Y|X) = -\sum_{x \in X} \sum_{y \in Y} P(y|x) \cdot P(x) \cdot \log_2(P(y|x)) $$ ## Problem 6 6. The **Manhattan** distance between two points $A(x_1, y_1)$ and $B(x_2, y_2)$ is defined by the formula: $$ \text{dist}_{\text{Manhattan}}(A, B) = |x_1 - x_2| + |y_1 - y_2| $$ Consider the following set of points in the 2D plane: $$ P = \{A(1, 2),\ B(2, 1),\ C(4, 5),\ D(7, 8),\ E(8, 8),\ F(9, 9)\} $$ The initial centroids are: $$ C_1^{(0)} = (2, 2), \quad C_2^{(0)} = (8, 9) $$ **a)** Apply a first step of the K-Means algorithm, using the Manhattan distance. Specify, for each point, which cluster it will belong to. **b)** After the two clusters have been formed, recompute their centroids as the arithmetic mean of the points in the cluster (on each coordinate). ## Problem 7 7. We start from the following game tree, in which the $\triangle$ nodes correspond to the MAX player and the $\nabla$ nodes correspond to MIN. *[Figure: see the original statement ([PDF](https://olimpiada.nitro-ai.org/2025/lot/subiecte-teorie.pdf), page 4). The tree is transcribed below: the root is a MAX node with three MIN children, each MIN node has three MAX children, and each MAX node has three leaves; leaf values are listed from left to right.]* ```text △ (MAX, root) ├── ∇ (MIN) │ ├── △ (MAX): 5, 1, 4 │ ├── △ (MAX): 2, 7, 9 │ └── △ (MAX): 3, 5, 7 ├── ∇ (MIN) │ ├── △ (MAX): 10, 2, 5 │ ├── △ (MAX): 5, 6, 4 │ └── △ (MAX): 8, 9, 2 └── ∇ (MIN) ├── △ (MAX): 3, 7, 2 ├── △ (MAX): 7, 6, 5 └── △ (MAX): 9, 8, 9 ``` **a)** Propagate the values in this game tree and show the path that will be chosen by a **MINIMAX** algorithm. **b)** Check whether α / β pruning can be applied to this game tree. Highlight the possible prunings (specifying the α / β values for the nodes of interest) and specify the type of each pruning. **c)** Suppose we have a game in which the **MAX** player has the ability to control the actions of the **MIN** player. More precisely, the **MAX** player will be able to force the **MIN** player to choose a particular action, but to do so will have to pay a cost $c = 2$ (with the same weight as the values given in the leaves of the game tree). Argue whether or not it is optimal for the **MAX** player to use this ability, paying the cost $c$, based on the game tree. ## Problem 8 8. Consider the following weighted graph as a representation of the state space of a search problem. We take $A$ to be the initial state of the problem and $G$ the final state of the problem. If the graph has the edge $(U, V)$, this means that for state $U$ we have state $V$ as one of the next states, and vice versa (the graph can be traversed in both directions). We also know a heuristic function for which one value is missing. *[Figure: see the original statement ([PDF](https://olimpiada.nitro-ai.org/2025/lot/subiecte-teorie.pdf), page 4). The graph is transcribed below: $A$ is the initial state and $G$ the final state; every edge is undirected.]* | Edge | A–B | A–C | B–C | B–D | C–D | D–E | D–F | D–G | E–G | F–G | |:--|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | Weight | 1 | 4 | 1 | 5 | 3 | 8 | 3 | 9 | 2 | 5 | | State | A | B | C | D | E | F | G | |:--|:-:|:-:|:-:|:-:|:-:|:-:|:-:| | $h$ | 10 | ? | 9 | 7 | 1.5 | 4.5 | 0 | **a)** Specify what value $h(B)$ must have for the heuristic $h$ to be admissible, and what value $h(B)$ should have for the heuristic $h$ to be consistent. Justify your answers! **b)** Propose a heuristic function for which the result of the A\* algorithm applied to this search space is $A \rightarrow C \rightarrow B \rightarrow D \rightarrow E \rightarrow G$. **c)** Consider two heuristic functions $h_1(s)$ and $h_2(s)$ that can be used with the A\* algorithm, knowing that they are admissible. We want to combine these two functions so as to obtain a function $g$. Can we construct a function $g$ that guarantees that fewer nodes are explored (compared with applying A\* with the function $h_1$ or A\* with the function $h_2$) and that guarantees the admissibility condition? Explain, and give an example of a definition for the function $g$. You may illustrate this using the given graph. ## Problem 9 9. The following sentences in natural language are given: - *"If a program is correct, then it produces conforming results. `PROG1` is a correct program. Therefore, `PROG1` produces conforming results."* **a)** Translate the above into propositional logic. **b)** Prove the statement by contradiction (reductio ad absurdum) using resolution. **Note:** resolution works only on sentences converted to CNF. ## Problem 10 10. Knowing that the following statements are true: *"The bowed head is not cut off by the sword"* (a Romanian proverb: *"Capul plecat nu este tăiat de sabie"*), and that *"Marcel's head was cut off."*, we want to prove that *"Marcel did not have his head bowed."*. **a)** Rephrase the proverb as a logical sentence (in first-order logic). **b)** Prove, using the resolution method, the claim that *Marcel did not have his head bowed*. **Attention:** proofs that do not use the resolution method receive no points. ## Problem 11 11. Consider the following constraint satisfaction problem (CSP): the variables $X$, $Y$ and $Z$ have the domains: - $X : \{1, 2, \ldots, 10\}$ - $Y : \{5, 6, \ldots, 10\}$ - $Z : \{5, 6, \ldots, 15\}$ and we have the following constraints: - $X > Y$ - $Y + Z = 12$ - $X + Z = 15$ **a)** Is there any arc that is **arc-consistent** for the given problem? **b)** Consider the arc consistency algorithm (AC-3). How is the queue of arcs initialised, and what is the maximum number of times an arc can be added to the queue? **c)** Apply the arc consistency algorithm (AC-3) to update the domains of the variables. ## Problem 12 12. Three exams (Math, CS, Physics) must be scheduled in two rooms (S1, S2), in three time slots (T1, T2, T3). For this schedule we have the following constraints: - Math and CS cannot be at the same time (they have students in common) - Physics and CS cannot be in the same room - A room cannot host two exams in the same time slot **a)** Represent the problem as a CSP and explain how the variables can be represented and what the domains of the variables are. **b)** State all the constraints in a formal way, using the variables proposed in the previous part. **c)** Use backtracking to find a valid solution. ## Problem 13 13. In a grid world, Pacman navigates a dangerous environment full of ghosts and food pellets. However, the very large size of this state space makes it impossible to use the **Q-learning** method directly in its classical form — which requires storing the $Q$-values for every state-action pair. To overcome this problem, we choose a strategy based on **features**: instead of storing every $Q$-value explicitly, Pacman uses a **linear approximation** function, in which the $Q$-value is computed from a set of features extracted from the current state and action. The chosen features, $F_g$ and $F_p$, for this representation are: - $F_g(s, a) = A(s) + B(s, a) + C(s, a)$: measures how close to, or exposed to, the ghosts Pacman is. - $F_p(s, a) = D(s) + 2 \cdot E(s, a)$: reflects the accessibility of the food pellets. - $A(s)$: the number of ghosts located one step away from the current state. - $B(s, a)$: the number of ghosts touched immediately after action $a$. - $C(s, a)$: the number of ghosts one step away from the position Pacman reaches after action $a$. - $D(s)$: the number of food pellets located one step away from the current state. - $E(s, a)$: the number of food pellets consumed by performing action $a$. For this Pacman grid, the ghosts will always be **stationary**, and the action space is {left, right, up, down, stay}. *[Figure 1: Current state – see the original statement ([PDF](https://olimpiada.nitro-ai.org/2025/lot/subiecte-teorie.pdf), page 6). The figure shows Pacman in the middle of a small walled area, with a red ghost in the cell directly to its left, a cyan ghost in the cell directly to its right, and a food pellet in the cell directly above it.]* **a)** You must compute the values of the features Fg and Fp for each available action: left, right, up, stay; in the state shown in Figure 1 (previous page). **b)** After several episodes of **Q-learning**, Pacman has learned to evaluate actions using weights associated with each feature: - $w_g = -10$: the weight associated with exposure to ghosts. - $w_p = +100$: the weight associated with opportunities to consume food pellets. Thus, the $Q$-value for an action $a$ in the current state $s$ is computed as: $$ Q(s, a) = w_g \cdot F_g(s, a) + w_p \cdot F_p(s, a) $$ The $Q$-values must be computed for each of the actions: **left**, **right**, **up**, **stay** from the current state shown in the figure. **c)** A specific transition is now observed: - Pacman starts from state $s$ and chooses the action *up*, - It reaches the new state $s'$, where a food pellet has been consumed, - It receives a reward $R(s, a, s') = 250$. From the new state $s'$, the possible actions are *down* and *stay*. A discount factor $\gamma = 0.5$ is assumed. The new estimate of the $Q$-value for the initial state and action — that is, for $Q(s, \mathit{up})$ — must be computed using the update rule: $$ Q_{\mathit{new}}(s, a) \leftarrow R(s, a, s') + \gamma \cdot \max_{a'} Q(s', a') $$ **d)** Given the new estimated value for $Q$, and knowing the current $Q$-value estimated by the feature function, we use the **weight update rule** in Q-learning: $$ w_i \leftarrow w_i + \alpha \cdot \delta \cdot F_i(s, a) $$ where: - $\alpha = 0.5$ is the **learning rate**, - $\delta = Q_{\text{new}} - Q_{\text{current}}$ is the **prediction error**, - $F_i(s, a)$ are the values of the features $F_g$ and $F_p$ for the action "up". The final result is an updated set of **weights** that will guide Pacman's future decisions in a more intelligent way, adapted to the experience accumulated. Starting from these relations, compute the values of the weights $w_g$ and $w_p$. ## Problem 14 14. A classification model was evaluated on a test set and produced the following confusion matrix: | | **Predicted A** | **Predicted B** | **Predicted C** | |:--|:-:|:-:|:-:| | **Actual A** | 40 | 5 | 5 | | **Actual B** | 4 | 35 | 11 | | **Actual C** | 2 | 8 | 40 | **a)** Compute the precision for each class (**A**, **B**, **C**). **b)** Compute the **macro-average F1** for this model, that is, the arithmetic mean of the F1-scores obtained for each class. **c)** Compute the **micro-average Recall** for this model. **d)** If the application that uses this classification model aims at the correct detection of cases of class **C** (for example, a rare and very serious disease), which metric should be maximised? What method can you propose to improve the performance for this class? ## Problem 15 15. In machine learning, *similarity functions* play a very important role both in automatic classification and in clustering. Let $X$ be a set consisting of rectangular images of arbitrary dimensions, in which each pixel is represented as an integer from the set $\{0, \ldots, 255\}$. Let $k_1 : X \times X \rightarrow \mathbb{R}$ be an image *similarity function*, defined as follows: $k_1(x, x')$ = the number of square regions (in English, *pixel patches*) of size $16 \times 16$ pixels that appear both in image $x$ and in image $x'$. > **Clarification** > > The position at which such a *square region* appears will not be taken into account, only the *image* / colouring of the region itself. Such a *region* may appear in several positions within the same image, but the function $k_1(x, x')$ will "count" a given *square region* only once if it appears [it does not matter exactly how many times] both in $x$ and in $x'$. **a)** Prove that the function $k_1$ has the following property: there exist $d \in \mathbb{N}^*$ and a function ("mapping") $\phi : X \rightarrow \mathbb{R}^d$ such that $k_1(x, x') = \phi(x) \cdot \phi(x')$ for all $x$ and $x' \in X$. In other words, the function $k_1$ is a *kernel function*. Here $\cdot$ denotes the dot product of vectors. **b)** Now let another *similarity function* be: $$ k_2(x, x') = \begin{cases} 1 & \text{if } k_1(x, x') \geq 1, \text{ i.e. there is at least one common "patch"} \\ & \text{(square region) for } x \text{ and } x' \\ 0 & \text{otherwise.} \end{cases} $$ Prove that the function $k_2$ has the following property: there exist a set of images $x_1, \ldots, x_n$ and a column vector $f \in \mathbb{R}^n$ such that $f^\top G f < 0$, where $\top$ denotes the transpose operation and $G$ is the $n \times n$ matrix with the entries $G(i, j) \overset{\text{def.}}{=} k_2(x_i, x_j)$, for $i, j = 1, \ldots, n$. In other words, the function $k_2$ is **not** positive semidefinite, and therefore it is **not** a kernel function (according to Mercer's theorem). > **Hint** > > You may carry out the proof constructively, that is, by choosing the number $n$ conveniently and "constructing" / defining the images $x_1, \ldots, x_n$ so that there exists $f \in \mathbb{R}^n$ with the property $f^\top G f < 0$. ## Problem 16 16. In recommender systems, the similarity between users or between items plays an essential role in predicting preferences. Consider a recommender system where: - $U = \{u_1, u_2, \ldots, u_n\}$ is the set of users; - $I = \{i_1, i_2, \ldots, i_m\}$ is the set of items (for example, films); - $R \in \mathbb{R}^{n \times m}$ is the rating matrix, where $R_{uj}$ is the rating given by the user $u \in \{u_1, u_2, \ldots, u_n\}$ to the item $i_j$, or is unknown if there is no rating. We now define a similarity function between two users $u$ and $v$ as follows: $$ \text{sim}(u, v) = \frac{\sum_{j \in I_{uv}} (R_{uj} - \bar{R}_u)(R_{vj} - \bar{R}_v)}{\sqrt{\sum_{j \in I_{uv}} (R_{uj} - \bar{R}_u)^2} \cdot \sqrt{\sum_{j \in I_{uv}} (R_{vj} - \bar{R}_v)^2}} $$ where $I_{uv}$ is the set of items rated by both users, and $\bar{R}_u$ is the mean of the ratings given by user $u$. > **Clarification** > > This similarity function is known as the **Pearson correlation** and is frequently used in user-based collaborative filtering. **a)** Suppose we have the following rating matrix (with "`-`" indicating a missing rating): $$ R = \begin{bmatrix} 5 & 3 & \texttt{-} & 1 \\ 4 & \texttt{-} & 3 & 2 \\ 1 & 1 & 5 & 5 \\ \texttt{-} & \texttt{-} & 5 & 4 \end{bmatrix} $$ Compute: - $\text{sim}(u_1, u_2)$ - $\text{sim}(u_1, u_3)$ State which of the two users is *more similar* to user $u_1$, taking $\sqrt{6} \approx 2.45$. **b)** Using user-based collaborative filtering, predict the rating that user $u_1$ might give to item $i_3$, using only the values given by the other two users ($u_2$ and $u_3$), based on the formula: $$ \hat{R}_{u_1,3} = \bar{R}_{u_1} + \frac{\sum\limits_{v \in \{u_2, u_3\}} \text{sim}(u_1, v) \cdot (R_{v3} - \bar{R}_v)}{\sum\limits_{v \in \{u_2, u_3\}} |\text{sim}(u_1, v)|} $$ **c)** We discuss a limitation of the method above. What happens in the case of a new user who has not rated any item (the so-called *cold-start* problem)? Propose a solution based on **content-based** filtering that could mitigate this problem. > **Hint** > > You may assume that each item is described by a feature vector (for example, genres for films). Think about how this vector could be used to recommend items to a user with no previous ratings. ## Problem 17 17. Sometimes we need to compare rankings. How can we quantify the similarity between two rankings? For a music chart, such a measure will tell us: *"How much do these two lists of top albums/tracks agree?"* We can view a ranking as a permutation $x$, where $x_i$ represents the position (rank) of element $i$. A whole family of correlation statistics for ordinal data is based on the number of **concordant** and **discordant** pairs between two variables. We compare all possible pairs of elements and count how many are ordered in the same way and how many in the opposite order. **Concordant pair:** if both rankings agree on the order of two elements (that is, element $i$ is ranked higher, or lower, than element $j$ in **both** lists). **Discordant pair:** if the two rankings disagree (that is, element $i$ is higher than $j$ in one list but lower in the other). Mathematically, the number of concordant pairs is: $$ P = \left| \{ (i, j) : 1 \leq i < j \leq n,\ (x_i - x_j)(y_i - y_j) > 0 \} \right|. $$ Similarly, the number of discordant pairs is: $$ Q = \left| \{ (i, j) : 1 \leq i < j \leq n,\ (x_i - x_j)(y_i - y_j) < 0 \} \right|. $$ The **PQ kernel** between two rankings $x$ and $y$ is defined as: $$ k_{PQ}(x, y) = P - Q. $$ We want to prove that $PQ$ is indeed a **kernel**, by showing how we can explicitly construct the feature map $\Psi$ such that: $$ k_{PQ}(x, y) = P - Q = \langle \Psi(x), \Psi(y) \rangle, $$ where $\langle \cdot, \cdot \rangle$ denotes the dot product.