Fast Kernel matrix computation python

Question

I would like to compute a kernel matrix in python in the fastest way as possible: the input is a matrix X= nsamples, nfeatues and the output should be a symmetric matrix D =nsamples, nsapmles

the method which I'm using right now, even though is based on iterators seems to be really slow do to the for loop... can anybody think to something better?

Thanks

my method so far is:

from itertools import combinations
def computeKernel(X,dlambda):
    nsamples=X.shape[0]
    D=numpy.zeros((nsamples,nsamples))
    for el in combinations(range(nsamples),2):
        i,j=el
        D[el]=quadraticChiDist(X[i,:],X[j,:])


    D=D+D.T
    D=numpy.exp(-dlambda*D/255)
    D=numpy.eye(D)+D    
    return D

where quadraticChiDist is the function that is evaluated for every possible pair of rows in X

Maybe this could help: docs.scipy.org/doc/scipy/reference/generated/… — Benjamin
– Benjamin, Commented Sep 16, 2011 at 17:54

rocksportrocker · Accepted Answer · 2011-09-12 18:07:36Z

1

You can half the running time by replacing the inner loop by

for i in range(nsamples):
    for j in range(i):
        D[i,j]=quadraticChiDist(X[i,:],X[j,:])
        D[j,i]=D[i,j]

Even if quadraticChiDist is not symmetric, that does not matter as you symmetrize you matrix by (did you forget to divide by 2 ?)::

D = D + D.T

For further speedup I would recommend to optimize the speed of quadraticChiDist.

Further I recommend http://cython.org/, especially http://docs.cython.org/src/tutorial/numpy.html. This gives you the speed of C in many cases.

answered Sep 12, 2011 at 18:07

rocksportrocker

7,4692 gold badges34 silver badges51 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Luca Fiaschi Over a year ago

Hi, the combinations(range(nsamples),2) already returns an iterator to the upper triangular matrix indices,therefore the two methods are equivalent: timing the two version there is a small gain in the two for loops version ... I have no idea why but the gain is around 0.2 seconds on 10 rounds of the code on the same matrix (the 10 runs take 40.2 seconds))

rocksportrocker Over a year ago

Then you should look at improving the speed of qaudraticChiDist.

Luca Fiaschi · Accepted Answer · 2011-09-15 09:41:42Z

0

After some search I realized that probably the best solution is to use the pdist function in scipy. It implements several distance functions or you can pass a functor to compute the distance. However, this function is very fast (since it is implemented in c) for the provided distances, but unfortunately does not gain much for a passed functor. Indeed, in the latter case, it is basically equivalent to the suggested for loop solution in pure python.

answered Sep 15, 2011 at 9:41

Luca Fiaschi

3,2157 gold badges34 silver badges47 bronze badges

Collectives™ on Stack Overflow

Fast Kernel matrix computation python

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related