Power of linear neural networks

Problem 4 Power of linear neural networks: Let $n ≥ 3$ be an odd natural number. Define the function $$MAJ_{n} : {−1, 1}^{n} → {−1, 1}$$ as, $$MAJ_{n}(x_{1}, . . . , x_{n}) = sgn(\sum_{i=1}^{n} x_{i}).$$

Consider fully connected neural networks with one hidden layer, n input neurons and one output neuron (the hidden layer can have any number of neurons).

All hidden and output neurons have identity activation, that is $σ(x) = x$.

Given n, define a neural network as above that computes the function $MAJ_{n}$ or prove that such a network does not exist.

Solution:

We can construct a fully connected neural network with one hidden layer, n input neurons, and one output neuron that computes the $MAJ_{n}$ function.

First, note that $MAJ_{n}$ can be expressed as the sign of a linear function. Specifically, we have:

$$MAJ_{n}(x_1, ..., x_n) = sgn \Big(x_1 + x_2 + ... + x_n \Big)$$

This suggests that we can use a linear combination of the input neurons as the input to the output neuron.

Let $w_1, w_2, ..., w_n$ be the weights on the input neurons, and let b be a bias term.

Then we can define the output neuron's input as:

$$z = w_{1}x_{1} + w_{2}x_{2} + ... + w_{n}x_{n} + b$$

If we choose the weights and bias appropriately, the sign of z will be the same as the sign of the sum $x_1 + x_2 + ... + x_n$.

Specifically, we can set:

\begin{eqnarray*} w_1 = w_2 = ... = w_n &=& 1/n\ b &=& -1/2 \end{eqnarray*}

With these choices, we have:

$$z = \frac{(x_1 + x_2 + ... + x_n)}{n} - \frac{1}{2}$$

If, $$x_1 + x_2 + ... + x_n > 0 \text{ i.e positive, then z > 0, (positive)}$$ Also, if $$x_1 + x_2 + ... + x_n < 0 \text{ i.e negative, then z < 0, (positive).}$$

Thus, the sign of z is the same as the sign of the sum, which is the desired output.

However, we only need one hidden neuron for this network, since the identity activation means that the output of each hidden neuron is just a linear combination of the input neurons.

Therefore, a neural network with one hidden layer, n input neurons, and one output neuron with the above weights and bias computes the MAJ_{n} function.