1
$\begingroup$

Given a kernel, can we represent it as a Gram matrix? For example, a linear kernel can be presented (in Python/MATLAB code) in a Gram matrix as follows: K = X*X.T. If this is true, how to represent other non-trivial kernels in their Gram matrix form, e.g., check the following link, page 5, equation 17 showing Jensen-Shannon kernel: K(p,q) = exp(-JS(p||q))

https://pdfs.semanticscholar.org/3e43/4ca7cbd1869f41e338658f7ab4f954782ad8.pdf

$\endgroup$
  • $\begingroup$ Can you briefly define (or point me to a definition) of "kernel", as you use the term? The paper you cite is pretty diffuse, full of examples and not precision. $\endgroup$ – kimchi lover Sep 9 '17 at 13:31
  • $\begingroup$ You can look at this for the relation between the kernel trick, a Gram matrix (dot product matrix, for a given dataset) and the inner product in a high-dimensional vector space. @kimchilover $\endgroup$ – reuns Sep 9 '17 at 16:53
  • $\begingroup$ This does not define the define kernel. $\endgroup$ – kimchi lover Sep 9 '17 at 16:55
  • $\begingroup$ @kimchilover In my linked post I explain why (in machine learning) a kernel is any function $k: \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}$ such that for any $x_i \in\mathbb{R}^n, i = 1 \ldots m$, the matrix $K_{ij} = k(x_i,x_j)$ is positive semi-definite. $\endgroup$ – reuns Sep 9 '17 at 16:57
  • $\begingroup$ Guys, I just want a Python/MATLAB Gram matrix expression for kernel above. $\endgroup$ – Hello World Sep 9 '17 at 16:58
3
$\begingroup$

It seems you are talking about Kernels in the context of machine learning. In which case the difference between the Kernel and the Kernel \ Gram matrix can be understood via the following expression of Mercer's theorem:

Mercer's theorem in the context of machine learning

Let $X = \{x^{(1)}, ... , x^{(m)} \}$ be a data set of $m$ points, each of which are $n$ dimensional vectors, i.e. $x^{(i)} \in \mathbb{R}^n$ then the function $K$ which maps $$ K(x^{(i)},x^{(j)}) : \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$$

is a a valid Kernel if and only if the matrix $G$, called the Kernel matrix, or Gram matrix is symmetric, positive definite.

The matrix $K$ is an $m \times m$ matrix where each entry is the kernel of the corresponding data points.

$$G_{i,j} = K(x^{(i)}, x^{(j)})$$

Moreover, note that

A function $K(x,z)$ is a valid kernel if it corresponds to an inner product in some (perhaps infinite dimensional) feature space.

Hence:

For the linear kernel, the Gram matrix is simply the inner product $ G_{i,j} = x^{(i) \ T} x^{(j)}$. For other kernels, it is the inner product in a feature space with feature map $\phi$: i.e. $ G_{i,j} = \phi(x^{(i)})^T \ \phi(x^{(j)})$

Sources

Page 18 - https://see.stanford.edu/materials/aimlcs229/cs229-notes3.pdf

Page 45 - http://svivek.com/teaching/machine-learning/fall2017/slides/svm/kernels.pdf

page 52 - https://people.eecs.berkeley.edu/~jordan/kernels/0521813972c03_p47-84.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.