Header logo is

On Pairwise Kernels: An Efficient Alternative and Generalization Analysis

2009

Conference Paper

ei


Pairwise classification has many applications including network prediction, entity resolution, and collaborative filtering. The pairwise kernel has been proposed for those purposes by several research groups independently, and become successful in various fields. In this paper, we propose an efficient alternative which we call Cartesian kernel. While the existing pairwise kernel (which we refer to as Kronecker kernel) can be interpreted as the weighted adjacency matrix of the Kronecker product graph of two graphs, the Cartesian kernel can be interpreted as that of the Cartesian graph which is more sparse than the Kronecker product graph. Experimental results show the Cartesian kernel is much faster than the existing pairwise kernel, and at the same time, competitive with the existing pairwise kernel in predictive performance.We discuss the generalization bounds by the two pairwise kernels by using eigenvalue analysis of the kernel matrices.

Author(s): Kashima, H. and Oyama, S. and Yamanishi, Y. and Tsuda, K.
Book Title: Advances in Knowledge Discovery and Data Mining: 13th Pacific-Asia Conference
Pages: 1030-1037
Year: 2009
Month: April
Day: 0
Editors: Theeramunkong, T. , B. Kijsirikul, N. Cercone, T. B. Ho
Publisher: Springer

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

DOI: 10.1007/978-3-642-01307-2_110
Event Name: PAKDD 2009
Event Place: Bangkok, Thailand

Address: Berlin, Germany
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{5655,
  title = {On Pairwise Kernels: An Efficient Alternative and Generalization Analysis},
  author = {Kashima, H. and Oyama, S. and Yamanishi, Y. and Tsuda, K.},
  booktitle = {Advances in Knowledge Discovery and Data Mining: 13th Pacific-Asia Conference},
  pages = {1030-1037},
  editors = {Theeramunkong, T. , B. Kijsirikul, N. Cercone, T. B. Ho},
  publisher = {Springer},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Berlin, Germany},
  month = apr,
  year = {2009},
  doi = {10.1007/978-3-642-01307-2_110},
  month_numeric = {4}
}