Multiple Kernel Sparse Representations for Supervised and Unsupervised Learning

Jayaraman J. Thiagarajan, Karthikeyan Natesan Ramamurthy, Andreas Spanias

TL;DR

This paper introduces Multiple Kernel Sparse Representations (MKSR), a framework that combines the strengths of Multiple Kernel Learning (MKL) and sparse dictionary learning. By fusing diverse image descriptors into a unified kernel space and optimizing them using graph-embedding principles, the authors achieve state-of-the-art performance in both supervised object recognition and unsupervised image clustering.

What Problem Does This Paper Address?

In computer vision, no single feature descriptor (like color, texture, or shape) is perfect for every task. To build robust recognition systems, researchers often combine multiple descriptors. However, fusing these diverse data types into a single, meaningful space is challenging.

While Multiple Kernel Learning (MKL) provides a principled way to fuse features, and Sparse Coding is excellent at finding the intrinsic structure of high-dimensional data, combining them effectively is difficult. Existing methods often struggle with computational complexity in the kernel space or fail to ensure that the resulting sparse codes are truly "discriminative"—meaning they don't just represent the data well, but actually help tell different classes apart.

Methods

The authors propose a two-pronged approach to bridge this gap:

  1. Kernel Multilevel Dictionary (KMLD) Learning: Instead of learning a single "flat" dictionary, the authors use a hierarchical approach. They adapt the K-hyperline clustering algorithm to the Reproducing Kernel Hilbert Space (RKHS). This involves performing 1-D subspace clustering at multiple levels, where each level captures a different aspect of the data's residual error. This multilevel structure is more stable and generalizes better to new, unseen data than traditional dictionaries.
  2. Discriminative Weight Optimization: The "Multiple Kernel" part comes from an ensemble kernel—a weighted combination of individual kernels. The authors use graph-embedding principles to tune these weights.
  3. In the supervised case, they optimize weights so that samples from the same class are pulled together while different classes are pushed apart in the embedded space.
  4. In the unsupervised case, they use the correlations between the sparse codes themselves to identify the underlying graph structure, creating a powerful feedback loop that improves clustering.

The algorithm iterates between updating the discriminative embedding, tuning the kernel weights, and re-learning the multilevel dictionary.

Datasets

The framework was evaluated on three standard, highly competitive benchmarks:

  • Oxford Flowers Dataset: 17 categories of flowers with 80 images each.
  • Caltech-101: A classic benchmark with 101 object categories (plus a background class).
  • Caltech-256: A more difficult version of Caltech-101 with 256 categories and significantly higher variability.

For clustering, they used a 20-class subset of Caltech-101 to compare against other unsupervised manifold learning techniques.

Key Insights and Ideas

  • The Power of the Residual: By learning dictionaries on the residuals of previous levels (the KMLD approach), the model captures fine-grained details that a single-level dictionary might miss.
  • Sparsity as a Graph Builder: One of the most interesting "aha" moments is using sparse codes to update the affinity graphs in the unsupervised setting. Because sparse models represent data as a union of subspaces, the resulting graph is "non-local" and less sensitive to small noise or perturbations in the raw data.
  • Linearity in the RKHS: The authors leverage the fact that linear models learned in a high-dimensional RKHS provide the power of non-linear models in the original input space, all while remaining computationally tractable via the "kernel trick."

Key Results

The MKSR framework consistently outperformed existing sparse coding and MKL-based methods:

  • Oxford Flowers: Achieved 86.3% accuracy, surpassing previous benchmarks like Gehler et al. (85.5%).
  • Caltech-101: Reached 82.9% accuracy with 30 training samples per class, showing superior performance compared to other sparse coding methods like K-SVD or ScSPM.
  • Caltech-256: Achieved 49.9% accuracy (with 45 training samples), outperforming several state-of-the-art fusion methods.
  • Clustering: In unsupervised tests, the method achieved a Normalized Mutual Information (NMI) of 0.77, a significant jump over the 0.74 achieved by standard MKL-LPP.

Limitations and Future Work

While the results are impressive, the authors note that the current framework relies on an iterative optimization process that could be computationally intensive as the number of kernels or training samples grows very large.

For future work, they suggest extending this framework to semi-supervised learning, where only a small fraction of the data is labeled. They also hint that the graph-embedding component is modular; it could be replaced with other learning strategies depending on the specific geometry of the data being analyzed.

Summary updated

Abstract

In complex visual recognition tasks, it is typical to adopt multiple descriptors, which describe different aspects of the images, for obtaining an improved recognition performance. Descriptors that have diverse forms can be fused into a unified feature space in a principled manner using kernel methods. Sparse models that generalize well to the test data can be learned in the unified kernel space, and appropriate constraints can be incorporated for application in supervised and unsupervised learning. In this paper, we propose to perform sparse coding and dictionary learning in the multiple kernel space, where the weights of the ensemble kernel are tuned based on graph-embedding principles such that class discrimination is maximized. In our proposed algorithm, dictionaries are inferred using multiple levels of 1D subspace clustering in the kernel space, and the sparse codes are obtained using a simple levelwise pursuit scheme. Empirical results for object recognition and image clustering show that our algorithm outperforms existing sparse coding based approaches, and compares favorably to other state-of-the-art methods.
BibTeX
@article{thiagarajan2014multiple,
  author = {Jayaraman J. Thiagarajan and Karthikeyan Natesan Ramamurthy and Andreas Spanias},
  title = {{Multiple Kernel Sparse Representations for Supervised and Unsupervised Learning}},
  journal = {IEEE Trans. Image Process.},
  year = {2014},
  url = {https://openreview.net/forum?id=0n7-eC-8piM},
}

Loading related content...

Figure