Characteristic and Universal Tensor Product Kernels

Zoltán Szabó, Bharath K. Sriperumbudur

TL;DR

This paper investigates the properties of "tensor product kernels," which are a powerful way to combine information from multiple sources (like images and text). The authors introduce and analyze several new notions of "characteristic" properties for these kernels, revealing crucial relationships between the properties of individual kernels and their combined tensor product. This work is vital for understanding when these combined kernels can reliably distinguish between different probability distributions and detect independence, which is fundamental for many machine learning tasks.

What Problem Does This Paper Address?

Machine learning often deals with data from multiple sources or modalities. To handle this, researchers use "tensor product kernels" to combine information from different domains. These kernels are built by taking the tensor product of individual kernels, each designed for a specific modality. While these combined kernels are widely used, there's a significant gap in understanding when they effectively capture essential properties of probability distributions, such as independence and distinctness. Specifically, the paper asks: when does a tensor product kernel "characterize" independence (meaning it can perfectly distinguish independent distributions from dependent ones), and when can it discriminate between different probability distributions? This is crucial because many statistical measures, like Maximum Mean Discrepancy (MMD) and Hilbert-Schmidt Independence Criterion (HSIC), rely on these kernel properties.

Methods

The paper introduces and rigorously analyzes several new notions of "characteristic" properties for tensor product kernels, building upon existing concepts like "characteristic" and "universal" kernels. These new notions include $\otimes$-characteristic, $\otimes_0$-characteristic, and I-characteristic. The core of the methodology involves:

  • Formal Definitions: Defining these new characteristic properties based on the behavior of kernel mean embeddings and related measures (like MMD and HSIC) on specific classes of probability measures.
  • Theoretical Analysis: Establishing relationships and implications between these different characteristic properties, particularly for tensor product kernels of $M \ge 2$ components. This involves proving theorems that show when the properties of individual kernels ($k_m$) imply properties of the combined tensor product kernel ($\otimes_m k_m$).
  • Counterexamples and Examples: Constructing specific examples of kernels and probability distributions to illustrate the theoretical findings, demonstrating when certain implications do not hold and highlighting surprising phenomena.
  • Focus on Product Spaces: The analysis is primarily conducted on product spaces, which are natural settings for tensor product kernels.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on the properties of kernels themselves, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Subtlety of Tensor Product Properties: The paper reveals that the characteristic property of individual kernels does not generally transfer to the tensor product kernel. This is a key insight, as it means simply having good individual kernels doesn't guarantee a good combined kernel.
  • New Notions of Characteristic Properties: The introduction of $\otimes$-characteristic, $\otimes_0$-characteristic, and I-characteristic properties provides a more nuanced understanding of what tensor product kernels can capture, especially for $M \ge 3$ components.
  • Universality as a Stronger Guarantee: The research highlights that universality of individual kernels is a sufficient condition for the tensor product kernel to be $\otimes$-characteristic. This is a valuable finding for constructing reliable kernels.
  • Surprising Relationships: The paper uncovers surprising equivalences between different characteristic notions for tensor product kernels under specific conditions (e.g., for translation-invariant kernels), which are not generally true for arbitrary kernels.
  • I-Characteristic for Independence: The I-characteristic property is shown to be directly linked to HSIC's ability to measure joint independence, making it a critical concept for multi-variable independence testing.

Key Results

  • Theorem 3(i): If two kernels $k_1$ and $k_2$ are characteristic (and spaces are second-countable), their tensor product $k_1 \otimes k_2$ is I-characteristic. This is a significant result for $M=2$.
  • Theorem 3(ii): If a tensor product kernel $\otimes_m k_m$ is I-characteristic, then all individual kernels $k_m$ must be characteristic. This establishes a necessary condition.
  • Theorem 4: For translation-invariant, continuous, and bounded kernels on $\mathbb{R}^{d_m}$, several notions of characteristic properties for the tensor product kernel (including $\otimes_0$-characteristic, $\otimes$-characteristic, I-characteristic, and characteristic) are shown to be equivalent.
  • Theorem 5: For co-kernels on locally compact Polish spaces, the tensor product of $M \ge 2$ co-universal kernels is co-universal, and vice versa. This is a generalization of previous results.
  • Counterexamples: The paper provides concrete examples showing that:
  • Characteristic individual kernels do not guarantee a characteristic tensor product kernel.
  • For $M \ge 3$, characteristic individual kernels are not sufficient for the tensor product kernel to be I-characteristic.
  • Even if one kernel is only characteristic (not universal), the tensor product kernel might not be I-characteristic.

Limitations and Future Work

  • Assumptions on Spaces: Many results rely on assumptions like second-countability or locally compact Polish spaces. Extending these results to more general topological spaces could be a future direction.
  • Bounded Kernels: The analysis often assumes bounded kernels. Investigating the implications for unbounded kernels would be valuable.
  • Generalization to $M > 2$: While the paper makes progress for $M \ge 2$, the relationships between characteristic properties become more complex as $M$ increases. Further exploration of these complex interactions for higher-dimensional tensor products is a natural extension.
  • Practical Implications: While the theoretical foundations are strong, translating these findings into practical guidelines for choosing and constructing effective tensor product kernels for real-world applications remains an ongoing area. The paper's results provide the theoretical underpinnings for such future work.

Summary updated

BibTeX
@article{szabo2017characteristic,
  author = {Zoltán Szabó and Bharath K. Sriperumbudur},
  title = {{Characteristic and Universal Tensor Product Kernels}},
  journal = {J. Mach. Learn. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=VY6RX48r6Pr},
}
Figure