4 ms·

Can you please explain why this distribution of embeddings is expected for high-dim spaces?

• nybsjytm 3y ago
  It's an example of concentration of measure: https://en.wikipedia.org/wiki/Concentration_of_measure https://en.wikipedia.org/wiki/Concentration_of_measure It's easy to verify this for yourself in a simple example in something like python. Draw from a multivariate normal distribution (or almost anything) in a 1000-dimensional space and look at the norm of your vector. If you do this a lot of times you'll see that the answer is close to the same each time. This even holds true if you replace the vector norm by the distance to an arbitrary fixed point. edit: here's some code: import numpy import matplotlib.pyplot norms = [] dists = [] for i in range(5000): vec = numpy.random.normal(size=4096) norms.append(numpy.linalg.norm(vec)) dists.append(numpy.linalg.norm(vec-numpy.ones(4096))) matplotlib.pyplot.hist(norms) matplotlib.pyplot.show() matplotlib.pyplot.hist(dists) matplotlib.pyplot.show() (didn't render right, sorry)
  • zyklu5 3y ago
    Can't believe you are the only one to mention this. I thought concentration of measure would be at least mentioned to ML students right about the time they learn about the curse of dimensionality
• ttul 3y ago
  One way to think about high-dimensional spaces is that there is a huge amount of volume relative to the number of coordinates in the space. Yes, there are infinitely many coordinates; however, each coordinate has more dimensions to it relative to a lower-dimensional space. As you increase the dimensionality, coordinates representing meaningful data spread out, leading to a bizarre situation in which most data points in the space are as far apart as a randomly chosen pair of data points, even if the data points you are measuring the distance between should be "close" to each other. For instance, consider a unit cube in n dimensions. The volume of this cube (1 unit on each side) remains constant, but the distance from the center to a corner increases with the square root of the number of dimensions. This implies that in high dimensions, most of the volume of a hypercube is located at its corners. This is bizarre to comprehend because it's hard to stop imagining a "cube" in the 3D sense. Algorithms that rely on distance measures (like k-nearest neighbors or clustering) may perform poorly in high-dimensional spaces without dimensionality reduction techniques like PCA (Principal Component Analysis) or t-SNE (t-Distributed Stochastic Neighbor Embedding). And even with these techniques, you can get very misleading results.
  • nybsjytm 3y ago
    >For instance, consider a unit cube in n dimensions. The volume of this cube (1 unit on each side) remains constant, but the distance from the center to a corner increases with the square root of the number of dimensions. This implies that in high dimensions, most of the volume of a hypercube is located at its corners. This is bizarre to comprehend because it's hard to stop imagining a "cube" in the 3D sense. This is incorrect. If you put a little box of small side length x at each corner, then each box has volume x^n and there are 2^n many of them, so the total volume they take up is 2^nx^n=(2x)^n, which is very small. Maybe what you meant is that most of the volume of a high-dimensional hypersphere is near its surface.
    • ttul 3y ago
      You are correct and thank you for the correction.
  • kridsdale1 3y ago
    I can kind of imagine it. There’s more “concentration of surface area, per volume” in the sharp corners of a 3-cube than there is in the center of a face. Surface area is 2-volume.