論文読みメモ： Poincaré Embeddings for Learning Hierarchical Representations（その1）

以下の論文を読みます。

Maximilian Nickel, Douwe Kiela. Poincaré Embeddings for Learning Hierarchical Representations. In Advances in Neural Information Processing Systems, 2017. https://papers.nips.cc/paper/7213-poincare-embeddings-for-learning-hierarchical-representations

※ キャラクターは架空のものです。解釈の誤りは筆者に帰属します。おかしい点がありましたらご指摘ください。

次回：まだ

f:id:cookie-box:20190101155733p:plain:w60

階層的な表現を学習するためのポアンカレ埋め込み…テキストやグラフといったシンボリックなデータを数値ベクトル化したいとき、そのようなデータは潜在的な階層構造（？）をもつことが多いので、それを考慮するには双曲空間（ここでは特にn次元ポアンカレ球体模型）という空間の数値ベクトルにすると階層構造も類似度も同時に捉えられてよい、という話なのですね？具体的にこの論文で行ったことは、そのような数値ベクトル表現を得る方法をリーマン計量（？）における最適化に基づいて提案し、潜在的な階層構造をもつデータで検証して、ポアンカレ球体模型への埋め込みはユークリッド空間への埋め込みより表現力も汎化性能も上回ることを示したようですが…表現力と汎化性能って別の概念なんですか？

f:id:cookie-box:20190101160814p:plain:w60

6ページのテーブルの下の Reconstruction と Link Prediction がそれぞれその指標みたいだね。グラフ埋め込みでよく用いられる指標みたい。まだきちんと読んでないけど、前者は上位概念―下位概念の関係をもつ単語ペアを、そのような関係をもたない単語ペアより近くに配置したかって感じなのかな。後者は、評価対象の単語ペアの関係を意図的に排除した状態で学習して、関係をもつ単語ペアを正しく近くに配置したかの推論の性能をみていると思う。両者は違う性能を測っているようにみえるね。単語ペアの関係がどのように与えられているデータセットなのかが確認しないとそれってどういう推論なのかはよくわからないけど…。

上位概念―下位概念とは？

例えば、「動物」という単語と「猫」という単語は上位概念―下位概念だろうし、「猫」と「アメリカンショートヘア」もまた上位概念―下位概念だよね…自然言語は否応なくそういう構造をもってる。というか7ページの学習結果の図示をみても、そのまま mammal（哺乳類）― carnivore（肉食動物）― canine（イヌ科）― German Shephered（ジャーマンシェパード）っていう階層がみえるね。

単語の意味の包含関係ということでしょうか。しかし、それを聞くと潜在的ではなく明示的な階層構造をもつデータで、階層構造に基づいた評価をしているようにみえるんですが…まあいいです。それが双曲空間という空間だと上手くいくというというのはどういうことなんでしょう？双曲空間というのも数値ベクトルの集合ではあるんですよね？双曲空間だと上手くいくというからにはユークリッド空間とは何かが違うようですが、何が違うんでしょう？

そうだな…例えば、「犬」「柴犬」「ポメラニアン」という3つの単語を2次元に埋め込むことを考える。このとき、「犬」と「柴犬」、「犬」と「ポメラニアン」の角度はそれぞれ同じにしたいし、「柴犬」と「ポメラニアン」の角度はそれよりは大きい角度にしたいという要望があるとする。こういう埋め込みってできるだろうか？

え？うーん、犬を適当な $\theta$ 方向に配置して、 $\theta - \Delta \theta$ 方向に「柴犬」、 $\theta + \Delta \theta$ 方向に「ポメラニアン」を配置でもすればいいんじゃないですか？

まあそれでいいよね。じゃあ、犬種が10種類あったらどうだろう？

10種類ですか！？それは…「犬」の周りに犬種たちを配置してしまうとどうしても犬種どうしが近くなってしまいますね…2次元に埋め込むのは難しいと思います。次元がもっとほしいですね…。

うん、近似的に表現するにしても、あまりよくなさそうだよね。自然言語って、きっとある単語にひもづく下位概念の単語がたくさんあって、その中の単語にもまた下位概念の単語がたくさんあって、でも下位概念にいけばいくほど必ずしも単語同士の意味が実際的に近くなるってわけでもないんだよね。単語 $a$ の周りにたくさんの単語を埋め込みたいし、その中の一つの単語 $b$ の周りにもたくさんの単語を埋め込みたいし、さらにその中の一つの単語 $c$ の周りにもたくさんの単語を埋め込みたいけど、埋め込む場所はそんなに狭くしていきたくない、みたいな。そういう願いがあるとき、ユークリッド空間は狭い。

いやそこで空間に文句を付けてどうするんです？狭いといっても、それはもう仕方ないでしょう。

仕方なくないかな。だって、距離の定義を変えればいいんだから。

距離の定義を変える？この点とこの点の間の距離はこう、と勝手に決めてしまうのですか？確かに「単語 $b$ の周りの点は単語 $b$ から離れているとする」「単語 $c$ の周りの点は単語 $c$ から離れているとする」などとすれば「そんなに狭くしていきたくない」を達成できるかもしれませんが、それだとめちゃくちゃな空間になってしまいませんか？というかちゃんと任意の2点間に距離が定義できますか？

「距離の定義を変える」というのは2点間の距離を定義するんじゃないよ。点 $x$ と点 $y$ の距離っていうのは点 $x$ と点 $y$ を結ぶあらゆる連続な経路の「長さ」のうち一番短いものと考える。この「長さ」の定義を変える。例えば、ある点を通るとき、ある向きに通るときはその微小経路で「長さ」を $1dt$ 消費することにするけど、同じ点を別の向きに通るときは「長さ」を $100dt$ 消費することにする。こんな風に、あらゆる点に対してあらゆる向きに通るときの「長さ」を決める。経路の長さは経路上の点のそれを積分する。そうすると、最短経路が直線とも限らなくなってきて、空間内の2点間の「距離」が変わってくる。

点や通る向きによっても「長さ」を変えてしまうんですか？なんだか場所や向きによって通りにくさが違うようですね。通りにくい場所では地面がぬかるんでいるんでしょうか。向きによっても通りにくさが違うということは風も吹いている？ …随分天候が悪い空間ですね。

いや知らないよ…。

しかし、あらゆる点に対してあらゆる向きに通ったときの微小長さを定義すれば差し障りなく空間内の距離を改造できるということなんですか？

本当は微小長さを勝手に直接定義するわけじゃないんだけどね。厳密にいうと、各点に対して「その点を通るあらゆる向き」の集合ではなくて、「その点を通ったとき滑らかな関数がどれだけ変化するかの写像（関数から微小変化への写像）」の集合を考える（この集合を接空間といって、この集合の元を接ベクトルというよ）。空間に定義される滑らかな関数がその点でどれだけ変化するかは、結局その点をどんな向きにどんな速度で通るかによるから、「その点を通るあらゆる向き」の集合を考えてるのとだいたい似てるんだけど。それでいま各点の接空間（その点を通るあらゆる向きっぽい集合）の各元に対して「その向きに通ったときの微小長さ」を定義したいんだったよね。ここでは接空間にノルムを入れてそれを微小長さとすることでそれを達成する。ノルムというか内積を定義して内積が誘導するノルムを採用するんだけどね。この内積がリーマン計量だ。

リーマン計量？アブストラクトにも「リーマン計量における最適化」とありました。

こういう枠組みで「長さ」を一般化して最適化を考えるということだろうね。リーマン計量によって長さが定義された空間をリーマン多様体というよ。私たちがよく知るユークリッド空間も、この論文が採用した双曲空間も、リーマン多様体の例だね。

…あの、リーマン計量では接空間に内積を定義することによって長さを定めるようですが、そこは内積やノルムによらないといけないものなんですか？そのリーマン計量を入れたリーマン多様体というのが空間の「長さ」を一般化した姿としてしっくりくるものなのかよくわからなくて。

そこを外すと「長さ」というものが素朴に満たしてほしい性質を満たさなくなってくると思うな…長さが負とかになってもいいならノルムの正定値性を落としてもいいよ？擬リーマン多様体っていってそういう対象も物理学とかでは利用されているみたいだから。

あ、長さが負とかは結構です。…そうですね、通常のユークリッド空間のリーマン計量というのは、どのような内積なんでしょうか。

ユークリッド計量はこうかな。

$\displaystyle g_p \left( \sum a_i \left( \frac{\partial}{\partial x_i} \right)_p , \; \sum b_i \left( \frac{\partial}{\partial x_i} \right)_p \right) \equiv \sum a_i b_i$ つまり、点 $p$ をある方向にある速度で通るときの微小変化が $\displaystyle \sum a_i \left( \frac{\partial}{\partial x_i} \right)_p$ なら、ここをそのように通るときの微小長さが $\sqrt{ || a ||^2 }$ ってことだね。

…すみません、それがどう私たちの知る距離を意味しているのか。

2次元平面を考えよう。時刻 $t=0$ に $(x_1, x_2) = (0,0)$ を出発して、時刻 $t=1$ に $(x_1, x_2) = (1,1)$ に到着するようにまっすぐ等速で歩く（まっすぐとは何かは計量によるけど、いまはユークリッド計量だから私たちのよく知るまっすぐね）。この経路の長さを測ろう。時刻 $t_0$ に $\gamma(t_0) = (t_0, t_0)$ にいるような経路だね。 $(t_0, t_0)$ を通る時、2次元平面上の任意の滑らかな関数 $f$ がどう微小変化するかを、 $v_{t_0}(f)$ とかこうか。 $v_{t_0}(f)$ は、

$\displaystyle v_{t_0}(f) = \lim_{t \to t_0}\frac{f(\gamma(t)) - f(\gamma(t_0))}{t - t_0} = \lim_{t \to t_0}\frac{f(t,t) - f(t_0, t_0)}{t - t_0}$
$\displaystyle \qquad \; \; = \lim_{t \to t_0}\frac{f(t,t) - f(t_0, t)}{t - t_0}+ \lim_{t \to t_0}\frac{f(t_0,t) - f(t_0, t_0)}{t - t_0}$
$\displaystyle \qquad \; \; = \left. \frac{\partial f}{\partial x_1} \right|_{(x_1, x_2)=(t_0, t_0)} + \left. \frac{\partial f}{\partial x_2} \right|_{(x_1, x_2)=(t_0, t_0)}$

だから結局、時刻 $t_0$ の接ベクトル $v_{t_0}$ がどういう写像だったのかというと、

$\displaystyle v_{t_0} = \left. \frac{\partial}{\partial x_1} \right|_{(x_1, x_2)=(t_0, t_0)} + \left. \frac{\partial}{\partial x_2} \right|_{(x_1, x_2)=(t_0, t_0)}$

だから、 $a_1 = a_2 = 1$ だね。よってこの経路の長さは、

$\displaystyle L(\gamma) = \int_0^1 \sqrt{g_p (v_t, v_t)} dt = \int_0^1 \sqrt{a_1^2 + a_2^2} dt = \int_0^1 \sqrt{1 + 1} dt = \sqrt{2}$

確かに $\sqrt{2}$ ですね。では、ユークリッド計量から別のリーマン計量に変えるとどうなるのでしょう。

この論文ではポアンカレ球体模型というリーマン多様体を利用しているからそれにしようか。さっきの経路の例で最後の計量だけ取り替えよう…と思ったけど、ポアンカレ球体模型は原点からのユークリッド距離が1未満の開球みたいだからさっきの経路だと突き抜けちゃうな。途中の時刻で歩くのをやめようか。ポアンカレ球体模型の計量は、論文の3ページにユークリッド計量との関係式があるね（計量ではなくて計量テンソルというものの関係式としてかかれているけど、この場合は計量の関係式と考えていいよ）。つまり、ユークリッド計量の $\displaystyle \left( \frac{2}{1 - ||x||^2} \right)^2$ 倍にしろってことみたいだ（ $||x||$ はユークリッドノルム）。その点を通るときの微小長さが原点からのユークリッド距離に依存することになる。この倍率は原点では 4 で、開球の端（ $||x||=1$ ）に近づくほど正の無限大に近づくね。つまり、開球の端の方では、近い点がめちゃくちゃ遠い。

何ですかその謎の日本語は…「ユークリッド計量では近い点が」という意味だとわかりますけど。

まあそれで $(0,0)$ から $(T, T)$ まで歩く経路の長さはこうなる。

$\displaystyle L(\gamma) = \int_0^T \frac{2 \sqrt{ g_p (v_t, v_t) } }{1 - ||(t,t)||^2} dt = \int_0^T \frac{2 \sqrt{2}}{1 - 2t^2} dt = 2 \, {\rm artanh} (\sqrt{2}T)$

論文の4ページに任意の2点間の距離の式が明示的にかいてあるけど、 $u=(0,0), \,v=(T, T)$ を代入するとこの結果と一致するよ。計算してみて。

え？えっと、 ${\rm artanh}(x)$ と ${\rm arcosh}(x)$ の定義に戻せば…確かに一致しますね。ん？いやでも、論文4ページの式 (1) は点 $u$ と点 $v$ の「距離」、つまり、「点 $u$ と点 $v$ を結ぶ経路のうち最短なものの長さ」ですよね。いま点 $(0,0)$ から点 $(T, T)$ にまっすぐ歩いた経路は確かにユークリッド空間において最短経路ですが、ポアンカレ球体模型においてもこれが $(0,0)$ から $(T, T)$ への最短経路ということですか？

まさしく。ポアンカレ球体模型の計量でユークリッド計量に乗じる倍率 $\displaystyle \left( \frac{2}{1 - ||x||^2} \right)^2$ って、原点から動径方向に遠ざかるほど「微小長さ」が長くなっていくことを意味してるけど、だったら現在地から動径方向にある目的地に行きたいときは迂回しても意味ないからね。「迂回すると微小長さが短い領域を歩けてお得」ってことにならないから。だから素直に動径方向に歩くのが最短。最短経路がユークリッド計量のときとずれてくるのは、スタートからゴールの向きが動径方向ではないときだ。この場合は（ユークリッド計量でいう）まっすぐ進むよりも、ちょっと原点に引っ張られるようにカーブしながら進む方が「微小長さ」を節約できる。原点に近いほど「微小長さ」が短いからね。論文3ページの Figure 1 の (a) にピンクとブルーとオレンジの線があるけど、これらはこの両端の点を結ぶ最短経路だよって図だと思う。ピンクだけは動径方向だから「まっすぐ」だね。

対して、ブルーとオレンジの線は確かに原点にひっぱられたカーブといった感じがしますね…これらは具体的にどういうカーブなんでしょう？

まずこういう2点を結ぶ最短経路のことを測地線というんだけど、ポアンカレ球体模型の場合は測地線は境界面に直交する円弧になる。ブルーとオレンジの線もそうみえるよね。

境界面に直交する円弧が本当に最短かどうかは、そういう円弧が測地線方程式っていう微分方程式を満たすことを示せばいい。けどすぐできなかった。ポアンカレ球体模型じゃなくてポアンカレ半平面模型っていうちょっと違うリーマン多様体の場合は測地線方程式から測地線はこうって記事が結構みつかる気がする。こっちの場合の測地線も境界と直交する円弧なんだけどこっちは球体じゃない。

そうですか…論文に戻って、先に最後の Discussion and Future Work もみておきます。…といっても、今後の展望として色々あって、埋め込み後の後段のタスクのモデルが現状ではユークリッド空間向けになっているので双曲空間向けにしなくては、といったくらいですかね。

（その2があれば）つづく