9
$\begingroup$

The curse of dimensionality tells us if the dimension is high, the distance metric will stop working, i.e., everyone will be close to everyone.

However, many machine learning retrieval systems rely on calculating embeddings and retrieve similar data points based on the embeddings. These embedding dimensions can be 512, 1024 or 2048, which is very high.

My question is: If the curse of dimensionality exists, how does embedding search work?

Improve this question
$\endgroup$
4
  • 9
    $\begingroup$ I think everyone will be far from (not close to) everyone in high dimensions. $\endgroup$
    – Richard Hardy
    May 24, 2021 at 8:30
  • 2
    $\begingroup$ Are you asking what results allow us to use low-dimensional embeddings and compute similarity between these embeddings instead of working with high-dimensional data? Or are you asking how searching/computing similarity between low dimensional embeddings works, given that the "low-dimensional" embeddings still have high dimensionality e.g. 512, 1024, 2048? $\endgroup$
    – microhaus
    May 25, 2021 at 14:16
  • $\begingroup$ Quote: The common theme of these problems is that when the dimensionality increases, the volume of the space increases so fast that the available data become sparse. in high dimensional data, however, all objects appear to be sparse and dissimilar in many ways, which prevents common data organization strategies from being efficient. ~ Wikepedia. What do you mean by everyone will be close to everyone? $\endgroup$
    – Lerner Zhang
    Sep 3, 2021 at 4:25
  • $\begingroup$ @RichardHardy I think what the OP means originate from this article: A Few Useful Things to Know About Machine Learning, and I also raised a question on this topic. $\endgroup$
    – Lerner Zhang
    Dec 28, 2021 at 16:35

1 Answer 1

Reset to default
2
$\begingroup$

The origion of vector space model is as follows:

The idea that the meaning of a word might be modeled as a point in a multi- dimensional semantic space came from psychologists like Charles E. Osgood, who had been studying how people responded to the meaning of words by assigning val- ues along scales like happy/sad or hard/soft. Osgood et al. (1957) proposed that the meaning of a word in general could be modeled as a point in a multidimensional Euclidean space, and that the similarity of meaning between two words could be modeled as the distance between these points in the space.

For the question

how does embedding search work

There are two methods: 1) you have embedding A and you compute the cosine distances between A and all the embeddings in a corpus and you rank the embeddings by the distances to find the nearest embeddings; or 2) you try the approximate nearest neighbor searching using FAISS or ScaNN.

Why consine? Because it is the normalized dot product since dot product favors long vectors.

Embedding is the result of one of the two vector semantic models: sparse vector models and dense vector models. Embeddings are obtained from dense vector models, and the sparse vector models include word-context and term-term matrix. We can also utilize distances between sparse vectors to measure semantic similarities/associations.

Reference:

Speech and Language Processing: An introduction to natural language processing

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This doesn't seem to anwer the question, which is about how the curse of dimensionality affects embeddings $\endgroup$
    – user20160
    Sep 2, 2021 at 15:41
  • $\begingroup$ @user20160 It reminds me of this answer, and I will update mine. $\endgroup$
    – Lerner Zhang
    Sep 2, 2021 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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