Nonlinear Dimensionality Reduction by Locally Linear Embedding

承上篇文章，我們往往會將一個複雜的資訊用一個高維的空間中的點加以表達。
而我們常常會遇到需要將維度加以減少的情況，
如下圖所示

這篇PAPER提出了一個 Locally Linear Embedding的方法，
可以避免計算距離過遠的兩個點的距離。



而LLE的大致過程我們可以由下圖表達

首先，我們對點選取特定數量的鄰居(通常用KNN)，
接著，設法利用這些選定的鄰居線性組合出i這個點，
也就是最小化下式

值得注意的是，如果j點並非i的鄰居，那他們之間的權重即為0，
另外一個是，我們加入了下式的限制。

而minimize這個的過程，也就等同於解least-squares problem，



值得一提的是，這樣提出來的組合，
在縮放，旋轉，變形之下，都是保持穩定的。



接著，我們設法將這樣的線性組合關係映射到低維度的空間中，
也就是minimize下面的式子

同樣的，這樣的問題也可以表達成quadratic 的形式，
更明確的說，我們可以利用解疏矩陣的eigenvalue來找到解。



LLE這個方法有一些其他方法所缺乏的特點，

最顯而易見的就是，不同於一些其他的方法需要大量參數，
他只有一個參數，也就是KNN的K

另外一個則是，LLE可以較輕易的達到global optimality

接著，由於LLE在區域性結構的穩定性，'當我們所映射到的子空間維度提升時，
我們不需要重新處理原先高維度的空間中的資料

最後，由於避免掉了計算兩點間的距離，
LLE也可以避免掉計算高維的DP所花費的時間。