Hi! I have two comments about scipy.spatial distance functions. First, scipy/spatial/src/distance.c contains several interesting distance measures. However, the vector versions are not visible outside the file because they are not declared in distance.h (for instance, euclidean_distance). Only the pdist_* and cdist_* versions are made visible. I would like to use the "raw" distance measures directly for some other functions, so would it be ok to introduce those in distance.h? Second, squared Euclidean distance is computed by taking the square of the Euclidean distance. I think it would make more sense to do it the other way around: the Euclidean distance is computed by taking the square root of the squared Euclidean distance. If these suggestions are ok, I can try to implement them or how should I proceed? Or any other comments? Regards, Jaakko
On Thu, Mar 8, 2012 at 1:40 PM, Jaakko Luttinen <jaakko.luttinen@aalto.fi>wrote:
Hi!
I have two comments about scipy.spatial distance functions.
First, scipy/spatial/src/distance.c contains several interesting distance measures. However, the vector versions are not visible outside the file because they are not declared in distance.h (for instance, euclidean_distance). Only the pdist_* and cdist_* versions are made visible. I would like to use the "raw" distance measures directly for some other functions, so would it be ok to introduce those in distance.h?
I don't see a problem with that.
Second, squared Euclidean distance is computed by taking the square of the Euclidean distance. I think it would make more sense to do it the other way around: the Euclidean distance is computed by taking the square root of the squared Euclidean distance.
Makes sense, should be a little faster.
If these suggestions are ok, I can try to implement them or how should I proceed? Or any other comments?
Implementing them and sending a pull request would be good. If you're familiar with these metrics, perhaps you also have an opinion on these two tickets: http://projects.scipy.org/scipy/ticket/1484 http://projects.scipy.org/scipy/ticket/1486 It seems that the definition of a couple of the metrics is incorrect. Ralf
On 2012-03-10, at 4:53 AM, Ralf Gommers wrote:
Second, squared Euclidean distance is computed by taking the square of the Euclidean distance. I think it would make more sense to do it the other way around: the Euclidean distance is computed by taking the square root of the squared Euclidean distance.
Makes sense, should be a little faster.
Actually, the current implementation is absolutely crazy, especially considering that SciPy has easy access to BLAS. One should never be computing Euclidean distances naively like is done in distance.c. In [36]: def euclidean_distance(X, Y): ....: x2 = (X**2).sum(axis=1) ....: y2 = (Y**2).sum(axis=1) ....: dist = np.dot(X, Y.T) ....: dist *= -2 ....: dist += x2[:, np.newaxis] ....: dist += y2 ....: return np.sqrt(dist) ....: In [37]: from scipy.spatial.distance import cdist In [38]: x = np.random.randn(500, 50) In [39]: y = np.random.randn(400, 50) In [40]: timeit euclidean_distance(x, y) 100 loops, best of 3: 7.57 ms per loop In [41]: timeit cdist(x, y, 'euclidean') 100 loops, best of 3: 16.8 ms per loop In [42]: np.allclose(euclidean_distance(x, y), cdist(x, y, 'euclidean')) Out[42]: True So, a Python implementation that calls NumPy is 2x faster (on my machine with EPD/MKL). A C/Cython implementation that called GEMM directly and didn't iterate over the data multiple times or allocate temporaries would be even faster. David
On Sat, Mar 10, 2012 at 08:35:51PM -0500, David Warde-Farley wrote:
On 2012-03-10, at 4:53 AM, Ralf Gommers wrote:
Second, squared Euclidean distance is computed by taking the square of the Euclidean distance. I think it would make more sense to do it the other way around: the Euclidean distance is computed by taking the square root of the squared Euclidean distance.
Makes sense, should be a little faster.
Actually, the current implementation is absolutely crazy, especially considering that SciPy has easy access to BLAS. One should never be computing Euclidean distances naively like is done in distance.c.
Actually, I think that we had this discussion a while ago on the scikit-learn mailing list and it depends on the dimensionality of your feature space. For a high-dimensional feature space, you are much better off computing euclidean distance as you suggest, with the dot product. However, I think that for a low-dimensional feature space (say 3D), scipy's current approach is better. I can't really compare, because on my laptop I must have a crap BLAS, as the dot product approach is only slighlty faster than cdist with your example. Gaël
On 2012-03-11, at 4:47 AM, Gael Varoquaux wrote:
Actually, I think that we had this discussion a while ago on the scikit-learn mailing list and it depends on the dimensionality of your feature space. For a high-dimensional feature space, you are much better off computing euclidean distance as you suggest, with the dot product. However, I think that for a low-dimensional feature space (say 3D), scipy's current approach is better.
I can't really compare, because on my laptop I must have a crap BLAS, as the dot product approach is only slighlty faster than cdist with your example.
Seems that you're right. If the inner dimension is 3, I get between 2 and 10x faster with cdist than with BLAS, depending on the outer dimensions. The opposite behaviour when the inner dimension is around 50. I guess I never work in less than 30 dimensions so I have a biased sample as to what works best. It seems that somewhere holding the dimension of the result fixed at (4000, 6000), the point where BLAS overtakes naive computation is somewhere in the neighbourhood of 20-25, however it's lower if I reduce the outer dimensions to (400, 600) -- here it's somewhere in the range of 10-15. I guess the only way to deal with this would be to either try and predict the cutoff where BLAS yields better performance on most machines (probably futile -- different machines, different BLAS, nevermind the confounding factor of the outer dimensions, etc.), or make the behaviour user-specifiable. David
On Sun, Mar 11, 2012 at 06:25:10AM -0400, David Warde-Farley wrote:
I guess the only way to deal with this would be to either try and predict the cutoff where BLAS yields better performance on most machines (probably futile -- different machines, different BLAS, nevermind the confounding factor of the outer dimensions, etc.), or make the behaviour user-specifiable.
I would favor making the behaviour user-specifiable with a default 'auto' mode that applies a reasonnable cut-off in terms of dimensionality to switch behaviors. G
Hi, 08.03.2012 13:40, Jaakko Luttinen kirjoitti: [clip]
First, scipy/spatial/src/distance.c contains several interesting distance measures. However, the vector versions are not visible outside the file because they are not declared in distance.h (for instance, euclidean_distance). Only the pdist_* and cdist_* versions are made visible. I would like to use the "raw" distance measures directly for some other functions, so would it be ok to introduce those in distance.h?
Do you want to expose these functions so that they could be used from Python, or do you mean something else? Exposing them to Python requires also writing some additional wrappers in distance_wrap.c, but those seem pretty straightforward to add. Once you got what you like, you can either send in a pull request, or file an enhancement ticket with the patch attached in our tracker, http://projects.scipy.org/scipy/ The pull request route is recommended as it allows for easier follow-up discussion &c. but there's some learning curve ahead if you have never worked with Git before. Some help can be found here (just substitute numpy -> scipy everywhere): http://docs.scipy.org/doc/numpy/dev/gitwash/development_workflow.html We'll probably improve these how-to-contribute instructions soon-ish. Cheers, Pauli
On 03/11/2012 03:01 AM, Pauli Virtanen wrote:
Hi,
08.03.2012 13:40, Jaakko Luttinen kirjoitti: [clip]
First, scipy/spatial/src/distance.c contains several interesting distance measures. However, the vector versions are not visible outside the file because they are not declared in distance.h (for instance, euclidean_distance). Only the pdist_* and cdist_* versions are made visible. I would like to use the "raw" distance measures directly for some other functions, so would it be ok to introduce those in distance.h?
Do you want to expose these functions so that they could be used from Python, or do you mean something else?
Exposing them to Python requires also writing some additional wrappers in distance_wrap.c, but those seem pretty straightforward to add.
No, I'm not planning to expose them to Python. I'm writing some other functions in C (which I'll expose to Python) and these C functions could use the existing code for computing different distance measures between two vectors. So just adding the functions to distance.h would suffice.
Once you got what you like, you can either send in a pull request, or file an enhancement ticket with the patch attached in our tracker, http://projects.scipy.org/scipy/
The pull request route is recommended as it allows for easier follow-up discussion &c. but there's some learning curve ahead if you have never worked with Git before. Some help can be found here (just substitute numpy -> scipy everywhere): http://docs.scipy.org/doc/numpy/dev/gitwash/development_workflow.html We'll probably improve these how-to-contribute instructions soon-ish.
Ok, thanks! -Jaakko
Cheers, Pauli
_______________________________________________ SciPy-Dev mailing list SciPy-Dev@scipy.org http://mail.scipy.org/mailman/listinfo/scipy-dev
15.03.2012 13:09, Jaakko Luttinen kirjoitti:
On 03/11/2012 03:01 AM, Pauli Virtanen wrote:
08.03.2012 13:40, Jaakko Luttinen kirjoitti: [clip]
First, scipy/spatial/src/distance.c contains several interesting distance measures. However, the vector versions are not visible outside the file because they are not declared in distance.h (for instance, euclidean_distance). Only the pdist_* and cdist_* versions are made visible. I would like to use the "raw" distance measures directly for some other functions, so would it be ok to introduce those in distance.h? [clip] No, I'm not planning to expose them to Python. I'm writing some other functions in C (which I'll expose to Python) and these C functions could use the existing code for computing different distance measures between two vectors. So just adding the functions to distance.h would suffice.
Ok. I think at the moment we don't knowingly offer any C APIs in Scipy, so there's no real guarantee of API stability here. In practice, however, the distance.* stuff will probably stay more or less unchanged. Best, Pauli
participants (5)
-
David Warde-Farley -
Gael Varoquaux -
Jaakko Luttinen -
Pauli Virtanen -
Ralf Gommers