The Curse of Dimensionality: Demonstsration Programs

The Curse of Dimensionality

Python scripts for demonstration

Python scripts in this website demonstrate two phenomena, known as the curse of dimensionality. One treats distribution of points, and the other distances of points.

Distribution of Points

As number of dimensions increases, uniformly distributed points gather near the boundary walls. To observe this phenomenon, points were randomly sampled from a d-dimensional cube, where s were independently distributed with uniform distribution . Then, proportion of points, which have at least one coordinate with or , is calculated. The Python script is like this:

import numpy as np

import numpy.random as nr

import matplotlib.pyplot as plt

def check(v):

ck = 0

for t in v:

if t < 0.1 or t > 0.9:

ck = 1

return ck

n = 10000

p_ck = []

p_model = []

d_range = [1, 2, 3, 5, 10, 25, 50]

for d in d_range:

data = nr.rand(n, d)

counts = np.array([check(v) for v in data])

p_ck.append(counts.mean())

print(d, p_ck[-1])

p_model.append(1.0 - 0.8**d)

plt.plot(d_range, p_ck, 'b-', linewidth = 2, label = 'Simulation')

plt.plot(d_range, p_model, 'g--', linewidth = 3, label = 'Model')

plt.xlabel('Number of Dimensions', fontsize = 14)

plt.ylabel('Prob. of being near-wall', fontsize = 14)

plt.legend(loc = 'lower right', fontsize = 16)

plt.show()

Executing this script, we have Figure 1.

Figure 1

The abscissa represents number of dimensions, and the ordinate represents the proportion, i.e., estimated probability, of the points that were near a boundary wall.

The model, which estimates the probability that a point is near a boundary wall, is as follows:

This probability can be calculated by first calculate probability that a point is not near the boundary wall.

For uniform distribution , probability of coordinate is not near the boundary points 0 or 1 is given by

Hence, probability that a point is not near the boundary wall is given by

because coordinates are independently distributed.

The probability that a point is near a boundary wall is calculated as the probability of the complimentary events of that of being not near a boundary wall, that is, by this:

Distances between Points

As number of dimensions increases, an average distance between points distributed uniformly also increases. To observe this phenomenon, points were sampled from uniform distribution in d-dimensional unit cube, and average distance was calculated. The script for this calculation is this:

import numpy as np

import numpy.random as nr

import matplotlib.pyplot as plt

n = 1000000

d_range = [1, 2, 3, 5, 10, 25, 50]

d_sqr_model = []

d_sqr_ck = []

d_sqrt = []

for d in d_range:

data1 = nr.rand(n, d)

data2 = nr.rand(n, d)

sqr_m = ((data1 - data2) ** 2).sum(axis = 1).mean()