Problem 1

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 [email protected].

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:

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

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

[Figure: see the original statement. 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:

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

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. 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).]