Counterintuitive Properties of High Dimensional Space
marckhoury.github.io
marckhoury.github.io
"Not only is today's Numberphile video potentially relevant, Numberphile actually directly addressed the article's exact topic several months ago."
How can you make two solid 2D squares occupy the space? They can't travel through each other, so...? Easy. Lift one of the squares into the 3rd Dimension, move it to the same X,Y coords, then drop it on the other (think of putting stacking 2 pieces of paper).
Similarly, you can have two 3D objects occupy the same space by "lifting" one into the 4th dimension, moving it to the same X,Y,Z coords as the other, and then "dropping it". You can "cheat" by thinking of the 4th dimension as time - one object travels through time, places itself at the same position of where the other object is, then returns. But as I said, that's "cheating".
1 dimensional - an endless line with 2 spots marking boundaries to some subpart X. If you're inside, you need to enter 2nd dimension to escape that subpart X without crossing boundaries (and ie come back to original dimension).
2 dimensional - circle, you're inside, you need to enter 3rd dimension to escape without touching the circle.
3 dimensional - sphere, entering 4th dimension to escape without touching the sphere.
I can't go with my simpleton mind much further but it should scale indefinitely :)
It's tempting to think of data sets as "point clouds". This article is a reality check for me: you can't safely apply intuition about 2- and 3-d point clouds to higher dimensional data. I suspect that this explains why methods like tSNE seem to produce unstable results depending on the parameters [0]. The notion of a "neighbor" in high dimensions is just not what I think it is.
I suppose the same is true for high-dimensional cost surfaces. Gradient descent is often described as "like walking down a hill". But without a deep understanding of high-dimensional geometry, I'm not at all confident that I know what a 4-, 10-, or 1000-dimensional hill looks like.
The lesson: Be skeptical of my own geometric intuition unless it is firmly backed by math.
On a thousand dimensional hill, my intuition is that it locally looks like a low dimensional hill, along axes that you can find through techniques like Principal Components Analysis. This has yet to mislead me. On the other hand, my pure math background was a long time ago, and I have not explored machine learning in any real depth...
Maybe I'm nitpicking, but this interpretation is not accurate IMO. Volume of N-dimensional sphere is measured is different units than that of (N-1)-dimensional sphere. E.g. one is m^5, and another is m^4. Comparing values measured in different units is not the best idea. It would be better worded as : the ratio of volume of N-dimensional sphere to the volume of same-dimensional cube approaches zero when N goes to infinity. But this is not a counter-intuitive statement.
It’s from this excellent article by Pedro Domingos: https://homes.cs.washington.edu/~pedrod/papers/cacm12.pdf
Regardless of the dimension, the volume of n-ball is V_n(r) = c_n * r^n, where r is radius, and c_n is a constant depending on n. The grandparent observation is that surprisingly enough, c_n goes (rather quickly) to 0 as n goes to infinity, so for unit n-ball, that is, a ball of radius 1, the volume is exactly c_n, which is very small. This is surprising to us, because in familiar case of n = 3, c_3 = 4/3 pi, which is moderately large.
As for the mass being concentrated around the peel, suppose we have an orange of radius R+e, and its peel has thickness of e. Then, the ratio of volume of the peel to the volume of the whole orange is exactly:
(V_n(R+e) - V_n(R))/V_n(R+e) = 1 - V_n(R)/V_n(R+e) = 1 - c_n R^n / c_n (R+e)^n = 1 - R^n/(R+e)^n = 1 - (R/(R+e))^n
Now, since R/(R+e) < 1, for large n, (R/(R+e))^n will be very small, and so the ratio of the volume of the peel to the volume of the whole orange will be 1 minus something very small, so close to 1.
Note that the peel argument works just as well with "square" oranges -- they also have most of their mass concentrated around the peel, but contrary to round oranges, their whole mass does not go to 0 as the dimension increases. To see that, note that the volume of n-dimensional square with side of R is exactly R^n, and if you do the above computation, it's exactly the same (note that the constant c_n cancelled out anyway).
In this sense, your comment and the grandparent ones are about two different phenomenons -- grandparent is talking specificly about the geometry of the sphere in L_2 norm, while you are talking generally about n-dimensional volumes.
The intuition for operating with polynomials is best obtained by not worrying about units.
(Even more infuriating is that physicists do believe in units, except when writing code).
I was too lazy to do the strict proof, so I sprayed it with lots of Monte Carlo bullets. It's like a page of code in any language. It turns out, as the article says, the volume of the N-sphere keeps getting smaller and smaller as N increases. In higher dimensions, there's a lot more volume in the corners of the N-cube. It did seem like the N-sphere was shrinking down to nothing in spaces with lots of dimensions.
Seems obvious after you read the article and look at the diagrams, but back then I had to think about it for a while. I thought my implementation was wrong somehow, but eventually I realized what was going on. Pretty amazing stuff.
which I solved with this F# script, while learning F# https://gist.github.com/jackmott/bec1e4c7e84904702bac1dae97c...
Quote: "In his article “An Adventure in the Nth Dimension,” Brian Hayes explores how in high dimensions, balls have surprisingly little volume. As the dimension n increases, the volume of a ball of radius 1 increases until n = 5. Then for larger n the volume steadily decreases."
[1] https://www.johndcook.com/blog/2017/07/13/concentration_of_m...
[2] https://www.johndcook.com/blog/2017/07/19/corners-stick-out-...
[3] https://www.johndcook.com/blog/2012/10/23/dimension-5-isnt-s...
The book is quite hard to get hold of, but here is a recent talk: https://www.youtube.com/watch?v=zUCoxhExe0o
Another interesting property is that high dimensional space has many shortcuts, or that at any point there are many paths. It's like a kaleidoscope with infinite reflections or like a mirror house. Or it's like any point has many close neighbours which can, paradoxically, be far apart between them.
Whereas a reasonable person needs evidence of affirmative to believe something. I.e., news that NASA probes have discovered bacteria in subterranean wells on Mars.
The former way of thinking can be used to "prove" just about anything. So yeah, in some sense, most data points helps fuel more conspiracies because certain people are conditioned to believe anything.
I think it would be more interesting if this wasn't the case. The set of all possible English words is <200,000, with probably 10% of those being in common use. Given the small set, large number of dimensions, and the nature of language, it seems likely that non-random word vectors would tend towards orthogonality.
I'm assuming you mean that, "I will run with Bob" and "I will jog with Stacy" are not orthogonal, because they convey a very similar message, but are orthogonal to, "Man, that was a good beer."
3 Blue,1 Brown had a video recently that kicked off my head scratching and is a great complement to your article: https://www.youtube.com/watch?v=zwAD6dRSVyI
That's a great video, I really like his slider method for understanding the coordinates. Thanks for linking it!
So, what is a 2-dimensional Sphere called if the 3-dimensional one is a 2-sphere?
A sphere in three dimensional space is a two dimensional object, in the sense that it's a surface on which the points can be described by two coordinates (say longitude and latitude).
Similarly a point on a circle can be described by a single coordinate (distance around the circle).
So the 1-sphere is a circle, and normally lives in 2 dimensional space, while the ordinary sphere is called a 2-sphere, and lives in three dimensional space.
Note that analogously, a cube in 3 dimensional space is always considered to be 3 dimensional.
>a cube in 3 dimensional space is always considered to be 3 dimensional.
So "cubes" are taken to include their interior. That makes sense I suppose. I wonder what the surface of a cube is called. A "box" maybe?
If you know German, then you might like this talk as well: https://www.youtube.com/watch?v=d19zmiVBLS8 (The curious world of four-dimensional geometry)
In dimensions 4 through infinity we quickly come to a problem. Do we come up with unique names to refer to amount of space enclosed by a unit sphere? Mathematicians have decided to just use the word volume. We rely on context to make it clear what the dimension is. Similarly we use the word n-sphere to refer to the collection of points in n-dimensional space that are exactly 1 unit from the origin.
Surface area of an n-sphere is used and studied.