4
$\begingroup$

I read some blog articles recently. One mentions that you could not imagine high dimensional space as 2d or 3d as distance between any 2 points in high dimensional space tends to be similar, which means 'dense'. However in the t-SNE paper, it says high dimensional space tends to be sparse such that you have to employ special dimensionality reduction techniques to visualize in 2d or 3d space in meaningful way. So how to reconciliate these 2 different views?

$\endgroup$
9
$\begingroup$

Data in a high dimensional space tends to be sparser than in lower dimensions. There are various ways to quantify this, but one way of thinking that may help your intuition is to start by imagining points spread uniformly at random in a three dimensional box. Now flatten the box into a square, pushing two opposite sides together so all the points lie on a single plane. Do you see that the average distance between a point and its nearest neighbor is now smaller? Now flatten the square into a line segment. Do you see that the average distance between a point and its neighbors is now smaller still?

There is no conflict between this and saying that the average distance between any 2 points in the high dimensional space tends to be similar. The latter statement doesn't imply density. The real number line is dense (it has no gaps), and yet the distance between points ranges from 0 to infinity. The point is that the higher the dimension of your space, the more likely the points are to lie near the edges of the space rather than the center.

Again, consider the dimensions we can actually see. Consider a circle with radius=1, inscribed in a square with sides of length=2. The circle occupies $\pi / 4$ of the square's area, about 78.5%. Now consider a sphere of radius=1 inscribed in a cube with sides of length=2. The sphere occupies $\pi / 6$ of the cube's volume, about 52.4%. As you see in this example, the odds of a randomly placed point lying close to the center (with close to the center in this case meaning within the circle or the sphere) is lower as the dimension increases. Points are more likely to be in the corners. This is why in high dimensions the distance between the points tends to be similar - because randomly placed points tend to be close to the edges of the region.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Another example I like: take 6 points evenly distributed on a circumference and they will be 60º apart; 6 points evenly distributed in the surface of a sphere will be 90º apart. $\endgroup$ – Pere Oct 18 '16 at 18:34
  • 1
    $\begingroup$ @Pere That's a good one, and a good complement to my answer, since it makes clear that the increasing sparseness isn't something unique to square boxes. $\endgroup$ – Tim Goodman Oct 18 '16 at 18:46
1
$\begingroup$

I would like to elaborate a bit on the fact that data in high dimensional spaces is sparser.

Usually, we think of euclidean spaces. This means if we have points $p_1, p_2 \in \mathbb{R}^n$ we say their distance is

$$d(p_1, p_2) = \sqrt{\sum_{i=1}^n {\left (p_1^{(i)} - p_2^{(i)} \right )}^2}$$

So we take the square root of the sum of the component-wise squared difference.

Now think of two points in a unit hypercube in $\mathbb{R}^n$ (hence $[0, 1]^n$). The maximum distance two points can have in this hypercube is when they are on the diagonal. Hence the distance is $\sqrt{n}$, meaning the higher the dimension is, the farer away can points be in the unit hypercube.

See also:

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Furthermore, the distance is concentrated; for most points, the distance is close to some value, and this is why you shouldn't use the Euclidean distance in high dimensions; it's not informative. $\endgroup$ – Emre Oct 19 '16 at 21:21
  • $\begingroup$ @Emre then what metric should be used in high dimensions? Fractional distance has similar concentration problem as Euclidean distance as shown in the link above. Is this still an active research area? $\endgroup$ – Michael SM Oct 20 '16 at 5:12
  • $\begingroup$ One solution is to find a lower-dimensional embedding; the "manifold learning" approach. t-SNE is a fine example. You will also find related papers on "representation learning". $\endgroup$ – Emre Oct 20 '16 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.