前提の確認
LargeVisの概要
LargeVisはt-SNEと同様に高次元データを低次元データに変換し可視化を行う研究であり、基本的にはt-SNEと同様な課題を取り扱います。
LargeVisでは基本的に下記のような2ステップに基づいて次元削減が行われます。
1. 近似最近傍(approximated k-Nearest Neighbor)法に基づいた重み付きグラフの構築
2. 確率モデルから定義される尤度に基づく次元削減の変換(関数)の学習
LargeVis論文 Figure 1
1.の重み付きグラフの構築はt-SNEでは明記されないものの、t-SNEの計算では重み付きグラフの構築(t-SNEでは近似ではない点にご注意ください)と同様な処理を行っているので、LargeVisはt-SNEと基本的に同様な考え方を元に構築されていると解釈できます。
Random Projection Trees(RPT)
LargeVisでは近似最近傍探索(approximated k-Nearest Neighbor Search)を行うにあたって、Random Projection Trees(RPT)という手法で空間分割を行った結果を用います。
RPT論文 Figure 1
RPTを用いることで上図のようにk-d treesを用いた結果(左)より柔軟な空間分割を行うことが可能になります(右)。以下ではk-d treesアルゴリズムを詳しく確認した上で、RPTにおける修正点について確認します。
RPT論文 本文より
まず上記がk-d treesのアルゴリズムです。MAKETREE(S)で表されるアルゴリズムは再帰的に書かれており、大まかにはデータセットの$S$を徐々に分割して木を構築していくと解釈すれば良いです。
k-d treesとRPTの相違点はCHOOSERULE(S)を変えることで実現され、k-d treesではデータセットの多次元ベクトルの要素を一つ選びその中央値を基準に分割が行われます。
RPT論文 本文より
k-d treesでは多次元ベクトルの要素を一つ選び分割を行いましたが、RPTree-Maxではランダムに単位ベクトルの$v \in \mathbb{R}^{D}$を選び、内積の中央値である$\mathrm{median}({ z \cdot v | z \in S })$に基づいて分割を行います。
また、分割にあたってサンプルが必ずしも半分ずつにならないように(中央値を用いると必ず半分ずつの分割となる)、中央値に$\sigma$が加えられています。$\sigma$は$x \in S$と$x$から最も離れた$y \in S$の差である$x-y$のEuclidean distanceに一様分布$U(-1,1)$から生成された乱数などをかけることにより生成されます。
RPT論文 本文より
RPTree-MeanではRPTree-Maxと同様にランダムに選んだベクトル$v \in S$と各点の位置ベクトルの内積を元に分割を行う一方で、サンプル集合$S$の直径(the distance between the two furthest points in the set)の$\Delta^{2}(S)$と、下記のように定義される$\Delta_{A}^{2}(S)$の比を元に処理を分岐する点が異なります。
\begin{align}
\Delta_{A}^{2}(S) = \frac{1}{|S|^{2}} \sum_{x,y \in S} ||x-y||^{2}
\end{align}
ここで$c$が定数であることから条件式$\Delta^{2}(S) \leq c \cdot \Delta_{A}^{2}(S)$は、「$S$内に外れ値がある場合はelseの処理、外れ値がない場合はthenの処理が選択されやすい」と解釈すると良いです。
LargeVis論文の詳細
LargeVis論文 Algorithm 1
上記がLargeVis論文に記載されているLargeVisのアルゴリズムです。質の良い木(RPT; Random Projection Trees)を複数構築することでkNNを行うと大量の木が必要になるので、LargeVisのアルゴリズムでは近傍探索(neighbor exploring)が用いられています。
LargeVisにおける近傍探索は「近傍の近傍は近傍である可能性が高い(a neighbor of my neighbor is also likely to be my neighbor)」というアイデアに基づいて実行されています。
アルゴリズムは下記のように理解すると良いと思います。
- いくつかのRPTを作成する
- それぞれのサンプル(node)について複数の木から近傍を探索し$\mathrm{knn}(i)$に追加する
- サンプル$i$に隣接するサンプル$j \in \mathrm{knn}(i)$に隣接するサンプルが$i$に隣接するか調べる