6
$\begingroup$

I have what I think might be a standard machine learning problem but I can't find a clear solution.

I have lots vectors of different dimensions. For each pair of vectors I can compute their similarity. I would like to embed these vectors into Euclidean space of some fixed dimension $d$ in such a way that vectors that are similar under the original measure have small Euclidean distance under the embedding.

This seems to be called similarity metric learning but the wiki doesn't seem to go into any detail about ways to tackle it. I also found some code for metric learning in Python but it seems to tackle a different problem to the one I am interested in.

How can you tackle this similarity learning problem?

Improve this question
$\endgroup$
2
  • $\begingroup$ This sounds related to the Distance geometry problem. $\endgroup$
    – Brian Stamper
    Jun 26 '18 at 19:39
  • 1
    $\begingroup$ Perhaps you are looking for Multidimensional scaling? (I'm not an expert on this, I'm investigating it because your question has given me an idea about a similar problem I am working on and now I want the answer too!) $\endgroup$
    – Brian Stamper
    Jun 26 '18 at 19:49
3
$\begingroup$

These are known as multidimensional scaling algorithms. From wikipedia (https://en.wikipedia.org/wiki/Multidimensional_scaling), "An MDS algorithm aims to place each object in N-dimensional space such that the between-object distances are preserved as well as possible." So essentially you input a distance matrix and the algorithms output a Euclidean representation that should approximate the distances. In your case, you have similarity scores, so you'll need to take either the reciprocal (distance = 1 / similarity) or subtract similarity from a large constant (distance = c - similarity).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. Do you learn a transformation which you can then apply to new vectors which are not in the training set? $\endgroup$
    – Anush
    Jun 26 '18 at 20:40
  • 1
    $\begingroup$ @Anush it depends on the algorithm and the implementation, but I think most algorithms do not allow for this. For example, sklearn.manifold.MDS does not allow for a held out test set. $\endgroup$
    – Wart
    Jun 28 '18 at 19:44
  • $\begingroup$ Note of caution in case you distance matrix does not contrain Euclidean distances, from wiki on Multidimensional Scaling: "Classical MDS assumes Euclidean distances" $\endgroup$
    – ngiann
    Jul 29 '20 at 11:46
2
$\begingroup$

vectors that are similar under the original measure have small Euclidean distance under the embedding

This is the goal of dimensionality reduction, especially the nonlinear dimensionality reduction, where it is the only goal (because they cannot in general enforce that distances between points that are far apart will be undistorted, if you're interested in proof you can find it here).

Some approaches:

  • Multidimensional scaling
    • Isomap (this is nonlinear method that uses MDS for distances retrieved from kNN graph)
  • Kernel PCA (uses kernel trick to do PCA in embedding space)
  • graph-based dimensionality reduction (your distance matrix defines a graph, and graphs give rise to useful matrices, check out A tutorial on Spectral Clustering. In Python megaman implements Spectral Embedding)
  • tSNE (reduces dimensionality trying to preserve distribution of distances)

If you're interested in Python in particular, then almost all of these methods are implemented in scikit-learn, especially in manifold module.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you. Do all of these methods allow you to learn a transformation which you can later apply to new vectors which are not in the training set? $\endgroup$
    – Anush
    Jun 27 '18 at 9:02
  • $\begingroup$ This can be found in scikit-learn documentation. If a class has transform method then it's possible (for example Isomap and KPCA have it). $\endgroup$
    – Jakub Bartczuk
    Jun 27 '18 at 9:06
  • $\begingroup$ That's very interesting, thank you. I notice TSNE only has fit and fit_transform. Do you know why it isn't suitable for applying to new data (as it has no transform method)? $\endgroup$
    – Anush
    Jun 27 '18 at 9:09
  • 2
    $\begingroup$ Hey @Anush I've updated my answer to also give an exposition of these methods. As to t-SNE I'm not sure, but I'd discourage using it has many problems if you don't use $d=2$ or $3$ and it's also probably the most computationally heavy method from the ones I've mentioned. It is also nondeterministic, and heavily so (some other algorithms may be sort of indeterministic, but t-SNE is likely most unstable, I've never actually seen people using it for anything else than 2d or 3d visualization). $\endgroup$
    – Jakub Bartczuk
    Jun 27 '18 at 9:12
  • $\begingroup$ For scikit-learn.org/stable/modules/generated/…, it's not clear to me how you specify a function that computes the similarity between pairs of your input vectors. The list of "Parameters:" doesn't seem to include anything suitable, as far as I can tell. Did I miss something simple? $\endgroup$
    – Anush
    Jun 27 '18 at 9:16

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.