The Curse of Dimensionality

You can find more info about the following post on my website: Dov Katz

The curse of dimensionality refers to various phenomena that arise when analyzing and organizing data in high-dimensional spaces (often with hundreds or thousands of dimensions) that do not occur in low-dimensional settings such as the three-dimensional physical space of everyday experience.” (https://en.wikipedia.org/wiki/Curse_of_dimensionality)

This is a funny definition if I’ve ever seen one. It implies that our everyday experience is low dimensional and therefore the data associated with it is easy to analyze and organize. But if the 3D world we live in was so simple, why is AI struggling to make sense of it?

The answer is that the above definition is both right and wrong. It’s wrong because the world we live in is very very very high dimensional. Sure, our space is three dimensional. But our visual perception of it is composed of millions of pixels refreshed multiple times per second. Therefore our visual data of the simple 3D space around us actually has millions of dimensions.

At the same time, this definition is exactly right. Or at least, it exposes a brilliant truth: it must be possible to organize the data pertaining to the world around us in a low dimensional form. Otherwise, how can any intelligent creature with finite resources (read: humans) make sense of it?

One of my favorite example is the dimensionality of a line. We all remember from school that a line can be described using the equation y=ax+b. In short, a line can be described using two parameters: a & b. Now, imagine tilting your head such that the line rotates to be parallel with the ground (or: x axis). Now, you can describe the line using a single number: y=c (or: the height of the line parallel to the x axis).

This simple example illustrates that perspective or representation is key. If you look at the data the right way, a high dimensional state space becomes lower dimensional. And, in the lower dimension representation, problems are easier to solve, and it becomes possible to make sense of a high dimensional world.