4
$\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$
7
  • $\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, 2017 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, 2017 at 16:53
  • 1
    $\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, 2017 at 16:57
  • 1
    $\begingroup$ This is not the good forum. Here we explain the maths behind. See stackoverflow and cs.stackexchange $\endgroup$
    – reuns
    Sep 9, 2017 at 16:59
  • 1
    $\begingroup$ So you are asking, is every positive semi-definite matrix a Gram matrix? Answer: of course. $\endgroup$
    – kimchi lover
    Sep 9, 2017 at 16:59

1 Answer 1

Reset to default
7
$\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 valid Kernel if and only if the matrix $G$, called the Kernel matrix, or Gram matrix is symmetric, positive semi-definite.

The matrix $G$ 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)})$$

Furthermore, 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

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .