Does "curse of dimensionality" really exist in real data?

Question

I understand what is "curse of dimensionality", and I have done some high dimensional optimization problems and know the challenge of the exponential possibilities.

However, I doubt if the "curse of dimensionality" exist in most real world data (well let's put images or videos aside for a moment, I am thinking about data such as customer demographic and purchase behavior data).

We can collect data with thousands of features but it is less likely even impossible the features can fully span a space with thousands of dimensions. This is why dimension reduction techniques are so popular.

In other words, it is very likely the data does not contain the exponential level of information, i.e., many features are highly correlated and many features satisfy 80-20 rules (many instances have same value).

In such a case, I think methods like KNN will still work reasonably well. (In most books "curse of dimensionality" says dimension > 10 could be problematic. In their demos they use uniform distribution in all dimensions, where entropy is really high. I doubt in real world this will ever happen.)

My personal experience with real data is that "curse of dimensionality" does not affect template method (such as KNN) too much and in most cases, dimensions ~100 would still work.

Is this true for other people? (I worked with real data in different industries for 5 years, never observed "all distance pairs have similar values" as described in the book.)

Answer 1

This paper(1) discusses the blessing of non-uniformity as a counterpoint to the curse of dimensionality. The main idea is that data are not uniformly dispersed within the feature space, so one can gain traction by identifying the ways in which the data are organized.

(1) Pedro Domingos, "A Few Useful Things to Know about Machine Learning"

Answer 2

Curse of dimensionality in machine learning is more often the problem of exploding empty space between the few data points that you have. Low manifold data can make it even worse. Here is an example setup with 10000 samples where I try to do kNN with 1 neighbor.

from numpy.random import normal
from sklearn.neighbors import KNeighborsClassifier
from sklearn.metrics import precision_score
import matplotlib.pyplot as plt
import numpy as np
from math import sqrt
from scipy.special import gamma

N=10000
N_broad=2
scale=20

dims=[]
precs=[]


def avg_distance(k):
    return sqrt(2)*gamma((k+1)/2)/gamma(k/2)

for dim in range(N_broad+1,30):
    clf = KNeighborsClassifier(1, n_jobs=-1)

    X_train=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_train=(X_train[:,N_broad]>0).astype(int)
    clf.fit(X_train, y_train)

    X_test=np.hstack([normal(size=(N,N_broad)), normal(size=(N,dim-N_broad))/avg_distance(dim-N_broad)/scale])
    y_test=(X_test[:,N_broad]>0).astype(int)
    y_test_pred=clf.predict(X_test)

    prec=precision_score(y_test, y_test_pred)
    dims.append(dim)
    precs.append(prec)
    print(dim, prec)

plt.plot(dims, precs)
plt.ylim([0.5,1])
plt.xlabel("Dimension")
plt.ylabel("Precision")
plt.title("kNN(1) on {} samples".format(N))
plt.show()

You didn't like fully uniform distributions, so I've made this a 2D manifold with smaller dimensions (reduced by scale) sprinkled around the 2D plane of the first two coordinates. As it happens, one of the smaller dimensions is predictive (the label is 1 when that dimension is positive).

The precision drops rapidly with increasing dimension.

Of course, precision=0.5 would be random guessing. With a decision surface, which is more complicating than a plane, it would get even worse.

It's like the kNN balls are too sparse to be helpful at probing a smooth hyperplane. With higher dimensions they feel increasingly more lonely.

On the other hand, methods like SVM have a global view and do much better.

Answer 3

Consider for example time series (and images, and audio). Sensor readings (Internet of Things) are very common.

The curse of dimensionality is much more common than you think. There is a large redundancy there, but also a lot of noise.

The problem is that many people simply avoid these challenges of real data, and only use the same cherryupicked UCI data sets over and over again.

Answer 4

There is a wonderful article, "Statistical Modeling: the two cultures", by Breiman. He explains the two groups of scientists who deal with data and how each of them look at "dimensionality". The answer to your question is "it depends" in which group you are. Check the paper out.