Extended Grassmann Kernels for Subspace-Based Learning

Jihun Ham, Daniel D. LeeNeurIPS 2008 · OpenReview

Introduction

This paper establishes a formal link between probabilistic similarity measures and geometric kernels on Grassmann manifolds. By analyzing the Kullback-Leibler (KL) distance in the limit of zero noise, the authors derive and extend "Projection kernels" to handle more complex data structures like affine and scaled subspaces. These extensions significantly improve performance in computer vision tasks such as face and object recognition.

The Challenge of Subspace Data

In many machine learning applications, particularly in computer vision, data does not merely exist as individual points (vectors) in Euclidean space. Instead, data often forms subspaces. For example, a set of images of the same face under different lighting conditions can be modeled as a low-dimensional linear subspace (often called "eigenfaces").

While "Grassmann kernels" exist to compare these subspaces, they are traditionally restricted to linear subspaces that pass through the origin (zero-mean). This paper addresses two main gaps in the field:

  1. Theoretical Foundation: The lack of a clear connection between geometric subspace kernels and well-established probabilistic distances.
  2. Practical Flexibility: The inability of standard Grassmann kernels to handle affine subspaces (subspaces with an offset or mean) and scaled subspaces (where the variance along different axes matters).

Methodology: Bridging Geometry and Probability

The authors bridge the gap between geometry and probability using Factor Analysis (FA). They model each data set as a Gaussian "blob" generated by a few latent factors plus some noise ($\sigma$).

  • The KL Link: They prove that as the noise ($\sigma$) approaches zero, the symmetrized KL distance between two distributions effectively becomes the squared Projection distance on a Grassmann manifold. This provides a rigorous probabilistic justification for using the Projection kernel.
  • The Bhattacharyya Failure: Conversely, they demonstrate that the Bhattacharyya kernel (another popular probabilistic measure) becomes "trivial" in the zero-noise limit. It essentially returns 1 if subspaces are identical and 0 otherwise, making it suboptimal for subspace-based learning.
  • New Extended Kernels: Based on the KL analysis, the authors propose three extended kernels:
  • $k_{LinSc}$ (Linear Scaled): Accounts for non-homogeneous scaling (eigenvalues) within the subspace.
  • $k_{Aff}$ (Affine): Handles subspaces with an offset (non-zero mean), ensuring the kernel is invariant to how the affine space is represented.
  • $k_{AffSc}$ (Affine Scaled): Combines both offset and scaling into a single robust kernel.

Key Insights

  • Probability Meets Geometry: The most significant theoretical contribution is showing that geometric projection kernels are not just arbitrary formulas; they are the natural limit of information-theoretic distances (KL) when noise is minimized.
  • The Importance of the Offset: Standard linear kernels fail when data has non-zero means. By explicitly adding an "offset term" to the kernel that is invariant to representation, the model can successfully distinguish between parallel subspaces that are shifted in space.
  • Robustness to Dimension: The extended kernels are relatively unaffected by the choice of subspace dimensionality ($m$). This is a major practical advantage, as the "true" dimensionality of real-world data is rarely known.

Experimental Results

The authors evaluated their kernels on both synthetic and real-world benchmarks, utilizing Support Vector Machines and Kernel Discriminant Analysis.

Synthetic Performance

The kernels were first tested on Synthetic MFA Data consisting of 100 Factor Analysis distributions generated with varying degrees of separation ("Easy," "Intermediate," and "Difficult").

Synthetic MFA Data Results

As shown in the results above, on "Easy" data (well-separated means), the Affine kernels achieved ~92% accuracy, while standard linear Grassmann kernels struggled at ~55%.

Real-World Recognition

For real-world testing, the authors used the Yale Face Database (images of 38 subjects under 45 different lighting conditions) and the ETH-80 Object Category Gallery (images of 8 object categories under 41 different poses).

Classification Rates on Yale Face and ETH-80
  • Yale Face: The extended kernels (specifically $k_{LinSc}$) achieved nearly 100% accuracy across various subspace dimensions, significantly outperforming the Euclidean baseline and the Binet-Cauchy (BC) kernel.
  • ETH-80: The Affine kernels consistently outperformed others, maintaining high accuracy even as the subspace dimension increased. In contrast, older probabilistic kernels like Bhattacharyya saw performance drop sharply at higher dimensions.

Limitations and Future Work

  • Computational Complexity: The "doubly kernel" approach for nonlinear subspaces (using an implicit map) adds a layer of computational overhead that might be challenging for very large datasets.
  • Probabilistic Scope: The paper focuses heavily on the KL distance. The relationship between Grassmann kernels and other probabilistic distances remains an open area for exploration.
  • Noise Assumption: The theoretical derivations rely on the limit where noise $\sigma \to 0$. In extremely noisy real-world scenarios, the data distribution might not collapse cleanly into a subspace, potentially weakening the theoretical link.

Summary updated

Abstract

Subspace-based learning problems involve data whose elements are linear subspaces of a vector space. To handle such data structures, Grassmann kernels have been proposed and used previously. In this paper, we analyze the relationship between Grassmann kernels and probabilistic similarity measures. Firstly, we show that the KL distance in the limit yields the Projection kernel on the Grassmann manifold, whereas the Bhattacharyya kernel becomes trivial in the limit and is suboptimal for subspace-based problems. Secondly, based on our analysis of the KL distance, we propose extensions of the Projection kernel which can be extended to the set of affine as well as scaled subspaces. We demonstrate the advantages of these extended kernels for classification and recognition tasks with Support Vector Machines and Kernel Discriminant Analysis using synthetic and real image databases.
BibTeX
@inproceedings{ham2008extended,
  author = {Jihun Ham and Daniel D. Lee},
  title = {{Extended Grassmann Kernels for Subspace-Based Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=B1Z66dbOWr},
}
Figure