LPP

方法概述

核心思想

• 有映射$\underset{m\ast n}{Y}=f(\underset{d\ast n}{X})$，能够实现将d维的样本变换到m维空间之中
• 假设：对于一个好的降维方法，在高维空间下距离近（相似度高）的两个点，在低维空间下依旧保持相近的关系
• 考虑映射$Y=W^{T}X$，即原样本空间中有$x_i$与$x_j$距离近，$y_i$与$y_j$ ($y_i=W^T{x}_i$)仍保持相近关系

相关定义

• 权重矩阵S：

  • 定义样本$x_i$与$x_j$之间的权重$w_{ij}$，原则是样本点之间距离越小，权重越大

  • 权重矩阵S常用定义方式：
    $$s_{ij}=\{\begin{array}{l}\begin{array}{rlr}& s_{ij}=exp(-\frac{||x_i-x_j|{|}^2}{t})& x_i\in N_k(x_j)即x_i是x_j的k近邻\\ & s_{ij}=0& else\end{array}\end{array}$$

    $$S=\left[\begin{array}{cccc}{s}_{11}& s_{12}& ...& s_{1n}\\ ...& ...& ...& ...\\ s_{n1}& s_{n2}& ...& s_{nn}\end{array}\right]$$

• 度矩阵D：

  • 度矩阵D是一个对角阵，其对角元素$D_{ii}={\sum }_{j=1}^n{s}_{ij}$

  • $$D=\left[\begin{array}{cccc}{\sum }_{j=1}^n{s}_{1j}& 0& ...& 0\\ 0& {\sum }_{j=1}^n{s}_{2j}& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\sum }_{j=1}^n{s}_{nj}\end{array}\right]$$

• 拉普拉斯矩阵L：$L=D-S$

• 有运算：
  $$\begin{array}{rl}YD{Y}^T& =[y_1,y_2,...,y_n]\left[\begin{array}{cccc}{d}_{11}& 0& ...& 0\\ 0& d_{22}& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& d_{nn}\end{array}\right]\left[\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_n^T\end{array}\right]\end{array}$$
  $$=[d_{11y}{y}_1,...,d_{nn}{y}_n]\left[\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_n^T\end{array}\right]$$
  $$=d_{11}{y}_1{y}_1^T+d_{22}{y}_2{y}_2^T+...+d_{nn}{y}_n{y}_n^T$$
  因此有：
  $$tr(YD{Y}^T)=\sum _i^N{d}_{ii}{y}_i^T{y}_i$$
  类似可得：
  $$tr(YS{Y}^T)=\sum _i^N\sum _j^N{s}_{ij}{y}_i^T{y}_j$$

优化目标

• 定义优化目标：
  $$min\sum _i\sum _j||y_i-y_j|{|}^2{s}_{ij}$$
  即在原始空间中近的点（$s_{ij}$大），其在降维后应该尽可能接近（$y_i$与$y_j$距离更小）

方法推导

• 对于LPP方法，有目标：
  $$\underset{W}{argmin}\sum _i\sum _j||y_i-y_j|{|}^2{s}_{ij}$$

• 对于目标：
  $$\begin{array}{rl}& \sum _i^N\sum _j^N||y_i-y_j|{|}^2{s}_{ij}\\ & =\sum _i^N\sum _j^N(y_i^T{y}_i-y_i^T{y}_j-y_j^T{y}_i+y_j^T{y}_j)s_{ij}\\ & =2\sum _i^N{y}_i^T{y}_i{d}_{ii}-2\sum _i^N\sum _j^N{y}_i^T{y}_j{s}_{ij}\\ & =2tr(YD{Y}^T)-2tr(YS{Y}^T)\\ & =2tr(YL{Y}^T)\end{array}$$
  去除乘数，最小化目标为：
  $$tr(YL{Y}^T)$$
  带入$Y=W^{T}X$，得最小化目标：
  $$tr(W^{T}XL{X}^{T}W)$$

• 该目标存在平凡零解：$W=O_{m\ast d}$

  此时L取最小值0，出现维度坍缩，所有样本映射到同一个点上，此解无意义

• 当W不取零矩阵时，由于没有添加尺度约束，在降维子空间一定（组成基向量方向一致）情况下，当尺度不断变小时，目标L会同时变小，无限趋于0，不存在最小值

• 因此，考虑对最小化目标变形为：
  $$\frac{tr(YL{Y}^T)}{tr(YD{Y}^T)}=\frac{tr(W^{T}XL{X}^{T}W)}{tr(W^{T}XD{X}^{T}W)}$$
  考虑到尺度因素，加以约束$YD{Y}^T=I$也即$W^{T}XD{X}^{T}W=I$

• 参考LDA中提到的广义瑞利商，可知：
  $${\lambda }_{min}((XD{X}^T{)}^{-1}(XL{X}^T))\le \frac{tr(W^{T}XL{X}^{T}W)}{tr(W^{T}XD{X}^{T}W)}\le {\lambda }_{max}((XD{X}^T{)}^{-1}(XL{X}^T))$$
  变换矩阵：$W=[w_1,w_2,...,w_m]$由$(XD{X}^T{)}^{-1}(XL{X}^T)$最小m个特征向量构成

• 矩阵形式推导：

  由拉格朗日乘子法，构建L：
  $$L=tr(W^{T}XL{X}^{T}W)-tr(\Lambda (W^{T}XD{X}^{T}W-I))$$
  对W求偏导并令为0：
  $$\begin{gathered} 2XL{X}^{T}W-2XD{X}^{T}W\Lambda =0 \\ XL{X}^{T}W=XD{X}^{T}W\Lambda \\ 有：(XD{X}^T{)}^{-1}XL{X}^{T}W=W\Lambda \end{gathered}$$
  W由$(XD{X}^T{)}^{-1}XL{X}^T$的特征向量作为列向量构成，且为了最小化目标函数，选取的特征向量应该是最小m个特征值对应的特征向量

LPP与PCA

• 对PCA方法，其优化目标为$\underset{W}{\mathrm{argmax}}=tr(W^{T}X{X}^{T}W)$，有约束$W^{T}W=I$

  构建的拉格朗日乘式解：$X{X}^{T}W=W\Lambda$，可变为$X{X}^{T}X{X}^{T}W=X{X}^{T}W\Lambda$

  与LPP对比，是$L=X^{T}X$且$D=I$的特例

• 即PCA可以看成是一种特殊的LPP，区别在于LPP更关注局部关系，而PCA关注的是全局方差信息

方法流程

1）由样本矩阵X构建权重矩阵S，度矩阵D，拉普拉斯矩阵L

2）求$(XD{X}^T{)}^{-1}XL{X}^T$的特征向量，取最小m个作列向量构成变换矩阵W

3）由$Y=W^{T}X$完成降维

参考资料

【1】LPP局部保持投影

【2】局部保留投影(LPP)推导

【3】算法小课堂：Locality Preserving Projections （LPP）