鄰域保持嵌入（NPE）

• 2019 年 10 月 3 日
• 筆記

傳統的線性降維方法，如主成分分析（PCA）、因子分析（FA）等，關注的是樣本的方差，能學習線性流形的結構，卻無法學習非線性流形。而經典的流形學習方法雖然能夠學習非線性流形結構，但由於本身屬於直推學習，無法進行新樣本的泛化。另外一些基於核函數的降維方法，如KPCA，儘管可以處理非線性問題，但又忽略了流形的非線性結構。

NPE 作為局部線性嵌入（LLE）算法的線性逼近，它不僅能夠捕捉流形的非線性結構，還保留了線性性質，能夠進行新樣本的泛化。因此，NPE 在效果令人滿意的同時，還能夠輕鬆應對新樣本，在工業上得到了廣泛的應用。

至於流形的問題，如流形是什麼，為什麼學習流形，可閱讀我之前的博客「學習流形」的初認識。

NPE 算法思想及步驟

NPE 的思想和LLE相同，主要是在降維過程中保持流形的局部線性結構不變，從而來提取數據中的有用信息。這裡的局部線性結構是通過重構權重矩陣來表徵的，而重構權重矩陣就是鄰域內鄰居點對結點的線性重構的係數矩陣。

和其他經典流形學習算法類似，NPE 的算法步驟主要分為三步：

1. 構建鄰域圖

利用 K 最近鄰（KNN）算法來構建鄰域圖。假設共有 m 個樣本，則鄰域圖共有 m 個結點，其中 ( mathbf{x} _ {i} ) 表示第 i 個結點。如果 ( mathbf{x} _ {j} ) 是 ( mathbf{x} _ {i} ) 的 k 個最近鄰居之一，那麼將這兩點連接，反之不連接。

2. 計算權重矩陣（提取流形特徵）

設權重矩陣為 (mathbf{W})，其中元素 (W _{ij})代表結點 i 和結點 j 之間的邊的權重，如果兩點之間沒有變，則對應的矩陣元素為 0。矩陣 (mathbf{W}) 的元素值主要通過最小化如下目標函數得到：

[ min sum _{i} left| left| mathbf{x} _{i} – sum _{j} W _{ij} mathbf{x} _{j} right| right| ^{2}, ]

其中 (mathbf{W}) 應滿足歸一化約束：

[ sum _{j} W _{ij} = 1,j=1,2,…,m. ]

3. 計算映射

通過求解廣義特徵向量問題來計算降維的線性映射：

[ mathbf{XMX} ^{T} mathbf{a}=lambda mathbf{XX} ^{T} mathbf{a}, ]

其中數據集 ( mathbf{X} = ( mathbf{x} _ {1},…,mathbf{x} _ {m} ) )，矩陣 ( mathbf{M} = ( mathbf{I} – mathbf{W} ) ^{T} ( mathbf{I} – mathbf{W} ) )，矩陣 ( mathbf{I} = diag(1,…,1) )。

按特徵值從小到大的次序（ ( lambda _ {0} leq …leq lambda _ {d-1} ) ）將求解到的特徵向量進行排列 ( mathbf{a} _ {0},…, mathbf{a} _ {d-1} )，這樣降維後的嵌入坐標則為：

[ mathbf{y} _ {i} = mathbf{A} ^{T} mathbf{x} _ {i}, ]

其中

[ mathbf{A} = ( mathbf{a} _{0}, mathbf{a} _{1},…,mathbf{a} _{d-1} ). ]

NPE算法推導

NPE 算法主要是先提取流形的局部線性信息，然後通過保留這種信息來實現降維。具體來說，NPE 首先用局部的線性重構來表示流形局部的線性結構，其形式為均方差。設定樣本數為 m ，維數為 n，降維後維數為 d，(mathbf{Q} (i)) 為樣本 i 的 k 個近鄰樣本集合，則在高維空間中表徵重構誤差的目標函數為：

[ phi ( mathbf{W} ) = sum ^{m} _{i=1} left| left| mathbf{x} _{i} – sum _{jin mathbf{Q}(i)} W _{ij} mathbf{x} _{j} right| right| ^{2}, ]

由優化目標函數得來的矩陣 (mathbf{W}) 便包含了流形的局部信息。在降維的過程中，NPE 在參數空間（降維後的低維空間）中以保留和高維原始空間相同的局部線性重構為目標（即在目標函數中使用相同的權重矩陣 (mathbf{W}) ），來實現線性降維，其低維空間的目標函數為：

[ Phi ( mathbf{y} ) = sum ^{m} _{i=1} left| left| y _{i} – sum ^{m} _{j=1} W _{ij} y _{j} right| right| ^{2}. ]

NPE 的算法推導主要分為兩步，一是計算權重矩陣，二是計算映射和低維嵌入。具體推導如下：

首先將第一個目標函數表示為矩陣形式：

[ phi ( mathbf{W} ) = sum ^{m} _{i=1} left| left| mathbf{x} _{i} – sum _{jin mathbf{Q}(i)} W _{ij} mathbf{x} _{j} right| right| ^{2} ]

[ = sum ^{m} _{i=1} left| left| sum _{jin mathbf{Q}(i)} W _{ij} mathbf{x} _{i} – sum _{jin mathbf{Q}(i)} W _{ij} mathbf{x} _{j} right| right| ^{2} ]

[ = sum ^{m} _{i=1} left| left| sum _{jin mathbf{Q}(i)} W _{ij} ( mathbf{x} _{i} – mathbf{x} _{j} ) right| right| ^{2} ]

[ = mathbf{W} ^{T} _{i} ( mathbf{x} _{i} – mathbf{x} _{j} )( mathbf{x} _{i} – mathbf{x} _{j} ) ^{T} mathbf{W} _{i} ]

[ = sum ^{m} _{i=1} mathbf{W} ^{T} _{i} mathbf{Z} _{i} mathbf{W} _{i} ]

其中 (mathbf{W} _ {i}) 是有樣本 i 的 k 個近鄰點對應的權重係數組成的列向量，矩陣 (mathbf{Z} _ {i} = ( mathbf{x} _ {i} – mathbf{x} _ {j} )( mathbf{x} _ {i} – mathbf{x} _ {j} ) ^{T} ,jin mathbf{Q}(i))。

考慮到歸一化約束，我們再將其約束等式化為矩陣形式：

[ sum _{jin mathbf{Q}(i)} W _{ij} = mathbf{W} ^{T} _{i} mathbf{1} _{k} =1, ]

其中 (mathbf{1} _{k}) 為 k 維全 1 向量。

利用拉格朗日乘子法將矩陣形式得目標函數和約束等式合併為一個目標：

[ mathbf{L} (mathbf{W}) = sum ^{m} _{i=1} mathbf{W} ^{T} _{i} mathbf{Z} _{i} mathbf{W} _{i} + lambda'(mathbf{W} ^{T} _{i} mathbf{1} _{k} – 1). ]

對 (mathbf{W}) 求導並令其值為 0，則：

[ mathbf{W} _{i} = -dfrac{1}{2} lambda mathbf{Z} ^{-1} _{i} mathbf{1} _{k}. ]

利用歸一化約束，對結果進行歸一化，則最終權重矩陣 (mathbf{W} _{i}) 為：

[ mathbf{W} _{i} = dfrac{-dfrac{1}{2} lambda mathbf{Z} ^{-1} _{i} mathbf{1} _{k}}{mathbf{W} ^{T} _{i} mathbf{1} _{k}} ]

[ = dfrac{mathbf{Z} ^{-1} _{i} mathbf{1} _{k}}{mathbf{1} ^{T} _{k} (mathbf{Z} ^{-1} _{i}) ^{T} mathbf{1} _{k}}. ]

得到權重矩陣後，我們就可以來計算降維的映射了。首先定義：

[ z _{i} = y _{i} – sum ^{m} _{j=1} W _{ij} y _{j}, ]

再將上式轉換為矩陣形式：

[ mathbf{z} = mathbf{y} – mathbf{Wy} = (mathbf{I} – mathbf{W}) mathbf{y}. ]

則第二個目標函數可簡化為：

[ Phi(mathbf{y}) = sum ^{m} _{i=1} left( y _{i} – sum ^{m} _{j=1} W _{ij} y _{j} right) ^{2} ]

[ = sum ^{m} _{i=1} (z _{i}) ^{2} ]

[ = mathbf{z} ^{T} mathbf{z} ]

[ = mathbf{y} ^{T} (mathbf{I} – mathbf{W}) ^{T} (mathbf{I} – mathbf{W}) mathbf{y}. ]

由於 NPE 算法是線性降維方法，所以降維後的嵌入可表示為：

[ mathbf{y} ^{T} = mathbf{a} ^{T} mathbf{X}, ]

這裡 (mathbf{y}) 只是 m 個樣本降到一維的嵌入坐標，(mathbf{a})是其對應的映射。

那麼第二個目標函數可進一步表示為：

[ Phi(mathbf{y}) = mathbf{a} ^{T} mathbf{X} (mathbf{I} – mathbf{W}) ^{T} (mathbf{I} – mathbf{W}) mathbf{X} ^{T} mathbf{a} ]

[ = mathbf{a} ^{T} mathbf{X} mathbf{M} mathbf{X} ^{T} mathbf{a}. ]

並且參數空間的嵌入坐標也有約束：

[ mathbf{y} ^{T} mathbf{y} = 1 implies mathbf{a} ^{T} mathbf{X} mathbf{X} ^{T} mathbf{a}. ]

同第一個目標函數的求解，這裡利用拉格朗日乘子法將第二個目標函數和約束條件合併，並對其求導，可得下列的廣義特徵向量問題：

[ mathbf{XMX} ^{T} mathbf{a}=lambda mathbf{XX} ^{T} mathbf{a}. ]

其中 (mathbf{M}) 可由求得的權重矩陣 (mathbf{W}) 得出，那麼上述的廣義特徵向量便可以求解。最後解得的特徵向量，按次序排列便是映射矩陣了。

代碼實現

這裡分別給出 python 和 matlab 的代碼實現。

python

首先創建一個典型的「瑞士卷」數據集：

import numpy    def swissroll(N=1000):      tt = numpy.array((5*numpy.pi/4)*(1+2*numpy.random.rand(N)))      height = numpy.array((numpy.random.rand(N)-0.5))      noise = 0.0      X = numpy.array([(tt+noise*numpy.random.randn(N))*numpy.cos(tt), 10*height, (tt+noise*numpy.random.randn(N))*numpy.sin(tt)])      return X

接着，再利用 shogun 庫來進行 NPE 算法的實現：

import modshogun as sg    # load data  feature_matrix = swissroll()  # create features instance  features = sg.RealFeatures(feature_matrix)    # create Neighborhood Preserving Embedding converter instance  converter = sg.NeighborhoodPreservingEmbedding()    # set target dimensionality  converter.set_target_dim(2)  # set number of neighbors  converter.set_k(10)  # set number of threads  converter.parallel.set_num_threads(2)  # set nullspace shift (optional)  converter.set_nullspace_shift(-1e-6)    # compute embedding with Neighborhood Preserving Projections method  embedding = converter.embed(features)

matlab

至於 matlab 代碼在何曉飛教授的主頁上有，由於篇幅過長，這裡就不貼出來了。