高次元のデータを扱うとき、「近い/遠い」という感覚は当てにならなくなる、とよく言われる。k近傍法(k-NN)のような距離ベースの手法が高次元で弱くなる理由としてよく引き合いに出される話で、直感的には「次元が増えるほど、一番近い点と一番遠い点の差がほとんど無くなってしまう」というものだ。

よく聞く話ではあるが、自分の手で数字を出したことは一度もなかった。今回はこれを実際に測ってみる。

実験に使ったコードの全文はGitHubに置いています。

実験の設計: [0,1]^d の中に2000点、原点からの距離を測る

やることはシンプルだ。$d$次元の単位超立方体 $[0,1]^d$ の中に、一様分布からN=2000点をランダムに生成する。基準点(クエリ点)は原点 $\mathbf{0}$ に固定し、そこから2000点それぞれまでのユークリッド距離を計算する。

import numpy as np

def distances_from_origin(d, N, seed):
    rng = np.random.default_rng(seed)
    pts = rng.uniform(0, 1, size=(N, d))
    query = np.zeros(d)  # 原点
    return np.linalg.norm(pts - query, axis=1)

言葉とコードだけだとイメージしづらいので、$d=2$の場合(=単位正方形)について、この設定をそのまま絵にしてみた。

基準点の原点は、正方形の「角」にあたる位置だ。この2000点の中には、たまたま原点のすぐそばに落ちた点があって、そこまでの距離が0.017。一番遠い点はほぼ対角の角のあたりに落ちていて、距離1.405。この2つの比が、タイトルにある「82倍」の正体だ。次元を上げても、やることはこの絵の距離測定をそのまま$d$次元に拡張するだけ——$[0,1]^d$の角(原点)から、超立方体の中に散らばった2000点までの距離を測る。

この距離の集合について、2つの指標を見る。

• 最大距離/最小距離の比: 「一番遠い点」と「一番近い点」がどれだけ違って見えるか。1に近づくほど、近傍も遠傍も区別がつかなくなる
• 変動係数CV(=標準偏差/平均): 距離の散らばりが、平均距離に対して相対的にどれだけ大きいか

次元数 $d$ を 2, 3, 5, 10, 20, 50, 100, 300 と振って、seed=42で1回ずつ計算した。下の表で報告するのはこの代表8点だが、折れ線グラフとGIFではこの間を対数刻みで埋めた計25通りの$d$についても同じ計算をしている。

結果: 比は82倍→1.21倍、CVは0.381→0.026まで縮んだ

実測した値がこちら。

    d        max        min       mean        std      ratio         cv
    2     1.4048     0.0171     0.7616     0.2903   82.35899    0.38121
    3     1.6622     0.0768     0.9513     0.2806   21.64246    0.29494
    5     2.0454     0.3326     1.2563     0.2694    6.14946    0.21443
   10     2.5903     0.8451     1.8065     0.2638    3.06497    0.14602
   20     3.3662     1.4901     2.5730     0.2620    2.25902    0.10181
   50     4.9774     3.1482     4.0773     0.2634    1.58103    0.06461
  100     6.6850     4.8848     5.7675     0.2592    1.36853    0.04495
  300    11.0639     9.1486     9.9905     0.2598    1.20935    0.02601

$d=2$ では最大距離1.40、最小距離0.017で比は82.36倍。ところが $d=300$ まで上げると最大11.06、最小9.15で比は1.21倍まで潰れる。CVも0.381から0.026まで、ほぼ1桁縮んだ。教科書でよく言われる「高次元では距離が均される」という話は、少なくともこの設定では素直にその通りだった。

図をよく見ると、赤い比の折れ線は$d=10$〜$20$付近などで小さく上下に揺れていて、厳密には単調に下がっていない(青いCVの線には、この揺れがない)。実はこれは作図の粗さではなく、比という指標の性質が既にここで顔を出しているのだが、その話は後半で詳しく見る。

見落としがちな点: 「距離が縮む」わけではない

ここで表のstd列(標準偏差)を見てほしい。$d=2$で0.2903、$d=300$で0.2598と、ほとんど変わっていない。次元を150倍にしても、距離のばらつき自体(絶対値)はさほど縮んでいないのだ。

縮んでいるのはmean(平均距離)に対する相対的な散らばり、つまりCVの方だ。$d=2$では平均0.76に対して標準偏差0.29(CV=0.38)というかなり目立つ散らばりだったのが、$d=300$では平均9.99に対して標準偏差0.26(CV=0.026)と、同じくらいの絶対的なばらつきが平均の陰に埋もれてしまう。

つまり「高次元では点同士が接近する」のではなく、「平均距離がどんどん伸びる一方で、散らばりの絶対量はほぼ据え置きなので、相対的に見れば誤差みたいなものになる」というのが正確な描写だ。この違いは、実際にstd列を並べて見るまで自分でも意識していなかった。

平均で正規化して重ねると一目瞭然で、$d=2$(赤)は0〜1.8倍まで横に広がった低い山なのに対し、$d=300$(青)は0.9〜1.1倍というごく狭い範囲に尖った山として収まっている。

GIFで、次元を上げていく過程を見る

$d$を2から300まで対数刻みで動かしながら、同じ正規化ヒストグラムがどう潰れていくかをアニメーションにした。

$d=10$あたりまでは目に見えて幅が狭まっていくが、$d=50$を過ぎると幅の方はほとんど動かなくなる(その後も山の高さだけは伸び続ける——同じ2000点がどんどん少数のビンに詰め込まれていくためで、ピークのビンの点数は$d=56$で約740点、$d=300$で約1150点になる)。「近い/遠いの区別が潰れる」という効果自体は低い次元の間にほとんど出てしまい、そこから先は「もう十分潰れているものが、さらにわずかに潰れる」だけになる印象だった。

正直に書く: 「比」はseedを変えるとかなり暴れる

ここまでは1回のseed(42)で計算した数字だった。もう少し慎重になろうと、同じ実験をseedだけ0〜9の10通りに変えて繰り返してみた。結果は予想より荒れた。

d=2:   ratio min=34.17  max=311.22  mean=130.30  |  cv min=0.3598 max=0.3826 mean=0.3709
d=3:   ratio min=10.90  max=43.07   mean=18.66   |  cv min=0.2809 max=0.2973 mean=0.2888
d=5:   ratio min=5.21   max=13.27   mean=7.71    |  cv min=0.2127 max=0.2207 mean=0.2161
d=10:  ratio min=2.75   max=3.79    mean=3.20    |  cv min=0.1414 max=0.1517 mean=0.1466
d=300: ratio min=1.18   max=1.21    mean=1.20    |  cv min=0.0252 max=0.0267 mean=0.0260

$d=2$では、最大/最小比がseedによって34.17倍から311.22倍まで、実に9倍近い開きが出た。最初に報告した「82.36倍」は、この広い分布のたまたま真ん中寄りの1点に過ぎなかったわけだ。一方でCVの方は$d=2$でも0.3598〜0.3826と、狭い範囲にきちんと収まっている。

理由を考えると納得はいく。最大/最小比は2000点のうちのたった2点(一番近い点と一番遠い点)という極値だけで決まる指標なので、たまたま原点のすぐそばに1点でも落ちれば比は跳ね上がる。低次元ほど「たまたま近い1点」が起きやすく、2000点程度のサンプルサイズでは運の影響をまともに受ける。一方CVは2000点全部を使った要約統計量なので、1点2点の極端な当たり外れに引きずられにくい。

参考までに、基準点を原点ではなく中心 $(0.5,\dots,0.5)$ や、ランダムに選んだ別の1点にしても、傾向自体(次元が上がるほど比・CVとも縮む)は変わらなかった($d=2$で比44.8〜116.7倍、$d=300$で比1.20〜1.23倍、CVも同程度の範囲)。「原点を選んだから起きた」現象ではなさそうだ。

「次元の呪いで距離が均される」という結論自体は今回もしっかり再現されたが、それを1個の比の数字だけで語ると、たまたま引いたサンプル次第でかなり違う印象を与えかねない、というのが動かしてみて初めて分かった注意点だった。CVのようなサンプル全体を使う指標と併せて見ることの大切さを実感した。

手を動かして意外だったこと

一番意外だったのは、教科書的な「次元の呪い」自体は素直に再現された一方で、それを測る指標の選び方でこんなに印象が変わることだった。「最大/最小比が82倍から1.21倍に縮んだ」と1回のseedだけで言い切ってしまうと、それらしく聞こえるが実は数字の桁が運次第で変わりうる、危うい報告になる。距離ベースの手法(k-NN など)が高次元で弱くなるという話も、根っこにあるのはこの「近傍も遠傍もほとんど同じ距離になる」現象そのものだが、それをどの指標でどう測るかによって、話の説得力が変わってしまう危うさを持っている。

これは仕事の意思決定にも通じる気がした。選択肢を比べるときに条件(評価軸)を増やしすぎると、どの選択肢も「総合的にはだいたい同じくらい良さそう/悪そう」に見えてくることがある。高次元空間で全部の点が原点からほぼ同じ距離になってしまうのと同じで、判断材料(次元)を増やしすぎると、選択肢同士の「本当の距離」が埋もれて見えなくなる。逆に言えば、比較したいなら評価軸を絞り込んで、少数の鋭い基準で測り直す方が、選択肢の間の実質的な違いがちゃんと「距離」として戻ってくるのだと思う。次元を増やすことは情報を増やすことではあるけれど、判断のための「距離感」を保つには、時々は次元を削る勇気の方が要るのかもしれない。

まとめ

• $[0,1]^d$ に一様分布させた2000点について、原点からの距離の最大/最小比を$d=2,3,5,10,20,50,100,300$で測定。比は82.36倍→1.21倍、変動係数CVは0.381→0.026まで、どちらもほぼ単調に収束した(細かい対数刻みで見ると、比の方だけは途中で小さく上下する)
• 標準偏差(std)自体は$d=2$の0.2903から$d=300$の0.2598までほぼ横ばい。「距離が縮む」のではなく、「平均距離が伸びる分、相対的な散らばり(CV)が縮む」というのが正確な描写だった
• 効果の大半は$d\lesssim50$までに出てしまい、それ以降(〜300)はすでに潰れたものがさらにわずかに潰れるだけだった
• 同じ実験を10通りのseedで繰り返すと、最大/最小比は$d=2$で34.17倍〜311.22倍と大きく暴れた一方、CVは0.3598〜0.3826とほぼ動かなかった。極値2点だけで決まる比は低次元・少サンプルではかなり運任せになる、というのが実測して初めて分かった注意点
• 基準点を原点・中心・ランダムな点のいずれにしても、傾向自体(次元が上がるほど比・CVとも縮む)は変わらなかった

• 実践記
• 次元削減

関連記事

• テセラクトの影で何が失われるか。4次元超立方体を2次元に潰したら、PCAがランダム射影200本の全部に負けた
• ランダムに撒いた400点を「自分の縄張りの重心」へ動かし続けたら、六角形の割合が31.4%から69.2%になった
• ヒルベルト曲線は「近さを保つ」と言われるが、平均で見ると行優先に負けた（155.6 対 128.5）

このブログでは、機械学習の仕組みを実際にコードで実装して確かめた実験をテーマ別に整理しています（拡散モデル・Transformer・強化学習・多様体学習・過学習など）。