Compositional Kernel Machines

Robert Gens, Pedro DomingosICLR 2017 · OpenReview

In the realm of computer vision, Convolutional Neural Networks (convnets) are the undisputed leaders. However, their dominance comes at a cost: they are notoriously difficult to train, requiring massive datasets, specialized hardware, and extensive hyperparameter tuning. In this paper, researchers propose a compelling alternative: Compositional Kernel Machines (CKMs).

TL;DR

Compositional Kernel Machines combine the structural advantages of convnets—such as hierarchical feature extraction and translation invariance—with the stable, instance-based learning of kernel methods. By using sum-product networks to efficiently evaluate an exponential number of "virtual" training instances, CKMs can outperform Support Vector Machines (SVMs) and compete with convnets, often training faster on a CPU than a convnet does on a GPU.

The Problem: Convnets vs. Kernel Methods

The authors highlight a fundamental tension in machine learning architectures. On one hand, convnets are powerful because they encode compositionality (building complex objects from simple parts) and symmetry (recognizing an object regardless of its position). However, their loss landscapes are non-convex, making them prone to local optima and computationally expensive to retrain.

On the other hand, Instance-Based Learning (IBL) methods, like k-Nearest Neighbors (k-NN) or SVMs, boast much simpler, convex training profiles. Yet, they suffer from the "curse of dimensionality." In high-dimensional spaces like image data, an astronomical number of training samples is required to find a neighbor that closely matches a query.

The goal of this research is to design a model that inherits the structural priors of a convnet while maintaining the learning efficiency of a kernel machine.

Methods: Virtual Instances and Sum-Product Functions

The core innovation of the CKM is the concept of virtual instances. Instead of comparing a query image to a single training image, the CKM compares it to an exponential number of "rearrangements" of pieces from the training set.

CKM Architecture

To make this computationally feasible, the authors leverage Sum-Product Functions (SPFs):

  1. Leaf Kernels: These measure the similarity between small local patches (using ORB features in the authors' experiments).
  2. Product Nodes: These represent the "composition" of parts. If the model has seen a roof and a door in different training images, a product node allows it to recognize a "house" composed of those distinct parts.
  3. Sum Nodes: These act as mixtures, allowing the model to handle different possible arrangements or virtual instances.

By applying the Sum-Product Theorem, the CKM can sum over this exponential set of combinations in time that is only linear relative to the size of the network. For training, the model uses block-coordinate gradient descent to optimize weights using a multiclass squared-hinge loss, made efficient through SPF caching.

Datasets

The authors evaluate CKMs on three variations of the NORB dataset (a collection of 3D object images):

  • Small NORB: The standard benchmark for 3D object recognition.
  • NORB Compositions: A custom dataset where images contain three different toys, testing the model's ability to recognize novel compositions.
  • NORB Symmetries: A dataset designed to test generalization to new angles, lighting conditions, and distortions.

Key Insights

  • The Rearrangement Hypothesis: The visual world can be understood as a rearrangement of low-dimensional pieces we have seen before. CKMs formalize this by constructing virtual training examples on the fly.
  • Implicit Augmentation: While convnets often require explicit data augmentation (flipping, cropping, rotating), CKMs have this invariance built directly into their architecture. They effectively "augment" the training set exponentially without increasing data storage.
  • CPU vs. GPU Efficiency: Remarkably, a CKM trained on a CPU can be competitive with a convnet trained for much longer on a GPU, as CKMs avoid the dozens of epochs required by stochastic gradient descent.
  • Structure over Parameters: Experiments show that even a CKM with uniform weights (no optimization) performs exceptionally well, suggesting the hierarchical structure itself does much of the heavy lifting.

Key Results

The empirical results demonstrate that CKMs are highly sample-efficient and excel at compositional tasks.

Accuracy vs. Training Instances
  • Accuracy: On Small NORB, the CKM with weight learning ($CKM_W$) achieved 89.8% accuracy, outperforming SVMs (88.4%) and approaching a convnet trained for 14 epochs (94.0%).
  • Compositional Power: In the "NORB Compositions" task, the CKM achieved 82.4% accuracy, significantly outperforming a standard convnet (50.6%) and an SVM using convnet-extracted features (75.0%).
  • Sample Efficiency: Learning curves indicate that CKMs generalize much better than competing methods when training data is scarce, particularly when learning symmetries.

Limitations and Future Work

  • Feature Learning: Currently, CKMs rely on hand-crafted features (like ORB) for their leaf kernels, whereas convnets learn their lowest-level features from scratch. Future CKMs could benefit from integrated feature learning.
  • Model Size: Like many instance-based methods, CKMs face a memory trade-off. They train rapidly, but the model size grows with the number of training instances, potentially leading to high memory usage for massive datasets.
  • Architecture Depth: Exploring more expressive CKM architectures, such as deeper hierarchies or more complex symmetry groups, remains a key direction for future research.

Summary updated

Abstract

Convolutional neural networks (convnets) have achieved impressive results on recent computer vision benchmarks. While they benefit from multiple layers that encode nonlinear decision boundaries and a degree of translation invariance, training convnets is a lengthy procedure fraught with local optima. Alternatively, a kernel method that incorporates the compositionality and symmetry of convnets could learn similar nonlinear concepts yet with easier training and architecture selection. We propose compositional kernel machines (CKMs), which effectively create an exponential number of virtual training instances by composing transformed sub-regions of the original ones. Despite this, CKM discriminant functions can be computed efficiently using ideas from sum-product networks. The ability to compose virtual instances in this way gives CKMs invariance to translations and other symmetries, and combats the curse of dimensionality. Just as support vector machines (SVMs) provided a compelling alternative to multilayer perceptrons when they were introduced, CKMs could become an attractive approach for object recognition and other vision problems. In this paper we define CKMs, explore their properties, and present promising results on NORB datasets. Experiments show that CKMs can outperform SVMs and be competitive with convnets in a number of dimensions, by learning symmetries and compositional concepts from fewer samples without data augmentation.
BibTeX
@inproceedings{gens2017compositional,
  author = {Robert Gens and Pedro Domingos},
  title = {{Compositional Kernel Machines}},
  booktitle = {International Conference on Learning Representations},
  year = {2017},
  url = {https://openreview.net/forum?id=S1Bm3T_lg},
}
Figure