Sensing-Aware Kernel SVM

Weicong Ding, Prakash Ishwar, Venkatesh Saligrama, W. Clem Karl

Abstract

We propose a novel approach for designing kernels for support vector machines (SVMs) when the class label is linked to the observation through a latent state and the likelihood function of the observation given the state (the sensing model) is available. We show that the Bayes-optimum decision boundary is a hyperplane under a mapping defined by the likelihood function. Combining this with the maximum margin principle yields kernels for SVMs that leverage knowledge of the sensing model in an optimal way. We derive the optimum kernel for the bag-of-words (BoWs) sensing model and demonstrate its superior performance over other kernels in document and image classification tasks. These results indicate that such optimum sensing-aware kernel SVMs can match the performance of rather sophisticated state-of-the-art approaches.

Introduction

In many machine learning tasks, we do not observe the "true" state of the world directly. Instead, we see a noisy or transformed version of it, such as X-ray projections in medical imaging or a "Bag of Words" (BoW) in text analysis. Traditional approaches typically choose between generative models, which can be computationally exhausting and assumption-heavy, and discriminative models like standard SVMs, which often ignore valuable domain knowledge about the data-generation process. This paper introduces "Sensing-Aware Kernels," a method for building SVMs that explicitly incorporate the physics or statistics of how data is collected (the "sensing model"), bridging the gap between generative modeling and discriminative classification.

Methodology

The core innovation is the Sensing-Aware Kernel. The authors prove that if the sensing model—the probability of seeing observation $x$ given a latent state $z$, written as $p(x|z)$—is known, the Bayes-optimum decision boundary is a hyperplane in a specific function space. To turn this into a practical SVM, they define a kernel as the inner product of these likelihood functions:

$$K(x, x') = \int_Z p(x|z)p(x'|z) dz$$

Specifically for the BoW model, the authors propose three practical approximations to handle numerical stability and varying document lengths:

  • Sensing 0: A simple log-mapping.
  • Sensing 1: A normalized version using word frequencies and Gamma functions.
  • Sensing 2: A resampling-based approach to handle documents of different lengths.

Experimental Results

The authors evaluated their approach on two primary benchmarks: the 20 Newsgroups text dataset and the Natural Scene Category image dataset.

Text Classification

On the 20 Newsgroups multi-class task, the Sensing 2 kernel achieved 80.5% accuracy, outperforming standard RBF kernels (75.9%) and Deep Learning approaches based on Restricted Boltzmann Machines (76.2%). It performed comparably to sophisticated, computationally heavy topic models like G-MedLDA.

Table 1: Classification accuracy (CCR %) on the 20 Newsgroups dataset comparing Sensing-Aware kernels with various baselines.

Image Classification

When applied to local image patches (where the BoW assumption is strongest), the Sensing 2 kernel (79.7%) outperformed the classic Spatial Pyramid (SP) kernel (79.3%) and other model-based kernels like the Probability Product Kernel (PPK).

Table 2: Classification accuracy on the Natural Scene Category dataset across different spatial pyramid levels (L).

Key Insights and Discussion

  • Efficiency: Because the kernel has a closed-form expression or simple approximation, it avoids the expensive iterative inference steps required by traditional generative models.
  • No Need for Inference: Unlike many latent variable models, the kernel handles the uncertainty of the hidden state by integrating over all possibilities, meaning the hidden state $z$ does not need to be explicitly estimated for classification.
  • Limitations: The primary limitation is the requirement of a known sensing model $p(x|z)$. While the kernel excels at local features, it struggles when applied to entire complex images without spatial context, suggesting that future work should focus on sensing models that capture spatial or temporal dependencies.

Summary updated

Abstract

We propose a novel approach for designing kernels for support vector machines (SVMs) when the class label is linked to the observation through a latent state and the likelihood function of the observation given the state (the sensing model) is available. We show that the Bayes-optimum decision boundary is a hyperplane under a mapping defined by the likelihood function. Combining this with the maximum margin principle yields kernels for SVMs that leverage knowledge of the sensing model in an optimal way. We derive the optimum kernel for the bag-of-words (BoWs) sensing model and demonstrate its superior performance over other kernels in document and image classification tasks. These results indicate that such optimum sensing-aware kernel SVMs can match the performance of rather sophisticated state-of-the-art approaches.
BibTeX
@inproceedings{ding2014sensing,
  author = {Weicong Ding and Prakash Ishwar and Venkatesh Saligrama and W. Clem Karl},
  title = {{Sensing-Aware Kernel SVM}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=9HKnpvzRM5O},
}
Figure