4 ms·

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

by ntumlin 14y ago

i2pi 14y ago
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 you were to distribute points with a Gaussian distribution in 2D, most of the mass is near the mean point of the distribution. As you increase the number of dimensions, more and more mass is contained within 'outliers'. In high dimensional space, things that seem unlikely in our usual 3D world become far more probable.
- aktau 14y ago
  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?
polm23 14y ago
The other replies are correct, but why do you care? The trick is what's counter-intuitive about this. If you work in a widget factory and are trying to figure out why widgets go bad, you might sort your widgets by size and color. If sorting by that doesn't seem to help you find a pattern in the bad widgets, you might add more data - whether the widgets are right or left handed, metric or English units, or something. The problem with this is that by adding more data you're actually making your problem harder since you've added an extra dimension, which as other commentors described will blow up your search space pretty quickly. The extra data will be the most help if it allows you to ignore the previous data. The more dimensions you add, the less likely it is the next dimension makes things simpler rather than just more complicated. One more reason to keep things simple.
francoisdevlin 14y ago
As my numerics professor said, "The more dimensions, the more you curse" :) This has to do with trying to get a finer estimate of a problem. Suppose you have a one dimensional problem you're trying to solve. You take the line segment, break it into 100 pieces. These techniques usually a matrix with about 100 rows in it, and you have to invert it / find and eigenvalue, etc. These are O(n^2) or O(n^3) depending on the problem. Now, let's get a better estimate, and use 200 points. We've doubled the number of points, so our solution now takes 4 to 8 times longer, depending on the type of problem. Switch gears to a 2d problem. You now have a 100 X 100 mesh, that creates a matrix with 10,000 elements. If you want to improve the accuracy, you need a 200 X 200 mesh, which creates a 40,000 element matrix. Our algorithms cost O(n^4) and O(n^6) to get a better measurement now. Now consider 3 dimensions and beyond. Your 100 x 100 x 100 system becomes a 200 x 200 x 200 system. This makes what is technically known a FREAKING HUGE matrix. Your algorithm is effectively O(n^6) or O(n^9), depending on the problem type. You can see how this gets nasty quickly. HTH
Brashman 14y ago
One example is suppose I'm trying to tune some parameters and I'm going to do this by sampling. If I have only one parameter which is between 0 and 1 to tune, then I can find the best choice to within .01 by trying 100 values (each .01 increment). Now instead, consider what happens when I have 100 parameters (high dimensionality). Now with 100 samples, I can't really learn much. Even if I wanted to try only 2 values in dimension (say 0 and 1), there would be 2^100 (roughly 10^30) different possibilities to try. I would say the key line from Wikipedia is that, "when the dimensionality increases, the volume of the space increases so fast that the available data becomes sparse."
thirdhaf 14y ago
I'm a big fan of concrete examples so here's one: Let's say you have two points on a line labeled 0 and 1. Let's also suppose there's a special property you're interested in at one of these locations, it minimizes some function, there's a pot of gold there, it's infested with lions, doesn't matter. Since there are only two points it's easy to just check both points and empirically find which one you want. We can extend this idea easily into 2 dimensions, now we have two axes each consisting of two points along perpendicular lines. Enumerated the points are [0,0], [0,1], [1,0], [1,1] and as you can see there are four of them. It should also be pretty easy to see that if we extend this further into 3 dimensions that you once again double the number of points in your space to 8. You can see this by starting to enumerate them in the same way: [0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0]...[1,1,1] From this it should follow that if you extend the problem into n-dimensions you end up with 2^n different points in your search space. If n is a small number, say 30 it's still possible to do an exhaustive search with a computer since 2^30 ~ 10^9 but soon you run out of resources regardless of how much money you're throwing at the problem. This is the heart of the curse of dimensionality, starting with stupidly easy problems in one dimension quickly gets you in trouble when you want to extend it. This is not to say that we can NEVER deal with high-dimensional problems, two wonderful areas where we are VERY good at solving problems are linear programming and quadratic programming, in the former problems with hundreds of thousands of dimensions are feasible and thousands of dimensions in the case of the latter.

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

by ntumlin 14y ago

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

i2pi 14y ago

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 you were to distribute points with a Gaussian distribution in 2D, most of the mass is near the mean point of the distribution. As you increase the number of dimensions, more and more mass is contained within 'outliers'. In high dimensional space, things that seem unlikely in our usual 3D world become far more probable.

aktau 14y ago
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?

polm23 14y ago

The other replies are correct, but why do you care? The trick is what's counter-intuitive about this. If you work in a widget factory and are trying to figure out why widgets go bad, you might sort your widgets by size and color. If sorting by that doesn't seem to help you find a pattern in the bad widgets, you might add more data - whether the widgets are right or left handed, metric or English units, or something. The problem with this is that by adding more data you're actually making your problem harder since you've added an extra dimension, which as other commentors described will blow up your search space pretty quickly. The extra data will be the most help if it allows you to ignore the previous data. The more dimensions you add, the less likely it is the next dimension makes things simpler rather than just more complicated. One more reason to keep things simple.

francoisdevlin 14y ago

As my numerics professor said, "The more dimensions, the more you curse" :) This has to do with trying to get a finer estimate of a problem. Suppose you have a one dimensional problem you're trying to solve. You take the line segment, break it into 100 pieces. These techniques usually a matrix with about 100 rows in it, and you have to invert it / find and eigenvalue, etc. These are O(n^2) or O(n^3) depending on the problem. Now, let's get a better estimate, and use 200 points. We've doubled the number of points, so our solution now takes 4 to 8 times longer, depending on the type of problem. Switch gears to a 2d problem. You now have a 100 X 100 mesh, that creates a matrix with 10,000 elements. If you want to improve the accuracy, you need a 200 X 200 mesh, which creates a 40,000 element matrix. Our algorithms cost O(n^4) and O(n^6) to get a better measurement now. Now consider 3 dimensions and beyond. Your 100 x 100 x 100 system becomes a 200 x 200 x 200 system. This makes what is technically known a FREAKING HUGE matrix. Your algorithm is effectively O(n^6) or O(n^9), depending on the problem type. You can see how this gets nasty quickly. HTH

Brashman 14y ago

One example is suppose I'm trying to tune some parameters and I'm going to do this by sampling. If I have only one parameter which is between 0 and 1 to tune, then I can find the best choice to within .01 by trying 100 values (each .01 increment). Now instead, consider what happens when I have 100 parameters (high dimensionality). Now with 100 samples, I can't really learn much. Even if I wanted to try only 2 values in dimension (say 0 and 1), there would be 2^100 (roughly 10^30) different possibilities to try. I would say the key line from Wikipedia is that, "when the dimensionality increases, the volume of the space increases so fast that the available data becomes sparse."

thirdhaf 14y ago

I'm a big fan of concrete examples so here's one: Let's say you have two points on a line labeled 0 and 1. Let's also suppose there's a special property you're interested in at one of these locations, it minimizes some function, there's a pot of gold there, it's infested with lions, doesn't matter. Since there are only two points it's easy to just check both points and empirically find which one you want. We can extend this idea easily into 2 dimensions, now we have two axes each consisting of two points along perpendicular lines. Enumerated the points are [0,0], [0,1], [1,0], [1,1] and as you can see there are four of them. It should also be pretty easy to see that if we extend this further into 3 dimensions that you once again double the number of points in your space to 8. You can see this by starting to enumerate them in the same way: [0,0,0], [0,0,1], [0,1,0], [0,1,1], [1,0,0]...[1,1,1] From this it should follow that if you extend the problem into n-dimensions you end up with 2^n different points in your search space. If n is a small number, say 30 it's still possible to do an exhaustive search with a computer since 2^30 ~ 10^9 but soon you run out of resources regardless of how much money you're throwing at the problem. This is the heart of the curse of dimensionality, starting with stupidly easy problems in one dimension quickly gets you in trouble when you want to extend it. This is not to say that we can NEVER deal with high-dimensional problems, two wonderful areas where we are VERY good at solving problems are linear programming and quadratic programming, in the former problems with hundreds of thousands of dimensions are feasible and thousands of dimensions in the case of the latter.