Week 4, Video: Why Deep Representations?

At the end of the video, Andrew says that a shallow network with just one hidden layer needs exponentially more units compared to the deeper neural network. I don’t understand this. Andrew said that the shallower network would require exponential units because of exponential possible settings of variables x1, … xn. Can someone please clarify this?

Thanks

Hi, I think this is explained in the paper “When and Why Are Deep Networks Better than Shallow Ones?” whose abstract is as follows:

"While the universal approximation property holds both for hierarchical and shallow networks, deep networks can approximate the class of compositional functions as well as shallow networks but with exponentially lower number of training parameters and sample complexity.

Compositional functions are obtained as a hierarchy of local constituent functions, where “local functions” are functions with low dimensionality. This theorem proves an old conjecture by Bengio on the role of depth in networks, characterizing precisely the conditions under which it holds. It also suggests possible answers to the the puzzle of why high-dimensional deep networks trained on large training sets often do not seem to show overfit."