LLE降维

LLE 是 Locally Linear embedding

直观是在样本点的高维空间相邻近的话，可以用低维的子空间描述。

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

$\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∈Ni​​Wij​xj​∣∣22​,

$\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∈Ni​​Wij​xj​∣∣22​=∑j​∣∣Wij​(xi​−xj​)∣∣22​=∑jk​Wij​Wik​Gjk​=WiT​GWi​,

$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​
使用拉格朗日方法：

$2GW_i-\lambda I=0, \sum_jW_{ij}=1$2GWi​−λI=0,∑j​Wij​=1

$W_i = \frac{G^{-1}I}{I^TG^{-1}I}$Wi​=ITG−1IG−1I​

$s.t. \sum_jW_{ij}=1 , \forall _i$s.t.∑j​Wij​=1,∀i​

为了防止G病态多个解，加入二范数
$min_{W_i}W_i^TGW_i + \gamma W_i^TW_i$minWi​​WiT​GWi​+γWiT​Wi​
得到
$2(G+\gamma I)W_i - \lambda I=0$2(G+γI)Wi​−λI=0

$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
$\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∈Ni​​Wij​yi​∣∣22​

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

$s.t. \sum_iy_i=0, \frac{1}{N}\sum_iy_iy_i^T=I$s.t.∑i​yi​=0,N1​∑i​yi​yiT​=I

解决方法拉格朗日方法 ， eigenvalue problem
$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​−∑j​Wij​yj​∣∣22​−21​∑αβ​λαβ​(N1​∑i​yi​αyi​β−δαβ)

$(1-W)^T(1-W)Y = \frac{1}{N}Y\Lambda, where \Lambda_{\alpha \beta} = \lambda _{\alpha \beta}$(1−W)T(1−W)Y=N1​YΛ,whereΛαβ​=λαβ​