HN Explorer

Ask HN: How to better grok the “curse of dimensionality”?

3 points by Solvency ↗ HN
I've sort of stumbled onto this topic organically and now I'm rather curious. In the context of building a recommendation system, I understand the concept of a high dimensional space made of vectors, and how cosine similarity is a way to derive similarity between vectors regardless of their magnitude.

Naturally I was curious about using simple distance-based calculations instead, and I'm hearing about the curse of dimensionality. I think I sort of get it but only on a surface level, not very deeply.

I'm also curious if it's possible to take any high dimensional space and somehow convert it into a weighted graph instead? And if there are recommendation/similarity systems based on this approach instead, and basically how all of this works in general at a holistic level.

I find 3Blue1Brown's videos (like https://www.youtube.com/watch?v=WUvTyaaNkzM) to be so good at explaining subject matter. Is there anything in this format that really helps illustrate all of this new material I'm referring to?

7 comments

[ 3.1 ms ] story [ 30.2 ms ] thread
nextworddev
As you add more criteria, it becomes harder to find the result you are looking for.
abecedarius
Why don't you try explaining what it is you find puzzling, yourself? That's not clear to me from your questions.
Solvency
It's unclear why zeros (sparsity) matters. Why shouldn't total distance between vectors still be meaningful? Why does alignment of normalized vectors work as a proxy for similarity, regardless of magnitude? Just because someone says it does? If higher and higher dimensionality becomes problematic, why not subdivide the dimensions over time? Why not run some simple space compression on the vectors to minimize the space between them? There are just many simple questions that naturally start to pile up when reading about these ideas, which I'm sure could be answered in the form of extremely complex math/theory/etc... but if it were presented in a visually intuitive way, perhaps the answers would emerge intuitively to me. So I'm looking for that kind of video / media, if it exists.
pillefitz
Seems odd to me to be interested in these relatively niche topics and ask these very specific questions, but not wanting to spend some time learning linear algebra, which is often taught with lots of graphical examples. One of my favorite intro books: Linear Algebra by Martin Anthony
tnecniv
You’re asking questions about what I assume is the curse of dimensionality as applied to some machine learning problem. The curse of dimensionality is more general: it really boils down to the fact that adding dimensions causes volumes to grow exponentially.

A simple case to visualize that is not related to machine learning is to solve a PDE numerically. Typically this is done via some form of discretization. If you were to solve the PDE in 2D by discretizing a region into, say, a 10x10 grid, then you need to compute the solution at 100 points. If you were to solve the same PDE in a cube, and discretize it similarly, you now need to solve it at 1000 points. Thus, scaling to higher dimensional PDEs rapidly becomes intractable even if the PDE isn’t becoming harder to solve (e.g. resulting linear equations remain equally well conditioned).

In the case of learning, you want your samples to capture behaviors over some region of space. As the number of dimensions increases, so does the volume of space you must gain information from, and thus so does the number of samples you need to explore that space.

The compression you mention is actually a pretty big topic across fields called dimensionality reduction. The idea is that, despite whatever physical process is generating your data (in learning, PDE solving, etc.) giving you a high dimensional vector, this data lives on some lower dimensional manifold (basically you can describe it’s location using a relatively small number of coordinates, e.g. if your data lies on the radius of a unit circle, then a datum is a point in 2D space but you only need to tell me an angle from the origin for each data point). If you can determine this manifold, then any subsequent computation is easier because you can work in a lower dimensional space. The question then is how to find this manifold?

Regarding distances, I don’t quite understand your question, but consider this: there is a difference between distance on a manifold and distance in the Euclidean space in which that manifold lives. For example, the straight-line distance between me and you is not the distance I need to walk to get to you. The former clips through the earth’s crust (thereby leaving the manifold which is the earth’s surface), is a lower bound on how far I need to walk to get to you, and this lower bound becomes a worse approximation the farther apart we are from one another. Therefore, you likely want your algorithm to work with the distance on the manifold as that is more physically meaningful. Finally, distances for mathematical / algorithmic purposes are really relative. You can’t just move the data to be closer together — that would be like setting your height equal to my height in a data base arbitrarily. If you rescale all the distances (convert our heights to kilometers, for example), that doesn’t change anything about the problem once you rescale everything else to respect that change. Finding this manifold and working with relevant distances on the manifold is basically trying to do compression while preserving the most meaningful properties of your data.

esalman
I first encountered this in my machine learning class in the context of solving ridge regression or SVM.

Simply put, when performing SVM you want to find a plane that minimizes the sum of its distance from coordinates belonging to two classes. The coordinates can be very high dimensional, which makes the minimization problem hard (primal formulation: $y = w^Tx + b$, w being the weights you need to estimate, which is equal to a very high dimension).

With help of the Lagrangian of the primal formulation, you can show that $x' ~ w^Tx + b ~ ayx^Tx + b$. So instead of having to estimate a very high number of w's, you can do away with only estimating the dot product x^Tx, which is limited by the number of inputs. This is the kernel trick you can use to avoid the curse of dimensionality.

bjourne
Distances grows as dimensionality grows is the curse of dimensionality. Imagine you have a circle with unit radius inscribed in a square whose sides are 2. The circle's area is pi, so pi/2^2 = 79% of all points in the space [-1,-1]-[1,1] are less than unit distance away from origin. For a sphere inside a cube the fraction is (4*pi/3)/2^3 = 52%, for a hypersphere it is (pi^2/2)/2^4 = 31%, and so on. As the number of dimensions grows the fraction approaches zero. E.g. only 0.25% of all points are inside the 10-dimensional sphere. So the distance between two random points in a high-dimensional space is likely large. Thus, modelling documents as high-dimensional vectors breaks down because they will be distant from each other and therefore dissimilar even though they may be "similar" to a human.

One way to get around this is to take the cosine of the angle between the documents' respective vectors. While this often works better than the Euclidean distance, it is also affected by the curse of dimensionality. Afaik, there is no good way to work around the curse of dimensionality and similarity metrics not using vector representations often work better in practice. For example, one can model documents as bag-of-words and divide the size of the intersection with the size of the union.