15
$\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?

$\endgroup$
4
  • 9
    $\begingroup$ I think everyone will be far from (not close to) everyone in high dimensions. $\endgroup$ Commented 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
    Commented 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$ Commented 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$ Commented Dec 28, 2021 at 16:35

2 Answers 2

5
$\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

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

I think this question has not been answered sufficiently despite being a good question.

The curse of dimensionality essentially says that random 3 vectors in sufficiently high dimensional space have roughly the same distance to each other with regards to euclidean distance. This is true, also in the case of dim = 512.

However, in vector search for embeddings are key differences:

  1. The vectors are not random: We are embedding text and questions. Our goal is to measure if they are related, if yes how they are related.
  2. We are not working with euclidean distance and usually normalised vectors, i.e.
  • $dist_{euchlidean} = d(\mathbf{p}, \mathbf{q}) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$
  • $dist_{cosine}=d(\mathbf{a}, \mathbf{b}) = 1 - \frac{\mathbf{a} \cdot \mathbf{b}}{\|\mathbf{a}\| \|\mathbf{b}\|} = \mathbf{a} \cdot \mathbf{b}$ , note that the cosine distance is a number between -1 and 1.

The cosine distance is measures the cosine angle between two vectors. It is a vastly different concept than the euclidean distance which will measure the length of a vector between those two. While the length of vector will increase with an increased dimension it is not the case for the cosine. Therefore the curse of dimensionality finds no application here.

$\endgroup$
1
  • $\begingroup$ I agree with your first point: if the data we have is actually contained in a smaller dimensional submanifold then we have some hope for avoiding the curse. I disagree with your second point: cosine similarity is basically just projecting all of your data onto a sphere. A large dimensional sphere has the same curse as a large dimensional Euclidean space. $\endgroup$ Commented Feb 16 at 19:09

Your Answer

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

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