HW2 4.1.2

[David Naylor]

Hi,

I'm a little confused by the hint for 4.1.2; maybe I'm misunderstanding something.

In class Alex told us, and you remind us in the hint, that if k is a kernel function, then all gram matrices K made with k are positive semi-definite. But the opposite is not necessarily true, is it? If k is a potential kernel function, then just because all gram matrices made from it are positive semidefinite we cannot conclude k is a proper kernel, right?

-- David

[Barnabas Poczos]

The answer to your question can be found here:
http://en.wikipedia.org/wiki/Mercer's_theorem

k is a kernel function if and only if it is a positive semidefinite function.

If for a function k, all Gram matrices on all possible finite data are
positive semidefinite, then k is a positive definite function, and
therefore it is a kernel function.
(See the second inequality of the above link)

However, simply looking at the Gram matrices on your training data is
not enough to say that the kernel is positive semidefinite.

Best,
Barnabas

> --
> http://alex.smola.org/teaching/cmu2013-10-701 (course website)
> http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9
> (YouTube playlist)
> ---
> You received this message because you are subscribed to the Google Groups
> "10-701 Spring 2013 CMU" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to 10-701-spring-201...@googlegroups.com.
> To post to this group, send email to
> 10-701-spri...@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[zhuoc]

You always asked what I want to ask. Thanks!

[Alex Smola]

hi zhuoc,

here's a bit more reasoning about what's happening (i didn't go into that detail since i didn't want to confuse everyone but here it goes):

for kernels of the form k(x-x') taking the fourier transform of the kernel and checking that it is nonnegative gives you a necessary and sufficient condition. you can easily check this simply by otherwise taking coefficients that take values like the frequency for which the fourier transform has negative value and plugging this into the expansion. you'd get a negative number.

for general purpose kernels, positive semidefiniteness of a specific matrix is a necessary but not sufficient condition. however, if you can prove that all matrices for all data regardless of the size of the matrix are positive semidefinite, you're in business. for instance, just showing things for all 2x2 submatrices is not enough. if you remember the counterexample i gave using 

[1 1 0; 1 1 1; 0 1 1]

all 2x2 submatrices are positive semidefinite but the 3x3 matrix isn't. 

in general, if you have an eigenfunction expansion of the kernel, i.e. 

k(x,x') = \sum_i \lambda_i \psi_i(x) \psi_i(x')

and some \lambda_i happened to be negative, then you could, due to the orthogonality of the \psi_i construct data (x_j) and corresponding weights \alpha_j = \psi_i(x_j) such that, for sufficiently large numbers of points, you'd get a negative value, hence you'd have a counterexample

cheers,

alex

--

http://alex.smola.org/teaching/cmu2013-10-701 (course website)
http://www.youtube.com/playlist?list=PLZSO_6-bSqHQmMKwWVvYwKreGu4b4kMU9 (YouTube playlist)
---
You received this message because you are subscribed to the Google Groups "10-701 Spring 2013 CMU" group.
To unsubscribe from this group and stop receiving emails from it, send an email to 10-701-spring-201...@googlegroups.com.
To post to this group, send email to 10-701-spri...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--

                            ''~``

                           ( o o )

+----------------------.oooO--(_)--Oooo.---------------------------+

| Prof. Alexander J. Smola             http://alex.smola.org       |

| 5000 Forbes Ave                      phone: (+1) 408-759-1044    |

| Gates Hillman Center 8002            Carnegie Mellon University  |

| Pittsburgh 15213 PA    (   )   Oooo. Machine Learning Department |

+-------------------------\ (----(   )-----------------------------+                          

                          \_)    ) /

                                (_/