Analysis and Extension of Arc-Cosine Kernels for Large Margin Classification

Youngmin Cho, Lawrence K. SaularXiv 2011 · OpenReview

TL;DR

This paper delves into the geometric properties of "arc-cosine" kernels, which are inspired by large neural networks. They discover that these kernels can induce surfaces with varying geometric characteristics (flat, curved, or even non-manifold) in feature space, offering a new perspective on kernel design. The authors also propose and evaluate extensions of these kernels, showing improved performance on classification tasks.

What Problem Does This Paper Address?

Kernel methods, particularly Support Vector Machines (SVMs), are powerful tools for pattern analysis and classification. They work by implicitly mapping data into a high-dimensional feature space where linear methods can be applied. The "kernel trick" allows us to compute inner products in this feature space without explicitly performing the mapping. Recently, a new family of kernels, called "arc-cosine" kernels, was introduced, which mimic the computations of large neural networks with Heaviside step activation functions. While these kernels showed promise, their underlying geometric properties and potential for extension were not fully understood. This paper aims to bridge this gap by analyzing the geometry of the feature spaces induced by these kernels and exploring variations that could lead to better classification performance.

Methods

The core of the paper's methodology lies in applying tools from differential geometry to analyze the surfaces in Hilbert space induced by the arc-cosine kernels. Specifically, they investigate:

  • Riemannian Manifold Analysis: For kernels that induce a Riemannian manifold, they derive expressions for the metric tensor ($g_{\mu\nu}$), volume element ($dV$), and scalar curvature ($S$). This allows them to characterize the intrinsic geometry of the feature space.
  • Kernel Variations: They propose two extensions to the basic arc-cosine kernel (specifically for the $n=0$ case):
  • Biased Threshold Functions: Introducing a bias term ($b$) to the Heaviside step function, aiming to regulate the sparsity of the feature representations.
  • Smoothed Threshold Functions: Replacing the Heaviside step function with a cumulative Gaussian function, effectively smoothing the non-analyticity of the original kernel.
  • Experimental Evaluation: The performance of the original and extended kernels was evaluated using Support Vector Machines (SVMs) on various benchmark datasets for large margin classification. They compared these kernels against each other and against standard kernels like Radial Basis Function (RBF) and linear kernels.

Datasets

The paper uses the following eight datasets for evaluating the performance of the proposed kernels:

  • MNIST-rand: A noisy variation of the MNIST handwritten digit dataset.
  • MNIST-image: MNIST dataset with backgrounds composed of other image patches.
  • Rectangles: A synthetic dataset for classifying tall vs. wide rectangles.
  • Rectangles-image: A harder version of Rectangles with complex backgrounds.
  • Convex: A synthetic dataset for classifying convex vs. non-convex regions.
  • 20-Newsgroups: A text classification dataset with 20 news categories.
  • ISOLET: A dataset for identifying spoken English letters.
  • Gisette: A dataset for distinguishing MNIST digits FOUR vs. NINE, with added sparse features.

Key Insights and Ideas

  • Geometric Diversity of Arc-Cosine Kernels: The paper reveals that arc-cosine kernels, depending on their degree ($n$), can induce feature spaces with significantly different geometric properties. This ranges from flat, Euclidean-like spaces ($n=1$) to curved Riemannian manifolds ($n \ge 2$), and even spaces that cannot be described as manifolds at all ($n=0$) due to non-analyticity. This is a key theoretical contribution, showing a richer geometric landscape than previously understood for kernel functions.
  • The $n=1$ Kernel's Euclidean Property: A surprising finding is that the arc-cosine kernel of degree $n=1$ induces an intrinsically flat surface in Hilbert space, preserving the Euclidean metric. This is notable because it achieves this while still performing a highly nonlinear mapping, unlike purely linear kernels.
  • Non-Analyticity of the $n=0$ Kernel: The simplest arc-cosine kernel ($n=0$) exhibits non-analyticity, meaning its Taylor series expansion around certain points doesn't behave as expected. This prevents its induced feature space from being described as a Riemannian manifold, distinguishing it from higher-order kernels and standard polynomial/Gaussian kernels.
  • Bias and Smoothing Improve Performance: The proposed extensions to the $n=0$ kernel (bias and smoothing) consistently improved classification performance on several datasets compared to the original $n=0$ kernel. This highlights the practical benefit of addressing the kernel's non-analyticity and controlling feature representation sparsity.
  • Multilayer Kernels Show Promise: Composing arc-cosine kernels (mimicking deeper neural networks) further improved performance on some datasets, sometimes outperforming RBF kernels. This suggests that the neural network inspiration can be leveraged effectively through deeper compositions.

Key Results

  • Geometric Characterization: The paper provides explicit formulas for the metric, volume element, and scalar curvature for arc-cosine kernels of degree $n \ge 2$, showing they induce curved Riemannian manifolds.
  • Flat Manifold for $n=1$: The $n=1$ arc-cosine kernel results in a flat manifold with a Euclidean metric ($g_{\mu\nu} = \delta_{\mu\nu}$).
  • Non-Manifold for $n=0$: The $n=0$ kernel's induced space is not a Riemannian manifold due to non-analyticity.
  • Performance Gains from Extensions: On several datasets, the biased and smoothed arc-cosine kernels achieved lower error rates than the original $n=0$ kernel. For example, on the Rectangles dataset, the "Bias" variation achieved an error rate of 2.48%, significantly better than the original $n=0$ kernel's 13.08%.
  • Multilayer Performance: Table 4 shows that multilayer arc-cosine kernels achieved competitive or superior results on datasets like Rectangles (2.11% error with RBF vs. 2.11% with multilayer arc-cosine) and ISOLET (3.01% with RBF vs. 3.01% with multilayer arc-cosine).

Limitations and Future Work

  • Non-Analyticity of $n=0$: The $n=0$ kernel's non-analyticity is a fundamental limitation that prevents it from being analyzed using standard Riemannian geometry tools. While extensions address this, the original kernel's behavior remains distinct.
  • RBF Kernels Often Still Best: Despite improvements from the proposed kernels and their compositions, RBF kernels still achieved the best performance on many datasets. This suggests that while arc-cosine kernels offer interesting geometric properties and potential, they don't universally outperform established methods.
  • Future Directions:
    • Leveraging Geometric Properties for Classification: The authors suggest exploring how the derived geometric properties (like volume elements) can be used to improve classification performance, perhaps through conformal transformations similar to those used for RBF kernels.
  • Probabilistic Modeling: The simple form of the volume element for some arc-cosine kernels might be useful for probabilistic modeling, potentially bridging kernel methods with deep belief networks.
  • Clustering, Dimensionality Reduction, Manifold Learning: The geometric properties of these kernels could be more prominent and useful in applications beyond classification.
  • More Effective Kernel Combinations: Investigating additive combinations (multiple kernel learning) and further exploring compositions of arc-cosine kernels with varying degrees and parameters is suggested.

Summary updated

Abstract

We investigate a recently proposed family of positive-definite kernels that mimic the computation in large neural networks. We examine the properties of these kernels using tools from differential geometry; specifically, we analyze the geometry of surfaces in Hilbert space that are induced by these kernels. When this geometry is described by a Riemannian manifold, we derive results for the metric, curvature, and volume element. Interestingly, though, we find that the simplest kernel in this family does not admit such an interpretation. We explore two variations of these kernels that mimic computation in neural networks with different activation functions. We experiment with these new kernels on several data sets and highlight their general trends in performance for classification.
BibTeX
@misc{cho2011analysis,
  author = {Youngmin Cho and Lawrence K. Saul},
  title = {{Analysis and Extension of Arc-Cosine Kernels for Large Margin Classification}},
  year = {2011},
  eprint = {1112.3712},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1112.3712},
}
Figure