Engel, D., Huttenberger, L., Hamann, B. (2012) A Survey of Dimension Reduction Methods for High-dimensional Data Analysis and Visualization. Visualization of Large and Unstructured Data Sets: Applications in Geospatial Planning, Modeling and Engineering – Proceedings of IRTG 1131 Workshop, 135-149.
次元縮約についてのレビュー論文。ちょっと調べものがあって。
Rdimtoolsというパッケージのマニュアルでお勧めされていたので読んでみたんだけど、Google様いわく被引用数63。だいじょうぶなんだろうか… いや、まあ、いいけどさ…
1. イントロダクション
次元縮約について、多変量データの視覚化に焦点をあててレビューします。データ解析の他の側面(特徴の再構成とか分類とか)のための次元縮約にはあまり触れないのでよろしく。幅広く知りたいんならBurges(2010, Foundations & Trens in ML), 歴史に関心があるんならLee & Verleysen (2010 IJCNN)を読めばいいんじゃないの。
2. 次元縮約
\(m\)次元空間上に\(n\)個の点\( X \in \mathbb{R}^{(n \times m)} \)があるとするじゃない？ データ空間\( \mathbb{R}^m \)にはmetric距離 \(\delta_m: \mathbb{R}^m \times \mathbb{R}^m \rightarrow \mathbb{R} \)があり、ターゲット空間 \( \mathbb{R}^t \)にもmetric距離 \(\delta_t: \mathbb{R}^t \times \mathbb{R}^t \rightarrow \mathbb{R} \) があるとするじゃない？ ちなみに \( t \ll m \) ね。
\(\delta_m(x_i, x_j) \approx \delta_t(y_i, y_j) \)となるように、つまり、データ空間上で近い2点はターゲット空間上でも近い2点となるように、データ点を目標点に「忠実に」マッピングする関数 \(\phi: \mathbb{R}^m \rightarrow \mathbb{R}^t \)を考える。
ふつう\( \phi \)は最小二乗誤差
$$ \epsilon_\phi = \sum_{i,j} W_{i,j} (\delta_m(x_i, x_j) – \delta_t(y_i, y_j))^2$$ を最小化するように定義される。\( W \in \mathbb{R}^{(n \times n)} \)はウェイト行列。[「最小二乗誤差を最小化する」って変じゃない？ 誤差二乗和を最小化するってことですよね]
上の定義はデータ距離とターゲット距離がともにmetricであることを求めている。つまり、正定値性、対称性、三角不等性を求めている [知らなかったんだけど、非負かつ同一律が成り立つことを正定値性というのだそうだ。正定値性って行列の用語かと思っていたよ…]。ターゲット空間ではユークリッド距離を使うことが多い。しかしデータ空間では、ユークリッド距離はあまり使わないし、そもそもmetricでないことも多い。
本論文では\( \phi \)を実現するアルゴリズムについて考えます。
手法は大きく以下に分かれる。
- projection-basedな手法。線型かつmetricなデータに用いる。
- graph-basedな手法. projection-basedの一部とみることもできるし多様体学習の一部とみることもできる。非線形かつmetricなデータに用いる。
- 多様体学習 (のうち、stress-basedな手法)。非線形かつnon-metricなデータに用いる。
2.1 Projection-basedな手法
多次元データを低次元空間に射影する。射影する空間は、そこでの距離が多次元空間のデータ転換の特定の関係を反映するような空間にする。
この定義ではあいまいなので、ここでは、線型の内積変換に基づいて射影する場合を指してprojection-basedと呼ぶ。
その1, PCA (主成分分析)。
下位空間においては、データは直交に射影され、最大の分散を持つ。つまりPCAは、「忠実に」という言葉の意味を、データの分散を最適に捉えるという意味に捉えているわけだ。
PCAは最小二乗誤差 $$ \epsilon_{PCA} = \sum_{i,j} (L_2(x_i, x_j) – L_2(y_i, y_j))^2$$ を最小化していることにもなる。計算もすごく楽。欠点と云えば、非線形データをうまく扱えないことだけだ。
\(X\)が中心化済みであるとして、PCAとは \(x_i\)を\(x_i \hat{\Gamma}\)に変換することだといえる。\( \hat{\Gamma} \)は\(m \times t\)の基底行列で、その列\(t\)は、データの共分散行列\(S = \frac{1}{n} X^\top X\)の\(t\)番目の固有ベクトルである。ランク\(t\)の下位空間に射影した \(\hat{X} = X \hat{\Gamma} \hat{\Gamma}^\top \)は、\(L_2\)の下での最良のランク\(t\)近似となる。
PCAは視覚化だけでなくいろんな用途に用いられている。いろんな変異形もある。
その2, metric MDS。
所与のペアワイズ距離について、それがmetricであると仮定し、その(最小二乗的な意味で)最適な線型フィットを目指す。仮に距離がユークリッド距離ならPCAと同じことになるが、任意のmetricな非類似性に対して最良の線型フィットを目指すので、その意味でPCAより柔軟である。
マッピング誤差は $$ \epsilon_{mMDS} = \sum_{i,j} (x_i x_j^\top – y_i y_j^\top)^2 $$ となる。
ペアワイズのmetric距離の行列を\(\Delta\)とする。その要素を\(\delta_{i,j}\)とする。\(A = -\frac{1}{2}\delta^2_{i,j}\)とする[えええ？ \( (A)_{i,j} = -\frac{1}{2}\delta^2_{i,j} \)じゃなくて?] 中心化行列を\(H\)とする [\(I – \frac{1}{n} I I^\top\)ってことかな]。で、内積のグラム行列 \(G = H A H^\top\)を求める。でもって、こいつをどうにかして固有値分解する。大きいので大変だけど、そこはいろいろ工夫がある。
metric MDSは、\(x_i\)を \(\hat{\Gamma}_i \hat{\Lambda}_i\)に変換することだといえる。\( \hat{\Gamma} \)は\(n \times t\)の基底行列で、その列\(t\)は、グラム行列\(G\)の\(t\)番目の固有ベクトルである。\(\hat{\Lambda}\)は対角行列で、要素は\(G\)の\(t\)番目の固有値の平方根である。
[うーん。このへん写経しちゃったけど、なぜこういう式になるのか、いつかきちんと勉強したいものだ。古典的MDSなんて仕事で使うことはほぼないので、どうしても後回しになっちゃうけど]
MDSでも、点は最大の分散を持つ線形下位空間にマップされる。しかしPCAと違って、その下位空間は内積の\(n \times n\)行列を固有値分解して得たものだ。共分散行列は\(S = \frac{1}{n} X^\top X = cov(X)\)だがグラム行列は\(\frac{1}{n} Cov(X^\top)\)である。つまり、次元の線形結合を反映した基底システムにおいて表現された共分散行列ではなくて、点の線形結合を反映した基底システムにおいて表現された共分散行列である。[なるほど…]
metric MDSは、点が非線形な多様体から得られている場合にどうなるか答えられないし、非類似性がmetricでなかったらどうなるか答えられない。というわけで、Kernel PCAやnon-metric MDSが生まれた。
その3, kernel PCA。[これ projection-based に分類されるのか。へー]
次のように仮定する。(1)データの背後にある特徴量の空間ではデータは線形である。(2)その特徴空間におけるデータ点の内積を近似する関数がある。
(2)の関数をカーネルという。線形のセッティングで非線形カーネルを使って非線形データ構造を捉える、これを人はカーネル・トリックと呼ぶ。ってなわけで、特徴空間へのマッピングを\(\Phi\)とし、カーネルを\((x_i, x_j)\)の\(\Phi(x_i)\Phi(x_j)^\top\)への変換とする。[すでにカーネル法を理解している読者向けの説明だ… 親切心のかけらもないぜ…]
kernel PCAとは、\(x_i\)の\(\hat{\Gamma}_i \hat{\Lambda}\)への変換である。\( \hat{\Gamma} \)は\(n \times t\)の行列で、その列\(t\)は、特徴空間における内積を表すグラム行列\(G^{(k)}\) [\( (G^{(k)})_{ij} = k(x_i, x_j)\)ってっことね] の\(t\)番目の固有ベクトルである。\(\hat{\Lambda}\)は対角行列で、要素は\(G^{(k)}\)の\(t\)番目の固有値の平方根である。
kernel PCAはmetric MDSの一般化といえる。ユークリッド・ドット積のかわりに一般化したドット積を使っているわけである。[←へー]
kernel PCAの弱点は正しいカーネルをどうやってみつけるかがわからんという点である。
2.2 多様体学習
projection-basedの次元縮約がうまくいくのはデータが線形の下位空間で近似できるときだ。そうでないときに残る頼みの綱は、データが少なくとも非線形のパターンに従っている、つまり多様体の上にある、という可能性である。
未知の近接関係を学習する方法は2つある。metricな非類似性に基づく方法とnon-metricな非類似性に基づく方法である。多様体上のmetricな距離をモデル化するためにはふつうgraph-basedの手法が使われる。しかし、どうしてもnon-metricな非類似性を図示しないといけないという応用場面も多い。その場合はgraph-basedアプローチでは歯が立たないので、非凸ストレス関数の最適化を行う。局所最適に捕まるし収束は遅い。
その1、non-metric MDS。
たとえば計量心理的な研究では、非類似性がmetricだという仮定は維持できない。こういうときは非類似行列を固有値分解するのではなくて、非類似性行列に関して \( \epsilon_\phi \) を直接に最小化する。残念ながらストレス関数は非凸になる。
入力を\( \Delta \), 出力を \( Y \), 最適なウェイト行列を \( W \)とする。完全な射影においては \( \epsilon_{MDS}(\Delta, Y, W) = 0 \)である。解を近似するために、$$ Y^{(k+1)} = Y^{(k)} + \alpha^{(k)} \nabla \epsilon_{MDS}(\Delta, Y^{(k)}, W)$$を\(k=0\)から繰り返す。ステップサイズ\(\alpha^{(k)}\)は定数にするなりline searchで決めるなりする。こうすれば、とにかく局所解には辿りつける。問題は解の近傍で収束が遅くなるという点である。それがいやならニュートン法かなにかで解く。
これはnon-metricな非類似性をmetricなターゲット空間にembeddingしているんだけど[←ここの意味がわからない…「埋め込み」と訳する数学用語らしいのだが…]、正確なembeddingは不可能である。non-metric MDSでは、非類似性の順位の保持だけを目指す。有名なのがShepard-Kruskalのアルゴリズムで、まずnon-metricな入力の順位を保持する単調変換をみつけ、出力の布置を修正するというのを繰り返して、ストレスと単調性のバランスをとる。[そうそう、そうだった。ああ、思い起こせば若かりし頃、N88 BASICで非計量MDSのプログラムを書いたものだった… なにやってたんだろう俺… 同世代の若者はもっとましな勉強をしたりスポーツしたりデートしたりセックスしたりしてただろうに… ]
その2、Isomap。[ようやくこの論文をめくっている目的に近づいてきた… 長かった…]
ターゲット空間への直接的な埋め込みを学習するのではなくて、geodesic距離[グラフでいうと最短パスのことらしい。多様体上でもなんか定義できるんでしょうね]の観点から、非線形的な近接関係を明示的にモデル化する。metric MDSでのmetric距離をgeodesic距離に置き換えたようなものである。
geodesic距離をどうやって学習するかというと、データ点をノード、ノードあたりk個の最近隣関係をエッジ、非類似性をエッジのウェイトにとった無向グラフをつくる。ウェイトは多様体上のgeodesic距離のローカルな近似になっている。でもって、ノード間の二乗geodesic距離行列をつくる。ここからはmetric MDSと同じ。
問題は、二重中心化したグラム行列が半正定値じゃないかもしれないという点[そりゃそうかもな…]。解決する方法のひとつがMaximum Variance Unfolding (MVU)で、近隣点の間の局所的な距離を保存するという制約の下で多様体をunfoldするというのが基本的アイデアである[←さっぱりわからん…]。
metric MDSと同じく、\(n \times n\)行列を固有値分解する羽目になるというのも弱点。これにも解決策の提案がある。
その3. Locally Linear Embedding [LLE]。
さっきのはglobalなgeodesic距離でもって多様体をモデル化しようとしていたが、今度は、局所的でintrinsicなgeometryを抽出することによって多様体をモデル化する[←???]。
データ\(x_i\)の近隣を\(N_i\)として、$$ x_i = \sum_{x_j \in N_i} W_{ij} x_j$$ ただし \( 0 \leq W_{ij} \leq 1, \ \sum_{x_j \in N_i} W_{ij} = 1, \ W_{ii} = 0 \), がすべてのデータ点について成り立つと仮定する。[←あーなるほど… どの点も、その近隣点をうまく重みづけた平均だと考えるわけね。これがlocal intrinsic geometryか…]
k-近隣グラフに基づき、\(W\)についての上の制約のもとで \( \sum_i^n || x_i – \sum_j^n W_{ij}x_j|| \)を最小化する\(W\)を求める。でもって、\( \sum_i^n || y_i – \sum_j^n W_{ij}y_j|| \)を最小化する\(y_j\)を求める。[←おもしれえええええ！なにこれ超おもしろいじゃんか！]
Isomapと同じく、これも\(W\)の固有値分解で解ける。\(W\)はスパースなので計算はすごく速い。
3. 最近のトピック
graph-basedとstress-basedからそれぞれ重要なのをひとつ紹介しよう。
3.1 Piecewise Laplacian-based Projection (PLP)
LLEと同じく、すべてのデータ点が、近隣の点の凸結合[係数がみな非負で和が1になる線形和のことらしい]で近似できると仮定する。しかしLLEとはちがって、あらかじめウェイトを次のように決めてしまう: $$ W_{ij} = \frac{1}{\delta_m(x_i, x_j)} / \sum_{x_k \in N_i} \frac{1}{\delta_m(x_i, x_j)} $$ ただし\(\delta_m\)はデータ空間上のmetric距離。
手順は次の通り。
- \(X\)を\(S_1, S_2, …, S_s\)に分割する。\(s\)は\(\sqrt{n}\)を超えない最大の整数。
- それぞれの\(S_j\)において、そこに属する\(x_i\)の近隣\(N_i\)を決める。また、control点の集合\(C_j\)をランダムにきめる決める。
- すべてのcontrol点を集めて、ターゲット空間に射影する。ここはたとえばstress-basedでよい。
- \(S_j\)ごとに別々に、\(C_j\)と\(N_i\)に基づく局所線形システムを構築して解く。
- 出来上がった\(Y\)をユーザにみせて、気に入るように点を動かしてもらう。で、Step 3からやりなおす。
[いやあ、変なことを考えるなあ… 面白そうだけど、具体的にはどういう応用場面があるんだろうか？]
3.2 Multigrid Multidimentional Scaling (MG-MDS)
MDSと同じく\(\epsilon_\phi\)を直接に最適化する。距離はmetricであることを求める。\(W\)はなにも制約せず、\( \epsilon(\phi(X); \Delta, W) \)を最小化する\(\phi\)を求めるのではなくて、0にする\(\phi\)を求める。
[具体的な手順が書いてあるんだけど、これが結構めんどくさい… 最初にデータ点の階層をつくっておいて逐次的に計算していくのだとかなんとか… たぶん死ぬまで使わないと思うし、力尽きたのでスキップ]
3.3 比較
[PLPとMG-MDSをいろんな観点から比較している。メモ省略]
4. 結論
現在の研究のモチベーションとして、複雑な非線形geometryを持つ多様体、より柔軟でインタラクティブなembedding, 情報のよりよい符号化、スケーラビリティ、がある。最新の手法では、マッピングと視覚化にユーザの知識を統合する半教師つき学習の方向へと焦点が移っている。云々。
…やれやれ、終わった… 求めていた内容とちょっと違ったけど、Locally Linear Embeddingというのがやたらに面白かったので良しとしよう。
えーっと、Rのパッケージでいうと、IsomapはdimRed, RDRToolBox, Rdimtoolsに載っている(ほかにもあるかもしれない)。LLEはlleというパッケージがあるしdimRedでもできるようだ。PLPはRdimtoolsに載っている模様(こんど試してみよう)。MG-MDSは… ちょっと探した限りにおいてはみつけられなかった。