Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Curse of dimensionality

en.wikipedia.org

Post reply on HN
Print view View original

21–30 of 30 posts

Re: Curse of dimensionality

#21

Post by colinhevans »

The number of parameters to be fit or estimated in a statistical or machine learning model will always be a function of the dimensionality. For example, fitting a Gaussian (a Bell Curve) with a fixed variance of 1.0 to an n-dimensional space requires estimating the mean, which is n parameters. If we want to estimate an nXn covariance matrix for our n-dimensional Gaussian, we need to estimate n+n^2 parameters. For linear or logistic regression, we'll need to estimate n+1 parameters, and so on.

The curse of dimensionality is that if you add dimensions but don't add data, your functions will overfit the data because you don't have sufficient samples to estimate your model parameters. The worst-case estimate is that for n dimensions, you will need on the order of 2^n samples. This comes from the combinatoric increase of relative "distances" as dimensions increase.

This 2^n bound assumes that your data has a high degree of uncorrelated variance across all dimensions. In practice, the curse of dimensionality often isn't a problem. This is because most high-dimensionality data residing in an n-dimensional space actually doesn't have uniform variance across all n dimensions, and can be mapped or otherwise transformed into a k-dimensional subspace where k is much smaller than n with a minimal loss of variance.

Dimensionality reduction approaches include principle component analysis (PCA), minimum message length methods (MML), various feature selection approaches, virtually every clustering algorithm. Anything that removes dimensions while retaining the essential information content will do the trick.

Re: Curse of dimensionality

#22

Post by tylerneylon »

When it comes to finding approximate neighbors, there is a nice simple trick to help address the curse of dimensionality.

An easy algorithm to find nearby neighbors is to split space into the generalization of squares / cubes, aka hypercubes. Then look at all the surrounding cubes and compile a list of all the neighbors in them. You can do this with a precomputed hash table mapping cubes to lists of points in that cube.

This suffers the curse because a cube in n dimensions has 3^n - 1 neighbors (it is in the middle of a 3x3x..x3 hypercube). Make it a little better with hash table from every cube corner to a list of points in all surrounding cubes, a benefit of 3^n down to 2^n lookups -- still exponential.

Simple idea: Split up space using triangles instead of squares (aka simplices instead of hypercubes). We just went from 2^n lookups down to n+1 (one for each corner) -- pretty good.

The questions are then: (1) how do you tile n-space with n-dim'l triangles/pyramids (simplices), and (2) how do we get highly regular simplices to do that? [Regularity is good because you usually want a sphere-like radius-based lookup.]

It turns out there's a vertex-transitive simplex that tiles any dimension, and as a bonus is easy to work with computationally. ("Vertex-transitive" is a type of regularity where basically every vertex "looks the same" as every other.) So if you care about point neighbors within a certain approximate radius, these tricks are extremely helpful.

Reference: http://www.siam.org/proceedings/soda/2010/SODA10_094_neylont...

Re: Curse of dimensionality

#23

Post by stiff »

Suppose you want to build a system that using some M features of the current weather (humidity, temperature, pressure etc.) will predict whether it will be sunny in 3 hours or not - to this end you manually collect a dataset of N measurements (samples) of those features together with the outcome 3 hours after taking the measurement. This dataset can be used to find a function that will map the current features of weather to a real variable from 0.0 to 1.0 - the likelihood of it being sunny in 3 hours given the samples we collected. Of course, since we cannot manually collect measurements of all possible combinations of features, we want to extend the domain of this function beyond just the combinations of features that occured in our measurements - we want to "generalize". The values of the function for those "generalized" inputs are our guesses about how the likelihood function behaves for measurements other than the ones we have taken. The guess for a given measurement is much more likely to be correct if we at least have _similar_ measurements in our collection.

Now, if there are too few features (M is too low), it might not be possible to do a good prediction. The basic aspect of the "curse of dimensionality" is that as the number M of features grows (linearly), the number of all possible combinations of the features grows exponentially and hence the number N of measurements you need to do to get a good representation of the whole space of possible feature combinations also grows exponentially. So either you have to collect much more measurements, or the function that is inferred will have to "guess" much more often, without having good evidence from the dataset in the form of similar cases.

What I refer to as "all possible combinations of features", can be thought as a high-dimensional space and hence it is customary and sometimes useful to use geometric language in analysing the problem.

Re: Curse of dimensionality

#24

Post by dnquark »

What finally made the curse of dimensionality "click" for me was recognizing that the volume of an n-sphere goes to zero as n grows large. In 2D, if I want to see which of my data points lie close to some reference point, I can draw a circle around my reference point and count the proportion of the data points inside. In 3D, I could do the same with a sphere. But in 20D, the volume of my hypersphere will be miniscule, and it will probably not even contain any points, so this procedure becomes useless for clustering. Note that I can't just pick the hypersphere of a larger radius: suppose all my points are contained inside a unit n-cube. The volume of the unit n-sphere, the largest one I could inscribe inside the n-cube will _still_ be approximately zero!

This result is pretty cool and somewhat surprising, and there's a neat and short derivation of it; in fact (shameless plug) I have a youtube video where I derive it in 3 minutes: http://www.youtube.com/watch?v=QkMn_5QpsX8 -- feel free to check it out!

Re: Curse of dimensionality

#26

Post by aktau »

i2pi wrote: post #6
ntumlin wrote: post #2

No article in simple.wikipedia.org, could someone please explain this in a bit simpler terms?

There are two things going on here. First, as other commenters have noted, that as you increase the number of dimensions, the search space grows exponentially. The second, and deeper problem, is that our intuitions about 'volume' fail for higher dimensional problems. As you increase the number of dimensions, the outer shell of any hypercube holds much more volume than the inner portion of the cube. This means that if…

I find this (and the other comment referencing the volumes of hypercubes) to be interesting. Perhaps exactly because it is so unintuitive. Maybe I could reason it up myself, but what exactly do you see as the "volume" of the inner portion and the "volume" of the shell? Are we talking about the same units here? Are there generic formulae?

Re: Curse of dimensionality

#27

Post by chuckbot »

dnquark wrote: post #24

What finally made the curse of dimensionality "click" for me was recognizing that the volume of an n-sphere goes to zero as n grows large. In 2D, if I want to see which of my data points lie close to some reference point, I can draw a circle around my reference point and count the proportion of the data points inside. In 3D, I could do the same with a sphere. But in 20D, the volume of my hypersphere will be miniscule…

Thank you, Sir! You are a scholar and a gentleman.

Re: Curse of dimensionality

#28

Post by tveita »

arjunnarayan wrote: post #17
pacala wrote: post #16

Earlier quoted context omitted.

Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.

Yes that will work. But, there are 1000C2 such combinations (that is, O(2^n)), and you have to try them all since you don't know which two dimensions are needed. And you cannot do each of the 100 separately in one-dimension and later hope to "combine" them together. In fact, you might not even know that it is 2 of the dimensions that are special. Maybe it is 7. So you have to try each of the 2^100 combinations separa…

I may be misunderstanding you, but the number of ways to pick 2 out of n dimensions is Θ(n²).

Even if we looked at up to d dimensions, (bruteforceable at Θ(n^d)), that doesn't imply we need to generalize to do all 1000.

The post you replied to actually suggested clustering just one dimension at a time. I think that's a reasonable solution given the situation you posited, where you have some dimensions that do cluster well, even individually, and some who are mostly noise.

I would say that the curse of dimensionality is more fundamental than the problem you describe. The problem doesn't lie just in separating noise from signal - in a truly high-dimensional space there may not be a "right angle" to see it from.

For a simple example, you may take randomly distributed points. Even at uniform random distribution, it is relatively easy to for instance index two dimensional points in such a way that you can later locate points that are close to any particular spot. For 20-dimensional points, this is very hard.

Re: Curse of dimensionality

#29

Post by mokus »

pacala wrote: post #16
arjunnarayan wrote: post #8

Here's my best attempt at a simple.wikipedia.org article. In accordance with both simple.wikipedia.org rules and the oft-repeated Einstein/Feynman/Michael Scott quotes about explaining things to 5-year olds being the best sign of understanding something yourself, I've kept the vocabulary simple: Feel free to remix and rework the text to improve it. "Machine learning" is often the problem of taking a bunch of data and…

Why not cluster one dimension at a time? K-means will meaningfully cluster for 2 of these dimensions and fail for the other 998. Measure how good the separation is and stick with the best X dimensions.

The problem is that in many dimensions that often just won't work. The cloud of points can be smeared in directions that don't line up with any axes, in such a way that no matter which 2 axes you choose the clusters will overlap (but choosing a plane that doesn't align with any axis will clearly separate them). Even in 3 dimensions, you can see this problem by considering your populations to lie on 2 parallel planes, x+y+z=1 and x+y+z=2. Looking at this in x-y, x-z, or y-z projections, the point clouds will often be inseparable. And yet if you know where to look, all it takes is a projection to one dimension (f(x,y,z) = x+y+z) to separate them cleanly.

The curse of dimensionality appears here in the fact that the "number" of possible ways of projecting the space increases dramatically with the dimension.

Re: Curse of dimensionality

#30

Post by mokus »

dnquark wrote: post #24

What finally made the curse of dimensionality "click" for me was recognizing that the volume of an n-sphere goes to zero as n grows large. In 2D, if I want to see which of my data points lie close to some reference point, I can draw a circle around my reference point and count the proportion of the data points inside. In 3D, I could do the same with a sphere. But in 20D, the volume of my hypersphere will be miniscule…

Very nice video. For those less able to follow the calculus, another way to get at least a little intuition about this result is to think about how far the farthest points in a unit cube are from the origin - in 20 dimensions, the point (1,1,...1,1) is sqrt(20) ~= 4.47 units from the origin, so the 19-sphere only "reaches" 1/sqrt(20) ~= 0.22 of the way to the corners of the 20-cube.
Post reply on HN