次元の呪い

ひとことで言うと

次元の呪いとは、特徴量の次元 $d$ が増えるほど入力空間の広さと複雑さが急増し、データが空間を埋められなくなる現象です。データ数を増やさないまま特徴量だけを足すと、訓練例のない領域が増え、近くの例から一般化する前提も崩れます。

なぜ必要か

学習器は入力空間のどこで出力が変わるかを、観測した例から推定します。各特徴を少なくとも2区間に分けるだけでも、区別すべき組合せは $2^d$ 個です。したがって、各領域に例を1つ置くという単純な基準でさえ、必要な例数は次元に対して指数的に増えます。実際には領域ごとの境界やノイズも推定するため、同じデータ数で次元だけを増やすと、訓練データがある部分だけに適合し、未観測部分の予測が不安定になります。

これは「特徴量が多いほど情報が増える」という直感と衝突します。情報を追加しても、学習に必要な組合せの数がそれ以上の速さで増えれば、データ密度は下がります。正則化や特徴選択はこの負担を抑える手段ですが、入力の表現そのものに構造を持たせる方法もあります。

区間数を2に固定した場合の増え方は次の通りです。

次元 $d$	区画数 $2^d$
2	4
10	1,024
20	1,048,576

仕組み

各次元を $m$ 個の区間に分けると、空間の区画数は

$$N_{\mathrm{regions}} = m^d$$

です。ここで $d$ は特徴量の次元、$m$ は1次元あたりの区切り数、$N_{\mathrm{regions}}$ は区画数です。総サンプル数を $n$ とすると、区画あたりの平均サンプル数は

$$\bar{n} = \frac{n}{m^d}$$

となり、$d$ が1増えるたびに $m$ 分の1になります。各区画を個別に覚えるモデルなら、未観測区画の値を根拠なく補うことになります。さらに高次元では、最も近い点でさえ全体の広がりに対して十分近いとは限らず、「近い」という局所性が弱まります。ここでは距離計算の手順ではなく、空間が疎になることが本質です。

深層学習では、入力をそのまま区画ごとの記号として扱わず、複数の特徴が組み合わさる分散表現へ写します。少数の特徴の組合せで多くの領域を区別できるため、必要な表現の数を入力次元に対して効率よく増やせます。分散表現の構成自体は別の論点ですが、次元の呪いに対する接続はここです。

試験でどう問われるか

問われ方	正解に寄る条件	引っかけ
次元増加の影響	区画数・組合せ数が指数的に増え、データが疎になる	データの情報量が単純に増えるだけとする
サンプル数の説明	同じ密度を保つには次元に応じて例数も増やす	例数を少し増やせば十分とする
距離の直感	距離の差が相対的に小さくなり、局所性が弱まる	高次元ほど必ず分類精度が上がる
深層学習との接続	分散表現が特徴の組合せで多くの領域を表す	分散表現は次元を必ず削減する、と断定する

実装で確かめる

区間数を固定したとき、次元の増加だけで区画数と平均密度がどう変わるかを確認します。

import numpy as np

n, bins = 100_000, 4
for d in (2, 4, 8, 12):
    regions = bins ** d
    print(d, regions, n / regions)

出力は 2 16 6250.0、4 256 390.625、8 65536 1.52587890625、12 16777216 0.0059604644775390625 です。サンプル数は変わらないのに、区画あたりの平均例数が急減します。これはモデルの優劣を測る実験ではなく、空間を局所的に埋める前提がどこで破綻するかを見る計算です。

取り違えやすいもの

用語	切り分け
過学習	次元の呪いはデータ密度が下がる問題。過学習は観測例への適合が強すぎる問題で、前者が後者を招くことがある
次元削減	座標の数を減らす操作。次元の呪いそのものではなく、負担を減らす対策の一つ
疎性	空間の大部分に例がない状態。高次元化で生じる観測上の帰結
分散表現	複数の特徴を共有して領域を表す表現。次元の呪いを緩める設計上の接続

想起チェック

次元が1増えると、区画数はどう変わるか

1次元あたり $m$ 区間なら、区画数は $m^d$ なので $m$ 倍になります。サンプル数を固定すれば、区画あたりの平均例数は $1/m$ になります。

次元の呪いの中心を「計算量が増える」とだけ説明してよいか

不十分です。中心は区画や組合せが指数的に増え、観測例が空間を埋められず、局所的な一般化の根拠が薄くなることです。

分散表現は何を共有することで負担を緩めるか

特徴を組合せて複数の領域を表し、領域ごとに独立した記号やパラメータを置く必要を減らします。