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

超球の体積、すなわち多次元空間における球は、一般的に私たちが観測する３次元の球体の体積とは遥かに異質な性質を示すらしい。 

機械学習の有名な教科書によれば、

 Our geometrical intuitions, formed through a life spent in a space of three dimensions, can fail badly when we consider spaces of higher dimensionality.

拙訳：　我々の幾何学に関する直観は、３次元空間の中で過ごした人生の中で形成されたものだが、高次元空間を考えるときには、まるで役立たないことがある。

("パターン認識と機械学習 上", 原書, p.36)

... in spaces of high dimensionality, most of the volume of a sphere is concentrated in a thin shell near the surface!

拙訳：　...(中略)... 高次元空間においては、球の体積のほとんどが、球表面近くの薄い「殻」に集中しているのだ！

(同書， p.36)

とのことである。一般的には「次元の呪い」と呼ばれる現象だ*1。

そして、先日この「殻」について、身悶えるほど鮮烈なイメージを与える具体例をツイッター上で観測した。 

球を多次元空間に飛ばした超球面で、ほぼすべての面積が表面に近いところに集まるため、超シュークリームはほぼパンばかりで不味くて、超メロンパンはほぼサクサクの皮で非常に美味いという世紀の大発見を @mima_tea くんが今日の輪講で披露してくれた。

— Graham Neubig (@neubig) 2015, 4月 20

メロンパンの皮。

確かにメロンパンの皮は、３次元空間では非常に薄っぺらなものでしかない。しかしそのメロンパンの皮の体積はｎ乗に比例して増加していくため、ｎ次元空間では皮がメロンパンの大半を占めることになる。

なんということだ。超球とはメロンパンのことであったのだ。

しかし、肝心のこの偉大な事実に関する発見者は、

グラム先生の「超メロンパン」のツイート、輪講だとあんまり受けなかったのにTwitterだと微妙に伸びてて世の中何が起きているかわからないし理解不能を感じる

— みまティー (@mima_tea) 2015, 4月 22

と言ったように、自身の発見がいかに素晴らしく価値のあるものであるか、それに見合った賞賛を受けていない。

ここでは、＠mima_tea氏の発見がいかにヴィヴィッドなものであるかを、R言語による可視化を用いて表現してみたい。作成したコードは記事の末尾に掲載するので、先に出力画像から紹介していく。

まずは、３次元空間において、我々が普段目にしているメロンパンである。

うん。メロンパンだ。

左図では、茶色がｎ次元空間（ここではｎ＝３）における皮の体積に、黄色がモチモチ部分の体積に対応するように面積を定めている。体積を面積で表現することで、直観がはたらきやすいように心がけた。３次元空間におけるメロンパンは、非常に美味しそうで、かぶりつけば今にもサクサクという音が耳に聞こえてきそうだ。

右図は、ヨコ軸が「メロンパンが存在する次元の次元数」、タテ軸が「皮がメロンパン全体に占める割合」を表す。●が左側で表現されたメロンパンが利用しているパラメータであり、ここで次元数が３，皮の割合が0.03なので「３％がサクサク」であると言える。

メロンパンの皮の厚みは、半径に対して1％に設定した。上の図からは、これが一般的なメロンパンの表現になっていることが推察される。以下では、これと同じパラメータを用いて、メロンパンの皮の挙動を調べていく。

続いて、３０次元空間におけるメロンパンを見てみる。

これは…

高級なパン屋にいくと、メロンパンの皮部分が厚いクッキー生地で作られており、別々に焼かれて張り付けられていることがある。

３０次元空間におけるメロンパンは、すなわちそのような高級メロンパンに近くなっていると言える。なんてお得なんだ。単にメロンパンを３０次元空間に飛ばすだけで、サクサク感を全体の２６％も楽しめる。

続いて、１００次元空間におけるメロンパンを見てみる。

皮の割合が６３％を超え、もはやメロンパンというよりクッキー状態である。
繰り返すが、「皮の厚み」を表す数値は３次元のときから変えていない。

半径のわずか１％のままである。それなのに、メロンパン全体に占める割合としては、すでに６３％に達してしまっている。高次元空間においては、いかにメロンパンが我々の幾何学的な直観に反する食物になるかが伺いしれるだろう。

そして最後に、５００次元空間における５００次元メロンパンを見てみよう。

完全に皮になってしまった…。

これがいわゆる次元の呪い、すなわちサクサクメロンパン問題である。

高次元空間においては、面積が球表面に集まりすぎて、
メロンパンがサクサクになりすぎてしまうのである。 

おわりに

次元の呪いを、メロンパンによって観察することで、高次元空間における面積の挙動について直観を得ることができた。

次元の呪いは、MCMCなど近年のサンプリング技術の理解において非常に大事な基礎的事実であるので、このような直感的な説明を提案した＠mima_tea氏に尊敬の意を表し、結びの言葉とする。

いつも心にメロンパン。

おしまい

使用したソースコード

melonpan-like visualization of "curse of dimension ...

参考文献

パターン認識と機械学習 上

質問コーナー

しつもん：　メロンパンは球ではなく円盤ではないのですか？

こたえ：　　君みたいな勘のいいガキは嫌いだよ

*1:１次関数 x と２次関数 x ^2について、 x < 1の部分では直線 x のほうが大きいのに、 x > 1になると急激に放物線x^2の値が直線より大きくなるような変動が、高次元ではより非直感的なレベルで起きるということのようだ。