How Deep Networks Learn Sparse and Hierarchical Data: the Sparse Random Hierarchy Model
This work addresses a fundamental question in machine learning about the learnability of high-dimensional data, providing a theoretical explanation for deep learning success, but it is incremental as it builds on existing viewpoints without introducing a new paradigm.
The authors tackled the problem of explaining why deep networks learn hierarchical representations and insensitivity to invariances by introducing the Sparse Random Hierarchy Model (SRHM), showing that sparsity in generative models leads to insensitivity to spatial transformations and that CNNs learn hierarchical representations when this insensitivity is acquired, with quantified sample complexity depending on sparsity and hierarchy.
Understanding what makes high-dimensional data learnable is a fundamental question in machine learning. On the one hand, it is believed that the success of deep learning lies in its ability to build a hierarchy of representations that become increasingly more abstract with depth, going from simple features like edges to more complex concepts. On the other hand, learning to be insensitive to invariances of the task, such as smooth transformations for image datasets, has been argued to be important for deep networks and it strongly correlates with their performance. In this work, we aim to explain this correlation and unify these two viewpoints. We show that by introducing sparsity to generative hierarchical models of data, the task acquires insensitivity to spatial transformations that are discrete versions of smooth transformations. In particular, we introduce the Sparse Random Hierarchy Model (SRHM), where we observe and rationalize that a hierarchical representation mirroring the hierarchical model is learnt precisely when such insensitivity is learnt, thereby explaining the strong correlation between the latter and performance. Moreover, we quantify how the sample complexity of CNNs learning the SRHM depends on both the sparsity and hierarchical structure of the task.