異空間散歩!双曲空間を歩いてみよう。

この記事は、scouty Advent Calendar の14日目です。

本記事には、線の束がウネウネ動くgif動画があります。人によっては気持ち悪いと感じるかもしれませんので、苦手な方はご注意ください。

f:id:nunuki:20181215054133p:plain

双曲空間埋め込み - Poincaré Embedding

近年、機械学習界隈で双曲空間(Hyperbolic geometry) への埋め込み(Poincaré Embedding; Nickel & Kiela, 2017)1が流行っています。 双曲空間は、ユークリッド空間(普通のN次元空間)と異なり、原点から遠ざかるに連れて(正確な表現ではありませんが)急激に空間が拡がるという性質を持っています。このため、ユークリッド空間では不可能であった『木構造の埋め込み』が双曲空間においては可能となる2など、少ない次元でより複雑な構造を扱うことができる点が注目されています。 今年のICML でも(Octavian et al., 2018)3 や (Nickel et al., 2018)4 などの最新手法が提案され、ますます盛り上がりを見せています。

双曲空間への埋め込みについては、日本語だと こちらのブログ が詳しいです。 また、scouty でもやってみた記事を出したりしてます。

今回は、「双曲空間には木構造をはじめとする複雑な構造を埋め込むことができる」ことを直感的に理解するために、双曲空間に作られた迷路を歩いてみましょう。

ポアンカレ円盤モデル

以降では、2次元の双曲空間のみを考えます。

まずは、通常のユークリッド空間に埋め込むことができない双曲空間をイメージするために、ポアンカレの円板モデルを導入します。 ポアンカレ円板とは、双曲空間を表現するモデルの1つです。 双曲空間を表すモデルはいくつもありますが、ポアンカレ円板モデルは数理的な解析がしやすいなどの理由から、双曲空間への埋め込みの研究の多くでこのモデルが採用されています。

ポアンカレ円板モデル
図1: ポアンカレ円板モデル (Wikipediaより)

図1: ポアンカレ円板モデル

ポアンカレ円板は双曲空間の局所座標の1つと考えることもできます。 いま、双曲空間の地図を書くことを考えます。双曲空間は通常の2次元平面(ユークリッド空間)に長さと角度を保ったまま埋め込むことはできません。そこで、長さと角度のどちらかは崩れてしまいますが、投影法を駆使して2次元の平面に地図を描きます。 これは、ちょうど、地球の表面(球面)の地図をメルカトル図法や方位図法などの投影法によって平面に描いていることに似ています。

双曲空間のポアンカレ円板モデルは、地球の地図における方位図法に相当する投影法であると言えます。 図2は、東京を中心とする(正距)方位図法で描かれた世界地図です。この地図では、東京と別の都市(例えばマイアミ)とを結ぶ最短経路は直線(赤線)で描かれます。地球の表面に沿った線をこのまま"まっすぐ"伸ばして行くと、地球を一周して東京に戻ってきます(青線)。 この「地球上の2点を結ぶ最短経路」は、地球の表面を ”まっすぐ” 走る車の軌跡であるとも言えます。 このように、球面のような曲がった面を "まっすぐ" 進むことでできる軌跡を測地線と呼びます。球面の測地線は、球面を球の中心を通る平面で切った輪切りの円(大円)になります。

f:id:nunuki:20181215054254p:plain
図2: 東京を中心とする正距投影図法で描かれた世界地図

下図3の赤線は、ポアンカレ円板モデルにおける中心点を通る測地線(赤線)を表しています。球面の方位図法と同様に、中心を通る測地線は直線で表されます。 ただし、双曲空間は球面と違って閉じていないので、どんなにまっすぐ進んでも元の点に戻ってくることはありません。つまり、図3の円の上下左右は繋がっておらず、ポアンカレ円板の外側の半径1の円は、双曲空間の無限遠点を表します。

f:id:nunuki:20181215054516p:plain
図3: ポアンカレ円板モデルにおける、原点を通る測地線(赤)と原点からの等距離線(青)

図3の青い円は、中心からの距離が一定の線(つまり、ポアンカレ空間における"円")を等間隔で表しています。中心点を離れるにつれて、円が詰まってい流のがわかります。 これは、中心から離れるとどんどん縮尺が小さくなり、円板の端では縮尺が無限小になっていることを表しています。このことは、図2において、中心から離れた点で縮尺が大きくなっている(例えば、南米大陸が非常に大きく伸びている)ことを考えると、対照的です。

ポアンカレ円板において、中心を通る測地線は直線で表されましたが、中心以外を通る測地線は、端の円と直交する円弧になります。中心以外の点を通る測地線の様子を図4に示しました。

f:id:nunuki:20181215054643g:plain
図4: ポアンカレ円板における平行移動

ポアンカレ円板モデルのもう1つの大事な性質として、双曲空間における2つの線のなす角度は、ポアンカレ円板における角度と等しいという性質(正角性)があります。 実際、図4では、赤い線と青い線は、平行移動しても常に直交していることがわかります。

「直進、右折」を繰り返す

ポアンカレ円板を導入して、双曲空間を歩く準備ができました。 しかしその前に、通常の平面や、球面を歩いた場合にどうなるかを復習しておきます。

あなたは通常の2次元平面の点Aに立っているとします(図5a)。 そこから、あなたはある距離(例えば100m)を真っ直ぐ歩き、次に90度回れ右をし、また同じだけ(100m)歩き、、と繰り返した場合どうなるでしょうか? もちろん、この操作を4回繰り返すと、正方形を描いて元の位置に戻ります。

f:id:nunuki:20181215054759j:plain
図5: 平面と球面上で、直進と右折を繰り返す。

しかし、球の場合には平面と異なり、直進と右折を、4回ではなく3回や2回繰り返すだけで元の点に戻ることが可能です。 図5b のように、北極点からスタートして、赤道まで歩き、90度回って赤道上を同じだけ歩き、さらに90度回って同じだけ歩くと、3回の繰り返しで北極に戻ってきます。 さらに、図5c のように、北極をスタートしてから南極まで歩き、そこで90度回ってまた同じだけ歩くと、元の北極点に戻ってきます。

それでは、双曲空間の場合、何回で戻ってくることができるでしょうか? 結論から言うと、戻ってくるのには、直進と右折を4回よりも多い回数繰り返す必要があります。 さらに、直進する距離がある程度以上長くなると、何回繰り返しても元の位置に戻らないことすらありえます。 このように「直進と右折を何度繰り返しても元の位置に戻らない」という性質が、実は「双曲空間に木構造を埋め込むことができる」ということと深く関連しているのです。

双曲空間の迷路を歩く

まずはこちらのgif動画をご覧ください。

f:id:nunuki:20181215054837g:plain
図6: 双曲空間の迷路を歩く

これは、双曲空間に無限に広がる迷路の中を進む様子をポアンカレ円板に投影した図です。 現在地から遠い点は、ポアンカレ円板に投影することによって歪んでしまっていますが、双曲空間において、迷路を構成している四角いタイルは全て同じ形で、すべての道はまっすぐ(測地線)で、すべての十字路は直交しています。

図6は、一本道では直進し、分かれ道(十字路)では常に右に90度回転していますが、平面や球面の場合とは異なり、一度訪れた場所に2度と訪れることはありません。 さらに、一度、ある分かれ道で「右折」を選ぶと、その分かれ道で「直進」や「左折」することでたどり着ける場所にたどり着くためには、この分かれ道まで戻ってくる以外に方法が無いこともわかります。 つまり、迷路の中の分かれ道をノード、分かれ道を繋ぐ通路をエッジとするグラフ構造を考えると、スタート地点を根とすると、1つのノードが、「直進」「右折」「左折」の3つのノードを子として持つ木構造になっていることがわかります。さらに言えば、これらのエッジはすべて同じ長さであり、すべてのノードは等価であることもわかります。 このように、双曲空間を用いることで、エッジの長さを保ったままグラフ構造を埋め込むことができることがわかりました。

まとめ

Poincaré Embedding など、巷で流行っている双曲空間を理解するため、ポアンカレ円板による可視化を行いました。 ユークリッド平面や球面と比較して、双曲空間は無限に「直進、右折」を繰り返しても元の点にたどり着かないことが起こりうることを説明しました。 このことが、「双曲空間に木構造を埋め込める」ということと深く関係していることを説明しました。

なお、作図に用いたスクリプトは一応こちらにおいておきます。

余談

図6の迷路のような構造を持った格子を(配位数4の)Bethe格子と呼んだりします。 ユークリッド空間では実現不可能ですが、木構造を持っているため、諸々の解析がしやすく、物性物理において格子系を研究する際の toy model としてよく使われたりします。

参考文献


  1. https://arxiv.org/abs/1705.08039

  2. これは、「初等的でない双曲群が階数2の自由群を含む」という事実からもわかります。京大の藤原先生の講義ノート「双曲群の手引き(1995)」にその証明があります(定理3.2)。

  3. http://proceedings.mlr.press/v80/ganea18a.html

  4. http://proceedings.mlr.press/v80/nickel18a.html