31:[] 2f:{"title":"High-Dimensional Hijinks","cells":[{"id":0,"value":"# High-Dimensional Hijinks\n\nOur intuitions about space, size, and distance can break down as we go from familiar 2- or 3-dimensional spaces into multi-dimensional worlds...","pinned":false,"hidden":false,"mode":"md"},{"id":147,"value":"## How much of its bounding box does a sphere take up?\n\nA \"sphere\" (in any dimension) is the surface consisting of all points at a specified distance (radius) from a center point. How much volume does this surface contain relative to the smallest bounding box (\"cube\") containing that sphere?\n\nImagine we have a sphere of radius 1. In 1-dimensional space, this is just a line segment of length 2 (the diameter of the \"sphere\"), and is exactly the same size as the 1D \"box\" containing our sphere. So the coverage is 100% (2 / 2 = 1).\n\nIn 2-dimensional space, our \"sphere\" is a circle with radius r = 1. So it's area is π r² = π. Meanwhile, the square enclosing the circle has sides of length s = 2, with area s² = 4. So the coverage is 78.5% (π / 4 = ${(Math.PI / 4).toFixed(4)}...).\n\nAlready, we see that as we gained a dimension our sphere got smaller relative to the \"corners\" of our bounding box. What happens as we go to higher dimensions?","pinned":false,"hidden":false,"mode":"md"},{"id":16,"value":"Plot.plot({\n x: { domain: [0, ndim] },\n y: { type: scaleType, percent: true },\n marks: [\n Plot.lineY(volumes, { x: 'dimensions', y: 'coverage' }),\n Plot.dot(volumes, { x: 'dimensions', y: 'coverage', fill: 'black', r: 2, title: d => d.coverage.toFixed(3) })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":165,"value":"viewof scaleType = Inputs.select(['linear', 'log'], { label: 'Scale Type', format: v => v[0].toUpperCase() + v.slice(1) })","pinned":false,"hidden":false,"mode":"ojs"},{"id":162,"value":"The relative volume of the sphere drops to a miniscule proportion of the overall region! A fixed region of high dimensional space is almost all \"corners\".","pinned":false,"hidden":false,"mode":"md"},{"id":175,"value":"## What does it mean to be average?\n\nLet sample some random points assuming a normal (Gaussian) distribution. Given enough samples, in one-dimension we should see a standard \"bell curve\" with mean (μ) and standard deviation (σ) closely matching our chosen distribution.\n\nHow far away, on average, is a point from the mean of the distribution? We might naturally expect values around the mean (the peak of the distribution) to be the most common, and indeed that is true for a one-dimensional distribution.\n\nThe plot below shows the results of sampling 10,000 points (with μ = 0 and σ = 1) and measuring the distance from the mean. The curve peaks around zero (matching the mean) and then drops off as we get further away.\n\nBut what happens as the dimensionality increases? Let's assume a standard deviation of σ_i = 1 for each dimension, and no covariance between dimensions.\n\n_Adjust the slider below and observe how the distance distribution shifts..._","pinned":false,"hidden":false,"mode":"md"},{"id":79,"value":"viewof dim = Inputs.range([1, ndim], { step: 1, value: 1, label: 'Dimensions' })","pinned":false,"hidden":false,"mode":"ojs"},{"id":85,"value":"Plot.plot({\n x: { domain: [0, 10] },\n y: { domain: [0, 4000] },\n marks: [\n Plot.rectY(dists, { x1: 'distance', x2: d => d.distance + 0.05, y: 'count', fill: 'steelblue' })\n ]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":193,"value":"As the dimensionality increases, most points actually reside some distance _away_ from the mean! After adding only a couple of dimensions, one is extremely unlikely to sample a point that resides near the mean of the distribution. Instead, most points reside in a \"shell\" some distance around the mean.","pinned":false,"hidden":false,"mode":"md"},{"id":205,"value":"_Exercises_:\n\n- Can you deduce the relationship between the dimensionality of the space (n) and the mode (peak) of the distance distribution?\n- What happens if instead we adjust the standard deviation as a function of the dimensionality n, for example by setting σ_i = √n rather than σ_i = 0?","pinned":false,"hidden":false,"mode":"md"},{"id":187,"value":"## Appendix","pinned":false,"hidden":false,"mode":"md"},{"id":20,"value":"ndim = 50","pinned":false,"hidden":false,"mode":"ojs"},{"id":8,"value":"volumes = d3.range(1, ndim + 1, 1).map(dim => ({\n dimensions: dim,\n volume: Math.pow(Math.PI, dim / 2) / mathjs.gamma(dim / 2 + 1),\n coverage: (Math.pow(Math.PI, dim / 2) / mathjs.gamma(dim / 2 + 1)) / Math.pow(2, dim),\n surfaceArea: 2 * Math.pow(Math.PI, (dim + 1) / 2) / mathjs.gamma((dim + 1) / 2)\n}))","pinned":false,"hidden":false,"mode":"ojs"},{"id":90,"value":"dists = aq.table({ x: Float64Array.from({ length: 1e5 }, () => l2(dim)) })\n .groupby({ distance: aq.bin('x', { step: 0.05 }) })\n .count()","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"l2 = function(dims) {\n let l2 = 0, i = dims, v;\n while (i--) l2 += (v = random()) * v;\n return Math.sqrt(l2);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"random = vega.randomNormal().sample","pinned":false,"hidden":false,"mode":"ojs"},{"id":6,"value":"mathjs = require('mathjs')","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"vega = require('vega-statistics')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}