Why, in deep learning, do we get computational power by going deeper?

I know by the expressiveness of a neural networks that it can be seen as a chain of function compositions, i.e. $$g(f(.. z(x)..))$$ and also that, if we go deep, we can approximate complex functions $$f: \mathbb{R} \rightarrow [0,1]$$ with a lower number of units.

But why, if we go deeper, do we get computing power?

• You have to explain what do you exactly mean by "getting computing power". Commented Aug 31, 2022 at 17:28
• Thaks, I edited, hope is much clear now.
– f_s
Commented Aug 31, 2022 at 17:38
• What do you mean by computing power? I understand computing power as the ability for a computing to do more operations by seconds, which is clearly not what you mean. Commented Aug 31, 2022 at 19:50

It is not that we "get more computing power", it is the fact that deep networks are more expressive than shallow ones, which is pretty much the result of what you have started stating about composition. It might be helpful to think of an example - here's a nice one I've written about here

We define the t-saw-tooth function as a piece-wise affine function with $$t$$ pieces. Also, we define the hat function as $$hat(x)=relu(2relu(x)-4relu(x-0.5))$$.

note that hat is a 4-saw-tooth function by definition. We can use hat to concatenate saw-tooth functions - let $$t(x) = hat(x)+hat(x-1)$$ comprises of two hats, and is a 6-saw-tooth function, and the composition $$t(t(x))$$ is a 10-saw-tooth, $$t(t(t(x))))$$ is a 18-saw-tooth, and in general, a composition of $$T$$ functions ($$T$$ $$t(x)$$'s) is a $$(2+2^{T+1})$$-saw-tooth, namely, the composition is comprised of $$2^T$$ hats. How can we represent this composition using a shallow network? remember that every neuron in the (single) hidden layer "represents" a single relu, therefore two neurons can represent a single hat. As there are exponentially many hats, a shallow network will have to use exponentially many neurons ($$2^{T+1}$$ to be exact). On the other hand, a deep neural network would only need $$\Theta(T)$$ (if, for example, we use $$T$$ layers and $$2$$ nodes per layer). This is the case because the deep network $$i'th$$ layer receives as input the values of the $$(i-1)'th$$ layer, and for that matter is represents the composition of $$t(x)$$ simply as a product of its architectural design.

It would be simple, intuitive answer but generally deeper networks have more "space" to learn more complex features. They start from very simple "shapes" (using CNNs as an example) and gradually build towards more complex ones. Having more layers means there can be a lot of intermediary stages that will help in constituting final features (near the end of the network). This assures that the final features can be complex. In that case more details are considered in the middle layers and last layers can take advantage of these details.

Whereas shallow networks don't have that space for developing complicated features at the end. They must make use of only few layers therefore the increase of features details will be big between layers, making it harder for complex "shapes" to be found at the end. A lot of useful information maybe lost in the process.

Let's try to get the intuition with an example.

If you're already familiar with CNNs, we can use the example of Feature Maps. Feature Maps help us visualize what CNNs learn at each layer. The observation is that the ones in the first layer capture the fine details of the input image, the ones in the second use them to get the finer details (that's why the feature map is less visualizable) and the same goes on as we go deeper. The feature maps at the second last layer may be hardly visualizable but has more information than the previous layers to predict the output.

In case you're not familiar with CNNs, we can use the example of a multi-layered artificial neural network. The idea is same as the CNN. The first layer captures the simple details of the input and creates some features, the second layer uses those features to get the better details and the same goes on till the second last layer. We feed the final features to an output function which gives us the final output.

I agree that in practice having deeper networks makes it simpler to construct more expressive functions for the reasons that other people have mentioned. However, while it is a practical convenience, it is not a theoretically necessity. The Wikipedia page on the Universal approximation theorem reminds us that

Kurt Hornik, Maxwell Stinchcombe, and Halbert White showed in 1989 that multilayer feed-forward networks with as few as one hidden layer are universal approximators.

That is to say, in line of principle even a network with a single hidden layer can approximate any function.