Hyperbolic Definitions for Machine Learning

# Graphical Image for Hyperbolic Space
代表的なPoincaré (Ball)、Lorentz (Hyperboloid)、Klein の関係性に関してイメージを掴むのに以下が参考になる。
[Hyperboloid and projections](https://www.geogebra.org/m/bzTEJreV)

# Basic Definitions
curvatureはEuclideanは 0 、Poincaré、Lorentz、Kleinは -1 だが、後者3つは任意の負の定数をとれるよう一般化して $-c\\:(c>0)$ または $-1/K\\:(K>0)$ と定義する。この時、Poincaré Ballなどの半径は$\sqrt{K}$となる。また、Space（空間）の点を${\bf x}$と${\bf y}$で表し、Tangent Space（接ベクトル、速度ベクトル、勾配の空間）の方向を${\bf u}$と${\bf v}$で表す。以下の定義は[^1][^2][^3][^4][^5]から参照し、まとめたものである。Gyrovecotrに関しては後日まとめる予定。

|  | Euclidean | Poincaré (Ball) | Lorentz (Hyperboloid) | Klein |
|:-:|:-:|:-:|:-:|:-:|
| Space $\mathcal{M}^{n,K}$ | $\\{{\bf x} \in \mathbb{R}^{n}\\}$ | $\\{{\bf x} \in \mathbb{R}^{n}:\lVert {\bf x} \rVert^2<K\\}$ | $\\{{\bf x} \in \mathbb{R}^{n+1}: \langle {\bf x}, {\bf x} \rangle_{\mathcal{L}}=-K, x_0>0\\}$ <br> where $\langle {\bf x}, {\bf x} \rangle_{\mathcal{L}}:=-x_0^2+\sum^n_{i=1} x_i^2$ and $x_0=\sqrt{K+\lVert\hat{{\bf x}}\rVert^2}$, <br> where $\lVert\hat{{\bf x}}\rVert^2=\sum^n_{i=1} x_i^2$ | $\\{{\bf x} \in \mathbb{R}^{n}:\lVert {\bf x} \rVert^2<K\\}$ |
| Tangent Space $T_{{\bf x}}\mathcal{M}^{n,K}$ | - | - | $\\{{\bf v} \in \mathbb{R}^{n+1}: \langle {\bf v}, {\bf x} \rangle_{\mathcal{L}}=0\\}$ | - | - |
| Metric Tensor in <br> $\mathrm{g}^K_{\bf x} : T\_{{\bf x}}\mathcal{M}^{n,K} \times T\_{{\bf x}}\mathcal{M}^{n,K} \rightarrow \mathbb{R}$ <br> which defines the inner product, norm, angle and distance in the Tangent Space | $I_n$ | $(\lambda^K_{\bf x})^2I_n$ <br> where $\lambda^K_{\bf x}$ is the conformal factor $\frac{2}{(1-\frac{1}{K}\lVert {\bf x} \rVert^2)}$ | $\mathrm{diag}(-1,{\bf 1}_n^{\mathrm{T}})=\left(\begin{array}{cccc}-1&0&\cdots &0 \\\\ 0&1&\cdots &0 \\\\\vdots&&\ddots& \\\\ 0&0&\cdots &1\end{array}\right)$ | $g^1_{ij}=\frac{\delta\{ij}}{1 - \lVert {\bf x} \rVert^2}+\frac{x_ix_j}{(1 - \lVert {\bf x} \rVert^2)^2}$ <br> when $K=1$, where $g^1_{ij}$ is the element of a matrix, derived from [^3] |
| Distance <br> $\mathrm{d}^K: \mathcal{M}^{n,K} \times \mathcal{M}^{n,K} \rightarrow \mathbb{R}$ | $\lVert {\bf x} - {\bf y} \rVert$ |  | $\sqrt{K}\mathrm{arcosh}(-\frac{\langle {\bf x}, {\bf y} \rangle_{\mathcal{L}}}{K})$ | - |
| Exponential Map <br> $\mathrm{exp}^K_{{\bf x}} : T\_{{\bf x}}\mathcal{M}^{n,K} \rightarrow \mathcal{M}^{n,K}$ | ${\bf x}+{\bf v}$ |  | $\mathrm{cosh}(\frac{\lVert {\bf v} \rVert_{\mathcal{L}}}{\sqrt{K}}){\bf x} + \sqrt{K}\mathrm{sinh}(\frac{\lVert {\bf v} \rVert_{\mathcal{L}}}{\sqrt{K}})\frac{{\bf v}}{\lVert {\bf v} \rVert_{\mathcal{L}}}$ <br> where $\lVert {\bf v} \rVert_{\mathcal{L}}=\sqrt{\langle {\bf v}, {\bf v} \rangle_{\mathcal{L}}}$ | - |
| Logarithmic Map <br> $\mathrm{log}^K_{{\bf x}} : \mathcal{M}^{n,K} \rightarrow  T\_{{\bf x}}\mathcal{M}^{n,K}$ <br> which is the inverse function of Exponential Map | ${\bf y}-{\bf x}$ |  | $\mathrm{d}^K_{\mathcal{L}}({\bf x}, {\bf y})\frac{{\bf y}+\frac{1}{K}\langle {\bf x}, {\bf y} \rangle_{\mathcal{L}}{\bf x}}{\lVert {\bf y}+\frac{1}{K}\langle {\bf x}, {\bf y} \rangle_{\mathcal{L}}{\bf x}\rVert_{\mathcal{L}}}$ <br> where $\mathrm{d}^K_{\mathcal{L}}({\bf x}, {\bf y})$ is the distance of Lorentz. | - |
| Parallel Transport <br> $P^K_{{\bf x} \rightarrow {\bf y}}:T_{\bf x}M \rightarrow T_{\bf y}M$  | ${\bf v}$ |   | ${\bf v} - \frac{\langle \log^K_{\bf x}({\bf y}), {\bf v}\rangle_{\mathcal{L}}}{\mathrm{d}^K_{\mathcal{L}}({\bf x}, {\bf y})^2}(\log^K_{\bf x}({\bf y}) + \log^K_{\bf y}({\bf x}))$  | - |
| To Poincaré | - | - | $\frac{\hat{{\bf x}}}{1+\frac{1}{\sqrt{K}}x_0}$ <br> where ${\bf x}=(x_0, \hat{{\bf x}}^{\mathrm{T}})^{\mathrm{T}}$  | $\frac{2{\bf x}}{1+\frac{1}{K}\lVert {\bf x} \rVert^2}$ |
| To Lorents | - | $(\sqrt{K}\frac{1+\frac{1}{K}\lVert {\bf x}\rVert^2}{1-\frac{1}{K}\lVert {\bf x}\rVert^2}, \frac{2}{1-\frac{1}{K}\lVert {\bf x}\rVert^2}{\bf x}^{\mathrm{T}})^{\mathrm{T}}$ | - | $\frac{1}{\sqrt{1 - \frac{1}{K}\lVert {\bf x} \rVert^2}}(\sqrt{K},{\bf x}^{\mathrm{T}})^{\mathrm{T}}$ |
| To Klein | - | $\frac{{\bf x}}{1+\sqrt{1-\frac{1}{K}\lVert {\bf x} \rVert^2}}$ |  $\frac{\hat{{\bf x}}}{\frac{1}{\sqrt{K}}x_0}$ <br> where ${\bf x}=(x_0, \hat{{\bf x}}^{\mathrm{T}})^{\mathrm{T}}$ | - |

Metric Tensorはある地点${\bf x}$を中心としたTangent Spaceにおける方向（接ベクトル、速度ベクトル、勾配）${\bf u}$と${\bf v}$の大きさと角度を定義する。大きさはEuclideanの場合、$\sqrt{\mathrm{g}^K_{\bf x}({\bf u},{\bf u})}=\sqrt{{\bf u}^{\mathrm{T}}I_n{\bf u}}=\lVert {\bf u} \rVert$で表され、これはL2 normである。他の空間でも、Metric Tensorを間に掛け合わせ、平方根を取ることで大きさを得られる。
Tangent Spaceにおける角度はEuclideanとPoincaréでは同じ（これを等角（conformal）という）で以下のように等価を証明できる（後ろから三番目がEuclidean、後ろから二番目がPoincaréのMetric Tensorを使った式である）。[^4]

$$cos\theta=\frac{\mathrm{g}^K\_{\bf x}({\bf u},{\bf v})}{\sqrt{\mathrm{g}^K\_{\bf x}({\bf u},{\bf u})} \sqrt{\mathrm{g}^K\_{\bf x}({\bf v},{\bf v})}}=\frac{{\bf u}^{\mathrm{T}}I\_n{\bf v}}{\sqrt{{\bf u}^{\mathrm{T}}I\_n{\bf u}}\sqrt{{\bf v}^{\mathrm{T}}I\_n{\bf v}}}=\frac{(\lambda^K\_{\bf x})^2{\bf u}^{\mathrm{T}}I\_n{\bf v}}{\sqrt{(\lambda^K\_{\bf x})^2{\bf u}^{\mathrm{T}}I\_n{\bf u}}\sqrt{(\lambda^K\_{\bf x})^{2}{\bf v}^{\mathrm{T}}I\_n{\bf v}}}=\frac{{\bf u}^{\mathrm{T}}{\bf v}}{\lVert {\bf u} \rVert\lVert {\bf v} \rVert}$$

$\lambda^K_{\bf x}$は分子分母で打ち消され、Euclideanと同じ角度となる。 $\lambda^K_{\bf x}$をconformal factorという。
Space 上の二点間の距離は以下のように$\mathrm{g}^K\_{\gamma(t)}$を使って定義できる。[^4]

$$\mathrm{d}^K({\bf x}, {\bf y}) = \mathrm{inf}_{\gamma}\int_0^1\sqrt{\mathrm{g}^K\_{\gamma(t)}(\dot{\gamma}(t),\dot{\gamma}(t))}dt$$

ここで $\gamma$ は $\gamma(0)={\bf x}$ 、 $\gamma(1)={\bf y}$ となる二点を結ぶ任意の線を表す関数である。この任意の線を表す関数のうち $\mathrm{inf}_{\gamma}$ 内の値を最小にする $\gamma$ を選び、その値を二点の距離として定義している。また選ばれた $\gamma$ を測地線（geodesic）という。 $\dot{\gamma}(t)$ は $t$ 時点での速度ベクトルを表し（$t=0$ の時、 ${\bf x}$ 地点の速度ベクトルを表す）、この大きさを足し合わせていくことで距離を算出している。各空間の Distance $\mathrm{d}^K$ はこの積分を解いたものである。

# Aggregation Operations

Tangent Space で通常の Euclidean Space のように average pooling をしたり（その後、Exponential Map で Hyperbolic 上に戻す）、以下のように Klein Space で Einstein Midpoint （Hyperbolic上での平均）を求める方法が提案されている。[^6]

$${\bf y}=\sum_i\frac{\gamma\_i {\bf x}_i}{\sum_j\gamma\_j}$$ $$\mathrm{where}\;\gamma\_i=\frac{1}{\sqrt{1 - \frac{1}{K}\lVert {\bf x}\_i \rVert^2}}\;\mathrm{and}\;{\bf x}\_i\;\mathrm{is}\;\mathrm{a}\;\mathrm{point}\;\mathrm{of}\;\mathrm{Klein}\;\mathrm{Space}$$

Poincaré、Lorentzの場合は、一旦Klein Spaceに移動してから、aggregation を行い、その後もとの空間に戻す。
また attention のようなケースで重み付きの Einstein Midpoint も提案されている。[^2]

$${\bf y}=\sum_i\frac{\alpha\_i\gamma\_i {\bf x}_i}{\sum_j\alpha\_j\gamma\_j}$$ $$\mathrm{where}\;\alpha\_i\;\mathrm{is}\;\mathrm{an}\;\mathrm{attention}\;\mathrm{weight}$$

他の方法としては Gyrovector により aggregation する方法も提案されている。
（Hyperbolic上での）max pooling や bi-interaction pooling などは提案されておらず、今の所 Tangent Space で行う方法しかない。

# Euclidean Space to Hyperbolic Space

Euclidean Space から Hyperbolic Space への変換方法として以下が提案されている。[^1]

$$\mathrm{exp}^K_{{\bf o},\mathcal{L}}((0,{\bf v}^{\mathrm{T}})^{\mathrm{T}})=(\sqrt{K}\mathrm{cosh}(\frac{\lVert {\bf v} \rVert}{\sqrt{K}}), \sqrt{K}\mathrm{sinh}(\frac{\lVert {\bf v} \rVert}{\sqrt{K}})\frac{\bf v}{\lVert {\bf v} \rVert})^{\mathrm{T}}$$ $$\mathrm{where}\; \mathrm{exp}^K_{{\bf o},\mathcal{L}}\; \mathrm{is}\; \mathrm{exp}^K_{\bf o}\; \mathrm{of}\; \mathrm{Lorentz}\; \mathrm{at}\; {\bf o}:=(\sqrt{K},0,\cdots,0)^{\mathrm{T}}\; \mathrm{and}\; {\bf v} \in \mathbb{R}^{n}$$

この方法を使えば Euclidean Space の特徴量を Hyperbolic Space に持っていくことも可能である。


[^1]: Hyperbolic Graph Convolutional Neural Networks： https://arxiv.org/pdf/1910.12933.pdf
[^2]: Hyperbolic Attention Networks： https://openreview.net/pdf?id=rJxHsjRqFQ
[^3]: https://math.stackexchange.com/questions/1292707/comparing-metric-tensors-of-the-poincare-and-the-klein-disk-models-of-hyperbolic/1295924#1295924
[^4]: Hyperbolic Neural Networks： https://arxiv.org/pdf/1805.09112.pdf
[^5]: Hyperbolic Neural Networks++: https://arxiv.org/pdf/2006.08210.pdf
[^6]: HyperText: Endowing FastText with Hyperbolic Geometry: https://arxiv.org/pdf/2010.16143.pdf