Python、機械学習

次元の呪いとは?説明変数が多すぎると、汎化性能が悪くなる。

説明変数は多ければ多いほどよいわけではありません。

説明変数が多すぎると、テストデータに対する予測精度が悪くなる(汎化性能が悪くなる)など、さまざまな問題が起こります。「次元の呪い」と呼ばれるものです。

「次元の呪い」とはどんなものなのでしょうか。

説明変数が多すぎると、データ空間がスカスカになる

説明変数が多い高次元の空間というのは、とにかく広大です。

例えば、将棋の世界は2次元です。9×9=81の碁盤目になっています。駒の数は全部で40個です。81のマス目のうち、40が駒で埋まっています。つまり、空間の充填率は約49%です。

これが3次元になったらどうでしょうか?1フロアしかなかった将棋盤が9フロアになり、9階建ての立方体になります。マス目は9x9x9=729になります。729のマス目のうち、40が駒で埋まることになりますので、充填率は約5%です。

マス目の住所も、2次元であれば「9六歩」で表せていましたが、3次元だと「9六Ⅲ歩」みたいになります。住所を示す数字がもう一つ増えます。

4次元だとマス目は6561、充填率は0.6%です。駒の数に対して空間が広がりすぎて、スカスカになることがよくわかると思います。

機械学習の文脈でいくと、マス目が空間、駒がデータ(プロット)です。駒が置いていないマス目がどうなるかを予測します。

2次元の場合、駒がないマス目がどうなるかを予測しやすいです。なぜなら、そのマス目の近くに駒があるからです。近くに「歩」が多ければ、そのマス目に入り得る駒も「歩」になるだろう、といった感じで予測できます。

高次元だとどうでしょうか。スカスカすぎて、近くに駒がいません。よって、そのマス目がどうなるか、予測するのが非常に難しいです。遠くにある駒を参考に、予測を試みることは可能ですが、当たる可能性は極めて低いでしょう。

予測したいマス目のほとんどが「外挿」領域になる、という言い方もできます。

一言で言うと、「説明変数が多い状態で機械学習をするのなら、空間がスカスカにならないよう、膨大なデータを準備しなければならない」ということです。

説明変数が多すぎると、空間が歪み、データが空間の「果て」に偏在する

空間がいがぐりのようなトゲトゲになる

2次元の将棋盤の世界では、形状は正方形で、空間の中心は「5五」になります。中心から空間の果て、つまり将棋盤の外周への距離感を見ると、一番近いのは各辺の中心にあたるところで、距離は4です。一番遠いのはコーナーで、距離は4×√2=5.7です。

3次元になると、形状は立方体で、空間の中心は「5五Ⅴ」になります。中心から空間の果てへの距離を見ると、一番近いところは同じく各辺の中心にあたるところで、距離は4です。一番遠いのはやはりコーナーで、距離は4×√3=6.9です。

n次元の空間では、中心から空間の果てまでの距離は、最も近いところで4、最も遠いところで4×√nになります。次元の数が増えるにしたがって、中心からコーナーへの距離がだんだん離れていきます。

コーナーの数も増えていきます。2次元では4つ、3次元では8つですが、n次元だと2nつになります。

低次元では角ばったコーナーをもつ空間だったのに、次元が増えるにつれ、コーナーがアンテナのように長く鋭く尖ってゆく、そして、コーナーの数も鬼のように増えていく・・・。

『はじめてのパターン認識』では、この高次元の空間の形を「毬栗(いがぐり)やウニのようなトゲトゲの形をしている」と表現しています。

データが空間の「果て」に偏在するようになる(球面集中現象)

ここでは将棋ではなく、オセロで考えます。

オセロの盤面は、将棋より少し狭い8×8のマス目になっています。オセロでは、外周を押さえると勝ちやすくなりますよねー、という話は置いておいて、8×8のマス目のうち、6×6が内側、外周の28マスが外周、つまり「果て」になります。外周は辺やコーナーにあたるところですね。割合で言うと、28/64=約44%が空間の「果て」にあたります。

オセロが3次元化したらどうなるでしょうか。8×8×8=512のマス目をもつ立方体がオセロ盤になります。そして、6×6×6が内側、立方体の表面にあたる296マスが空間の「果て」になります。割合で言うと、296/512=約58%が空間の「果て」にあたります。

4次元だと約68%、5次元だと約76%、10次元だと約94%、20次元だと99.7%、30次元だと99.98%、・・・。高次元空間では、マス目のほとんどが空間の「果て」になります。

ここでは四角のオセロ盤で説明しましたが、球状の空間で考える場合も同じで、空間のほとんどが「球面」になってしまうため、「球面集中現象」という名前がついています。メロンパンのほとんどがサクサクの皮になると表現するウェブサイトもあります。

どんな問題が起こるか

空間の「果て」は空間の中心からいがぐり状に広がっていき、おまけにデータは空間の「果て」に偏在するようになる・・・。

複数のデータの共通性から、帰納的に法則性を見つけるのが機械学習だったのに、個々のデータ同士が異常に離れてしまい、共通性、類似性が見出せなくなってしまいます。データ間の平均をとってみようもんなら、たいていは空間の中心になってしまう。いがぐり状の島に住んでいて、別々の半島に住むコたちが集まろうとしたら、どうしても島の中心になっちゃいますからね。

学校のクラスメイトもそうで、はじめはお互いのことをよく知らないので、限られた情報、例えば性別だったり、よく喋る/大人しいだったり、メガネの有無だったり身長の高い低いだったりと、なんとなく共通性を見出しやすい状況にありますが、やがてお互いのことをよく知るにつれて、様々な視点から(=たくさんの説明変数で)それぞれの友だちを捉えるようになっていきます。

出身地はどこで、こんな兄弟がいて、こんな趣味があって、国語が得意で砂遊びが好きで、足は速いけど風邪をひきやすい、マリオカートが強くて鶏の唐揚げが好き、お父さんは建築士でお母さんは体操の先生、冬も半ズボン、耳たぶが大きくておでこにホクロがある、ドラえもんが好きで、・・・。説明変数が増えて高次元にデータ(その友だち)を捉えているのがわかります。

そうすると、一人一人の個性が光って、「みんなちがって、みんないい」となります。クラスタリングのような分類が難しくなります。無理やり分類して、各クラスタの平均をとったとしても、そこにはクラスメイトたちとの共通点が全く感じられない”友だち像”ができあがってしまいます。

まとめ

ということで、高次元になるとたくさんのデータが必要になる。高次元になると、データから機械学習で法則性を導くのが難しくなってくる。無理やり法則性を導いても、実態と乖離したものになりがち。ゆえに、汎化性能を良くするためのハードルが極端に上がってしまうということです。

こちらの解説がとても分かりやすいと思います。

集団化する人工知能鈴木教授による解説シリーズ9 機械学習を妨げる次元の呪い

次元の呪い、あるいは「サクサクメロンパン問題」

変数選択して説明変数をできるだけ少なくし、スパースな(説明変数が少ない)モデルにすることは、次元の呪いを回避する上で重要な指針です。