6
$\begingroup$

I am struggling to understand kernels and how to determine whether they are proper or not.

For these examples can anyone explain why an example is proper and why another example is not.

Given $K_1$ and $K_2$ two proper kernels, determine which of the following formulae define proper kernels:

$$ K_4(x_1,x_2) = -K_1(x_1,x_2)^2 K_2(x_1,x_2) \\ K_3(x_1,x_2) = -K_2(x_1,x_2) + 3K_1(x_1,x_2) \\ K_5(x_1,x_2) = 15 K_1(x_1,x_2) $$

I am particularly interested in how you get the answer, rather than stating which are proper and which are not.

Improve this question
$\endgroup$
1
  • $\begingroup$ Point of clarification required - Is $K_4$ defined to be the point-wise multiplication of entries in $-K_1^2$ and $K_2$ or the matrix product $-K_1^2K_2$? $\endgroup$ – Ansari Apr 18 '13 at 20:59
8
$\begingroup$

In a machine learning context (i.e. "kernel methods"), the key requirement for a kernel is that it must be symmetric and positive-definite, that is, if $K$ is a kernel matrix, then for any (column) vector $x$ of the appropriate length, $x^{T}Kx$ must be a positive real number. This restriction is in place mostly due to requirements of optimization processes that operate downstream on this matrix.

To answer your question, certain basic operations preserve positive-definiteness, and some don't. You can use the definition of positive-definiteness above to decide whether an operation preserves that property or not. The product operation does not always preserve positive definiteness (it does preserve it in the case where their product is commutative). The square operation however does preserve it. For a real positive number $r$, $rK$ is positive definite, and the sum of any two positive definite matrices is also positive definite.

So in your examples, $K_3$ and $K_4$ may or may not be proper kernel matrices (to use your terminology) and $K_5$ is definitely a proper kernel matrix.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Linear operations involving negative numbers as in $K_3$, cannot possibly always preserve positive-definiteness. After all if $K$ is positive definite then $-K$ is negative definite. $\endgroup$ – whuber♦ Apr 18 '13 at 19:57
  • $\begingroup$ @whuber - Right you are! I wasn't thinking straight. $\endgroup$ – Ansari Apr 18 '13 at 20:00
  • 2
    $\begingroup$ Notice that $K_4$ is guaranteed to be nonpositive--there's no uncertainty about that. $\endgroup$ – whuber♦ Apr 18 '13 at 20:03
  • $\begingroup$ @whuber - how can you be sure? As far as I can tell, $K_4$ is guaranteed non-positive only if $K_1K_2 = K_2K_1$. I must be missing something again ... $\endgroup$ – Ansari Apr 18 '13 at 20:07
  • $\begingroup$ $-K_1^2$, being the negative of a square, is always negative when applied to nonzero arguments and by assumption $K_2$ is always positive when applied to nonzero arguments, QED. $\endgroup$ – whuber♦ Apr 18 '13 at 20:29
4
$\begingroup$

One easy way is to think of a kernel function as a positive-semidefinite (PSD) matrix. Then you can use PSD tricks.

For example, if $K$ is PSD, then $-K$ is NSD and thus not PSD. On the other hand, if $K$ is PSD, $c K$ is PSD if $c$ is a scalar and $c > 0$. Thus, $K_4$ and $K_3$ are not generally kernels and $K_5$ is.

Improve this answer
$\endgroup$
1
  • $\begingroup$ oops sorry for the late answer - my connection was lost for a while. $\endgroup$ – Bitwise Apr 18 '13 at 20:52

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.