In many machine learning tasks, models must distinguish between meaningful variations in data and "nuisance" transformations. For instance, a digit '3' remains a '3' regardless of a slight tilt, yet a global rotation could transform a '6' into a '9'. This paper, presented at AISTATS 2017, introduces a mathematically rigorous framework for building models that are "locally invariant" to specific transformations like rotations or translations.
The Challenge: Invariance vs. Selectivity
Convolutional Neural Networks (CNNs) are inherently robust to translations through pooling operations, but they often struggle with other transformation groups, such as rotations or scaling, unless specifically augmented. The core difficulty lies in the trade-off between invariance and selectivity. A model that is globally invariant to rotation might lose the ability to distinguish between objects that are rotations of one another but have different semantic meanings.
We require local invariance—the capacity to ignore small, expected transformations while remaining sensitive to large changes that alter an object's identity. Previous kernel-based attempts at this were either computationally prohibitive or lacked a principled method for defining "locality."
Methodology: LGIKA
The authors propose Local Group Invariant Kernel Approximation (LGIKA), leveraging group theory and kernel methods to achieve scalable local invariance.
1. Orbit Embeddings and RKHS Mapping
Instead of representing a data point $x$ as a single vector, the method considers its "orbit"—the set of all possible versions of $x$ under a group of transformations $G$. By treating this orbit as a probability distribution, the authors use a "characteristic kernel" to embed the distribution into a high-dimensional Reproducing Kernel Hilbert Space (RKHS). This mapping is injective, ensuring no information about the distribution is lost.
2. Achieving Locality
To implement local rather than global invariance, the framework introduces a probability density $q(g)$ over the group. By concentrating this density around the "identity" transformation (no change), the model learns to be invariant only to small transformations. This allows for a "soft" tuning of exactly how much invariance is required for a given task.
3. Scalable Approximations
To ensure computational feasibility, the authors employ Random Fourier Features (RFF) and Nyström approximations. These techniques approximate the complex "orbit kernel" with a finite set of random features, transforming a complex kernel problem into a standard linear learning problem. Furthermore, if transformations are "unitary" (like rotation), they can be applied to a small set of random "templates" (filters) rather than the entire dataset, significantly boosting efficiency.
Experimental Results
The LGIKA method was evaluated across three distinct domains: quantum chemistry, digit recognition, and general image classification.
Quantum Chemistry
On the Quantum Machine Dataset, which requires invariance to the permutation of atoms to predict atomization energies, LGIKA achieved a Root Mean Square Error (RMSE) of 10.05. This significantly outperformed the previous state-of-the-art "Rand-Coulomb" method, which recorded an RMSE of 11.40.
Rotated MNIST
In tests using Rotated MNIST (digits randomly rotated 0-360 degrees), LGIKA achieved 97.21% accuracy. This result outperformed standard deep CNNs and rotation-invariant RBMs, performing comparably to more complex architectures like Group-equivariant CNNs.
CIFAR-10
On the CIFAR-10 benchmark, LGIKA improved upon vanilla Random Fourier Features by nearly 5%. This demonstrates that even simple local invariance provides a significant performance boost to standard kernel machines when dealing with affine transformations (rotation, translation, and scaling).
Conclusion and Future Directions
LGIKA demonstrates that well-designed kernel methods can compete with, and sometimes exceed, the performance of deep neural networks for specific types of structured invariance. While the current implementation treats images as flat vectors, future work aims to apply this framework to local image patches to better exploit spatial correlations. Additionally, while the group of transformations must currently be specified by the user, future iterations may explore methods for the model to discover relevant transformations directly from the data.
Summary updated