「確率的機械学習入門編II」を読む　～第20章次元削減 ⑥多様体学習(LLEなど)～

はじめに

持橋大地・鈴木大慈監訳「確率的機械学習入門編II」は，世界的に評価の高いK.P.Murphy著 "Probabilistic Machine Learning (Book1)" の和訳であり，確率モデルに基づく機械学習，深層学習といった基礎が丁寧に整理されている。

本記事は，「第20章次元削減」の多様体学習における，最大分散展開・局所線形埋め込み・ラプラシアン固有写像・t-SNEなどに関する読書メモである。

20.4　多様体学習

20.4.7　最大分散展開（MVU）

カーネル主成分分析では，動径基底関数カーネルなどを用いると，低次元埋め込みにならなかった。

この対策として，最大分散展開(maximum variance unfolding)では，潜在空間の多様体を伸ばすように，埋め込みを学習する。

$\begin{align} &\max \sum_{i, j} \lVert \mathbfit{z}_i - \mathbfit{z}_j \rVert_2^2 \\ \\ &\mathrm{s.t.} \quad \lVert \mathbfit{z}_i - \mathbfit{z}_j \rVert_2^2 = \lVert \mathbfit{x}_i - \mathbfit{x}_j \rVert_2^2 \quad \text{for all $(i, j) \in G$} \\ \\ \end{align}$

ここで， $G$ は近傍グラフである。近傍のみの距離が保存されるよう制約をおきつつ，潜在空間ではデータ間の距離が最大化されるように学習される。
学習の際には半整定値計画の問題として扱われる。

20.4.8　局所線形埋め込み

局所線形埋め込み(locally linear embedding)は，疎な固有値問題を用いる手法であり，データの局所的な構造により焦点を当てる手法となる。

局所線形埋め込みでは，データ多様体が各点 $\mathbfit{x}_i$ の周りで局所的に線形であると仮定し，次の最適化問題を解くことで再構成重み $\mathbfit{W}$ を計算する。

$\begin{align} &\hat{\mathbfit{W}} = \min_{\mathbfit{W}} \sum_{i=1}^N \left( \mathbfit{x}_i - \sum_{j=1}^N w_{ij} \mathbfit{x}_j \right)^2 \\ \\ &\mathrm{s.t.} \begin{cases} w_{ij} = 0 & (\mathbfit{x}_j \notin \mathrm{nbr}(\mathbfit{x}_i, K)) \\ \\ \sum_{j=1}^N w_{ij} = 1 \\ \end{cases} \\ \\ \end{align}$

●ブログ筆者註 :
特に説明がなかったが， $\mathrm{nbr}(\mathbfit{x}_i, K)$ は $\mathbfit{x}_i$ の $K$ 近傍であると思われる。

低次元埋め込みを求めるための損失関数は，この重みを用いて，

$\begin{align} \mathcal{L}(\mathbfit{Z}) = \lVert \mathbfit{Z} - \mathbfit{W} \mathbfit{Z} \rVert^2 = \mathbfit{Z}^T (\mathbfit{I} - \mathbfit{W})^T (\mathbfit{I} - \mathbfit{W}) \mathbfit{Z} \\ \\ \end{align}$

と書き表せる。

この解は， $(\mathbfit{I} - \mathbfit{W})^T (\mathbfit{I} - \mathbfit{W})$ の，小さい順に取った非ゼロ固有値に対応する固有ベクトルによって与えられる。

https://github.com/probml/pml-book/releases/latest/download/book1.pdf のFigure 20.37から引用

20.4.9　ラプラス固有写像

ラプラス固有写像(Laplacian eigenmap)あるいはスペクトル埋め込みは，各データ点とその $K$ 近傍の間の重み付き距離が最小化されるように，データの低次元表現を計算する。

グラフラプラス作用素の固有ベクトルを用いた埋め込み計算

ラプラス固有写像では，以下の損失関数を最小化する埋め込みを見つける。

$\begin{align} &\mathcal{L}(\mathbfit{Z}) = \sum_{(i, j) \in E} W_{i, j} \lVert \mathbfit{z}_i - \mathbfit{z}_j \rVert_2^2 \\ \\ &W_{i, j} = \begin{cases} \exp \left( -\frac{1}{2 \sigma^2} \lVert \mathbfit{x}_i - \mathbfit{x}_j \rVert_2^2 \right) & (\text{$i$と$j$が近傍}) \\ \\ 0 & (\text{otherwise}) \\ \end{cases} \\ \\ \end{align}$

これを，制約 $\mathbfit{Z}^T \mathbfit{D} \mathbfit{Z} = \mathbfit{I}$ のもとで最小化する。ただし $\mathbfit{D}$ は対角の重み行列である。

損失関数は，次のように書き直せる。

$\begin{align} \mathcal{L}(\mathbfit{Z}) &= \sum_{(i, j) \in E} W_{i, j} \lVert \mathbfit{z}_i \rVert_2^2 + \lVert \mathbfit{z}_j \rVert_2^2 - 2 \mathbfit{z}_i^T \mathbfit{z}_j \\ \\ &= 2\mathrm{tr} (\mathbfit{Z}^T \mathbfit{D} \mathbfit{Z}) - 2\mathrm{tr} (\mathbfit{Z}^T \mathbfit{W} \mathbfit{Z}) = 2\mathrm{tr} (\mathbfit{Z}^T \mathbfit{L} \mathbfit{Z}) \\ \\ \end{align}$

ここで， $\mathbfit{L} = \mathbfit{D} - \mathbfit{W}$ はグラフラプラス作用素である。

これを制約条件のもと最小化するのは，一般化固有値問題 $\mathbfit{L} \mathbfit{z}_i = \lambda_i \mathbfit{D} \mathbfit{z}_i$ と等価である。

●ブログ筆者註 :
グラフラプラス作用素(グラフラプラシアン)の説明は，以下の過去記事に記載した。
stern-bow.hatenablog.com

20.4.10　t-SNE

SNE

確率的近傍埋め込み(stochastic neighbor embedding, SNE)は，高次元空間における類似度(条件付き確率) $p_{j|i}$ と低次元空間における類似度(条件付き確率) $q_{j|i}$ が近づくように埋め込みを求める。

高次元空間における類似度(条件付き確率) $p_{j|i}$ と低次元空間における類似度(条件付き確率) $q_{j|i}$ は，それぞれ

$\begin{align} p_{j|i} &= \frac{ \exp \left( -\frac{1}{2 \sigma_i^2} \lVert \mathbfit{x}_i - \mathbfit{x}_j \rVert^2 \right) }{ \sum_{k \neq i} \exp \left( -\frac{1}{2 \sigma_i^2} \lVert \mathbfit{x}_i - \mathbfit{x}_k \rVert^2 \right) } \\ \\ q_{j|i} &= \frac{ \exp \left( - \lVert \mathbfit{z}_i - \mathbfit{z}_j \rVert^2 \right) }{ \sum_{k \neq i} \exp \left( - \lVert \mathbfit{z}_i - \mathbfit{z}_k \rVert^2 \right) } \\ \\ \end{align}$

で表される。

目的関数は，

$\begin{align} \mathcal{L}(\mathbfit{Z}) = \sum_i D_{\mathbb{KL}} (P_i \mid\mid Q_i) = \sum_i \sum_j p_{j|i} \log \frac{p_{j|i}}{q_{j|i}} \\ \\ \end{align}$

というKLダイバージェンスとなる。

t分布確率的近傍埋め込み

確率的近傍埋め込みでは，高次元空間では比較的遠くにある点が，低次元の埋め込み空間では近くにまとめられるという問題がおきる。

この対策の1つが，潜在空間の確率分布をより重い裾を持つ分布にするというものである。t-SNEでは，潜在空間の類似度にスチューデントのt分布を用いる。

$\begin{align} q_{j|i} &= \frac{ \left( 1 + \lVert \mathbfit{z}_i - \mathbfit{z}_j \rVert^2 \right)^{-1} }{ \sum_{k \lt l} \left( 1 + \lVert \mathbfit{z}_k - \mathbfit{z}_l \rVert^2 \right)^{-1} } \\ \\ \end{align}$

t-SNEに類似した手法として，UMAP(Uniform Manifold Approximation and Projection)があるが，t-SNEより高速である。

まとめと感想

今回は，「第20章次元削減」の多様体学習における，最大分散展開・局所線形埋め込み・ラプラシアン固有写像・t-SNEなどについてまとめた。

本節で登場した手法を整理すると，以下のようになる。

手法	特徴
MDS	距離保存
Isomap	測地距離保存
Kernel PCA	カーネル非線形
MVU	多様体展開
LLE	局所線形構造
ラプラス固有写像	グラフラプラシアン
t-SNE	確率近傍