The Curse of Dimensionality¶
A hypercube with side length 1, in d dimensions is defined to be the set of points (x1, x2, ..., xd) such that 0 <= xj <= 1 for all j = 1, 2, ..., d. The boundary of the hypercube is defined to be the set of all points such that there exists a j for which 0 <= xj <= 0.05 or 0.95 <= xj <= 1 (namely, the boundary is the set of all points that have at least one dimension in the most extreme 10% of possible values). What proportion of the points in a hypercube of dimension 50 are in the boundary?
In [10]:
import seaborn as sns
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
def proportion_in_boundry(bndry, dim):
return 1 - (1 - bndry) ** dim
# Answer
print('Answer: {}'.format(np.around(proportion_in_boundry(0.1, 2), decimals=3)))
# Chart of proportion in a 10% boundry with exponents 1 - 50.
x = pd.Series(np.arange(1,50))
y = pd.Series([proportion_in_boundry(0.1, dim) for dim in x])
df = pd.DataFrame([x,y], index=['dimension', 'proportion located in most extreme 10% of volume']).T
_, ax = plt.subplots(figsize=(20,10))
sns.lineplot(ax=ax, x='dimension', y='proportion located in most extreme 10% of volume', data=df)
Answer: 0.19
Out[10]:
<matplotlib.axes._subplots.AxesSubplot at 0x117181710>
