# Problem 1

*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.*

Neural networks are a family of models that can represent a wide class of functions. In this problem we will try to understand better what such networks can and cannot do. We will restrict ourselves to multi-layer perceptron (MLP) networks, using ReLU as the activation function.

Useful functions:

- $ReLU(x) = \begin{cases} 0 & \text{if } x < 0, \\ x & \text{otherwise} \end{cases}$

- $nn.Linear(x, y, bias)$

  If $x \in R^{n}$ (the input), $y \in R^{m}$ (the output), then $y = W \times x + b$, where $W \in R^{(m \times n)}$.

  $b \in R^{m}$ is 0 and cannot be modified by the learning algorithm if the parameter $bias = False$; otherwise it is considered a learnable parameter and is used in computing the output $y$.

## Question 1.1:

Can the network MLP1 represent any function learned by the network MLP2?

**MLP1:**

Code:

```python
import torch.nn as nn
model = nn.Sequential(
    nn.Linear(2, 4),
    nn.ReLU(),
    nn.Linear(4, 1, bias=False),
)
```

Corresponding graphical representation:

*[Figure: see the [original statement](https://docs.google.com/document/d/17uYj7I1qKqvrxk85XErk32Stk-DSelwAELItOveIUr0/edit). It shows the input $x$ (2 input nodes), connected through $W_1$ to the hidden layer $h$ (4 hidden-layer neurons), connected through $W_2$ to the output $y$ (output without a bias term).]*

**MLP 2:**

```python
import torch.nn as nn
model = nn.Sequential(
    nn.Linear(2, 3),
    nn.ReLU(),
    nn.Linear(3, 1),
)
```

*[Figure: see the [original statement](https://docs.google.com/document/d/17uYj7I1qKqvrxk85XErk32Stk-DSelwAELItOveIUr0/edit). It shows the input $x$ (2 input nodes), connected through $U_1$ to the hidden layer $z$ (3 hidden-layer neurons), connected through $U_2$ to the output $y$ (output with a bias term).]*

**Legend** (for the figures):

- Input (a plain light-purple circle)
- Output (without a bias term) (a plain pink circle)
- Output (with a bias term) (a pink double circle)
- Hidden-layer neuron (contains a bias, and ReLU is applied at the end of the operation) (a green circle with the ReLU symbol)

You may demonstrate this in one of two ways:

a) Theoretically,

b) Empirically, using experiments on a use case and a dataset of your choice; try to extract the intuition behind the answer from these experiments

## Question 1.2:

The general intuition in the AI community is that the number of layers plays an important role. This is also where the term ***deep-learning*** comes from, because ***deep*** refers to a large number of layers.

In the previous part, we tried to see whether MLP1 can express any function represented by MLP2. We will now consider the opposite direction.

**a) Can MLP2 express any function expressed by MLP1?**

In the same context, we can also think about the number of layers. The question then, given that the number of parameters and neurons is constant, becomes: can a model with a single layer represent the same functions as a model with several layers?

**b) Concretely, can MLP 4 (given below) express any function implemented by MLP 3?**

Can you show (empirically, or theoretically as above) whether this is true?

A few remarks:

- Both networks have approximately the same number of parameters, and they have the same total number of neurons
- Try to think about the problem from a geometric point of view.

  A. A ReLU unit divides the input space into two regions (using a line in 2D, the plane is divided into 2 half-planes; using a point in 1D, the line is divided into two half-lines):
     - A region in which the output is always 0 (for negative values of the input).
     - A region in which it behaves like a linear function (for positive values of the input).

  B. A linear layer can be seen as a combination of scaling, rotation and translation applied to the input, following the definition in part 1.1, $y = W \times x + b$. Thus, the parameter $b$ can be considered a translation, and the matrix $W$ can represent the operations of rotation (in the plane) and scaling.

MLP 3:

```python
model = nn.Sequential(
    nn.Linear(1, 3),
    nn.ReLU(),
    nn.Linear(3, 2),
    nn.ReLU(),
    nn.Linear(2, 1),
)
```

Graphical representation:

*[Figure: see the [original statement](https://docs.google.com/document/d/17uYj7I1qKqvrxk85XErk32Stk-DSelwAELItOveIUr0/edit). It shows the input $x$ (1 input node), connected through $W_1$ to the hidden layer $h$ (3 hidden-layer neurons), connected through $W_2$ to the hidden layer $v$ (2 hidden-layer neurons), connected to the output $y$ (output with a bias term); the last set of connections is also labelled $W_2$ in the figure.]*

MLP 4:

```python
import torch.nn as nn
model = nn.Sequential(
    nn.Linear(1, 5),
    nn.ReLU(),
    nn.Linear(5, 1),
)
```

Graphical representation:

*[Figure: see the [original statement](https://docs.google.com/document/d/17uYj7I1qKqvrxk85XErk32Stk-DSelwAELItOveIUr0/edit). It shows the input $x$ (1 input node), connected through $U_1$ to the hidden layer $z$ (5 hidden-layer neurons), connected through $U_2$ to the output $y$ (output with a bias term).]*