Capacity of Group-invariant Linear Readouts from Equivariant Representations: How Many Objects can be Linearly Classified Under All Possible Views?

Abstract

Equivariance has emerged as a desirable property of representations of objects subject to identity-preserving transformations that constitute a group, such as translations and rotations. However, the expressivity of a representation constrained by group equivariance is still not fully understood. We address this gap by providing a generalization of Cover's Function Counting Theorem that quantifies the number of linearly separable and group-invariant binary dichotomies that can be assigned to equivariant representations of objects. We find that the fraction of separable dichotomies is determined by the dimension of the space that is fixed by the group action. We show how this relation extends to operations such as convolutions, element-wise nonlinearities, and global and local pooling. While other operations do not change the fraction of separable dichotomies, local pooling decreases the fraction, despite being a highly nonlinear operation. Finally, we test our theory on intermediate representations of randomly initialized and fully trained convolutional neural networks and find perfect agreement.

arXiv commentVersion accepted to ICLR 2022

References in corpus (25)

• Group Equivariant Convolutional Networks
• On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups
• 3D Steerable CNNs: Learning Rotationally Equivariant Features in Volumetric Data
• DeepSphere: Efficient spherical Convolutional Neural Network with HEALPix sampling for cosmological applications
• Balanced Excitation and Inhibition are Required for High-Capacity, Noise-Robust Neuronal Selectivity
• Classification and Geometry of General Perceptual Manifolds
• Universal Invariant and Equivariant Graph Neural Networks
• Covariant Compositional Networks For Learning Graphs
• A Group-Theoretic Framework for Data Augmentation
• Deep Models of Interactions Across Sets
• Lorentz Group Equivariant Neural Network for Particle Physics
• PDE-based Group Equivariant Convolutional Neural Networks
• Hierarchical, rotation-equivariant neural networks to select structural models of protein complexes
• On Learning Sets of Symmetric Elements
• Small ReLU networks are powerful memorizers: a tight analysis of memorization capacity
• Universal approximations of permutation invariant/equivariant functions by deep neural networks
• Deep Scale-spaces: Equivariance Over Scale
• Scale equivariance in CNNs with vector fields
• Generalization Error of Invariant Classifiers
• A rotation-equivariant convolutional neural network model of primary visual cortex
• A Practical Method for Constructing Equivariant Multilayer Perceptrons for Arbitrary Matrix Groups
• Statistical learning theory of structured data
• Counting the learnable functions of structured data
• On the Benefits of Invariance in Neural Networks
• Coordinate Independent Convolutional Networks -- Isometry and Gauge Equivariant Convolutions on Riemannian Manifolds