2
$\begingroup$

For a kernel function, we have two conditions one is that it should be symmetric which is easy to understand intuitively because dot products are symmetric as well and our kernel should also follow this. The other condition is given below

There exists a map $φ:R^d→H$ called kernel feature map into some high dimensional feature space $H$ such that $∀x,x′$ in $R^d:k(x,x′) \ = \ <φ(x),φ(x′)>$

I understand that this means that there should exist a feature map that will project the data from low dimension to any high dimension $D$ and kernel function will take the dot product in that space.

For example, the Euclidean distance is given as

$d(x,y)=\sum_{i}(x_i-y_i)^2= <x,x>+<y,y>-2<x,y>$

If I look this in terms of second condition how do we know that doesn't exist any feature map for euclidean distance? What exactly are we looking in feature maps mathematically?

$\endgroup$
1

1 Answer 1

1
$\begingroup$

To check if the kernel $K$ (feature map function) is a valid kernel or not, $K$ must satisfying Mercer's condition.

Mercer's condition: The kenel $K$, is a valid kernel if and only if $K$ is positive definite.

This satisifed in case of there's a matrix $c$ such that

$M$ = $c^T K c$, where $K$ is the Gram matrix (Kernel resultant matrix).

$st:$ $M \geq 0, for \,\, all \,\, real \,\ value \,\ c_i$

Or

$\sum_{i=1}^{n}\sum_{j=1}^{n} c_i k_i{_j} c_j \geq 0 $

$\geq 0$ $\Leftrightarrow$ positive semi-definite

before going to the intuition of why using Mercer's condition & intuitive proof, I would like to mention that, check the existence of the kernel $K$ and Mercer's condition has nothing to do with feature map itself, however it's a crucial for the convergence of the quadratic program such (SVM), or more generally the convexity.


Intuition

$K$ is a symmetric matrix then by the spectral theorem $K$ is a diagonalizable matrix (in other words, we can decompose it), so we can reformulate K by eigendecomposition

$K = VDV^T$

where $V$ is an orthogonal matrix and its column are the eigenvectors, and $D$ is a diagonal matrix with eigenvalues $λ_i{_j}$ on the diagonal.

If : $\exists $ $λ_i{_j}$ $for \,\, all \,\, i=j$ $such \ that \ λ_i{_j} < 0$

($\exists $) $\Leftrightarrow$ There's exist

Then the kernel $K$ not a valid kernel, beacuse of the negative eigenvalue means, there's a such point at which the Hessian is indefinite, in other words, the critical point is a saddle (the function is strongly convex-concave), then the primal problem has no solution, and even dual problem could be very expensive to compute (arbitrarily large).

by Sylvester's criterion, $K$ has negative eigenvalues if and only if it is not positive semi-definite.


Geometric intuition

The feature mapping by kenel function or the inner product of the features vector (row matrix) $x_i$ , $x_j$, $K=\langle \phi(x_i)\,, \phi(x_j)\rangle$ is same as the mesurement of the similarity of two functions by the definition of Hilbert space concept, visually, the kernel function is a congruent transformation, which is a transformation in an isometric space, if we have a negative eigenvalue, then transformation has occurred in the opposite direction in isometric space, in other words, the image reflecte across some axis.

$\endgroup$
9
  • $\begingroup$ Nice explanation, Computing Kernel Matrices for all of the space for example in the euclidean distance just to check whether it's valid or not would be a very difficult and time-consuming task. What do you recommend in that scenario? How should one approach to formal proofing then? $\endgroup$ Jun 18, 2020 at 17:22
  • $\begingroup$ Euclidean distance isn't a valid kernel function, as $K$ is not positive semi-definite and by Sylvester's criterion, we have nothing to check, otherwise you may use Sylvester's criterion $\endgroup$
    – 4.Pi.n
    Jun 18, 2020 at 18:01
  • $\begingroup$ For SVM for example, it's commonly used RBF kernel, the polynomial kernel as those kernels satisfies Mercer's condition, in machine learning the kernel valid if and only if it's always valid for all possible random variable X, not only for the training set. $\endgroup$
    – 4.Pi.n
    Jun 18, 2020 at 18:02
  • $\begingroup$ Depend on your use case the best thing to do so, is to use the popular kernel function, or Sylvester's criterion. $\endgroup$
    – 4.Pi.n
    Jun 18, 2020 at 18:06
  • 1
    $\begingroup$ Yeah, check the positive definiteness and then the factorization if there's exist $B$ such that $A=B^TB$ and $B$ is nonsingular then all eigenvalues are positive (kernel is valid), you also could check this text book page 558 cse.zju.edu.cn/eclass/attachments/2015-10/… $\endgroup$
    – 4.Pi.n
    Jun 18, 2020 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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