Dimension reduction using space filling curve to avoid "Curse of dimensionality"?

Question

In machine learning, we want to train a model. While training, if the dimension of data is high, we have a problem (Curse of Dimensionality), so we want to reduce the dimension of our data.

Since we know $\mathbb{R}^n$ and $\mathbb{R}$ have the same cardinality. So we always have some space-filling curve that maps each point uniquely in both directions. i.e. we can always bijectively map any n-dimensional data to 1-dimension. So what is the problem we have in the first place?

I come up with two problems that can still be there:

1. With this space-filling curve map, we can't reduce the size of data. i.e., we have to increase the precision when we are writing it in 1-dimension.
2. This is the place where I have doubts. I am thinking that while representing data in $\mathbb{R}^n$ we have more information than representing it in $\mathbb{R}$. There is some structure when we write data in $\mathbb{R}^n$ like which point is near to which point. That is lost in this map (space-filling curve), i.e, the map is not homomorphic.

My question:

1. Is it right what I am thinking?
2. I don't know what information I am talking about in point 2. could you help me make it more rigorous is.
3. Is there any other problem?

Example:

Suppose we have a training data with $x^i \in \mathbb{R}^n $ with label $y^i \in \mathbb{R}$ where $i \in \{1,2,..,N\}$. When we are training a neural network to fit this data. If we change the order of the bases i.e.

$$x^i = (x_1^i,x_2^i,..,x_n^i)$$

if we take

$$\tilde{x}^i = (x_{\rho(1)}^i,x_{\rho(2)}^i,..,x_{\rho(n)}^i)$$

where $\rho$ is some permutation function(same for all $i$). then the training of neural network doesn't affect. So when order doesn't matter. What if I transform all the data from $\mathbb{R}^n$ to $\mathbb{R}$? It should also don't matter. But it did matter. Otherwise, there is nothing like the curse of dimensions.

I think When we transform the data from $\mathbb{R}^n$ to $\mathbb{R}$, we lose some information or do something wrong. What is that?

Answer 1

I think your intuition is right; moving from $\mathbb{R}^n$ to an affine parameter along a space-filling curve will discard information about what points are close to one another in the high-dimensional space. Points in the same neighborhood can be separated by arbitrarily large distances along the curve.

Consider, as an example, a problem where your prediction targets lie in a compact region in $\mathbb{R}^n$. Your machine learning task is to find a way to characterize that region. In the space-filling curve representation, the curve likely dips in and out of that region for an infinite number of ranges of the affine parameter $\lambda$. Finding these segments of the curve is not only much harder than finding the boundaries of the region in $\mathbb{R}^n$, it is likely impossible because you probably have arbitrary large $\lambda$ that lie in the region. Your generalization error will be terrible, since any new case that lies along a segment of the curve you haven't explored yet will generate a missed prediction, even if it differs imperceptibly from a training point in the $\mathbb{R}^n$ representation.

Dimension reduction does have a place in machine learning, but the trick is to discard dimensions that are not providing useful information for your prediction problem. Just forcing everything into one dimension using a construct like a space-filling curve doesn't accomplish that.

Answer 2

The problem of the curse of dimensionality is caused by the amount of data needed, in the worst case, to adequately represent the underlying distribution goes up exponentially in the number of features/attributes. Unfortunately using a space-filling curve to reduce the number of dimensions will not eliminate the curse of dimensionality. Consider a Gaussian distribution in a d-dimensional space, which could be described by a mean vector and a covariance matrix. This is a nice smooth and "simple" distribution. Now consider where the areas of high density would lie on the space-filling curve. Instead of one contiguous smooth distributions, there would now be exponentially (in the dimension of the original space) many bumps of high data density along the "string". We would still need exponentially large amounts of data to specify where along the "string" those bumps should be, and how high and how wide they would be. So sadly this approach is highly unlikely to work.

Answer 3

If you transform the data by some dimensional reduction then you will be affecting the distance metrics that you will be using implicitly in the higher dimensional training.

Try creating a 3d nearness metric from a 2d image - it's all distorted (see Fr Ted: "small, far away").

If you believe that all the N dimensions are useful, you could simply 'clump' the data based on clump size (a nearest neighbours metric over a reduced dimension, or a scaling matrix (eigenvalue/vectors), and either train each clump independently, or train against the clumps, depending on how the split happens/occurs/forced. I.e. something along the lines of the RVM/IVM approaches What is the difference between Informative (IVM) and Relevance (RVM) vector machines

Answer 4

This approach does work, to a degree, in low-dimensional $\mathbb{R}^n$ spaces, certainly in $\mathbb{R}^2$ and $\mathbb{R}^3$. A $k$-d tree is basically a data structure for ordering points along a space-filling curve.

The common reason why/when tree-based techniques work is because they turn a decision among $\mathcal{O}(m)$ choices into a sequence of $\mathcal{O}(\log m)$ decisions among $\mathcal{O}(n)$ choices. That's useful as long as $n\ll m$, but it becomes utterly counterproductive when $n$ is similar or bigger than $m$.

Oftentimes, the spaces for which the curse of dimensionality applies are not just high-dimensional, but conceptually infinite-dimensional, which makes a direct space-filling approach hopeless. Nevertheless, I wouldn't say it's completely futile to work in that direction, because even in such problems the data is in reality often confined to a finite-, perhaps even low-dimensional submanifold, and subdividing only that manifold in $k$-d fashion might well have its merits. The real problem is finding that manifold in the first place; that's what dimensionality reduction is all about.