Hash kernels for structured data

Qinfeng Shi; James Petterson; Gideon Dror; John Langford; Alex Smola; S. V.N. Vishwanathan

Hash kernels for structured data

Qinfeng Shi^*
, James Petterson
, Gideon Dror
, John Langford
, Alex Smola
, S. V.N. Vishwanathan

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

161 Citations (Scopus)

Abstract

We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs

Original language	English
Pages (from-to)	2615-2637
Number of pages	23
Journal	Journal of Machine Learning Research
Volume	10
Publication status	Published - 2009

Cite this

@article{3616de71a10e4f1db0e00fcdeb200850,

title = "Hash kernels for structured data",

abstract = "We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs",

keywords = "Graphlet kernel, Hashing, Multiclass classification, Stream, String kernel",

author = "Qinfeng Shi and James Petterson and Gideon Dror and John Langford and Alex Smola and Vishwanathan, \{S. V.N.\}",

year = "2009",

language = "English",

volume = "10",

pages = "2615--2637",

journal = "Journal of Machine Learning Research",

issn = "1532-4435",

publisher = "Microtome Publishing",

}

TY - JOUR

T1 - Hash kernels for structured data

AU - Shi, Qinfeng

AU - Petterson, James

AU - Dror, Gideon

AU - Langford, John

AU - Smola, Alex

AU - Vishwanathan, S. V.N.

PY - 2009

Y1 - 2009

N2 - We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs

AB - We propose hashing to facilitate efficient kernels. This generalizes previous work using sampling and we show a principled way to compute the kernel matrix for data streams and sparse feature spaces. Moreover, we give deviation bounds from the exact kernel matrix. This has applications to estimation on strings and graphs

KW - Graphlet kernel

KW - Hashing

KW - Multiclass classification

KW - Stream

KW - String kernel

UR - https://www.scopus.com/pages/publications/73549107233

M3 - Article

SN - 1532-4435

VL - 10

SP - 2615

EP - 2637

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -

Hash kernels for structured data

Abstract

Other files and links

Fingerprint

Cite this