276
reads

Kuang-Yao Lee

2008-07-29
13:30:00 - 15:00:00

An explanation of "Kernel trick" and the construction of kernels for discrete structures

308 , Mathematics Research Center Building (ori. New Math. Bldg.)

In statistical learning community, kernel-based methods are becom­ing widely used, such as Support vector machines (SVMs) and Kernel Principle Component Analysis (KPCA). The central idea behind them is the so called “kernel trick”. Via Mercer’s theorem, for an appro­priate kernel function defined on input space, K :Ω × Ω → R, there exists a mapping, φK :Ω → ΦK , which maps the original data space into a higher (generally infinite) dimension space ΦK. ΦK is a repro­ducing kernel Hilbert space so that non-linear extension for common statistical problem can be reasonably constructed. An interpretation by Minh et al. (2006) will be introduced here. Then, I will focus on kernels for discrete structures. Categorical data and more general, graph-like data, are often seen in real world; for example, the hyper-link in WWW and citations in scientific articles. Therefore, how to use kernels to capture the relationship between graph points might be interesting. Two possible methods, R-convolution (Haussler 1999) and diffusion kernels (Kondor & Lafferty 2002) will also be discussed.