Helve’s Python memo

Pythonを使った機械学習やデータ分析の備忘録

LLE (Locally Linear Embedding) による非線形データの次元削減

LLE (Locally Linear Embedding) は、非線形データを対象とする次元削減手法の1つである。
本記事では、LLEのアルゴリズムについて解説する。

目次

はじめに

次元削減 (dimensionality reduction) とは、データの構造をなるべく保ったまま、特徴量の数を減らすことである。
特徴量の数を減らすことにより、機械学習を高速に実行できたり、データの可視化をしやすくなる利点がある。

次元削減には、射影と多様体学習という2つの主なアプローチがある。
射影を使った手法としては、主成分分析 (PCA, Principal Components Analysis) が有名である。
一方、本記事で扱うLLEは、多様体学習と呼ばれるアプローチに属する。

多様体

多様体 (manifold) とは、簡単に表すと、局所的に低次元の超平面と見なせる図形のことである。
例えば、以下に示すSwiss Rollは、3次元空間のデータであるが、局所的には2次元の平面と見なせる。
すなわち、データから2次元平面をうまく見つけることができれば、構造を保ったまま3次元から2次元に圧縮できる。

f:id:Helve:20190922134756p:plain

このように、多様体のモデルを見つけることを多様体学習と呼ぶ。
多様体学習には、以下のように様々な手法がある。

  • LLE
  • 多次元尺度法 (multi-dimensional scaling, MDS)
  • Isomap
  • t-SNE (t-distributed Stochastic Neighbor Embedding)
  • UMAP (Uniform Manifold Approximation and Projection)

LLEには、大域的な位置関係を保存できる長所がある。
一方、以下の短所もある。

  • 多様体が複数ある場合、互いの位置関係をうまく保存できない。
  • 圧縮後のデータ位置を再構成する計算量がデータ数の2乗に比例するため、大規模なデータに適用しづらい。

LLEアルゴリズム

LLEのアルゴリズムは、2つのステップでデータ間の局所的な線形モデルを構築し、次元を削減する。

  1. 局所的な関係の線形モデル化
  2. 関係を維持した次元削減

局所的な関係の線形モデル化

まず、データの各インスタンスに対して、近傍にあるk点のインスタンスを探し、それらインスタンスの線形結合で表すことを考える。
ただし、kはハイパーパラメータである。

例として、下図のように2次元空間において5つの点A~Eが与えられた場合に、
点Cを近傍インスタンスの線形和として表すことを考える。
k=2とすると、点Cの近傍インスタンスは点B, Dである。
また、点B, C, Dの位置は\boldsymbol{x^{(B)}, x^{(C)}, x^{(D)}}で与えられるとする。

f:id:Helve:20190922134832p:plain

次に、\boldsymbol{x^{(B)}, x^{(D)}}の線形結合として次式を考える。
w_{C, B}\boldsymbol{x^{(B)}} + w_{C, D}\boldsymbol{x^{(D)}}
ただし、w_{C, B}, w_{C, D}は点Cに対する点B, Dの重み係数である。
また、
w_{C, B}+w_{C, D}=1
である。

さらに、点Cを点B, Dの線形結合で近似するため、次式が最小となるw_{C, B}, w_{C, D}を求める。
\boldsymbol{x^{(C)}} - (w_{C, B}\boldsymbol{x^{(B)}} + w_{C, D}\boldsymbol{x^{(D)}})
\mathrm{subject\ to\ } w_{C, B}+w_{C, D}=1

下図は、上記の考えを幾何的に示したものである。
図の点B, Dを結ぶ破線は、\boldsymbol{x^{(B)}, x^{(D)}}の線形結合を表す。
また、求める係数w_{C, B}, w_{C, D}は、
w_{C, B}\boldsymbol{x^{(B)}} + w_{C, D}\boldsymbol{x^{(D)}}
と、
\boldsymbol{x^{(C)}}
の距離を最小とする値となる。

f:id:Helve:20190922134853p:plain

以上、ある点に対する線形モデル化を示したが、全ての点に対して一般化した式を示す。
インスタンスの数をNとして、重み係数を行列W\in\mathbb{R}^{N\times N}にまとめる。
重み係数w_{i,j}W(i,j)成分とする。
このとき、線形モデル化とは、次式を最小化する重み行列Wを求める問題となる。
\displaystyle \sum_{i=1}^{N} \left( \boldsymbol{x^{(i)}} - \sum_{j=1}^{N} w_{i,j} \boldsymbol{x^{(j)}} \right)^2
\displaystyle \mathrm{subject\ to\ } 
\begin{cases}
    \sum_{j=1}^{N} w_{i,j} = 1 & (\mathrm{for\ } i=1,2,...,N) \\
    w_{i,j} = 0                & (\boldsymbol{x^{(j)}} が \boldsymbol{x^{(i)}} の近傍点ではない)
\end{cases}

関係を維持した次元削減

前節で得られた重み行列Wを用いて、データの局所的な関係をなるべく維持できるように、圧縮後の次元におけるインスタンスの位置を求める。
圧縮後のインスタンスの位置を\boldsymbol{y^{(i)} (i=1,2,...,N)}とする。
ただし、\boldsymbol{y^{(i)}}の次元は\boldsymbol{x^{(i)}}の次元より小さくなければならない。
このとき、\boldsymbol{y^{(i)}}は次式を最小化する値として得られる。
\displaystyle \sum_{i=1}^{N} \left( \boldsymbol{y^{(i)}} - \sum_{j=1}^{N} w_{i,j} \boldsymbol{y^{(j)}} \right)^2

先程の例の続きで説明する。
2次元空間上の点B, C, Dの位置\boldsymbol{x^{(B)}, x^{(C)}, x^{(D)}}を1次元空間に圧縮するものとして、圧縮後の位置を\boldsymbol{y^{(B)}, y^{(C)}, y^{(D)}}とする。
得られた重み係数w_{C, B}, w_{C, D}を用いると、\boldsymbol{y^{(B)}}の最適な位置は次式で与えられる(下図参照)。
w_{C, B}\boldsymbol{y^{(B)}} + w_{C, D}\boldsymbol{y^{(D)}}


f:id:Helve:20190922135022p:plain

参考

LLEについて、以下のウェブサイトと書籍を参考にさせて頂いた。
書籍では、次元削減アルゴリズムおよびscikit-learnにおける実装について1章(約20ページ)割かれており、次元削減の概要をつかむのに良いと思う。

【多様体学習】LLEとちょっとT-SNE - HELLO CYBERNETICS

※Adblockが有効の場合やモバイル版ページでは、シェアボタンをクリックできません