LLE (Locally Linear Embedding) は、非線形データを対象とする次元削減手法の1つである。
本記事では、LLEのアルゴリズムについて解説する。
目次
はじめに
次元削減 (dimensionality reduction) とは、データの構造をなるべく保ったまま、特徴量の数を減らすことである。
特徴量の数を減らすことにより、機械学習を高速に実行できたり、データの可視化をしやすくなる利点がある。
次元削減には、射影と多様体学習という2つの主なアプローチがある。
射影を使った手法としては、主成分分析 (PCA, Principal Components Analysis) が有名である。
一方、本記事で扱うLLEは、多様体学習と呼ばれるアプローチに属する。
多様体
多様体 (manifold) とは、簡単に表すと、局所的に低次元の超平面と見なせる図形のことである。
例えば、以下に示すSwiss Rollは、3次元空間のデータであるが、局所的には2次元の平面と見なせる。
すなわち、データから2次元平面をうまく見つけることができれば、構造を保ったまま3次元から2次元に圧縮できる。
このように、多様体のモデルを見つけることを多様体学習と呼ぶ。
多様体学習には、以下のように様々な手法がある。
- LLE
- 多次元尺度法 (multi-dimensional scaling, MDS)
- Isomap
- t-SNE (t-distributed Stochastic Neighbor Embedding)
- UMAP (Uniform Manifold Approximation and Projection)
LLEには、大域的な位置関係を保存できる長所がある。
一方、以下の短所もある。
- 多様体が複数ある場合、互いの位置関係をうまく保存できない。
- 圧縮後のデータ位置を再構成する計算量がデータ数の2乗に比例するため、大規模なデータに適用しづらい。
LLEアルゴリズム
LLEのアルゴリズムは、2つのステップでデータ間の局所的な線形モデルを構築し、次元を削減する。
- 局所的な関係の線形モデル化
- 関係を維持した次元削減
局所的な関係の線形モデル化
まず、データの各インスタンスに対して、近傍にあるk点のインスタンスを探し、それらインスタンスの線形結合で表すことを考える。
ただし、kはハイパーパラメータである。
例として、下図のように2次元空間において5つの点A～Eが与えられた場合に、
点Cを近傍インスタンスの線形和として表すことを考える。
k=2とすると、点Cの近傍インスタンスは点B, Dである。
また、点B, C, Dの位置はで与えられるとする。
次に、の線形結合として次式を考える。
ただし、は点Cに対する点B, Dの重み係数である。
また、
である。
さらに、点Cを点B, Dの線形結合で近似するため、次式が最小となるを求める。
下図は、上記の考えを幾何的に示したものである。
図の点B, Dを結ぶ破線は、の線形結合を表す。
また、求める係数は、
と、
の距離を最小とする値となる。
以上、ある点に対する線形モデル化を示したが、全ての点に対して一般化した式を示す。
インスタンスの数をとして、重み係数を行列
にまとめる。
重み係数を
の
成分とする。
このとき、線形モデル化とは、次式を最小化する重み行列を求める問題となる。
参考
LLEについて、以下のウェブサイトと書籍を参考にさせて頂いた。
書籍では、次元削減アルゴリズムおよびscikit-learnにおける実装について1章（約20ページ）割かれており、次元削減の概要をつかむのに良いと思う。
