LLE降维

ゝ一纸荒年。 2023-03-13 02:36 13阅读 0赞

LLE 是 Locally Linear embedding  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RIX05VTQ_size_16_color_FFFFFF_t_70]  
直观是在样本点的高维空间相邻近的话，可以用低维的子空间描述。

基本原理分三步：  
（1） 找到邻居 neighbors .(可以使用多种方法，邻居K的数目选择影响很大)  
（2）使用周围的邻居作为基向量， reconstruct with linear weights  
minimize reconstruction error.

m i n W ε ( W ) = ∑ i ∣ ∣ x i − ∑ j ∈ N i W i j x j ∣ ∣ 2 2 \\underset\{W\}\{min\}\\varepsilon (W) = \\sum\_i||x\_i - \\sum\_\{j\\in N\_i\}W\_\{ij\}x\_j||^2\_2 Wminε(W)=∑i∣∣xi−∑j∈NiWijxj∣∣22,

∑ i ∣ ∣ x i − ∑ j ∈ N i W i j x j ∣ ∣ 2 2 = ∑ j ∣ ∣ W i j ( x i − x j ) ∣ ∣ 2 2 = ∑ j k W i j W i k G j k = W i T G W i \\sum\_i||x\_i - \\sum\_\{j\\in N\_i\}W\_\{ij\}x\_j||^2\_2=\\sum\_j||W\_\{ij\}(x\_i-x\_j)||^2\_2=\\sum\_\{jk\}W\_\{ij\}W\_\{ik\}G\_\{jk\}=W\_i^TGW\_i ∑i∣∣xi−∑j∈NiWijxj∣∣22=∑j∣∣Wij(xi−xj)∣∣22=∑jkWijWikGjk=WiTGWi,

G j k = ( x i − x j ) T ( x i − x k ) , ∀ j , k ∈ N i G\_\{jk\}=(x\_i-x\_j)^T(x\_i-x\_k), \\forall j,k \\in N\_i Gjk=(xi−xj)T(xi−xk),∀j,k∈Ni  
使用拉格朗日方法：

2 G W i − λ I = 0 , ∑ j W i j = 1 2GW\_i-\\lambda I=0, \\sum\_jW\_\{ij\}=1 2GWi−λI=0,∑jWij=1

W i = G − 1 I I T G − 1 I W\_i = \\frac\{G^\{-1\}I\}\{I^TG^\{-1\}I\} Wi=ITG−1IG−1I

s . t . ∑ j W i j = 1 , ∀ i s.t. \\sum\_jW\_\{ij\}=1 , \\forall \_i s.t.∑jWij=1,∀i

为了防止G病态多个解，加入二范数  
 m i n W i W i T G W i + γ W i T W i min\_\{W\_i\}W\_i^TGW\_i + \\gamma W\_i^TW\_i minWiWiTGWi\+γWiTWi  
得到  
 2 ( G + γ I ) W i − λ I = 0 2(G+\\gamma I)W\_i - \\lambda I=0 2(G\+γI)Wi−λI=0

W i = ( G + γ I ) − 1 I I T ( G + γ I ) − 1 I W\_i = \\frac\{(G+\\gamma I)^\{-1\}I\}\{I^T(G+\\gamma I)^\{-1\}I\} Wi=IT(G\+γI)−1I(G\+γI)−1I

(3) Map to embedding coordinates  
 m i n Y ϕ ( Y ) = ∑ i ∣ ∣ y i − ∑ j ∈ N i W i j y i ∣ ∣ 2 2 \\underset\{Y\}\{min\}\\phi(Y) = \\sum\_i||y\_i-\\sum\_\{j \\in N\_i\}W\_\{ij\}y\_i||^2\_2 Yminϕ(Y)=∑i∣∣yi−∑j∈NiWijyi∣∣22

对y要做约束，不然有很多解，比如平移。

s . t . ∑ i y i = 0 , 1 N ∑ i y i y i T = I s.t. \\sum\_iy\_i=0, \\frac\{1\}\{N\}\\sum\_iy\_iy\_i^T=I s.t.∑iyi=0,N1∑iyiyiT=I

解决方法拉格朗日方法 ， eigenvalue problem  
 F = 1 2 ∑ i ∣ ∣ y i − ∑ j W i j y j ∣ ∣ 2 2 − 1 2 ∑ α β λ α β ( 1 N ∑ i y i α y i β − δ α β ) F=\\frac\{1\}\{2\}\\sum\_i||y\_i-\\sum\_jW\_\{ij\}y\_j||^2\_2-\\frac\{1\}\{2\}\\sum\_\{\\alpha \\beta\}\\lambda\_\{\\alpha \\beta\}(\\frac\{1\}\{N\}\\sum\_iy\_i\\alpha y\_i \\beta - \\delta\\alpha \\beta) F=21∑i∣∣yi−∑jWijyj∣∣22−21∑αβλαβ(N1∑iyiαyiβ−δαβ)

( 1 − W ) T ( 1 − W ) Y = 1 N Y Λ , w h e r e Λ α β = λ α β (1-W)^T(1-W)Y = \\frac\{1\}\{N\}Y\\Lambda, where \\Lambda\_\{\\alpha \\beta\} = \\lambda \_\{\\alpha \\beta\} (1−W)T(1−W)Y=N1YΛ,whereΛαβ=λαβ

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RIX05VTQ_size_16_color_FFFFFF_t_70]: /images/20230312/ebf5f01b82974adc905b914e28c9db82.png