次元の呪いデモプログラム

次元の呪い（The curse of dimensionality）と呼ばれている高次元空間における現象があるが、デモ用プログラムを点の分布に関するもの、および距離に関するものをPythonで作成してみた。

一様分布する点の配置が、次元を上げていくと壁に近いものが増加するという現象が指摘されている。この現象を確認するために、次元数の空間において点の各座標値が独立に一様分布に従うようにサンプリングを行った。いずれかの座標値が壁から0.1以内、すなわちまたはのとき、壁に近いと見なし、その比率を数えるプログラムを以下のように作成した。

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()

実行すると図１の結果を得る。

図１

横軸が次元数、縦軸が点の位置が壁に近い確率である。シミュレーションは点を一様乱数により発生して、壁に近いものの比率を数えたものであるが、モデルは以下のように導かれる。

点が壁の近くにある確率は、まず点が壁から離れた位置にある確率を求めて、その補事象の確率として求める。

点が壁から離れている確率は、各次元については

である。各次元の座標値が独立であるので、点が壁から離れている、すなわち各次元において端点から離れている確率の積

で与えられる。これより、点が壁の近くにある確率は

で与えられる。

距離

２点をランダムにとったとき、その距離は次元が高くなると増大する傾向にある。この現象を確認するために、次元数の空間において２点およびの各座標値およびが独立に一様分布に従うようにサンプリングを行った。サンプリングされた２点の距離および距離の２乗を求め、それぞれの平均値を算出し、グラフを描くプログラムを以下のように作成した。