I had a question about dimensionality reduction for finding nearest neighbors and was hoping someone could help me out here.

Suppose I have good features for images, say penultimate layer features from VGG-16 trained on ImageNet classification. I want to find nearest neighbors in this space, however, it is of dimensionality 4096, and this makes life hard when the number of data points is large, say a million. Given this, I would like to reduce the dimensionality of the features, to something really small, say 2 or 3.

PCA would not be a good choice as this focuses on preserving directions of highest variance and I am really interested in preserving pairwise distances because I want to use this for NN search.

t-SNE, commonly used for visualization of high dimensional data, can reduce points to 2/3 dimensions. However, the author warns that Notice that t-SNE does not retain distances but probabilities, so measuring some error between the Euclidean distances in high-D and low-D is useless. (https://lvdmaaten.github.io/tsne/)

Here's my question: Is the above concern really valid if I am only interested in retrieving the local neighborhood around a point? After all, t-SNE preserves the local structure of data. Further, is there something better than t-SNE if I want to go to such low dimensions? I just need something that can maintain pairwise distance / similarity while going down to a few dimensions.

  • $\begingroup$ This is a good question. I don't know t-SNE well enough to know, but my suspicion would be not to trust this. Beyond that, finding nearest neighbors shouldn't be a problem so much for a large number of data points (a million), but for a large dimensionality, unless you are just up against the computational limits of your system. If the curse of dimensionality applies to your data, either it will also apply to PCA transformed data, or you won't preserve the pairwise distances. $\endgroup$ – gung Dec 4 '18 at 19:45
  • 1
    $\begingroup$ This is a bizarre question. If you run t-SNE on a million points, the algorithm will start by finding k nearest neighbours of all points (or k approximate nearest neighbours). If that's all you need, then you can stop here. CC @gung. $\endgroup$ – amoeba Dec 4 '18 at 20:56
  • $\begingroup$ +1 to @amoeba comment. I think you need to focus on your final task which is to find nearest neighbours. Side-note: The idea that some methodology is better than worse than other right of the bat is a bit hard to quantify accurately... For example, if we just want something newer and fancier than $t$-SNE we could go with UMAP, would that be better? (For the record, I think UMAP is extremely promising!) $\endgroup$ – usεr11852 Dec 9 '18 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.