Nearest Neighbors: Maximal Inner Product or Minimal Distance

[garrettwrong]

@janden and @yoelsh,

Historically ASPIRE has used the dot product as a measure for feature/image similarity, ie sorting neighbors by maximizing dot product. I have found that third party Nearest Neighbor (and other) tools are minimizing some (often configurable) notion of distance instead. This comes into play when trying to coherently mix legacy code with code using third party or approximate solutions. Restated, we have a legacy method returning a notion of correlation, and new codes/tools accepting/returning a notion of distance. These are related but the next component should take only one measurement/sorting approach consistently. Right now I just dodge it by sorting the right direction when mixing code, but this is a hack and confuses people, and leaves the NN distances an ambiguous variable.

For example, the scikit nearest neighbors can solve for and return these metrics. Default, which we use, is more/less L2 distance I think. (of two pca compressed bispectrum feature vectors). They also provide mahalanobis, which was presented in one of our groups papers...

In any case, for coding reasons we need to pick whether I should be converting scikit distances towards corr (dot), or our legacy code towards distance; what most tools seem to be doing.

I have found the following transformation that could seem to apply to us. I believe it can remap our corr values to distances with a simple formula.

https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/XboxInnerProduct.pdf

Its also possible to just have the legacy code compute L2 distance directly , but I was worried this might not reflect the legacy algorithm as well.

What do you think? Thanks!

[yoelsh]

If the more common approach is to use distances, I think we should do that as well.
It should be easy to convert our correlation to distance.
If I am not mistaken, if c is the correlation then 1-c should do the trick, giving something we can use as a "distance".
Changing from correlation to L2 distance will give different results in case the input vectors are not normalized.

[garrettwrong]

Cool. I think the legacy code in Initial_classification_FD_update was just using matrix product (collection of dot products), calling that corr, then using mainly just for sorting. I can normalize by magnitude so 1-corr behaves. Thanks!