Manifold Methods

Nonlinear dimensionality reduction by locally linear embedding

Summary:
作者提出了一個利用locally linear embedding的方式，透過保存local geometry的方式，將data point投影到一個比原來維度D還低的d維度空間上，就可以做到nonlinear dimensionality reduction的效果。
其作法如下:
1. 對於每個data point(Xi)，找出最接近此點的K個nearest point，找出一組係數Wij，使得Σj|Wij| = 1且讓cost function:Σi|Xi - ΣjWijXj |^2極小化。
2. 有了這組linear weights之後，接下來要解如何將D維的Xi投影到d維的Yi上，其cost function為Σi|Yi - ΣjWijYj |^2，可將其視為一個解NxN的eigenvalue problem，就可得到符合cost minimization的解。
作者還用此方法對著臉的照片以及word-document count去作實驗，也證明了此種方法可以將臉的表情變換投影到一個二維的low dimension座標系上的轉換，並且可在轉換路徑上看到表情的逐漸變換；而在文字上作實驗的結果上來看，也可以看出此方法成功的將意義相關的字投影到距離較短的分布上。

Critiques:
這篇提到了利用LLE作nonlinear dimensionality reduction的方法，而最近由於本身研究的關係，看到了一些作spectral clustering的方法，其方法也是類似利用affinity matrix(對graph中每個vertex都有連結或是類似bilateral filter的限制來建立)，再對此一個affinity matrix去求其eigevector的解，而對前幾大的eigenvalue對應到的eigenvector值去作K-means clustering就可做到分群的效果，此一方法也是可以做到manifold dimensionality reduction的效果。此外，在 “Diffusion Maps and Coarse-Graining: A Unified Framework for Dimensionality Reduction, Graph Partitioning, and Data Set Parameterization’’. IEEE Trans. on Pattern Analysis and Machine Intelligence(2006). 中還提到了如何利用diffusion map來作有關分群、降維的動作，有興趣的人可以參考一下。