Need helps for assignment 3:part1

[ChenchengLiang]

Hey,
I went to implement the kernel with only the first layer.
But it does not work and report a error from line 74
normal = multivariate_normal(mean=m.flatten(), cov=cc + EPS*np.eye(cc.shape[0]))
says
The input matrix must be positive semidefinite

I cannot simplify this code anymore to see what is wrong (only 6 lines code). Could someone help me to look at it?
Maybe I have some misunderstandings of the instruction?

The code can be found here:
https://colab.research.google.com/drive/1ky9ggtb0YHggZC_F0aCpauYx5Xxc62tA?usp=sharing
@antonior92

[el-hult]

Check the eigenvalues of cc. They should all be real and nonnegative. Try np.linalg.eig. The eigenvalues might be small negative values, but they should not be larger in magnitude than EPS. If they are, something is off at a different place in your code.

[el-hult]

In any case someone else has a similar issue: torch is using single precision by default, so EPS must be super large if you use torch. Or, you need to call torch.set_default_dtype(torch.double) so that you use double precision. Then, suddenly things get a little better.

However, the code that you struggeled with @ChenchengLiang is in numpy, which is double precison by default, so your issue is something else.

[el-hult]

Okay. So after the first layer, the rank of Sigma is 3, and it is 105x105. So it is very ill conditioned and the numerical imprecision is bad.

Conditioning on observed data (computing cc in your code) makes the problem even worse conditioned, so I needed a very large EPS to get it to work with only the first layer implemnted (as your code looks). Maybe 1e-4 or something....

BUT every extra layer you implement makes the problem less ill+conditioned. So after L layers, I could use EPS=1e-7 again.

So you have just some numerical issues. And if you implement more, they go away.

[ChenchengLiang]

Thank you!
Checking cc's eigenvalues is very helpful.
I will check if using larger EPS and implementing more layers work.

[antonior92]

Hi Chencheng.

A quick fix here would be to replace c by c + EPS*np.eye(c.shape[0]) before the conditioning. This corresponds to allowing a small noise additive term in the Gaussian process. Otherwise, you were trying to fit a linear kernel with no noise to a data generated nonlinearly, which I believe was making the problem ill-conditioned.

[ChenchengLiang]

Thank you! The first layer works!
I went to implement the recursive NTK but there are still "not positive definite" errors between layers.
So I simplify it to only contain two layers without recursive. It still stuck to there. I print out the minimum value of eigvals for c and cc. they are negative, so there must be some step wrong in sigma_2. I followed the instruction to implement it step by step and tried some variations, but it is not working at all. Maybe I have some misunderstanding in the instructions. Could you please help to check it?
The code is still here

[antonior92]

I think the problem is that as you compute the kernel for each pair of inputs (x1, x2) individually. I think this might be causing a couple of problems.

The first is that your matrix c is not symetric because k(x1, x2) and k(x2, x1) will yield different values, since they were sampled from different random seeds. The quick and dirty fix for it is just making the matrix symentric by, say, redefining (c + c.T)/2. I tried that in your code but the error still persists.

I believe that is because the diagonal computation is still wrong in the way you are performing it.

[antonior92]

A suggestion that might work might be to redefine the kernel interface from

kernel(x1, x2) -> y

where y is a scalar value. To the interface:

kernel(x) -> Sigma

where x = [x1, x2, x3, ..., xn] is a vector of size n. And Sigma is a n x n matrix containing at position i, j k(x_i, x_j).

This might make it easier to compute everything inside the same function and sample only once (avoiding this problem of having to sample multiple times for the pairs)...

[ChenchengLiang]

Thank you very much! I think I had some misunderstandings of the instruction before.
Now, the problem is solved, I think I get the correct results.
Thanks again!

[antonior92]

Awesome! Nice to know it now works!