Probability Product Kernels

Tony Jebara, Risi Kondor, Andrew G. HowardJMLR 2004 · OpenReview

Abstract

This paper introduces Probability Product Kernels, a versatile framework that allows discriminative learning algorithms, such as Support Vector Machines (SVMs), to operate directly on probability distributions. By mapping data points to distributions and computing their inner product via integration, we create a powerful bridge between generative modeling and kernel-based classification. This approach preserves the rich, nonlinear structure of generative models while leveraging the classification power of discriminative methods.

Introduction

In machine learning, a persistent challenge is the trade-off between discriminative methods and generative models. Discriminative methods like SVMs are highly effective for classification but typically require fixed-length vector representations. Conversely, generative models, such as Hidden Markov Models (HMMs) or Gaussian Mixtures, excel at handling structured, variable-length data (e.g., text or DNA sequences) but are not always optimal for pure classification tasks.

Previous attempts to combine these paradigms, such as Fisher Kernels, often rely on linear approximations that may lose the nonlinear characteristics of the underlying models. Probability Product Kernels address this by defining a kernel directly as an inner product in a Hilbert space of distributions, allowing the full power of generative models to serve as a feature extractor for discriminative classifiers without sacrificing mathematical rigor.

Methodology

The core concept involves fitting a probability distribution $p(x)$ to each data point and defining the kernel as the integral of the product of these distributions, each raised to a power $ ho$:

$$k(p, p') = \int p(x)^\rho p'(x)^\rho dx$$

Special Cases and Extensions

  • Statistical Affinities: When $ ho = 1/2$, the formulation corresponds to the Bhattacharyya affinity. When $ ho = 1$, it becomes the Expected Likelihood Kernel.
  • Closed-Form Solutions: For distributions within the Exponential Family (e.g., Gaussians, Multinomials), this integral can be solved analytically, ensuring computational efficiency. The table below details the components used to derive these solutions for common distributions.
Table 1: Sufficient statistics and parameters for common Exponential Family distributions used to derive closed-form kernel solutions.
  • Latent Variable Support: The framework extends to complex models with hidden states, such as Hidden Markov Models (HMMs) and Linear Dynamical Systems (LDS), utilizing efficient message-passing algorithms similar to the forward-backward algorithm.
  • Approximations: For intractable models, the authors provide robust methods using Monte Carlo sampling and Variational Mean Field approximations.

Experimental Results

The authors evaluated Probability Product Kernels across three distinct domains:

  1. Text Classification (WebKB): On the WebKB dataset of university web pages, the Bhattacharyya kernel consistently outperformed standard linear and RBF kernels, particularly when training data was limited. The $\rho = 1/2$ setting naturally implements a "square root squashing" of word frequencies, aligning with empirical wisdom in Information Retrieval.
  2. Bioinformatics (HS3D): For gene sequence classification (distinguishing introns from exons), the HMM-based kernel achieved an error rate of 10-11%, significantly outperforming standard string kernels, which had error rates between 18% and 34%.
  3. Time Series Analysis: The kernel based on Switching Linear Dynamical Systems (SLDS) outperformed standard LDS and RBF kernels on synthetic data, demonstrating its ability to capture both discrete transitions and continuous dynamics.

Discussion and Conclusion

Probability Product Kernels treat probability distributions as points in a high-dimensional Hilbert space, enabling the use of sophisticated graphical models to engineer kernels for specific data types. Unlike Fisher kernels, they maintain the nonlinear flexibility of the generative models.

While the exact kernels are mathematically guaranteed to be valid Mercer kernels, approximations like sampling may occasionally produce non-positive definite matrices. Furthermore, the performance is dependent on the choice of the generative model. Future work involves exploring more complex graphical models, such as Markov Random Fields, and further investigating the learning theory behind non-positive definite kernels.

Summary updated

BibTeX
@article{jebara2004probability,
  author = {Tony Jebara and Risi Kondor and Andrew G. Howard},
  title = {{Probability Product Kernels}},
  journal = {J. Mach. Learn. Res.},
  year = {2004},
  url = {https://openreview.net/forum?id=Il4H4p4FlE},
}

Loading related content...

Figure