19 ms·
Spikey Spheres
- musgravepeter 10y agoFun. I love that weird intuition trap you mention - the volume of a N dimensional sphere of radius R sphere goes to zero as N -> infinity. https://en.wikipedia.org/wiki/Volume_of_an_n-ball https://en.wikipedia.org/wiki/Volume_of_an_n-ball
- jacobolus 10y agoThis comes down to the definition of (hyper)volume. We use a (hyper)cube as our unit, but that’s somewhat arbitrary. We could alternately define (hyper)volume using a standard n–simplex as the unit, then we would say the volume of an n–ball → ∞ as n → ∞.
- Someone 10y agohere is a way to intuit that: - because (1-ε)^n/1^n goes to zero if n goes up, most of the volume of a cube gets concentrated near its surface. - to go from a n-dimensional cube to a n-dimensional sphere, you have to cut away most of its surface (everything except for 2n 'caps' near the points with coordinates (0,0,0,...,0,0,±½,0,0,0,...,0,0,0)), and hence, most of its volume.
- SonOfLilit 10y agoFor a more rigorous treatment (and many other gems on the border of highly practical and highly theoretical), see Richard Hamming's great book "The Art of Doing Science and Engineering", available for download from Bret Victor's website: http://worrydream.com/refs/Hamming-TheArtOfDoingScienceAndEngineering.pdf http://worrydream.com/refs/Hamming-TheArtOfDoingScienceAndEn...
- srean 10y agoHigh dimensions are indeed very, what shall I say, non-intuitive. Bellman introduced, or perhaps popularized, the term 'curse of dimensionality'. High dimensions may also comes with its blessing, 'concentration of measure' a phenomenon where randomness concentrates into events of certainty in high dimensions. I checked out their Wikipedia pages, while the former has a lucid description, the page on the latter is quite technical. Both these notions play a significant role in topics like machine learning, statistics, function approximations etc. Its sometimes a delight sometimes sheer frustration to see these two phenomena play it out.
- snippyhollow 10y agoI did a quick "visualization" hack a while ago http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/syhw/9025964/raw/441645b476a2a997f27f5993e4da2988febe1ef3/SpikeySpheres http://nbviewer.jupyter.org/urls/gist.githubusercontent.com/...
- tel 10y agoAnother counterintuitive result in this vein is to think about randomly sampling uniformly distributed points in a sphere. As the dimension rises, the chance of finding a sample within, say, r/100 of the surface goes to infinity. In high dimensions, all of the mass of the sphere is concentrated at the edge.
- falcor84 10y agoSorry for the nitpick, but I assume you meant that the chance goes to 100%, rather than infinity.
- tel 10y agoYup! But too late to edit :( Thanks!
- wyager 10y agoThat makes sense now that you mention it. The equation for the surface area of an n-sphere goes up as r^n, and the volume growth at any given radius is equal to the surface area at that radius.
- wbl 10y agoI've heard this phrased as "oranges are not a fun fruit in high dimensions".
- dllthomas 10y agoPithy.
- pakl 10y agoExactly! Now consider that deep networks that classify images are tasked with getting reliable statistics in very high dimensional spaces. Conv nets are being forced to map from high dimensional spaces down to a very low dimensional categorical decision. This is why weird classification errors you see in "adversarial examples" keep popping up. The learned classification boundaries are very spiky, and it's easy for the world to fall in between the spikes. More data can't solve it (at least not practically) because there are way too many gaps between the spikes. A more tractable approach is to learn to use dynamics for perception rather than ("just") statistics. The dynamical physics of a ball rolling is much simpler (lower dimensional, more tractable) than a statistical view of millions of differently illuminated pixels hitting a camera. (A colleague of mine has a blog post on this issue of "statistics and dynamics" at http://blog.piekniewski.info/2016/11/01/statistics-and-dynamics/ http://blog.piekniewski.info/2016/11/01/statistics-and-dynam...)
- ot 10y agoOne other mindblowing fact is that if you project the mass of the sphere onto a line that goes through the origin, you get a Gaussian distribution as the dimension goes to infinity. If you're interested in more technical details about the weird geometry of balls, I can't recommend enough the first few pages of "An Elementary Introduction to Modern Convex Geometry" [1]. Ironically, the author's last name is Ball. [1] http://library.msri.org/books/Book31/files/ball.pdf http://library.msri.org/books/Book31/files/ball.pdf
- repsilat 10y ago> you get a Gaussian distribution as the dimension goes to infinity. Wow, that's really cool. I wonder, I'm sure you could prove this in more direct ways, but is it also a consequence of the central limit theorem?
- effie 10y agoThat's doubtful, as no random variables are apparently involved in the questions of geometry. The situation with the Gauss function is perhaps similar to that of pi, which appeared originally in geometry of circles and only later was discovered in formulae for probability distributions or sums of infinite series. Neither Gauss function nor pi seem to be naturally connected to questions of probability; but applications of the probability theory to special situations lead to expressions that use these most basic mathematical concepts.
- rcthompson 10y agoIt should be clarified that this fact refers to a ball of volume 1 in N dimensions. Since the volume is held constant, as the dimension goes to infinity, so does the radius.
- js8 10y agoI am not sure I would interpret this observation as spheres that are getting more spikey. Maybe what gets more spikey is the actual box, so the sphere has it easier to touch or even extend outside of it.
- JadeNB 10y ago> I am not sure I would interpret this observation as spheres that are getting more spikey. Maybe what gets more spikey is the actual box, so the sphere has it easier to touch or even extend outside of it. I think that this is not correct. In n dimensions, the cross section of a unit n-cube near the edge is a unit (n - 1)-cube, just as your intuition tells you. However, the cross section of a unit n-sphere near its intersection with the unit n-cube is a tiny, tiny (n - 1)-sphere (the radius of a cross section at height z = 1 − 𝜀 goes to 0 as n goes to ∞); this is the 'spikiness' that the author is discussing.
- js8 10y agoOn the other hand, it seems to me (maybe I am wrong) that the solid n-dimensional angle of each corner of the n-cube is progressively smaller (as a ratio of full n-dimensional angle). So in that sense, each n-cube gets more spikey, and there is "less space" in each corner for each n-sphere that enclose the central n-sphere.
- jakobegger 10y agoA teacher of mine told us, "Don't try to imagine 4D space. You can't. If you think you can imagine a 4D hypersphere, you're wrong. It's just not possible." And everytime someone talks about how to imagine higher-dimensional space, I have to think back, and I'm convinced that my teacher was right. Our intuitive understanding of 2D and 3D just doesn't generalise to higher dimensions. A hypersphere is nothing like a sphere, just like a sphere is nothing like a circle, which is again nothing like a line segment. If you talk about multidimensional geometries, stick to the math, and don't try imagining it. Analogies to 2D or 3D objects (it's smooth, but like a spike) are pointless and don't lead to new insights. We really need to stick to precise, mathematical language if we want to work with higher dimensional geometry.
- Retric 10y agoI find some value from picturing 4D objects as 3D objects moving and changing size and or shape through space. In the ball example. At T:1/4 and T:3/4 I see the same 3D ball shape with different balls. At time 0, 0.5, and 1 they are gone. As such it's natural for a 4D where to fit in the middle as it can be centered at T:1/2 and you just need to find the intersection point in 4D space where the balls touch. Now, this does not work for rotations, but it's better than nothing.
- jacobolus 10y agoHowever there is a 4-dimensional sphere (3-sphere) that you can easily access: the possible rotations of any object in 3-dimensional space is topologically and metrically isomorphic to a (half of a) 3-sphere, in the same way as the rotations of an object in 2-dimensional space are isomorphic to a 1-sphere (circle). Think of an object’s current orientation as the “north pole” of our abstract 4-dimensional sphere. Rotating the object around any axis pushes you toward the equator, which you reach once you have rotated the object halfway around (the equator is made from all 180° turns, and is topologically a 2-sphere). Continuing to rotate the object takes you towards the “south pole”, which is where you get if you rotate your object 360°. To get back to the north pole, rotate by 360° again. Cf. https://en.wikipedia.org/wiki/Versor https://en.wikipedia.org/wiki/Versor https://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation https://en.wikipedia.org/wiki/Quaternions_and_spatial_rotati... and https://en.wikipedia.org/wiki/Rotation_group_SO(3) https://en.wikipedia.org/wiki/Rotation_group_SO(3) * * * One other way you can get at the 3-sphere is by taking a stereographic projection into all of 3-dimensional space (plus a point at infinity). If you have some 3-dimensional shapes drawn on the surface of your 3-sphere, these will get distorted under the stereographic projection, but locally angles will be preserved, just like a stereographic projection of the 2-sphere onto a piece of paper.
- benjismith 10y agoVery interesting! I've done a lot of work with higher-dimensional spaces in NLP and Machine Learning (creating feature vectors with tens of thousands of dimensions, and then calculating cosines between vectors to estimate document similarity), but these ideas about spikey geometry are new to me and very insightful. Thanks!
- sbierwagen 10y agohttps://en.wikipedia.org/wiki/Curse_of_dimensionality https://en.wikipedia.org/wiki/Curse_of_dimensionality
- pakl 10y agoTo see some concrete examples of how this sort of phenomenon causes surprising failures in deep networks classifying images, see "Intriguing properties of neural networks"[1] [1] https://cs.nyu.edu/~zaremba/docs/understanding.pdf https://cs.nyu.edu/~zaremba/docs/understanding.pdf
- nkurz 10y agoSo one visualisation of a sphere in very high dimensions is not something smooth and round, but something that is somehow simultaneously very symmetrical, and yet also very spikey. It's unlikely that this will help anyone, but I recently learned that the spiky protrusions a naval mine are called "Hertz horns": http://www.popsci.com/blog-network/shipshape/terrible-thing-waits-under-ocean http://www.popsci.com/blog-network/shipshape/terrible-thing-... So if for some reason you are trying to trying to make a loose analogy to the spikiness of hyperspheres to an older military mariner who has never seen a hedgehog, you could clarify by saying "you know, like the Hertz horns on a sea mine?"