1
$\begingroup$

The kernel is $K(x,z) = \sum_{i=1}^D (x_i+z_i)$

My approach was trying to express $K = \phi(x)^T\phi(z) = (x_1 x_2 ... x_D \quad 1 1 ...1)(1 1 ...1\quad z_1 z_2 ... z_D )^T$ where $\phi$ is 2Dx1

The solution says:

K is not a kernel. Consider $x_1 = [1 \quad 0]^T \quad x_2 = [0 \quad 2]^T$. Their kernel matrix has eigenvalues −1 and 5.

What explains this discrepancy?

[EDIT]: Based on the link below and the given $x_1, x_2$, I arrive at $S = 2a_1^2+6a_1a_2+4a_2^2$ Now, how can I choose $a_1,a_2$ to make this negative?

$\endgroup$
5
  • 1
    $\begingroup$ You can't show that a kernel is valid by constructing a single example which looks good, but you can show it's invalid by constructing a single example which looks bad (in this case, not positive definite.) See for example stats.stackexchange.com/questions/183215/…, which may be helpful. $\endgroup$
    – jbowman
    Oct 13, 2018 at 2:33
  • $\begingroup$ @jbowman: Please see edit above. $\endgroup$
    – db18
    Oct 13, 2018 at 17:05
  • $\begingroup$ You might be interested in this thread: stats.stackexchange.com/questions/199620/… $\endgroup$
    – Sycorax
    Oct 13, 2018 at 17:14
  • $\begingroup$ Response to edit: $S$ factors as $2(a_1+a_2)(a_1+2a_2)$, which will be negative if $a_1+a_2 > 0$ and $a_1+2a_2 < 0$, for example, $a_1 = 3$ and $a_2 = -2$. $\endgroup$
    – jbowman
    Oct 13, 2018 at 17:36
  • $\begingroup$ @jbowman: Thanks! Btw, how do I arrive at the eigenvalues mentioned in the original solution? $\endgroup$
    – db18
    Oct 13, 2018 at 18:04

1 Answer 1

2
$\begingroup$

Based on the link below and the given $x_1, x_2$, I arrive at $S = 2a_1^2+6a_1a_2+4a_2^2$ Now, how can I choose $a_1,a_2$ to make this negative?

We can factorize $S$ to obtain $$ S = 2(a_1 + a_2) (a_1 + 2 a_2) $$ so if we want $S < 0$, we need to choose $a_1, a_2$ such that exactly one of $(a_1 + a_2) <0$ or $(a_1 + 2a_2)<0$. This is because the product of two positive numbers is positive and the product of two negative numbers is positive but the product of a positive number and a negative number is negative.

Since this problem is under-determined, a useful way to go about solving it is to fix $a_1$ at some value and then find $a_2$ that satisfies our criteria. Arbitrarily, I chose $a_1 = -1$. This gives

$$ S = 2(-1 + a_2) (-1 + 2 a_2) $$

Now I decided to make the second factor negative and the third factor positive. This means we need $a_2 - 1 < 0$ but $2a_2 -1 >0$. Together, these inequalities provide $\frac{1}{2} < a_2 < 1$. We can arbitrarily choose any $a_2$ in that interval.

Thus one solution among many is $a_1 = -1, a_2 = \frac{3}{4}$.

$\endgroup$
6
  • $\begingroup$ That helps! Btw, how do I arrive at the eigenvalues mentioned in the original solution? $\endgroup$
    – db18
    Oct 13, 2018 at 18:04
  • $\begingroup$ Compute the kernel matrix using the given inputs. For 2 inputs, the kernel is $2 \times 2$, so you can compute the eigenvalues trivially by hand because the characteristic polynomial is a quadratic, and solving quadratic is easy (en.wikipedia.org/wiki/Quadratic_formula). More information: mathworld.wolfram.com/CharacteristicPolynomial.html $\endgroup$
    – Sycorax
    Oct 13, 2018 at 18:09
  • $\begingroup$ Yes, I'm aware of the quadratic formula and characteristic equation. Maybe I'm missing something obvious in this "Compute the kernel matrix using the given inputs" $\endgroup$
    – db18
    Oct 14, 2018 at 22:58
  • $\begingroup$ You wrote the general expression for computing an element of the kernel matrix in your question. A kernel matrix for 2 vectors has 4 elements. How do you use your expression to populate the 4 elements of the matrix using $x_1, x_2$? $\endgroup$
    – Sycorax
    Oct 14, 2018 at 23:07
  • $\begingroup$ So that gives the Kernel matrix as [2 3;3 4] but this gives the eigenvalues as -0.16 and 6.16 $\endgroup$
    – db18
    Oct 14, 2018 at 23:13

Your Answer

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

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