アラフォーからの機械学習

アラフォーです。機械学習や統計学の解説記事を書いていきます

次元の呪いとはなにか

機械学習における「次元の呪い」とは高次元（特徴量の数が多い）のときに生じる問題のことです。ということなので、この特徴量の数を' $p$ 'という変数にして、増やしていったときにどのような事象が発生するのかを考えてみましょう。まず、各辺の長さが1であるp次元の単位超立方体を考えます。これはつまり、以下のような条件のデータです。

特徴量がp個であるデータ
各特徴量の値は[0, 1]の範囲に収まるように正規化されている

グラフ上にp次元で可視化していることと同じと考えて良いです。簡単のために、3次元（つまり特徴量が3つ）で可視化をした場合には下図のようになっています。

f:id:matakanobu:20200525120250p:plain

各辺は特徴量の軸と考えることができます。さて、この単位超立方体の中に小さな単位超立方体を作ります（右下の小さな立方体です）。これを「近傍」と呼びましょう。単位超立方体全体のデータ数に対する近傍のデータ数の割合を $r$ とします。このとき、この近傍の一辺の長さの期待値は

$e_p(r) = r^{1/p}$

になります。この期待値というのは各特徴量の近傍における範囲と考えてください。

これで説明の準備ができました。まずは低次元と言える2次元 $p=2$ から考えてみます。近傍に全データの1%( $r=0.01$ )、10%( $r=0.1$ )が入るとすると、

$e_{p=2}(r=0.01) = 0.01^{1/2} = 0.10 \\ e_{p=2}(r=0.1) = 0.1^{1/2} =0.32$

近傍に全データの1%が入る場合の各特徴量の取り得る範囲は10%、10%の場合は32%です。次は、高次元と言えるかどうかもありますが、10次元の場合も同様に計算してみます。

$e_{p=10}(r=0.01) = 0.01^{1/10} = 0.63 \\ e_{p=10}(r=0.1) = 0.1^{1/10} =0.80$

それぞれ、特徴量の63%、80%の範囲を近傍とみなすことになり、いずれも入力範囲の過半数以上であり、これはもはや近傍とは言いにくいです。近傍のデータ数を減らすことで特徴量の範囲を小さくすることができますが、分散が大きくなり推定値が安定しなくなります。

仮に、近傍における特徴量の範囲を2次元の時と同じくなるようにする（10%に収める）場合、近傍のデータ数の割合 $r$ は

$r^{1/10} = 0.1 \ ;\ r = 0.1^{10}$

となり、近傍に10個のデータを入れたいときに全体で必要となるデータ数は、

$データ数=\frac{10}{r} = \frac{10}{0.1^{10}} = 10^{11}$

です。よって膨大なデータ数を必要とします。これは高次元のデータでモデル化をするときに気をつけるべきということになりますが、この対応策については別の機会に説明してみます。

参考

統計的学習の基礎 ―データマイニング・推論・予測―