Nonlinear Dimensionality Reduction by Locally Linear Embedding

Nonlinear Dimensionality Reduction by Locally Linear Embedding


Sam T. Roweis and Lawrence K. Saul
SCIENCE   VOL 290   22 DECEMBER 2000
======================================================

這篇paper提出一個方法可以在做dimension reduction 的時候
還能夠保有原先相近的neighbors

因為做完dimension reduction 原先很遠的point 有可能變到很近
這樣就會造成distance distortion
這篇的方法就是把每個 point 利用neighbor 來表示
主要可以分為以下三個步驟：

1. K nearest neighbor
2. 找出這些neighbor的weight
3. 組成 low dimension embedding vector

1. K nearest neighbor:
這部分在很多相關的paper都有提到
這篇沒有特別詳述
不過這裡要找的是each point 的 exactly K nearest
不是 K-centroid 或是 K nearest-approximate

2. 找出這些neighbor的weight:
K neighbors 用 linear 的方式組起來，總和為1
這些weight求解是least sqaure problem 
paper裡還有提到這樣的解法可以invariant to rotation, scaling, translation

3. 組成 low dimension embedding vector
最後假設要降成 d dimension
列出跟 2. 一樣的embedding cost function
這裡的解法是 NxN eigenvalue problem

paper裡提到以上的步驟裡唯一的變數是 K
一旦K決定了之後，剩下的東西都可以按照optimize 來求解
(d應該是User自己決定要用多少，但對每個point來說  K有可能不同
每個point 要用怎樣的K 才是問題，因此才是唯一的變數)

paper裡也提到很多algorithm
(ex: neural networks, self-organizing maps, latent variable models)
幾乎都有很多要set 的變數
而且也不能保証會 global convergence
這篇paper 提出的LLE 可以保証 global convergence
也就是不用set 變數  求出來的解會一致

實驗的部分 有提供兩個實驗
1. 用sequential face 表情變換 project 到2d 圖上，
然後找出它們的transfer path
這樣就可以証明相似的neighbor 會在附近 不會亂跳

2. 把term word project 到 2d semantic meaning map上
意思相近的term 就會在附近
這個map 的意義比較抽象

======================================================

優點：
1. paper 寫得很簡潔，一看就懂，figure 2 一張圖就可以把全部過程表達清楚
2. 方法很簡單，也很make sense，可以應用的地方很多
3. problem solving 都有對應的解法，解出來的答案會converge
4. 變數幾乎沒有(只要找每個K)，不用一些ad-hoc 的setting
5. 兩個實驗都很有創意，比起一般的perfomance showing 來得有意思

缺點：
1. KNN 那裡要找每個point 的 K neighbor，這裡會很耗時間
2. 第二個實驗的結果好像有些部分不是很好，但paper裡沒解釋