4
$\begingroup$

How do I determine the time complexity of the forward pass algorithm of a feedforward neural network? How many multiplications are done to generate the output?

$\endgroup$
5
$\begingroup$

Let's suppose that we have an MLP with $15$ inputs, $20$ hidden neurons and $2$ output neurons. The operations performed are only in the hidden and output neurons, given that the input neurons only represent the inputs (so they do not perform any operation).

Each hidden neuron performs a linear combination of its inputs followed by the application of a non-linear (or activation) function. So, each hidden neuron $j$ performs the following operation

\begin{align} o_j = \sigma \left(\sum_{i}^{15} w_{ij}x_i \right),\tag{1}\label{1} \end{align}

where $i$ is the input coming from the input neuron $i$, $w_{ij}$ is the weight of the connection from the input neuron $i$ to the hidden neuron $j$, and $o_j$ is used to denote the output of neuron $j$.

There are $20$ hidden neurons and, for each of them, according to equation $\ref{1}$, we perform $15$ multiplications (ignoring any multiplications that might be associated with the activation function), so $15*20 = 300$ multiplications are performed at the (only) hidden layer. In general, if there are $n$ inputs and $m$ hidden neurons, then $n*m$ multiplications will be performed in the first hidden layer.

Now, each neuron $j$ at the next layer (in this case, the output layer), also performs a linear combination followed by the application of an activation function

\begin{align} o_j = \tau \left(\sum_{i}^{20} w_{ij}x_i \right),\tag{2}\label{2} \end{align}

where $\tau$ is another activation function which might or not be equal to $\sigma$, but we ignore all multiplications that might involve the application of the activation functions (we just want to count the ones in the linear combinations). Of course, in this case, $x_i$ corresponds to the activation of neuron $i$ (of the hidden layer).

Similarly to the previous reasoning, there are $2$ output neurons and, to compute the output of each of them, $20$ multiplications are performed (in the linear combination), so there are a total of $2*20 = 40$ multiplications at the output layer.

So, an MLP with $15$ inputs, $20$ hidden neurons and $2$ output neurons will perform $15*20 + 20*2 = 340$ multiplications (excluding activation functions). Of course, in this case, the number of multiplication depends not only on the number of neurons but also on the input size.

In general, an MLP with $n$ inputs, $M$ hidden layers, where the $i$th hidden layer contains $m_i$ hidden neurons, and $k$ output neurons will perform the following number of multiplications (excluding activation functions)

\begin{align} nm_{1} + m_{1}m_{2} + m_{2}m_{3} + \dots + m_{M-1}m_{M} + m_{M}k = nm_{1} + m_{M}k + \sum_{i=1}^{M-1} m_{i}m_{i+1} \end{align}

which, in big-O notation, can be written as

\begin{align} \Theta\left(nm_{1} + m_{M}k + \sum_{i=1}^{M-1} m_{i}m_{i+1} \right) \end{align}

where $\Theta(\cdot)$ is used (as opposed to $\mathcal{O}(\cdot)$) because this is a strict bound. If you have just one hidden layer, the number of multiplications becomes

\begin{align} \Theta\left(nm_{1} + m_{1}k \right) \end{align}

Of course, at each layer, the number of multiplications can be computed independently of the multiplications of the other layers (you can think of each layer as a perceptron), hence we sum (and not e.g. multiply) the multiplications of each layer when computing the total number of multiplications of the whole MLP.

In general, when analyzing the time complexity of an algorithm, we do it with respect to the size of the input. However, in this case, the time complexity (more precisely, the number of multiplications involved in the linear combinations) also depends on the number of layers and the size of each layer. The time complexity of a forward pass of a trained MLP thus is architecture-dependent (which is a similar concept to an output-sensitive algorithm).

You can easily include other operations (sums, etc.) in this reasoning to calculate the actual time complexity of a trained MLP.

$\endgroup$
  • 1
    $\begingroup$ Thank you for your complete answer. It helped me a lot. Unfortunately my reputation is not enough yet for voting you up. So virtually i give you +1 for your good explanation :). Thanks. $\endgroup$ – Artificial Jul 28 at 10:08
  • $\begingroup$ From a different perspective, if we see Neural Networks as plain matrix products (post training feedforward), shouldn't it be something of the form {O(n^3)}? Just my two cents... $\endgroup$ – Karan Shah Jul 29 at 16:17
  • $\begingroup$ @KaranShah No, it shouldn't, but what is $n$ in your case? The complexity is proportional to the number of layers and the number of neurons per layer. $\endgroup$ – nbro Jul 29 at 16:25
  • $\begingroup$ Yes, it is a function of the number of layers. So assuming O(n^3) for 1 matrix product, it scales for L layers in the same manner, that's how I'm seeing it... $\endgroup$ – Karan Shah Jul 29 at 17:04
  • 1
    $\begingroup$ @KaranShah Matrix-matrix multiplication is $O(n^3)$ (actually, you can have a better bound than this). Anyway, the input is a vector, so you multiply a vector by a matrix (and not a matrix by another matrix), which is not $n^3$. See https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra. $\endgroup$ – nbro Jul 29 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.