A Group Theoretic Perspective on Unsupervised Deep Learning

Arnab Paul, Suresh Venkatasubramanian

This extended abstract, presented at ICLR 2015, offers a provocative theoretical framework for one of the most successful empirical tricks in deep learning: unsupervised pre-training. By applying the mathematical lens of group theory, the authors provide a formal intuition for why neural networks learn simple features first and how hierarchical representations emerge.

TL;DR

The paper uses the orbit-stabilizer theorem from group theory to explain why unsupervised pre-training works. It argues that "simple" features like edges are learned first because they have larger mathematical "stabilizers," making them easier targets for a learning algorithm to find in a high-dimensional search space.

What Problem Does This Paper Address?

Deep Learning (DL) has seen massive success, but a rigorous theoretical understanding of why it works remains elusive. Specifically, the authors tackle two key questions:

  1. Why do networks learn simple features first? Empirical evidence shows that early layers of a network consistently learn basic edges and gradients before moving to complex shapes.
  2. How do higher-order representations emerge? Why does the layer-by-layer pre-training of autoencoders lead to a useful hierarchy of features?

The authors suggest that the answer lies in the relationship between the complexity of a feature and the mathematical transformations that leave it unchanged.

Methods

The authors bridge the gap between deep learning and group theory by framing the training of an autoencoder as a search for a stabilizer.

In group theory, if a group $G$ acts on a set $X$, the stabilizer of an element $x$ is the subset of group elements that leave $x$ unchanged. The authors define an autoencoder as a transformation that, once trained, acts as a stabilizer for its input (i.e., it reproduces the input $f$ such that $T(f) \approx f$).

They utilize the Orbit-Stabilizer Theorem, which states that for a finite group, the size of an element's orbit (the set of all points reachable via group actions) multiplied by the size of its stabilizer equals the size of the group ($|O_x| \cdot |S_x| = |G|$). This implies an inverse relationship: the smaller the orbit, the larger the stabilizer.

Figure 1: (a) Autoencoder schematic, (b) Post-learning behavior, (c) Alternate ways of decomposing a signal. The theory suggests simpler features (bottom row) are learned first.

Datasets

Not discussed in the paper. This is a theoretical extended abstract focusing on conceptual frameworks rather than empirical benchmarking.

Key Insights and Ideas

  • Simplicity = Small Orbits: Intuitively, a simple feature like a straight line segment has a much smaller "orbit" under linear deformations (like rotation or scaling) than a complex, flower-like shape. A line looks like a line in fewer ways than a complex object looks like itself.
  • The "Big Target" Theory: Because of the inverse relationship in the orbit-stabilizer theorem, a small orbit implies a large stabilizer. If we view the learning process as a search (like a Markov chain) through the space of possible transformations, a larger stabilizer is a "bigger target." Therefore, the learning algorithm is statistically much more likely to "hit" a stabilizer for a simple feature (like an edge) much earlier than one for a complex feature.
  • Hierarchical Composition: The authors extend this to multiple layers. Each subsequent layer finds a feature with a large stabilizer relative to the previous layer's output. While these features are "simple" in the transformed space of the hidden layer, they correspond to increasingly complex, high-order representations when mapped back to the original input space.

Key Results

  • Theoretical Justification for Pre-training: The paper provides a formal reason for Geoff Hinton’s principle that learning a generative model (computer graphics) helps classification (computer vision).
  • Explaining Edge Detection: It offers a mathematical explanation for why edge-like features are the universal building blocks of early neural network layers: they are simply the easiest stabilizers to find.
  • Shadow Groups: The authors introduce the concept of "shadow groups"—mathematical structures that serve as close approximations to the transformations performed by neural network layers, even if the networks themselves don't strictly form groups.

Limitations and Future Work

  • Formal Proofs: As an extended abstract, the paper sketches these ideas rather than providing rigorous proofs for the existence and properties of "shadow groups" in real-world weight spaces.
  • Group Assumptions: The theory assumes the space of autoencoders behaves like a group. In practice, neural network transformations may not always satisfy group axioms (like invertibility).
  • Scaling to Modern Architectures: The paper focuses on layer-wise pre-training, a technique less common in the era of ResNets and Transformers, though the underlying logic of feature simplicity may still apply.

Summary updated

Abstract

Why does Deep Learning work? What representations does it capture? How do higher-order representations emerge? We study these questions from the perspective of group theory, thereby opening a new approach towards a theory of Deep learning. One factor behind the recent resurgence of the subject is a key algorithmic step called {\em pretraining}: first search for a good generative model for the input samples, and repeat the process one layer at a time. We show deeper implications of this simple principle, by establishing a connection with the interplay of orbits and stabilizers of group actions. Although the neural networks themselves may not form groups, we show the existence of {\em shadow} groups whose elements serve as close approximations. Over the shadow groups, the pre-training step, originally introduced as a mechanism to better initialize a network, becomes equivalent to a search for features with minimal orbits. Intuitively, these features are in a way the {\em simplest}. Which explains why a deep learning network learns simple features first. Next, we show how the same principle, when repeated in the deeper layers, can capture higher order representations, and why representation complexity increases as the layers get deeper.
BibTeX
@inproceedings{paul2015group,
  author = {Arnab Paul and Suresh Venkatasubramanian},
  title = {{A Group Theoretic Perspective on Unsupervised Deep Learning}},
  booktitle = {International Conference on Learning Representations},
  year = {2015},
  url = {http://arxiv.org/abs/1504.02462},
}
Figure