次元の呪い

はじめに

　今回は、「次元の呪い」に関連した3つの話題を解説する。

次元の呪いとは？

　次元の呪い（The curse of dimensionality）とは、次元数を高くしたとき、3次元までの常識からは予想できない特異な振る舞いが出現することである。リチャード・ベルマン（強化学習で有名なベルマン方程式のひと）が1957年の論文で初めて使った概念である。以下3つの具体例で見られる高次元の特異な振る舞いを解説する。

  1. 高次元空間における球の体積と表面積の比
  2. 高次元空間における球の体積と球に外接する立方体の体積の比
  3. 高次元正規分布

高次元空間における球の体積と表面積の比

　最初に、2次元空間内の半径rの円を考える。このとき、円周S_2(r)と面積V_2(r)は次式で与えられる。

(1)   \begin{eqnarray*} S_2(r)&=&2\pi r \\ V_2(r)&=&\pi r^2 \end{eqnarray*}

次に、3次元空間内の半径rの球の表面積S_3(r)と体積V_3(r)を考える。

(2)   \begin{eqnarray*} S_3(r)&=&4\pi r^2 \\ V_3(r)&=&\frac{4}{3}\pi r^3 \end{eqnarray*}

一般に、D次元空間における球（これを超球と呼ぶ）の表面積S_D(r)と体積V_D(r)は次式で与えられる。

(3)   \begin{eqnarray*} S_D(r)&=&C_{D} r^{D-1} \\ V_D(r)&=&\frac{C_D}{D}r^D \end{eqnarray*}

ここで、C_{D}は定数であり、C_{2}=2\pi、C_{3}=4\piである。C_Dの正確な表式は、例えばBishop本の演習問題に掲載されている。表面積と体積の比を取ると次式を得る。

(4)   \begin{equation*} \frac{V_D(r)}{S_D(r)}=\frac{r}{D} \end{equation*}

したがって、D\rightarrow \inftyのとき、式(4)の右辺は0になる。すなわち、次元が高くなるほど体積よりも表面積からの寄与が大きくなるのである。このことはよく、次のように例えられることが多い。

高次元空間におけるメロンパンは表面のカリカリ部分が多くなり嬉しいが、高次元空間におけるシュークリームはクリームが減ってしまい残念である。

高次元空間における球の体積と球に外接する立方体の体積の比

　最初に2次元空間を考える。半径rの円の面積V_2(r)と円に外接する正方形の面積V_2^c(r)は次式で与えられる。

(5)   \begin{eqnarray*} V_2(r)&=&\pi r^{2} \\ V_2^c(r)&=&(2r)^2 \end{eqnarray*}

次に、3次元空間を考える。半径rの球の体積V_3(r)と球に外接する立方体の体積V_3^c(r)は次式で与えられる。

(6)   \begin{eqnarray*} V_3(r)&=&\frac{4}{3}\pi r^{3} \\ V_3^c(r)&=&(2r)^3 \end{eqnarray*}

一般に、D次元空間における立方体（これを超立方体と呼ぶ）の体積V_D^c(r)は次式で与えられる。

(7)   \begin{equation*} V_D^c(r)=(2r)^D \end{equation*}

したがって、球と立方体の比は次式で与えられる。

(8)   \begin{equation*} \frac{V_D(r)}{V_D^c(r)}=\frac{C_D}{2^{D}D} \end{equation*}

D\rightarrow \inftyのとき、式(8)の右辺は0になることを示すことができる（証明はBishop本の演習問題にある）。すなわち、高次元空間においては、球の体積の寄与が減るのである。

高次元空間では、箱に入れられた高級メロンはとても小さい。

さて、球の中心（立方体の中心でもある）から立方体の1つの角までの距離は\sqrt{r^{2}D}であるから（下図参照）、

球の半径rとの比をとると

(9)   \begin{equation*} \frac{\sqrt{r^{2}D}}{r}=\sqrt{D} \end{equation*}

となる。D\rightarrow \inftyのとき、式(9)の右辺は\inftyになる。すなわち、高次元空間における立方体の角は刺のように鋭く（スパイク状に）伸びていることになる。また、立方体の角の数は2^Dであるから、D\rightarrow \inftyのとき、角の数も\inftyになる。

高次元空間での立方体の形状は雲丹である。

ここで、モンテカルロ法を用いた\piの算出手順を紹介したい。図のような半径1の扇形を考え、以下の手順を行うことで\piの近似値を得ることができる。

  1. 変数sを0で初期化する。
  2. [0,1]の間の実数値を生成する乱数器を用いて座標(x,y)を作る。
  3. この座標が扇形内(x^2+y^2\leq 1,x\geq 0,y\geq 0)にあればsに1を加算する。
  4. この手順を適当な回数Nだけ繰り返す。
  5. 最後にs/Nを4倍すれば\piの近似値を得る。

ここで行っていることは、正方形内に生成した座標のうち、扇形内にある点だけを選ぶことである。これを高次元空間で考えた場合どうなるか。既に見たように高次元では、立方体（超立方体）に占める球（超球）の体積の割合は小さくなる。つまり、高次元になるほど、乱数で生成した座標が球内に収まる確率が小さくなっていくことになる。言い換えると、精度良く\piを求めるのに必要な座標の数が多くなっていくことになる。この現象は、次元の呪いが数値計算に及ぼす悪影響として良く取り上げられる。

高次元正規分布

　ここでは、高次元正規分布の振る舞いを見る。いま、D次元の等方的な正規分布を考える。

(10)   \begin{equation*} p_D(x)=\frac{1}{(2\pi\sigma^2)^{D/2}}\exp{\left(-\frac{\|x\|^2}{2\sigma^2}\right)} \end{equation*}

ただしx\in\mathbb{R}^Dである。このとき、確率分布p_D(x)の下での、ある量f(x)の期待値E[f]は次式で与えられる。

(11)   \begin{equation*} E[f]=\int dx f(x)p_D(x) \end{equation*}

積分範囲は全空間である。ここで、極座標変換を行う。f(x)が中心からの距離rだけに依存する場合、上式は以下のように変形することできる。

(12)   \begin{eqnarray*} E[f]&=&\int_0^{\infty} dr f(r)q_D(r) \\ q_D(r)&=&\frac{C_D\;r^{D-1}}{(2\pi\sigma^2)^{D/2}}\exp{\left(-\frac{r^2}{2\sigma^2}\right)} \end{eqnarray*}

C_Dは既出の定数である。ここで、関数q_D(r)に指数函数だけでなく、D-1次の項（r^{D-1}）が現れることが重要である（この事実は、極座標変換を行ったときf(x)が角度依存性も持つ場合でも成り立つ）。関数q_D(r)の様子を下に示す。

Dが大きくなるに従い、極大値の位置が中心から離れていくことが分かる。極大値の位置\hat{r}はq_D(r)を微分すれば容易に求めることができ、\hat{r}=\sqrt{D-1}\sigmaとなる。以上の事実を踏まえて期待値の式

(13)   \begin{equation*} E[f]=\int_0^{\infty} dr f(r)q_D(r) \end{equation*}

を眺めると、次元が高くなるほどf(r)の中心近傍の振る舞いが結果に反映されなくなることが分かる。この現象は、既に見た球の体積と表面積の関係や、球と立方体の体積の関係とよく似ている。高次元ほど、中心ではなく端の影響が大きくなるのである。

高次元正規分布は半径\hat{r}の超球の表面にへばりついた分布になる。

このことは、高次元正規分布を用いてサンプルされる点のほとんどは、球の表面近傍の点であると表現することもできる。これはモンテカルロ法などサンプリングを必要とする数値計算を行うときに注意しなければならない点である。

まとめ

　今回は、高次元空間では直観とは異なる現象が起きていることを見た。球の表面積と体積の関係や、立方体と球の体積の関係で解説したように、高次元空間内の点は、そのほとんどが中心から離れた薄い皮の表面にへばりつくように分布する。この事実が計算効率を落としたり、精度を維持するために膨大な数のデータ（空間内の点に対応する）を必要とする原因となる。同じ現象が正規分布でも起きていることを示した。機械学習や深層学習では高次元ベクトルを当たり前のように扱うが、「次元の呪い」があることに留意しなければならない。

Kumada Seiya

Kumada Seiya

仕事であろうとなかろうと勉強し続ける、その結果”中身”を知ったエンジニアになれる

最近の記事

  • 関連記事
  • おすすめ記事
  • 特集記事

アーカイブ

カテゴリー

PAGE TOP