The connection between number of layer of DNN and computational complexity of it

number of layer of DNN and computational complexity of it are correlated after optimization, but how to estimate it before designing DNN?

1 Answer

The computational complexity of DNNs is based on 3 main factors.

1. Matrix Multiplication
2. Non linear transformation
3. Weight sharing

Matrix multiplication is the fundamental operation when computing the forward and backward passed in DNNs if using back-propagation. As the complexity of matrix multiplications becomes more expensive as the size of matrices become larger, understanding how to construct networks with effectively sized later which balance the time complexity with accuracy becomes imperative.

Nonlinear transformations allow DNNs to learn nonlinear functions. It is a very important aspect and has been studied rigorously. Classically, the functionf(x) = 1(1+exp(x)) was used to squash outputs from linear layers to be a nonlinear output. However this function has recently been replaced in many applications with the linear rectifier unit (ReLU) f(x)=max(x,0). The relu is much much faster to compute and doesn’t seem to affect the end performance substantially or even noticeably in some situations.

Weight sharing is the idea that some weights in a DNN must share the same value. Beyond the theoretical reasons why this is chosen, it also decreases the number of values that must be updated when performing back-propagation. This is the reason why Convolutional NNs are orders of magnitude faster than their non-convolutional counter parts for image recognition tasks.

There are other things to be aware of when trying to analyze the computational complexity of DNNs but they usually relate to one of the 3 items above.

To estimate the complexity, counting the number of matrix multiplications and their matrix sizes, add time for nonlinearities and you should have a pretty good estimate.