論文メモ Poincaré Embeddings for Learning Hierarchical Representations

May 9, 2020

概要

単語のように上位下位関係のある記号を、ポアンカレ球体模型という双曲空間に埋め込む手法を発表した論文である。ユークリッド空間よりも、記号間の類似度や上位下位関係が保たれていることを実験的に示した。記号を木のノードとして配置し関係を表現するとき、ノード数は深さ$l$対して指数関数的に増加する。双曲幾何学では、円板の面積や周は半径$r$に対して指数関数的に増大するため、木を2次元でモデル化できる。たとえば、深さ$l$以下のノードを半径$r \varpropto l $の空間に配置することができる。一方、2次元のユークリッド空間の場合、半径$r$に対する円周は線形、円の面積は2次関数的であるため、モデル化が難しい。実験では、次元数が少ないほど、ポアンカレ球体模型とユークリッド空間の間で、上下関係や類似度の表現力に差があった。

損失関数

埋め込みたい上下関係$\mathcal{D}=\{(u, v)\}$を記号の数を$n$として入力すると、アルゴリズムは、埋め込みベクトルの集合${\rm \Theta}=\{\boldsymbol{\theta}_i\}^n_{i=1}$を出力する。ただし、$\boldsymbol{\theta}\in \mathcal{B}^d$, $\mathcal{B}^d=\{\boldsymbol{x}\in \mathbb{R}^d\mid ||\boldsymbol{x}||<1\}$とする。学習では、次の損失関数$\mathcal{L}(\Theta)$をもちいる。

$$ \mathcal{L}(\Theta)=\sum_{(u, v)\in \mathcal{D}}\log\frac{e^{-d(\boldsymbol{u}, \boldsymbol{v})}}{\sum_{\boldsymbol{v}’\in \mathcal{N}(u)}e^{-d(\boldsymbol{u}, \boldsymbol{v}’)}} $$ $\mathcal{N}(u)=\{v’\mid (u, v’)\notin \mathcal{D}\} \cup \{v\}$は$v$を含んだ$u$に対する負例である。実験では、正例に対して10の負例をサンプリングしていた。 $d$は、$\boldsymbol{u}, \boldsymbol{v}\in \mathcal{B}^d$の距離であり、次の式であたえらえる。

$$ d(\boldsymbol{u}, \boldsymbol{v}) = \mathrm{arccosh}\left(1+2\frac{||\boldsymbol{u}-\boldsymbol{v}||^2}{(1-||\boldsymbol{u}||^2)(1-||\boldsymbol{v}||^2)}\right) $$

最適化

RSGDやRSVRGで損失関数の値を最小化する埋め込みベクトルを探す。ここでは、RSGDについて説明する。 RSGDでは、次のパラメタの更新式をとる。

$$ \boldsymbol{\theta}_{t+1} = \mathfrak{R}_{\theta_t}(-\eta_t\nabla_R\mathcal{L}(\boldsymbol{\theta}_t)) $$ $\mathfrak{R}_{\theta_t}$はレトラクションで、ここでは$\mathfrak{R}_\theta(\boldsymbol{v})=\boldsymbol{\theta}+\boldsymbol{v}$をもちいる。 $\eta_t$は時刻$t$の学習率をさす。 $\nabla_R$はリーマン多様体上の勾配であり、ユークリッド空間上の勾配$\nabla_E$とは

$$ \nabla_R = \frac{(1-||\boldsymbol{\theta_t}||^2)^2}{4}\nabla_E $$ の関係がある。以上より、更新式は

$$ \mathrm{proj}(\boldsymbol{\theta})= \begin{cases} \boldsymbol{\theta}/||\boldsymbol{\theta}|| - \epsilon &\mathrm{if}\ ||\boldsymbol{\theta}||\ge 1 \\ \boldsymbol{\theta}&\mathrm{otherwise.} \end{cases} $$

$$ \boldsymbol{\theta}_{t+1}\leftarrow \mathrm{proj}\left(\boldsymbol{\theta}_t-\eta_t\frac{(1-||\boldsymbol{\theta}_t||^2)^2}{4}\nabla_E\right) $$ となる。$\epsilon$は計算の安定のために導入する小さな値であり、実験では$10^{-5}$がつかわれた。なお、$\nabla_E=\frac{\partial\mathcal{L}(\boldsymbol{\theta})}{\partial d(\boldsymbol{\theta}, \boldsymbol{x})}\frac{\partial d(\boldsymbol{\theta}, \boldsymbol{x})}{\partial\boldsymbol{\theta}}$であり、$\alpha=1-||\boldsymbol{\theta}||^2, \beta=1-||\boldsymbol{x}||^2, \gamma=1+\frac{2}{\alpha\beta}||\boldsymbol{\theta}-\boldsymbol{x}||^2$とすると、

$$ \frac{\partial d(\boldsymbol{\theta},\boldsymbol{x})}{\partial \boldsymbol{\theta}}=\frac{4}{\beta\sqrt{\gamma^2-1}}\left(\frac{||\boldsymbol{x}||^2-2\langle\boldsymbol{\theta}, \boldsymbol{x}\rangle+1}{\alpha^2}\boldsymbol{\theta}-\frac{\boldsymbol{x}}{\alpha}\right) $$ である。

論文をこちらからダウンロードできます。