Poincare Embeddingの実装について

まえがき

この記事はAP Advent Calendar 2017の25日目です，メリークリスマス．私はチョコレートケーキでも買って美味しく頂こうと思います．

この記事では論文Poincaré Embeddings for Learning Hierarchical Representationsにて提案されている双曲空間上での学習アルゴリズムの実装について，特に幾何学と計算機の相性という観点から述べます．やや変わった視点なので，もう少し癖のない記事が読みたい方はこちらの解説記事をおすすめします．なお，本記事では私が新しくやったものは何一つないです．

この周辺で研究していることはあるんですが，それは論文にしていないのでまだここには書けません．すみません．宣伝みたいで恐縮なのですが，私の研究の話は後日の創造輪講で話す予定なので，興味がある人はそちらで(詳細は一番最後に書きます)．

論文の大まかな紹介

1行要約

階層構造やグラフ構造を持つデータは双曲空間というリーマン多様体に埋め込むと学習が上手くいく．

もう少し解説

階層やグラフ構造を持つデータは世の中に色々あって，それらはグラフで表現することができます．自然言語における単語の間には親単語-子単語の関係があるのでグラフで表現できます(単語がノード，親子関係の有無がエッジの有無です)し，ネットワークはグラフそのものです．さて，グラフ構造をグラフ構造のまま見てあげてもよいのですが，各ノードを距離空間に埋め込んで表現することを考えます．勿論，今考えているのは背後にグラフ構造があるデータの埋め込みですから，好き勝手に埋め込んで良い訳はありません．そこで，埋め込みに次のような要請を課すことにしましょう．

ノード間にエッジが張られているならば距離が近く，張られていないならば距離が遠くなるように埋め込め．

この要請を充たすようにグラフを空間に埋め込むことで，次のような工学的ご利益が期待できます．

ネットワークグラフが与えられていて，一部のエッジの情報が欠落していたとします．そこで現時点で存在がわかっているエッジの情報をもとにしてノードたちを埋め込みます．埋め込んだ結果，リンクが張られていないにも関わらず近くなるノードの組があったとすると，そのノードの間には実は欠落していたエッジが存在するのではないか，という予測・知識発見に繋がります．
自然言語処理においては親子関係があるかないかという2値の分類のみならず，単語と単語の意味の近さみたいなものも定量化できます．例えば「コーヒー」と「ドーナツ」という単語はどちらが「飲み物」という単語と近いか，みたいな問いに対して数字で解答できます(当然，「コーヒー」のほうが「ドーナツ」よりも「飲み物」に近くあってほしいわけですが)．

以上のご利益は原論文に記載がありましたが，これを応用すれば例えば文章が与えられたときにそのトピックを推定するなどの問題にも精度良い解答を出せるかもしれません．このあたりのポテンシャルは未知数です．

さて，この要請を充たすためにとりあえず空間を用意しましょう．いの一番に思いつくのはユークリッド距離を入れたユークリッド空間に埋め込むことです．ノード $u$ たちを適当な乱数を振ってバラ撒いた上で，例えば $\sum_{(u,v) \in E} d(u,v) - \sum_{(u,v) \notin E} d(u,v)$ みたいな損失函数を定めて最小化すればこの目的が達成できそうな気がするでしょう．¹

しかしながら，たとえば1次元とか2次元のユークリッド空間に撒くノードの数を増やしていくと，それぞれのノードの間の制約はどんどん増えていきますから，そのうち限界が来て上手く行かなそうな気がします．実際にこの予想は正しく，ユークリッド距離を用いてこの埋め込みを実行すると，埋め込み先の空間の次元を充分大きく取らないと実用上は満足行く性能が出ないことが実験的にわかっています．

そこで現れるのが「双曲空間」と呼ばれるリーマン多様体です．この双曲空間はグラフ・木を埋め込むには大変相性の良い距離函数を備えていて，ユークリッド空間に埋め込むと100次元くらい必要な表現能力を5次元とかそこらで実現してしまいます．このあたりの話は原論文も詳しいですし，既にある解説記事がとても丁寧で参考になります．

双曲空間

ユークリッド空間や球面と並んでリーマン幾何では重要な図形(多様体)です．ここでは，

上掲した論文が読める程度の最低限の説明
もうすこしちゃんとした説明

をします．

必要最低限の事項

多様体とか言われるとむずかしくてよくわかりませんが，事実として次のことを知っていれば論文は読めるし再現実験ももう少し勉強すれば多分できます．

「 $n$ 次元双曲空間 $\mathbb{H}^n$ 」とは，集合としては $n$ 次元ユークリッド空間内の単位球 $D^n := \{ x \in \mathbb{R}^n\ |\ \|x\| \leq 1 \}$ ．
2点 $u,v \in \mathbb{H}^n$ 間の距離は $d_{\mathbb{H}^n}(u,v) = {\rm arcosh} \Big(1+ \frac{\|u-v\|^2}{(1-\|u\|^2)(1-\|v\|^2)}\Big)$ ．
原点中心の半径 $0 \lt r \lt 1$ の円の弧の長さは $2 \pi \sinh r$ ．これは $r$ に関して指数的に大きくなること，即ち原点から離れるに従って指数的に空間が広がっていくことが重要．
例えば二分木を考えると，これは木の深さ $n$ が増えるに従って総ノード数は指数オーダ $O(2^n)$ で増える．この指数で増えるノードたちを上手く扱うために，ユークリッド空間では次元を大きく上げることで対応したが，双曲空間は原点から離れるだけで勝手に空間が広がってくれるので都合がいい．

さて，計算機との相性についても少し述べておきましょう．

距離函数はそんなに面倒な形をしてなくて， $u,v$ の数値を与えれば(一番重たいのが内積の計算なので)高々 $O(n)$ で計算機に計算させることができる．実時間的にもC++のstdなら多分早いし，GPUを使えば多分もっと早い．
距離函数をその引数で微分して得られる導函数( $\frac{\partial d}{\partial u}$ とか)も頑張れば解析解を計算できて， $u,v$ の数値を与えれば $O(n)$ で計算機に計算させることができる．
計量テンソルの行列表示と呼ばれるものがスカラー行列になっていて，これの逆行列計算は単独で行ったとしても高々 $O(n)$ でできる．ここで何言ってんのかわからない人はスルーしてください．ただ，少なくとも私にとってこの事実はマイム・マイムを踊って喜びたくなるくらい嬉しいことなのだということだけ覚えていて下さい．

とにかく色々なものが解析的に計算できるので計算機に載せて頑張ろうという気になれるのが何よりも重要です．

もうすこしちゃんとした説明

この節ではリーマン幾何の初歩を既知として，双曲空間について知られている事実をもう少しちゃんと列挙し，更に「自然勾配法」と呼ばれているアルゴリズムの実装可能性について言及しておきます．

双曲空間は等長同型だが見た目が異なるモデルが複数存在する．1つのモデルの作り方は次の通り： $\mathbb{R}^{n+1}$ に通常の位相を入れ，更に2次形式 $Q(x)=(x^1)^2+ \cdots + (x^{n})^2 - (x^{n+1})^2$ から誘導される標準ローレンツ計量を入れたミンコフスキ空間 $\mathbb{M}^{n+1}$ を考える． $Q(x)=-1$ で指定される超曲面 $S$ を考えると， $S$ への標準ローレンツ計量の制限は正定値になる．このリーマン計量を備えた超曲面 $S$ を双曲空間の放物面モデルと呼ぶ．
この放物線のある点 $x$ から点 $(0,0,\cdots,0,-1)$ へ直線を引くと，この直線は $D^n := \{ x \in \mathbb{M}^{n+1}\ | \ \|x\| \lt 1, x^{n+1} = 0 \}$ とただ1点で交わる．このような仕方で $S$ から $D^n$ への全単射 $\varphi$ が作れるから，これを用いて $D^n$ をリーマン多様体と見做す(ちゃんと言うなら逆写像 $\varphi^{-1}$ で位相と計量を引き戻している)．この $D^n$ を双曲空間の共形円板モデルと呼ぶ．
その他にも等長同型なモデルはたくさんあります．ベルトラミ・クラインモデルとか上半平面モデルとか．
共形円板モデルのリーマン計量 $g_\mathbb{H}$ は上掲した仕方で構成されるが，その構成をきちんと追いかければ $g_\mathbb{H} = \Big(\frac{2}{1-\|x\|^2}\Big)^2g_\mathbb{R}$ となることがわかる．但し $g_\mathbb{R}$ はユークリッド空間のユークリッド計量．特にこのことから双曲計量の行列表示がスカラー行列になることがわかる．
従ってある点 $u \in \mathbb{H}^n$ およびその点における接ベクトル $V \in T_u\mathbb{H}^n$ が与えられた時，勝手な函数 $f \colon \mathbb{H}^n \to \mathbb{R}$ の勾配ベクトル場 ${\rm grad }\ f$ が高々線形時間で計算できる．

自然勾配法との関係

勾配ベクトル場が計算できると自然勾配法が使えて嬉しいという話ですが，その前に手短に自然勾配法を復習しましょう．

リーマン多様体 $(M,g)$ に対して，函数 $f \colon M \to \mathbb{R}$ の勾配ベクトル場 ${\rm grad }\ f$ とは任意の $u \in M$ および $V \in T_uM$ に対して $g({\rm grad }\ f,V) = Vf$ を充たすような唯一のベクトル場のことを言った．但し右辺は $V$ による $f$ の微分．
局所座標 $(x^1,\cdots,x^n)$ を取って計算すると， ${\rm grad}\ f$ の第 $i$ 座標は $g^{ij}\frac{\partial f}{\partial x^j}$ となることがわかる．但し $g^{ij}$ はこの局所座標に関する $g$ の行列表示の逆行列の $(i,j)$ 成分．
このベクトル場の積分曲線をグラディエント・フローと呼ぶ．グラディエント・フローに沿って移動すると函数値は上昇する．
多様体上の函数 $f$ が与えられた時，適当なステップ幅 $\eta$ を取って， $u \leftarrow u - \eta {\rm grad}\ f$ なる更新を繰り返すことで $f$ の最適化を試みる手法のことを自然勾配法と呼ぶ．

つまり， $f$ のグラディエント・フローを1次近似しようというのが自然勾配法の戦略です．もっと言えば，座標ごとの微分を並べたもの $\Big(\frac{\partial f}{\partial x^i}\Big)$ は $f$ の外微分の成分表示なので座標変換に対する共変性を持ちますが，座標函数は座標変換に対して反変に振る舞うので型が合いません．そこで計量を用いて $\Big(\frac{\partial f}{\partial x^i}\Big)$ の添字を上げ，型をキャストしてあげることでちゃんと足し算をしている雰囲気を出しています．これは実験的に良い性能を出すことが知られていますし，勾配法の収束の証明を真似れば適切な仮定のもとで局所収束も言えると思います…多分．²

ところで，このアルゴリズムの実行には各ステップで計量行列の逆行列計算が必要になります．従って時間計算量はステップごとに $O(n^3)$ です．やや口が悪くなりますが，これは余程特別な場合を除いて使い物にならないと言い切って良いです．しかし今回は計量行列がスカラー行列なので，逆行列の計算に $O(n^3)$ も要りません．余程特別な場合に相当するわけです．そりゃヒャッハーの1つくらいしたくなります．

アルゴリズムの設計

細かいチューニングはともかく，今までの話を踏まえれば次のような手続きを踏んでいけば良いことがわかります．

損失函数を予め設計しておく．損失函数はノード間の距離に依存し，上に挙げた要請を反映しているとする．
単位球の内部にノードを適当にばらまく．
損失函数を自然勾配法で最適化する．双曲空間においては自然勾配法は実行できる．

おまけ:私の研究の話

今回の記事は事実を淡々と述べていく仕方で済ませましたが，いま現在この論文の内容に手を加えて色々やっているところです．その内容について，12月26日の創造輪講で話す予定です．

あとで気づいたのですが，創造輪講は原則非公開でした．なので興味ある人は直接聞きに来て下さい．

実際にこの損失函数を使うわけではないです．損失函数は実際の問題に応じて慎重な設計をする必要があります．ここでは適用する問題の詳細に立ち入らずに大まかな解説をしたいのでこのようなtoy modelを挙げたに過ぎません．↩
多分，と言っているのは私が証明を読んだことがないからです． S.Amari “Information Geometry and Its Applications” には理論的なことが主張されていましたが，私自身の手で証明をverifyできていません．↩

にっき

勉強したことや思ったことを書きます