パターン認識と機械学習の勉強ノート【1.4 次元の呪い】

こちらの『パターン認識と機械学習』を読んで，勉強したことをまとめていきます．

リンク

前回は，1.3節のモデル選択についてまとめました．

今回は，1.4節の次元の呪いです．

次元の呪いとは
状態の数（場合の数）が爆発的に増加する
高次元空間ではデータはどう分布するか
1. 高次元球では，中身がスカスカになる
高次元空間に対する実用的な考え方
まとめ

次元の呪いとは

次元の呪いとは，

『取り扱う空間の次元が大きくなると，様々な不都合なことが起きてしまう問題』

のことを指します．

以降では，この「不都合なこと」についていくつか述べていきます．

状態の数（場合の数）が爆発的に増加する

次元Dが増加すると，考えなければならない状態の数は指数的に増加します．

上の図で行くと，D＝1次元のときは一つの軸に対して3つの状態しかなくても，

D＝2次元になると，状態数は3×3＝9個になります．

また，D=3次元になると，立方体を考えれば状態数は3×3×3＝27個になります（上の図の個数を考えるのが面倒なので立方体にしました）．

つまり，次元 $D$ に対して状態の数はざっくり $M^D$ で増加することになります． $M$ は一つの軸に対する変数の自由度です．例えば，サイズを小，中，大で分割すると， $M=3$ です．

次に，似たような説明になりますが，多項式フィッティングの例を使って説明します．

$x$ に対して3次の多項式

$y(\mathbf x, \mathbf w) = w_{0}+\sum_{i=0}^{D}w_{i}x_{i} +\sum_{i=0}^{D}\sum_{j=0}^{D}w_{ij}x_{i}x_{j} +\sum_{i=0}^{D}\sum_{j=0}^{D}\sum_{k=0}^{D}w_{ijk}x_{i}x_{j}x_{k}$

を，色々な次元 $D$ で考えてみます．

以下のように，M次の係数の数は $D^M$ で増加します．

$D=1$ のとき，

$y(\mathbf x, \mathbf w) = w_{0}+w_{1}x_{1} +w_{11}x_{1}x_{1} +w_{111}x_{1}x_{1}x_{1}$

例えば，3次の項の係数は1個．全部で4個の係数

$D=2$ のとき，

$y(\mathbf x, \mathbf w) =w_{0}+w_{1}x_{1}+w_{2}x_{2}+w_{11}x_{1}x_{1}+w_{12}x_{1}x_{2}+w_{21}x_{2}x_{1}+w_{22}x_{2}x_{2}+w_{111}x_{1}x_{1}x_{1}$

$+w_{112}x_{1}x_{1}x_{2}+w_{122}x_{1}x_{2}x_{2}+w_{222}x_{2}x_{2}x_{2}+w_{121}x_{1}x_{2}x_{1}+w_{221}x_{2}x_{2}x_{1}+w_{211}x_{2}x_{1}x_{1}+w_{212}x_{2}x_{1}x_{2}$

例えば，3次の項の係数は $2^{3}=8$ 個．全部で15個の係数

このように，次元が増えると係数が増え，特徴を探すことが困難になります（機械学習において係数は特徴付けをするものです）．

高次元空間ではデータはどう分布するか

高次元になると起こる問題として，あまりにも高次元になると『データの次元が実質的に一つ落ちてしまう』ことがあります．

一見，次元が落ちるのでいいことのように思えますが（ときには本当にいいことかもしれない），この人間の直感にはよくわからないことは，人間によるデータ分析の妨げになることがあります．

高次元球では，中身がスカスカになる

以降で説明するように，３次元の球の体積は半径の3乗に比例しますが，もっと高次元なN次元球の体積は，球の表面に密集し，半径のN-1乗に近くなります．

まず， $N$ 次元球の体積は，以下の式で求められます．

$N$ 次元球の体積

$V_N(r)=\frac{\pi^\frac{N}{2}}{\Gamma(\frac{N}{2}+1)}r^{N}$

$r$ は半径です． $\Gamma(a)$ はガンマ関数ですが， $r$ によらないので，今は定数だと思っておいてください．

ガンマ関数： $\Gamma(z) = \int_{0}^{\infty}t^{z-1}e^{-t}dt$

この体積の式の導出は，よく知られたものなので調べればすぐに出てきますから，ここでは省略します．

ちなみに，球の表面積 $S_N(r)$ は体積を $r$ で微分したものなので，

$S_N(r) = \frac{dV_N(r)}{dr} = N\frac{\pi^\frac{N}{2}}{\Gamma(\frac{N}{2}+1)}r^{N-1}$

です．

例えば，3次元の場合は， $V_3(r)=\frac{4}{3}\pi r^{3}$ ， $S_3(r)=4\pi r^{2}$ と，見慣れたものになります．

とにかく，N次元球の体積は $r^N$ に比例し，N次元球の面積は $r^{N-1}$ に比例することが分かればOKです．

さて，N次元球の体積の表面の性質についてみることにします．

N次元球の半径が $\delta r$ だけ減った，半径 $r - \delta r$ の球の体積 $V_N(r - \delta r)$ を考えると，半径 $r$ の球の体積 $V_N(r)$ の差 $V_N(r)-V_N(r - \delta r)$ は， $\delta r$ の厚さを持った球殻の体積になります．