aMMAI: [aMMAI] Paper Summary: Nonlinear dimensionality reduction by locally linear embedding

Title: Nonlinear dimensionality reduction by locally linear embedding

Author: Roweis & Saul

Publication: Science, 2000

在描述真實世界中的物件時，通常都是使用高維的向量來表示。

維度越高，處理起來會有很多問題，因此就會想要做降維。

在原本物件的結構上，比較相近的點會有一些關聯性(例如:影像中相鄰的像素不會差太多)。

這邊paper提出一個unsupervised learning algorithm的非線性降維方法，稱做locally linear embedding (LLE)，降維的過程中，空間上每一點保留與原本鄰近點的相關性，這些鄰近點不會因為位移或旋轉而改變，如下圖所示。

圖B中所表示的是在三維空間中的點，我們希望將他降維乘如圖A所表示的二維空間形式，其中圖上顏色越相近的表示他們是越相近的點。

LLE的降維方式不同於PCA或是傳統的MDS，會在降維過程中將原本相近的點map到不同的平面上，如下圖，有些顏色不相似的點混在一起。

LLE降維過程主要有三個步驟，如下圖所示。

假設空間中有N個點，每個點都有D個維度，用向量X_i表示。

Step 1:

先找出原本空間中每個點的鄰居。

Step 2:

藉由該點四周圍的鄰居重建出這一點。

重建的過程中，需要最小化cost function (1)。

X_i表示原本的點，總合W_ijX_j表示由j個點重建出來的X_i。

這個cost function需要滿足兩個限制:

1. 每個點只有用那一點的鄰居來重建，如果W_ij等於零，表示j點不是i點的鄰居。

2. Weight matrix總和必須等於零。

Step 3:

要將原本高維的向量X對應到低維向量Y中，首先要先建立出Y的向量空間。

我們利用前面的weight W來建立出Y的向量空間，藉由最小化cost function (2)來達到。

由於weight已經固定，利用解eigenvalue，取eigenvalue最小的d個eignevector做為Y向量空間的orthogonal coordinates。

LLE的優點是，只需要評估K(鄰居數量)這個參數，沒有很多參數須要做調整。

LLE可以應用在很多方面上，paper中舉了人臉與文字語意的例子，下面是該例子的例圖

PCA與LLE降維步驟這兩張圖來自這份投影片:

aMMAI