Multiple Kernel Sparse Representations for Supervised and Unsupervised Learning

Jayaraman J. Thiagarajan, Karthikeyan Natesan Ramamurthy, Andreas Spanias

Abstract

In complex visual recognition tasks it is typical to adopt multiple descriptors, that 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 1-D 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.

Introduction

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 or fail to ensure that the resulting sparse codes are truly discriminative.

Methodology

The authors propose the Multiple Kernel Sparse Representations (MKSR) framework, which bridges the gap between MKL and sparse dictionary learning through two primary components:

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.

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. 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 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.

Overview of the MKSR framework

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

Key Results

The MKSR framework consistently outperformed existing sparse coding and MKL-based methods across several standard benchmarks:

  • 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.
Performance comparison on Oxford Flowers dataset

Conclusion

MKSR demonstrates that combining hierarchical dictionary learning with graph-based kernel weight optimization leads to highly discriminative representations. By leveraging the power of residuals and the "kernel trick," the framework remains computationally tractable while providing the benefits of non-linear modeling. Future work may extend this framework to semi-supervised learning tasks.

Summary updated

Abstract

In complex visual recognition tasks it is typical to adopt multiple descriptors, that 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 1-D 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},
}
Figure