Week 05: Nonlinear dimensionality reduction by locally linear embedding

題目：Nonlinear Dimensionality Reduction by Locally Linear Embedding

作者：Sam T. Roweis, Lawrence K. Saul

文章概要：

          本篇文章主要目的是用更緊湊的方式表現高維資料，從而實現降維的目的。如圖1所示，將這種方法作者稱為locally linear embedding（LLE），它是一種unsupervised的方法，將高維度的輸入用低維度、較緊湊的方式表達。此處需要注意的是，它是一種降維的方法，不是clustering的方法。

圖1 LLE圖示

主要算法：

          Locally Linear Embedding的方法主要分為以下3個部份：

       （1）對每個資料點assign 鄰居點，比如使用 nearest neighborhoods；

       （2）找出最好的weight reconstruct 每個點，使得公式1取得最小值；

       （3）將以上尋找到的X映射到可以最小化公式2的低維度Y。

          算法流程如圖2所示。

圖2  算法流程圖

實驗結果：

        文章利用人臉特徵和文字特徵進行降維，來說明降維效果。圖3與圖4顯示了將人臉和文字降為二維並且顯示出了很好的效果，可以看出相同語義和類似表情的文字和人臉二維距離很近，達到了降維的效果。

圖3  人臉降維示例圖

圖4  文字降維示例圖

創新之處和心得：

         本文出發點在於面對日益複雜和龐大的科學數據，維度龐大是一個日益嚴重的問題，它影響學習知識的速度，在儲存方面也遇到很多問題。所以本文的提出對於降低特徵維度但不影響正確率很有影響，是一篇非常經典的文章。